Introduktion til Kryptering

Report
INTRODUKTION TIL KRYPTERING
Introduktion, substitution
HVAD ER KRYPTERING?
• Egentlig hedder området Kryptologi
• Består af
• Kryptografi (fra græsk: ”skjule tekst”) – at omforme
information fra noget forståeligt til noget uforståeligt (kodet),
som kan gendannes til noget forståeligt ved hjælp af en
metode og en nøgle
• Krypto-analyse – at forsøge på at afkode kodet information
uden adgang til metode og/eller nøgle
HVAD ER KRYPTERING?
• To generelle situationer, kryptering kan hjælpe os med:
• Vi besidder noget data, f.eks. et dokument på en harddisk,
som vi ikke ønsker andre skal kunne læse
• Vi besidder noget data, og vil gerne kommunikere dette data
til en anden person, uden at andre kan opsnappe og afkode
data undervejs
HVAD ER KRYPTERING?
Jeg vil fortælle Lis
en hemmelighed
Jeg vil gerne kende
den hemmelighed
HVAD ER KRYPTERING? – OPGAVE 1
• Hvordan kan Bo sikre sig, at Lis får hemmeligheden
(beskeden) at vide, uden at John opsnapper beskeden
undervejs?
• Tænk over, hvordan dette kan gøres i følgende
scenario (og hvad sårbarhederne er):
• Teknik på middelalder-niveau
• Bo og Lis er geografisk adskilt
• Intet organiseret postvæsen eller lignende
HVAD ER KRYPTERING?
• Hvordan kan Bo sikre sig, at Lis får hemmeligheden
(beskeden) at vide, uden at John opsnapper beskeden
undervejs?
• Fortælle beskeden ”direkte” til Lis (mund-til-øre)
• Fortælle beskeden til en tredjepart, som rejser hen til Lis, og
fortæller hende beskeden direkte
• Putte beskeden i en sikker beholder, som kun Lis kan åbne
• Skrive beskeden i et sprog, som kun Lis forstår
HVAD ER KRYPTERING?
• Fortælle beskeden direkte til Lis
• Fordele
• Simpelt – intet ekstra arbejde
• Ulemper
• Kræver at Bo og Lis mødes IRL
HVAD ER KRYPTERING?
• Fortælle beskeden til en tredjepart (kurér), som rejser
hen til Lis, og fortæller hende beskeden direkte
• Fordele
• Bo og Lis behøver ikke mødes
• Stadig ret simpel metode
• Ulemper
• Kræver en kurér som Bo og Lis kan stole på
• Hvad hvis tredjepart fanges, tortureres, m.v….?
HVAD ER KRYPTERING?
• Putte beskeden i en sikker beholder, som kun Lis kan
åbne
• Fordele
• Bo og Lis behøver ikke mødes
• Besked kan sendes med ”usikker” transport
• Ulemper
• Hvornår er en beholder sikker?
• Hvordan får Lis nøglen til beholderen?
HVAD ER KRYPTERING?
• Skrive beskeden i et sprog, som kun Lis forstår
• Fordele
• Bo og Lis behøver ikke mødes
• Ingen brug for sikker beholder
• Besked kan sendes med ”usikker” transport
• Ulemper
• At ”forstå” et sprog kan kræve en eller anden form for nøgle
• Kræver arbejde at omforme besked
HVAD ER KRYPTERING?
• Vi fokuserer på sidste mulighed – omformning
(kryptering) af beskeden, så kun Lis kan forstå den
• En kryptering består af to komponenter
• En metode
• En nøgle
• Metoden kan være kendt (offentlig), men nøglen må
kun være kendt af Lis og Bo (privat)
HVAD ER KRYPTERING?
• Eksempel på kryptering
• Metode: Oversættelse til andet sprog
• Nøgle: Spansk
• Metode: Hvert bogstav erstattes med en talkode
• Nøgle: Tabel, som viser hvilken talkode hvert bogstav skal
oversættes til
• Kryptering, hvor nøglen er privat, kaldes generelt for
Private Key Kryptering
PRIVATE KEY KRYPTERING
• Behov for kryptering næsten fra civilisationens start
• Klassisk eksempel – udveksling af informationer til brug
i krigsførelse
• En af de første navngivne metoder til kryptering er
Cæsars kryptering
• Et eksempel på såkaldt monoalfabetisk substitution
CÆSARS KRYPTERING
• Yderst simpelt princip – udskift hvert bogstav med det
næste bogstav i alfabetet
• Man ”roterer” alfabetet én plads:
CÆSARS KRYPTERING
• Selv om metoden er meget simpel, bliver en tekst
alligevel ganske uforståelig:
• HEJ LIS, DIN SO bliver til IFK MJT, EJO TP
• Den ukodede tekst kaldes klarteksten
• Den kodede tekst kaldes kodeteksten
• ”Tekst” kan også være lyd, video, m.v..
CÆSARS KRYPTERING
• Lidt mere generel version – alfabetet roteres N pladser
• Rotation af alfabet er metoden
• Antal pladser N er nøglen
• Eksempel (N = 3)
CÆSARS KRYPTERING – OPGAVE 2
A. Kryptér sætningen ”Jeg går igen” med N = 2
B. Dekryptér sætningen ”Mhj hu wloedjh” med N = 3
C. Sværere: Med hvilken nøgle (værdi af N) er følgende
sætning krypteret: ”Wtmw qiwx qip”?
• Svar A: ”Lgi ibt kigp”
• Svar B: ”Jeg er tilbage”
• Svar C: N = 4
CÆSARS KRYPTERING
• I vore øjne ser denne metode alt for simpel ud
• Hvorfor kunne den virke?
• Kun få kunne læse/skrive i det hele taget
• Lavere intellektuelt niveau generelt
• Besked sikkert beskyttet på anden vis
CÆSARS KRYPTERING - PROBLEMER
• Cæsars kryptering – og monoalfabetisk substitution i
det hele taget – er ret let at bryde.
• Ganske få nøgler, N <= 26
• Brute force: prøv alle mulige nøgler af
• En krypto-analytiker kunne også benytte ligvistisk
analyse
CÆSARS KRYPTERING - PROBLEMER
• Problem – et givent bogstav bliver altid udskiftet med
det samme bogstav
• I normal tekst forekommer de enkelte bogstaver med
forskellig frekvens
CÆSARS KRYPTERING - PROBLEMER
Frekvens af bogstaver
i engelsk tekst
CÆSARS KRYPTERING - PROBLEMER
• Monoalfabetisk substitution ændrer bogstaverne, men
selve frekvensmønsteret bevares!
• Giver mulighed for kvalificerede gæt på substitution
• Hvis Z forekommer oftest, betyder Z nok E eller T
• …og så videre
• Kan foretage tilsvarende analyser af endelser, tobogstavs ord, dobbelt-konsonanter, med videre
VIGENÉRES KRYPTERING
• Efterhånden brug for mere kompleks kryptering
• Franskmanden Vigenére opfandt (lagde navn til) en
metode baseret på polyalfabetisk substitution
• Ikke kun en enkelt mulighed for substitution, men en
hel tabel med 26 muligheder
VIGENÉRES KRYPTERING
VIGENÉRES KRYPTERING
• Princip – der skiftes hele tiden mellem de 26 mulige
substitutioner
• Rækkefølgen der skiftes mellem substitutionerne i
udgør nøglen!
• En nøgle kan f.eks. være 1, 5, 8, 11, 14
• Første substitution benytter række 1, så række 5, osv,
indtil der startes med række 1 igen
VIGENÉRES KRYPTERING
VIGENÉRES KRYPTERING – OPGAVE 3
A. Kryptér sætningen ”Jeg går igen” med nøglen
(2,4,3,6,11), dansk alfabet incl. w
B. Dekryptér sætningen ”Jfw nv mfinpkhy” med nøglen
(2,1,5,9,4), dansk alfabet incl. w
C. Sværere: Med hvilken nøgle er følgende sætning
krypteret: ”rsø qk sieøe”?
VIGENÉRES KRYPTERING – OPGAVE 3
A. Svar: ”Lij mkt mjky”
B. Svar: ”Her er kedeligt”
C. Svar: Nøglen er (3,0,8,2,4), giver ”ost og pizza”
VIGENÉRES KRYPTERING
• Hvorfor er Vigenéres metode bedre end Cæsars?
• Samme bogstav i klarteksten kan blive udskiftet med
forskellige bogstaver i kodeteksten
• Forskellige bogstaver i klarteksten kan blive udskiftet med
samme bogstav i kodeteksten
• Frekvensmønsteret bliver kraftigt udvandet
VIGENÉRES KRYPTERING
• Desuden stiger antallet af mulige nøgler drastisk i
Vigenéres metode
• Antal mulige nøgler i Cæsars metode: 26
• Hvis der anvendes fem substitutioner i Vigenéres
metode, bliver antal mulige nøgler: 265 > 10,000,000
• Helt uoverkommeligt at knække med brute force – før
computeren…

similar documents