Titkosítási algoritmus GOST 28147-89. Egyszerű csere módszer. - Archívum WASM.RU

„Amíg élsz, ne halj meg, nézd meg ezt a világot.
Itt sokaknak halott a lelke - belül halottak.
De sétálnak és nevetnek, nem tudva, hogy nem azok,
Ne siettesse halálos óráját - mondta nekem.

Aria, "Magas fent"

2.1 Feistel hálózatok.
2.2 Blokk titkosítás GOST 28147-89

3.1 Kulcs információ
3.2 A titkosítási átalakítás fő lépése

3.3 Alap ciklusok:“ 32-Z” , “ 32-R” .

4.1 A titkosítás átalakításának fő lépése
4.2 Az algoritmus sebességének növelése
5. Főbb információs követelmények
6. A felhasznált irodalom jegyzéke
7. Köszönetnyilvánítás.

Bevezetés.

Ez a dokumentum az én kísérletem, hogy leírjak egy módszert, amellyel egyszerűen lecserélhetjük a GOST 28147-89 titkosítási algoritmust a legegyszerűbb, de ennek ellenére technikailag kompetens nyelvre. Az első hat pont elolvasása után az olvasó elmondja véleményét arról, hogy mennyire jól tettem.

Annak érdekében, hogy munkám nagyobb hasznot nyújtson, javaslom, hogy fegyverezze fel magát a használt irodalom jegyzékében feltüntetett szerzők munkáival. Javasolt továbbá, hogy a számológép rendelkezzen funkcióval a művelet kiszámításához. XOR mivel A cikk elolvasása feltételezi, hogy az olvasó ezt a titkosítási algoritmust kívánta tanulmányozni. Bár referenciaként is alkalmas, de ezt a cikket pontosan képzésként írtam.

Előzetes információk a blokkolt titkosításokról.

Mielőtt elkezdenénk nézni az algoritmust, meg kell ismernünk az ilyen típusú kódok létrehozásának történetét. Az algoritmus a blokkotitkosítás kategóriájába tartozik, amelynek architektúrájában az információ véges számú blokkra oszlik, a végső természetesen nem teljes. A titkosítási folyamat a titkosítást alkotó teljes blokkokon megy keresztül. Az utolsó blokkot, ha hiányos, kiegészítik valamivel (az alábbiakban a kitöltés árnyalatairól szólok), és ugyanúgy titkosítva, mint a teljes blokkok. Titkosítás alatt azt az eredményt értem, hogy a titkosítási funkció egy bizonyos adatmennyiségre hat, amelyet a felhasználó küldött titkosításra. Más szóval, a titkosítás a titkosítás végeredménye.

A blokkolt titkosítás fejlődésének története a 70 -es évek elejéhez kapcsolódik, amikor az IBM, felismerve az adatok védelmének szükségességét, amikor adatokat továbbít a számítógépes kommunikációs csatornákon keresztül, saját kutatási programjába kezdett, amely az elektronikus hálózatok információinak védelmével foglalkozik, beleértve a titkosítást.

Az IBM kutatói - fejlesztői csoportja, amely szimmetrikus kulcshasználati sémával kezdte a titkosítási rendszerek kutatását, dr. Horst Feistel.

2.1 Feistel hálózatok

A Feistel által a klasszikus irodalomban javasolt új titkosítási módszer architektúráját "The Feistel Architecture" -nek hívják, de jelenleg az orosz és a külföldi irodalomban egy bevált kifejezést használnak - "Feistel hálózata" vagy Feistel NetWork. Ezt követően a "Lucifer" titkosítás erre az architektúrára épült - amelyet később publikáltak, és új érdeklődési hullámot keltett általában a kriptográfia iránt.

A "Feistel network" architektúra ötlete a következő: az információs adatfolyam n bit méretű blokkokra van felosztva, ahol n páros szám. Mindegyik blokk két részre van osztva-L és R, majd ezeket a részeket egy iteratív blokkotitkosítóba táplálják, amelyben a j-edik szakasz eredményét az előző j-1 szakasz eredménye határozza meg! Ezt egy példával szemléltethetjük:

Rizs. 1

Ahol az A függvény a blokk titkosítás fő művelete. Ez lehet egy egyszerű művelet, például egy XOR művelet, vagy lehet egy bonyolultabb formája is, mint egy sor egyszerű művelet - modulo összeadás, bal eltolás, elemcsere stb. Együttesen, ezek az egyszerű műveletek az úgynevezett - a titkosítási átalakítás fő lépése.

Meg kell jegyezni, hogy a függvény működésének kulcsfontosságú elemei a kulcsfontosságú elemek ellátása és a XOR művelet, és ezeknek a műveleteknek a jól átgondolt működéséből a rejtjel egészének titkosítási erejéről beszél.

Annak érdekében, hogy a Feistel -hálózatok elképzelése végre világos legyen, fontolja meg a legegyszerűbb esetet, amely a rizs. 1, ahol az A függvényben - lesznek „mod 2” („xor”) műveletek, de ez legegyszerűbb egy eset, súlyosabb helyzetben, például az állami jelentőségű információk elrejtése, az A funkció összetettebb lehet (amennyire láttam, az A funkció valóban nagyon összetett):

Kezdeti adatok:

L = 1110b, R = 0101, K = 1111b

Vegyél egy titkosítást

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Magyarázzuk el tetteinket:

1. Ez a művelet az add mod 2 4. A gyakorlatban egy ilyen művelet egyszerű összeadásra redukálódik, ahol két számot kell hozzáadnunk, és figyelmen kívül kell hagynunk az 5. számjegyre történő átvitelt. Mivel ha egy szám bináris ábrázolásának számjegye fölé teszünk kitevőket, akkor az ötödik számjegy felett négy kitevő lesz, nézzük meg az alábbi ábrát, amely a műveletünk műveleteit mutatja:

Rizs. 2

Itt mutattam a kitevőkre egy nyíllal, mint látható, az eredménynek 10100 -nak kellett volna lennie, de mivel a mod 2 4 művelet során figyelmen kívül hagyják az átvitelt, 0100 -at kapunk.

2. Ezt a műveletet az irodalomban mod 2 -nak hívják, assembly nyelven a parancs hajtja végre XOR... De helyesebb neve a mod 2 1. Ezen egyedülálló művelet nélkül aligha lehet gyors, könnyen megvalósítható titkosítási algoritmust felépíteni, és ezzel egyidejűleg úgy, hogy az még mindig meglehetősen erős legyen. Ennek a műveletnek az egyedisége abban rejlik, hogy maga az ellenkezője! Például, ha az A számot XOR -al jelöltük a B számmal, ennek eredményeként B -t kapunk, a jövőben elegendő BX és C számok egymás közötti reXOR -át kapni, hogy megkapjuk A korábbi értékét!

Ebben a műveletben 1010 -et kaptunk 1110 és 0100 számokkal, hogy visszakapjuk az 1110 -et, elegendő túllépni a 0100 és 1010 számokat! További részletek erről a műveletről a cikkben találhatók, amely az oldalhoz csatolt. www.wasm.ru, « Elemi útmutató aCRC_ hibafelismerő algoritmusok»A szerző, aki Ross N. Williams... Ennek a munkának van értelme - „ 5. Bináris aritmetika elválasztás nélkül". Ebben a cikkben írják le a műveletet. xor! Felkiáltok, mert ebben a cikkben ez a művelet úgy van ütemezve, hogy az olvasó nemcsak érti, hogyan működik ez a művelet, hanem el is indítja. látni, hallani és érezni!

3. Ez a művelet szükséges ahhoz, hogy a kezdeti értékeket a titkosításból meg lehessen szerezni a visszafejtés során.

2.2 Blokk titkosítás GOST 28147-89

A GOST 28147 - 89 titkosítási algoritmus a kiegyensúlyozott Feistel -hálózatok architektúrája szerint működő blokkotitkosító kategóriába tartozik, ahol a kiválasztott információblokk két része azonos méretű. Az algoritmust a KGB nyolcadik osztályának mélyén fejlesztették ki, mára FAPSI -vé alakították át, és 1989 -ben az Orosz Föderáció titkosítási szabványaként rögzítették.

Az algoritmus ezen módszerének működéséhez 64 bites méretű blokkokra kell osztani az információkat. Hozza létre vagy adja meg a titkosítási rendszerben a következő kulcsinformációkat: kulcs- és helyettesítési táblázat. A titkosítás kulcs- és helyettesítő táblájának megválasztását nagyon komolyan kell venni, mert ez az információ biztonságának alapja. A kulccsal szemben támasztott követelményekről és a cserék táblázatáról lásd a "Kulcsinformációk követelményei" tételt.

A módszer mérlegelésekor nem fogunk erre összpontosítani, mert Ezt a cikket, mint fentebb említettem, azzal a céllal írtuk, hogy megtanítsuk az olvasót az adatok titkosítására a titkosítási algoritmus egyszerű cseréjének módszerével, de ezt a kérdést mindenképpen érintjük a cikk végén.

Elméleti minimum.

3.1 Kulcsinformációk

Amint fentebb említettem, a következők aktívan részt vesznek az adatok titkosításában:

3.1.1. A kulcs nyolc elemből álló sorozat, egyenként 32 bit. A következőkben K szimbólummal jelöljük, és az elemeket, amelyekből áll, k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Helyettesítési táblázat - nyolc sorból és tizenhat oszlopból álló mátrix, a továbbiakban - Hij. Az i sor és a j oszlop metszéspontjában lévő minden elem 4 bitet foglal el.

3.2 A titkosítási átalakítás alapvető lépése

A titkosítási folyamat fő lépése a titkosítási átalakítás fő lépése. Ez nem más, mint egy művelet az adatok titkosítására egy adott algoritmus szerint, csak a fejlesztők vezették be a túl nehézkes nevet.

A titkosítás megkezdése előtt a blokk két részre, L -re és R -re oszlik, egyenként 32 bitre. A kulcs elem kiválasztásra kerül, és csak ezután a blokk e két része, a kulcs elem, a helyettesítési táblázat kerül a fő lépés funkcióba, a fő lépés eredménye az alapciklus egy iterációja, amelyet a a következő bekezdés. A fő lépés a következőkből áll:

1. Az R mondat összeadási részét összegezzük a K mod 2 32 kulcselemmel. Fentebb leírtam egy hasonló műveletet, itt ugyanaz csak a kitevő nem "4", hanem "32" - ennek a műveletnek az eredményét Smod jelöléssel látjuk el a jövőben.
2. Ossza fel a korábban kapott Smod eredményt négybites s7, s6, s5, s4, s3, s2, s1, s0 elemekre, és adja be a helyettesítő függvénybe. A helyettesítés a következő: a Smod - si elem ki van választva, kezdjük az elejétől a legalacsonyabb elemmel, és cseréljük ki a cserék táblázatából származó értékkel i - az s elem értéke által mutatott sor és oszlop én. Átmegyünk az s i +1 elemhez, és ugyanígy járunk el, és addig folytatjuk, amíg meg nem változtatjuk az utolsó Smod elem értékét - ennek a műveletnek az eredménye: Ssimple.
3. Ebben a műveletben ciklikusan eltoljuk a Ssimple értékét balra 11 bit -el, és kapjuk az Srol értéket.
4. Kiválasztjuk az L blokk második részét, és hozzáadjuk a mod 2 -t Srol -tal, ennek eredményeként megvan az Sxor.
5. Ebben a szakaszban az L mondat része egyenlővé válik az R rész értékével, és az R részt viszont inicializálja az Sxor eredménnyel, és ezzel befejeződik a fő lépés funkciója!

3.3 Alapciklusok: "32-З", "32-Р".

Az információk titkosításához 64 bites méretű blokkokra kell bontani, természetesen az utolsó blokk lehet kevesebb, mint 64 bit. Ez a tény az Achilles -sarka ennek a "könnyen cserélhető" módszernek. Mivel a 64 bites hozzáadása nagyon fontos feladat a titkosítóprogram titkosítási erősségének növelésére és erre az érzékeny helyre, ha jelen van az információs tömbben, és előfordulhat, hogy nem is létezik (például egy 512 bájtos fájl! ), Nagy felelősséggel kell bánni!

Miután blokkolta az információkat, a kulcsot elemekre kell osztania:

K = k1, k2, k3, k4, k5, k6, k7, k8

Maga a titkosítás az úgynevezett alapciklusok használatából áll. Amelyek magukban foglalják a kripto-transzformáció alapvető lépéseinek n-edik számát.

Az alapvető ciklusok meg vannak jelölve, hogyan kell mondani: n - m. Ahol n a kriptotranszformáció alapvető lépéseinek száma az alapciklusban, és m az alapciklus "típusa", azaz miről van szó, a "Z" vagy az "R" titkosításról.

Az alap titkosítási ciklus 32-З a kripto-átalakítás 32 alapvető lépéséből áll. Az N mondat és a K kulcs egy eleme betáplálódik a lépés műveleteit megvalósító függvénybe, és az első lépés a k1, a második a k2 elemmel kapott eredmény felett történik stb. a következő séma szerint:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

A 32-P dekódolási folyamata hasonló módon történik, de a kulcsfontosságú elemek fordított sorrendben vannak megadva:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Gyakorlat.

4.1 A titkosítás átalakításának fő lépése

Miután megismerkedtünk az információk titkosításának elméletével, ideje volt megnézni, hogyan működik a titkosítás a gyakorlatban.

Kezdeti adatok:

Vegyünk egy információs blokkot N = 0102030405060708h, itt az L és R részek egyenlők:

L = 01020304h, R = 05060708h, vegyük a kulcsot:

K = ' 28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(ezek ASCII kódok, a hexadecimális ábrázolás megtekintéséhez megnyithatja ezt a fájlt nézet módban a Total Commanderben a gomb megnyomásával F3"És akkor a kulcs" 3 "). Ebben a kulcsban az elemek értékei a következők lesznek:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Vegye ki a következő helyettesítési táblázatot is:

Rizs. 3

Itt a sorok 0 -tól 7 -ig, az oszlopok 0 -tól F -ig vannak számozva.

Egy figyelmeztetés: Minden információ, beleértve a kulcsot a helyettesítési táblával, példaként szolgál az algoritmus mérlegeléséhez!

A "Kezdeti adatok" segítségével meg kell szerezni a kripto -transzformáció fő lépéseinek eredményét.

1. Válassza ki az R = 05060708h részt és a k1 = 'as28' kulcselemet, hexadecimális formában a kulcs elem így fog kinézni: 61733238h. Most elvégezzük az összegzési műveletet: mod 2 32:

Rizs. 4

Amint az az ábrán látható, nem volt 33 bites átvitelünk pirossal és kitevővel " 32 ". És ha más értékeink lennének az R -re és a kulcselemre, akkor ez megtörténhetett volna, és akkor figyelmen kívül hagytuk volna, és csak a sárgával jelölt biteket használtuk.

Ezt a műveletet az assembler paranccsal hajtom végre hozzá:

; eax = R, ebx = 'as28'

Ennek a műveletnek az eredménye Smod = 66793940h

2. Most a legbonyolultabb művelet, de ha alaposan megnézzük, már nem olyan ijesztő, mint elsőre tűnik. Képzeljük el Smodot a következőképpen:

Rizs. 5

Próbáltam megjeleníteni a Smod elemeket az ábrán, de mindenképpen elmagyarázom:

s0 = 0, s1 = 4, s2 = 9 stb.

Most a legalacsonyabb s0 elemből kiindulva végezzük el a cserét. A bekezdésre emlékezve " 3.2 A titkosítási átalakítás alapvető lépése»I - sor, s i - oszlop, keresse meg az értéket a nulla sorban és a nulla oszlopban:

6. ábra

Tehát a Smod jelenlegi értéke nem 6679394 0 h, és 6679394 5 h.

Folytatjuk az s1 cseréjét, azaz négy. Az első sor és a negyedik oszlop használatával (s1 = 4!). Megnézzük a képet:

Rizs. 7

Most már a Smod értéke, nem a 667939 4 5h, 667939 2 5 óra. Feltételezem, hogy most a csere algoritmusa világos az olvasó számára, és azt mondhatom, hogy a Ssimple végeredménye után a következő érték lesz - 11e10325h.

Arról, hogy ezt hogyan lehet a legegyszerűbben megvalósítani, az assembler parancsok formájában, a következő bekezdésben fogok beszélni, miután a kibővített táblázatról beszélek.

1. A kapott Ssimple értéket 11 bittel balra kell tolnunk.

Rizs. nyolc

Mint látható, ez a művelet meglehetősen egyszerű, és az összeszerelési nyelv egyetlen parancsával hajtható végre - rollés ennek a Srol műveletnek az eredménye 0819288Fh.

4. Most az információs blokkunk L részét XOR -ként kell megadni a Srol értékkel. Előveszek egy számológépet a w2k sp4 -ből, és kapok Sxor = 091b2b8bh.

5. Ez a művelet végleges, és egyszerűen hozzárendeljük, megtisztítjuk az R részt az L rész értékéhez, és inicializáljuk az L részt a Sxor értékkel.

Végeredmény:

L = 091b2b8bh, R = 01020304h

4.2 Az algoritmus sebességének növelése

Most beszéljünk az algoritmus optimalizálásáról a sebességhez. Egy projekt megvalósítása során figyelembe kell venni, hogy egy program, amely gyakrabban dolgozik regiszterekkel, mint memóriával, a leggyorsabban működik, és itt ez az ítélet is nagyon fontos, mivel egy blokk információ felett akár 32 titkosítási művelet!

Amikor megvalósítottam a titkosítási algoritmust a programomban, a következőket tettem:

1. Az L blokk kiválasztott része az eax regiszterhez, és az R az edxhez.

2. Az esi regiszterben, a kiterjesztett kulcs címével inicializálva, bővebben az alábbiakban.

3. Az ebx regiszterben a kibővített helyettesítési táblázat címének értékét rendelte hozzá, erről bővebben alább

4. Az 1., 2., 3. tétel információit a helyzettől függően átvitte a 32 - З vagy 32 - Р alapciklus funkciójába.

Ha megnézi a bekezdésben szereplő kulcsfontosságú elemek folyamatábráját " Alapciklusok: "32-З", "32-Р"", Ekkor a 32 - 3 alapciklus kulcsa a következőképpen ábrázolható:

K 32-Z =

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”

Azok. kezdettől fogva vannak k1, k2, k3, k4, k5, k6, k7, k8 - ‘ mint 28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' ez a sorozat háromszor megismétlődik. Ezután az elemek fordított sorrendben mennek, azaz: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.

A tömb elemeit előre elrendeztem a 32 -es betáplálás sorrendjében. Z. Így kulcsrakészen növeltem a szükséges memóriát, de megmentettem magam néhány gondolkodási folyamattól, amelyekre nem volt szükségem, és növeltem a sebességet az algoritmus, a memória -hozzáférési idő csökkentésével! Itt csak a 32 -es kulcsot írtam le - З, a 32 -es ciklushoz - Р Ugyanezt tettem, de az ellátóelemek más sémáját használva, amelyet a bekezdésben is leírtam " Alapciklusok: „32-Z”, „32-P».

Itt az ideje, hogy leírjam a helyettesítő funkció megvalósítását, ahogy fentebb ígértem. Korábban nem tudtam leírni, mert ehhez új koncepció - kiterjesztett helyettesítési táblázat - bevezetésére van szükség. Nem tudom megmagyarázni neked, mi az. Ehelyett megmutatom, és maga fogalmazza meg magának, mi ez - a helyettesítések kiterjesztett táblázata?

Tehát ahhoz, hogy megértsük, mi a kiterjesztett helyettesítési táblázat, szükségünk van például egy helyettesítési táblázatra, és az alábbi ábrát mutatom be. 3.

Például le kellett cserélnünk a 66793940h számot. A következőképpen mutatom be:

Rizs. kilenc

Ha most az s1, s0 elemeket vesszük, azaz legkevésbé szignifikáns bájt, a cserefunkció eredménye 25 óra lesz! Miután elolvastam Andrey Vinokurov cikkét, amelyet a bekezdésben idéztem " A felhasznált irodalom jegyzéke", Valójában azt tapasztalja, hogy ha két sort vesz, tömböt kaphat, amely lehetővé teszi, hogy gyorsan megtalálja a csereelemeket az assembler paranccsal xlat. Azt mondják, hogy más módon gyorsabban is meg lehet csinálni, de Andrey Vinokurov körülbelül négy évet töltött azzal, hogy gyors algoritmusokat kutasson a GOST megvalósítására! Nem hiszem, hogy újra kellene feltalálni a kereket, ha már van.

Tehát a tömbről:

Vegyük az első két sort nullának és az elsőt, hozzunk létre egy 256 bájtos tömböt. Most megfigyelünk egy sajátosságot, hogy ha 00h -t kell átalakítani, akkor az eredmény 75h lesz (a 3. ábra alapján) - ezt az értéket a 00h eltoláskor helyezzük a tömbbe. Felvesszük a 01h értéket, a 79h helyettesítési függvény eredményét, betesszük a tömbbe a 01 -es eltoláskor, és így tovább 0FFh -ig, ami 0FCh -t ad nekünk, amelyet a 0FFh eltoláskor teszünk a tömbbe. Így egy kibővített cserélési táblázatot kaptunk az első sorcsoporthoz: az elsőhöz és a nullához. De még mindig három csoport van: második 2. oldal, 3. oldal, harmadik 4. oldal, 5. oldal, negyedik 6. oldal, 7. oldal. Ezzel a három csoporttal ugyanúgy foglalkozunk, mint az elsővel. Az eredmény egy kiterjesztett cserélési táblázat!

Most megvalósíthatunk egy algoritmust, amely elvégzi a cserét. Ehhez vesszük a forráskódokat, amelyeket Andrei Vinokurov közzétett az oldalán, lásd " Bibliográfia».

lea ebx, kiterjesztett_tábla_egyszerű

mov eax, [írja be a cserélni kívánt számot]

add ebx, 100h; ugrás a következő két csomópontra

sub ebx, 300h; hogy a jövőben az ebx az asztalra mutasson

Most még egy szolgáltatás, a korábbi műveletek mellett nem csak kicseréltük, hanem 8 bittel eltoltuk a számot balra! Csak a további 3 bitet kell balra tolnunk:

és megkapjuk a rol eax, 11 művelet eredményét!

Az optimalizáláshoz nem tudok többet hozzátenni, az egyetlen dolog, amit ki tudok emelni, az, amit fentebb mondtam - gyakrabban használja a regisztereket, mint a memóriahozzáférést. Azt hiszem, ezek a szavak csak a kezdőknek szólnak, tapasztaltak, és szavaim nélkül tökéletesen megértik.

A legfontosabb információkra vonatkozó követelmények.

Amint azt Andrey Vinokurov cikke írja, a kulcsot két kritérium szerint választják ki:

A bitek egyenlő valószínűségű eloszlásának kritériumai az 1 és a 0 értékek között. Általában a bitek egyenlő valószínűségű eloszlásának kritériuma a Pearson-kritérium ("chi-square").

Ez kulcsot jelent, elvileg bármilyen szám. Vagyis amikor a kulcs következő bitje létrejön, annak valószínűsége, hogy inicializálja eggyel vagy nullával 50/50!

Kérjük, vegye figyelembe, hogy a kulcs nyolc, egyenként 32 bites elemből áll, így csak 32 * 8 = 256 bit van a kulcsban, és a lehetséges kulcsok száma 2 256! Ez nem üt rád?

Sorozat kritérium.

Ha megnézzük a kulcsunkat, amelyet a bekezdésben adtam meg " 4.1 A titkosítás átalakításának fő lépése», Akkor észre fogja venni, hogy a következő jelölés érvényes:

Rizs. tíz

Egy mondatban a k 1 értékét nem szabad megismételni, nem a k 2 -ben, sem a kulcs bármely más elemében.

Vagyis a kulcs, amelyet a titkosítási algoritmus figyelembevételével választottunk, teljes mértékben megfelel a fenti két kritériumnak.

Most a helyettesítési táblázat kiválasztásáról:

Most beszéljünk arról, hogyan válasszuk ki a megfelelő helyettesítő táblázatot. A helyettesítő táblázatok kiválasztásának fő követelménye az elemek „megismételhetetlenségének” jelensége, amelyek mindegyike 4 bit méretű. Amint fentebb látta, a helyettesítési táblázat minden sora a 0h, 1h, 2h, 3h,…, 0fh értékekből áll. Tehát a fő követelmény az, hogy minden sor tartalmazza a 0h, 1h, 2h, ..., 0fh értékeket és minden ilyen értéket egy példányban. Például a sorrend:

1 2 3 4 5 6 7 8 9 A B C D E F

Teljes mértékben megfelel ennek a követelménynek, de mégis! Nem ajánlott ezt a sorozatot karakterláncként kiválasztani. Mivel ha egy értéket adsz meg egy függvény bemenetéhez, amely egy ilyen karakterláncra támaszkodik, akkor ugyanazt az értéket kapod a kimeneten! Nem hiszel nekem? Ezután vegye a 332DA43Fh számot és nyolc ilyen sort helyettesítési táblázatnak. Végezze el a csere műveletet, és biztosíthatom Önöket, hogy a kimenet a 332DA43Fh szám lesz! Vagyis ugyanazt, amit benyújtott a művelet bemenetéhez! És ez nem a titkosítás jó formájának jele, és volt?

Ez volt az egyik követelmény, a következő kritérium azt mondja, hogy - a kimeneti blokk minden bitjének statisztikailag függetlennek kell lennie a bemeneti blokk minden bitjétől!

Hogyan néz ki egyszerűbben? És például itt választottuk ki a fenti szám közül az s0 = 0Fh, 01111b elemet. Annak a valószínűsége, hogy most az első bitet kicseréljük egyre vagy nullára, 0,5! A második, harmadik és negyedik bit kicserélésének valószínűsége, minden egyes bitnél, külön -külön, egyesekkel vagy nullákkal, szintén 0, 5. Az s1 = 0Eh kiválasztásakor annak valószínűsége, hogy nulla bit vagyunk, és ez a "0" , helyébe nulla vagy egy egyenlő - 0,5! Így e kritérium szerint nincs szabályosság az s0, s1 elemek nulla bitjeinek cseréje között! Igen, helyettesítheti azokat, de nullákat is.

A táblázat e kritérium szerint történő értékeléséhez összeállíthat egy táblázatot a következő képlet alapján kiszámított korrelációs együtthatókról:

Ha p = 1, akkor a j bit értéke a kimeneten megegyezik az i bit értékével a bemeneten a bemeneten lévő bitek bármely kombinációja esetén;

Ha p = -1, akkor a j bit értéke a kimeneten mindig az i bemeneti bit inverze;

Ha p = 0, akkor a j kimeneti bit azonos valószínűséggel a 0 és 1 értékeket veszi fel az i bemeneti bit bármely rögzített értékére.

Vegyünk egy sor példát:

Bontjuk "komponensekre":

Számítsunk ki egy együtthatót a fenti képlet szerint. Annak érdekében, hogy könnyebben megértsük, hogyan történik ez, részletesebben elmagyarázom:

A 0. szám (0) 0. bitjét vesszük a bemenetre, és a 0. szám 0. bitjét a kimenetre (1), végrehajtjuk a 0 XOR 1 = 1 műveletet.

Az 1. szám (1) 0. bitjét vesszük a bemenetre, és az 1. szám 0. bitjét a kimenetre (1), végrehajtjuk az 1 XOR 1 = 0 műveletet.

A bemeneten a 2. szám (0) 0. bitjét, a kimeneten (0) a 2. szám 0. bitjét vesszük, végrehajtjuk a 0 XOR 0 = 0 műveletet.

