Vernam titkosítás

A Vernam - rejtjel egy szimmetrikus titkosítási rendszer , amelyet 1917-ben Gilbert Vernam [1] talált fel .

A rejtjel egyfajta egyszeri pad kriptorendszer. A logikai exkluzív-or függvényt használja . A Vernam-rejtjel egy példa egy abszolút kriptográfiai erősségű rendszerre [2] . Ugyanakkor az egyik legegyszerűbb titkosítási rendszernek tartják [3] .

Történelem

Először Frank Miller írta le 1882-ben. [4] [5] [6]

A rejtjel Gilbert Vernam távíróról kapta a nevét , aki 1917 -ben feltalált és 1919-ben szabadalmaztatott egy rendszert a távirati üzenetek automatikus titkosítására.

Vernam nem az XOR koncepciót használta a szabadalomban, hanem pontosan ezt a műveletet valósította meg a létralogikában. Az üzenet minden karaktere bitenkénti XOR-re volt írva (kizárólagos vagy) a papírszalag billentyűvel [7] . Joseph Mauborgne (akkor az amerikai hadsereg kapitánya, később a jelzőhadtest főnöke) úgy módosította ezt a rendszert, hogy a kulcsszalagon a karakterek sorrendje teljesen véletlenszerű legyen, mivel ebben az esetben a kriptoanalízis lenne a legnehezebb.

Vernam olyan eszközt készített, amely automatikusan, titkosító közreműködése nélkül végzi el ezeket a műveleteket. Így indult el az úgynevezett "lineáris titkosítás", amikor az üzenet titkosítása és továbbítása egyidejűleg zajlik. Addig a titkosítás előzetes volt, így a vonali titkosítás jelentősen megnövelte a kommunikáció sebességét.

Vernam azonban nem kriptográfus, de helyesen vette észre rejtjelének egy fontos tulajdonságát: minden szalagot csak egyszer szabad használni, majd megsemmisíteni. Ezt a gyakorlatban nehéz alkalmazni, ezért a készüléket több hurkos szalaggá alakították át, amelyeknek ismételt periódusa volt [8] .

Leírás

A kriptorendszert a távirati üzenetek titkosítására javasolták, amelyek bináris szövegek voltak, amelyekben a nyílt szöveget a Baudot-kód képviseli (ötjegyű "impulzuskombinációk" formájában). Ebben a kódban például az "A" betű így nézett ki (1 1 0 0 0). A papírszalagon az „1” szám a lyuknak, a „0” szám pedig a hiányának felelt meg. A titkos kulcsnak egyazon ábécé kaotikus betűkészletének kellett volna lennie [8] .

A titkosított szöveg megszerzéséhez a nyílt szöveget egy XOR művelettel kombinálják a titkos kulccsal . Így például amikor a kulcsot (1 1 1 0 1) alkalmazzuk az "A" betűre (1 1 0 0 0), egy titkosított üzenetet kapunk (0 0 1 0 1): Tudva, hogy a kapott üzenetre rendelkezik a kulccsal (1 1 1 0 1), akkor ugyanazzal a művelettel könnyen megkaphatja az eredeti üzenetet: Az abszolút kriptográfiai erősség érdekében a kulcsnak három kritikus tulajdonsággal kell rendelkeznie [2] : $(11000)\oplus (11101)=(00101)$ $(00101)\oplus (11101)=(11000)$

Legyen egy véletlenszerű diszkrét egyenletes eloszlása: , ahol k a kulcs és N a kulcsban lévő bináris karakterek száma; $P_{k}(k)=1/2^{N}$
A megadott egyszerű szöveg méretével megegyezőnek kell lennie;
Csak egyszer alkalmazza.

Szintén jól ismert az úgynevezett Vernam-rejtjel modulo m , amelyben a nyílt szöveg, a rejtjelezett szöveg és a kulcs jelei a Z m maradékok gyűrűjéből vesznek értékeket . A rejtjel az eredeti Vernam-rejtjel általánosítása, ahol m = 2 [2] .

