Vernam chiffer

Vernam- chifferet är ett symmetriskt krypteringssystem som uppfanns 1917 av Gilbert Vernam [1] .

Ett chiffer är en typ av engångskodskryptosystem. Den använder den booleska funktionen exklusive-eller . Vernam-chifferet är ett exempel på ett system med absolut kryptografisk styrka [2] . Samtidigt anses det vara ett av de enklaste kryptosystemen [3] .

Historik

Beskrev först av Frank Miller 1882. [4] [5] [6]

Chiffert är uppkallat efter telegrafen Gilbert Vernam , som 1917 uppfann och 1919 patenterade ett system för automatisk kryptering av telegrafmeddelanden.

Vernam använde inte XOR-konceptet i patentet, utan implementerade exakt denna operation i ladderlogik. Varje tecken i meddelandet XORed bitvis (exklusivt eller) med papperstejptangenten [7] . Joseph Mauborgne (då kapten i den amerikanska armén och senare chef för signalkåren) modifierade detta system så att sekvensen av tecken på nyckelbandet var helt slumpmässigt, eftersom kryptoanalys i detta fall skulle vara svårast.

Vernam skapade en enhet som utför dessa operationer automatiskt, utan deltagande av en kryptograf. Således initierades den så kallade "linjära krypteringen", när processerna för kryptering och överföring av ett meddelande sker samtidigt. Fram till dess var kryptering preliminär, så linjekryptering ökade kommunikationshastigheten avsevärt.

Men eftersom han inte var kryptograf, märkte Vernam korrekt en viktig egenskap hos hans chiffer - varje band bör endast användas en gång och sedan förstöras. Detta är svårt att tillämpa i praktiken - därför omvandlades apparaten till flera slingade band med coprime- perioder [8] .

Beskrivning

Kryptosystemet föreslogs för att kryptera telegrafmeddelanden, som var binära texter där klartexten representeras i Baudot-koden (i form av femsiffriga "pulskombinationer"). I den här koden såg till exempel bokstaven "A" ut (1 1 0 0 0). På papperstejpen motsvarade siffran "1" hålet och siffran "0" - dess frånvaro. Den hemliga nyckeln var tänkt att vara en kaotisk uppsättning bokstäver i samma alfabet [8] .

För att erhålla chiffertexten kombineras klartexten med en XOR- operation med den hemliga nyckeln . Så, till exempel, när vi applicerar nyckeln (1 1 1 0 1) på bokstaven "A" (1 1 0 0 0), får vi ett krypterat meddelande (0 0 1 0 1): Vi vet att för det mottagna meddelandet har nyckeln (1 1 1 0 1), är det lätt att få det ursprungliga meddelandet med samma operation: För absolut kryptografisk styrka måste nyckeln ha tre kritiska egenskaper [2] : $(11000)\oplus (11101)=(00101)$ $(00101)\oplus (11101)=(11000)$

Ha en slumpmässig diskret enhetlig fördelning: , där k är nyckeln och N är antalet binära tecken i nyckeln; $P_{k}(k)=1/2^{N}$
Ha samma storlek som den angivna klartexten;
Använd endast en gång.

Också välkänt är det så kallade Vernam-chifferet modulo m , där tecknen för klartext, chiffertext och nyckel tar värden från ringen av rester Z m . Chifferet är en generalisering av det ursprungliga Vernam-chifferet, där m = 2 [2] .

Till exempel, Vernam chiffer modulo m = 26 (A=0,B=1,…, Z=25):

Nyckel: EVTIQWXQVVOPMCXREPYZ Vanlig text: ALLSWELLTHATENDSWELL (Allt är bra som slutar bra) Chiffertext: EGEAMAIBOCOIQPAJATJK

Vid kryptering utförs transformationen enligt Vigenère-tabellen (tillägget av teckenindex modulo längden på alfabetet ger denna tabell).

Nyckelbokstaven är kolumnen, klartextbokstaven är raden och chiffertexten är bokstaven i skärningspunkten.

Utan kunskap om nyckeln kan ett sådant meddelande inte analyseras. Även om det vore möjligt att prova alla nycklar, skulle resultatet bli alla möjliga meddelanden av en given längd, plus ett kolossalt antal meningslösa dechiffrering som ser ut som ett virrvarr av bokstäver. Men även bland meningsfulla dechiffreringar skulle det inte finnas något sätt att välja den önskade. När en slumpmässig sekvens (nyckeln) kombineras med en icke-slumpmässig (klartexten) är resultatet ( chiffertexten ) helt slumpmässigt och saknar därför de statistiska egenskaper som skulle kunna användas för att analysera chiffern. [9] .

