Šifrovací algoritmus GOST 28147-89. Jednoduchý spôsob výmeny. - Archív WASM.RU

"Kým žiješ, neumieraj, pozri sa na tento svet."
Mnohí tu majú mŕtvu dušu - sú mŕtvi vo vnútri.
Ale chodia a smejú sa, nevediac, že ​​nie sú,
Neponáhľaj sa so svojou hodinou smrti, “povedala mi.

Aria, „tam hore“

2.1 Feistel siete.
2.2 Bloková šifra GOST 28147-89

3.1 Kľúčové informácie
3.2 Hlavný krok krypto transformácie

3.3 Základné cykly:“ 32-Z” , “ 32-R” .

4.1 Implementácia hlavného kroku krypto transformácie
4.2 Zvýšenie rýchlosti algoritmu
5. Kľúčové informačné požiadavky
6. Zoznam použitej literatúry
7. Poďakovanie.

Úvod.

Tento dokument je mojím pokusom popísať metódu jednoduchej výmeny šifrovacieho algoritmu GOST 28147-89 za najjednoduchší, ale napriek tomu technicky kompetentný jazyk. Po prečítaní prvých šiestich bodov čitateľ poskytne svoj názor na to, ako som to urobil.

Aby mala moja práca väčší úžitok, odporúčam vám vyzbrojiť sa dielami autorov uvedených v zozname použitej literatúry. Odporúča sa tiež, aby kalkulačka mala funkciu na výpočet operácie. XOR od prečítanie článku predpokladá, že čitateľ má v úmysle preštudovať tento šifrovací algoritmus. Hoci je vhodný aj ako referencia, ale tento článok som napísal presne ako školiaci.

Predbežné informácie o blokových šifrách.

Predtým, ako sa pozrieme na algoritmus, musíme sa zoznámiť s históriou vzniku tohto druhu šifier. Algoritmus patrí do kategórie blokových šifier, v architektúre ktorých sú informácie rozdelené do konečného počtu blokov, pričom posledný nemusí byť úplný. Proces šifrovania prebieha v celých blokoch, ktoré tvoria šifru. Posledný blok, ak je neúplný, je niečím doplnený (nižšie poviem o nuanciách jeho dokončenia) a je šifrovaný rovnakým spôsobom ako úplné bloky. Pod šifrou mám na mysli výsledok šifrovacej funkcie pôsobiacej na určité množstvo údajov, ktoré používateľ odoslal na šifrovanie. Inými slovami, šifra je konečným výsledkom šifrovania.

História vývoja blokových šifier je spojená so začiatkom 70. rokov, keď spoločnosť IBM, uvedomujúc si potrebu ochrany informácií pri prenose údajov prostredníctvom počítačových komunikačných kanálov, zahájila vlastný výskumný program zameraný na ochranu informácií v elektronických sieťach, vrátane kryptografie.

Skupinu výskumníkov - vývojárov z IBM, ktorá začala skúmať šifrovacie systémy so symetrickou schémou použitia kľúčov, viedol Dr. Horst Feistel.

2.1 Siete Feistel

Architektúra novej metódy šifrovania, ktorú Feistel navrhol v klasickej literatúre, sa nazýva „Feistel Architecture“, ale v súčasnosti sa v ruskej a zahraničnej literatúre používa ustálenejší výraz - „Feistelova sieť“ alebo Feistelova sieť. Následne bola na tejto architektúre postavená šifra „Lucifer“ - ktorá bola neskôr publikovaná a spôsobila novú vlnu záujmu o kryptografiu vo všeobecnosti.

Myšlienka architektúry „siete Feistel“ je nasledovná: vstupný tok informácií je rozdelený na bloky s veľkosťou n bitov, kde n je párne číslo. Každý blok je rozdelený na dve časti-L a R, potom sú tieto časti zaradené do iteratívnej blokovej šifry, v ktorej je výsledok j-tého stupňa určený výsledkom predchádzajúceho stupňa j-1! Možno to ilustrovať na príklade:

Ryža. 1

Kde funkcia A je hlavným pôsobením blokovej šifry. Môže ísť o jednoduchú akciu, ako je napríklad operácia XOR, alebo môže mať zložitejší tvar ako sekvencia série jednoduchých akcií - pridanie modula, posun doľava, výmena prvku atď. Spolu tieto jednoduché akcie tvoria takzvaný - hlavný krok krypto transformácie.

Je potrebné poznamenať, že kľúčovými prvkami činnosti funkcie sú dodávka kľúčových prvkov a operácia XOR a z toho, ako dobre bola práca týchto operácií premyslená, hovorí o kryptografickej sile šifry ako celku.

Aby bola myšlienka sietí Feistel konečne jasná, zvážte najjednoduchší prípad uvedený v ryža. 1, kde vo funkcii A - budú operácie „mod 2“ („xor“), ale toto najjednoduchšie prípad, v závažnejšej situácii, napríklad skrývajúca informácie štátneho významu, funkcia A môže byť zložitejšia (pokiaľ som videl, funkcia A je skutočne veľmi zložitá):

Počiatočné údaje:

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

Získajte šifru

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

Vysvetlime svoje akcie:

1. Táto operácia je režim pridania 2 4. V praxi sa takáto operácia zredukuje na jednoduché sčítanie, kde musíme sčítať dve čísla a prenos na 5. číslicu ignorovať. Pretože, ak umiestnime exponenty nad číslice binárnej reprezentácie čísla, bude existovať exponent štyri nad piatou číslicou, pozrime sa na nasledujúci obrázok, ktorý ukazuje akcie našej operácie:

Ryža. 2

Tu som ukázal na exponenty šípkou, ako vidíte, výsledok mal byť 10100, ale pretože prenos je počas operácie mod 2 4 ignorovaný, dostaneme 0100.

2. Táto operácia sa v literatúre nazýva mod 2, v montážnom jazyku je implementovaná príkazom XOR... Správnejší názov je však mod 2 1. Bez tejto unikátnej operácie je len ťažko možné postaviť rýchly, ľahko implementovateľný šifrovací algoritmus a zároveň tak, aby bol stále dostatočne kryptograficky silný. Jedinečnosť tejto operácie spočíva v tom, že sama je opakom! Napríklad, ak je číslo A XOROVANÉ s číslom B, v dôsledku toho dostaneme B, v budúcnosti stačí medzi sebou reXOROVAŤ čísla B a C, aby sme získali predchádzajúcu hodnotu A!

V tejto operácii sme dostali 1010 s číslami 1110 a 0100, aby sme sa vrátili 1110, stačí znova XOR čísiel 0100 a 1010! Viac podrobností o tejto operácii nájdete v článku, ktorý je pripojený k webu. www.wasm.ru, « Základný sprievodca kAlgoritmy detekcie chýb CRC_»Autor, ktorý Ross N. Williams... V tejto práci je bod - „ 5. Binárna aritmetika bez delenia slov“. V tomto článku je popísaná operácia. xor! Volám, pretože v tomto článku je táto operácia naplánovaná tak, že čitateľ nielenže pochopí, ako táto operácia funguje, ale dokonca ju spustí. vidieť, počuť a ​​cítiť!

3. Táto akcia je potrebná, aby bolo možné zo šifrovania počas dešifrovania získať počiatočné hodnoty.

2.2 Bloková šifra GOST 28147-89

Šifrovací algoritmus GOST 28147 - 89 patrí do kategórie blokových šifier pracujúcich podľa architektúry vyvážených sietí Feistel, kde dve časti vybraného bloku informácií majú rovnakú veľkosť. Algoritmus bol vyvinutý v hĺbke ôsmeho oddelenia KGB, teraz sa transformoval na FAPSI a bol zakódovaný ako šifrovací štandard Ruskej federácie v roku 1989 pod ZSSR.

Aby tento spôsob algoritmu fungoval, je potrebné rozdeliť informácie do blokov s veľkosťou 64 bitov. Vygenerujte alebo zadajte do šifrovacieho systému nasledujúce kľúčové informácie: kľúč a substitučná tabuľka. Výber kľúča a substitučnej tabuľky na šifrovanie by sa mal brať veľmi vážne, pretože to je základ bezpečnosti vašich informácií. Informácie o tom, aké požiadavky sú na kľúč kladené, a tabuľka substitúcií nájdete v časti „Požiadavky na kľúčové informácie“.

Pri zvažovaní metódy sa na to nebudeme zameriavať, pretože Tento článok, ako som už uviedol vyššie, bol napísaný s cieľom naučiť čitateľa šifrovať údaje pomocou metódy jednoduchej náhrady tohto šifrovacieho algoritmu, ale tejto problematike sa určite budeme venovať na konci článku.

Teoretické minimum.

3.1 Kľúčové informácie

Ako som už uviedol vyššie, do šifrovania údajov sa aktívne zapájajú tieto:

3.1.1. Kľúč je sekvencia ôsmich prvkov, každý po 32 bitoch. V nasledujúcom texte budeme označovať symbolom K a prvky, z ktorých pozostáva, sú k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Substitučná tabuľka - matica ôsmich riadkov a šestnástich stĺpcov, ďalej - Hij. Každý prvok v priesečníku riadka i a stĺpca j zaberá 4 bity.

3.2 Základný krok krypto transformácie

Hlavným krokom v procese šifrovania je - hlavný krok krypto transformácie. Nejde o nič iné ako o akciu na šifrovanie údajov podľa určitého algoritmu, iba vývojári predstavili názov, ktorý je príliš ťažkopádny.

Pred šifrovaním je blok rozdelený na dve časti L a R, každá po 32 bitoch. Vyberie sa kľúčový prvok a až potom sa tieto dve časti bloku, kľúčový prvok, substitučná tabuľka, zavedú do funkcie hlavného kroku, výsledkom hlavného kroku je jedna iterácia základného cyklu, o ktorej sa bude diskutovať v nasledujúci odsek. Hlavný krok pozostáva z nasledujúcich:

1. Prídavná časť bloku R sa sčíta s kľúčovým prvkom K mod 2 32. Vyššie som popísal podobnú operáciu, tu iba tá istá vec nie je „4“, ale „32“ - výsledok tejto operácie bude v budúcnosti označovaný ako Smod.
2. Rozdeľte predtým získaný výsledok Smod na štvorbitové prvky s7, s6, s5, s4, s3, s2, s1, s0 a vložte ho do náhradnej funkcie. Nahradenie je nasledovné: vyberie sa prvok Smod - si, od začiatku začíname najnižším prvkom a nahradíme hodnotou z tabuľky nahradení i - riadok a stĺpec, na ktoré ukazuje hodnota prvku s i. Prejdeme k prvku s i +1 a postupujeme rovnako a pokračujeme tak dlho, kým nezmeníme hodnotu posledného prvku Smod - výsledok tejto operácie bude označený ako Ssimple.
3. V tejto operácii posunieme hodnotu Ssimple cyklicky doľava o 11 bitov a dostaneme Srol.
4. Vyberieme druhú časť bloku L a pridáme ho mod 2 pomocou Srol, v dôsledku čoho máme Sxor.
5. V tejto fáze sa časť bloku L rovná hodnote časti R a časť R sa naopak inicializuje s výsledkom Sxor, a tým sa funkcia hlavného kroku dokončí!

3.3 Základné cykly: "32-З", "32-Р".

Na zašifrovanie informácií je potrebné ich rozdeliť na bloky s veľkosťou 64 bitov, posledný blok môže mať samozrejme menej ako 64 bitov. Táto skutočnosť je Achillovou pätou tejto metódy „jednoduchej výmeny“. Pretože jeho pridanie k 64 bitom je veľmi dôležitou úlohou na zvýšenie kryptografickej sily šifrového programu a na toto citlivé miesto, ak je prítomné v informačnom poli, ale nemusí existovať (napríklad súbor 512 bajtov! ), K jednému by sme sa mali správať s veľkou zodpovednosťou!

Po rozdelení informácií do blokov by ste mali kľúč rozdeliť na prvky:

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

Samotné šifrovanie spočíva v použití takzvaných základných cyklov. Čo zase zahŕňa n-tý počet základných krokov krypto-transformácie.

Základné cykly sú označené takto: n - m. Kde n je počet základných krokov krypto transformácie v základnom cykle, a m je „typ“ základného cyklu, t.j. o čo ide, o šifrovaní „Z“ alebo „R“ šifrovaní údajov.

Základný šifrovací cyklus 32-З pozostáva z 32 základných krokov krypto-transformácie. Blok N a prvok kľúča K sa vložia do funkcie, ktorá implementuje činnosti kroku, a prvý krok nastane s k1, druhý nad výsledkom získaným s prvkom k2 atď. podľa nasledujúcej schémy:

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

Dekódovací proces pre 32-P prebieha podobným spôsobom, ale kľúčové prvky sú uvedené v opačnom poradí:

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

Prax.

4.1 Realizácia hlavného kroku krypto transformácie

Potom, čo sme sa zoznámili s teóriou šifrovania informácií, bolo načase zistiť, ako šifrovanie funguje v praxi.

Počiatočné údaje:

Vezmite si blok informácií N = 010203040506060708h, tu sú časti L a R rovnaké:

L = 01020304h, R = 05060708h, vezmeme kľúč:

K = ' ako28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(jedná sa o kódy ASCII, na zobrazenie hexadecimálnej reprezentácie môžete tento súbor otvoriť v režime zobrazenia v programe Total Commander stlačením klávesu F3"A potom kľúč" 3 "). V tomto kľúči budú hodnoty prvkov:

k1 = „as28“, k2 = „zw37“, k3 = „q839“, k4 = „7342“

k5 = „ui23“, k6 = „8e2t“, k7 = „wqm2“, k8 = „ewp1“