Például Vernam titkosítási modulo m = 26 (A=0,B=1,…, Z=25):

Kulcs: EVTIQWXQVVOPMCXREPYZ Egyszerű szöveg: ALLSWELLTHATENDSWELL (Minden jó, ha jó a vége) Rejtjelezett szöveg: EGEAMAIBOCOIQPAJATJK

Titkosításkor a transzformáció a Vigenère táblázat szerint történik (a karakterindexek modulo az ábécé hosszának összeadása adja ezt a táblázatot).

A kulcsbetű az oszlop, az egyszerű szöveges betű a sor, a titkosított szöveg pedig a metszéspontban lévő betű.

A kulcs ismerete nélkül egy ilyen üzenet nem értelmezhető. Még ha ki is lehetne próbálni az összes billentyűt, az eredmény egy adott hosszúságú összes lehetséges üzenet lenne, plusz óriási számú értelmetlen megfejtés , amelyek úgy néznek ki, mint egy betűrend. De még értelmes megfejtések között sem lenne mód kiválasztani a kívántat. Ha egy véletlen sorozatot (a kulcsot) egy nem véletlenszerű sorozattal (a nyílt szöveggel) kombinálunk, az eredmény (a titkosított szöveg ) teljesen véletlenszerű, ezért hiányoznak a titkosítás elemzéséhez használható statisztikai jellemzők. [9] .

Kriptográfiai erősség

1945-ben Claude Shannon megírta a "The Mathematical Theory of Cryptography" (csak a második világháború után, 1949-ben oldották fel a titkosításokat a " Theory of Communication in Secret Systems " néven) címmel, amelyben bebizonyította a vernam-rejtjel abszolút kriptográfiai erejét. Vagyis a rejtjelezett szöveg kulcs nélküli elfogása nem ad információt az üzenetről. A kriptográfia szempontjából lehetetlen olyan rendszert elképzelni, amely biztonságosabb a Vernam-rejtjelnél [2] . Az ilyen séma megvalósításának követelményei meglehetősen nem triviálisak, mivel biztosítani kell az üzenet hosszával megegyező egyedi gamma előírását, annak későbbi garantált megsemmisítésével. Ebben a tekintetben a Vernam-rejtjel kereskedelmi használata nem olyan elterjedt, mint a nyilvános kulcsú sémák, és főként a kormányzati szervek által különösen fontos üzenetek továbbítására használják [8] .

Bemutatjuk az abszolút kriptográfiai biztonság bizonyítékát. Legyen az üzenet egy bináris hosszúságú sorozattal ábrázolva . Az üzenet valószínűségi eloszlása bármi lehet. A kulcsot egy azonos hosszúságú bináris sorozat is képviseli , de az összes kulcsra egyenletes eloszlású. $N:m=m_{1},m_{2},\lpontok,m_{n}$ $P_{m}(m)$ $k=k_{1},k_{2},\ldots ,k_{n}$ $P_{k}(k)=1/2^{N}$

A titkosítási sémának megfelelően a nyílt szöveg és a kulcs modulo 2 szekvenciáinak komponensenkénti összegzésével egy titkosított szöveget állítunk elő:

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

A törvényes felhasználó ismeri a kulcsot, és végrehajtja a visszafejtést:

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

Keressük meg a titkosított szövegek N-blokkjainak valószínűségi eloszlását a következő képlet segítségével:

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}

Az eredmény megerősíti azt a jól ismert tényt, hogy két valószínűségi változó összege, amelyek közül az egyik diszkrét egyenletes eloszlású egy véges csoporton , egyenletes eloszlású valószínűségi változó. Így esetünkben a rejtjelezett szövegek eloszlása egységes.

Megírjuk a nyílt és titkosított szövegek közös eloszlását:

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

