Vernam chiffer

Vernam - chifferet er et symmetrisk krypteringssystem opfundet i 1917 af Gilbert Vernam [1] .

En cipher er en type engangspude-kryptosystem. Den bruger den booleske eksklusive-eller- funktion . Vernam-chifferet er et eksempel på et system med absolut kryptografisk styrke [2] . Samtidig betragtes det som et af de simpleste kryptosystemer [3] .

Historie

Først beskrevet af Frank Miller i 1882. [4] [5] [6]

Chifferen er opkaldt efter telegrafen Gilbert Vernam , som i 1917 opfandt og i 1919 patenterede et system til automatisk kryptering af telegrafbeskeder.

Vernam brugte ikke XOR-konceptet i patentet, men implementerede netop denne operation i ladder-logik. Hvert tegn i meddelelsen blev bitvist XORed (eksklusiv eller) med papirtape-tasten [7] . Joseph Mauborgne (dengang kaptajn i den amerikanske hær og senere chef for signalkorpset) modificerede dette system, så sekvensen af tegn på nøglebåndet var fuldstændig tilfældig, da krypteringsanalyse i dette tilfælde ville være sværest.

Vernam skabte en enhed, der udfører disse operationer automatisk, uden deltagelse af en kryptograf. Således blev den såkaldte "lineære kryptering" igangsat, når processerne med kryptering og transmission af en meddelelse sker samtidigt. Indtil da var kryptering foreløbig, så linjekryptering øgede kommunikationshastigheden markant.

Ikke at være en kryptograf, men Vernam bemærkede korrekt en vigtig egenskab ved hans chiffer - hvert bånd bør kun bruges én gang og derefter destrueres. Dette er svært at anvende i praksis - derfor blev apparatet omdannet til flere løkkebånd med coprime - perioder [8] .

Beskrivelse

Kryptosystemet blev foreslået til at kryptere telegrafmeddelelser, som var binære tekster, hvor almindelig tekst er repræsenteret i Baudot-koden (i form af femcifrede "pulskombinationer"). I denne kode så bogstavet "A" for eksempel ud (1 1 0 0 0). På papirbåndet svarede tallet "1" til hullet, og tallet "0" - dets fravær. Den hemmelige nøgle skulle være et kaotisk sæt bogstaver i det samme alfabet [8] .

For at opnå chifferteksten kombineres almindelig tekst med en XOR- operation med den hemmelige nøgle . Så når vi f.eks. anvender nøglen (1 1 1 0 1) på bogstavet "A" (1 1 0 0 0), får vi en krypteret meddelelse (0 0 1 0 1): Ved at vide, at vi for den modtagne meddelelse har nøglen (1 1 1 0 1), er det nemt at få den originale besked ved samme operation: For absolut kryptografisk styrke skal nøglen have tre kritiske egenskaber [2] : $(11000)\oplus (11101)=(00101)$ $(00101)\oplus (11101)=(11000)$

Har en tilfældig diskret ensartet fordeling: , hvor k er nøglen og N er antallet af binære tegn i nøglen; $P_{k}(k)=1/2^{N}$
Være den samme størrelse som den angivne klartekst;
Anvend kun én gang.

Også kendt er den såkaldte Vernam-chiffer modulo m , hvor fortegnene i klartekst, chiffertekst og nøgle tager værdier fra ringen af rester Z m . Chifferen er en generalisering af den oprindelige Vernam-ciffer, hvor m = 2 [2] .

For eksempel, Vernam cipher modulo m = 26 (A=0,B=1,…, Z=25):

Nøgle: EVTIQWXQVVOPMCXREPYZ Almindelig tekst: ALLSWELLTHATENDSWELL (Alt er godt, der ender godt) Krypteringstekst: EGEAMAIBOCOIQPAJATJK

Ved kryptering udføres transformationen i henhold til Vigenère-tabellen (tilføjelsen af tegnindekser modulo længden af alfabetet giver denne tabel).

Nøglebogstavet er kolonnen, almindeligt bogstav er rækken, og chifferteksten er bogstavet i krydset.

Uden kendskab til nøglen kan en sådan besked ikke analyseres. Selvom det var muligt at prøve alle tasterne, ville resultatet være alle mulige beskeder af en given længde, plus et kolossalt antal meningsløse dechifreringer , der ligner et virvar af bogstaver. Men selv blandt meningsfulde dechiffreringer ville der ikke være nogen måde at vælge den ønskede. Når en tilfældig sekvens (nøglen) kombineres med en ikke-tilfældig (klarteksten), er resultatet ( chifferteksten ) fuldstændig tilfældigt og mangler derfor de statistiske træk, der kunne bruges til at analysere chifferen. [9] .

Kryptografisk styrke

