Cifrul Vernam

Cifrul Vernam este un sistem de criptare simetric inventat în 1917 de Gilbert Vernam [1] .

Un cifr este un tip de criptosistem cu pad unic. Utilizează funcția boolean exclusive-or . Cifrul Vernam este un exemplu de sistem cu putere criptografică absolută [2] . În același timp, este considerat unul dintre cele mai simple criptosisteme [3] .

Istorie

Descris pentru prima dată de Frank Miller în 1882. [4] [5] [6]

Cifrul este numit după telegraful Gilbert Vernam , care în 1917 a inventat și în 1919 a patentat un sistem de criptare automată a mesajelor telegrafice.

Vernam nu a folosit conceptul XOR în brevet, ci a implementat exact această operație în logica ladder. Fiecare caracter din mesaj a fost XOR pe biți (exclusiv sau) cu tasta de bandă de hârtie [7] . Joseph Mauborgne (pe atunci căpitan în armata SUA și mai târziu șef al corpului de semnale) a modificat acest sistem, astfel încât secvența de caractere de pe banda de cheie să fie complet aleatorie, deoarece în acest caz criptoanaliza ar fi cea mai dificilă.

Vernam a creat un dispozitiv care efectuează aceste operațiuni automat, fără participarea unui criptograf. Astfel, a fost inițiată așa-numita „criptare liniară”, atunci când procesele de criptare și transmitere a unui mesaj au loc simultan. Până atunci, criptarea era preliminară, așa că criptarea în linie a crescut semnificativ viteza de comunicare.

Nefiind criptograf însă, Vernam a observat corect o proprietate importantă a cifrului său - fiecare bandă ar trebui folosită o singură dată și apoi distrusă. Acest lucru este dificil de aplicat în practică - prin urmare, aparatul a fost convertit în mai multe benzi în buclă cu perioade de coprime [8] .

Descriere

Criptosistemul a fost propus pentru a cripta mesajele telegrafice, care erau texte binare în care textul simplu este reprezentat în codul Baudot (sub formă de „combinații de impulsuri”) de cinci cifre. În acest cod, de exemplu, litera „A” arăta ca (1 1 0 0 0). Pe banda de hârtie, numărul „1” corespundea găurii, iar numărul „0” - absența acestuia. Cheia secretă trebuia să fie un set haotic de litere ale aceluiași alfabet [8] .

Pentru a obține textul cifrat, textul simplu este combinat cu o operație XOR cu cheia secretă . Deci, de exemplu, atunci când aplicăm cheia (1 1 1 0 1) la litera „A” (1 1 0 0 0), obținem un mesaj criptat (0 0 1 0 1): Știind că pentru mesajul primit au cheia (1 1 1 0 1), este ușor să obțineți mesajul original prin aceeași operațiune: Pentru puterea criptografică absolută, cheia trebuie să aibă trei proprietăți critice [2] : $(11000)\oplus (11101)=(00101)$ $(00101)\oplus (11101)=(11000)$

Au o distribuție uniformă discretă aleatorie: , unde k este cheia și N este numărul de caractere binare din cheie; $P_{k}(k)=1/2^{N}$
Să aibă aceeași dimensiune ca textul simplu specificat;
Aplicați o singură dată.

De asemenea, binecunoscut este și așa-numitul cifru Vernam modulo m , în care semnele textului clar, textului cifrat și cheii iau valori din inelul de reziduuri Z m . Cifrul este o generalizare a cifrului original Vernam, unde m = 2 [2] .

De exemplu, cifra Vernam modulo m = 26 (A=0,B=1,..., Z=25):

Cheie: EVTIQWXQVVOPMCXREPYZ Text simplu: ALLSWELLTHATENDSWELL (Totul e bine care se termină bine) Text cifrat: EGEAMAIBOCOIQPAJATJK

La criptare, transformarea se realizează conform tabelului Vigenère (adăugarea indicilor de caractere modulo lungimea alfabetului dă acest tabel).

Litera cheie este coloana, litera text simplu este rândul, iar textul cifrat este litera de la intersecție.

Fără cunoașterea cheii, un astfel de mesaj nu poate fi analizat. Chiar dacă ar fi posibil să încercăm toate cheile, rezultatul ar fi toate mesajele posibile de o anumită lungime, plus un număr colosal de descifrări fără sens care arată ca un amestec de litere. Dar chiar și printre descifrări semnificative, nu ar exista nicio modalitate de a alege cea dorită. Când o secvență aleatorie (cheia) este combinată cu una non-aleatoare (textul simplu), rezultatul ( textul cifrat ) este complet aleatoriu și, prin urmare, nu are caracteristicile statistice care ar putea fi utilizate pentru a analiza cifrul. [9] .