Tiež si vezmite nasledujúcu tabuľku substitúcií:

Ryža. 3

Tu sú riadky očíslované od 0 do 7, stĺpce od 0 do F.

Varovanie: Všetky informácie, vrátane kľúča s tabuľkou substitúcie, slúžia ako príklad na zváženie algoritmu!

Pomocou „Počiatočných údajov“ je potrebné získať výsledok akcie hlavného kroku krypto transformácie.

1. Vyberte časť R = 05060708h a kľúčový prvok k1 = 'as28', v hexadecimálnej forme bude kľúčový prvok vyzerať takto: 61733238h. Teraz vykonáme súhrnnú operáciu mod 2 32:

Ryža. 4

Ako vidíte na obrázku, nemali sme prenos v 33 bitoch označených červenou farbou a s exponentom „ 32 “. A keby sme mali iné hodnoty R a kľúčového prvku, mohlo by sa to stať. Potom by sme to ignorovali a ďalej používali iba bity označené žltou farbou.

Túto operáciu vykonávam príkazom assembler pridať:

; eax = R, ebx = 'as28'

Výsledok tejto operácie Smod = 66793940h

2. Teraz najzložitejšia operácia, ale ak sa pozriete pozorne, už to nie je také hrozné, ako sa na prvý pohľad zdá. Predstavme si Smod nasledovne:

Ryža. 5

Pokúsil som sa vizualizovať prvky Smodu na obrázku, ale aj tak to vysvetlím:

s0 = 0, s1 = 4, s2 = 9 atď.

Teraz, počnúc najnižším prvkom s0, vykonáme výmenu. Zapamätanie si odseku „ 3.2 Základný krok krypto transformácie»I - riadok, s i - stĺpec, vyhľadajte hodnotu v nulovom riadku a nulovom stĺpci:

Obr

Aktuálna hodnota Smodu teda nie je 6679394 0 h, a 6679394 5 h.

Pokračujeme k nahradeniu s1, t.j. štyri. Pomocou prvého riadka a štvrtého stĺpca (s1 = 4!). Pozeráme sa na obrázok:

Ryža. 7

Teraz už hodnota Smodu, nie 667939 4 5h, 667939 2 5h. Predpokladám, že teraz je náhradný algoritmus čitateľovi jasný, a môžem povedať, že po konečnom výsledku Ssimple bude mať nasledujúcu hodnotu - 11e10325h.

O tom, ako je to najľahšie implementovateľné vo forme príkazov assembleru, budem hovoriť neskôr v nasledujúcom odseku, keď hovorím o rozšírenej tabuľke.

1. Výslednú hodnotu Ssimple musíme posunúť o 11 bitov doľava.

Ryža. osem

Ako vidíte, táto akcia je pomerne jednoduchá a je implementovaná jedným príkazom jazyka zostavenia - rol a výsledok tejto operácie Srol je 0819288Fh.

4. Teraz bude časť L nášho bloku informácií XOROVANÁ s hodnotou Srol. Vezmem kalkulačku z w2k sp4 a dostanem Sxor = 091b2b8bh.

5. Táto akcia je konečná a jednoducho priradíme, vyčistíme R, hodnotu L časti a inicializujeme L časť s hodnotou Sxor.

Konečný výsledok:

L = 091b2b8bh, R = 01020304h

4.2 Zvýšenie rýchlosti algoritmu

Teraz sa porozprávajme o optimalizácii algoritmu pre rýchlosť. Pri procese implementácie projektu je potrebné vziať do úvahy, že program, ktorý pracuje s registrami častejšie ako s pamäťou, funguje najrýchlejšie, a tu je tento úsudok tiež veľmi dôležitý, pretože cez jeden blok informácií až 32 šifrovacích akcií!

Keď som implementoval šifrovací algoritmus do svojho programu, urobil som nasledujúce:

1. Vybraná časť bloku L do registra eax a R do edx.

2. V registri esi inicializovanom adresou rozšíreného kľúča, viac o tom nižšie.

3. V registri ebx priradená hodnota adresy rozšírenej tabuľky substitúcií, viac o tom nižšie

4. Informácie o položkách 1, 2, 3 preniesli do funkcie základného cyklu 32 - З alebo 32 - Р, v závislosti od situácie.

Ak sa pozriete na vývojový diagram kľúčových prvkov v odseku „ Základné cykly: „32-З“, „32-Р“", Potom môže byť náš kľúč pre základný cyklus 32 - 3 reprezentovaný nasledovne:

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“

Títo. od začiatku je k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 “,„zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' táto sekvencia sa opakuje trikrát. Potom idú prvky v opačnom poradí, tj: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1“, „wqm2“, „8e2t“, „ui23“, „7342“, „q839“, „zw37“, „as28“.

Prvky som usporiadal do poľa vopred v poradí, v akom by mali byť kŕmené v 32 - Z. Tým som zvýšil potrebnú pamäť na kľúč, ale zachránil som sa pred niektorými procesmi myslenia, ktoré som nepotreboval, a zvýšil som rýchlosť. algoritmu, pretože skrátením času prístupu do pamäte! Tu som popísal iba kľúč pre 32 - З, pre cyklus 32 - Р Urobil som to isté, ale pomocou inej schémy dodávania prvkov, ktorú som tiež popísal v odseku „ Základné cykly: „32-Z“, „32-P».

Teraz je načase popísať implementáciu náhradnej funkcie, ako som sľúbil vyššie. Nedokázal som to opísať skôr, pretože to si vyžaduje zavedenie nového konceptu - rozšírenej tabuľky substitúcie. Neviem ti vysvetliť, čo to je. Namiesto toho vám to ukážem a vy sami formulujete, čo to je - rozšírená tabuľka striedaní?

Aby sme pochopili, čo je rozšírená substitučná tabuľka, potrebujeme napríklad substitučnú tabuľku, vezmem si tabuľku uvedenú na obr. 3.

Potrebovali sme napríklad nahradiť číslo 66793940h. Predstavím to nasledovne:

Ryža. deväť

Teraz, keď vezmeme prvky s1, s0, t.j. najmenej významný bajt, výsledok náhradnej funkcie bude 25 hodín! Po prečítaní článku Andreja Vinokurova, ktorý som citoval v odseku „ Zoznam použitej literatúry", V skutočnosti zistíte, že ak urobíte dva riadky, môžete získať pole, ktoré vám umožní rýchlo nájsť náhradné prvky pomocou príkazu assembler. xlat. Hovorí sa, že sa to dá urobiť aj iným spôsobom rýchlejšie, ale Andrey Vinokurov strávil asi štyri roky skúmaním rýchlych algoritmov na implementáciu GOST! Nemyslím si, že by ste mali znovu objavovať koleso, ak ho už máte.

Takže o poli:

Vezmite prvé dva riadky nula a prvý, vytvorte pole 256 bajtov. Teraz pozorujeme jednu zvláštnosť, že ak je potrebné transformovať 00h, potom bude výsledok 75h (na základe obr. 3) - túto hodnotu vložíme do poľa pri posunutí 00h. Vezmeme hodnotu 01h, výsledok substitučnej funkcie 79h, vložíme ju do poľa pri offsete 01 a tak ďalej až do 0FFh, čím získame 0FCh, ktoré vložíme do poľa pri offsete 0FFh. Získali sme teda rozšírenú substitučnú tabuľku pre prvú skupinu riadkov: prvý a nulu. Stále však existujú tri skupiny: druhá strana 2, strana 3, tretia strana 4, strana 5, štvrtá strana 6, strana 7. S týmito tromi skupinami zaobchádzame rovnako ako s prvou. Výsledkom je rozšírená tabuľka striedania!

Teraz môžeme implementovať algoritmus, ktorý vykoná výmenu. Na tento účel použijeme zdrojové kódy, ktoré Andrei Vinokurov zverejnil na svojej stránke, pozri „ Bibliografia».

lea ebx, extended_table_simple

mov eax, [zadajte číslo, ktoré má byť nahradené]

pridajte EBX, 100 h; preskočte na ďalšie dva uzly

sub ebx, 300 h; aby v budúcnosti ebx ukazovalo na tabuľku

Teraz ešte jedna funkcia, pričom predchádzajúcimi akciami sme nielen nahradili, ale tiež posunuli číslo o 8 bitov doľava! Musíme iba posunúť číslo o ďalšie 3 bity doľava:

a dostaneme výsledok operácie rol eax, 11!

K optimalizácii nemôžem dodať nič viac, jediné, čo môžem zdôrazniť, je to, čo som povedal vyššie - používajte registre častejšie ako prístup do pamäte. Myslím si, že tieto slová sú len pre začiatočníkov, skúsených a bez mojich slov to dokonale chápu.

Požiadavky na kľúčové informácie.

Ako je uvedené v článku Andreja Vinokurova, kľúč je vybraný podľa dvoch kritérií:

Kritérium pre rovnomerné rozdelenie bitov medzi hodnotami 1 a 0. Kritérium pre rovnako pravdepodobné rozdelenie bitov je obvykle Pearsonovo kritérium („chi-square“).

To znamená, že v zásade môže každý kľúč. To znamená, že keď sa vytvorí ďalší bit kľúča, pravdepodobnosť jeho inicializácie o jednu alebo nulu je 50/50!

Upozorňujeme, že kľúč pozostáva z ôsmich prvkov, každý z 32 bitov, takže v kľúči je iba 32 * 8 = 256 bitov a počet možných kľúčov je 2 256! Nepríde vám to?

Kritérium série.

Ak sa pozrieme na náš kľúč, ktorý som uviedol v odseku „ 4.1 Realizácia hlavného kroku krypto transformácie», Potom si všimnete, že platí nasledujúci zápis:

Ryža. desať

V jednej fráze by sa hodnota k 1 nemala opakovať ani v k 2, ani v žiadnom inom prvku kľúča.

To znamená, že kľúč, ktorý sme vybrali ako zváženie šifrovacieho algoritmu, plne spĺňa dve vyššie uvedené kritériá.

Teraz o výbere tabuľky substitúcií:

Teraz sa porozprávajme o tom, ako vybrať správnu substitučnú tabuľku. Hlavnou požiadavkou na výber náhradných tabuliek je fenomén „neopakovateľnosti“ prvkov, z ktorých každý má veľkosť 4 bity. Ako ste videli vyššie, každý riadok substitučnej tabuľky pozostáva z hodnôt 0h, 1h, 2h, 3h, ..., 0fh. Hlavnou požiadavkou teda je, aby každý riadok obsahoval hodnoty 0h, 1h, 2h, ..., 0fh a každú takúto hodnotu v jednej kópii. Napríklad postupnosť:

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

Plne vyhovuje tejto požiadavke, ale napriek tomu! Neodporúča sa vyberať takú sekvenciu ako reťazec. Pretože ak privádzate hodnotu na vstup funkcie, ktorá sa spolieha na takýto reťazec, získate rovnakú hodnotu na výstupe! Neveríš mi? Potom vezmite číslo 332DA43Fh a osem takýchto riadkov ako tabuľku substitúcie. Vykonajte operáciu výmeny a ubezpečujem vás, že výstup bude mať číslo 332DA43Fh! To je to isté, čo ste predložili vstupu operácie! A to nie je znak dobrej formy šifrovania, a bolo?

To bola jedna požiadavka, ďalšie kritérium hovorí, že - každý bit výstupného bloku musí byť štatisticky nezávislý od každého bitu vstupného bloku!

Ako to vyzerá jednoduchšie? A tu je príklad, ako sme napríklad vybrali z vyššie uvedeného čísla prvok s0 = 0Fh, 01111b. Pravdepodobnosť, že teraz nahradíme prvý bit jednou alebo nulou, je 0,5! Pravdepodobnosť nahradenia druhého, tretieho a štvrtého bitu každým bitom, uvažujeme oddelene, s jednotkami alebo nulami, je tiež 0, 5. Pri výbere s1 = 0Eh je pravdepodobnosť, že sme nulový bit, a to je „0“ , bude nahradený nulou alebo sa tiež rovná - 0,5! Podľa tohto kritéria teda neexistuje žiadna pravidelnosť medzi nahradením nulových bitov prvkov s0, s1! Áno, môžete nahradiť jedny, ale môžete tiež nahradiť nuly.

Na vyhodnotenie tabuľky podľa tohto kritéria môžete zostaviť tabuľku korelačných koeficientov vypočítanú podľa vzorca:

Ak p = 1, potom sa hodnota bitu j na výstupe rovná hodnote bitu i na vstupe pre akékoľvek kombinácie bitov na vstupe;

Ak p = -1, potom hodnota bitu j na výstupe je vždy inverzná voči vstupnému bitu i;

Ak p = 0, potom výstupný bit j s rovnakou pravdepodobnosťou nadobúda hodnoty 0 a 1 pre akúkoľvek pevnú hodnotu vstupného bitu i.

Zoberme si jeden riadkový príklad:

Rozoberme to na „komponenty“:

Vypočítajme jeden koeficient podľa vyššie uvedeného vzorca. Aby som pochopil, ako sa to robí, podrobnejšie vysvetlím:

Vezmeme 0 -ty bit 0 -teho čísla (0) na vstupe a 0 -ty bit 0. čísla na výstupe (1) vykonáme operáciu 0 XOR 1 = 1.

Vezmeme 0 -ty bit 1. čísla (1) na vstupe a 0 -tý bit 1. čísla na výstupe (1) vykonáme operáciu 1 XOR 1 = 0.

Na vstupe vezmeme 0. bit 2. čísla (0) a na výstupe 0 bit 2. čísla (0) vykonáme operáciu 0 XOR 0 = 0.

