Selkeä teksti -hyökkäys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3.1.2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Tunnettu selkotekstihyökkäys on eräänlainen kryptausanalyysi , jossa salatekstissä on standardinmukaisia kohtia , joiden merkitys on analyytikon tiedossa etukäteen. Toisen maailmansodan aikana englantilaiset kryptanalyytikot kutsuivat tällaisia kohtia "vihjeiksi" ( englanniksi crib - vihje, huijauslehti) [Huom. 1] .

Eri maiden salakirjoitukset sisälsivät usein erityisiä ilmaisuja: Heil Hitler! , Banzai! , Kaikkien maiden proletaarit, liittykää yhteen! jne.

Toinen esimerkki menetelmän käytöstä on salaushyökkäys yksinkertaista gamma -algoritmia vastaan . Jos ainakin yksi selväteksti tunnetaan ja sitä vastaavan salatekstin pituus on suurempi tai yhtä suuri kuin gamman (avaimen) pituus, niin jälkimmäinen löydetään yksiselitteisesti.

Kuvaus

Kerckhoffsin periaatteen mukaan kryptoanalyytikolla on kaikki tiedot salausjärjestelmästä lukuun ottamatta tiettyä parametrijoukkoa, jota kutsutaan avaimeksi . Kryptusanalyytikon tehtävänä on löytää yhteinen salausavain tai salauksenpurkualgoritmi muiden salaustekstien purkamiseksi samalla avaimella.

Annettu:

P 1 , P 2 , …, P i — selkotekstit
C 1 =E k (P 1 ), C 2 =E k (P 2 ), …, C i =E k (P i ) — niiden vastaavat salatekstit

Pitää löytää:

k on salausavain tai
D(C) - salauksenpurkutoiminto (ei avaimen, vaan vain salatekstin funktiona)

Erot muihin kryptausanalyysimenetelmiin

Vain salakirjoitushyökkäys

Vain salakirjoitushyökkäys on ensisijainen kryptausanalyysitekniikka, jossa kryptanalyytikko tuntee vain salatekstit. Selkotekstihyökkäys on parannus siihen, koska tunnemme myös lähdetekstit. Esimerkiksi salatekstipohjaisessa kryptoanalyysissä usein käytetty taajuuskryptausanalyysimenetelmä selkeän tekstipohjaisen kryptausanalyysin tapauksessa avaa enemmän mahdollisuuksia, koska salatun viestin taajuusvastetta ei tarvitse verrata kielen taajuusvasteeseen, vaan sen taajuusvasteeseen. alkuperäisen viestin taajuusvaste (tietyissä tapauksissa avoimen tekstin taajuusvaste), teksti ja kielen taajuusvaste voivat vaihdella suuresti).

Valittu selkokielinen hyökkäys

Valittu selkokielinen hyökkäys - Tämäntyyppinen hyökkäys on parannus selkeään tekstiin perustuvaan menetelmään. Tässä kryptanalyytikolla on myös joukko selväteksti/salateksti-pareja, jotka ovat etukäteen tiedossa. Mutta hän voi myös vastaanottaa etukäteen valitsemiaan tekstejä vastaavia salatekstejä. Tapa saada tällaisia salatekstejä on esimerkiksi kirjoittaa kirje pelkällä tekstillä, samalla teeskennellen olevansa henkilö, jolta odotetaan salattua viestiä, ja tietyin edellytyksin voit saada vastauksen lainauksella tästä tekstistä, mutta jo salatussa muodossa. Ero tämän menetelmän ja selkeän tekstin hyökkäyksen välillä on, että tässä menetelmässä kryptanalyytikko voi valita, minkä tekstin hän haluaa salata. Ja pelkkä teksti -menetelmässä kaikki selväteksti/salateksti-parit tunnetaan etukäteen.

Adaptive Plaintext Attack