I 1945 skrev Claude Shannon "The Mathematical Theory of Cryptography" (først afklassificeret efter Anden Verdenskrig i 1949 som " The Theory of Communication in Secret Systems "), hvori han beviste Vernam-chifferets absolutte kryptografiske styrke. Det vil sige, at aflytning af chifferteksten uden nøgle ikke giver nogen information om beskeden. Fra et kryptografisk synspunkt er det umuligt at tænke på et system, der er mere sikkert end Vernam-chifferet [2] . Kravene til implementeringen af en sådan ordning er ret ikke-trivielle, da det er nødvendigt at sikre pålæggelsen af et unikt gamma svarende til længden af meddelelsen med dens efterfølgende garanterede ødelæggelse. I denne henseende er den kommercielle brug af Vernam-chifferet ikke så almindelig som offentlige nøgleordninger, og den bruges hovedsageligt til transmission af meddelelser af særlig betydning af offentlige myndigheder [8] .

Vi præsenterer et bevis på absolut kryptografisk sikkerhed. Lad meddelelsen være repræsenteret af en binær sekvens af længde . Budskabssandsynlighedsfordelingen kan være hvad som helst. Nøglen er også repræsenteret af en binær sekvens af samme længde, men med en ensartet fordeling for alle nøgler. $N:m=m_{1},m_{2},\ldots ,m_{n}$ $P_{m}(m)$ $k=k_{1},k_{2},\ldots ,k_{n}$ $P_{k}(k)=1/2^{N}$

I overensstemmelse med krypteringsskemaet vil vi producere en chiffertekst ved at komponent-for-komponent summere modulo 2-sekvenser af klarteksten og nøglen:

C=M\oplus K=(m_{1}\oplus k_{1},m_{2}\oplus k_{2},\ldots ,m_{N}\oplus k_{N})

Den lovlige bruger kender nøglen og udfører dekrypteringen:

M=C\oplus K=(c_{1}\oplus k_{1},c_{2}\oplus k_{2},\ldots ,c_{N}\oplus k_{N})

Lad os finde sandsynlighedsfordelingen af N-blokke af chiffertekster ved hjælp af formlen:

P(c=a)=P(m\oplus k=a)=\sum _{m}{P(m)}P(m\oplus k=a|m)=\sum _{m} {P(m)1/2^{N}}=1/2^{N}

Resultatet bekræfter det velkendte faktum, at summen af to stokastiske variable, hvoraf den ene har en diskret ensartet fordeling på en endelig gruppe , er en ensartet fordelt stokastisk variabel. I vores tilfælde er fordelingen af chiffertekster således ensartet.

Vi skriver den fælles distribution af klartekster og chiffertekster:

P(m=a,c=b)=P(m=a)P(c=b|m=a)

Lad os finde den betingede fordeling

P(c=b|m=a)=P(m\oplus k=b|m=a)=P(k=b\oplus a|m=a)=P(k=b\oplus a)=1 /2^{N},

da nøglen og klarteksten er uafhængige tilfældige variable. I alt:

P(c=b|m=a)=1/2^{N}

Erstatning af højre side af denne formel i fællesfordelingsformlen giver

P(m=a,c=b)=P(m=a)1/2^{N}

Hvilket beviser uafhængigheden af chiffertekster og klartekster i dette system. Dette betyder absolut kryptografisk styrke [10] .

Omfang

I øjeblikket bruges Vernam-kryptering sjældent. Dette skyldes i høj grad nøglens betydelige størrelse, hvis længde skal svare til meddelelsens længde. Det vil sige, at brugen af sådanne cifre kræver enorme omkostninger til produktion, opbevaring og destruktion af nøglematerialer. Ikke desto mindre fandt helt stærke cifre som Vernam stadig praktisk anvendelse til at beskytte kritiske kommunikationslinjer med en relativt lille mængde information. For eksempel brugte briterne og amerikanerne cifre af Vernam-typen under Anden Verdenskrig. Modulo 2 Vernam-chifferet blev brugt på en regeringshotline mellem Washington og Moskva, hvor nøglematerialerne var papirbånd, hvorpå nøglesekvensens tegn var perforeret [2] .

I praksis er det muligt fysisk at overføre informationsbæreren med en lang, virkelig tilfældig nøgle én gang, og derefter videresende beskeder efter behov. Idéen med chifferpuder er baseret på dette : chifferekspedienten er forsynet med en notesbog via diplomatisk post eller personligt, hvor hver side indeholder nøgler. Den modtagende part har samme notesblok. Brugte sider destrueres [11] .

Ulemper

En virkelig tilfældig sekvens ( nøgle ) er nødvendig for at Vernam-chifferet kan fungere . Per definition er en sekvens opnået ved hjælp af enhver algoritme ikke virkelig tilfældig, men pseudo-tilfældig. Det vil sige, at du skal få en tilfældig sekvens ikke algoritmisk, men for eksempel ved hjælp af radioaktivt henfald skabt af en elektronisk hvid støjgenerator eller andre ret tilfældige hændelser. For at gøre fordelingen så tæt på ensartet som muligt sendes en tilfældig sekvens normalt gennem en hashfunktion som MD5 [12] .

