Eingongslykel

Utdrag frå ein eingongslykelblokk.

Eingongslykel eller one-time pad (OTP) er innan kryptografi ein krypteringsalgoritme der klarteksta vert sett saman med ein tilfeldig lykel eller «pad» som er like lang som klarteksta, og vert nytta berre ein gong. Ein modulær addering vert brukt for å setja saman klarteksta med lykelen. (For binære data, så gjer operasjonen XOR det same.) Eingongslykelen vart oppfunne i 1917 og vart patentert i 1919. Viss lykelen er verkeleg tilfeldig, aldri nytta om att, og halde løynleg, så er eingongslykelen perfekt for å hemmeligholde informasjon. Det har òg vorte bevist at kvart og eit chiffer som skal ha perfekt tryggleik, må bruka nøklar med dei same krav som eingongsnøkler. Lykelen består som regel av ein tilfeldig straum av tal, der kvart av tala indikerer kor mange plassar i alfabetet (eller talrekkja, viss klarteksta er i numerisk form) ein skal skifta tilsvarande bokstav eller tal i klarteksta. For meldingar i det norske alfabetet, så vil lykelen bestå av ei tilfeldig rekkje av tal mellom 0 og 29, for binære meldingar vil lykelen bestå av ei tilfeldig rekkje av 0'er og 1'ere, og så vidare.

Til å byrja med vart eingongslyklar distribuert på papir, ofte som ei blokk med ark, slik at det øvste arket kan rivast av og øydeleggjast etter bruk. For enkelt å kunna skjula ein slik blokk, så kunne den verta så laga liten at det kunne vera naudsynt å bruka forstørrelsesglass for å bruka den. Bilete tilgjengeleg på internett viser blokker som har vorte teke frå KGB som er så små at dei får plass i handflata, eller i eit valnøttskall. For å auka tryggleiken så vart blokkene i blant laget av brannfarleg material slik som nitrocellulose.

Eingongslykelen er derivert av Vernams chiffer, namngjeve etter Gilbert Vernam, ein av oppfinnarane. Vernams system var eit chiffer som sett saman ei melding med ein lykel som vart lese av ein papirremse som stod i ein løkke. I den originale forma, så var ikkje Vernams system uknekkbart fordi lykelen kunne gjenbrukast. Eingangsbruken kom litt seinare når Joseph Mauborgne forstod at om lykel-remsen var totalt vilkårleg, så ville den kryptoanalytiske vanskegraden auka.

Det eksisterer tvitydige nemningar som er grunna i at nokre forfattarar brukar uttrykt "Vernam chiffer" som eit synonym for «eingongslykel», der der andre viser til kvart og eit additiv flytchiffer som eit «Vernam chiffer», inkludert dei som er basert på kryptografisk sikre pseudovilkårlige nummergeneratorar.

Perfekt tryggleik

Vernam-Mauborgnes eingongslykel vart tidleg anerkjent som vanskeleg å knekka, men den spesielle statusen som umogleg å knekka vart ikkje etablert før 25 år etter, av Claude Shannon. Han beviste, ved å bruka informasjonsteoretiske synspunkt, at eingongslykelen har ein eigenskap han kalla perfekt tryggleik. Denne eigenskapen bestod i at chifferteksta C ikkje gjev nokon som helst tilleggsinformasjon om klarteksta. Difor er den a priori sannsynligheten for ei klartekst M den same som den a posteriori sannsynligheten for klartekst M, gjeve den korresponderande chifferteksta. Mate${\displaystyle }$atisk kan dette uttrykkjast H (${\displaystyle }$) = ${\displaystyle }$( ${\displaystyle }$ | C ) {${\displaystyle }$ ${\displaystyle }$(M)=${\displaystyle }$(M${\displaystyle }$)} , der H ( M ) {${\displaystyle }$ H(M)} er den entropiske versjonen av klarteksta, og H ( M | C ) {\displaystyle H(M|C)} er den kondisjonelle entropiske varianten av klarteksta gjeve chifferteksta C. Perfekt tryggleik er ein sterk angivelse av kryptoanalytisk vanskegrad.${\displaystyle }$${\displaystyle }$${\displaystyle }$

Til trass for Shannons bevis på tryggleiken, så har eingongsnøkkelen endel praktiske ulemper:

• krev verkeleg tilfeldig eingongslykel
• krev sikker generering og distribusjon av nøkkelmaterialen, som må vera minst like langt som sjølve meldinga
• krev omhyggelig handsaming for å sikra at den vert verande løynleg overfor kvar og ein motstandar, og at den vert avhend på korrekt måte for å unngå gjenbruk av heile eller delar av nøkkelen (derav ordet eingongs-)

Fordi eingongslykel må distribuerast og takast vare på på sikkert vis, og nøkkelen må vera minst like lang som meldinga, så er det ofte inget poeng i å bruka eingongsnøkkelen og heller senda klarteksta i seg sjølv (sidan dei er same storleik og må sendast sikkert). Derimot, om ein veldig lang eingongsnøkkel har vorte distribuert på sikkert vis (til dømes ein harddisk full av tilfeldige data), så kan den brukast for framtidige meldingar, inntil summen av storleiken til meldingane er like stor som eingongsnøkkelen.