Na vstupe vezmeme 0 -ty bit 3. čísla (1) a na výstupe (1) 0 -bit tretieho čísla vykonáme operáciu 1 XOR 1 = 0.

Pri postupnom vykonávaní operácií XOR v tomto poradí spočítame počet všetkých nenulových hodnôt a dostaneme hodnotu 6. Preto P 00 = 1- (6/2 4-1) = 0,25. Ukázalo sa teda, že hodnota bitu 0 na výstupe sa rovná hodnote bitu 0 na vstupe v 4 prípadoch zo 16;

Konečná tabuľka kurzov:

Ako je zrejmé z tabuľky korelačných koeficientov, bit 3 na vstupe je invertovaný vzhľadom na bit 0 na výstupe v 14 prípadoch zo 16, čo je 87,5%. To už nie je prijateľné pre bežné šifrovacie systémy. Zoberme si ďalší príklad zmeny:

Tabuľka koeficientov bude nasledovná (pre koho nie je lenivé prepočítať)

V tejto tabuľke sú veci ešte horšie - bity 1 a 2 skupiny zostávajú nezmenené! Cryptanalyst sa má kde obrátiť Po zohľadnení všetkých týchto požiadaviek sa jednoduchým vyhľadaním („hlava na hlave“) našli permutačné tabuľky zodpovedajúce uvedenej teórii (dnes - 1276 kombinácií) Tu sú niektoré z nich:

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

Zoznam použitej literatúry.

1. Článok Andreja Vinokurova:

Šifrovací algoritmus GOST 28147-89, jeho použitie a implementácia

pre počítače s platformou Intel x86.

Existujú aj zdrojové kódy na implementáciu šifrovacieho algoritmu.

1. Článok Horsta Feistela:

Kryptografia a počítačová bezpečnosť.

(nájdete na rovnakej adrese ako predchádzajúci článok)

1. Ross N. Williams:

Základný sprievodca pre algoritmy na detekciu chýb CRC

Uverejnené na stránke www.wasm.ru.

Poďakovanie.

Chcel by som poďakovať všetkým návštevníkom fóra www.wasm.ru. Osobitne by som však chcel poďakovať ChS, ktorá je v súčasnosti známa ako SteelRat, pomohol mi porozumieť veciam, ktoré by som pravdepodobne nikdy nepochopil, a tiež mi pomohol pri písaní odseku: „ Kľúčové informačné požiadavky”, Hlavnú časť tohto odseku napísal on. Som tiež veľmi vďačný zamestnancovi KSTU pomenovanému po A.N. Tupolev Anikin Igor Vyacheslavovich a bol by hriech nespomenúť Chrisa Kasperskyho za to, že je a Volodya / wasm.ru za jeho pokyny. Ach, a mám to od neho. Chcem tiež poznamenať Sega-Zero / Callipso, ale to mi v mysli prinieslo matematickú džungľu.

To je možno všetko, čo by som vám chcel povedať.

Bol by som vďačný za kritiku alebo otázky súvisiace s týmto článkom alebo len za rady. Moje kontaktné údaje: [chránené e -mailom], ICQ - 337310594.

S pozdravom, Evil's Interrupt.

P.S .: Týmto článkom som sa nesnažil nikoho prevýšiť. Bol napísaný so zámerom, uľahčiť štúdium GOST, a ak máte problémy, neznamená to, že som za to vinný. Buďte rozumní a trpezliví, všetko najlepšie pre vás!

"Kým žiješ, neumieraj, pozri sa na tento svet."
Mnohí tu majú mŕtvu dušu - sú mŕtvi vo vnútri.
Ale chodia a smejú sa, nevediac, že ​​nie sú,
Neponáhľaj sa so svojou hodinou smrti, “povedala mi.

Aria, „tam hore“

1. Úvod

1. Predbežné informácie o blokových šifrách

2.1 Feistel siete.
2.2 Bloková šifra GOST 28147-89

1. Teoretické minimum

3.1 Kľúčové informácie
3.2 Hlavný krok krypto transformácie

3.3 Základné cykly:“ 32-Z” , “ 32-R” .

1. Prax

4.1 Implementácia hlavného kroku krypto transformácie
4.2 Zvýšenie rýchlosti algoritmu
5.
6. Zoznam použitej literatúry
7. Poďakovanie.

Úvod.

Tento dokument je mojím pokusom popísať metódu jednoduchej výmeny šifrovacieho algoritmu GOST 28147-89 za najjednoduchší, ale napriek tomu technicky kompetentný jazyk. Po prečítaní prvých šiestich bodov čitateľ poskytne svoj názor na to, ako som to urobil.

Aby mala moja práca väčší úžitok, odporúčam vám vyzbrojiť sa dielami autorov uvedených v zozname použitej literatúry. Odporúča sa tiež, aby kalkulačka mala funkciu na výpočet operácie. XOR od prečítanie článku predpokladá, že čitateľ má v úmysle preštudovať tento šifrovací algoritmus. Hoci je vhodný aj ako referencia, ale tento článok som napísal presne ako školiaci.

Predbežné informácie o blokových šifrách.

Predtým, ako sa pozrieme na algoritmus, musíme sa zoznámiť s históriou vzniku tohto druhu šifier. Algoritmus patrí do kategórie blokových šifier, v architektúre ktorých sú informácie rozdelené do konečného počtu blokov, pričom posledný nemusí byť úplný. Proces šifrovania prebieha v celých blokoch, ktoré tvoria šifru. Posledný blok, ak je neúplný, je niečím doplnený (nižšie poviem o nuanciách jeho dokončenia) a je šifrovaný rovnakým spôsobom ako úplné bloky. Pod šifrou mám na mysli výsledok šifrovacej funkcie pôsobiacej na určité množstvo údajov, ktoré používateľ odoslal na šifrovanie. Inými slovami, šifra je konečným výsledkom šifrovania.

História vývoja blokových šifier je spojená so začiatkom 70. rokov, keď spoločnosť IBM, uvedomujúc si potrebu ochrany informácií pri prenose údajov prostredníctvom počítačových komunikačných kanálov, zahájila vlastný výskumný program zameraný na ochranu informácií v elektronických sieťach, vrátane kryptografie.

Skupinu výskumníkov - vývojárov z IBM, ktorá začala skúmať šifrovacie systémy so symetrickou schémou použitia kľúčov, viedol Dr. Horst Feistel.

2.1 Siete Feistel

Architektúra novej metódy šifrovania, ktorú Feistel navrhol v klasickej literatúre, sa nazýva „Feistel Architecture“, ale v súčasnosti sa v ruskej a zahraničnej literatúre používa zavedenejší výraz - „Feistelova sieť“ alebo Feistelova sieť. Následne bola na tejto architektúre postavená šifra „Lucifer“ - ktorá bola neskôr publikovaná a spôsobila novú vlnu záujmu o kryptografiu vo všeobecnosti.

Myšlienka architektúry „siete Feistel“ je nasledovná: vstupný tok informácií je rozdelený na bloky s veľkosťou n bitov, kde n je párne číslo. Každý blok je rozdelený na dve časti-L a R, potom sú tieto časti zaradené do iteratívnej blokovej šifry, v ktorej je výsledok j-tého stupňa určený výsledkom predchádzajúceho stupňa j-1! Možno to ilustrovať na príklade:

Ryža. 1

Kde funkcia A je hlavným pôsobením blokovej šifry. Môže ísť o jednoduchú akciu, ako je napríklad operácia XOR, alebo môže mať zložitejší tvar ako sekvencia série jednoduchých akcií - pridanie modula, posun doľava, výmena prvku atď. Spolu tieto jednoduché akcie tvoria takzvaný - hlavný krok krypto transformácie.

Je potrebné poznamenať, že kľúčovými prvkami činnosti funkcie sú dodávka kľúčových prvkov a operácia XOR a z toho, ako dobre bola práca týchto operácií premyslená, hovorí o kryptografickej sile šifry ako celku.

Aby bola myšlienka sietí Feistel konečne jasná, zvážte najjednoduchší prípad uvedený v ryža. 1, kde vo funkcii A - budú operácie „mod 2“ („xor“), ale toto najjednoduchšie prípad, v závažnejšej situácii, napríklad skrývajúca informácie štátneho významu, funkcia A môže byť zložitejšia (pokiaľ som videl, funkcia A je skutočne veľmi zložitá):

Počiatočné údaje:

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

Získajte šifru

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

Vysvetlime svoje akcie:

1. Táto operácia je pridaním režimu 2 4. V praxi sa takáto operácia zredukuje na jednoduché sčítanie, kde musíme sčítať dve čísla a prenos na 5. číslicu ignorovať. Pretože, ak umiestnime exponenty nad číslice binárnej reprezentácie čísla, bude existovať exponent štyri nad piatou číslicou, pozrime sa na nasledujúci obrázok, ktorý ukazuje akcie našej operácie:

Ryža. 2

Tu som ukázal na exponenty šípkou, ako vidíte, výsledok mal byť 10100, ale pretože prenos je počas operácie mod 2 4 ignorovaný, dostaneme 0100.

1. Táto operácia sa v literatúre nazýva mod 2, v montážnom jazyku je implementovaná príkazom XOR... Správnejší názov je však mod 2 1. Bez tejto unikátnej operácie je len ťažko možné postaviť rýchly, ľahko implementovateľný šifrovací algoritmus a zároveň tak, aby bol stále dostatočne kryptograficky silný. Jedinečnosť tejto operácie spočíva v tom, že sama je opakom! Napríklad, ak je číslo A XOROVANÉ s číslom B, v dôsledku toho dostaneme B, v budúcnosti stačí medzi sebou reXOROVAŤ čísla B a C, aby sme získali predchádzajúcu hodnotu A!

V tejto operácii sme dostali 1010 s číslami 1110 a 0100, aby sme sa vrátili 1110, stačí znova XOR čísiel 0100 a 1010! Viac podrobností o tejto operácii nájdete v článku, ktorý je pripojený k webu. www.wasm.ru, « Základný sprievodca kAlgoritmy detekcie chýb CRC_»Autor, ktorý Ross N. Williams... V tejto práci je bod - „ 5. Binárna aritmetika bez delenia slov“. V tomto článku je popísaná operácia. xor! Volám, pretože v tomto článku je táto operácia naplánovaná tak, že čitateľ nielenže pochopí, ako táto operácia funguje, ale dokonca ju spustí. vidieť, počuť a ​​cítiť!

1. Táto akcia je potrebná, aby počas dešifrovania bolo možné zo šifry získať počiatočné hodnoty.

2.2 Bloková šifra GOST 28147-89

Šifrovací algoritmus GOST 28147 - 89 patrí do kategórie blokových šifier pracujúcich podľa architektúry vyvážených sietí Feistel, kde dve časti vybraného bloku informácií majú rovnakú veľkosť. Algoritmus bol vyvinutý v hĺbke ôsmeho oddelenia KGB, teraz sa transformoval na FAPSI a bol zakódovaný ako šifrovací štandard Ruskej federácie v roku 1989 pod ZSSR.

Aby tento spôsob algoritmu fungoval, je potrebné rozdeliť informácie do blokov s veľkosťou 64 bitov. Vygenerujte alebo zadajte do šifrovacieho systému nasledujúce kľúčové informácie: kľúč a substitučná tabuľka. Výber kľúča a substitučnej tabuľky na šifrovanie by sa mal brať veľmi vážne, pretože to je základ bezpečnosti vašich informácií. Informácie o tom, aké požiadavky sú na kľúč kladené, a tabuľka substitúcií nájdete v časti „Požiadavky na kľúčové informácie“.

Pri zvažovaní metódy sa na to nebudeme zameriavať, pretože Tento článok, ako som už uviedol vyššie, bol napísaný s cieľom naučiť čitateľa šifrovať údaje pomocou metódy jednoduchej náhrady tohto šifrovacieho algoritmu, ale tejto problematike sa určite budeme venovať na konci článku.

Teoretické minimum.

3.1 Kľúčové informácie

Ako som už uviedol vyššie, do šifrovania údajov sa aktívne zapájajú tieto:

3.1.1. Kľúč je sekvencia ôsmich prvkov, každý po 32 bitoch. V nasledujúcom texte budeme označovať symbolom K a prvky, z ktorých pozostáva, sú k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Substitučná tabuľka - matica ôsmich riadkov a šestnástich stĺpcov, ďalej - Hij. Každý prvok v priesečníku riadka i a stĺpca j zaberá 4 bity.

Hlavným krokom v procese šifrovania je - hlavný krok krypto transformácie. Nejde o nič iné ako o akciu na šifrovanie údajov podľa určitého algoritmu, iba vývojári uviedli názov príliš ťažkopádny :).

Pred šifrovaním je blok rozdelený na dve časti L a R, každá po 32 bitoch. Vyberie sa kľúčový prvok a až potom sa tieto dve časti bloku, kľúčový prvok, substitučná tabuľka, zavedú do funkcie hlavného kroku, výsledkom hlavného kroku je jedna iterácia základného cyklu, o ktorej sa bude diskutovať v nasledujúci odsek. Hlavný krok pozostáva z nasledujúcich:

1. Prídavná časť bloku R sa sčíta s kľúčovým prvkom K mod 2 32. Vyššie som popísal podobnú operáciu, tu iba tá istá vec nie je „4“, ale „32“ - výsledok tejto operácie bude v budúcnosti označovaný ako Smod.
2. Rozdeľte predtým získaný výsledok Smod na štvorbitové prvky s7, s6, s5, s4, s3, s2, s1, s0 a vložte ho do náhradnej funkcie. Nahradenie je nasledovné: vyberie sa prvok Smod - si, začneme od začiatku najnižším prvkom a nahradíme hodnotou z tabuľky nahradení i - riadok a stĺpec, na ktoré ukazuje hodnota prvku s i. Prejdeme k prvku s i +1 a postupujeme rovnako a pokračujeme tak dlho, kým nezmeníme hodnotu posledného prvku Smod - výsledok tejto operácie bude označený ako, Ssimple.
3. V tejto operácii posunieme hodnotu Ssimple cyklicky doľava o 11 bitov a dostaneme Srol.
4. Vyberieme druhú časť bloku L a pridáme ho mod 2 pomocou Srol, v dôsledku čoho máme Sxor.
5. V tejto fáze sa časť bloku L rovná hodnote časti R a časť R sa naopak inicializuje s výsledkom Sxor, a tým sa funkcia hlavného kroku dokončí!

3.3 Základné cykly: "32-З", "32-Р".

Na zašifrovanie informácií je potrebné ich rozdeliť na bloky s veľkosťou 64 bitov, posledný blok môže mať samozrejme menej ako 64 bitov. Táto skutočnosť je Achillovou pätou tejto metódy „jednoduchej výmeny“. Pretože jeho pridanie k 64 bitom je veľmi dôležitou úlohou na zvýšenie kryptografickej sily šifrového programu a na toto citlivé miesto, ak je prítomné v informačnom poli, ale nemusí existovať (napríklad súbor 512 bajtov! ), K jednému by sme sa mali správať s veľkou zodpovednosťou!

Po rozdelení informácií do blokov by ste mali kľúč rozdeliť na prvky:

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

Samotné šifrovanie spočíva v použití takzvaných základných cyklov. Čo zase zahŕňa n-tý počet základných krokov krypto-transformácie.

Základné cykly sú označené takto: n - m. Kde n je počet základných krokov krypto transformácie v základnom cykle, a m je „typ“ základného cyklu, t.j. o čo ide, o šifrovaní „Z“ alebo „R“ šifrovaní údajov.

Základný šifrovací cyklus 32-З pozostáva z 32 základných krokov krypto-transformácie. Blok N a prvok kľúča K sa vložia do funkcie, ktorá implementuje činnosti kroku, a prvý krok nastane s k1, druhý nad výsledkom získaným s prvkom k2 atď. podľa nasledujúcej schémy:

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

Dekódovací proces pre 32-P prebieha podobným spôsobom, ale kľúčové prvky sú uvedené v opačnom poradí:

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

Prax.

Potom, čo sme sa zoznámili s teóriou šifrovania informácií, bolo načase zistiť, ako šifrovanie funguje v praxi.

Počiatočné údaje:

Vezmite si blok informácií N = 010203040506060708h, tu sú časti L a R rovnaké:

L = 01020304h, R = 05060708h, vezmeme kľúč:

K = ' ako28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(jedná sa o kódy ASCII, na zobrazenie hexadecimálnej reprezentácie môžete tento súbor otvoriť v režime zobrazenia v programe Total Commander stlačením klávesu F3"A potom kľúč" 3 "). V tomto kľúči budú hodnoty prvkov:

k1 = „as28“, k2 = „zw37“, k3 = „q839“, k4 = „7342“

k5 = „ui23“, k6 = „8e2t“, k7 = „wqm2“, k8 = „ewp1“

Tiež si vezmite nasledujúcu tabuľku substitúcií:

Ryža. 3

Tu sú riadky očíslované od 0 do 7, stĺpce od 0 do F.

Varovanie: Všetky informácie, vrátane kľúča s tabuľkou substitúcie, slúžia ako príklad na zváženie algoritmu!

Pomocou „Počiatočných údajov“ je potrebné získať výsledok akcie hlavného kroku krypto transformácie.

1. Vyberieme časť R = 05060708h a kľúčový prvok k1 = 'as28', v hexadecimálnom tvare bude kľúčový prvok vyzerať takto: 61733238h. Teraz vykonáme súhrnnú operáciu mod 2 32:

Ryža. 4

Ako vidíte na obrázku, nemali sme prenos v 33 bitoch označených červenou farbou a s exponentom „ 32 “. A keby sme mali iné hodnoty R a kľúčového prvku, mohlo by sa to stať. Potom by sme to ignorovali a ďalej používali iba bity označené žltou farbou.

Túto operáciu vykonávam príkazom assembler pridať:

; eax = R, ebx = 'as28'

Výsledok tejto operácie Smod = 66793940h

1. Teraz najzložitejšia operácia, ale ak sa pozriete pozorne, už to nie je také hrozné, ako sa na prvý pohľad zdá. Predstavme si Smod nasledovne:

OBRAZ NIE JE ULOŽENÝ

Ryža. 5

Pokúsil som sa vizualizovať prvky Smodu na obrázku, ale aj tak to vysvetlím:

s0 = 0, s1 = 4, s2 = 9 atď.

Teraz, počnúc najnižším prvkom s0, vykonáme výmenu. Zapamätanie si odseku „ 3.2 Základný krok krypto transformácie»I - riadok, s i - stĺpec, vyhľadajte hodnotu v nulovom riadku a nulovom stĺpci:

Obr

Aktuálna hodnota Smodu teda nie je 6679394 0 h, a 6679394 5 h.

Pokračujeme k nahradeniu s1, t.j. štyri. Pomocou prvého riadka a štvrtého stĺpca (s1 = 4!). Pozeráme sa na obrázok:

Ryža. 7

Teraz už hodnota Smodu, nie 667939 4 5h, 667939 2 5h. Predpokladám, že teraz je náhradný algoritmus čitateľovi jasný, a môžem povedať, že po konečnom výsledku Ssimple bude mať nasledujúcu hodnotu - 11e10325h.

O tom, ako je to najľahšie implementovateľné vo forme príkazov assembleru, budem hovoriť neskôr v nasledujúcom odseku, keď hovorím o rozšírenej tabuľke.

1. Výslednú hodnotu Ssimple musíme posunúť o 11 bitov doľava.

Ryža. osem

Ako vidíte, táto akcia je pomerne jednoduchá a je implementovaná jedným príkazom jazyka zostavenia - rol a výsledok tejto operácie Srol je 0819288Fh.

1. Teraz zostáva L časť nášho bloku informácií, ktorá má byť XORovaná s hodnotou Srol. Vezmem kalkulačku z w2k sp4 a dostanem Sxor = 091b2b8bh.
2. Táto akcia je konečná a jednoducho priradíme, vyčistíme R, hodnotu L časti a inicializujeme L časť s hodnotou Sxor.

Konečný výsledok:

L = 091b2b8bh, R = 01020304h

4.2 Zvýšenie rýchlosti algoritmu

Teraz sa porozprávajme o optimalizácii algoritmu pre rýchlosť. Pri procese implementácie projektu je potrebné vziať do úvahy, že program, ktorý pracuje s registrami častejšie ako s pamäťou, funguje najrýchlejšie, a tu je tento úsudok tiež veľmi dôležitý, pretože cez jeden blok informácií až 32 šifrovacích akcií!

Keď som implementoval šifrovací algoritmus do svojho programu, urobil som nasledujúce:

1. Vybraná časť bloku L do registra eax a R do edx.
2. V registri esi inicializovanom adresou rozšíreného kľúča, viac o tom nižšie.
3. V registri ebx priradila hodnotu adresy rozšírenej tabuľky substitúcií, viac o tom nižšie
4. Prenesené informácie z položiek 1, 2, 3 do funkcie základného cyklu 32 - З alebo 32 - Р, v závislosti od situácie.

Ak sa pozriete na vývojový diagram kľúčových prvkov v odseku „ Základné cykly: „32-З“, „32-Р“", Potom môže byť náš kľúč pre základný cyklus 32 - 3 reprezentovaný nasledovne:

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“

Títo. od začiatku je k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 “,„zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' táto sekvencia sa opakuje trikrát. Potom idú prvky v opačnom poradí, tj: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1“, „wqm2“, „8e2t“, „ui23“, „7342“, „q839“, „zw37“, „as28“.

Prvky som usporiadal do poľa vopred v poradí, v akom by mali byť kŕmené v 32 - Z. Tým som zvýšil potrebnú pamäť na kľúč, ale zachránil som sa pred niektorými procesmi myslenia, ktoré som nepotreboval, a zvýšil som rýchlosť. algoritmu, pretože skrátením času prístupu do pamäte! Tu som popísal iba kľúč pre 32 - З, pre cyklus 32 - Р Urobil som to isté, ale pomocou inej schémy dodávania prvkov, ktorú som tiež popísal v odseku „ Základné cykly: „32-Z“, „32-P».

Teraz je načase popísať implementáciu náhradnej funkcie, ako som sľúbil vyššie. Nedokázal som to opísať skôr, pretože to si vyžaduje zavedenie nového konceptu - rozšírenej tabuľky substitúcie. Neviem ti vysvetliť, čo to je. Namiesto toho vám to ukážem a vy sami formulujete, čo to je - rozšírená tabuľka striedaní?

Aby sme pochopili, čo je rozšírená substitučná tabuľka, potrebujeme napríklad substitučnú tabuľku, vezmem si tabuľku uvedenú na obr. 3.

Potrebovali sme napríklad nahradiť číslo 66793940h. Predstavím to nasledovne:

OBRAZ NIE JE ULOŽENÝ

Ryža. deväť

Teraz, keď vezmeme prvky s1, s0, t.j. najmenej významný bajt, výsledok náhradnej funkcie bude 25 hodín! Po prečítaní článku Andreja Vinokurova, ktorý som citoval v odseku „ Zoznam použitej literatúry", V skutočnosti zistíte, že ak urobíte dva riadky, môžete získať pole, ktoré vám umožní rýchlo nájsť náhradné prvky pomocou príkazu assembler. xlat. Hovorí sa, že sa to dá urobiť aj iným spôsobom rýchlejšie, ale Andrey Vinokurov strávil asi štyri roky skúmaním rýchlych algoritmov na implementáciu GOST! Nemyslím si, že by ste mali znovu objavovať koleso, ak ho už máte.

Takže o poli:

Vezmite prvé dva riadky nula a prvý, vytvorte pole 256 bajtov. Teraz pozorujeme jednu zvláštnosť, že ak je potrebné transformovať 00h, potom bude výsledok 75h (na základe obr. 3) - túto hodnotu vložíme do poľa pri posunutí 00h. Vezmeme hodnotu 01h, výsledok substitučnej funkcie 79h, vložíme ju do poľa pri offsete 01 a tak ďalej až do 0FFh, čím získame 0FCh, ktoré vložíme do poľa pri offsete 0FFh. Získali sme teda rozšírenú substitučnú tabuľku pre prvú skupinu riadkov: prvý a nulu. Stále však existujú tri skupiny: druhá strana 2, strana 3, tretia strana 4, strana 5, štvrtá strana 6, strana 7. S týmito tromi skupinami zaobchádzame rovnako ako s prvou. Výsledkom je rozšírená tabuľka striedania!

Teraz môžeme implementovať algoritmus, ktorý vykoná výmenu. Na tento účel použijeme zdrojové kódy, ktoré Andrei Vinokurov zverejnil na svojej stránke, pozri „ Bibliografia».

lea ebx, extended_table_simple

mov eax, [zadajte číslo, ktoré má byť nahradené]

pridajte EBX, 100 h; preskočte na ďalšie dva uzly

sub ebx, 300 h; aby v budúcnosti ebx ukazovalo na tabuľku

Teraz ešte jedna funkcia, pričom predchádzajúcimi akciami sme nielen nahradili, ale tiež posunuli číslo o 8 bitov doľava! Musíme iba posunúť číslo o ďalšie 3 bity doľava:

a dostaneme výsledok operácie rol eax, 11!

K optimalizácii nemôžem dodať nič viac, jediné, čo môžem zdôrazniť, je to, čo som povedal vyššie - používajte registre častejšie ako prístup do pamäte. Myslím si, že tieto slová sú len pre začiatočníkov, skúsených a bez mojich slov to dokonale chápu :).

Požiadavky na kľúčové informácie.

Ako je uvedené v článku Andreja Vinokurova, kľúč je vybraný podľa dvoch kritérií:

- kritérium pre rovnomerné rozdelenie bitov medzi hodnotami 1 a 0. Kritériom pre rovnako pravdepodobné rozdelenie bitov je obvykle Pearsonovo kritérium („chi-square“).

To znamená, že v zásade môže každý kľúč. To znamená, že keď sa vytvorí ďalší bit kľúča, pravdepodobnosť jeho inicializácie o jednu alebo nulu je 50/50!

Upozorňujeme, že kľúč pozostáva z ôsmich prvkov, každý z 32 bitov, takže v kľúči je iba 32 * 8 = 256 bitov a počet možných kľúčov je 2 256! Nepríde vám to? 🙂

- kritérium série.

Ak sa pozrieme na náš kľúč, ktorý som uviedol v odseku „ 4.1 Realizácia hlavného kroku krypto transformácie», Potom si všimnete, že platí nasledujúci zápis:

Ryža. desať

V jednej fráze by sa hodnota k 1 nemala opakovať ani v k 2, ani v žiadnom inom prvku kľúča.

To znamená, že kľúč, ktorý sme vybrali ako zváženie šifrovacieho algoritmu, plne spĺňa dve vyššie uvedené kritériá.

Teraz o výbere tabuľky substitúcií:

Teraz sa porozprávajme o tom, ako vybrať správnu substitučnú tabuľku. Hlavnou požiadavkou na výber náhradných tabuliek je fenomén „neopakovateľnosti“ prvkov, z ktorých každý má veľkosť 4 bity. Ako ste videli vyššie, každý riadok substitučnej tabuľky pozostáva z hodnôt 0h, 1h, 2h, 3h, ..., 0fh. Hlavnou požiadavkou teda je, aby každý riadok obsahoval hodnoty 0h, 1h, 2h, ..., 0fh a každú takúto hodnotu v jednej kópii. Napríklad postupnosť:

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

