Vernamin salaus

Vernam- salaus on symmetrinen salausjärjestelmä , jonka Gilbert Vernam keksi vuonna 1917 [1] .

Salaus on eräänlainen kertaluontoinen salausjärjestelmä. Se käyttää boolen yksinomaista-tai- funktiota . Vernam-salaus on esimerkki järjestelmästä, jolla on absoluuttinen kryptografinen vahvuus [2] . Samalla sitä pidetään yhtenä yksinkertaisimmista salausjärjestelmistä [3] .

Historia

Frank Miller kuvasi ensimmäisen kerran vuonna 1882. [4] [5] [6]

Salaus on nimetty lennättäjä Gilbert Vernamin mukaan, joka vuonna 1917 keksi ja vuonna 1919 patentoi järjestelmän lennätinviestien automaattiseen salaukseen.

Vernam ei käyttänyt XOR-konseptia patentissa, vaan toteutti juuri tämän operaation tikapuulogiikassa. Jokainen viestin merkki oli bittikohtaisesti XOR-korjattu (yksinomainen tai) paperiteippinäppäimellä [7] . Joseph Mauborgne (silloin Yhdysvaltain armeijan kapteeni ja myöhemmin signaalijoukkojen päällikkö) muokkasi tätä järjestelmää niin, että avainnauhan merkkijono oli täysin satunnainen, koska tässä tapauksessa kryptausanalyysi olisi vaikeinta.

Vernam loi laitteen, joka suorittaa nämä toiminnot automaattisesti ilman kryptografin osallistumista. Niin kutsuttu "lineaarinen salaus" aloitettiin, kun viestin salaus- ja lähetysprosessit tapahtuvat samanaikaisesti. Siihen asti salaus oli alustavaa, joten linjasalaus lisäsi viestintänopeutta merkittävästi.

Koska Vernam ei kuitenkaan ollut kryptografi, hän huomasi oikein salauksensa tärkeän ominaisuuden - jokaista nauhaa tulisi käyttää vain kerran ja sen jälkeen tuhota. Tätä on vaikea soveltaa käytännössä - siksi laite muunnettiin useiksi silmukkanauhoiksi, joissa oli koprimejaksoja [ 8] .

Kuvaus

Salausjärjestelmää ehdotettiin salaamaan lennätinsanomia, jotka olivat binääritekstejä, joissa selkeä teksti on esitetty Baudot-koodissa (viisinumeroisten "pulssiyhdistelmien" muodossa). Tässä koodissa esimerkiksi kirjain "A" näytti tältä (1 1 0 0 0). Paperinauhalla numero "1" vastasi reikää ja numero "0" - sen puuttumista. Salaisen avaimen piti olla kaoottinen sarja saman aakkoston kirjaimia [8] .

Salatekstin saamiseksi pelkkä teksti yhdistetään XOR -operaatioon salaisella avaimella . Joten esimerkiksi kun käytämme avainta (1 1 1 0 1) kirjaimeen "A" (1 1 0 0 0), saamme salatun viestin (0 0 1 0 1): Tietäen, että vastaanotetulle viestille sinulla on avain (1 1 1 0 1), alkuperäinen viesti on helppo saada samalla toiminnolla: Absoluuttisen kryptografisen vahvuuden saavuttamiseksi avaimella on oltava kolme kriittistä ominaisuutta [2] : $(11000)\oplus (11101)=(00101)$ $(00101)\oplus (11101)=(11000)$

Niillä on satunnainen diskreetti tasainen jakauma: , jossa k on avain ja N on avaimen binäärimerkkien lukumäärä; $P_{k}(k)=1/2^{N}$
oltava samankokoinen kuin määritetty selkeä teksti;
Hae vain kerran.

Tunnettu on myös ns. Vernam-salaus modulo m , jossa selkeän tekstin, salatekstin ja avaimen merkit ottavat arvot jäännösrenkaasta Z m . Salaus on yleistys alkuperäisestä Vernam-salauksesta, jossa m = 2 [2] .