Kryptografisk styrka

1945 skrev Claude Shannon "The Mathematical Theory of Cryptography" (avklassificerad först efter andra världskriget 1949 som " The Theory of Communication in Secret Systems "), där han bevisade den absoluta kryptografiska styrkan hos Vernam-chifferet. Det vill säga avlyssning av chiffertexten utan nyckel ger ingen information om meddelandet. Ur kryptografisynpunkt är det omöjligt att tänka på ett system som är säkrare än Vernam-chifferet [2] . Kraven för implementeringen av ett sådant schema är ganska icke-triviala, eftersom det är nödvändigt att säkerställa påförandet av ett unikt gamma som är lika med meddelandets längd, med dess efterföljande garanterade förstörelse. I detta avseende är kommersiell användning av Vernam-chifferet inte lika vanligt som offentliga nyckelsystem, och det används främst för överföring av meddelanden av särskild betydelse av statliga myndigheter [8] .

Vi presenterar ett bevis på absolut kryptografisk styrka. Låt meddelandet representeras av en binär längdsekvens . Sannolikhetsfördelningen för meddelandet kan vara vad som helst. Nyckeln representeras också av en binär sekvens av samma längd, men med en enhetlig fördelning för alla nycklar. $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 enlighet med krypteringsschemat kommer vi att producera en chiffertext genom att komponent-för-komponent summera modulo 2-sekvenser av klartexten och nyckeln:

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

Den lagliga användaren känner till nyckeln och utför dekrypteringen:

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

Låt oss hitta sannolikhetsfördelningen för N-block av chiffertexter med hjälp av formeln:

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

Resultatet bekräftar det välkända faktumet att summan av två stokastiska variabler, varav den ena har en diskret enhetlig fördelning på en finit grupp , är en enhetligt fördelad stokastisk variabel. I vårt fall är alltså fördelningen av chiffertexter enhetlig.

Vi skriver den gemensamma distributionen av klartexter och chiffertexter:

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

Låt oss hitta den villkorliga fördelningen

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},

eftersom nyckeln och klartexten är oberoende slumpvariabler. Total:

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

Att ersätta den högra sidan av denna formel med den gemensamma fördelningsformeln ger

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

Vilket bevisar chiffertexternas och klartexternas oberoende i detta system. Detta innebär absolut kryptografisk styrka [10] .

Omfattning

För närvarande används Vernam-kryptering sällan. Till stor del beror detta på nyckelns betydande storlek, vars längd måste matcha meddelandets längd. Det vill säga att användningen av sådana chiffer kräver enorma kostnader för produktion, lagring och destruktion av nyckelmaterial. Ändå fann helt starka chiffer som Vernam fortfarande praktisk användning för att skydda kritiska kommunikationslinjer med en relativt liten mängd information. Till exempel använde britterna och amerikanerna chiffer av Vernam-typ under andra världskriget. Modulo 2 Vernam-chifferet användes på en statlig hotline mellan Washington och Moskva, där nyckelmaterialen var papperstejper på vilka tecknen i nyckelsekvensen perforerades [2] .

I praktiken är det möjligt att fysiskt överföra informationsbäraren med en lång, verkligt slumpmässig nyckel en gång, och sedan vidarebefordra meddelanden efter behov. Idén med chifferblock är baserad på detta : chiffertjänstemannen förses med en anteckningsbok via diplomatisk post eller personligen, vars varje sida innehåller nycklar. Den mottagande parten har samma anteckningsblock. Använda sidor förstörs [11] .

Nackdelar

En verkligt slumpmässig sekvens ( nyckel ) behövs för att Vernam-chifferet ska fungera . Per definition är en sekvens som erhålls med hjälp av vilken algoritm som helst inte riktigt slumpmässig, utan pseudo-slumpmässig. Det vill säga att du behöver få en slumpmässig sekvens inte algoritmiskt, utan till exempel genom att använda radioaktivt sönderfall skapat av en elektronisk vitbrusgenerator eller andra ganska slumpmässiga händelser. För att göra fördelningen så nära likformig som möjligt skickas en slumpmässig sekvens vanligtvis genom en hashfunktion som MD5 [12] .