A 3. szám (1) 0. bitjét vesszük a bemenetre, és a 3. szám 0. bitjét a kimenetre (1), végrehajtjuk az 1 XOR 1 = 0 műveletet.

Ebben a sorrendben egymás után XOR műveleteket végezve megszámoljuk az összes nem nulla érték számát, és megkapjuk a 6. értéket. Ezért P 00 = 1- (6/2 4-1) = 0,25. Tehát kiderült, hogy a 0 bit értéke a kimeneten 16 esetben 4 esetben egyenlő a 0 bit értékével a bemeneten;

Végső esélytáblázat:

Amint az a korrelációs együtthatók táblázatából is látható, a bemenet 3. bitje a 16 -ból 14 esetben fordítva van a kimeneti 0. bithez képest, ami 87,5%. Ez a normál titkosítási rendszerek esetében már nem elfogadható. Vegyünk egy másik példát a változáshoz:

Az együtthatók táblázata a következő lesz (kinek nem lusta újraszámolni)

Nos, ebben a táblázatban a dolgok még rosszabbak - a csoport 1. és 2. bitje változatlan marad! A Cryptanalystnek van hová fordulnia Mindezeket a követelményeket figyelembe véve egy egyszerű keresés ("head -on") a megadott elméletnek megfelelő permutációs táblázatokat talált (ma - 1276 kombináció) Íme néhány közülük:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

A felhasznált irodalom jegyzéke.

1. Andrey Vinokurov cikke:

GOST 28147-89 titkosítási algoritmus, használata és végrehajtása

Intel x86 platformú számítógépekhez.

A forráskódok a titkosítási algoritmus megvalósításához is rendelkezésre állnak.

1. Horst Feistel cikke:

Kriptográfia és számítógépes biztonság.

(ugyanazon a címen található, mint az előző cikk)

1. Ross N. Williams:

Elemi útmutató a CRC hibafelismerő algoritmusokhoz

Közzétéve az oldalon www.wasm.ru.

Köszönetnyilvánítás.

Köszönetemet szeretném kifejezni a www.wasm.ru fórum minden látogatójának. De különösen szeretnék köszönetet mondani ChS -nek, akit jelenleg SteelRat néven ismernek, segített megérteni azokat a dolgokat, amelyeket valószínűleg soha nem értettem volna meg, valamint segítséget a bekezdés megírásában: „ Főbb információs követelmények”, Ennek a bekezdésnek a fő részét ő írta. Nagyon hálás vagyok a KSTU nevéhez fűződő alkalmazottjának is A.N. Tupolev Anikin Igor Vjacseszlavovics, és bűn lenne nem említeni Chris Kasperskyt azért, hogy ő az, és Volodya / wasm.ru utasításait. Ja, és tőle kapom. Szeretném megjegyezni a Sega-Zero / Callipso-t is, de ez valami matematikai dzsungelt juttatott az eszembe.

Talán csak ennyit szeretnék elmondani.

Hálás lennék minden kritikáért vagy kérdésért, ami ehhez a cikkhez kapcsolódik, vagy csak tanácsokat. Elérhetőségeim: [e -mail védett], ICQ - 337310594.