Esimerkiksi Vernam-salauksen modulo m = 26 (A=0,B=1,…, Z=25):

Avain: EVTIQWXQVVOPMCXREPYZ Pelkkä teksti: ALLSWELLTHATENDSWELL (Kaikki hyvin, mikä päättyy hyvin) Salateksti: EGEAMAIBOCOIQPAJATJK

Salattaessa muunnos suoritetaan Vigenère-taulukon mukaan (merkkiindeksien lisäys modulo aakkosten pituus antaa tämän taulukon).

Avainkirjain on sarake, selväkielinen kirjain on rivi ja salakirjoitus on risteyksen kirjain.

Ilman avaimen tuntemista tällaista viestiä ei voida jäsentää. Vaikka kaikkia näppäimiä olisi mahdollista kokeilla, tuloksena olisi kaikki mahdolliset tietynpituiset viestit sekä valtava määrä merkityksettömiä , kirjainten sekamelskaa näyttäviä tulkintoja . Mutta edes mielekkäiden tulkintojen joukossa ei olisi mitään mahdollisuutta valita haluttua. Kun satunnainen sekvenssi (avain) yhdistetään ei-satunnaiseen (selkoteksti), tulos ( salausteksti ) on täysin satunnainen ja siksi siitä puuttuu tilastolliset ominaisuudet, joita voitaisiin käyttää salauksen analysointiin. [9] .

Kryptografinen vahvuus

Vuonna 1945 Claude Shannon kirjoitti "Salauksen matemaattisen teorian" (luokittelu poistettiin vasta toisen maailmansodan jälkeen vuonna 1949 nimellä " Theory of Communication in Secret Systems "), jossa hän osoitti Vernam-salauksen ehdottoman kryptografisen vahvuuden. Toisin sanoen salatekstin sieppaus ilman avainta ei anna mitään tietoa viestistä. Salauksen näkökulmasta on mahdotonta kuvitella Vernam-salausta turvallisempaa järjestelmää [2] . Vaatimukset tällaisen järjestelmän toteuttamiselle ovat melko ei-triviaaleja, koska on varmistettava viestin pituutta vastaavan ainutlaatuisen gamman asettaminen ja sen myöhempi taattu tuhoutuminen. Tässä suhteessa Vernam-salauksen kaupallinen käyttö ei ole yhtä yleistä kuin julkisen avaimen järjestelmät, ja sitä käytetään pääasiassa valtion virastojen erityisen tärkeiden viestien välittämiseen [8] .

Esitämme todisteen absoluuttisesta kryptografisesta vahvuudesta. Esitetään viesti binäärisekvenssillä, jonka pituus on . Viestin todennäköisyysjakauma voi olla mikä tahansa. Avainta edustaa myös samanpituinen binäärisekvenssi, joka jakautuu tasaisesti kaikille avaimille. $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}$

Salausmenetelmän mukaisesti tuotamme salatekstin komponenttikohtaisesti summaamalla selkeän tekstin ja avaimen modulo 2 -sekvenssit:

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

Laillinen käyttäjä tietää avaimen ja suorittaa salauksen purkamisen:

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

Etsitään salatekstien N-lohkojen todennäköisyysjakauma kaavalla:

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}

Tulos vahvistaa hyvin tunnetun tosiasian, että kahden satunnaismuuttujan summa, joista toisella on diskreetti tasainen jakauma äärellisessä ryhmässä , on tasaisesti jakautunut satunnaismuuttuja. Näin ollen meidän tapauksessamme salatekstien jakautuminen on tasaista.

Kirjoitamme selkotekstien ja salatekstien yhteisjakelun:

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

Etsitään ehdollinen jakauma

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

koska avain ja selkeä teksti ovat itsenäisiä satunnaismuuttujia. Kaikki yhteensä:

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

