Engangsnøkkel

Engangsnøkkel eller one-time pad (OTP) er innen kryptografi en krypteringsalgoritme hvor klarteksten blir satt sammen med en tilfeldig nøkkel eller «pad» som er like lang som klarteksten, og blir benyttet kun en gang. En modulær addering blir brukt for å sette sammen klarteksten med nøkkelen. (For binære data, så gjør operasjonen XOR det samme.) Engangsnøkkelen ble oppfunnet i 1917 og ble patentert i 1919. Hvis nøkkelen er virkelig tilfeldig, aldri benyttet om igjen, og holdt hemmelig, så er engangsnøkkelen perfekt for å hemmeligholde informasjon. Det har også blitt bevist at ethvert chiffer som skal ha perfekt sikkerhet, må bruke nøkler med samme krav som engangsnøkler. Nøkkelen består som regel av en tilfeldig strøm av tall, hvor hvert av tallene indikerer hvor mange plasser i alfabetet (eller tallrekken, hvis klarteksten er i numerisk form) man skal skifte tilsvarende bokstav eller tall i klarteksten. For meldinger i det norske alfabetet, så vil nøkkelen bestå av en tilfeldig rekke av tall mellom 0 og 29; for binære meldinger vil nøkkelen bestå av en tilfeldig rekke av 0-er og 1-ere, og så videre.
Til å begynne med ble engangsnøkler distribuert på papir, ofte som en blokk med ark, slik at det øverste arket kunne rives av og ødelegges etter bruk. For enkelt å kunne skjule en slik blokk, så kunne den lages så liten at det kunne være nødvendig å bruke forstørrelsesglass for å lese den. Bilder tilgjengelig på internett viser blokker som har blitt tatt fra KGB som er så små at de får plass i håndflaten, eller i et valnøttskall. For å øke sikkerheten ble blokkene i blant laget av brannfarlig materiale slik som nitrocellulose.
Engangsnøkkelen er derivert av Vernams chiffer, navngitt etter Gilbert Vernam, en av oppfinnerne. Vernams system var et chiffer som satt sammen en melding med en nøkkel som ble lest av en papirremse som sto i en løkke. I den originale formen var ikke Vernams system uknekkbart fordi nøkkelen kunne bli gjenbrukt. Engangsbruken kom litt senere når Joseph Mauborgne forsto at om nøkkelremsen var totalt vilkårlig, så ville den kryptoanalytiske vanskelighetsgraden øke.
Det eksisterer tvetydige betegnelser som er grunnet i at noen forfattere bruker uttrykket «Vernam chiffer» som et synonym for «engangsnøkkel», der hvor andre viser til enhver additiv flytchiffer som et «Vernam chiffer», inkludert de som er basert på kryptografisk sikre pseudovilkårlige nummergeneratorer.

Historie

Engangsnøkkelens historie er preget av fire forskjellige, men tett forbundete oppdagelser.
Det første engangsnøkkelsystemet var elektronisk. I 1917 oppfant Gilbert Vernam hos AT&T et chiffer basert på teletype maskinteknologi. Dette ble senere patentert i 1919. Hver karakter i en melding ble elektronisk satt sammen med en karakter fra en papirremse (nøkkel). Kaptein Joseph Mauborgne forstod at om sekvensen av karakterer på nøkkelremsen kunne være totalt vilkårlig, så ville en kryptoanalyse av resultatet være meget vanskelig. Sammen fant de opp det første engangsnøkkel remsesystemet.
Den andre utviklingen var papirblokksystemet. Diplomater hadde lenge brukt koder og chiffer for konfidensialitet og for å minimere telegrafikostnader. Som koder ble ofte ord eller fraser konvertert til nummergrupper (typisk 4 eller 5 siffer) ved å bruke en slags ordliste, eller kodebok. For å øke sikkerheten så kunne et hemmeligholdt nummer bli satt sammen med (vanligvis modulær addisjon) hver kodegruppe før forsendelse. Det hemmelige nummeret ble endret ved jevne mellomrom (dette kalles dobbeltkryptering). På begynnelsen av 1920-tallet så innså tre tyske kryptografer, Werner Kunze, Rudolf Shauffler og Erich Langlotz, som var involvert i oppgaven med å knekke slike systemer, at om hver kodegruppe ble dobbeltkrytpert med et helt tilfeldig nummer så kunne meldingen aldri dekrypteres. De brukte et par identiske papirblokker som hadde bli påtrykt linjer med tilfeldige nummergrupper. Hver side hadde et serienummer og 8 linjer. Hver linje hadde 6 femsifrede nummer. En side ble brukt som et arbeidsark for å kryptere en melding, og deretter tilintetgjort. Serienummeret ble sendt sammen med den krypterte meldingen. Mottageren ville så reversere prosedyren, og deretter ødelegge hans versjon av siden. Det tyske utenriksdepartementet satt systemet i drift i 1921.
En tredje variant var å bruke en blokk engangsnøkler basert på bokstaver, som ble brukt til å kryptere klartekst direkte, slik som neste eksempel vil vise. Leo Marks har beskrevet hvordan en slikt system ble oppfunnet for de britiske Special Operations Executive (SOE) under den andre verdenskrig, selv om han på det tidspunktet mistenkte at metoden allerede var kjent i den lukkede verden av kryptografi, som for eksempel på Bletchley Park.
Den siste eksempelet på oppdagelse ble gjort av Claude Shannon på 1940-tallet. Han innså og beviste den teoretiske betydningen av et engangsnøkkelsystem. Shannon leverte sine funn og resultaet i en hememligstemplet rapport i 1945, og publiserte disse offentlig i 1949. På samme tid, men helt uavhengig, hadde Vladimir Kotelnikov bevist absolutt sikkerhet hos engangsnøkler. Hans resultatet ble levert i en rapport i 1941 som tydeligvis fremdeles er hemmeligstemplet.