Eingongslykel har ikkje vorte brukt i utbreidd forstand innan informasjonstryggleik, då utfordringane ved å implementera dette er så store og vanskelege å ivareta, at mange system har vorte knokke på grunn av dette. Det er særleg viktig å understreka at kravet til å bruka ein nøkkel berre ein gong er absolutt. Viss ein eingongsnøkkel vert brukt to gonger, så kan enkle matematiske operasjonar redusera nøkkelen til eit kontinuerleg nøkkelchiffer. Viss begge klartekstene er skriven i vanleg språk (til dømes engelsk, russisk eller portugisisk for skulda i den sak), så kan dei med stor grad av sannsynlighet, sjølv om begge er løynlege, hentast fram igjen ved hjelp av heuristisk kryptoanalyse, med enkelte tvitydigheiter. Om meldingane er av ulik lengd, så kan bara dei delane som har felles nøkkelbruk analyserast og dekryptert. Den mest kjende utnyttelsen av denne sårbarheten er VENONA prosjektet.

Eingongslykelr gjev ingen funksjonalitet for å sikra at meldinga ikkje har vorte kompromittert, slik at i teorien såg kan eit angrep frå ein mellommann som kjenner den eksakte klarteksta, erstatta heile eller deler av teksta med si eiga tekst, sålenge den er av lik lengd. Standard teknikkar for å forhindra dette, slik som å bruka ein kode for meldingsautentisering, men denne teknikken har ikkje den perfekte tryggleiken som eingongslykel

Historie

Eingongslykelen sin historie er prega av fire ulike, men tett forbundne oppdagingar.

Det første eingongsnøkkelsystemet var elektronisk. I 1917 oppfann Gilbert Vernam hos AT&T eit chiffer basert på teletype maskinteknologi. Detta vart seinare patentert i 1919. Kvar karakter i ei melding vart elektronisk sett saman med ein karakter frå ein papirremse (nøkkel). Kaptein Joseph Mauborgne forstod at om sekvensen av karakterar på nøkkelremsen kunne vera totalt vilkårleg, så ville ein kryptoanalyse av resultatet vera særs vanskeleg. Saman fann dei opp det første eingongsnøkkel remsesystemet.

Den andre utviklinga var papirblokksystemet. Diplomatar hadde lenge brukt kodar og chiffer for konfidensialitet og for å minimera telegrafikostnader. Som kodar vart ofte ord eller frasar konvertert til nummergrupper (typisk 4 eller 5 siffer) ved å bruka ein slag ordliste, eller kodebok. For å auka tryggleiken så kunne eit hemmeligholdt nummer setjast saman med (vanlegvis modulær addisjon) kvar kodegruppe før sending. Det løynlege nummeret vart endra ved jamne mellomrom (dette kallast dobbeltkryptering). På byrjinga av 1920-talet så innsåg tre tyske kryptografar, Werner Kunze, Rudolf Shauffler og Erich Langlotz, som var involvert i oppgåva med å knekka slike system, at om kvar kodegruppe vart dobbeltkrytpert med eit heilt tilfeldig nummer så kunne meldinga aldri dekrypteres. Dei brukte eit par identiske papirblokker som hadde verta påtrykt linjer med tilfeldige nummergrupper. Kvar side hadde eit serienummer og 8 linjer. Kvar linje hadde 6 femsifrede nummer. Ei side vart brukt som eit arbeidsark for å kryptera ei melding, og deretter tilinkjegjord. Serienummeret vart sendt saman med den krypterte meldinga. Mottageren ville så reversera prosedyren, og deretter øydeleggja hans versjon av sida. Det tyske utenriksdepartementet sat systemet i drift i 1921.

Ein tredje variant var å bruka ei blokk eingongslykel basert på bokstavar, som vart brukt til å kryptera klartekst direkte, slik som neste døme vil visa. Leo Mark si har skildra korleis ein slikt system vart oppfunnen for dei britiske Special Operations Executive (SOE) under den andre verdskrigen, sjølv om han på det tidspunktet mistenkte at metoden allereie var kjend i den lukka verda av kryptografi, som til dømes på Bletchley Park.

Det siste dømet på oppdaging vart gjort av Claude Shannon på 1940-talet. Han innsåg og beviste den teoretiske tydinga av eit eingongslykelsystem. Shannon leverte sina funn og resultaet i ein hememligstemplet rapport i 1945, og publiserte desse offentleg i 1949. På same tid, men heilt uavhengig, hadde Vladimir Kotelnikov bevist absolutt tryggleik hos eingongsnøkler. Hans resultatet vart levert i ein rapport i 1941 som tydelegvis framleis er hemmelegstempla.

Døme