Üdvözlettel: Evil`s Interrupt.

P.S .: Ezzel a cikkel nem próbáltam senkit felülmúlni. Szándékosan írták, hogy megkönnyítsék a GOST tanulmányozását, és ha nehézségei vannak, ez nem jelenti azt, hogy bűnös vagyok ebben. Légy ésszerű és türelmes, minden jót neked!

„Amíg élsz, ne halj meg, nézd meg ezt a világot.
Itt sokaknak halott a lelke - belül halottak.
De sétálnak és nevetnek, nem tudva, hogy nem azok,
Ne siettesse halálos óráját - mondta nekem.

Aria, "Magas fent"

1. Bevezetés

1. Előzetes információk a blokkolt titkosításokról

2.1 Feistel hálózatok.
2.2 Blokk titkosítás GOST 28147-89

1. Elméleti minimum

3.1 Kulcs információ
3.2 A titkosítási átalakítás fő lépése

3.3 Alap ciklusok:“ 32-Z” , “ 32-R” .

1. Gyakorlat

4.1 A titkosítás átalakításának fő lépése
4.2 Az algoritmus sebességének növelése
5.
6. A felhasznált irodalom jegyzéke
7. Köszönetnyilvánítás.

Bevezetés.

Ez a dokumentum az én kísérletem, hogy leírjak egy módszert, amellyel egyszerűen lecserélhetjük a GOST 28147-89 titkosítási algoritmust a legegyszerűbb, de ennek ellenére technikailag kompetens nyelvre. Az első hat pont elolvasása után az olvasó elmondja véleményét arról, hogy mennyire jól tettem.

Annak érdekében, hogy munkám nagyobb hasznot nyújtson, javaslom, hogy fegyverezze fel magát a használt irodalom jegyzékében feltüntetett szerzők munkáival. Javasolt továbbá, hogy a számológép rendelkezzen funkcióval a művelet kiszámításához. XOR mivel A cikk elolvasása feltételezi, hogy az olvasó ezt a titkosítási algoritmust kívánta tanulmányozni. Bár referenciaként is alkalmas, de ezt a cikket pontosan képzésként írtam.

Előzetes információk a blokkolt titkosításokról.

Mielőtt elkezdenénk nézni az algoritmust, meg kell ismernünk az ilyen típusú kódok létrehozásának történetét. Az algoritmus a blokkotitkosítás kategóriájába tartozik, amelynek architektúrájában az információ véges számú blokkra oszlik, a végső természetesen nem teljes. A titkosítási folyamat a titkosítást alkotó teljes blokkokon megy keresztül. Az utolsó blokkot, ha hiányos, kiegészítik valamivel (az alábbiakban a kitöltés árnyalatairól szólok), és ugyanúgy titkosítva, mint a teljes blokkok. Titkosítás alatt azt az eredményt értem, hogy a titkosítási funkció egy bizonyos adatmennyiségre hat, amelyet a felhasználó küldött titkosításra. Más szóval, a titkosítás a titkosítás végeredménye.

A blokkolt titkosítás fejlődésének története a 70 -es évek elejéhez kapcsolódik, amikor az IBM, felismerve az adatok védelmének szükségességét, amikor adatokat továbbít a számítógépes kommunikációs csatornákon keresztül, saját kutatási programjába kezdett, amely az elektronikus hálózatok információinak védelmével foglalkozik, beleértve a titkosítást.

Az IBM kutatói - fejlesztői csoportja, amely szimmetrikus kulcshasználati sémával kezdte a titkosítási rendszerek kutatását, dr. Horst Feistel.

2.1 Feistel hálózatok

A Feistel által a klasszikus irodalomban javasolt új titkosítási módszer architektúráját „The Feistel Architecture” -nek hívták, de jelenleg az orosz és a külföldi irodalomban egy bevált kifejezést használnak - „Feistel hálózata” vagy Feistel NetWork. Ezt követően a "Lucifer" titkosítás erre az architektúrára épült - amelyet később publikáltak, és új érdeklődési hullámot keltett általában a kriptográfia iránt.

A "Feistel network" architektúra ötlete a következő: az információs adatfolyam n bit méretű blokkokra van felosztva, ahol n páros szám. Mindegyik blokk két részre van osztva-L és R, majd ezeket a részeket egy iteratív blokkotitkosítóba táplálják, amelyben a j-edik szakasz eredményét az előző j-1 szakasz eredménye határozza meg! Ezt egy példával szemléltethetjük:

Rizs. 1

Ahol az A függvény a blokk titkosítás fő művelete. Ez lehet egy egyszerű művelet, például egy XOR művelet, vagy lehet egy bonyolultabb formája is, mint egy sor egyszerű művelet - modulo összeadás, bal eltolás, elemcsere stb. Együttesen, ezek az egyszerű műveletek az úgynevezett - a titkosítási átalakítás fő lépése.

Meg kell jegyezni, hogy a függvény működésének kulcsfontosságú elemei a kulcsfontosságú elemek ellátása és a XOR művelet, és ezeknek a műveleteknek a jól átgondolt működéséből a rejtjel egészének titkosítási erejéről beszél.

Annak érdekében, hogy a Feistel -hálózatok elképzelése végre világos legyen, fontolja meg a legegyszerűbb esetet, amely a rizs. 1, ahol az A függvényben - lesznek „mod 2” („xor”) műveletek, de ez legegyszerűbb egy eset, súlyosabb helyzetben, például az állami jelentőségű információk elrejtése, az A funkció összetettebb lehet (amennyire láttam, az A funkció valóban nagyon összetett):

Kezdeti adatok:

L = 1110b, R = 0101, K = 1111b

Vegyél egy titkosítást

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Magyarázzuk el tetteinket:

1. Ez a művelet a mod 2 4 kiegészítése. A gyakorlatban egy ilyen művelet egyszerű összeadásra redukálódik, ahol két számot kell hozzáadnunk, és figyelmen kívül kell hagynunk az 5. számjegyre történő átvitelt. Mivel ha egy szám bináris ábrázolásának számjegye fölé teszünk kitevőket, akkor az ötödik számjegy felett négy kitevő lesz, nézzük meg az alábbi ábrát, amely a műveletünk műveleteit mutatja:

Rizs. 2

Itt mutattam a kitevőkre egy nyíllal, mint látható, az eredménynek 10100 -nak kellett volna lennie, de mivel a mod 2 4 művelet során figyelmen kívül hagyják az átvitelt, 0100 -at kapunk.

1. Ezt a műveletet a szakirodalomban mod 2 -nak hívják, assembly nyelven a parancs hajtja végre XOR... De helyesebb neve a mod 2 1. Ezen egyedülálló művelet nélkül aligha lehet gyors, könnyen megvalósítható titkosítási algoritmust felépíteni, és ezzel egyidejűleg úgy, hogy az még mindig meglehetősen erős legyen. Ennek a műveletnek az egyedisége abban rejlik, hogy maga az ellenkezője! Például, ha az A számot XOR -al jelöltük a B számmal, ennek eredményeként B -t kapunk, a jövőben elegendő BX és C számok egymás közötti reXOR -át kapni, hogy megkapjuk A korábbi értékét!

Ebben a műveletben 1010 -et kaptunk 1110 és 0100 számokkal, hogy visszakapjuk az 1110 -et, elegendő túllépni a 0100 és 1010 számokat! További részletek erről a műveletről a cikkben találhatók, amely az oldalhoz csatolt. www.wasm.ru, « Elemi útmutató aCRC_ hibafelismerő algoritmusok»A szerző, aki Ross N. Williams... Ennek a munkának van értelme - „ 5. Bináris aritmetika elválasztás nélkül". Ebben a cikkben írják le a műveletet. xor! Felkiáltok, mert ebben a cikkben ez a művelet úgy van ütemezve, hogy az olvasó nemcsak érti, hogyan működik ez a művelet, hanem el is indítja. látni, hallani és érezni!

1. Ez a művelet szükséges ahhoz, hogy a visszafejtés során a kezdeti értékeket meg lehessen szerezni a titkosításból.

2.2 Blokk titkosítás GOST 28147-89

A GOST 28147 - 89 titkosítási algoritmus a kiegyensúlyozott Feistel -hálózatok architektúrája szerint működő blokkotitkosító kategóriába tartozik, ahol a kiválasztott információblokk két része azonos méretű. Az algoritmust a KGB nyolcadik osztályának mélyén fejlesztették ki, mára FAPSI -vé alakították át, és 1989 -ben az Orosz Föderáció titkosítási szabványaként rögzítették.

Az algoritmus ezen módszerének működéséhez 64 bites méretű blokkokra kell osztani az információkat. Hozza létre vagy adja meg a titkosítási rendszerben a következő kulcsinformációkat: kulcs- és helyettesítési táblázat. A titkosítás kulcs- és helyettesítő táblájának megválasztását nagyon komolyan kell venni, mert ez az információ biztonságának alapja. A kulccsal szemben támasztott követelményekről és a cserék táblázatáról lásd a "Kulcsinformációk követelményei" tételt.

A módszer mérlegelésekor nem fogunk erre összpontosítani, mert Ezt a cikket, mint fentebb említettem, azzal a céllal írtuk, hogy megtanítsuk az olvasót az adatok titkosítására a titkosítási algoritmus egyszerű cseréjének módszerével, de ezt a kérdést mindenképpen érintjük a cikk végén.

Elméleti minimum.

3.1 Kulcsinformációk

Amint fentebb említettem, a következők aktívan részt vesznek az adatok titkosításában:

3.1.1. A kulcs nyolc elemből álló sorozat, egyenként 32 bit. A következőkben K szimbólummal jelöljük, és az elemeket, amelyekből áll, k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Helyettesítési táblázat - nyolc sorból és tizenhat oszlopból álló mátrix, a továbbiakban - Hij. Az i sor és a j oszlop metszéspontjában lévő minden elem 4 bitet foglal el.

A titkosítási folyamat fő lépése a titkosítási átalakítás fő lépése. Ez nem más, mint egy művelet az adatok titkosítására egy bizonyos algoritmus szerint, csak a fejlesztők vezették be a nevet túl nehézkesnek :).

A titkosítás megkezdése előtt a blokk két részre, L -re és R -re oszlik, egyenként 32 bitre. A kulcs elem kiválasztásra kerül, és csak ezután a blokk e két része, a kulcs elem, a helyettesítési táblázat kerül a fő lépés funkcióba, a fő lépés eredménye az alapciklus egy iterációja, amelyet a a következő bekezdés. A fő lépés a következőkből áll:

1. Az R mondat összeadási részét összegezzük a K mod 2 32 kulcselemmel. Fentebb leírtam egy hasonló műveletet, itt ugyanaz csak a kitevő nem "4", hanem "32" - ennek a műveletnek az eredményét Smod jelöléssel látjuk el a jövőben.
2. Ossza fel a korábban kapott Smod eredményt négybites s7, s6, s5, s4, s3, s2, s1, s0 elemekre, és adja be a helyettesítő függvénybe. A helyettesítés a következő: a Smod - si elem ki van választva, kezdjük az elejétől a legalacsonyabb elemmel, és cseréljük ki a cserék táblázatából származó értékkel i - az s elem értéke által mutatott sor és oszlop én. Átmegyünk az s i +1 elemhez, és ugyanígy járunk el, és addig folytatjuk, amíg meg nem változtatjuk az utolsó Smod elem értékét - ennek a műveletnek az eredménye: Ssimple.
3. Ebben a műveletben ciklikusan eltoljuk a Ssimple értékét balra 11 bit -el, és kapjuk az Srol értéket.
4. Kiválasztjuk az L blokk második részét, és hozzáadjuk a mod 2 -t Srol -tal, ennek eredményeként megvan az Sxor.
5. Ebben a szakaszban az L mondat része egyenlővé válik az R rész értékével, az R rész pedig inicializálásra kerül az Sxor eredménnyel, és ezzel befejeződik a fő lépés funkciója!

3.3 Alapciklusok: "32-З", "32-Р".

Az információk titkosításához 64 bites méretű blokkokra kell bontani, természetesen az utolsó blokk lehet kevesebb, mint 64 bit. Ez a tény az Achilles -sarka ennek a "könnyen cserélhető" módszernek. Mivel a 64 bites hozzáadása nagyon fontos feladat a titkosítóprogram titkosítási erősségének növelésére és erre az érzékeny helyre, ha jelen van az információs tömbben, és előfordulhat, hogy nem is létezik (például egy 512 bájtos fájl! ), Nagy felelősséggel kell bánni!

Miután blokkolta az információkat, a kulcsot elemekre kell osztania:

K = k1, k2, k3, k4, k5, k6, k7, k8

Maga a titkosítás az úgynevezett alapciklusok használatából áll. Amelyek magukban foglalják a kripto-transzformáció alapvető lépéseinek n-edik számát.

Az alapvető ciklusok meg vannak jelölve, hogyan kell mondani: n - m. Ahol n a kriptotranszformáció alapvető lépéseinek száma az alapciklusban, és m az alapciklus "típusa", azaz miről van szó, a "Z" vagy az "R" titkosításról.

Az alap titkosítási ciklus 32-З a kripto-átalakítás 32 alapvető lépéséből áll. Az N mondat és a K kulcs egy eleme betáplálódik a lépés műveleteit megvalósító függvénybe, és az első lépés a k1, a második a k2 elemmel kapott eredmény felett történik stb. a következő séma szerint:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

A 32-P dekódolási folyamata hasonló módon történik, de a kulcsfontosságú elemek fordított sorrendben vannak megadva:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Gyakorlat.

Miután megismerkedtünk az információk titkosításának elméletével, ideje volt megnézni, hogyan működik a titkosítás a gyakorlatban.

Kezdeti adatok:

Vegyünk egy információs blokkot N = 0102030405060708h, itt az L és R részek egyenlők:

L = 01020304h, R = 05060708h, vegyük a kulcsot:

K = ' 28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(ezek ASCII kódok, a hexadecimális ábrázolás megtekintéséhez megnyithatja ezt a fájlt nézet módban a Total Commanderben a gomb megnyomásával F3"És akkor a kulcs" 3 "). Ebben a kulcsban az elemek értékei a következők lesznek:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Vegye ki a következő helyettesítési táblázatot is:

Rizs. 3

Itt a sorok 0 -tól 7 -ig, az oszlopok 0 -tól F -ig vannak számozva.

Egy figyelmeztetés: Minden információ, beleértve a kulcsot a helyettesítési táblával, példaként szolgál az algoritmus mérlegeléséhez!

A "Kezdeti adatok" segítségével meg kell szerezni a kripto -transzformáció fő lépéseinek eredményét.

1. Kiválasztjuk az R = 05060708h részt és a k1 = ‘as28’ kulcselemet, hexadecimális formában a kulcs elem így fog kinézni: 61733238h. Most elvégezzük az összegzési műveletet: mod 2 32:

Rizs. 4

Amint az az ábrán látható, nem volt 33 bites átvitelünk pirossal és kitevővel " 32 ". És ha más értékeink lennének az R -re és a kulcselemre, akkor ez megtörténhetett volna, és akkor figyelmen kívül hagytuk volna, és csak a sárgával jelölt biteket használtuk.

Ezt a műveletet az assembler paranccsal hajtom végre hozzá:

; eax = R, ebx = 'as28'

Ennek a műveletnek az eredménye Smod = 66793940h

1. Most a legbonyolultabb művelet, de ha alaposan megnézzük, már nem olyan szörnyű, mint elsőre tűnik. Képzeljük el Smodot a következőképpen:

AZ ÁBRA NEM MENTETT

Rizs. 5

Próbáltam megjeleníteni a Smod elemeket az ábrán, de mindenképpen elmagyarázom:

s0 = 0, s1 = 4, s2 = 9 stb.

Most a legalacsonyabb s0 elemből kiindulva végezzük el a cserét. A bekezdésre emlékezve " 3.2 A titkosítási átalakítás alapvető lépése»I - sor, s i - oszlop, keresse meg az értéket a nulla sorban és a nulla oszlopban:

6. ábra

Tehát a Smod jelenlegi értéke nem 6679394 0 h, és 6679394 5 h.

Folytatjuk az s1 cseréjét, azaz négy. Az első sor és a negyedik oszlop használatával (s1 = 4!). Megnézzük a képet:

Rizs. 7

Most már a Smod értéke, nem a 667939 4 5h, 667939 2 5 óra. Feltételezem, hogy most a csere algoritmusa világos az olvasó számára, és azt mondhatom, hogy a Ssimple végeredménye után a következő érték lesz - 11e10325h.

Arról, hogy ezt hogyan lehet a legegyszerűbben megvalósítani, az assembler parancsok formájában, a következő bekezdésben fogok beszélni, miután a kibővített táblázatról beszélek.

1. A kapott Ssimple értéket 11 bittel balra kell tolnunk.

Rizs. nyolc

Mint látható, ez a művelet meglehetősen egyszerű, és az összeszerelési nyelv egyetlen parancsával hajtható végre - rollés ennek a Srol műveletnek az eredménye 0819288Fh.

1. Most továbbra is az információblokkunk L része lesz XOR a Srol értékkel. Előveszek egy számológépet a w2k sp4 -ből, és kapok Sxor = 091b2b8bh.
2. Ez a művelet végleges, és egyszerűen hozzárendeljük, megtisztítjuk az R részt az L rész értékéhez, és inicializáljuk az L részt a Sxor értékkel.

Végeredmény:

L = 091b2b8bh, R = 01020304h

4.2 Az algoritmus sebességének növelése

Most beszéljünk az algoritmus optimalizálásáról a sebességhez. Egy projekt megvalósítása során figyelembe kell venni, hogy egy program, amely gyakrabban dolgozik regiszterekkel, mint memóriával, a leggyorsabban működik, és itt ez az ítélet is nagyon fontos, mivel egy blokk információ felett akár 32 titkosítási művelet!

Amikor megvalósítottam a titkosítási algoritmust a programomban, a következőket tettem:

1. Az L blokk kiválasztott része az eax regiszterhez, és az R az edxhez.
2. Az esi regiszterben, a kiterjesztett kulcs címével inicializálva, bővebben az alábbiakban.
3. Az ebx regiszterben a kibővített helyettesítési táblázat címének értékét rendelte hozzá, erről bővebben alább
4. Az 1., 2., 3. tétel információit a helyzettől függően átvitte a 32 - З vagy 32 - Р alapciklus funkciójába.

Ha megnézi a bekezdésben szereplő kulcsfontosságú elemek folyamatábráját " Alapciklusok: "32-З", "32-Р"", Ekkor a 32 - 3 alapciklus kulcsa a következőképpen ábrázolható:

K 32-Z =

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”

Azok. kezdettől fogva vannak k1, k2, k3, k4, k5, k6, k7, k8 - ‘ mint 28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' ez a sorozat háromszor megismétlődik. Ezután az elemek fordított sorrendben mennek, azaz: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.

A tömb elemeit előre elrendeztem a 32 -es betáplálás sorrendjében. Z. Így kulcsrakészen növeltem a szükséges memóriát, de megmentettem magam néhány gondolkodási folyamattól, amelyekre nem volt szükségem, és növeltem a sebességet az algoritmus, a memória -hozzáférési idő csökkentésével! Itt csak a 32 -es kulcsot írtam le - З, a 32 -es ciklushoz - Р Ugyanezt tettem, de az ellátóelemek más sémáját használva, amelyet a bekezdésben is leírtam " Alapciklusok: „32-Z”, „32-P».

Itt az ideje, hogy leírjam a helyettesítő funkció megvalósítását, ahogy fentebb ígértem. Korábban nem tudtam leírni, mert ehhez új koncepció - kiterjesztett helyettesítési táblázat - bevezetésére van szükség. Nem tudom megmagyarázni neked, mi az. Ehelyett megmutatom, és maga fogalmazza meg magának, mi ez - a helyettesítések kiterjesztett táblázata?

Tehát ahhoz, hogy megértsük, mi a kiterjesztett helyettesítési táblázat, szükségünk van például egy helyettesítési táblázatra, és az alábbi ábrát mutatom be. 3.

Például le kellett cserélnünk a 66793940h számot. A következőképpen mutatom be:

AZ ÁBRA NEM MENTETT

Rizs. kilenc

Ha most az s1, s0 elemeket vesszük, azaz legkevésbé szignifikáns bájt, a cserefunkció eredménye 25 óra lesz! Miután elolvastam Andrey Vinokurov cikkét, amelyet a bekezdésben idéztem " A felhasznált irodalom jegyzéke", Valójában azt tapasztalja, hogy ha két sort vesz, tömböt kaphat, amely lehetővé teszi, hogy gyorsan megtalálja a csereelemeket az assembler paranccsal xlat. Azt mondják, hogy más módon gyorsabban is meg lehet csinálni, de Andrey Vinokurov körülbelül négy évet töltött azzal, hogy gyors algoritmusokat kutasson a GOST megvalósítására! Nem hiszem, hogy újra kellene feltalálni a kereket, ha már van.

Tehát a tömbről:

Vegyük az első két sort nullának és az elsőt, hozzunk létre egy 256 bájtos tömböt. Most megfigyelünk egy sajátosságot, hogy ha 00h -t kell átalakítani, akkor az eredmény 75h lesz (a 3. ábra alapján) - ezt az értéket a 00h eltoláskor helyezzük a tömbbe. Felvesszük a 01h értéket, a 79h helyettesítési függvény eredményét, betesszük a tömbbe a 01 -es eltoláskor, és így tovább 0FFh -ig, ami 0FCh -t ad nekünk, amelyet a 0FFh eltoláskor teszünk a tömbbe. Így egy kibővített cserélési táblázatot kaptunk az első sorcsoporthoz: az elsőhöz és a nullához. De még mindig három csoport van: második 2. oldal, 3. oldal, harmadik 4. oldal, 5. oldal, negyedik 6. oldal, 7. oldal. Ezzel a három csoporttal ugyanúgy foglalkozunk, mint az elsővel. Az eredmény egy kiterjesztett cserélési táblázat!

Most megvalósíthatunk egy algoritmust, amely elvégzi a cserét. Ehhez vesszük a forráskódokat, amelyeket Andrei Vinokurov közzétett az oldalán, lásd " Bibliográfia».

lea ebx, kiterjesztett_tábla_egyszerű

mov eax, [írja be a cserélni kívánt számot]

add ebx, 100h; ugrás a következő két csomópontra

sub ebx, 300h; hogy a jövőben az ebx az asztalra mutasson

Most még egy szolgáltatás, a korábbi műveletek mellett nem csak kicseréltük, hanem 8 bittel eltoltuk a számot balra! Csak a további 3 bitet kell balra tolnunk:

és megkapjuk a rol eax, 11 művelet eredményét!

Az optimalizáláshoz nem tudok többet hozzátenni, az egyetlen dolog, amit ki tudok emelni, az, amit fentebb mondtam - gyakrabban használja a regisztereket, mint a memóriahozzáférést. Azt hiszem, ezek a szavak csak a kezdőknek, a tapasztaltoknak szólnak, és a szavaim nélkül ezt tökéletesen megértik :).

A legfontosabb információkra vonatkozó követelmények.

Amint azt Andrey Vinokurov cikke írja, a kulcsot két kritérium szerint választják ki:

- a bitek 1 és 0 közötti értékek egyenlő valószínűségű eloszlásának kritériuma. Általában a bitek valószínűsíthető eloszlásának kritériuma a Pearson-kritérium ("chi-square").

Ez kulcsot jelent, elvileg bármilyen szám. Vagyis amikor a kulcs következő bitje létrejön, annak valószínűsége, hogy inicializálja eggyel vagy nullával 50/50!

Kérjük, vegye figyelembe, hogy a kulcs nyolc, egyenként 32 bites elemből áll, így csak 32 * 8 = 256 bit van a kulcsban, és a lehetséges kulcsok száma 2 256! Ez nem üt rád? 🙂

- sorozat kritérium.

Ha megnézzük a kulcsunkat, amelyet a bekezdésben adtam meg " 4.1 A titkosítás átalakításának fő lépése», Akkor észre fogja venni, hogy a következő jelölés érvényes:

Rizs. tíz

Egy mondatban a k 1 értékét nem szabad megismételni, nem a k 2 -ben, sem a kulcs bármely más elemében.

Vagyis a kulcs, amelyet a titkosítási algoritmus figyelembevételével választottunk, teljes mértékben megfelel a fenti két kritériumnak.

Most a helyettesítési táblázat kiválasztásáról:

Most beszéljünk arról, hogyan válasszuk ki a megfelelő helyettesítő táblázatot. A helyettesítő táblázatok kiválasztásának fő követelménye az elemek „megismételhetetlenségének” jelensége, amelyek mindegyike 4 bit méretű. Amint fentebb látta, a helyettesítési táblázat minden sora a 0h, 1h, 2h, 3h,…, 0fh értékekből áll. Tehát a fő követelmény az, hogy minden sor tartalmazza a 0h, 1h, 2h, ..., 0fh értékeket és minden ilyen értéket egy példányban. Például a sorrend:

1 2 3 4 5 6 7 8 9 A B C D E F

Teljes mértékben megfelel ennek a követelménynek, de mégis! Nem ajánlott ezt a sorozatot karakterláncként kiválasztani. Mivel ha egy értéket adsz meg egy függvény bemenetéhez, amely egy ilyen karakterláncra támaszkodik, akkor ugyanazt az értéket kapod a kimeneten! Nem hiszel nekem? Ezután vegye a 332DA43Fh számot és nyolc ilyen sort helyettesítési táblázatnak. Végezze el a csere műveletet, és biztosíthatom Önöket, hogy a kimenet a 332DA43Fh szám lesz! Vagyis ugyanazt, amit benyújtott a művelet bemenetéhez! És ez nem a titkosítás jó formájának jele, és volt? 🙂

Ez volt az egyik követelmény, a következő kritérium azt mondja, hogy - a kimeneti blokk minden bitjének statisztikailag függetlennek kell lennie a bemeneti blokk minden bitjétől!

Hogyan néz ki egyszerűbben? És például itt választottuk ki a fenti szám közül az s0 = 0Fh, 01111b elemet. Annak a valószínűsége, hogy most az első bitet kicseréljük egyre vagy nullára, 0,5! A második, harmadik és negyedik bit kicserélésének valószínűsége, minden egyes bitnél, külön -külön, egyesekkel vagy nullákkal, szintén 0, 5. Az s1 = 0Eh kiválasztásakor annak valószínűsége, hogy nulla bit vagyunk, és ez a "0" , helyébe nulla vagy egy egyenlő - 0,5! Így e kritérium szerint nincs szabályosság az s0, s1 elemek nulla bitjeinek cseréje között! Igen, helyettesítheti azokat, de nullákat is. 🙂

A táblázat e kritérium szerint történő értékeléséhez összeállíthat egy táblázatot a következő képlet alapján kiszámított korrelációs együtthatókról:

- ha p = 1, akkor a j bit értéke a kimeneten megegyezik az i bit értékével a bemeneten a bemeneten lévő bitek bármely kombinációja esetén;

- ha p = -1, akkor a j bit értéke a kimeneten mindig az i bemeneti bit inverze;

- ha p = 0, akkor a j kimeneti bit azonos valószínűséggel a 0 és 1 értékeket veszi fel az i bemeneti bit bármely rögzített értékére.

Vegyünk egy sor példát:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Bontjuk "komponensekre":

Számítsunk ki egy együtthatót a fenti képlet szerint. Annak érdekében, hogy könnyebben megértsük, hogyan történik ez, részletesebben elmagyarázom:

- a bemeneten a 0. szám (0) 0. bitjét, a (1) kimeneten a 0. szám 0. bitjét hajtjuk végre, a 0 XOR 1 = 1 műveletet.

- az 1. szám 0. bitjét (1) vesszük a bemenetre, és az 1. szám 0. bitjét a kimenetre (1), végrehajtjuk az 1 XOR 1 = 0 műveletet.

- a bemeneten a 2. szám (0) 0. bitjét, a kimeneten (0) a 2. szám 0. bitjét vesszük, végrehajtjuk a 0 XOR 0 = 0 műveletet.

- a bemeneten a 3. szám (1) 0. bitjét, a kimeneten (1) a 3. szám 0. bitjét vesszük, végrehajtjuk az 1 XOR 1 = 0 műveletet.

Ebben a sorrendben egymás után XOR műveleteket végezve megszámoljuk az összes nem nulla érték számát, és megkapjuk a 6. értéket. Ezért P 00 = 1- (6/2 4-1) = 0,25. Tehát kiderült, hogy a 0 bit értéke a kimeneten 16 esetben 4 esetben egyenlő a 0 bit értékével a bemeneten;

Végső esélytáblázat:

Az együtthatók táblázata a következő lesz (kinek nem lusta újraszámolni)

	bejárat
Kimenet		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Nos, ebben a táblázatban a dolgok még rosszabbak - a csoport 1. és 2. bitje változatlan marad! A rejtjelezőnek hová kell fordulnia 🙂 Mindezeket a követelményeket figyelembe véve, egyszerű kereséssel ("fejjel") megtalálták a jelzett elméletnek megfelelő permutációs táblázatokat (ma - 1276 kombináció) Íme néhány közülük:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

A felhasznált irodalom jegyzéke.

1. Andrey Vinokurov cikke:

GOST 28147-89 titkosítási algoritmus, használata és végrehajtása

Intel x86 platformú számítógépekhez.

(megtalálható: http://www.enlight.ru/crypto/frame.htm).

A forráskódok a titkosítási algoritmus megvalósításához is rendelkezésre állnak.

1. Horst Feistel cikke:

Kriptográfia és számítógépes biztonság.

(ugyanazon a címen található, mint az előző cikk)

1. Ross N. Williams:

Elemi útmutató a CRC hibafelismerő algoritmusokhoz

Közzétéve az oldalon www.wasm.ru.

Köszönetnyilvánítás.

Köszönetemet szeretném kifejezni a www.wasm.ru fórum minden látogatójának. De különösen szeretnék köszönetet mondani ChS -nek, akit jelenleg SteelRat néven ismernek, segített megérteni azokat a dolgokat, amelyeket valószínűleg soha nem értettem volna meg, valamint segítséget a bekezdés megírásában: „ Főbb információs követelmények”, Ennek a bekezdésnek a fő részét ő írta. Nagyon hálás vagyok a KSTU nevéhez fűződő alkalmazottjának is A.N. Tupolev Anikin Igor Vjacseszlavovics, és bűn lenne nem említeni Chris Kasperskyt azért, hogy ő az, és Volodya / wasm.ru utasításait. Ja, és tőle kapom :). Szeretném megjegyezni a Sega-Zero / Callipso-t is, de ez valami matematikai dzsungelt juttatott az eszembe.

Talán csak ennyit szeretnék elmondani.

Hálás lennék minden kritikáért vagy kérdésért, ami ehhez a cikkhez kapcsolódik, vagy csak tanácsokat. Elérhetőségeim: [e -mail védett], ICQ - 337310594.

Üdvözlettel: Evil`s Interrupt.