Eksempel

Gitt at Kari ønsker å sende meldingen «HELLO» til Ola. Gå ut fra at to arkblokker med identiske vilkårlige sekvenser av bokstaver har blitt laget forut for dette, og at Kari og Ola har fått hvert sitt eksemplar av dette arket. Kari velger ut et ubrukt ark fra blokken. Metoden for å gjøre dette er ofte avtalt på forhånd, eksempelvis «bruk det tolvte arket på skjærtorsdag» eller «bruk det neste tigjengelige arket for neste melding». Teksten på det valgte arket er nøkkelen for denne meldingen. Hver bokstav fra arket vil bli satt sammen på en forhåndsbestem måte med hver bokstav i meldingen. Det er vanlig, men ikke påkrevet, å gi hver bokstav en numerisk verdi: eksempelvis så kan «A» være 0, «B» være 1 og så videre til alfabetet er slutt. I dette eksempelet så vil metoden i bruk være å sette sammen nøkkelen og meldingen ved å bruke modulær addisjon. De numeriske verdiene av bokstavene i meldignen og bokstavene i nøkkelen blir lagt sammen, modulus 26 (utgangspunktet her er et engelsk alfabet). Om nøkkelmaterialet begynner med
X M C K L
og meldingen er «HELLO», så kan krypteringen bli gjort som følger:
   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) melding
+ 23 (X)  12 (M)   2 (C)  10 (K)  11 (L) nøkkel
= 30      16      13      21      25     melding + nøkkel
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) melding + nøkkel (mod 26) >> chiffertekst
Merk at om et nummer er større enn 25, så vil man, i modulær aritmetikk, bruke det som er igjen etter at man har trukket fra 26. Enkelt sagt så vil det si at hvis du går forbi «Z», begynn på «A» igjen.
Chifferteksten som skal sendes til Ola er «EQNVZ». Ola brukes sin kopi av tilsvarende ark på blokka, og gjennomfører den samme prosedyren, bare omvendt, for å finne klarteksten. Her blir nøkkelen subtrahert fra chifferteksten, igjen ved å bruke modulær aritmetikk:
    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciffertekst
–  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) nøkkel
= -19       4      11      11      14     chiffertekst – nøkkel
=   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) chiffertekst – nøkkel (mod 26) >> melding
På samme måte som over, om et tall blir negativt, legg til 26 for å gjøre tallet positivt.
På denne måten så får Ola frem Karis melding «HELLO». Både Kari og Ola ødelegger arket umiddelbart etter bruk, slik at det ikke skal bli gjenbrukt og dermed forhindre et angrep på chifferet.

Sikkerhet

Engangsnøkler er informasjonsteoretisk sikre, basert på at den krypterte meldingen (chifferteksten) ikke gir en kryptoanalytiker noen informasjon om den opprinnelige meldingen bortsett fra lengden på meldingen. Dette er en veldig sterk indikator på sikkerheten, som først ble utviklet under den annen verdenskrig av Claude Shannon, og matematisk bevist av ham ved bruk av engangsnøkler omtrent på samme tid. Hans resultater ble publisert i Bell Labs Technical Journal i 1949. Ved korrekt bruk så vil engangsnøkler være informasjonsteoretisk sikre selv mot angripere med ubegrenset prosesseringskraft. For å fortsette eksemplet ovenfor: Gitt at Eva har fått tak i Karis krypterte melding «ENQVZ». Om Eva hadde hatt ubegrenset prosesseringskraft, så ville hun raskt ha funnet at nøkkelen «XMCKL» ville produsert klarteksten «HELLO», men hun ville også finne at nøkkelen «TQURI» ville produsert klarteksten «LATER», som er en like sannsynlig klartekst:
    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) chiffertekst
−  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) mulig nøkkel
= −15       0      −7       4      17     chiffertekst-nøkkel
=  11 (L)   0 (A)  19 (T)   4 (E)  17 (R) chiffertekst-nøkkel (mod 26)
Det er mulig å «dekryptere» chifferteksten hvilken som helst melding med det samme antall bokstaver ved å bruke forskjellige nøkler, og det finnes ingen informasjon i chifferteksten som setter Eva i stand til å velge blant de forskjellige mulige resultatene.
Konvensjonelle symmetriske krypteringsalgoritmer bruker komplekse mønstre av substitusjon og transponeringer. For de beste av disse som er bruk i dag så er det ikke kjent om det finnes en kryptoanalytisk prosedyre som kan reversere helt eller delvis disse mønstrene uten å kjenne nøkkelen som ble brukt under krypteringen. Asymmetriske krypteringsalgoritmer bruker matematiske utfordringer som er ansett som umulige å løse, slik som heltallsfaktorisering eller diskrete logaritmer. Det finnes dog ikke bevis på at disse utfordringene er uløselige, og matematiske gjennombrudd kan gjøre eksisterende systemer sårbare for angrep.