Plne vyhovuje tejto požiadavke, ale napriek tomu! Neodporúča sa vyberať takú sekvenciu ako reťazec. Pretože ak privádzate hodnotu na vstup funkcie, ktorá sa spolieha na takýto reťazec, získate rovnakú hodnotu na výstupe! Neveríš mi? Potom vezmite číslo 332DA43Fh a osem takýchto riadkov ako tabuľku substitúcie. Vykonajte operáciu výmeny a ubezpečujem vás, že výstup bude mať číslo 332DA43Fh! To je to isté, čo ste predložili vstupu operácie! A to nie je znak dobrej formy šifrovania, a bolo? 🙂

To bola jedna požiadavka, ďalšie kritérium hovorí, že - každý bit výstupného bloku musí byť štatisticky nezávislý od každého bitu vstupného bloku!

Ako to vyzerá jednoduchšie? A tu je príklad, ako sme napríklad vybrali z vyššie uvedeného čísla prvok s0 = 0Fh, 01111b. Pravdepodobnosť, že teraz nahradíme prvý bit jednou alebo nulou, je 0,5! Pravdepodobnosť nahradenia druhého, tretieho a štvrtého bitu každým bitom, uvažujeme oddelene, s jednotkami alebo nulami, je tiež 0, 5. Pri výbere s1 = 0Eh je pravdepodobnosť, že sme nulový bit, a to je „0“ , bude nahradený nulou alebo sa tiež rovná - 0,5! Podľa tohto kritéria teda neexistuje žiadna pravidelnosť medzi nahradením nulových bitov prvkov s0, s1! Áno, môžete nahradiť jedny, ale môžete tiež nahradiť nuly. 🙂

Na vyhodnotenie tabuľky podľa tohto kritéria môžete zostaviť tabuľku korelačných koeficientov vypočítanú podľa vzorca:

- ak p = 1, potom je hodnota bitu j na výstupe rovnaká ako hodnota bitu i na vstupe pre akékoľvek kombinácie bitov na vstupe;

- ak p = -1, potom hodnota bitu j na výstupe je vždy inverzná voči vstupnému bitu i;

- ak p = 0, potom výstupný bit j s rovnakou pravdepodobnosťou nadobúda hodnoty 0 a 1 pre akúkoľvek pevnú hodnotu vstupného bitu i.

Zoberme si jeden riadkový príklad:

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

Rozoberme to na „komponenty“:

Vypočítajme jeden koeficient podľa vyššie uvedeného vzorca. Aby som pochopil, ako sa to robí, podrobnejšie vysvetlím:

- vezmeme 0 -ty bit 0 -teho čísla (0) na vstupe a 0 -ty bit 0. čísla na výstupe (1) vykonáme operáciu 0 XOR 1 = 1.

- na vstupe vezmeme 0 -ty bit 1. čísla (1) a na výstupe (0) 0 -bit 1. čísla vykonáme operáciu 1 XOR 1 = 0.

- na vstupe vezmeme 0 -ty bit 2. čísla (0) a na výstupe 0 -bit 2. čísla (0) vykonáme operáciu 0 XOR 0 = 0.

- na vstupe vezmeme 0. bit tretieho čísla (1) a na výstupe (0) 0. bit 3. čísla vykonáme operáciu 1 XOR 1 = 0.

Pri postupnom vykonávaní operácií XOR v tomto poradí spočítame počet všetkých nenulových hodnôt a dostaneme hodnotu 6. Preto P 00 = 1- (6/2 4-1) = 0,25. Ukázalo sa teda, že hodnota bitu 0 na výstupe sa rovná hodnote bitu 0 na vstupe v 4 prípadoch zo 16;

Konečná tabuľka kurzov:

Tabuľka koeficientov bude nasledovná (pre koho nie je lenivé prepočítať)

	vchod
Výkon		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

V tejto tabuľke sú veci ešte horšie - bity 1 a 2 skupiny zostávajú nezmenené! Kryptanalytik sa má kam obrátiť 🙂 Vzhľadom na všetky tieto požiadavky sa jednoduchým vyhľadaním („hlava na hlave“) našli permutačné tabuľky zodpovedajúce uvedenej teórii (dnes - 1276 kombinácií) Tu sú niektoré z nich:

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

Zoznam použitej literatúry.

1. Článok Andreja Vinokurova:

Šifrovací algoritmus GOST 28147-89, jeho použitie a implementácia

pre počítače s platformou Intel x86.

(nájdete na: http://www.enlight.ru/crypto/frame.htm).

Existujú aj zdrojové kódy na implementáciu šifrovacieho algoritmu.

1. Článok Horsta Feistela:

Kryptografia a počítačová bezpečnosť.

(nájdete na rovnakej adrese ako predchádzajúci článok)

1. Ross N. Williams:

Základný sprievodca pre algoritmy na detekciu chýb CRC

Uverejnené na stránke www.wasm.ru.

Poďakovanie.

Chcel by som poďakovať všetkým návštevníkom fóra www.wasm.ru. Osobitne by som však chcel poďakovať ChS, ktorá je v súčasnosti známa ako SteelRat, pomohol mi porozumieť veciam, ktoré by som pravdepodobne nikdy nepochopil, a tiež mi pomohol pri písaní odseku: „ Kľúčové informačné požiadavky”, Hlavnú časť tohto odseku napísal on. Som tiež veľmi vďačný zamestnancovi KSTU pomenovanému po A.N. Tupolev Anikin Igor Vyacheslavovich a bol by hriech nespomenúť Chrisa Kasperskyho za to, že je a Volodya / wasm.ru za jeho pokyny. Aha, a mám to od neho :). Chcem tiež poznamenať Sega-Zero / Callipso, ale to mi v mysli prinieslo matematickú džungľu.

To je možno všetko, čo by som vám chcel povedať.

Bol by som vďačný za kritiku alebo otázky súvisiace s týmto článkom alebo len za rady. Moje kontaktné údaje: [chránené e -mailom], ICQ - 337310594.

S pozdravom, Evil's Interrupt.

P.S .: Týmto článkom som sa nesnažil nikoho prevýšiť. Bol napísaný so zámerom, uľahčiť štúdium GOST, a ak máte problémy, neznamená to, že som za to vinný. Buďte rozumní a trpezliví, všetko najlepšie pre vás!

Tento algoritmus je povinný používať ako šifrovací algoritmus v štátnych organizáciách Ruskej federácie a v mnohých komerčných.

Popis algoritmu

Algoritmický diagram je znázornený na obr. 3.1. Ako vidíte, schéma tohto algoritmu je pomerne jednoduchá, čo jednoznačne zjednodušuje jeho softvérovú alebo hardvérovú implementáciu.

Algoritmus GOST 28147-89 šifruje informácie v blokoch so 64 bitmi, ktoré sú rozdelené do dvoch subblokov s 32 bitmi (N1 a N2). Subblok N1 je spracovaný určitým spôsobom, po ktorom je pridaná jeho hodnota

s hodnotou subbloku N2 (sčítanie sa vykonáva modulo 2), potom sa subbloky vymenia. Takáto transformácia sa vykonáva pre určitý počet kôl: 16 alebo 32 v závislosti od režimu činnosti algoritmu (popísaného nižšie). V každom kole sa vykonávajú tieto operácie:

1. Prekrytie kľúča. K obsahu subbloku / VI je pridaný modul 2 32 s časťou kľúča Kx.

Šifrovací kľúč algoritmu GOST 28147-89 má rozmer 256 bitov a Kx je jeho 32-bitová časť, to znamená, že 256-bitový šifrovací kľúč je reprezentovaný ako zreťazenie 32-bitových podkľúčov (obr. 3.2) :

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

V procese šifrovania sa používa jeden z týchto podkľúčov v závislosti od zaokrúhleného čísla a režimu činnosti algoritmu.

Ryža. 3.1. Schéma algoritmu GOST 28147-

Ryža. 3.2. Šifrovací kľúč algoritmu GOST 28147-89

2. Tabuľková náhrada. Po vložení kľúča je subblok / VI rozdelený na 8 častí po 4 bity, pričom hodnota každého z nich je individuálne nahradená v súlade s náhradnou tabuľkou pre túto časť subbloku. Substitučné boxy (S-boxy) sa často používajú v moderných šifrovacích algoritmoch, preto stojí za to ich zvážiť podrobnejšie.

Tabuľková náhrada sa používa týmto spôsobom: blok údajov určitej dimenzie (v tomto prípade 4-bitový) sa privádza na vstup, ktorého číselné zobrazenie určuje číslo výstupnej hodnoty. Máme napríklad S-box nasledujúceho tvaru:

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

Nechajte 4-bitový blok „0100“ prísť na vstup, to znamená na hodnotu 4. Podľa tabuľky bude výstupná hodnota 15, to znamená. „1111“ (0 sa nahradí 4, 1 sa nahradí 11, hodnota 2 sa nezmení atď.).

Ako vidíte, schéma algoritmu je veľmi jednoduchá, čo znamená, že najväčšie zaťaženie šifrovania údajov pripadá na náhradné tabuľky. Algoritmus má bohužiaľ tú vlastnosť, že existujú „slabé“ substitučné tabuľky, pri ktorých použití je možné algoritmus odhaliť kryptanalytickými metódami. K slabým patrí napríklad tabuľka, v ktorej sa výstup rovná vstupu:

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

3. Bitový cyklický posun doľava o 11 bitov.

Režimy prevádzky algoritmu

Algoritmus GOST 28147-89 má 4 prevádzkové režimy:

□ jednoduchý režim výmeny;

□ režim gama;

Režim P gama so spätnou väzbou;

□ spôsob výroby simulátorov.

Tieto režimy sa trochu líšia od všeobecne akceptovaných (popísaných v časti 1.4), preto stojí za to ich zvážiť podrobnejšie.

Tieto režimy majú rôzne účely, ale používajú rovnakú transformáciu šifrovania, ako je popísané vyššie.

Jednoduchý režim výmeny

V režime jednoduchej výmeny sa 32 kôl opísaných vyššie jednoducho vykoná na šifrovanie každého 64-bitového bloku informácií. 32-bitové podkľúče sa používajú v nasledujúcom poradí:

□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI atď. - v 1. až 24. kole;

□ K1, Kb, K5, K4, KZ, K2, K \, KO - v kolách od 25. do 32.

Dešifrovanie v režime jednoduchej výmeny sa vykonáva úplne rovnakým spôsobom, ale s mierne odlišnou postupnosťou podkľúčov:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - v kolách od 1 do 8;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb atď. - v kolách od 9. do 32. miesta.

Podobne ako v štandardnom režime ECB, kvôli oddelenému šifrovaniu blokov sa od jednoduchého náhradného režimu dôrazne neodporúča šifrovať samotné údaje; mal by sa používať iba na šifrovanie iných šifrovacích kľúčov vo viackľúčových schémach.

Režim gama

V režime gama (obr. 3.3) sa ku každému bloku holého textu pridá bitovo modul 2 so 64-bitovým šifrovacím blokom gama. Gama šifry je špeciálna sekvencia, ktorá sa generuje pomocou vyššie opísaných transformácií:

1. V registroch N1 a N2 je zapísané ich počiatočné naplnenie - 64 -bitová hodnota nazývaná „sync burst“ (synchro burst je prakticky analogický s inicializačným vektorom v režimoch CBC, CFB a OFB).

2. Šifrovanie obsahu registrov / VI a N2 (v tomto prípade - synchronizačné správy) sa vykonáva v jednoduchom náhradnom režime.

3. K obsahu N1 sa pridá modulo (2 32 - 1) s konštantou CI = 2 24 + 2 16 + 2 8 + 4, výsledok pridania sa zapíše do registra / VI.

4. K obsahu N2 sa pridá modulo 2 s konštantou C2 = 2 24 + 2 16 + 2 8 +1, výsledok sčítania sa zapíše do registra N2.

5. Obsah registrov / VI a N2 je vyvedený ako 64-bitový šifrovací gama blok (tj. V tomto prípade / VI a N2 tvoria prvý gama blok).

6. Ak je potrebný ďalší blok gama (tj. Musíte pokračovať v šifrovaní alebo dešifrovaní), vráťte sa na krok 2.

Na dešifrovanie sa gama generuje podobným spôsobom, potom sa operácia XOR opäť aplikuje na šifrový text a gama bity.

Na vygenerovanie rovnakého spektra šifier musí užívateľ dešifrovať kryptogram mať rovnaký kľúč a rovnakú hodnotu synchrónnych správ, aké boli použité na šifrovanie informácií. V opačnom prípade nebude možné získať pôvodný text zo šifrovaného.

Vo väčšine implementácií algoritmu GOST 28147-89 nie je synchronizačná správa tajným prvkom, synchronizačná správa však môže byť rovnako tajná ako šifrovací kľúč. V tomto prípade môžeme predpokladať, že efektívna dĺžka kľúča algoritmu (256 bitov) sa zvýši o ďalších 64 bitov synchronizačnej správy, čo možno považovať za ďalší kľúčový prvok.

Režim gama so spätnou väzbou

V režime gama so spätnou väzbou sa ako vyplnenie registrov / VI a L / 2, počnúc od 2. bloku, nepoužije predchádzajúci blok gama, ale výsledok šifrovania predchádzajúceho bloku obyčajného textu (obr. 3.4) . Prvý blok v tomto režime je generovaný úplne podobne ako predchádzajúci.

Ryža. 3.4. Generovanie šifry gama v režime spätnej väzby gama