P.S .: Ezzel a cikkel nem próbáltam senkit felülmúlni. Szándékosan írták, hogy megkönnyítsék a GOST tanulmányozását, és ha nehézségei vannak, ez nem jelenti azt, hogy bűnös vagyok ebben. Légy ésszerű és türelmes, minden jót neked!

Ez az algoritmus kötelező titkosítási algoritmusként az Orosz Föderáció kormányzati szervezeteiben és számos kereskedelmi szervezetben.

Algoritmus leírása

Az algoritmus diagramja az ábrán látható. 3.1. Amint láthatja, ennek az algoritmusnak a sémája meglehetősen egyszerű, ami egyértelműen leegyszerűsíti a szoftver vagy a hardver megvalósítását.

A GOST 28147-89 algoritmus 64 bites blokkokban titkosítja az információkat, amelyek két 32 bites részblokkra (N1 és N2) vannak felosztva. Az N1 alblokk bizonyos módon kerül feldolgozásra, majd hozzáadódik az értéke

az alblokk N2 értékével (az összeadást a 2. modullal hajtjuk végre), akkor az alblokkok felcserélődnek. Az ilyen átalakítást bizonyos számú körre hajtják végre: 16 vagy 32, az algoritmus működési módjától függően (alább). Minden körben a következő műveleteket hajtják végre:

1. Kulcsréteg. A / VI alblokk tartalmát a Kx kulcs egy részével modulo 2 32 hozzáadjuk.

A GOST 28147-89 algoritmus titkosítási kulcsa 256 bites, a Kx pedig a 32 bites része, vagyis a 256 bites titkosítási kulcs 32 bites alkulcsok összefűzéseként jelenik meg (3.2. Ábra) :

SH ATI, AG2, Yu, AG4, K5, KB, K7.

A titkosítási folyamatban az egyik alkulcsot használják, a kerek számtól és az algoritmus működési módjától függően.

Rizs. 3.1. GOST 28147 algoritmus séma

Rizs. 3.2. GOST 28147-89 algoritmus titkosítási kulcs

2. Táblás csere. A kulcs megadása után a / VI alblokk 4 bitből álló 8 részre oszlik, amelyek mindegyikének értékét egyedileg cserélik ki az alblokk ezen részének cseréjét tartalmazó táblázatnak megfelelően. A helyettesítő dobozokat (S-box) gyakran használják a modern titkosítási algoritmusokban, ezért érdemes részletesebben megfontolni őket.

A táblázatos helyettesítést ilyen módon használják: egy bizonyos dimenziójú adatblokkot (ebben az esetben 4 bites) táplálnak a bemenetre, amelynek számszerű megjelenítése határozza meg a kimeneti érték számát. Például van egy S-boxunk a következő formában:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Jöjjön egy 4 bites "0100" mondat a bemenetre, azaz a 4. értékre. A táblázat szerint a kimeneti érték 15 lesz, azaz. "1111" (a 0 helyett 4, az 1 helyett 11, a 2 értéke nem változik stb.).

Amint láthatja, az algoritmus séma nagyon egyszerű, ami azt jelenti, hogy a legnagyobb adattitkosítási terhelés a helyettesítő táblákra esik. Sajnos az algoritmusnak megvan az a tulajdonsága, hogy vannak „gyenge” helyettesítő táblák, amelyek használatakor az algoritmus kriptoanalitikus módszerekkel nyilvánosságra hozható. A gyengék közé tartozik például egy táblázat, amelyben a kimenet megegyezik a bemenettel:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Bitenkénti ciklikus bal eltolás 11 bittel.

Algoritmus működési módok

A GOST 28147-89 algoritmus 4 üzemmóddal rendelkezik:

□ egyszerű cseremód;

□ gamma mód;

P gamma mód visszacsatolással;

□ szimulátorok gyártási módja.

Ezek az üzemmódok némileg különböznek az általánosan elfogadottaktól (az 1.4. Fejezetben leírtak), ezért érdemes részletesebben megfontolni őket.

Ezeknek az üzemmódoknak különböző céljaik vannak, de ugyanazt a titkosítási transzformációt használják.

Egyszerű csere mód

Egyszerű cserélési módban a fent leírt 32 fordulót egyszerűen végrehajtják az egyes 64 bites információblokkok titkosításához. A 32 bites alkulcsokat a következő sorrendben használjuk:

□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI, stb. - az 1-24. Fordulóban;

□ K1, Kb, K5, K4, KZ, K2, K \, KO - 25 -től 32 -ig tartó körökben.

Az egyszerű csere módban a visszafejtés pontosan ugyanúgy történik, de az alkulcsok kissé eltérő sorrendjében:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - 1-8. Fordulóban;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb, stb. - 9. és 32. között.

A szokásos EKB módhoz hasonlóan a blokkok külön titkosítása miatt az egyszerű helyettesítési mód erősen nem ajánlott az adatok titkosítására; csak többkulcsos sémákban más titkosítási kulcsok titkosítására használható.

Gamma mód

Gamma üzemmódban (3.3. Ábra) minden egyszerű szöveges blokk bites módon hozzáadódik a modulo 2-hez egy 64 bites titkosított gamma blokkkal. A titkosítás gamma egy speciális szekvencia, amelyet a fent leírt transzformációk segítségével állítanak elő:

1. Az N1 és N2 regiszterekben a kezdeti kitöltésük van írva-egy 64 bites érték, amelyet "szinkron-törtnek" neveznek (a szinkron-tört, valójában az inicializáló vektor analógja a CBC, CFB és OFB módokban).

2. A regiszterek / VI és N2 tartalmának titkosítása (ebben az esetben - szinkronizáló üzenetek) egyszerű cseremódban történik.

3. Az N1 tartalmát modulusan (2 32 - 1) adjuk hozzá CI = 2 24 + 2 16 + 2 8 + 4 konstanssal, az összeadás eredményét a / VI regiszterbe írjuk.

4. Az N2 tartalmát hozzáadjuk a 2 modulushoz a C2 = 2 24 + 2 16 + 2 8 +1 állandóval, a hozzáadás eredményét az N2 regiszterbe írjuk.

5. A / VI és N2 regiszterek tartalma 64 bites titkosított gamma blokkként kerül kiadásra (azaz ebben az esetben a / VI és N2 képezik az első gamma blokkot).

6. Ha a következő gamma blokkra van szükség (azaz folytatnia kell a titkosítást vagy a visszafejtést), akkor visszatér a 2. lépéshez.

A dekódoláshoz a gamma hasonló módon jön létre, majd az XOR műveletet ismét alkalmazza a titkosított szövegre és a gamma bitekre.

Ugyanazon titkosítási tartomány létrehozásához a kriptogramot visszafejtő felhasználónak ugyanazzal a kulccsal és azonos szinkronüzenet értékkel kell rendelkeznie, amelyet az információk titkosítására használtak. Ellenkező esetben nem lesz lehetséges az eredeti szöveg lekérése a titkosított szövegből.

A GOST 28147-89 algoritmus legtöbb megvalósításában a szinkronizálási üzenet nem titkos elem, azonban a szinkronizálási üzenet olyan titkos lehet, mint a titkosítási kulcs. Ebben az esetben feltételezhetjük, hogy az algoritmuskulcs tényleges hossza (256 bit) a szinkronizálási üzenet további 64 bitjével növekszik, ami további kulcselemnek tekinthető.

Gamma mód visszajelzéssel

