Egyszerű szöveges támadás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 3-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az ismert szöveges támadás a kriptoanalízis egy olyan típusa, amelyben szabványos szövegrészek vannak jelen a titkosított szövegben , amelyek jelentését az elemző előre ismeri. A második világháború alatt az angol kriptoanalitikusok „tippeknek” nevezték az ilyen szövegrészeket ( angol kiságy – hint, cheat sheet) [Megjegyzés. 1] .

A különböző országokból származó titkosítások gyakran tartalmaztak konkrét kifejezéseket: Heil Hitler! , Banzai! , Minden ország proletárjai, egyesüljetek! stb.

Egy másik példa a módszer használatára az egyszerű gamma algoritmus elleni kriptográfiai támadás . Ha legalább egy nyílt szöveg ismert, és a hozzá tartozó rejtjelezett szöveg hossza nagyobb vagy egyenlő, mint a gamma (kulcs) hossza, akkor az utóbbi egyértelműen megtalálható.

Leírás

A Kerckhoff-elv szerint a kriptoanalitikus minden információval rendelkezik a kriptorendszerről, kivéve egy bizonyos paramétercsoportot, amelyet kulcsnak neveznek . A rejtjelelemző feladata egy közös titkosítási kulcs vagy dekódolási algoritmus megtalálása, amellyel más rejtjelezett szövegeket is dekódolhat ugyanazzal a kulccsal.

Adott:

P 1 , P 2 , …, P i – egyszerű szövegek
C 1 =E k (P 1 ), C 2 =E k (P 2 ), …, C i =E k (P i ) – a megfelelő titkosított szövegek

Meg kell találni:

k a titkosítási kulcs, vagy
D(C) - visszafejtő funkció (nem a kulcs függvénye, hanem csak a rejtjelezett szöveg)

Különbségek a kriptoanalízis egyéb módszereitől

Csak titkosított szövegű támadás

A csak rejtjelezett szöveget használó támadás egy elsődleges kriptográfiai módszer, amelyben a titkosítási elemző csak a rejtjelezett szövegeket ismeri. A plaintext támadás továbbfejlesztése, hiszen ismerjük a forrásszövegeket is. Például a titkosított szöveg alapú kriptográfiai elemzéshez gyakran használt frekvencia kriptoanalízis módszer a nyílt szöveg alapú kriptográfiai elemzés esetén több lehetőséget nyit meg, hiszen a titkosított üzenet frekvenciaválaszát nem a nyelv frekvenciaválaszával kell összehasonlítani, hanem az eredeti üzenet frekvenciaválasza (adott esetben a nyitott szöveg frekvenciaválasza), a szöveg és a nyelv frekvenciaválasza nagymértékben változhat).

Választott egyszerű szöveges támadás

Választott egyszerű szöveges támadás – Ez a fajta támadás az egyszerű szöveg alapú módszer továbbfejlesztése. Itt a kriptoanalizátornak számos, előre ismert egyszerű szöveg/titkosszöveg párja is van. De kaphat az általa előre kiválasztott szövegeknek megfelelő titkosított szövegeket is. Az ilyen titkosított szövegek beszerzésének módja az, hogy például sima szöveggel írunk egy levelet, miközben olyan embernek adjuk ki magunkat, akitől titkosított üzenetet várunk, és bizonyos feltételek mellett ebből a szövegből idézettel is kaphatunk választ, de már titkosított formában. A különbség e módszer és az egyszerű szöveges támadás között az, hogy ebben a módszerben a kriptoanalizátor kiválaszthatja, hogy melyik szöveget szeretné titkosítani. A csak egyszerű szöveges módszerben pedig minden egyszerű szöveg/titkosított szöveg pár előre ismert.

Adaptive Plaintext Attack

Az adaptívan választott egyszerű szöveges támadás a választott egyszerű szöveges támadás kiterjesztése. A különbség abban rejlik, hogy miután megkapta az adott nyílt szövegnek megfelelő rejtjelezett szöveget, a kriptoanalitikus maga dönti el, hogy melyik szöveget kívánja tovább titkosítani, ami mintegy visszacsatolást ad a hackelési módszerhez. Ez a módszer közvetlen hozzáférést igényel a titkosító eszközhöz.

Alkalmazási példa a történelemben

Az Enigma esetében a német főparancsnokság nagyon aprólékosan biztosította a rendszert, mivel tisztában voltak az egyszerű szövegek alapján történő feltörés lehetséges problémájával. A feltörésen dolgozó csapat az üzenetek elküldésének időpontja alapján kitalálhatta a szövegek tartalmát. Például az időjárás-előrejelzést minden nap ugyanabban az időben továbbították. A katonai üzenetekre vonatkozó előírások szerint minden üzenet ugyanazon a helyen tartalmazta az "Időjárás" (Vizesebb) szót, és az adott terület időjárásának ismerete nagy segítséget jelentett az üzenet többi részének tartalmának kitalálásában. Szintén nagyon hasznosak voltak a tiszttől kapott üzenetek, aki minden alkalommal "Nincs jelentendő" üzenetet küldve, amely anyagot szolgáltatott a kriptoanalízishez. Más parancsnokok is szabványos válaszokat küldtek, vagy válaszaik szabványos részeket tartalmaztak.