Spôsob výroby simulátora

Predpona je kryptografický kontrolný súčet vypočítaný pomocou šifrovacieho kľúča na overenie integrity správ. Na jeho výpočet existuje špeciálny režim algoritmu GOST 28147-89.

Generovanie simulátora sa vykonáva nasledovne:

1. Prvý 64-bitový informačný blok, pre ktorý je vypočítaná predpona, je zapísaný do registrov N1 a N2 a zašifrovaný v redukovanom režime jednoduchej náhrady, v ktorom sa vykoná prvých 16 kôl z 32.

2. Získaný výsledok sa sčíta modulo 2 s ďalším blokom informácií, pričom výsledok sa uloží do N1 a N2.

3. M a N2 sú opäť šifrované v redukovanom režime jednoduchej výmeny a tak ďalej až do posledného bloku informácií.

Imitátor je 64-bitový výsledný obsah registrov N1 a N2 alebo ich časti. Používa sa najčastejšie 32-bitová predpona, to znamená polovica obsahu registra. To je dosť, pretože ako každý kontrolný súčet je simulátor určený predovšetkým na ochranu pred náhodným skreslením informácií. Na ochranu pred zámernou úpravou údajov sa používajú iné kryptografické metódy - predovšetkým elektronický digitálny podpis (pozri časť 1.1).

Imitátor sa používa nasledovne:

1. Pri šifrovaní akýchkoľvek informácií sa vypočíta predpona holého textu a odošle sa spolu so šifrovacím textom.

2. Po dešifrovaní sa predpona znova vypočíta a porovná s odoslaným.

3. Ak sa vypočítané a odoslané predpony nezhodujú - šifrový text bol pri prenose skreslený alebo boli počas dešifrovania použité nesprávne kľúče.

Predpona je obzvlášť užitočná na overenie správneho dešifrovania kľúčových informácií pri použití viackľúčových schém.

Imitátor je nejaký analóg autentifikačného kódu MAC správy vypočítanej v režime CBC; rozdiel je v tom, že synchronizačná správa sa nepoužíva na výpočet predpony, zatiaľ čo inicializačný vektor sa používa na výpočet MAC.

Kryptografická sila algoritmu

V roku 1994 bol popis algoritmu GOST 28147-89 preložený do angličtiny a publikovaný; potom sa začali objavovať výsledky jeho analýzy vykonanej zahraničnými odborníkmi; však už značnú dobu neboli zistené žiadne útoky, ktoré by sa blížili k uskutočniteľnosti.

□ veľká dĺžka kľúča - 256 bitov; spolu so správou tajnej synchronizácie sa efektívna dĺžka kľúča zvýši na 320 bitov;

□ 32 kôl transformácií; po 8 kolách sa dosiahne plný účinok rozptýlenia vstupných údajov: zmena jedného bitu bloku holého textu ovplyvní všetky bity bloku šifrového textu a naopak, to znamená, že existuje viacnásobná bezpečnostná rezerva.

Zvážte výsledky kryptoanalýzy algoritmu GOST 28147-89.

Analýza náhradných tabuliek

Pretože substitučné tabuľky nie sú v norme uvedené, množstvo prác (napríklad c) naznačuje, že „kompetentná organizácia“ môže vyrábať „dobré“ aj „zlé“ substitučné tabuľky. Slávny odborník Bruce Schneier však takéto predpoklady nazýva „fámy“. Je zrejmé, že kryptografická sila algoritmu do značnej miery závisí od vlastností použitých náhradných tabuliek; podľa toho existujú slabé náhradné tabuľky (pozri príklad vyššie), ktorých použitie môže zjednodušiť útok na algoritmus. Napriek tomu sa možnosť použitia rôznych substitučných tabuliek javí ako veľmi hodný nápad, v prospech ktorého je možné citovať dve skutočnosti z histórie šifrovacieho štandardu DES (podrobnosti nájdete v časti 3.15):

□ útoky využívajúce lineárnu aj diferenciálnu kryptoanalýzu algoritmu DES používajú špecifické vlastnosti náhradných tabuliek; pri použití iných tabuliek bude musieť kryptoanalýza začať odznova;

□ boli urobené pokusy posilniť DES proti lineárnej a diferenciálnej kryptoanalýze použitím robustnejších substitučných tabuliek; také tabuľky, ktoré sú skutočne robustnejšie, boli navrhnuté napríklad v algoritme s 5 DES; ale bohužiaľ nebolo možné nahradiť DES s 5 DES, pretože náhradné tabuľky sú v štandarde prísne definované, respektíve implementácia algoritmu pravdepodobne nepodporuje schopnosť meniť tabuľky na iné.

V mnohých prácach (napríklad a) sa mylne uvádza, že tajné tabuľky substitúcií algoritmu GOST 28147-89 môžu byť súčasťou kľúča a predĺžiť jeho efektívnu dĺžku (čo je bezvýznamné, pretože algoritmus má veľmi veľký 256-bitový kľúč). Práca však ukázala, že tajné substitučné tabuľky je možné vypočítať pomocou nasledujúceho útoku, ktorý je možné uplatniť v praxi:

1. Nastaví sa nulovací kľúč a vykoná sa hľadanie „nulového vektora“, to znamená hodnôt z = / (0), kde / () je funkciou zaokrúhľovania algoritmu. Táto fáza trvá asi 2 operácie šifrovania.

2. Pomocou nulového vektora sa vypočítajú hodnoty substitučných tabuliek, ktoré netrvajú viac ako 2 11 operácií.

Úpravy algoritmov a ich analýza

Práca vykonala kryptoanalýzu modifikácií algoritmu GOST 28147-89:

Algor algoritmus GOST-H, v ktorom sa v porovnaní s pôvodným algoritmom zmení poradie použitia podkľúčov, konkrétne v cykloch 25 až 32 sa podkľúče používajú v priamom poradí, to znamená rovnakým spôsobom ako v predchádzajúce kolá algoritmu;

□ 20-kruhový algoritmus GOST®, ktorý používa XOR na použitie kľúča namiesto pridávania modulo 32.

Na základe výsledkov analýzy sa dospelo k záveru, že GOST-H a GOST © sú slabšie ako pôvodný algoritmus GOST 28147-89, pretože oba majú triedy slabých kľúčov. Stojí za zmienku, že v časti kryptoanalýzy GOST © práca slovo za slovom opakuje časť venovanú kryptoanalýze algoritmu GOST 28147-89, publikovanej v roku 2000 známym dielom (bez akýchkoľvek odkazov na originál). . To vyvoláva pochybnosti o profesionalite autorov diela a ostatných jeho výsledkov.

V práci je navrhnutá veľmi zaujímavá modifikácia algoritmu: tabuľky S \ ... Ss musia byť odlišné; v každom kole algoritmu musia byť usporiadané podľa určitého zákona. Táto permutácia môže byť závislá od šifrovacieho kľúča alebo môže byť tajná (to znamená, že môže byť súčasťou šifrovacieho kľúča väčšia ako pôvodný 256-bitový kľúč). Obe tieto možnosti podľa ich autorov výrazne zvyšujú odolnosť algoritmu voči lineárnej a diferenciálnej kryptanalýze.

V práci je uvedená ešte jedna modifikácia týkajúca sa substitučných tabuliek, ktorá analyzuje jednu z možných metód výpočtu substitučných tabuliek na základe šifrovacieho kľúča. Autori práce dospeli k záveru, že takáto závislosť oslabuje algoritmus, pretože vedie k prítomnosti slabých kľúčov a k niektorým potenciálnym zraniteľnostiam algoritmu.

Úplná analýza algoritmov

Existujú útoky na úplný GOST 28147-89 bez akýchkoľvek úprav. Jeden z prvých otvorených dokumentov analyzujúcich algoritmus, známy dokument, je venovaný útokom, ktoré využívajú slabiny postupu rozšírenia kľúča mnohých známych šifrovacích algoritmov. Konkrétne, úplný algoritmus GOST 28147-89 je možné prelomiť pomocou diferenciálnej kryptoanalýzy na prepojených kľúčoch, ale iba vtedy, ak sa použijú slabé substitučné tabuľky. 24-kruhový variant algoritmu (ktorému chýba prvých 8 kôl) sa otvára rovnakým spôsobom pre všetky substitučné tabuľky, ale silné substitučné tabuľky (napríklad zobrazené na písmene c) robia takýto útok úplne nepraktickým.

Domáci vedci A. G. Rostovtsev a E. B. Makhovenko v roku 2001 vo svojej práci navrhli zásadne novú metódu kryptoanalýzy (podľa autorov je oveľa efektívnejšia ako lineárna a diferenciálna kryptoanalýza) vytvorením objektívnej funkcie zo známeho holého textu, ktorý mu zodpovedá šifrovacím a požadovanú kľúčovú hodnotu a nájdenie jej extrému zodpovedajúceho skutočnej kľúčovej hodnote. Našli tiež veľkú triedu slabých kľúčov algoritmu GOST 28147-89, ktoré umožňujú prelomiť algoritmus iba pomocou 4 vybraných obyčajných textov a zodpovedajúcich šifrových textov s pomerne nízkou komplexnosťou. V práci pokračuje kryptoanalýza algoritmu.

V roku 2004 skupina špecialistov z Kórey navrhla útok, pomocou ktorého je pomocou diferenciálnej kryptoanalýzy na prepojených kľúčoch možné získať s 91,7% pravdepodobnosťou 12 bitov tajného kľúča. Útok vyžaduje 2 35 vybraných holých textov a 2 36 šifrovacích operácií. Ako vidíte, tento útok je prakticky nepoužiteľný pre skutočný útok na algoritmus.

Algoritmus GOST 28147-89 a šifra „Magma“ (GOST R 34.12-2015)

Všeobecná schéma algoritmu. Algoritmus opísaný v GOST 28147-89 „Systémy na spracovanie informácií. Kryptografická ochrana. Kryptografický transformačný algoritmus “je domáci štandard pre symetrické šifrovanie (pred 1. januárom 2016) a je povinný na implementáciu do certifikovaných nástrojov na ochranu kryptografických informácií používaných v štátnych informačných systémoch a v niektorých prípadoch aj v komerčných systémoch. Certifikácia prostriedkov kryptografickej ochrany informácií je potrebná na ochranu informácií predstavujúcich štátne tajomstvo Ruskej federácie a informácií, ktorých dôvernosť je potrebné zabezpečiť v súlade s platnými právnymi predpismi. Aj v Ruskej federácii sa na ochranu bankových informačných systémov odporúča použiť algoritmus GOST 28147-89.

Algoritmus GOST 28147-89 (obr. 2.21) je založený na Feistelovej schéme a šifruje informácie v blokoch so 64 bitmi, ktoré sú rozdelené do dvoch subblokov s 32 bitmi (I a R). Subblok R, je spracovaná funkciou okrúhlej transformácie, po ktorej sa jeho hodnota pripočíta k hodnote podbloku Lj, potom sa podbloky prehodia. Algoritmus má 16 alebo 32 kôl, v závislosti od režimu šifrovania (výpočet vloženia imitácie alebo iné režimy šifrovania).

Ryža. 2.21.

V každom kole algoritmu sa vykonajú nasledujúce transformácie.