A gamma módban visszacsatolással, a regiszterek / VI és L / 2 kitöltéseként, a 2. blokktól kezdve nem az előző gamma blokkot használják, hanem az előző szöveges blokk titkosításának eredményét (3.4. Ábra) . Az első blokk ebben a módban teljesen hasonló az előzőhöz.

Rizs. 3.4. A gamma kódolás generálása visszacsatolási gamma módban

A szimulátor gyártási módja

Az előtag egy titkosítási ellenőrző összeg, amelyet egy titkosítási kulcs segítségével számítanak ki az üzenetek integritásának ellenőrzésére. Ennek kiszámításához van egy speciális mód a GOST 28147-89 algoritmusra.

A szimulátor generálása a következőképpen történik:

1. Az első 64 bites információblokkot, amelyhez az előtagot kiszámítják, az N1 és N2 regiszterekbe írják, és az egyszerű csere csökkentett módjában titkosítják, amelyben a 32-ből az első 16 kör kerül végrehajtásra.

2. A kapott eredmény összegződik a 2 -es modulo -val a következő információblokkal, és az eredményt N1 -ben és N2 -ben tárolja.

3. Az M és az N2 újra titkosítva van az egyszerű csere csökkentett módjában, és így tovább az utolsó információs blokkig.

Az utánzó az N1 és N2 regiszterek 64 bites eredő tartalma vagy annak egy része. A leggyakrabban használt 32 bites előtagot használják, vagyis a regiszter tartalmának felét. Ez elég, hiszen mint minden ellenőrző összeg, a szimulátort is elsősorban az információk véletlen torzulása elleni védelemre tervezték. A szándékos adatmódosítás elleni védelem érdekében más kriptográfiai módszereket használnak - először is egy elektronikus digitális aláírást (lásd az 1.1. Szakaszt).

Az utánzót a következőképpen használják:

1. Bármilyen információ titkosításakor kiszámítunk egy egyszerű szöveges előtagot, és elküldjük a titkos szöveggel együtt.

2. A dekódolás után az előtag újra kiszámításra kerül, és összehasonlításra kerül az elküldöttel.

3. Ha a számított és elküldött előtagok nem egyeznek - a titkosított szöveg torz volt az átvitel során, vagy helytelen kulcsokat használtak a visszafejtés során.

Az előtag különösen hasznos a kulcsinformációk helyes visszafejtésének ellenőrzéséhez, ha többkulcsos sémákat használ.

Az utánzó a CBC módban számított MAC üzenet hitelesítési kód valamilyen analógja; a különbség az, hogy a szinkronizálási üzenetet nem használják az előtag számításakor, míg az inicializáló vektort a MAC kiszámításához használják.

Az algoritmus kriptográfiai ereje

1994-ben a GOST 28147-89 algoritmus leírását lefordították angolra és közzétették; ez után kezdtek megjelenni a külföldi szakértők által végzett elemzésének eredményei; azonban jó ideje nem találtak megvalósíthatónak számító támadásokat.

□ nagy kulcshossz - 256 bit; a titkos szinkronizálási üzenettel együtt a tényleges kulcshossz 320 bitre nő;

□ 32 forduló fordulat; 8 forduló után a bemenő adatok szórásának teljes hatása érhető el: a sima szöveges blokk egy bitjében bekövetkező változás a titkosított szövegblokk összes bitjét érinti, és fordítva, azaz többszörös biztonsági tartalék.

Tekintsük a GOST 28147-89 algoritmus kriptoanalízisének eredményeit.

A helyettesítő táblázatok elemzése

Mivel a helyettesítési táblázatok nem szerepelnek a szabványban, számos munka (például c) azt sugallja, hogy az "illetékes szervezet" képes "jó" és "rossz" helyettesítési táblázatokat is előállítani. A híres szakértő, Bruce Schneier azonban "pletykának" nevezi az ilyen feltételezéseket. Nyilvánvaló, hogy az algoritmus titkosítási erőssége nagymértékben függ a használt helyettesítő táblák tulajdonságaitól, ennek megfelelően vannak gyenge helyettesítő táblák (lásd a fenti példát), amelyek használata egyszerűsítheti az algoritmus elleni támadást. Mindazonáltal a különböző helyettesítő táblák használatának lehetősége nagyon érdemes ötletnek tűnik, amely mellett két tény is említhető a DES titkosítási szabvány történetéből (részletekért lásd a 3.15. Szakaszt):

□ A DES algoritmus lineáris és differenciális kriptoanalízisét alkalmazó támadások a helyettesítő táblázatok sajátosságait használják; más táblázatok használatakor a kriptoanalízist elölről kell kezdeni;

□ megpróbálták megerősíteni a DES -t a lineáris és differenciális kriptoanalízis ellen robusztusabb helyettesítési táblázatok használatával; ilyen, valóban robusztusabb táblákat javasoltak például az s 5 DES algoritmusban; de sajnos lehetetlen volt a DES -t s 5 DES -re cserélni, mivel a helyettesítő táblák mereven vannak definiálva a szabványban, az algoritmus megvalósítása valószínűleg nem támogatja a táblázatok másokra való cseréjének lehetőségét.

Számos munka (például és) tévesen arra a következtetésre jut, hogy a GOST 28147-89 algoritmus helyettesítési titkos táblái a kulcs részei lehetnek, és növelhetik annak tényleges hosszát (ami jelentéktelen, mivel az algoritmus nagyon nagy 256- bit kulcs). A munka azonban bebizonyította, hogy a titkos helyettesítő táblákat a következő támadással lehet kiszámítani, amely a gyakorlatban is alkalmazható:

1. Beállítjuk a nulla gombot, és végrehajtjuk a „nullavektor” keresését, vagyis a z = / (0) értékeket, ahol a (() az algoritmuskör függvénye. Ez a szakasz körülbelül 2 titkosítási műveletet igényel.

2. A nullavektor segítségével kiszámítják a helyettesítő táblák értékeit, ami nem több, mint 2 11 művelet.

Az algoritmus módosítása és elemzése

A munka a GOST 28147-89 algoritmus módosításainak kriptoanalízisét végezte:

□ a GOST-H algoritmus, amelyben az eredeti algoritmushoz képest megváltozik az alkulcsok használatának sorrendje, nevezetesen a 25–32. Körben az alkulcsokat közvetlen sorrendben használják, azaz ugyanabban az algoritmus előző fordulói;

□ 20 körös GOST® algoritmus, amely XOR-t használ a kulcs alkalmazására a modulo 32 összeadás helyett.

Az elemzés eredményei alapján arra a következtetésre jutottak, hogy a GOST-H és a GOST © gyengébbek, mint az eredeti GOST 28147-89 algoritmus, mivel mindkettőnek vannak gyenge kulcsú osztályai. Meg kell jegyezni, hogy a GOST © kriptoanalízis részében a mű szóról szóra megismétli a GOST 28147-89 algoritmus kriptoanalízisének szentelt részt, amelyet 2000-ben publikált egy jól ismert mű (az eredetire való hivatkozás nélkül) . Ez kétségbe vonja a mű szerzőinek professzionalizmusát és a többi eredményét.

Az algoritmus egy nagyon érdekes módosítását javasoljuk a munkában: az S \… Ss tábláknak különbözőeknek kell lenniük; az algoritmus minden fordulójában át kell rendezni őket egy bizonyos törvény szerint. Ez a permutáció függhet a titkosítási kulttól, vagy lehet titkos is (vagyis része lehet az eredeti 256 bites kulcsnak nagyobb titkosítási kulcsnak). Szerzőik szerint mindkét lehetőség jelentősen növeli az algoritmus lineáris és differenciális kriptoanalízissel szembeni ellenállását.

A helyettesítő táblákhoz kapcsolódó további módosítást pedig a munka ad, amely a titkosítási kulcs alapján a helyettesítő táblák kiszámításának egyik lehetséges módszerét elemzi. A munka szerzői arra a következtetésre jutottak, hogy az ilyen függőség gyengíti az algoritmust, mivel gyenge kulcsok jelenlétéhez és az algoritmus néhány potenciális sebezhetőségéhez vezet.

Teljes körű algoritmus elemzés

A GOST 28147-89 teljes körű támadásai vannak módosítások nélkül. Az egyik első nyilvános munka, amelyben az algoritmus elemzését végezték - egy jól ismert munka - olyan támadásoknak szentelt, amelyek kihasználják számos ismert titkosítási algoritmus kulcsbővítési eljárásának gyengeségeit. Különösen a teljes körű GOST 28147-89 algoritmus megszakítható differenciális kriptoanalízissel a kapcsolt kulcsokon, de csak akkor, ha gyenge helyettesítési táblázatokat használnak. Az algoritmus 24 körös változata (amelyből hiányzik az első 8 forduló) ugyanúgy nyitható meg minden helyettesítő táblánál, de az erős csere táblázatok (például a c. Ábrán láthatók) teljesen alkalmatlanná teszik az ilyen támadást.

A hazai tudósok, A. G. Rostovcev és E. B. Makhovenko 2001 -ben munkájukban egy alapvetően új kriptoanalízis -módszert javasoltak (a szerzők szerint sokkal hatékonyabb, mint a lineáris és differenciális kriptoanalízis) azzal, hogy egy ismert egyszerű szövegből objektív függvényt alakítanak ki a titkosított szövegnek megfelelően és a kívánt kulcsértéket, és megtalálja a végső értékét a valódi kulcsértéknek megfelelően. Megtalálták a GOST 28147-89 algoritmus gyenge kulcsainak nagy osztályát is, amelyek lehetővé teszik az algoritmus megnyitását csak 4 kiválasztott egyszerű szöveg és a megfelelő titkosított szövegek használatával, meglehetősen alacsony összetettséggel. A munkában folytatódik az algoritmus rejtjelezése.

2004 -ben egy koreai szakembercsoport támadást javasolt, amellyel a kapcsolt kulcsokon végzett differenciális kriptoanalízis segítségével 91,7% -os valószínűséggel 12 bit titkos kulcsot lehet beszerezni. A támadáshoz 2 35 kiválasztott nyílt szöveg és 2 36 titkosítási művelet szükséges. Mint látható, ez a támadás gyakorlatilag haszontalan az algoritmus elleni valódi támadáshoz.

GOST 28147-89 algoritmus és "Magma" rejtjelezés (GOST R 34.12-2015)

Az algoritmus általános sémája. A GOST 28147-89 „Információfeldolgozó rendszerek. Kriptográfiai védelem. Cryptographic Transformation Algorithm ", a szimmetrikus titkosítás hazai szabványa (2016. január 1 -je előtt), és kötelező az állami információs rendszerekben, és bizonyos esetekben a kereskedelmi rendszerekben használt hitelesített titkosítási információvédelmi eszközökben való megvalósításhoz. Az információk titkosításának védelmére szolgáló eszközök tanúsítása szükséges az Orosz Föderáció államtitokát képező információk, valamint az olyan információk védelméhez, amelyek titkosságáról a hatályos jogszabályoknak megfelelően gondoskodni kell. Szintén az Orosz Föderációban a GOST 28147-89 algoritmus használata ajánlott a banki információs rendszerek védelmére.

A GOST 28147-89 algoritmus (2.21. Ábra) a Feistel-sémán alapul, és 64 bites blokkokban titkosítja az információkat, amelyek két 32 bites (I, és R). Részblokk R, a kerek transzformációs függvény dolgozza fel, majd ennek értékét hozzáadjuk az Lj alblokk értékéhez, majd a részblokkokat felcseréljük. Az algoritmus 16 vagy 32 fordulóból áll, a titkosítási módtól függően (az utánzatbeillesztés vagy más titkosítási módok kiszámítása).

Rizs. 2.21.

Az algoritmus minden körében a következő átalakításokat hajtják végre.

1. Kulcsréteg. Tartalom alblokkolása R i hozzá a modulo 2 32 kerek kulccsal K. Kj a kerek kulcsként használt eredeti kulcs 32 bites része. A GOST 28147-89 ns algoritmus kulcsbővítési eljárást alkalmaz, az eredeti 256 bites titkosítási kulcs nyolc 32 bites alkulcs összekapcsolásaként (összefűzés) jelenik meg (2.22. Ábra): K 0, K (, K t K, K A, K 5, K 6, K 7.

A titkosítási folyamat ezen alkulcsok egyikét használja. NAK NEK

1. és 24. forduló között - közvetlen sorrendben:

A 25. és a 32. forduló között - fordított sorrendben:

Rizs. 2.22. A GOST 28147-89 algoritmus titkosítási kulcsa szerkezete

2. Táblás csere. A kulcs alkalmazása után a részblokk R i nyolc részre, de 4 bitre van osztva, amelyek mindegyikének értékét külön-külön cserélik ki a helyettesítő táblázatnak (S-box) megfelelően. Összesen nyolc S -dobozt használnak - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. A GOST 28147-89 algoritmus minden S-doboza egy vektor (egydimenziós tömb), amelynek ^ elemei 0-tól 15-ig vannak számozva. Az S-box értékei 4 bites számok; egész szám 0 és 15 között.

Az S-box táblából egy elem kerül, amelynek sorszáma egybeesik a helyettesítő bemenethez kapott értékkel.

Példa 2.6.

Legyen a következő alakú S-blokk:

Legyen ennek az S-boxnak a bemenete a 0100 2 = 4. Az S-box kimenete a helyettesítési táblázat 4. eleme lesz, azaz. 15 = 1111 2 (az elemek nullától kezdődően vannak számozva).

a helyettesítő személyeket nem határozza meg a szabvány, mint például a DES -kódban. A helyettesítő táblák megváltoztatható értékei jelentősen megnehezítik az algoritmus kriptoanalízisét. Ugyanakkor az algoritmus robusztussága jelentősen függ a helyes választástól.

Sajnos a GOST 28147-89 algoritmus „gyenge” helyettesítési táblákkal rendelkezik, amelyek használatakor az algoritmus könnyen felfedhető kriptoanalitikus módszerekkel. A "gyengék" közé tartozik például a triviális helyettesítési táblázat, amelyben a bemenet megegyezik a kimenettel (2.16. Táblázat).

2.16. Táblázat

Példa a gyenge S-boxra

Úgy gondolják, hogy a helyettesítő táblák konkrét értékeit titokban kell tartani, és hosszú távon kulcsfontosságú elemek, azaz sokkal hosszabb ideig érvényesek, mint az egyes kulcsok. A helyettesítő táblák titkos értékei azonban nem képezik a kulcs részét, és nem növelhetik annak tényleges hosszát.

Valójában a titkos helyettesítő táblákat a következő támadással lehet kiszámítani, amely a gyakorlatban is alkalmazható:

• egy nulla kulcs van beállítva, és a "nulla vektor" keresése történik, azaz. jelentése z = F ( 0), hol F - kerek transzformációs algoritmus függvénye. Ez körülbelül 2 32 teszt titkosítási műveletet igényel;
• a nulla vektor használatával kiszámítják a helyettesítő táblák értékeit, ami nem több, mint 2 11 művelet.

Azonban még akkor is, ha megsértik a helyettesítő táblázatok titkosságát, a titkosítás erőssége rendkívül magas marad, és nem esik a megengedett határ alá.

Azt is feltételezzük, hogy a helyettesítő táblák közösek minden titkosítási csomóponton belül egy kriptográfiai védelmi rendszeren belül.

Az S-dobozok szerkezetének javítása az egyik legintenzívebben kutatott probléma a szimmetrikus blokkotitkosítások területén. Alapvetően szükség van arra, hogy az S-dobozok bemeneteiben bekövetkező bármilyen változás kiáramoljon véletlen látszólag megváltoztatja a kimenetet. Egyrészt minél nagyobbak az S-dobozok, annál jobban ellenáll az algoritmus a lineáris és differenciális kriptoanalízis módszereinek. Másrészt egy nagy csereasztalt nehezebb megtervezni.

A modern algoritmusokban az S-dobozok általában vektorokat (egydimenziós tömb) tartalmaznak 2 "t- bit elemek. A blokk bemenet határozza meg az elem számát, amelynek értéke az S-mondat kimenete.

Az S-dobozok tervezéséhez számos kritériumot terjesztettek elő. A helyettesítési táblázatnak meg kell felelnie:

• szigorú lavina kritérium;
• bit függetlenségi kritérium;
• nemlinearitási követelmény a bemeneti értékekből.

Az utolsó követelmény teljesítése érdekében javasolták a lineáris kombináció meghatározását én bit ( i = 1, ..., T) helyettesítési táblázat értékei hajlított függvények(eng, hajlított - eltérés, ebben az esetben - a lineáris függvényektől). A hajlított függvények a Boole -függvények egy speciális osztályát alkotják, amelyet a nemlinearitás legmagasabb osztálya és a szigorú lavina kritériumnak való megfelelés jellemez.

Néhány munkában az S-dobozok esetében javasolt az y sorrend garantált lavinahatásának teljesítésének ellenőrzése-ha egy bemeneti bit megváltozik, akkor legalább az S-box kimeneti bitjei változnak. A garantált lavinaeffektus tulajdonsága, amely y-tól 2-ig terjed, nagyjából elegendő diffúziós karakterisztikát biztosít az S-dobozok számára bármilyen titkosítási algoritmushoz.

A kellően nagy csereasztalok tervezésekor a következő módszerek használhatók:

• véletlenszerű kiválasztás (kis S-dobozok esetén gyenge helyettesítő táblák létrehozásához vezethet);
• véletlenszerű kiválasztás, majd a különböző kritériumoknak való megfelelés ellenőrzése, és a gyenge S-dobozok elutasítása;
• kézi kiválasztás (túl fáradságos a nagy S-blokkokhoz);
• matematikai megközelítés, például hajlított függvényeket használó generálás (ezt a megközelítést alkalmazzák a CAST algoritmusban).

A GOST 28147-89 algoritmus egyes S-blokkjainak tervezésére a következő eljárás javasolt:

• minden S-box négy logikai függvénnyel írható le, mindegyik funkciónak négy logikai argumentummal kell rendelkeznie;
• ezeknek a funkcióknak elég összetettnek kell lenniük. Ezt a komplexitási követelményt formálisan nem lehet kifejezni, azonban szükséges feltételként megkövetelhető, hogy a megfelelő logikai függvények, amelyeket minimális formában (azaz a lehető legkisebb kifejezéshosszal) írjunk meg, alapvető logikai műveletek mellett, ne legyenek rövidebbek, mint egy bizonyos előírt érték;
• az egyes függvényeknek, még a különböző helyettesítési táblázatokban is használva, kellően különbözniük kell egymástól.

2011-ben egy új támadást "reflexív találkozó közepén" javasoltak, amely kissé csökkenti a GOST 28147-89 ellenállását (2256-ról 2225-re). Az algoritmus legjobb kriptoanalízis eredménye 2012-től 2192-re csökkenti az erejét, ami viszonylag nagy titkosított szövegméretet és előre elkészített adatok mennyiségét igényli. A javasolt támadások ellenére a GOST 28147-89 gyakorlatilag stabil marad a számítástechnika jelenlegi fejlettségi szintjén.

"Magma" kód (GOST R 34.12-2015). A GOST 28147-89 szabvány több mint 25 éve van érvényben Oroszországban. Ez idő alatt elegendő tartósságot és jó hatékonyságot mutatott a szoftver- és hardver implementációkban, beleértve az alacsony erőforrású eszközöket is. Bár olyan kriptoanalitikus támadásokat javasoltak, amelyek csökkentik az ellenállás becsléseit (a legjobb 2192 -ig), ezek távolról sem kivitelezhetők. Ezért úgy döntöttek, hogy a GOST 28147-89 algoritmust beépítik az újonnan kifejlesztett szimmetrikus titkosítási szabványba.

A 2015-ös üzletben két új nemzeti titkosítási szabványt fogadtak el: GOST R 34.12-2015 „Informatikai technológia. Kriptográfiai információvédelem. Blokkos titkosítás "és a GOST R 34.13-2015" Informatikai technológia. Kriptográfiai információvédelem. A blokkolt rejtjelezés működési módjai ", amelyek 2016. január 1 -jén lépnek hatályba.

A GOST R 34.12-2015 szabvány két, 128 és 64 bites blokkhosszúságú titkosító kód leírását tartalmazza. A rögzített nemlineáris helyettesítő blokkokkal rendelkező GOST 28147-89 titkosítást az új GOST R 34.12-2015 64 bites titkosító kódként tartalmazza.

Az alábbiakban a szabványban rögzített csereblokkok találhatók:

A szabványban megadott S-dobozok biztosítják a legjobb jellemzőket, amelyek meghatározzák a kriptoalgoritmus differenciális és lineáris kriptoanalízissel szembeni ellenállását.

Az "Információk titkosításának védelme" szabványosítási technikai bizottság (TC 26) szerint a nemlineáris helyettesítő blokkok rögzítése egységesebbé teszi a GOST 28147-89 algoritmust, és segít megszüntetni a "gyenge" nemlineáris helyettesítő blokkok használatát. Ezenkívül a titkosítás minden hosszú távú paraméterének rögzítése megfelel az elfogadott nemzetközi gyakorlatnak. Az új GOST R 34.12-2015 szabvány terminológiailag és fogalmilag kapcsolódik az ISO / IEC 10116 „Informatikai technológia” nemzetközi szabványokhoz. Biztonsági módszerek. Üzemmódok a "bites blokk titkosításhoz" (ISO / IEC 10116: 2006 Informatika - Biztonsági technikák - Egy n -bites blokkotitkosító működési módjai) és az ISO / IEC 18033 sorozat "Informatika. A biztonság biztosításának módszerei és eszközei. Titkosítási algoritmusok ": ISO / IEC 18033-1: 2005" 1. rész. Általános "(ISO / IEC 18033-1: 2005 Informatika - Biztonsági technikák - Titkosítási algoritmusok - 1. rész: Általános) és ISO / IEC 18033-3: 2010 "3. rész. Blokkoló titkosítás" (ISO / IEC 18033-3: 2010 (Informatika - Biztonsági technikák - Titkosítási algoritmusok - 3. rész: Blokkos titkosítás)).

A GOST P 34.12-2015 szabvány tartalmaz egy új, 128 bites blokkméretű blokkot ("Grasshopper") is. Ez a rejtjelezés várhatóan robusztus lesz a ma ismert összes blokktitkos támadással szemben.

A blokkoló rejtjelezési módok (egyszerű csere, gamma, gamma kimeneti visszacsatolással, gamma titkosított szövegvisszacsatolással, egyszerű lecserélés bekapcsolással és utánzatbetét kifejlesztése) egy külön szabványban találhatók, amely megfelel a GOST R 34.13-2015 szabványnak. az elfogadott nemzetközi gyakorlat. Ezek az üzemmódok mind a Magma, mind az új Grasshopper titkosításra alkalmazhatók.

• A bites körkörös bal oldali eltolást 11 bittel hajtjuk végre. A visszafejtés ugyanazon séma szerint, de eltérő kulcshasználati ütemterv szerint történik: az 1. és a 8. visszafejtési forduló között - közvetlen sorrendben: a 9. és 32. visszafejtési körből - fordított sorrendben: A A GOST 28147-89 szabványban szereplő DES-titkosítás a következő előnyökkel rendelkezik: jelentősen hosszabb kulcs (256 bit a DES-titkosításhoz képest 56-tal szemben), olyan támadás, amely ellen a kulcskészlet nyers erővel történő felsorolása jelenleg lehetetlennek tűnik; a kulcs használatának egyszerű ütemezése, amely egyszerűsíti az algoritmus megvalósítását és növeli a számítások sebességét. S-blokkok tervezése GOST 28147-89. Nyilvánvaló, hogy a GOST 28147-89 algoritmus sémája nagyon egyszerű. Ez azt jelenti, hogy a legnagyobb titkosítási terhelés a helyettesítő táblákra esik. Tab értékek
• Panasepko S.P. Titkosítási algoritmusok: speciális referenciakönyv. SPb.: BHV-Peter-burg, 2009.
• Kara O. Reflexiós támadások a termék titkosításai ellen. URL: http://eprint.iacr.org/2007/043.pdf
• Orosz titkosítási szabvány: csökkentett erősség. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Ne rohanjon temetni."

Az ismert kutató, az algebrai kriptoanalízis alapítója, Nicolas Courtois azt állítja, hogy a GOST blokk-titkosítás, amely a közeljövőben nemzetközi szabvány lett, valójában meghibásodott, és számos publikációt vár a jövőben, amelyek fejlesztik elképzeléseit. az algoritmus instabilitásáról.

Az alábbiakban röviden idézünk ebből a munkából, amely a nemzetközi szabványosítás közepette riasztó támadásnak tekinthető (a szerző az AES -hez hasonló túlzásokról volt ismert, de munkája ekkor nagy elméleti hatással volt a kriptoanalízisre, de nem vezetett az AES elleni gyakorlati támadásokhoz). De talán ez is egy igazi figyelmeztetés a "repülőgép farkába bukás" szakaszának kezdetére, amely a nemzeti titkosítási szabvány összeomlásával érhet véget, mint az SHA-1 hash algoritmus esetében. a de facto MD5 hash algoritmus.

A GOST 28147-89 szabványt 1989-ben szabványosították, és ez lett a hivatalos szabvány a bizalmas információk védelmére, de a titkosítási előírás zárva maradt. 1994 -ben a szabványt megszüntették, közzétették és lefordították angolra. Az AES -hez hasonlóan (és a DES -től eltérően) a GOST korlátozások nélkül védheti a minősített információkat, az orosz szabványban meghatározott módon. Hogy. A GOST nem a DES analógja, hanem a 3-DES versenytársa három független kulccsal vagy AES-256-al. Nyilvánvaló, hogy a GOST egy meglehetősen komoly, katonai kritériumoknak megfelelő titkosítás, amelyet a legkomolyabb alkalmazások elvárásával hoztak létre. Az orosz bankok által használt alkalmazások alapján legalább két GOST S-doboz sorozatot azonosítottak. Ezeknek a bankoknak titkos kommunikációt kell folytatniuk több száz fiókteleppel, és dollármilliárdokat kell megvédeniük a csalárd lopásoktól.

A GOST egy egyszerű Feistel felépítésű blokkotitkosító, 64 bites blokkmérettel, 256 bites kulccsal és 32 fordulóval. Minden kör tartalmazza a modulok 2 ^ 32 gombok hozzáadását, egy nyolc darab 4 bites S-boxot és egy egyszerű 11 bites ciklikus eltolást. A GOST egyik jellemzője az S-blokkok titkos tárolásának képessége, amely második kulcsként jeleníthető meg, amely 610 bitre növeli a hatékony kulcsanyagot. Az S-boxok egy készletét 1994-ben tették közzé a GOST-R 34.11-94 kivonatfüggvény specifikáció részeként, és ahogy Schneier írta, az Orosz Föderáció Központi Bankja használta. Ez is szerepel az RFC4357 szabványban az "id-GostR3411-94-CryptoProParamSet" részben. Hiba volt a forráskódban Schneier könyve végén (S-box sorrendben). A natív orosz eredetű legpontosabb referencia -megvalósítás az OpenSSL könyvtárban található. Ha valahol titkos S-dobozokat használnak, akkor ezeket ki lehet nyerni a szoftver implementációiból és a mikroáramkörökből, sőt, a megfelelő munkákat közzétették.

A GOST komoly versenytárs

A nagyon nagy kulcsméret mellett a GOST lényegesen alacsonyabb végrehajtási költséggel rendelkezik az AES és más hasonló titkosítási rendszerekhez képest. Valójában sokkal kevesebbe kerül, mint az AES, ami négyszer annyi hardver logikai kaput igényel a jóval alacsonyabb biztonsági szinthez.

Nem meglepő, hogy a GOST internetes szabványmá vált, különösen sok kriptokönyvtárban, például az OpenSSL -ben és a Crypto ++ -ban, és egyre népszerűbb a származási országán kívül. 2010 -ben a GOST -t az egész világra kiterjedő titkosítási szabványnak nyilvánították az ISO szabványosításra. Rendkívül kevés algoritmus vált nemzetközi szabványt. Az ISO / IEC 18033-3: 2010 a következő algoritmusokat írja le: négy 64 bites titkosítás-TDEA, MISTY1, CAST-128, HIGHT-és három 128 bites rejtjelezés-AES, Camellia, SEED. A GOST-ot javasolt hozzáadni ugyanahhoz az ISO / IEC 18033-3 szabványhoz.

Az ipari szabványosítás történetében először foglalkozunk ilyen versenyképes algoritmussal a költségek és a biztonsági szint közötti optimitás szempontjából. A GOST 20 éves kriptoanalízis erőfeszítéseket tesz, és a közelmúltig katonai szintű biztonságát nem kérdőjelezték meg.

Amint azt a szerző nemrég magánlevelezésből megtudta, a legtöbb ország ellenezte a GOST -ot a szingapúri ISO -szavazáson, de ennek a szavazásnak az eredményeit továbbra is figyelembe vesszük az ISO SC27 plenáris ülésén, így a GOST még mindig szabványosítási folyamatban van e mű megjelenése.

Szakértői vélemények a GOST -ról

A GOST -ra vonatkozó rendelkezésre álló információk és irodalmak egyike sem indokolja azt, hogy a rejtjelezés nem biztonságos. Éppen ellenkezőleg, a nagy kulcsméret és a nagy számú kör teszi a GOST -ot első pillantásra alkalmassá több évtizedes használatra.

Aki ismeri Moore törvényét, rájön, hogy elméletileg a 256 bites kulcsok legalább 200 évig biztonságban maradnak. A GOST -ot széles körben tanulmányozták a titkosítással foglalkozó vezető szakértők, akik ismertek a blokk -titkosítás elemzésében, például Schneier, Biryukov, Dankelman, Wagner, sok ausztrál, japán és orosz tudós, az ISO titkosítási szakértői és minden kutató kifejezte, hogy minden úgy néz ki, hogy biztonságban lehet vagy kell lennie. Bár a vélemény széles körben megértette, hogy a GOST szerkezete például rendkívül gyenge, különösen a DES -hez képest, a diffúzió nem olyan jó, azonban ez mindig annak volt köszönhető, hogy ezt kompenzálni kell nagyszámú kör (32), valamint további nemlinearitás és diffúzió a modulus hozzáadásával.

Biryukov és Wagner ezt írta: "A nagy számú kör (32) és a jól tanulmányozott Feistel-konstrukció, valamint az egymást követő Shannon-féle permutációk kombinációja szilárd alapot biztosít a GOST biztonságához." Ugyanebben a munkában ezt olvashatjuk: "jelentős idő- és erőfeszítés után nem történt előrelépés a szabvány titkosított elemzésében a nyílt irodalomban." Így nem voltak olyan jelentős támadások, amelyek lehetővé tennék a visszafejtést vagy a kulcsok helyreállítását egy reális forgatókönyvben, ahol a GOST -ot sokféle véletlenszerű kulccsal történő titkosításban használják. Ezzel ellentétben sok mű ismert a GOST gyenge kulcsok elleni támadásairól, a kapcsolódó kulcsokkal történő támadásokról, a titkos S-dobozok helyreállításáról szóló támadásokról. A Crypto-2008-on egy ezen kódoláson alapuló hash függvény feltörését mutatták be. Minden támadásnál a támadónak lényegesen nagyobb szabadsága van, mint amit általában megengednének neki. A véletlenszerűen kiválasztott kulcsokat használó titkosítás hagyományos alkalmazásaiban eddig nem találtak komoly titkosítási támadásokat a GOST ellen, amit 2010 -ben az utolsó mondat fejezett ki: "a titkosítási elemzők jelentős erőfeszítései ellenére az elmúlt 20 évben a GOST repedt "(Axel Poschmann, San Ling és Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, 219-233, 2010).

Lineáris és differenciális elemzés GOST

Schneier jól ismert könyvében ezt olvashatjuk: "A differenciális és lineáris kriptoanalízis ellen a GOST valószínűleg robusztusabb, mint a DES." A GOST biztonságának fő értékelését 2000 -ben Gabidulin és munkatársai adták. Eredményeik nagyon lenyűgözőek: 2 ^ 256 -os biztonsági szint mellett öt kör elegendő a GOST megvédéséhez a lineáris kriptoanalízistől. Sőt, még akkor is, ha az S -dobozokat azonosra cseréli, és az egyetlen nemlineáris titkosítási művelet - az add mod 2 ^ 32 -, a kód még mindig ellenáll a lineáris kriptoanalízisnek 32 fordulóból 6 kör után. A 2 ^ 128 -as biztonsági szint eléréséhez a kutatók (Vitalij V. Shorin, Vadim V. Jelezniakov és Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint benyújtva az Elsevier Preprint -hez, 2001. április 4.) 7 kör alatt elegendő tartósságot feltételeztek. . Szerintük a GOST megtörése több mint öt fordulóban "rendkívül nehéz". Ezenkívül két japán kutató kimutatta, hogy egy klasszikus közvetlen differenciál támadásnak, egy differenciális jellemzővel, rendkívül kicsi a valószínűsége, hogy nagyszámú körön megy keresztül. Azon tény alapján, hogy korlátozott számú körre elegendő "jó" iteratív differenciális karakterisztikát tanulmányoztak (amely maga is valószínű, hogy körönként nem jobb, mint 2-11,4), a megfelelő kulcsok értéke kevesebb, mint a fele . Egy teljes körű GOST esetén egy ilyen, egyetlen jellemzővel rendelkező támadás csak a 2-62 nagyságrendű kulcsok elhanyagolható részével fog működni (és még ebben a kis részben is legfeljebb 2-360 valószínűséggel passzol ).

A kifinomultabb támadások több differenciálist foglalnak magukban, amelyek bizonyos mintákat követnek, például egyedi S-dobozokat használnak, amelyek nulla differenciálist tartalmaznak, míg más bitek nem nullát. A GOST gyenge diffúziós tulajdonságai alapján diszkriminatív támadásokról beszélünk. Ezek közül a legjobb támadások a GOST 17 fordulója ellen működnek, a kulttól függnek, és rendkívül gyenge megkülönböztető képességgel rendelkeznek a véletlenszerű adatok között a kimeneten, így valahogy felhasználhatók a kulccsal kapcsolatos információk megszerzésére.

Csúszás és elterelés támadások

Biryukov és Wagner szerint a GOST szerkezet, amely az alkulcsok fordított sorrendjét tartalmazza az utolsó körökben, ellenáll a csúszó támadásoknak (az úgynevezett "csúsztatásoknak"). Mivel azonban a rejtjelezésben nagy az ön-hasonlóság, ez lehetővé teszi a kulcsfontosságú inverziós támadásokat a rögzített pontok és a "tükröződési" tulajdonságok kombinációi ellen (ún. "Reflektív támadások") bizonyos gyenge kulcsok esetén. Ennek a támadásnak a bonyolultsága 2 ^ 192 és 2 ^ 32 egyező nyílt szöveg.

Legújabb eredmények

Az új támadások szintén tükröződést alkalmaznak, és valóban megtörték a GOST -ot, amelyet az FSE 2011. konferenciáján mutattak be, és ezeket a támadásokat a cikk szerzője önállóan is felfedezte. A támadás 2 ^ 132 bájt memóriát igényel, ami valójában rosszabb, mint a lassabb, kevesebb memóriaigényű támadás.

Számos új önhasonló támadás működik az összes GOST kulcs ellen, és lehetővé teszi a teljes körű GOST megszakítását 256 bites kulccsal, és nem csak a gyenge kulcsok esetében, mint korábban. Mindezek a támadások lényegesen kevesebb memóriát igényelnek, és lényegesen gyorsabbak.

Ezek az új támadások példáknak tekinthetők a blokk rejtjeleinek rejtjelezésének új általános paradigmájára, az úgynevezett "algebrai komplexitáscsökkentésre", és ezeknek a támadásoknak az általános rögzített pontokra, csúszásokra, involúciókra és ciklusokra vonatkozó támadásainak speciális eseteire általánosítását. Fontos, hogy mindezen támadások családjában vannak olyanok, amelyek lehetővé teszik a GOST kriptoanalízisét mindenféle reflexió nélkül és a számítások során megjelenő szimmetrikus pontok nélkül. Az egyik példa egy egyszerű GOST hackeléses támadás, amely nem tükrözi ezt a munkát.

Algebrai kriptoanalízis és alacsony adat bonyolultságú támadások a csökkentett fordulójú kódolók ellen

A blokk- és adatfolyam -titkosítók elleni algebrai támadások problémaként jeleníthetők meg egy nagy logikai algebrai egyenletrendszer megoldása során, amely követi egy adott kriptográfiai séma geometriáját és szerkezetét. Maga az ötlet Shannonra nyúlik vissza. A gyakorlatban a DES számára (ezt a munka szerzője mutatta be) formális kódolási módszerként mutatták be, és csak egy ismert egyszerű szövegben képes 6 kört feltörni. Az egyenletmanipuláció XL algoritmusokon, Gröbner bázisokon, ElimLin metóduson, SAT megoldókon alapul.

A gyakorlatban algebrai támadásokat hajtottak végre a blokk-rejtjelek nagyon kis száma ellen, de ezek már a patak titkosításának megrepedéséhez vezettek, és a mikroberendezések ultrakönnyű rejtjeleinek feltörése is sikeres. A memória mérete és a számítási költségbecslések nehézségei miatt ezeket más támadásokkal kombinálják.

Hogyan lehet feltörni a GOST -ot?

Ebben a kiadványban részletesebben bemutatjuk a teljes körű GOST elleni algebrai támadást. Egy korábbi művében a szerző már felvázolt 20 algebrai támadást a GOST ellen, és nagyszámúra számít a közeljövőben. Az ebben a munkában javasolt támadás nem a legjobb közülük, de egyszerű (legalábbis a kriptográfiai megértés számára) utat nyit a későbbi fejlesztések számára, hogy sajátos módszertant hozzon létre a GOST feltöréséhez.

A gyakorlati eredmény még szerény: 2 ^ 64 ismert egyszerű szöveg és 2 ^ 64 memória a nyílt szöveg / titkosított szöveg párok tárolására lehetővé teszi a GOST 2 ^ 8 gyorsabb feltörését, mint az egyszerű nyers erő. De ami a kriptoanalízist illeti, ez teljesen igazságossá teszi azt, hogy "a GOST feltört".

következtetéseket

A GOST célja, hogy katonai szintű biztonságot nyújtson 200 évre. A GOST -ot tanulmányozó vezető szakértők többsége egyetértett abban, hogy "a 20 éves jelentős kriptoanalitikai erőfeszítések ellenére a GOST -ot még nem sikerült feltörni". 2010 -ben a GOST -t globális titkosítási szabványként az ISO 18033 szabványra emelték.

Az algebrai kriptoanalízissel kapcsolatos elképzelések alapja több mint 60 évvel ezelőtt jelent meg. De csak az elmúlt 10 évben fejlesztettek ki hatékony szoftvereszközöket számos NP-teljes probléma (részleges) megoldására. Számos adatfolyam -titkosítás feltört. Ezzel a módszerrel csak egy blokkot rejtett el - maga a gyenge KeeLoq. Ebben a munkában a szerző megtörik egy fontos, ténylegesen használt GOST -titkosítást. Megjegyzi, hogy ez az első alkalom a történelemben, amikor egy szabványosított állapot -titkosítást megtört az algebrai kriptoanalízis.

Az FSE 2011 konferenciáján már bemutattak egy egyszerű "MITM -t, amely tükrözi a GOST -ot" támadást. A cikkben tárgyalt munkában egy másik támadás csak annak bemutatására szolgál, hogy hány GOST elleni támadás már megjelent, amelyek közül sok gyorsabbak, és az algebrai támadás sokkal kevesebb memóriát igényel, és szinte kimeríthetetlen lehetőségek tárházát nyitja meg az ellenfél számára, hogy különböző módon támadja meg a titkosítást. Ebben a dokumentumban is látható, hogy nincs szükség a reflexió tulajdonság használatára hackeléshez.

A szerző azt állítja, hogy nyilvánvaló, hogy a GOST -nak komoly hibái vannak, és most nem biztosítja az ISO által megkövetelt tartóssági szintet. Sok GOST elleni támadás az algebrai komplexitás csökkentésének paradigmájának megerősítése keretében kerül bemutatásra.

Végül a kutató különösen megjegyez néhány tényt, amelyek még nem állnak az olvasó rendelkezésére, de a kutató számára ismertek, és amelyek fontosak az ISO szabványosítási folyamat során. Ez a támadás nem csak egy "tanúsítási" támadás a GOST ellen, amely gyorsabb, mint a brute force brute force támadás. Valójában a GOST szabványosítása most rendkívül veszélyes és felelőtlen lenne. Ennek oka az, hogy a támadások egy része praktikus. A gyakorlatban egyes GOST -kulcsok akár visszafejthetők, legyenek azok gyengék, vagy a GOST privát alkalmazásaiból származó kulcsok. Az előző munkában a szerző részletesen megvizsgálja a gyakorlati támadások lehetőségének eseteit. Lényeges, hogy "ez az első alkalom a történelemben, hogy a katonai szintű titkok védelmére kifejlesztett, szabványosított, tömeges titkosítási kódot, amelyet a kormányok, nagybankok és más szervezetek államtitkai védelmére terveztek, egy matematikai támadás veszélyeztette."