Miután egy elfogott német bevallotta a kihallgatás során, hogy a kezelőknek parancsot kaptak a számok titkosítására úgy, hogy minden számjegyet betűkkel írnak, Alan Turing átnézte az üzeneteket, és megállapította, hogy az "eins" szó az üzenetek 90%-ában előfordul. Ez alapján Eins készített egy katalógust, amely a rotorok összes lehetséges pozícióját, kezdőpozícióit és az Enigma kulcskészleteket tartalmazza.

Most

A modern titkosítások rosszul alkalmazkodnak ehhez a kriptoanalízis-módszerhez. Például a DES feltöréséhez megközelítőleg egyszerű szöveg/titkosított szöveg párokra van szükség. $2^{{47}}$

Ugyanakkor a különféle titkosított archívumok, például a ZIP , sebezhetőek a támadás ilyen formájával szemben. Ebben az esetben a támadónak, aki titkosított ZIP fájlok csoportját akarja megnyitni, csak egy titkosítatlan fájlt kell tudnia az archívumból vagy annak egy részéből, amely ebben az esetben tiszta szövegként fog működni. Továbbá a szabadon elérhető programok segítségével gyorsan megtalálják a teljes archívum visszafejtéséhez szükséges kulcsot. A feltörő megpróbálhatja megtalálni a titkosítatlan fájlt az interneten vagy más archívumokban, vagy megpróbálhatja visszaállítani az egyszerű szöveget a titkosított archívum nevének ismeretében.

Alapvető módszerek

A kriptoanalízis lineáris módszere

A nyílt sajtóban a kriptoanalízis lineáris módszerét először Matsui japán matematikus javasolta. A módszer feltételezi, hogy a kriptoanalizátor ismeri a nyílt szöveget és a megfelelő titkosított szövegeket. A titkosítás során leggyakrabban modulo 2 -es kulccsal történő szöveg hozzáadása, keverési és szórási műveletek használatosak. A kriptoanalitikus feladata egy ilyen lineáris közelítés megtalálása

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

melyik lesz a legjobb. Legyen annak a valószínűsége, hogy (1) teljesül. Egyértelmű, hogy szükségünk van -ra, és az is, hogy az érték maximális legyen. Ha ez az érték elég nagy, és a kriptoanalitikus elég párat ismer a nyílt szövegből és a megfelelő titkosított szövegből, akkor az (1) egyenlőség jobb oldalán lévő kulcs bitjeinek modulo 2 összege egyenlő a legvalószínűbbvel. a megfelelő bitek modulo 2 összegének értéke a nyitott és titkosított szövegekben a bal oldalon. Abban az esetben, ha , az (1) jobb oldalán lévő összeg nulla, ha a bal oldalon lévő bitek összege a rejtjelezett szövegpárok több mint felében nulla. A jobb oldali bitek összege eggyel egyenlő, ha a bal oldali bitek összege a szövegek eseteinek több mint felében eggyel egyenlő. Ha , akkor fordítva: a jobb oldali bitek összege eggyel egyenlő, ha a bal oldali bitek összege a szövegek több mint felénél nulla. A jobb oldali bitek összege pedig nulla, ha a bal oldali bitek összege eggyel több, mint az idő fele. A kulcs minden bitjének megtalálásához most meg kell oldani egy lineáris egyenletrendszert e bitek megfelelő ismert kombinációira. Ez nem nehéz, mivel ennek a rendszernek a bonyolultságát a kulcshossz legfeljebb egyharmad fokának megfelelő polinom fejezi ki. A rejtjel feltöréséhez szükséges egyszerű szöveg/rejtjelezett szöveg párok számát a képlet becsüli meg . Egy DES-rejtjel ilyen módon történő feltöréséhez körülbelül 247 nyitott/titkosított blokkpárra van szükség. $p$ $p\approx 0,5$ $|p-0,5|$ $p>0,5$ $p<0,5$ $N=|p-1/2|2^{{-2}}$

A kriptoanalízis differenciális módszere.

