Cæsarchiffer

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
Illustrasjon av cæsarchiffer, her med den klassiske forskyvningen på tre plasser i alfabetet.

Innen kryptografi er Cæsarchiffer, også kjent som Caesars chiffer, skiftchiffer, Cæsars kode og Cæsarskift, en av de enkleste og mest kjente krypteringsteknikker. Det er en type substitusjonschiffer der hver bokstav i klarteksten erstattes med en annen bokstav et gitt antall steg lenger ut i alfabetet. Med et skift på tre steg erstattes A med D, B blir E og så videre. Metoden har navn etter Julius Cæsar som benytten denne koden til å kommunisere med sine generaler.

Selv om Cæsarchiffer er meget enkelt, så inngår det likevel ofte i mer komplekse krypteringsstrukturer som Vigenère chiffer. En finner det også igjen i moderne anvendelser som ROT13. Cæsarchiffer i seg selv, som et monoalfabetisk substiusjonschiffer er i dag et meget enkelt system å bryte og gir ingen kommunikasjonssikkerhet. Det egner seg imidlertid til en første introduksjon til kryptering

Eksempel[rediger | rediger kilde]

Transformasjonen kan lett gjennomføres ved å stille opp to alfabet: det ene representerer klarteksten, det andre er forskjøvet, eller rotert, og representerer chifferteksten. I eksempelet under er forskyvningen 3 plasser. Parameteren som angir antall skift, her 3, fungerer som nøkkel.

Klartekst:      ABCDEFGHIJKLMNOPQRSTUVWXYZ
Chiffertekst:   DEFGHIJKLMNOPQRSTUVWXYZABC

Under chifrering leter en opp den aktuelle klartekstbokstaven i øvre linje og erstatter den med bokstaven under. Ved dechifrering går en motsatt fra nedre linje til den øvre.

Klartekst:     WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
Chiffertekst:  the quick brown fox jumps over the lazy dog

Chifreringen kan også gjøres ved å benytte modulær aritmetikk. Først erstattes alle bokstaver med tall etter følgende oppsett: A = 0, B = 1,..., Z = 25.[1]


Chifrering av en klartekstbokstav P med en forskyvning på K tegn i et alfabet med 26 tegn er da gitt ved:[2]

\text{encrypt}_K(P) = (P + K) \mod {26}

Tilsvarende uttrykkes dechifreringen av en hemmelig bokstav C:

\text{decrypt}_K(C) = (C - K) \mod {26}


(Det er noe forskjellige definisjoner av modulo operationen. I eksempelet over har en antatt et alfabet med 26 karakterer, altså at svaret skal ligge i området 0...25. I.e., hvis x+n eller x-n ikke ligger i området 0...25, må en trekke fra eller legge til 26.)

Forskyvningen er her den samme gjennom hele meldingen. Dermed klassifiseres Cæsarchiffer som et enkelt substitusjonschiffer i motsetning til et polyalfabetisk chiffer.

Historikk og bruk[rediger | rediger kilde]

Cæsarchifferet har navn etter Julius Caesar, som benyttet dette chifferet med en venstreforskyvning på tre.


Cæsarchiffer har navn etter den romerske keiser Julius Cæsar som, i følge Suetonius, brukte det med et skift på tre steg for å beskytte militære meldinger. En kjenner også til at substitusjonschiffer også er anvendt enda tidligere.

Sitat Skulle han meddele noe konfidensielt så skrev han i kode, det vil si ved å endre rekkefølgen på bokstavene i alfabetet slik at intet ord kunne forstås. Hvis noen ønsker å dekode dette og få frem meningen, så må han erstatte den fjerde bokstaven i alfabetet, nemlig D med A og så videre for de resterende. Sitat
Suetonius

Hans nevø, Augustus, brukte også et slikt chiffer, men med en forskyvning på én:

Sitat Alltid, når han skrev i kode, så skrev han B for A, C for B og de øvrige bokstavene på samme måte. For X brukte han AA. Sitat
Suetonius

Det er også indikasjoner på at Julius Cæsar også benytter mer kompliserte systemer.[3] En annen nedtegnelse fra Aulus Gellius referer til ??? and one writer, , refers to a (now lost) treatise on his ciphers:

Sitat There is even a rather ingeniously written treatise by the grammarian Probus concerning the secret meaning of letters in the composition of Caesar's epistles. Sitat
Aulus Gellius