Ulempen ved at bruge Vernam-chifferet er manglen på bekræftelse af meddelelsens ægthed og integritet. Modtageren kan ikke bekræfte fraværet af skade eller afsenderens ægthed. Hvis en tredjepart på en eller anden måde genkender beskeden, vil den nemt gendanne nøglen og være i stand til at erstatte beskeden med en anden af samme længde. Løsningen på problemet er at bruge en hash-funktion. En hash-funktion beregnes ud fra almindelig tekst, og dens værdi krypteres sammen med beskeden. Enhver ændring i meddelelsen vil ændre hashværdien. Således, selvom en angriber får fat i en chifferpude uden at kende algoritmen til at beregne hash-funktionen, vil han ikke være i stand til at bruge den til at transmittere information [11] .

Det er altid nødvendigt at have et tilstrækkeligt antal nøgler ved hånden, hvilket kan være nødvendigt i fremtiden for at kryptere store mængder almindelig tekst. Tekstens reelle volumen er ofte svær at vurdere på forhånd, især på det diplomatiske og militære område, hvor situationen kan ændre sig hurtigt og uforudsigeligt. Dette kan føre til mangel på nøgler, hvilket kan få kryptografen til enten at genbruge nøglen/nøglerne eller fuldstændig bryde den krypterede kommunikation.

Problemet er den sikre overførsel af sekvensen og at holde den hemmelig. Hvis der er en meddelelsestransmissionskanal, der er pålideligt beskyttet mod aflytning, er der slet ikke brug for chiffer: hemmelige meddelelser kan transmitteres over denne kanal. Hvis nøglen til Vernam-systemet imidlertid transmitteres ved hjælp af en anden chiffer (for eksempel DES ), så vil den resulterende chiffer blive beskyttet nøjagtigt lige så meget som DES er beskyttet. På samme tid, da nøglelængden er den samme som beskedlængden, er det ikke nemmere at transmittere den end beskeden. En chifferblok på et fysisk medie kan stjæles eller kopieres [11] .

Vernam-chifferet er følsomt over for ethvert brud på krypteringsproceduren. Der var tilfælde, hvor den samme notesblokside blev brugt to gange af forskellige årsager. Blandt hele mængden af sovjetisk krypteret korrespondance, som blev opsnappet af amerikansk efterretningstjeneste i 40'erne af det sidste århundrede, blev der for eksempel fundet meddelelser, der blev lukket med en dobbelt anvendt gamma. Denne periode varede ikke særlig længe, for allerede efter de første succeser for amerikanske kryptoanalytikere i slutningen af 1940'erne lærte USSRs hemmelige tjenester om alvorlige problemer med pålideligheden af deres krypterede korrespondance. Sådanne beskeder blev dechiffreret i løbet af de næste 40 år som en del af det hemmelige Venona-projekt , hvis dokumenter senere blev afklassificeret og offentliggjort på NSA's hjemmeside [13] .

Noter

↑ Symmetriske algoritmer .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Mao, 2005 .
↑ Miller, Frank. Telegrafisk kode for at sikre privatlivets fred og hemmeligholdelse ved transmission af telegrammer. — C. M. Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: Opfinder af One-Time Pad . kryptologi . 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . Kodebog viser en krypteringsformular dateres tilbage til telegrafer (25. juli 2011). Hentet 26. juli 2011.
↑ US 1310719A patent
↑ 1 2 3 Babash, et al., 2003 .
↑ Kryptografi (utilgængeligt link) . Dato for adgang: 8. februar 2014. Arkiveret fra originalen 2. november 2013. (ubestemt)
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , s. 41-43.
↑ 1 2 3 Engangs Pad .
↑ Ofte stillede spørgsmål .
↑ Kiwi, 2005 .

Litteratur

Fomichev V. M. Diskret matematik og kryptologi : Forelæsningsforløb / red. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - S. 239-246. — 397 s. — ISBN 978-5-86404-185-7
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssikkerhed : lærebog - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Mao V. Moderne kryptografi : Teori og praksis / oversættelse. D. A. Klyushina - M . : Williams , 2005. - S. 255. - 768 s. — ISBN 978-5-8459-0847-6
Robert L. Benson. The Venona Story (engelsk) // Center for Cryptologic History National Security Agency. Arkiveret fra originalen den 27. maj 2010.
Babash A. V. , Goliev Yu. I. , Larin D. A. , Shankin G. P. Kryptografiske ideer fra det 19. århundrede // Informationssikkerhed. Fortrolig - St. Petersborg. : 2004. - udgave. 3.