Mukautuvasti valittu selväkielihyökkäys on valitun selväkielihyökkäyksen laajennus. Ero on siinä, että saatuaan tiettyä selkeää tekstiä vastaavan salatekstin kryptanalyytikko päättää itse, minkä tekstin haluaa edelleen salata, mikä ikään kuin lisää palautetta hakkerointimenetelmään. Tämä menetelmä vaatii suoran pääsyn salauslaitteeseen.

Esimerkki sovelluksesta historiassa

Enigman tapauksessa Saksan korkea komento oli erittäin huolellinen järjestelmän turvaamisessa, koska he olivat tietoisia mahdollisesta murtumisongelmasta, joka perustuu selkeisiin teksteihin. Hakkeroinnin parissa työskennellyt tiimi saattoi arvata tekstien sisällön sen perusteella, milloin viestit lähetettiin. Esimerkiksi sääennuste lähetettiin joka päivä samaan aikaan. Sotilasviestien määräysten mukaan jokainen viesti sisälsi sanan "Sää" (kosteampi) samassa paikassa ja tietyn alueen säätiedot auttoivat suuresti arvaamaan muun viestin sisältöä. Erittäin hyödyllisiä olivat myös viestit poliisilta, joka lähetti "Ei mitään raportoitavaa" joka kerta tarjoten materiaalia kryptausanalyysiin. Myös muut komentajat lähettivät vakiovastauksia tai heidän vastauksensa sisälsivät vakioosia.

Sen jälkeen kun vangittu saksalainen tunnusti kuulustelun aikana, että operaattoreita käskettiin salaamaan numerot kirjoittamalla jokainen numero kirjaimin, Alan Turing kävi läpi viestit ja totesi, että sana "eins" esiintyy 90 prosentissa viesteistä. Tämän perusteella Eins loi luettelon, joka sisälsi kaikki mahdolliset roottoreiden asennot, alkuasennot ja Enigma-näppäinsarjat.

Nyt

Nykyaikaiset salaukset soveltuvat huonosti tälle kryptausanalyysimenetelmälle. Esimerkiksi DES:n murtaminen vaatii noin selväteksti/salateksti-pareja. $2^{{47}}$

Samaan aikaan useat salatut arkistot, kuten ZIP , ovat alttiina tälle hyökkäykselle. Tässä tapauksessa hyökkääjän, joka haluaa avata ryhmän salattuja ZIP-tiedostoja, on tiedettävä vain yksi salaamaton tiedosto arkistosta tai sen osasta, joka tässä tapauksessa toimii selkeänä tekstinä. Lisäksi vapaasti saatavilla olevien ohjelmien avulla koko arkiston salauksen purkamiseen tarvittava avain löytyy nopeasti. Krakkauslaite voi yrittää löytää salaamattoman tiedoston Internetistä tai muista arkistoista tai yrittää palauttaa selkeän tekstin tuntemalla nimen salatusta arkistosta.

Perusmenetelmät

Kryptusanalyysin lineaarinen menetelmä

Avoimessa lehdistössä japanilainen matemaatikko Matsui ehdotti ensimmäisenä lineaarista kryptaanalyysimenetelmää. Menetelmässä oletetaan, että kryptanalyytikko tietää selkeän tekstin ja vastaavat salatekstit. Useimmiten salattaessa käytetään modulo 2 -tekstin lisäystä avaimella, sekoitus- ja sirontatoimintoja. Kryptusanalyytikon tehtävänä on löytää tällainen lineaarinen approksimaatio

$x_{i_{1}}+\ldots +x_{i_{r}}+y_{j_{1}}+y_{j_{s}}=z_{k_{1}}+\ldots +z_ {k_{t}}$ , (yksi)