Det ukjent om Cæsarchiffer var en tilstrekkelig sikker for sin tid, men en kan anta at den var rimelig sikker. Dette fordi motstanderen både måtte være lesekyndig, kjenne latinsk språk og ikke forveksle koden med en melding skrevet i et annet fremmed språk.[4] En har ikke funnet noen beskrivelse fra den tid som angir noen teknikk for å løse selv et så enklet chiffer som et monoalfabetisk substitusjonschiffer. Den første kjente nedtegnelsen etter Al-Kindi er fra det 9. århundre som omtaler arabernes oppdagelse av frekvensanalyse[5]

På baksiden av Mezuza er det vanlig å finne «כוזו במוכסז כוזו» som er et Cæsarchiffer med et skift på én. Ordene er hentet fra Shemas 3. 4. og 5. ord: Adonai, Eloheinu, Adonai, "Herren, vår Gud, Herren". Dette kan være en reminisens fra tidlig tid da jødene da Mezuza var forbudt.[6]

Under Personlig-spalten i fant en i det 19. århundre tidvis beskjeder som var kryptert med enkle krypteringsmetoder. Kahn beskriver forekomster der forelskede par har benyttet cæsarchiffer i The Times.[7] Endog så sent som i 1915 ble cæsarchiffer benyttet: Den russiske arme tok det i bruk i stedet for sikrere, men mer kompliserte metoder - metoder som viste seg å være for vanskelig for de russiske troppene å beherske. Tyske og australske kryptoanalytikere hadde dermed lite problemer med å dechifrere de russiske meldingene.[8]

Cæsarchiffer kan en forstatt finne i leketøy slik som i hemmelige dekoderringer. Cæsarchifrering med et skift på tretten finnes i ROT13 algoritmen som en enkel måte å «skjule» informasjon i Usenet. En kan også finne det i form av tilsløring av poenget i en spøk eller for å gjøre det noe vanskeligerere å avdekke en spoiler, men cæsarchiffer er ingen reell måte å kryptere en melding på.[9]

Vigenère cipher bruker en utvidelse av cæsarchiffer. Her legges det inn et nytt skift for hver boksatv som skal kodes. Skiftlengden styres av et repetert kodeord, en nøkkel. Dersom lengden av kodeordet er like lang som meldingen selv og i seg selv en tilfeldig rekkefølge av bokstaver, ikke blir avslørt og benyttes kun en gang, så er dette et chiffer med en engangsnøkkel. Et slikt chiffer er uknekkelig. Å gjennomføre en slik kryptering i praksis er imidlertid nær uoppnåelig. Dersom det benyttes et kodeord som er kortere enn meldingen vil dette kunne introdusere sykliske mønster som kan avsløres med avanserte statisktiske metoder innen frekvensanalyse.[10]

I april 2006 ble mafia sjefen Bernardo Provenzano avslørt og arrestert i sitt skjulested på Sicilia. Dette delvis på bakgrunn av at noen av hans meldinger ble snappet opp. De var skrevet i en form for cæsarchiffer. Provenzano erstattet bokstavene med tall slik at en "A" ble erstattet med "4", "B" med "5" osv.[11]

I 2011 ble Rajib Karim dømt i Storbritannia for planlegging av terror etter at han hadde kommunisert med islamske aktivister i Bangladesh der de hadde diskutert anslag for å sprenge fly fra British Airways og å forstyrre deres datanettverk. Selv om gruppen hadde tilgang til metoder med en betydelig høyere sikkerhet, valgte de å bruke sitt eget chiffer implementert i Microsoft Excel. Karim benyttet selv PGP for å lagre informasjon på sin egen harddisk, men «siden dette chifferet var kjent av 'kaffir'er, eller ikke-troende, ville dette chifferet være mindre sikkert».[12]

Knekke krypteringen[rediger | rediger kilde]

Dekrypterings
skift
Mulig klartekst
0 exxegoexsrgi
1 dwwdfndwrqfh
2 cvvcemcvqpeg
3 buubdlbupodf
4 attackatonce
5 zsszbjzsnmbd
6 yrryaiyrmlac
...
23 haahjrhavujl
24 gzzgiqgzutik
25 fyyfhpfytshj

Et cæsarchiffer kan enkelt knekkes, endog om en kun har tilgang til chiffertekst. To situasjoner er tenkbare:

  1. angriperen vet, eller gjetter, at det er benyttet et eller annet slags substiusjonschiffer, men vet ikke om dette er et cæsarchiffer eller noe annet,
  2. angriperene vet at det er et cæsarchiffer, men kjenner ikke hvilket skift, hvilken nøkkel, som er benyttet.

Det første tilfellet er det vanskeligste. Gitt at en har tilgang til tilstrekkelig med chifrert tekst kan en benytte frekvensanalyse på bokstaver og på ord.[13] Ut fra resultatene er det trolig at analytikeren snart innser at chfferet trolig er et cæsarchiffer.