Nackdelen med att använda Vernam-chifferet är bristen på bekräftelse av meddelandets äkthet och integritet. Mottagaren kan inte verifiera frånvaron av skada eller avsändarens äkthet. Om en tredje part på något sätt känner igen meddelandet kommer den enkelt att återställa nyckeln och kunna ersätta meddelandet med ett annat av samma längd. Lösningen på problemet är att använda en hash-funktion. En hash-funktion beräknas från klartexten och dess värde krypteras tillsammans med meddelandet. Alla ändringar i meddelandet kommer att ändra hashvärdet. Således, även om en angripare får tag i ett chifferfält utan att känna till algoritmen för att beräkna hashfunktionen, kommer han inte att kunna använda den för att överföra information [11] .

Det är alltid nödvändigt att ha ett tillräckligt antal nycklar till hands, vilket kan behövas i framtiden för att kryptera stora mängder klartext. Den verkliga volymen av texten är ofta svår att uppskatta i förväg, särskilt inom den diplomatiska och militära sfären, där situationen kan förändras snabbt och oförutsägbart. Detta kan leda till brist på nycklar, vilket kan göra att kryptografen antingen återanvänder nyckeln/nycklarna eller helt bryter den krypterade kommunikationen.

Problemet är säker överföring av sekvensen och att hålla den hemlig. Om det finns en kanal för meddelandeöverföring som är tillförlitligt skyddad från avlyssning behövs inga chiffer alls: hemliga meddelanden kan sändas över denna kanal. Om emellertid nyckeln till Vernam-systemet sänds med ett annat chiffer (till exempel DES ), kommer det resulterande chifferet att skyddas exakt lika mycket som DES är skyddat. Samtidigt, eftersom nyckellängden är densamma som meddelandelängden, är det inte lättare att överföra det än meddelandet. En chifferblock på ett fysiskt medium kan stjälas eller kopieras [11] .

Vernam-chifferet är känsligt för eventuella brott mot krypteringsproceduren. Det fanns fall då samma anteckningsblockssida användes två gånger av olika anledningar. Till exempel, bland hela volymen av sovjetisk krypterad korrespondens som fångades av amerikansk underrättelsetjänst på 40-talet av förra seklet, hittades meddelanden som stängdes med ett dubbelt använt gamma. Denna period varade inte särskilt länge, för redan efter de första framgångarna för amerikanska kryptoanalytiker i slutet av 1940-talet fick Sovjetunionens underrättelsetjänster veta om allvarliga problem med tillförlitligheten av deras krypterade korrespondens. Sådana meddelanden dechiffrerades under de kommande 40 åren som en del av det hemliga Venona-projektet , vars dokument senare avhemligas och publicerades på NSA:s webbplats [13] .

Anteckningar

↑ Symmetriska algoritmer .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Mao, 2005 .
↑ Miller, Frank. Telegrafisk kod för att säkerställa integritet och sekretess vid överföring av telegram. — C. M. Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: Uppfinnaren av One-Time Pad . kryptologi . 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . Kodbok visar ett krypteringsformulär från Telegraphs (25 juli 2011). Hämtad 26 juli 2011.
↑ US 1310719A patent
↑ 1 2 3 Babash, et al., 2003 .
↑ Kryptografi (otillgänglig länk) . Tillträdesdatum: 8 februari 2014. Arkiverad från originalet 2 november 2013. (obestämd)
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , sid. 41-43.
↑ 1 2 3 One-time Pad .
↑ Vanliga frågor .
↑ Kiwi, 2005 .

Litteratur

Fomichev V. M. Diskret matematik och kryptologi : Föreläsningskurs / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - S. 239-246. — 397 sid. — ISBN 978-5-86404-185-7
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssäkerhet : lärobok - M .: MIPT , 2011. - 225 sid. — ISBN 978-5-7417-0377-9
Mao V. Modern kryptografi : Teori och praktik / övers. D. A. Klyushina - M . : Williams , 2005. - S. 255. - 768 sid. — ISBN 978-5-8459-0847-6
Robert L. Benson. The Venona Story (engelska) // Center for Cryptologic History National Security Agency. Arkiverad från originalet den 27 maj 2010.
Babash A.V. , Goliev Yu. I. , Larin D.A. , Shankin G.P. Kryptografiska idéer från 1800-talet // Informationssäkerhet. Confidant - St Petersburg. : 2004. - nummer. 3.

Länkar

Symmetriska algoritmer (ryska) .
Dirk Rijmenants. One-time Pad (engelska) .
Marcus J. Ranum. One-Time-Pad (Vernam 's Chipher) Vanliga frågor .
Byrd Kiwi. Prisfel . - 2005. Arkiverad den 24 december 2013.