Puterea criptografică

În 1945, Claude Shannon a scris „The Mathematical Theory of Criptography” (declasificată abia după cel de-al Doilea Război Mondial în 1949 ca „ Theory of Communication in Secret Systems ”), în care a dovedit puterea criptografică absolută a cifrului Vernam. Adică, interceptarea textului cifrat fără cheie nu oferă nicio informație despre mesaj. Din punctul de vedere al criptografiei, este imposibil să ne gândim la un sistem mai sigur decât cifrul Vernam [2] . Cerințele pentru implementarea unei astfel de scheme sunt destul de nebanale, deoarece este necesar să se asigure impunerea unui gamma unic egal cu lungimea mesajului, cu distrugerea sa ulterioară garantată. În acest sens, utilizarea comercială a cifrului Vernam nu este la fel de comună ca schemele de chei publice și este folosită în principal pentru transmiterea de mesaje de importanță deosebită de către agențiile guvernamentale [8] .

Vă prezentăm o dovadă a puterii criptografice absolute. Fie ca mesajul să fie reprezentat printr-o secvență binară de lungime . Distribuția de probabilitate a mesajului poate fi orice. Cheia este reprezentată și de o secvență binară de aceeași lungime, dar cu o distribuție uniformă pentru toate cheile. $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}$

În conformitate cu schema de criptare, vom produce un text cifrat component cu component însumând secvențe modulo 2 ale textului simplu și cheii:

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

Utilizatorul legal cunoaște cheia și efectuează decriptarea:

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

Să găsim distribuția de probabilitate a N-blocuri de texte cifrate folosind formula:

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}

Rezultatul confirmă faptul binecunoscut că suma a două variabile aleatoare, dintre care una are o distribuție uniformă discretă pe un grup finit , este o variabilă aleatoare distribuită uniform. Astfel, în cazul nostru, distribuția textelor cifrate este uniformă.

Scriem distribuția comună a textelor simple și a textelor cifrate:

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

Să găsim distribuția condiționată

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

întrucât cheia și textul simplu sunt variabile aleatoare independente. Total:

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

Înlocuirea părții drepte a acestei formule în formula de distribuție comună dă

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

Ceea ce demonstrează independența textelor cifrate și a textelor simple în acest sistem. Aceasta înseamnă putere criptografică absolută [10] .

Domeniul de aplicare

În prezent, criptarea Vernam este rar folosită. În mare măsură, acest lucru se datorează dimensiunii semnificative a cheii, a cărei lungime trebuie să se potrivească cu lungimea mesajului. Adică, utilizarea unor astfel de cifruri necesită costuri uriașe pentru producția, depozitarea și distrugerea materialelor cheie. Cu toate acestea, cifrurile complet puternice, cum ar fi Vernam, au găsit încă o utilizare practică pentru protejarea liniilor critice de comunicare cu o cantitate relativ mică de informații. De exemplu, britanicii și americanii au folosit cifruri de tip Vernam în timpul celui de-al Doilea Război Mondial. Cifrul Vernam modulo 2 a fost folosit pe o linie telefonică guvernamentală între Washington și Moscova, unde materialele cheie erau benzi de hârtie pe care erau perforate caracterele secvenței de taste [2] .

În practică, este posibil să transferați fizic purtătorul de informații cu o cheie lungă, cu adevărat aleatorie, o dată și apoi să transmiteți mesajele după cum este necesar. Ideea tampoanelor de cifrat se bazează pe aceasta : funcționarul de cifrare este furnizat cu un caiet prin poștă diplomatică sau personal, fiecare pagină conține chei. Partea care primește are același bloc de note. Paginile folosite sunt distruse [11] .

Dezavantaje

Pentru ca cifra Vernam să funcționeze, este necesară o secvență ( cheie ) cu adevărat aleatorie. Prin definiție, o secvență obținută folosind orice algoritm nu este cu adevărat aleatorie, ci pseudoaleatoare. Adică, trebuie să obțineți o secvență aleatorie nu algoritmic, ci, de exemplu, folosind dezintegrarea radioactivă creată de un generator electronic de zgomot alb sau alte evenimente destul de aleatorii. Pentru a face distribuția cât mai aproape de uniformă posibil , o secvență aleatorie este de obicei trecută printr-o funcție hash ca MD5 [12] .