Hyppigheten av de enkelte bokstaver i et avsnitt med typisk engelsk tekst. Denne har en distinkt fordeling, typisk for språket. Et cæsarchiffer vil flytte stolpene et gitt antall steg til høyre eller venstre.

I det andre tilfellet over er det trivielt å knekke chifferet. Siden det er et begrenset antall skift som er mulig (26 i engelsk, 29 i norsk og 24 i latin), kan en enkelt gjennomføre et brute force angrep.[14]

En måte å gjennomføre dette på er å skrive ut en utsnitt av chifferteksen i en tabell med alle mulige skift.[15] [16] I eksempelet er benyttet chifferteksten "EXXEGOEXSRGI". Ved å lete ned gjennom tabellen finner en straks at med et skift på fire får en en meningsfull klartekst: attackatonce (angripumiddelbart). En annen tilnærming er å skrive ut alfabetet på papirremser. Remsene organiseres vertikalt og forskyves slik at en i en av linjene stiller inn chifferteksten. I en av de andre linjene vil da klarteksten fremkomme.

En annen brute forcemetode er å benytte freksvensanalyse. Ved å tegne et stolpediagram av forekomsten av de enkelte bokstavene i chifferteksten og sammenligne dette diagrammet med et tilsvarende diagram for forekomsten av bokstavene i klartekstspråket vil en umiddelbart se hvilken forskyvning som er benyttet. For eksempel i engelsk språk er bokstavene E og T de som med høyest forekomst, mens Q og Z opptrer sjeldent.[17]

Datamaskiner kan enkelt programmeres til å gjøre slike sammenligninger.[18]

I de flese tilfeller vil en nær umiddelbart finne den mest plausibel klarteksten, dog kan særlig korte meldinger gi tvetydighet som: MPQY kan bety "aden" or "know (gitt at klarteksten er i engelsk). Med tilgang til mer chiffertekst vil denne usikkerheten forsvinne.

I mange chiffer vil en kunne øke sikkerheten ved å gjenta gjennomløpe krypteringen flere ganger. Dette fordi en førte chifrering med skift shift n og deretter en ny chifrering med skift m vil tilvare en enkelt chifrering med n + m.[19]

Referanser[rediger | rediger kilde]

  1. ^ Luciano, Dennis; Gordon Prichett (januar 1987). «Cryptology: From Caesar Ciphers to Public-Key Cryptosystems». The College Mathematics Journal, 18 (1), s. 2–17. doi:10.2307/2686311. JSTOR 2686311. 
  2. ^ Wobst s. 19
  3. ^ Reinke, Edgar C. (desember 1992). «Classical Cryptography». The Classical Journal, 58 (3), s. 114. 
  4. ^ Pieprzyk, Josef; Thomas Hardjono, Jennifer Seberry (2003). Fundamentals of Computer Security. Springer. s. 6. ISBN 3-540-43101-2. 
  5. ^ Sing s. 14-20
  6. ^ Alexander Poltorak. «Mezuzah and Astrology». chabad.org. Besøkt 13. juni 2008. 
  7. ^ Kahn (1967) s. 775-6
  8. ^ Kahn (1967) s. 631-2
  9. ^ Wobst s. 20
  10. ^ Kahn (1967)
  11. ^ Leyden, John (19. april 2006). «Mafia boss undone by clumsy crypto». The Register. Besøkt 13. juni 2008. 
  12. ^ «BA jihadist relied on Jesus-era encryption». The Register. 22. mars 2011. Besøkt 1. april 2011. 
  13. ^ Beutelspacher, Albrecht (1994). Cryptology. Mathematical Association of America. s. 9–11. ISBN 0-88385-504-6. 
  14. ^ Beutelspacher, Albrecht (1994). Cryptology. Mathematical Association of America. s. 8–9. ISBN 0-88385-504-6. 
  15. ^ Leighton, Albert C. (april 1969). «Secret Communication among the Greeks and Romans». Technology and Culture, 10 (2), s. 139–154. doi:10.2307/3101474. JSTOR 3101474. 
  16. ^ Sinkov, Abraham; Paul L. Irwin (1966). Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America. s. 13–15. ISBN 0-88385-622-0. 
  17. ^ Singh s. 72-77
  18. ^ Savarese, Chris; Brian Hart (15. juli 2002). «The Caesar Cipher». Besøkt 16. juli 2008. 
  19. ^ Wobst s. 31

Bibliografi[rediger | rediger kilde]

Eksterne lenker[rediger | rediger kilde]