Gjeve at Kari ynskjer å senda meldinga «HELLO» til Ola. Gå frå ut at to arkblokker med identiske vilkårlege sekvensar av bokstavar har vorte laga forut for dette, og at Kari og Ola har fått kvart sit eksemplar av dette arket. Kari vel ut eit ubrukt ark frå blokka. Metoden for å gjera dette er ofte avtalt på førehand, eksempelvis «bruk det tolvte arket på skjærtorsdag» eller «bruk det neste tigjengelige arket for neste melding». Teksta på det valde arket er nøkkelen for denne meldinga. Kvar bokstav frå arket vil setjast saman på ein førehandbeistEM måte med kvar bokstav i meldinga. Det er vanleg, men ikkje påkravt, å gje kvar bokstav ein numerisk verdi: eksempelvis såg kan «A» vera 0, «B» vera 1 og så vidare til alfabetet er slutt. I dette dømet så vil metoden i bruk vera å setja saman nøkkelen og meldinga ved å bruka modulær addisjon. Dei numeriske verdiane av bokstavane i meldignen og bokstavane i nøkkelen vert lagt saman, modulus 26 (utgangspunktet her er eit engelsk alfabet). Om nøkkelmaterialen byrjar med

X M C K L

og meldinga er «HELLO», så kan krypteringen gjerast som følgjer:

   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 eit nummer er større enn 25, så vil ein, i modulær aritmetikk, bruka det som er igjen etter at ein har trekt frå 26. Enkelt sagt så vil den si at viss du går forbi «Z», byrj på «A» igjen.

Chifferteksta som skal sendast til Ola er «EQNVZ». Ola vert brukt sin kopi av tilsvarande ark på blokka, og gjennomfører den same prosedyren, berre omvendt, for å finna klarteksta. Her vert nøkkelen subtrahert frå chifferteksta, igjen ved å bruka 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å same måte som over, om eit tal vert negativt, legg til 26 for å gjera talet positivt.

På denne måten så får Ola fram Karis melding «HELLO». Både Kari og Ola øydelegg arket umiddelbart etter bruk, slik at det ikkje skal gjenbrukast og dermed forhindra eit angrep på chifferet.

Tryggleik

Engangsnøkler er informasjonsteoretisk sikre, basert på at den krypterte meldinga (chifferteksta) ikkje gjev ein kryptoanalytiker nokon informasjon om den opphavlege meldinga bortsedd frå lengda på meldinga. Dette er ein veldig sterk indikator på tryggleiken, som først vart utvikla under den annan verdskrig av Claude Shannon, og matematisk bevist av han ved bruk av eingongsnøkler omtrent på same tid. Hans resultat vart publisert i Bell Lab sin Technical Journal i 1949. Ved korrekt bruk så vil eingongsnøkler vera informasjonsteoretisk sikre sjølv mot åtakarar med uavgrensa prosesseringskraft. For å halda fram dømet ovanfor: Gjeve at Eva har fått tak i Karis krypterte melding «ENQVZ». Om Eva hadde hatt uavgrensa prosesseringskraft, så ville ho raskt ha funne at nøkkelen «XMCKL» ville produsert klarteksta «HELLO», men ho ville òg finna at nøkkelen «TQURI» ville produsert klarteksta «LÈT», som er ein like sannsynleg klartekst:

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) chiffertekst
−  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) mogleg 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 mogleg å «dekryptere» chifferteksta kva for ein som helst melding med det same mengd bokstavar ved å bruka ulike nøklar, og det finst ingen informasjon i chifferteksta som set Eva i stand til å velja blant dei ulike moglege resultata.

Konvensjonelle symmetriske krypteringsalgoritmer brukar komplekse mønstra av substitusjon og transponeringer. For dei beste av desse som er bruk i dag så er det ikkje kjent om det finst ein kryptoanalytisk prosedyre som kan reversera helt eller delvis desse mønstera utan å kjenna nøkkelen som vart brukt under krypteringen. Asymmetriske krypteringsalgoritmer brukar matematiske utfordringar som er sett på som umoglege å løysa, slik som heltallsfaktorisering eller diskrete logaritmar. Det finst endå ikkje bevis på at desse utfordringane er uløselige, og matematiske gjennombrot kan gjera eksisterande system sårbare for angrep.

Kjelder

• Erskine, Ralph, "Enigma's Security: What the Germans Really Knew", in "Action this Day", edited by Ralph Erskine and Michael Smith, pp 370–386, 2001.

• Denne artikkelen bygger på «Engangsnøkkel» frå Wikipedia på bokmål, den 23. november 2017.

Bakgrunnsstoff

• Detaljert skildring av engangsnøkkel med døme og bilete Cipher Machines and Cryptology
• Marcus Ranums engangsnøkkel FAQ
• FreeS/WAN ordbokinnlegg med diskusjon om engangsnøkkelens veikskapar
• Engangsnøkkel-basert program[1]

Vidare lesnad

• Robert Wallace and H. Keith Melton, with Henry R. Schlesinger, Spycraft: The Secret History of the CIA's Spytechs, from Communism to al-Qaeda, New York, Dutton, 2008 . ISBN 0525949801