Korvaamalla tämän kaavan oikean puolen yhteisjakaumakaavaksi saadaan

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

Mikä todistaa salatekstien ja selkeiden tekstien riippumattomuuden tässä järjestelmässä. Tämä tarkoittaa absoluuttista kryptografista vahvuutta [10] .

Laajuus

Tällä hetkellä Vernam-salausta käytetään harvoin. Tämä johtuu suurelta osin avaimen merkittävästä koosta, jonka pituuden on vastattava viestin pituutta. Toisin sanoen tällaisten salausten käyttö vaatii valtavia kustannuksia keskeisten materiaalien tuotannosta, varastoinnista ja tuhoamisesta. Siitä huolimatta täysin vahvat salaukset, kuten Vernam, löysivät silti käytännöllistä käyttöä kriittisten viestintälinjojen suojaamiseen suhteellisen pienellä tietomäärällä. Esimerkiksi britit ja amerikkalaiset käyttivät Vernam-tyyppisiä salauksia toisen maailmansodan aikana. Modulo 2 Vernam -salausta käytettiin Washingtonin ja Moskovan välisellä hallituksen vihjelinjalla, jossa avainmateriaalina oli paperiteippejä, joihin näppäinsarjan merkit oli rei'itetty [2] .

Käytännössä tiedonsiirtoväline voidaan fyysisesti siirtää pitkällä, todella satunnaisella avaimella kerran ja sitten lähettää viestejä eteenpäin tarpeen mukaan. Salauslehtien idea perustuu tähän : salakirjoittaja saa diplomaattisessa postissa tai henkilökohtaisesti muistikirjan, jonka jokaisella sivulla on avaimet. Vastaanottavalla osapuolella on sama muistilehtiö. Käytetyt sivut tuhotaan [11] .

Haitat

Vernam-salauksen toimintaan tarvitaan todella satunnainen sekvenssi ( avain ) . Määritelmän mukaan millä tahansa algoritmilla saatu sekvenssi ei ole todella satunnainen, vaan näennäissatunnainen. Toisin sanoen, sinun täytyy saada satunnainen sekvenssi ei algoritmisesti, vaan esimerkiksi käyttämällä elektronisen valkokohinageneraattorin aiheuttamaa radioaktiivista hajoamista tai muita melko satunnaisia tapahtumia. Jotta jakauma olisi mahdollisimman tasainen , satunnainen sekvenssi ohjataan yleensä hash-funktion, kuten MD5 :n, läpi [12] .

Vernam-salauksen käytön haittana on viestin aitouden ja eheyden vahvistamisen puute. Vastaanottaja ei voi varmistaa vaurioiden puuttumista tai lähettäjän aitoutta. Jos kolmas osapuoli jotenkin tunnistaa viestin, se palauttaa avaimen helposti ja pystyy korvaamaan viestin toisella samanpituisella. Ratkaisu ongelmaan on käyttää hash-funktiota. Hajautusfunktio lasketaan selkeästä tekstistä ja sen arvo salataan viestin mukana. Mikä tahansa muutos viestissä muuttaa hash-arvon. Näin ollen vaikka hyökkääjä saisi käsiinsä salausalustan tietämättä hash-funktion laskenta-algoritmia, hän ei voi käyttää sitä tiedon välittämiseen [11] .

Kädessä on aina oltava riittävä määrä avaimia, joita voidaan tarvita tulevaisuudessa suurten tekstimäärien salaamiseen. Tekstin todellista volyymiä on usein vaikea arvioida etukäteen, varsinkin diplomaattisella ja sotilaallisella alalla, jossa tilanne voi muuttua nopeasti ja arvaamattomasti. Tämä voi johtaa avainten puutteeseen, mikä voi saada kryptografin joko käyttämään avaimia uudelleen tai katkaisemaan salatun viestinnän kokonaan.