A kriptoanalízis differenciális módszerét (DCA) 1990-ben E. Biham és A. Shamir javasolta. A differenciális kriptoanalízis kísérlet a blokk-rejtjelek titkos kulcsának feltörésére, amelyek kriptográfiailag gyenge titkosítási műveletek ismételt alkalmazásán alapulnak. A kriptoanalízis feltételezi, hogy minden titkosítási ciklus saját titkosítási alkulcsát használja. A DFA használhat kiválasztott és ismert egyszerű szövegeket is. Az r-ciklikus rejtjel megnyitására irányuló kísérletek sikerének fő feltétele az (r-1)-edik ciklus differenciáleinek megléte, amelyek nagy valószínűséggel rendelkeznek. Az i-edik ciklus differenciálját úgy definiáljuk, mint egy olyan számpárt , amelynél az x és x* különböző nyíltszövegpárok, amelyeknek különbsége van, az i-edik ciklus után y és y* párat eredményezhet különbséggel . Az i-ciklusú differenciál valószínűsége annak a feltételes valószínűsége , hogy y és y* különbsége az i-edik ciklus után egyenlő , feltéve, hogy kezdetben x és x* különbséggel volt . Az egyszerű szövegű x és az 1 , 2 , … és i alkulcsok függetlenek és véletlenszerűek. A DFA-eljárás egy r-ciklikus titkosításhoz kiválasztott egyszerű szövegekkel a következő lehet: $(\alpha ,\beta )_{i},$ $\alpha$ $\beta$ $P(\Delta y(i)=\beta |\Delta x=\alpha )$ $\beta$ $\alpha$

Ez a szakasz az előszámítások szakasza. Ezen keresünk egy (r-1) ciklusú differenciálművet . Az adott halmazt a valószínűségük értéke szerint rendezzük. $(\alpha _{1},\beta _{1})_{r-1},(\alpha _{2},\beta _{2})_{r-1},... .(\alpha _{s},\beta _{s})_{r-1}$
Ebben a szakaszban úgy kell kiválasztanunk x és x* értéket, hogy a különbségük egyenlő legyen -vel, ezekhez van egy y(r), y*(r) titkosított szövegpár. Úgy gondoljuk, hogy az utolsó előtti ciklus kimenetén a különbség egyenlő a legvalószínűbb . Egy hármas esetén megtaláljuk a k (r) alkulcs minden lehetséges értékét . Növeljük a számlálót az előfordulás minden ilyen érték kapcsolódik (r) . $\alpha_{1}$ $\Delta y(r-1)=\beta _{1}$ $(\Delta y(r-1),y(r),y^{*}(r))$
Ebben a szakaszban addig ismételjük az előző bekezdést, amíg egy vagy több alkulcs gyakrabban nem jelenik meg, mint mások. Az adott kulcsot (vagy kulcskészletet) vesszük (r) megoldásának .
Ebben a szakaszban megismételjük az 1-3 lépéseket az (r-1)-edik ciklushoz, míg az y(r-1) értékeit úgy számítjuk ki, hogy az y(r) dekódolását a programban található ( r ) kulcs segítségével előző lépés. És addig ismételjük ezeket a műveleteket, amíg meg nem találjuk az összes ciklus kulcsát.

Ezt a módszert eredetileg egyetlen rejtjel megoldására javasolták, de aztán sok Markov-rejtjel kriptoanalízisében sikeresnek bizonyult. Egy titkosítást Markov-félenek nevezünk, ha egy cikluson belüli egyenlete teljesíti azt a feltételt, hogy a differenciál valószínűsége nem függ a nyílt szövegek megválasztásától. Ekkor ha a ciklusok billentyűi függetlenek, akkor az egyes ciklusok különbségeinek sorozata egy Markov-láncot alkot, amelyben minden következő elem csak az előzőtől függ. A Markov-rejtjelekre példa a DES és a FEAL. Mutassuk meg, hogy a független alkulcsokkal rendelkező Markov r-ciklikus rejtjel akkor és csak akkor sebezhető a DFA-val szemben, ha egy ciklusra a kulcs könnyen kiszámítható az ismert hármasból . Van egy (r-1) differenciál is , és ennek valószínűsége kielégíti azt a kifejezést, ahol n a bitek száma a rejtjelezett szöveg blokkban. A Q(r) r-ciklikus rejtjel kulcsának megtalálásának bonyolultságát a felhasznált titkosítások számaként határozzuk meg, majd ezt követi a kulcs megtalálása: ahol Különösen, ha , akkor egy ilyen támadás nem lesz sikeres. Mivel az alkulcs keresése munkaigényesebb, mint a titkosítás művelete, a komplexitás mértékegysége egy ciklus lehetséges alkulcsainak megtalálásának összetettsége ismert hármasok felett . a titkosítás (pl. linearitás, egyéb.) Csak a differenciálok valószínűség-eloszlásának egyenetlenségén alapul. $(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} }=\operátornév {max} (\alpha )\operátornév {max} (\beta )(P(\Delta y(r-1)=\beta |\Delta x=\ alfa )).$ $P_{\mathrm {max} }\kb. 1/(2^{n}-1)$ $(\Delta y(r-1),y(r),y^{*}(r)).$

Jegyzetek

↑ A kiságy szónak (főnév és ige egyaránt) több tucat jelentése van az angolban, beleértve a szlengeket is . Az iskolai szlengben a kiságy utalást, csalólapot stb. jelent. illegális vizsgák letételének módszerei

Irodalom

Bruce Schneier. Alkalmazott kriptográfia . Archivált : 2014. február 28. a Wayback Machine -nél }
David Kahn. Kódtörők.

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