Dezavantajul utilizării cifrului Vernam este lipsa confirmării autenticității și integrității mesajului. Destinatarul nu poate verifica absența deteriorării sau autenticitatea expeditorului. Dacă o terță parte recunoaște cumva mesajul, va recupera cu ușurință cheia și va putea înlocui mesajul cu altul de aceeași lungime. Soluția problemei este utilizarea unei funcții hash. O funcție hash este calculată din textul simplu și valoarea acesteia este criptată împreună cu mesajul. Orice modificare a mesajului va schimba valoarea hash. Astfel, chiar dacă un atacator pune mâna pe un cipher pad fără să cunoască algoritmul de calcul al funcției hash, el nu îl va putea folosi pentru a transmite informații [11] .

Este întotdeauna necesar să aveți la îndemână un număr suficient de chei, care poate fi necesar în viitor pentru a cripta cantități mari de text simplu. Volumul real al textului este adesea greu de estimat în prealabil, mai ales în sfera diplomatică și militară, unde situația se poate schimba rapid și imprevizibil. Acest lucru poate duce la o lipsă de chei, ceea ce poate determina criptograful fie să refolosească cheile (cheile) fie să întrerupă complet comunicarea criptată.

Problema este transmiterea în siguranță a secvenței și păstrarea ei secretă. Dacă există un canal de transmitere a mesajelor care este protejat în mod fiabil de interceptare, cifrurile nu sunt deloc necesare: mesajele secrete pot fi transmise prin acest canal. Dacă, totuși, cheia sistemului Vernam este transmisă folosind un alt cifr (de exemplu, DES ), atunci cifrul rezultat va fi protejat exact cât este protejat DES. În același timp, deoarece lungimea cheii este aceeași cu lungimea mesajului, nu este mai ușor să o transmiteți decât mesajul. Un tampon de cifrat pe un mediu fizic poate fi furat sau copiat [11] .

Cifrul Vernam este sensibil la orice încălcare a procedurii de criptare. Au existat cazuri când aceeași pagină de notepad a fost folosită de două ori din diferite motive. De exemplu, printre întregul volum de corespondență criptată sovietică interceptată de informațiile americane în anii 40 ai secolului trecut, s-au găsit mesaje care au fost închise cu un gamma dublu utilizat. Această perioadă nu a durat foarte mult, deoarece deja după primele succese ale criptoanaliștilor americani la sfârșitul anilor 1940, serviciile secrete ale URSS au aflat despre probleme serioase legate de fiabilitatea corespondenței lor criptate. Astfel de mesaje au fost descifrate în următorii 40 de ani în cadrul proiectului secret Venona , ale cărui documente au fost ulterior desecretizate și postate pe site-ul NSA [13] .

Note

↑ Algoritmi simetrici .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Mao, 2005 .
↑ Miller, Frank. Cod telegrafic pentru a asigura confidențialitatea și secretul în transmiterea telegramelor. — C. M. Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: Inventatorul blocului unic . criptologie . 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . Cartea de coduri afișează un formular de criptare datând din telegraf (25 iulie 2011). Preluat la 26 iulie 2011.
↑ Brevet US 1310719A
↑ 1 2 3 Babash, et al., 2003 .
↑ Criptografie (link inaccesibil) . Data accesului: 8 februarie 2014. Arhivat din original pe 2 noiembrie 2013. (nedefinit)
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , p. 41-43.
↑ 1 2 3 Pad unic .
↑ Întrebări frecvente .
↑ Kiwi, 2005 .

Literatură

Fomichev V. M. Matematică discretă și criptologie : Curs de cursuri / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - S. 239-246. — 397 p. — ISBN 978-5-86404-185-7
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Mao V. Criptografia modernă : Teorie și practică / transl. D. A. Klyushina - M . : Williams , 2005. - S. 255. - 768 p. — ISBN 978-5-8459-0847-6
Robert L. Benson. Povestea Venona (engleză) // Centrul pentru Istoria Criptologică Agenția Națională de Securitate. Arhivat din original pe 27 mai 2010.
Babash A. V. , Goliev Yu. I. , Larin D. A. , Shankin G. P. Ideile criptografice ale secolului al XIX-lea // Securitatea informațiilor. confident - Sankt Petersburg. : 2004. - emisiune. 3.

Link -uri

Algoritmi simetrici (rusă) .
Dirk Rijmenants. Pad unic (engleză) .
Marcus J. Ranum. One-Time-Pad (Cifrul lui Vernam ) Întrebări frecvente .
Byrd Kiwi. Greșeli de preț . - 2005. Arhivat la 24 decembrie 2013.