Ongelmana on sekvenssin turvallinen siirto ja sen salassa pitäminen. Jos on viestinvälityskanava, joka on luotettavasti suojattu sieppaukselta, salauksia ei tarvita ollenkaan: salaisia viestejä voidaan lähettää tämän kanavan kautta. Jos kuitenkin Vernam-järjestelmän avain lähetetään toisella salauksella (esimerkiksi DES ), niin tuloksena oleva salaus suojataan täsmälleen yhtä paljon kuin DES on suojattu. Samalla, koska avaimen pituus on sama kuin viestin pituus, sen välittäminen ei ole helpompaa kuin viestin. Fyysisellä tietovälineellä oleva salausalusta voidaan varastaa tai kopioida [11] .

Vernam-salaus on herkkä kaikille salausmenettelyn rikkomuksille. Oli tapauksia, joissa samaa muistilehtiösivua käytettiin kahdesti eri syistä. Esimerkiksi koko Neuvostoliiton salatun kirjeenvaihdon joukosta, jonka Yhdysvaltain tiedustelupalvelu sieppasi viime vuosisadan 40-luvulla, löydettiin viestejä, jotka oli suljettu kaksinkertaisella gammalla. Tämä ajanjakso ei kestänyt kovin kauan, koska jo amerikkalaisten kryptanalyytikkojen ensimmäisten menestysten jälkeen 1940-luvun lopulla Neuvostoliiton salaiset palvelut saivat tietää vakavista ongelmista salatun kirjeenvaihdon luotettavuudessa. Tällaisia viestejä purettiin seuraavien 40 vuoden aikana osana salaista Venona-projektia , jonka asiakirjoista poistettiin myöhemmin luottamuksellisuus ja ne julkaistiin NSA:n verkkosivuilla [13] .

Muistiinpanot

↑ Symmetriset algoritmit .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Mao, 2005 .
↑ Miller, Frank. Lennätyskoodi yksityisyyden ja salassapitovelvollisuuden takaamiseksi sähkeiden lähettämisessä. - C. M. Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: Kertakäyttöisen tyynyn keksijä . kryptologia . 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . Koodikirja näyttää salauslomakkeen päivämäärät Telegraphsiin (25. heinäkuuta 2011). Haettu 26. heinäkuuta 2011.
↑ US 1310719A -patentti
↑ 1 2 3 Babash et ai., 2003 .
↑ Kryptografia (pääsemätön linkki) . Käyttöpäivä: 8. helmikuuta 2014. Arkistoitu alkuperäisestä 2. marraskuuta 2013. (määrätön)
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , s. 41-43.
↑ 1 2 3 Kertakäyttöinen tyyny .
↑ Usein kysytyt kysymykset .
↑ Kiwi, 2005 .

Kirjallisuus

Fomichev V. M. Diskreetti matematiikka ja kryptologia : Luentokurssi / toim. 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. Tietoturva : oppikirja - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Mao V. Moderni kryptografia : teoria ja käytäntö / käännös. D. A. Klyushina - M .: Williams , 2005. - S. 255. - 768 s. — ISBN 978-5-8459-0847-6
Robert L. Benson. The Venona Story (englanniksi) // Center for Cryptologic History National Security Agency. Arkistoitu alkuperäisestä 27. toukokuuta 2010.
Babash A. V. , Goliev Yu. I. , Larin D. A. , Shankin G. P. 1800-luvun kryptografiset ideat // Tietoturva. Luottamusmies - Pietari. : 2004. - numero. 3.

Linkit

Symmetriset algoritmit (venäjäksi) .
Dirk Rijmenants. Kertakäyttöinen tyyny (englanniksi) .
Marcus J. Ranum. Kertakäyttöinen muistilappu ( Vernamin salakirjoitus ) Usein kysytyt kysymykset .
Byrd Kiwi. Hinta virheitä . - 2005. Arkistoitu 24. joulukuuta 2013.