Keressük a feltételes eloszlást

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

mivel a kulcs és a nyílt szöveg független valószínűségi változók. Teljes:

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

Ha ennek a képletnek a jobb oldalát behelyettesítjük az együttes eloszlási képletbe, akkor azt kapjuk

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

Ami bizonyítja a titkosított szövegek és a nyílt szövegek függetlenségét ebben a rendszerben. Ez abszolút kriptográfiai erősséget jelent [10] .

Hatókör

Jelenleg a Vernam titkosítást ritkán használják. Ez nagyrészt a kulcs jelentős méretének köszönhető, amelynek hosszának meg kell egyeznie az üzenet hosszával. Vagyis az ilyen rejtjelek használata hatalmas költségeket igényel a kulcsfontosságú anyagok előállításához, tárolásához és megsemmisítéséhez. Ennek ellenére a teljesen erős titkosítások, mint például a Vernam, még mindig találtak gyakorlati hasznot a kritikus kommunikációs vonalak viszonylag kis mennyiségű információval történő védelmére. Például a britek és az amerikaiak Vernam-típusú rejtjeleket használtak a második világháború alatt. A modulo 2 Vernam titkosítást a Washington és Moszkva közötti kormányzati forródróton használták, ahol a kulcsfontosságú anyagok papírszalagok voltak, amelyeken a kulcssorozat karaktereit perforálták [2] .

A gyakorlatban lehetőség van egy hosszú, valóban véletlenszerű kulccsal egyszer fizikailag átvinni az információhordozót, majd szükség szerint továbbítani az üzeneteket. A rejtjeltömbök ötlete ezen alapul : a rejtjelező ügyintéző diplomáciai úton vagy személyesen kap egy jegyzetfüzetet, amelynek minden oldala kulcsokat tartalmaz. A fogadó félnek ugyanaz a jegyzettömbje van. A használt oldalakat megsemmisítik [11] .

Hátrányok

Valóban véletlenszerű sorrendre ( kulcsra ) van szükség a Vernam-rejtjel működéséhez . Definíció szerint egy tetszőleges algoritmussal kapott sorozat nem igazán véletlen, hanem pszeudovéletlen. Vagyis nem algoritmikusan, hanem például egy elektronikus fehérzaj -generátor által létrehozott radioaktív bomlás vagy más meglehetősen véletlenszerű események segítségével kell véletlenszerű sorozatot kapni. Annak érdekében, hogy az eloszlás a lehető legközelebb legyen , egy véletlenszerű sorozatot általában egy hash függvényen, például MD5 -ön keresztül vezetnek át [12] .

A Vernam-rejtjel használatának hátránya az üzenet hitelességének és integritásának megerősítésének hiánya. A címzett nem tudja ellenőrizni a sérülés hiányát vagy a feladó hitelességét. Ha egy harmadik fél valamilyen módon felismeri az üzenetet, könnyen visszaállítja a kulcsot, és képes az üzenetet egy másik, azonos hosszúságúra cserélni. A probléma megoldása egy hash függvény használata. Egy hash függvényt számítanak ki az egyszerű szövegből, és az értékét az üzenettel együtt titkosítják. Bármilyen változás az üzenetben, megváltoztatja a hash értékét. Így még ha egy támadó úgy is kézhez kap egy rejtjelező padot, hogy nem ismeri a hash-függvény kiszámításának algoritmusát, nem fogja tudni használni azt információ továbbítására [11] .

Mindig szükség van arra, hogy elegendő számú kulcs legyen kéznél, amelyre a jövőben szükség lehet nagy mennyiségű egyszerű szöveg titkosításához. A szöveg valódi mennyiségét sokszor nehéz előre megbecsülni, különösen a diplomáciai és katonai szférában, ahol a helyzet gyorsan és kiszámíthatatlanul változhat. Ez a kulcsok hiányához vezethet, aminek következtében a kriptográfus vagy újra felhasználhatja a kulcs(oka)t, vagy teljesen megszakíthatja a titkosított kommunikációt.