mikä tulee olemaan paras. Antaa olla todennäköisyys, että (1) täyttyy. On selvää, että tarvitsemme , ja myös, että arvo on maksimi. Jos tämä arvo on riittävän suuri ja kryptanalyytikko tuntee tarpeeksi selkeän tekstin ja vastaavan salatekstin pareja, niin avaimen bittien summa modulo 2 vastaavassa paikassa yhtälön (1) oikealla puolella on yhtä suuri kuin todennäköisin. vasemmalla puolella olevien avointen ja salaustekstien vastaavien bittien modulo 2 summan arvo. Siinä tapauksessa , että (1):n oikealla puolella oleva summa on nolla, kun vasemman puolen bittien summa on nolla yli puolessa salatekstipareista. Oikean puolen bittien summa on yhtä suuri kuin yksi, jos vasemman puolen bittien summa on yhtä suuri kuin yksi yli puolessa tekstitapauksista. Jos , niin päinvastoin: oikean puolen bittien summa on yhtä suuri kuin yksi, jos vasemman puolen bittien summa on nolla yli puolella teksteistä. Ja oikean puolen bittien summa on nolla, jos vasemman puolen bittien summa on yksi enemmän kuin puolet ajasta. Avaimen jokaisen bitin löytämiseksi on nyt tarpeen ratkaista lineaarinen yhtälöjärjestelmä näiden bittien vastaaville tunnetuille yhdistelmille. Tämä ei ole vaikeaa, koska tämän järjestelmän monimutkaisuus ilmaistaan polynomilla, joka on enintään kolmas aste avaimen pituudesta. Salauksen rikkomiseen tarvittavien selväkieli/salateksti-parien määrä arvioidaan kaavalla . DES-salauksen rikkomiseksi tällä tavalla käy ilmi, että tarvitaan noin 247 avointa/salattua lohkoparia. $s$ $p\noin 0,5$ $|p-0,5|$ $p>0,5$ $p<0,5$ $N=|p-1/2|2^{{-2}}$

Differentiaalinen kryptausanalyysimenetelmä.

E. Biham ja A. Shamir ehdottivat differentiaalista kryptoanalyysimenetelmää (DCA) vuonna 1990. Differentiaalinen kryptausanalyysi on yritys murtaa lohkosalausten salainen avain, jotka perustuvat kryptografisesti heikkojen salausoperaatioiden toistuvaan soveltamiseen r kertaa. Salausanalyysi olettaa, että jokainen salausjakso käyttää omaa salauksen aliavaintaan. DFA voi käyttää sekä valittuja että tunnettuja selkeitä tekstejä. Pääedellytys r-syklisen salauksen avaamisyritysten onnistumiselle on (r-1) -jakson differentiaalien olemassaolo, jolla on suuri todennäköisyys. i:nnen jakson differentiaali määritellään lukupariksi siten, että eri selkeiden tekstien x ja x* pari, joilla on ero , voi i:nnen jakson jälkeen tuottaa y:n ja y*:n parin erolla . I-syklin differentiaalin todennäköisyys on ehdollinen todennäköisyys , että y:n ja y*:n ero i:nnen syklin jälkeen on yhtä suuri , edellyttäen, että alun perin x:n ja x*:n ero on . Selkeä teksti x ja aliavaimia 1 , 2 , …, i pidetään riippumattomina ja satunnaisina. DFA-menettely r-sykliselle salaukselle, jossa on valitut selkotekstit, voi olla seuraava: $(\alpha ,\beta )_{i},$ $\alpha$ $\beeta$ $P(\Delta y(i)=\beta |\Delta x=\alpha )$ $\beeta$ $\alpha$