1. Prekrytie kľúča. Obsah podbloku RI pridané modulo 2 32 s okrúhlym kľúčom K. Kj je 32-bitová časť pôvodného kľúča používaná ako okrúhla. Algoritmus GOST 28147-89 ns používa postup rozšírenia kľúča, pôvodný 256-bitový šifrovací kľúč je reprezentovaný ako zreťazenie (zreťazenie) ôsmich 32-bitových podkľúčov (obr. 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

Proces šifrovania používa jeden z týchto podkľúčov TO

Od 1. do 24. kola - v priamom poradí:

Od 25. do 32. kola - v opačnom poradí:

Ryža. 2.22. Štruktúra šifrovacieho kľúča algoritmu GOST 28147-89

2. Tabuľková náhrada. Potom, čo bol kľúč použitý, sub-blok RI je rozdelený na osem častí, ale 4 bity, pričom hodnota každej z nich je individuálne nahradená v súlade s tabuľkou náhrad (S-box). Používa sa celkom osem S -boxov - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Každý S-box algoritmu GOST 28147-89 je vektor (jednorozmerné pole) s ^ prvkami očíslovanými od 0 do 15. Hodnoty S-boxu sú 4-bitové čísla; celé čísla od 0 do 15.

Prvok je prevzatý z tabuľky S-boxu, ktorého poradové číslo sa zhoduje s hodnotou, ktorá prišla na vstup substitúcie.

Príklad 2.6.

Nech je blok S v nasledujúcom tvare:

Vstupu tohto S-boxu nech je daná hodnota 0100 2 = 4. Výstupom S-boxu bude 4. prvok substitučnej tabuľky, tj. 15 = 1111 2 (prvky sú očíslované od nuly).

substitučné osoby nie sú štandardom definované, ako sa to robí napríklad v šifre DES. Vymeniteľné hodnoty substitučných tabuliek značne komplikujú kryptoanalýzu algoritmu. Robustnosť algoritmu zároveň výrazne závisí od ich správneho výberu.

Algoritmus GOST 28147-89 má bohužiaľ „slabé“ substitučné tabuľky, pri ktorých použití je možné algoritmus celkom ľahko odhaliť kryptanalytickými metódami. Medzi „slabé“ patrí napríklad triviálna tabuľka substitúcií, v ktorej sa vstup rovná výstupu (tabuľka 2.16).

Tabuľka 2.16

Príklad slabého S-boxu

Verí sa, že konkrétne hodnoty náhradných tabuliek by mali byť utajené a sú dlhodobým kľúčovým prvkom, t.j. sú platné oveľa dlhšie ako jednotlivé kľúče. Tajné hodnoty náhradných tabuliek však nie sú súčasťou kľúča a nemôžu predĺžiť jeho efektívnu dĺžku.

Tajné substitučné tabuľky je možné vypočítať pomocou nasledujúceho útoku, ktorý je možné uplatniť v praxi:

• nastaví sa nulový kľúč a vykoná sa hľadanie „nulového vektora“, t.j. význam z = F ( 0), kde F - funkcia kruhovej transformácie algoritmu. To vyžaduje asi 2 32 operácií testovacieho šifrovania;
• pomocou nulového vektora sa vypočítajú hodnoty substitučných tabuliek, ktoré netrvajú viac ako 2 11 operácií.

Avšak aj keď je narušená dôvernosť substitučných tabuliek, sila šifry zostáva extrémne vysoká a neklesá pod prípustnú hranicu.

Tiež sa predpokladá, že substitučné tabuľky sú spoločné pre všetky šifrovacie uzly v rámci rovnakého systému kryptografickej ochrany.

Vylepšenie štruktúry S-boxov je jedným z najintenzívnejšie skúmaných problémov v oblasti symetrických blokových šifier. V zásade sa požaduje, aby sa všetky zmeny na vstupoch S-boxov vyliali do náhodný zdanlivo meniaci výstup. Na jednej strane, čím sú S-boxy väčšie, tým je algoritmus odolnejší voči metódam lineárnej a diferenciálnej kryptanalýzy. Na druhej strane je veľký náhradný stôl ťažšie navrhnúť.

V moderných algoritmoch sú S-boxy obvykle vektorom (jednorozmerné pole) obsahujúcim 2 "t- bitové prvky. Blokový vstup definuje číslo prvku, ktorého hodnota slúži ako výstup S-bloku.

Pre návrh S-boxov bolo predložených niekoľko kritérií. Tabuľka substitúcie musí spĺňať:

• prísne lavínové kritérium;
• kritérium nezávislosti bitov;
• požiadavka na nelinearitu zo vstupných hodnôt.

Aby sa splnila posledná požiadavka, bolo navrhnuté špecifikovať lineárnu kombináciu i bity ( i = 1, ..., T) hodnoty substitučnej tabuľky ohnuté funkcie(angl., ohnutý - odchýlka, v tomto prípade - od lineárnych funkcií). Ohnuté funkcie tvoria špeciálnu triedu booleovských funkcií charakterizovaných najvyššou triedou nelinearity a súladom s prísnym lavínovým kritériom.

V niektorých prácach sa pre S-boxy navrhuje skontrolovať splnenie zaručeného lavínového efektu poradia y-keď sa zmení jeden vstupný bit, zmenia sa aspoň výstupné bity S-boxu. Vlastnosť zaručeného lavínového účinku rádu y od 2 do 5 poskytuje dostatočne dobré difúzne charakteristiky S-boxov pre akýkoľvek šifrovací algoritmus.

Pri navrhovaní dostatočne veľkých náhradných tabuliek je možné použiť nasledujúce prístupy:

• náhodný výber (pre malé S-boxy to môže viesť k vytvoreniu slabých substitučných tabuliek);
• náhodný výber, po ktorom nasleduje kontrola súladu s rôznymi kritériami a odmietnutie slabých S-boxov;
• manuálny výber (príliš pracný pre veľké bloky S);
• matematický prístup, napríklad generovanie pomocou ohnutých funkcií (tento prístup sa používa v algoritme CAST).

Na navrhovanie jednotlivých blokov S algoritmu GOST 28147-89 je možné navrhnúť nasledujúci postup:

• každý S-box môže byť opísaný štyrmi logickými funkciami, každá z funkcií musí mať štyri logické argumenty;
• tieto funkcie musia byť dostatočne komplexné. Túto požiadavku zložitosti nie je možné formálne vyjadriť, ale ako nevyhnutnú podmienku je možné požadovať, aby zodpovedajúce logické funkcie napísané v minimálnej forme (tj s minimálnou možnou dĺžkou výrazu) používajúce základné logické operácie neboli kratšie ako určitá požadovaná hodnota;
• jednotlivé funkcie, dokonca používané v rôznych substitučných tabuľkách, sa musia navzájom dostatočne líšiť.

V roku 2011 bol navrhnutý nový útočný „reflexný stret uprostred“, ktorý mierne znižuje odpor GOST 28147-89 (z 2256 na 2225). Najlepším výsledkom kryptoanalýzy algoritmu z roku 2012 je zníženie jeho sily na 2 192, čo si vyžaduje relatívne veľkú veľkosť šifrového textu a objem vopred vytvorených údajov. Napriek navrhovaným útokom zostáva GOST 28147-89 na súčasnej úrovni rozvoja počítačovej technológie prakticky stabilný.

Kód „Magma“ (GOST R 34.12-2015). Norma GOST 28147-89 platí v Rusku viac ako 25 rokov. Počas tejto doby ukázal dostatočnú trvanlivosť a dobrú účinnosť softvérových a hardvérových implementácií, vrátane implementácií na zariadeniach s nízkymi zdrojmi. Napriek tomu, že boli navrhnuté kryptoanalytické útoky, ktoré znižujú odhady jeho odolnosti (najlepšie na 2 192), zďaleka nie sú uskutočniteľné. Preto bolo rozhodnuté zahrnúť algoritmus GOST 28147-89 do novo vyvinutého štandardu symetrického šifrovania.

V obchode 2015 boli prijaté dve nové národné kryptografické normy: GOST R 34.12-2015 „Informačné technológie. Ochrana kryptografických informácií. Blokové šifry “a GOST R 34.13-2015„ Informačné technológie. Ochrana kryptografických informácií. Prevádzkové režimy blokových šifier “, ktoré nadobúdajú účinnosť 1. januára 2016.

Štandard GOST R 34.12-2015 obsahuje popis dvoch blokových šifier s dĺžkou bloku 128 a 64 bitov. Šifra GOST 28147-89 s pevnými nelineárnymi substitučnými blokmi je v novom GOST R 34.12-2015 zahrnutá ako 64-bitová šifra s názvom „Magma“.

Nasledujú náhradné bloky upevnené v štandarde:

Sada S-boxov uvedených v norme poskytuje najlepšie vlastnosti, ktoré určujú odolnosť kryptoalgoritmu voči diferenciálnej a lineárnej kryptanalýze.

Podľa technickej komisie pre normalizáciu „Zabezpečenie kryptografických informácií“ (TC 26), vďaka fixácii nelineárnych substitučných blokov bude algoritmus GOST 28147-89 zjednotenejší a pomôže eliminovať používanie „slabých“ nelineárnych substitučných blokov. Fixácia v štandarde všetkých dlhodobých parametrov šifry navyše spĺňa uznávanú medzinárodnú prax. Nová norma GOST R 34.12-2015 je terminologicky a koncepčne prepojená s medzinárodnými normami ISO / IEC 10116 „Informačné technológie. Metódy zabezpečenia. Prevádzkové režimy pre „-bitové blokové šifry“ (ISO / IEC 10116: 2006 Informačná technológia - Bezpečnostné techniky - Prevádzkové režimy pre n -bitovú blokovú šifru) a ISO / IEC 18033 séria „Informačné technológie. Metódy a prostriedky zaistenia bezpečnosti. Šifrovacie algoritmy ": ISO / IEC 18033-1: 2005" Časť 1. Všeobecné "(ISO / IEC 18033-1: 2005 Informačné technológie - Bezpečnostné techniky - Šifrovacie algoritmy - Časť 1: Všeobecné) a ISO / IEC 18033-3: 2010 „Časť 3. Blokové šifry“ (ISO / IEC 18033-3: 2010 (Informačné technológie - Bezpečnostné techniky - Šifrovacie algoritmy - Časť 3: Blokové šifry)).

Štandard GOST P 34.12-2015 tiež obsahuje novú blokovú šifru („Grasshopper“) s veľkosťou bloku 128 bitov. Očakáva sa, že táto šifra bude odolná voči všetkým dnes známym útokom na blokové šifry.

Režimy činnosti blokových šifier (jednoduchá náhrada, gama, gama s výstupnou spätnou väzbou, gama so šifrovou textovou spätnou väzbou, jednoduchá náhrada za zapojenie a generovanie imitácie vložky) sú zahrnuté v samostatnej norme GOST R 34.13-2015, ktorá zodpovedá uznávaná medzinárodná prax. Tieto režimy sú použiteľné pre šifru Magma aj pre novú šifru Grasshopper.

• Vykonáva sa bitový kruhový posun doľava o 11 bitov. Dešifrovanie sa vykonáva podľa rovnakej schémy, ale s iným kľúčovým plánom použitia: od 1. do 8. kola dešifrovania - v priamom poradí: od 9. do 32. kola dešifrovania - v opačnom poradí: V porovnaní s Šifra DES v GOST 28147-89 má nasledujúce výhody: výrazne dlhší kľúč (256 bitov oproti 56 pre šifru DES), útok, na ktorý sa v súčasnosti zdá vyčíslenie sady kľúčov hrubou silou nemožné; jednoduchý rozvrh použitia kľúča, ktorý zjednodušuje implementáciu algoritmu a zvyšuje rýchlosť výpočtov. Návrh blokov S GOST 28147-89. Je zrejmé, že schéma algoritmu GOST 28147-89 je veľmi jednoduchá. To znamená, že najväčšie zaťaženie šifrovaním pripadá na substitučné tabuľky. Hodnoty tabulátora
• Šifrovacie algoritmy Panasepko S.P.: špeciálna príručka. SPb.: BHV-Peter-burg, 2009.
• Kara O. Reflexné útoky na produktové šifry. URL: http://eprint.iacr.org/2007/043.pdf
• Ruský štandard šifrovania: znížená sila. 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: „Neponáhľajte sa ho pochovať.“

Slávny bádateľ, zakladateľ algebraickej kryptanalýzy, Nicolas Courtois, tvrdí, že bloková šifra GOST, ktorá sa mala v blízkej budúcnosti stať medzinárodným štandardom, bola skutočne prelomená a v budúcnosti čaká na mnohé publikácie, ktoré by mali rozvinúť jeho predstavy o nestabilita tohto algoritmu.

Nasledujú stručné úryvky z tejto práce, ktorú možno považovať za poplašný útok uprostred medzinárodnej normalizácie (autor bol známy podobnými zveličeniami vo vzťahu k AES, ale jeho práca mala vtedy veľký teoretický vplyv na kryptanalýzu, ale má neviedlo k praktickým útokom na samotný AES). Ale možno je to tiež skutočné varovanie pred začiatkom fázy „potápania lietadla s chvostom“, ktoré môže skončiť zrútením národného šifrovacieho štandardu, ako to bolo v prípade hashovacieho algoritmu SHA-1 a de facto MD5 hashovací algoritmus.

GOST 28147-89 bol štandardizovaný v roku 1989 a stal sa prvýkrát oficiálnym štandardom na ochranu dôverných informácií, ale špecifikácia šifry zostala uzavretá. V roku 1994 bola norma odtajnená, uverejnená a preložená do angličtiny. Analogicky s AES (a na rozdiel od DES) môže GOST chrániť utajované skutočnosti bez obmedzení v súlade so spôsobom, ktorý je uvedený v ruskej norme. To. GOST nie je analógom DES, ale je konkurentom 3-DES s tromi nezávislými kľúčmi alebo AES-256. GOST je očividne dosť vážna šifra, ktorá spĺňa vojenské kritériá a bola vytvorená s očakávaním najvážnejších aplikácií. Na základe aplikácií používaných ruskými bankami boli identifikované najmenej dve sady GOST S-boxov. Tieto banky musia viesť tajnú komunikáciu so stovkami pobočiek a chrániť miliardy dolárov pred podvodnými krádežami.

GOST je bloková šifra s jednoduchou Feistelovou štruktúrou s veľkosťou bloku 64 bitov, 256-bitovým kľúčom a 32 zaokrúhľovaním. Každé kolo obsahuje pridanie kľúča modulo 2 ^ 32, sadu ôsmich 4-bitových S-boxov a jednoduchý 11-bitový cyklický posun. Funkciou GOST je schopnosť tajne ukladať S-bloky, ktoré môžu byť reprezentované ako druhý kľúč, ktorý zvyšuje efektívny materiál kľúča na 610 bitov. Jedna sada S-boxov bola publikovaná v roku 1994 ako súčasť špecifikácie hašovacej funkcie GOST-R 34.11-94 a, ako napísal Schneier, bola použitá Centrálnou bankou Ruskej federácie. Je tiež zahrnutý v štandarde RFC4357 v časti „id-GostR3411-94-CryptoProParamSet“. Na konci Schneierovej knihy (v poradí S-box) bola chyba v zdrojovom kóde. Najpresnejšiu referenčnú implementáciu pôvodného ruského pôvodu je teraz možné nájsť v knižnici OpenSSL. Ak sa niekde používajú tajné S-boxy, môžu byť extrahované zo softvérových implementácií a z mikroobvodov, v skutočnosti boli publikované zodpovedajúce práce.

GOST je vážnym konkurentom

Okrem veľmi veľkej veľkosti kľúča má GOST výrazne nižšie náklady na spustenie v porovnaní s AES a inými podobnými šifrovacími systémami. V skutočnosti to stojí oveľa menej ako AES, čo vyžaduje štyrikrát viac hardvérových logických brán na oveľa nižšie deklarované zabezpečenie.

Nie je prekvapujúce, že sa GOST stal internetovým štandardom, najmä je zahrnutý v mnohých krypto knižniciach, ako sú OpenSSL a Crypto ++, a stáva sa populárnejším aj mimo svojej krajiny pôvodu. V roku 2010 bol GOST vyhlásený za štandardizáciu ISO ako celosvetový štandard šifrovania. Extrémne malý počet algoritmov sa dokázal stať medzinárodnými štandardmi. ISO / IEC 18033-3: 2010 opisuje nasledujúce algoritmy: štyri 64-bitové šifry-TDEA, MISTY1, CAST-128, HIGHT-a tri 128-bitové šifry-AES, Camellia, SEED. GOST sa navrhuje pridať k rovnakej norme ISO / IEC 18033-3.

Po prvýkrát v histórii priemyselnej normalizácie sa zaoberáme takýmto konkurenčným algoritmom z hľadiska optimality medzi nákladmi a úrovňou zabezpečenia. GOST má 20 rokov úsilia o kryptoanalýze a až donedávna nebola spochybnená jeho bezpečnosť na vojenskej úrovni.

Ako sa autor nedávno dozvedel zo súkromnej korešpondencie, väčšina krajín bola proti GOST na hlasovaní ISO v Singapure, ale výsledky tohto hlasovania budú ešte zvážené na plenárnom zasadnutí ISO SC27, takže GOST je v čase normalizácie stále v procese štandardizácie. vydanie tejto práce.

Názory odborníkov na GOST

Nič z dostupných informácií a literatúry týkajúce sa GOST nedáva dôvod domnievať sa, že šifra môže byť nebezpečná. Naopak, veľká veľkosť kľúča a veľký počet kôl robí z GOST na prvý pohľad vhodný na desaťročia používania.

Každý, kto pozná Moorov zákon, si uvedomuje, že teoreticky 256-bitové kľúče zostanú bezpečné najmenej 200 rokov. GOST bol podrobne študovaný poprednými odborníkmi v oblasti kryptografie, známymi v oblasti analýzy blokových šifier, ako sú Schneier, Biryukov, Dankelman, Wagner, mnohými austrálskymi, japonskými a ruskými vedcami, odborníkmi na kryptografiu z ISO a všetkými výskumníkmi. vyjadril, že všetko vyzerá takto, že môže byť alebo by mal byť v bezpečí. Aj keď názor dosiahol široké pochopenie, že samotná štruktúra GOST je napríklad v porovnaní s DES mimoriadne slabá, difúzia najmä nie je taká dobrá, vždy to však bolo spôsobené tým, že by to malo byť kompenzované veľký počet kôl (32), ako aj dodatočná nelinearita a difúzia poskytovaná prídavkom modulu.

Biryukov a Wagner napísali: „Veľký počet kôl (32) a dobre preštudovaná Feistelova konštrukcia v kombinácii s postupnými Shannonovými permutáciami poskytujú pevný základ pre bezpečnosť GOST.“ V tej istej práci čítame: „po značnom vynaložení času a úsilia nebol v kryptanalýze štandardu v otvorenej literatúre dosiahnutý žiadny pokrok“. V realistickom scenári, kde sa pri šifrovaní GOST používa mnoho rôznych náhodných kľúčov, teda nedošlo k žiadnym významným útokom, ktoré by umožnili dešifrovanie alebo obnovu kľúčov. Naproti tomu je známych veľa prác o útokoch na slabé kľúče v GOST, útokoch s priradenými kľúčmi, útokoch na obnovu tajných S-boxov. Na Crypto-2008 bolo predstavené hacknutie hašovacej funkcie založenej na tejto šifre. Pri všetkých útokoch má útočník výrazne väčšiu mieru slobody, ako by mu bolo normálne dovolené. V tradičných aplikáciách šifrovania pomocou náhodne vybraných kľúčov sa zatiaľ nezistili žiadne závažné kryptografické útoky na GOST, čo v roku 2010 vyjadrovala záverečná veta: „Napriek výraznému úsiliu kryptanalytikov za posledných 20 rokov GOST ešte nebol prasknuté “(Axel Poschmann, San Ling a Huaxiong Wang: 256-bitové štandardizované krypto pre 650 GE GOST Revisited, In CHES 2010, LNCS 6225, s. 219-233, 2010).

Lineárna a diferenciálna analýza GOST

V Schneierovej známej knihe čítame: „Proti diferenciálnej a lineárnej kryptoanalýze je GOST pravdepodobne robustnejší ako DES.“ Hlavné hodnotenie bezpečnosti GOST poskytli v roku 2000 Gabidulin a kol. Ich výsledky sú veľmi pôsobivé: s úrovňou zabezpečenia 2 ^ 256 je päť kôl postačujúcich na ochranu GOST pred lineárnou kryptoanalýzou. Navyše, aj po výmene S -boxov za identické a jedinej nelineárnej šifrovej operácii - adičný mód 2 ^ 32 - je šifra stále odolná voči lineárnej kryptanalýze aj po 6 kolách z 32. GOST diferenciálna kryptoanalýza vyzerá relatívne jednoduchšie a priťahuje väčšiu pozornosť. Pre úroveň bezpečnosti 2 ^ 128 bádatelia (Vitaly V. Shorin, Vadim V. Jelezniakov a Ernst M. Gabidulin: Lineárna a diferenciálna kryptoanalýza ruskej GOST, predtlač predložená Elsevier Preprint, 4. apríla 2001) predpokladali dostatočnú trvanlivosť v 7 kolách. Podľa nich je prelomenie GOST vo viac ako piatich kolách „mimoriadne náročné“. Dvaja japonskí vedci navyše dokázali, že klasický priamy diferenciálny útok s jednou diferenciálnou charakteristikou má extrémne nízku pravdepodobnosť, že prejde veľkým počtom kôl. Na základe skutočnosti, že študujeme dostatočne „dobrú“ iteračnú diferenciálnu charakteristiku pre obmedzený počet kôl (ktorá sama o sebe má pravdepodobnosť, že neprebehne lepšie ako 2–11,4 na kolo), je hodnota sady vhodných kľúčov menšia ako polovica . Pre úplnú GOST bude taký útok s jedinou charakteristikou fungovať iba so zanedbateľnou časťou kľúčov rádovo 2-62 (a dokonca aj v tejto malej časti bude mať pravdepodobnosť, že prejde nie viac ako 2–360 ).

Sofistikovanejšie útoky zahŕňajú viacero diferenciálov, ktoré sa riadia určitými vzormi, napríklad pomocou samostatných S-boxov, ktoré majú nulové diferenciály, zatiaľ čo ostatné bity majú nenulové. Hovoríme o diskriminačných útokoch na základe zlých difúznych vlastností GOST. Najlepší z týchto útokov funguje proti 17 kolám GOST, závisí od kľúča a má extrémne slabý rozlišovač náhodných údajov na samotnom výstupe, takže ho možno nejakým spôsobom použiť na získanie informácií o kľúči.

Kĺzavé a odvracajte útoky

Podľa Biryukova a Wagnera je štruktúra GOST, ktorá v posledných kolách zahŕňa obrátené poradie podkľúčov, odolná voči kĺzavým útokom (takzvané „kĺzavé útoky“). Avšak kvôli prítomnosti veľkej podobnosti v šifre to umožňuje útokom inverzných kľúčov na kombinácie pevných bodov a vlastností „odrazu“ (takzvané „reflexné útoky“) pre určité slabé kľúče. Zložitosť tohto útoku je 2 ^ 192 a 2 ^ 32 zhodných holých textov.

Najnovšie výsledky

Nové útoky tiež používajú odraz a v skutočnosti prelomili GOST, ktorý bol predstavený na konferencii FSE 2011. Tieto útoky zistil nezávisle aj autor tohto príspevku. Útok vyžaduje 2 ^ 132 bajtov pamäte, čo je v skutočnosti horšie ako pomalšie útoky s menšími požiadavkami na pamäť.

Množstvo nových útokov na vlastnú podobnosť funguje proti všetkým kľúčom GOST a umožňuje vám rozbiť úplnú GOST s 256-bitovým kľúčom, nielen pre slabé kľúče, ako to bolo predtým. Všetky tieto útoky vyžadujú podstatne menej pamäte a sú výrazne rýchlejšie.

Tieto nové útoky možno považovať za príklady novej všeobecnej paradigmy kryptoanalýzy blokových šifier nazývanej „zníženie algebraickej komplexnosti“ s generalizáciou týchto útokov na mnoho špeciálnych prípadov útokov so známymi pevnými bodmi, diapozitívmi, evolúciami a cyklami. Je dôležité, aby v rodine všetkých týchto útokov boli tie, ktoré umožňujú kryptoanalýzu GOST bez akýchkoľvek odrazov a bez akýchkoľvek symetrických bodov, ktoré sa objavujú v priebehu výpočtov. Jedným z príkladov je jednoduchý hackerský útok GOST bez reflexie v tejto práci.

Algebraická kryptoanalýza a útoky s nízkou komplexitou údajov na šifry so zníženým počtom nábojov

Algebraické útoky na blokové a prúdové šifry môžu byť reprezentované ako problém riešenia veľkého systému booleovských algebraických rovníc, ktorý sleduje geometriu a štruktúru konkrétnej kryptografickej schémy. Samotná myšlienka sa vracia k Shannonovi. V praxi to bolo prezentované pre DES (prvýkrát predstavený autorom tejto práce) ako formálna metóda kódovania a môže rozlúsknuť 6 kôl iba v jednom známom holom texte. Manipulácia s rovnicami je založená na algoritmoch XL, Gröbnerových bázach, metóde ElimLin, SAT riešiteľoch.

V praxi boli algebraické útoky implementované proti veľmi malému počtu cyklov blokových šifier, ale už viedli k popraskaniu prúdových šifier a úspechy sa dosiahli aj pri lámaní ultraľahkých šifier pre mikro zariadenia. Vzhľadom na problémy s veľkosťou pamäte a odhadmi výpočtových nákladov sú kombinované s inými útokmi.

Ako hacknúť GOST?

Algebraický útok na úplný GOST je podrobnejšie predstavený v tejto publikácii. V predchádzajúcom diele autor už načrtol 20 algebraických útokov na GOST a očakáva ich veľký počet v blízkej budúcnosti. Útok navrhovaný v tejto práci nie je najlepší z nich, otvára však jednoduchú cestu (aspoň pre pochopenie kryptografov) pre ďalší vývoj s cieľom vytvoriť konkrétnu metodológiu prelomenia GOST.

Praktický výsledok je stále skromný: 2 ^ 64 známych holých textov a 2 ^ 64 pamäť na ukladanie párov holého textu / šifrového textu umožňuje prelomiť GOST 2 ^ 8 rýchlejšie ako jednoduchá hrubá sila. Ale pokiaľ ide o kryptoanalýzu, je úplne spravodlivé tvrdiť, že „GOST bol prelomený“.

závery

GOST je navrhnutý tak, aby poskytoval vojenskú úroveň bezpečnosti na 200 rokov dopredu. Väčšina popredných odborníkov, ktorí študovali GOST, súhlasila s tým, že „napriek značnému kryptoanalytickému úsiliu počas 20 rokov GOST ešte nebol prelomený“. V roku 2010 bol GOST povýšený na ISO 18033 ako globálny štandard šifrovania.

Základ myšlienok o algebraickej kryptoanalýze sa objavil pred viac ako 60 rokmi. Ale iba za posledných 10 rokov boli vyvinuté efektívne softvérové ​​nástroje na (čiastočné) riešenie mnohých problémov NP-complete. Mnoho prúdových šifier bolo prasknutých. Touto metódou bola prelomená iba jedna bloková šifra - samotný slabý KeeLoq. V tejto práci autor láme dôležitú, skutočne používanú šifru GOST. Poznamenáva, že je to prvýkrát v histórii, kedy bola štandardizovaná štátna šifra prelomená algebraickou kryptanalýzou.

Jednoduchý útok typu „MITM s odrazom“ na GOST už bol predstavený na konferencii FSE 2011. V práci diskutovanej v tomto článku je ďalší útok predstavený len na ilustráciu skutočnosti, koľko útokov na GOST sa už teraz vyskytlo, z ktorých mnohé sú rýchlejšie a algebraický útok vyžaduje oveľa menej pamäte a otvára protivníkovi takmer nevyčerpateľný priestor možností, ako zaútočiť na šifru rôznymi spôsobmi. Aj v tomto článku sa ukazuje, že na hackovanie nie je potrebné používať vlastnosť odrazu.

Autor tvrdí, že je zrejmé, že GOST má vážne chyby a teraz neposkytuje takú trvanlivosť, akú vyžaduje ISO. Mnoho útokov na GOST je prezentovaných v rámci potvrdenia paradigmy zníženia algebraickej zložitosti.

Nakoniec si výskumník osobitne všimne niektoré skutočnosti, ktoré ešte nie sú čitateľovi k dispozícii, ale sú im známe, ktoré sú dôležité v priebehu procesu normalizácie ISO. Tento útok nie je len „certifikačným“ útokom na GOST, ktorý je rýchlejší ako útok hrubou silou hrubou silou. V skutočnosti by štandardizácia GOST bola teraz mimoriadne nebezpečná a nezodpovedná. Dôvodom je, že niektoré útoky sú praktické. V praxi môžu byť niektoré kľúče GOST dokonca dešifrované, či už sú to slabé kľúče alebo kľúče od súkromných skutočných aplikácií GOST. V predchádzajúcom diele autor podrobne zvažuje prípady možnosti praktických útokov. Je príznačné, že „je to prvýkrát v histórii, čo bola vážna štandardizovaná bloková šifra navrhnutá na ochranu tajomstiev vojenskej triedy a určená na ochranu štátnych tajomstiev vlád, veľkých bánk a ďalších organizácií narušená matematickým útokom“.