A probléma a sorozat biztonságos továbbítása és titokban tartása. Ha van olyan üzenetátviteli csatorna, amely megbízhatóan védett a lehallgatástól, akkor egyáltalán nincs szükség rejtjelekre: ezen a csatornán titkos üzenetek továbbíthatók. Ha azonban a Vernam rendszer kulcsát egy másik rejtjellel továbbítják (például DES ), akkor az eredményül kapott rejtjel pontosan annyira védett lesz, mint a DES. Ugyanakkor, mivel a kulcs hossza megegyezik az üzenet hosszával, nem könnyebb továbbítani, mint az üzenetet. A fizikai adathordozón lévő rejtjelező tömb ellopható vagy lemásolható [11] .

A Vernam-rejtjel érzékeny a titkosítási eljárás bármely megsértésére. Voltak olyan esetek, amikor ugyanazt a jegyzettömb oldalt kétszer használták különböző okokból. Például a múlt század 40-es éveiben az amerikai hírszerzés által elfogott szovjet titkosított levelezés teljes mennyisége között olyan üzeneteket találtak, amelyeket duplán használt gammával zártak le. Ez az időszak nem tartott túl sokáig, mert már az 1940-es évek végén az amerikai kriptoanalitikusok első sikerei után a Szovjetunió titkosszolgálatai komoly problémákat tapasztaltak titkosított levelezésük megbízhatóságával kapcsolatban. Az ilyen üzeneteket a következő 40 év során megfejtették a titkos Venona projekt részeként , amelynek dokumentumait később feloldották, és feltették az NSA webhelyére [13] .

Jegyzetek

↑ Szimmetrikus algoritmusok .
↑ 1 2 3 4 5 Fomicsev, 2003 .
↑ Mao, 2005 .
↑ Miller, Frank. Távirati kód a magánélet és a titoktartás biztosítására a táviratok továbbítása során. – C. M. Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: Az egyszeri betét feltalálója . kriptológia . 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . A kódkönyv egy titkosítási űrlapot mutat be a Telegraphs -ig visszamenőleg (2011. július 25.). Letöltve: 2011. július 26.
↑ US 1310719A szabadalom
↑ 1 2 3 Babash et al., 2003 .
↑ Kriptográfia (elérhetetlen link) . Hozzáférés időpontja: 2014. február 8. Az eredetiből archiválva : 2013. november 2.. (határozatlan)
↑ Gabidulin, Ksevetszkij, Kolybelnikov, 2011 , p. 41-43.
↑ 1 2 3 Egyszeri betét .
↑ Gyakran Ismételt Kérdések .
↑ Kiwi, 2005 .

Irodalom

Fomichev V. M. Diszkrét matematika és kriptológia : Előadások kurzusa / szerk. 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. Információbiztonság : tankönyv - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Mao V. Modern kriptográfia : Elmélet és gyakorlat / ford. D. A. Klyushina - M .: Williams , 2005. - S. 255. - 768 p. — ISBN 978-5-8459-0847-6
Robert L. Benson. The Venona Story (angol) // Center for Cryptologic History Nemzetbiztonsági Ügynökség. Archiválva az eredetiből 2010. május 27-én.
Babash A. V. , Goliev Yu. I. , Larin D. A. , Shankin G. P. Cryptographic ideas of the 19th century // Information Security. Bizalmas - Szentpétervár. : 2004. - szám. 3.

Linkek

Szimmetrikus algoritmusok (orosz) .
Dirk Rijmenants. Egyszeri betét (angol) .
Marcus J. Ranum. Egyszeri tömb ( Vernam titkosírása) Gyakran Ismételt Kérdések .
Byrd Kiwi. Ár hibák . - 2005. Archiválva : 2013. december 24.