Tämä vaihe on ennakkolaskelmien vaihe. Siitä etsimme sarjaa (r-1)-jaksodifferentiaaleja . Järjestämme annetut sarjat niiden todennäköisyyksien arvon mukaan. $(\alpha _{1},\beta _{1})_{r-1},(\alpha _{2},\beta _{2})_{r-1},... .(\alpha _{s},\beta _{s})_{r-1}$
Tämä vaihe edellyttää, että valitsemme x ja x* niin, että niiden ero on yhtä suuri kuin , niille meillä on salatekstien pari y(r), y*(r). Uskomme, että toiseksi viimeisen syklin lähdössä ero on yhtä suuri kuin todennäköisin . Triplelle löydämme aliavaimen k (r) kaikki mahdolliset arvot . Kasvatamme jokaisen sellaisen arvon esiintymisen laskuria, joka on kytketty (r) . $\alpha_{1}$ $\Delta y(r-1)=\beta _{1}$ $(\Delta y(r-1),y(r),y^{*}(r))$
Tässä vaiheessa toistamme edellistä kappaletta, kunnes yksi tai useampi aliavain alkaa ilmestyä useammin kuin muut. Otamme annetun avaimen (tai näppäinjoukon) ratkaisuksi (r) .
Tässä vaiheessa toistamme vaiheet 1-3 (r-1) syklille, kun taas y(r-1):n arvot lasketaan purkamalla y(r):n salaus käyttämällä avainta (r) :lle, joka löytyy Edellinen askel. Ja toistamme näitä toimia, kunnes löydämme kaikkien syklien avaimet.

Tätä menetelmää ehdotettiin alun perin yhden salauksen ratkaisemiseen, mutta sitten se osoitti menestystä monien Markovin salausten kryptausanalyysissä. Salausta kutsutaan Markoviksi, jos sen yhtälö yhdellä syklillä täyttää ehdon, että differentiaalin todennäköisyys ei riipu selkeiden tekstien valinnasta. Sitten jos syklien näppäimet ovat riippumattomia, niin kunkin syklin erojen sarja muodostaa Markov-ketjun, jossa jokainen seuraava elementti riippuu vain edellisestä. Esimerkkejä Markovin salakirjoista ovat DES ja FEAL. Osoitetaan, että Markovin r-syklinen salaus itsenäisillä aliavaimilla on alttiina DFA:lle, jos ja vain jos avain voidaan helposti laskea yhden syklin aikana tunnetusta kolmiosasta . On myös (r-1) differentiaali ja sen todennäköisyys täyttää lausekkeen, jossa n on bittien lukumäärä salatekstilohkossa. R-syklisen salauksen Q(r) avaimen löytämisen monimutkaisuus määritellään käytettyjen salausten lukumääränä, jota seuraa avaimen löytäminen: missä Erityisesti jos , niin tällainen hyökkäys ei onnistu. Koska aliavaimen löytäminen on työläämpää kuin salaus, niin monimutkaisuuden yksikkönä on se, kuinka monimutkainen on löytää mahdolliset aliavaimet yhdelle syklille tunnettujen kolmioiden yli.. Differentiaalisen krypta-analyysin erottuva piirre on, että se ei juuri käytä algebrallisia ominaisuuksia salauksen (kuten lineaarisuus, muut.) Se perustuu vain differentiaalien todennäköisyysjakauman epäyhtenäisyyteen. $(y,y^{*},\Delta x)$ ${\displaystyle (\alpha ,\beta )_{r-1))$ $P(\Delta y(r-1)=\beta |\Delta x=\alpha )\gg 2^{-n},$ $Q(r)\geqslant 2/(P_{\mathrm {max} }-1/(2^{n}-1)),$ $P_{\mathrm {max} }=\operaattorinimi {max} (\alpha )\operaattorinimi {max} (\beta )(P(\Delta y(r-1)=\beta |\Delta x=\ alfa )).$ $P_{\mathrm {max} }\noin 1/(2^{n}-1)$ $(\Delta y(r-1),y(r),y^{*}(r)).$

Muistiinpanot

↑ Sanalla crib (sekä substantiivi että verbi) on kymmeniä merkityksiä englanniksi, mukaan lukien slangi . Erityisesti kouluslangissa sänky tarkoittaa vihjettä, huijauslehteä jne. laittomia menetelmiä kokeiden läpäisemiseksi

Kirjallisuus

Bruce Schneier. Sovellettu kryptografia . Arkistoitu 28. helmikuuta 2014 Wayback Machinessa }
David Kahn. Koodin katkaisijat.

Welchman, Gordon (1982), The Hut Six Story: Breaking the Enigma Codes , Harmondsworth: Allen Lane, ISBN 0713912944