Hazai adattitkosítási szabvány. Hazai adattitkosítási szabvány Kriptográfiai konverziós algoritmus GOST 28147 89

A rejtjel rövid leírása

A GOST 28147-89 - A szimmetrikus titkosítás szovjet és orosz szabványa, amelyet 1990-ben vezettek be, szintén a FÁK szabványa. Teljes név - „GOST 28147-89 Információfeldolgozó rendszerek. Kriptográfiai védelem. Kriptográfiai transzformációs algoritmus”. Blokk titkosítási algoritmus. A gamma-titkosítási módszer alkalmazásakor képes ellátni egy adatfolyam titkosítási algoritmus funkcióit.

A GOST 28147-89 egy blokk titkosítás 256 bites kulccsal és 32 konverziós ciklussal, amely 64 bites blokkokkal működik. A rejtjelezési algoritmus alapja a Feistel hálózat. A GOST 28147-89 szerinti alapvető titkosítási mód az egyszerű helyettesítési mód (összetettebb módok is vannak meghatározva - gamma, gamma Visszacsatolásés szimulált beszúrási mód).

Hogyan működik az algoritmus

Az algoritmus alapvetően nem különbözik a DES-től. A Feistel-séma szerint (2.9. ábra) titkosítási ciklusokat is tartalmaz (32 db van).

Rizs. 2.9. A GOST 28147-89 algoritmus titkosítási körei.

Alkulcsok generálásához az eredeti 256 bites kulcsot nyolc 32 bites blokkra osztják: k 1 …k 8 . A k 9 ... k 24 billentyűk a k 1 ... k 8 billentyűk ciklikus ismétlődése (a legkisebb jelentőségű bitektől a legjelentősebbekig számozva). A k 25 ...k 32 billentyűk a k 1 ...k 8 billentyűk fordított sorrendben haladnak.

Az algoritmus mind a 32 körének befejezése után az A 33 és a B 33 blokkokat összeragasztjuk (megjegyzendő, hogy A 33 lesz a legjelentősebb bit, és B 33 lesz a legkevésbé jelentős bit) - az eredmény az algoritmus eredménye.

Funkció f(A én ,K én) kiszámítása a következőképpen történik: A i és K i összeadjuk modulo 2 32 , majd az eredményt nyolc 4 bites részsorozatra osztjuk, amelyek mindegyikét a saját bemenetére tápláljuk. helyettesítő táblázat csomópontja(a bit elsőbbségének növekvő sorrendjében), az alábbiakban nevezzük S-blokk. A GOST S-blokkok teljes száma nyolc, azaz megegyezik a részsorozatok számával. Minden S-blokk számok permutációját jelenti 0-tól 15-ig. Az első 4 bites részsorozat az első S-box bemenetére esik, a második - a második bemenetére stb. egy 32 bites szó, akkor az egész szó ciklikusan balra (a legjelentősebb bitekre) tolódik el 11 bittel. Mind a nyolc S-box különböző lehet. Valójában további kulcsfontosságú anyagok is lehetnek, de gyakrabban olyan sémaparaméterek, amelyek a felhasználók egy bizonyos csoportja számára közösek. A szabvány szövege azt jelzi, hogy a csereegységek (S-blokkok) töltésének szállítása az előírt módon történik, pl. algoritmus fejlesztő. Az orosz CIPF fejlesztők közössége megállapodott az interneten használt cserecsomópontokról.

A visszafejtés ugyanúgy történik, mint a titkosítás, de a k i alkulcsok sorrendje fordított.

A GOST 28147-89 algoritmus működési módjai

A GOST 28147-89 algoritmus négy üzemmóddal rendelkezik.

1. Módegyszerű csere olyan adatokat fogad be bemenetként, amelyek mérete 64 bit többszöröse. A titkosítás eredménye a bemeneti szöveg, amelyet 64 bites blokkokban konvertálunk a "32-3" ciklusú titkosítás esetén, illetve a dekódolás esetén a "32-P" ciklussal.

2. Módméretezés bármilyen méretű adatot fogad be bemenetként, valamint egy további 64 bites paramétert - üzenet szinkronizálása. Működés közben a szinkronizálási üzenet a "32-Z" ciklusban konvertálódik, az eredmény két részre oszlik. Az első rész modulo 2 32-vel egészül ki 1010101 16 állandó értékkel. Ha a második rész egyenlő 2 32 -1-gyel, akkor értéke nem változik, ellenkező esetben modulo 2 32 -1-et ad hozzá 1010104 16 állandó értékkel. A két konvertált rész kombinálásával kapott érték, az úgynevezett gamma titkosítás, belép a "32-3" hurokba, ennek eredménye a modulo 2 bitenkénti hozzáadásával egy 64 bites bemeneti adatblokk. Ha ez utóbbi kevesebb, mint 64 bit, akkor a kapott érték extra bitjeit eldobja. Az eredményül kapott érték elküldésre kerül a kimenetre. Ha még mindig vannak bejövő adatok, akkor a művelet megismétlődik: a 32 bites részekből álló blokkot részekre konvertálja, és így tovább.

3. Módméretezés visszajelzéssel bármilyen méretű adatot és szinkronizálási üzenetet is elfogad bemenetként. A bemeneti adatok blokkját bitenként hozzáadjuk modulo 2-ként a transzformáció eredményével a szinkron üzenet "32-3" ciklusában. Az eredményül kapott érték elküldésre kerül a kimenetre. A szinkronizálási üzenet értékét titkosítás esetén a kimeneti blokk, dekódolás esetén pedig a bemeneti, azaz titkosított váltja fel. Ha a bejövő adatok utolsó blokkja kevesebb, mint 64 bit, akkor a gamma extra bitjei (a "32-3" hurok kimenete) el lesznek dobva. Ha még mindig vannak bejövő adatok, akkor a művelet megismétlődik: a gamma-rejtjel a lecserélt érték titkosításának eredményéből jön létre, és így tovább.

4. Termelési módbetétutánzatok olyan bemeneti adatokat vesz, amelyek legalább két teljes 64 bites blokk méretűek, és egy 64 bites adatblokkot ad vissza, amelyet beszúrás megszemélyesítésnek neveznek. Az ideiglenes 64 bites érték 0-ra van állítva, majd amíg van bemenő adat, bitenként hozzáadódik modulo 2 a "16-3" ciklus végrehajtásának eredményeként, aminek a bemenete a bemeneti adatblokk . A bevitel vége után az ideiglenes érték kerül visszaadásra eredményként.

A titkosítás kriptanalízise

A GOST 28147-89 titkosítás 256 bites kulcsot használ, és a kulcsterület mérete 2256. Egyetlen jelenleg létező általános célú számítógép sem képes kitalálni egy kulcsot kevesebb mint sok száz éven belül. A GOST 28147-89 orosz szabványt nagy ráhagyással tervezték, és sok nagyságrenddel meghaladja az amerikai DES szabványt 56 bites valós kulcsméretével és mindössze 2 56 kulcsterületével.

Vannak támadások a teljes körű GOST 28147-89 ellen is, minden módosítás nélkül. Az elsők egyike nyitott művek, amelyben az algoritmus elemzését végezték, számos jól ismert titkosítási algoritmus kulcsbővítési eljárásának gyengeségeit használja fel. Különösen a GOST 28147-89 teljes körű algoritmus bontható meg differenciális kriptográfiai elemzéssel összekapcsolt kulcsokon, de csak akkor, ha gyenge helyettesítési táblákat használnak. Az algoritmus 24 körös változata (amelyből az első 8 kör hiányzik) ugyanúgy megnyílik bármely helyettesítési táblánál, azonban az erős helyettesítési táblázatok teljesen kivitelezhetetlenné teszik az ilyen támadást.

A hazai tudósok A.G. Rosztovcev és E.B. Makhovenko 2001-ben egy alapvetően új kriptoanalízis-módszert javasolt úgy, hogy egy ismert nyílt szövegből célfüggvényt alkot, a hozzá tartozó rejtjelezett szöveget és a kívánt kulcsértéket, és megkeresi a kulcs valódi értékének megfelelő szélsőértékét. 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öveggel és a megfelelő titkosított szövegekkel, meglehetősen alacsony bonyolultsággal.

2004-ben koreai szakértők egy csoportja olyan támadást javasolt, amellyel a kapcsolódó kulcsok differenciális kriptoanalízise segítségével 91,7%-os valószínűséggel 12 bites titkos kulcsot lehet megszerezni. A támadáshoz 235 kiválasztott egyszerű szövegre és 236 titkosítási műveletre van szükség. Mint látható, ez a támadás gyakorlatilag haszontalan az algoritmus valódi megnyitásához.

A helyettesítési táblázat hosszú távú kulcselem, vagyis sokkal többre is érvényes hosszútávú mint egyetlen kulcs. Feltételezzük, hogy egy titkosítási védelmi rendszeren belül minden titkosítási csomópontra közös. A táblázat minősége határozza meg a titkosítás minőségét. Egy "erős" helyettesítési táblázatnál a titkosítás erőssége nem esik egy bizonyos elfogadható határ alá, még akkor sem, ha nyilvánosságra hozzuk. Ezzel szemben a „gyenge” táblázat használata elfogadhatatlanul alacsony határra csökkentheti a titkosítás erősségét. Nincs információ a helyettesítési táblázat minőségéről nyitott pecsét Oroszországot nem publikálták, de a "gyenge" táblák létezése kétségtelen - példa erre a "triviális" helyettesítési táblázat, amely szerint minden értéket önmagával helyettesít. Számos munkában tévesen azt a következtetést vonták le, hogy a GOST 28147-89 algoritmus titkos helyettesítési táblái a kulcs részét képezhetik, és növelhetik annak effektív hosszát (ami nem jelentős, mivel az algoritmus nagyon nagy, 256 bites kulccsal rendelkezik ).

Titkosító algoritmus GOST 28147-89. Egyszerű helyettesítési módszer. — Archívum WASM.RU

„Amíg élsz, ne halj meg, nézd ezt a világot.
Itt sokaknak halott a lelke – belül halottak.
De sétálnak és nevetnek, nem tudván, hogy nincsenek ott,
Ne siesd el a halálodat – mondta nekem.

Aria, "Fenn"

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

3.1 Kulcs információ
3.2 A kriptotranszformáció fő lépése

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

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

Bevezetés.

Ez a dokumentum arra tesz kísérletet, hogy leírjam a GOST 28147-89 titkosítási algoritmus egyszerű helyettesítésének módszerét a legegyszerűbb, de technikailag művelt nyelven. Hogy mennyire sikerült, arról az olvasó az első hat pont elolvasása után mondja el véleményét.

Azért, hogy a munkám adja több haszon Javaslom, hogy a felhasznált irodalomjegyzékben feltüntetett szerzők munkáival vértezzék fel magukat. Számológép is javasolt, hogy legyen funkciója a művelet kiszámításához XOR, mert a cikk olvasása feltételezi, hogy az olvasó ezt a titkosítási algoritmust tanulmányozta. Bár referenciaeszköznek is alkalmas, ezt a cikket pontosan oktatóanyagként írtam.

Bevezetés a blokkolt titkosításba.

Mielőtt elkezdenénk megvizsgálni az algoritmust, meg kell ismerkednünk az ilyen típusú rejtjel létrehozásának történetével. Az algoritmus a blokk titkosítások kategóriájába tartozik, amelyek architektúrájában az információ véges számú blokkra van felosztva, a végső természetesen nem lehet teljes. A titkosítási folyamat pontosan a teljes blokkokon megy végbe, amelyek a titkosított szöveget alkotják. Az utolsó blokkot, ha hiányos, kiegészítik valamivel (a hozzáadás árnyalatairól alább beszélek), és ugyanúgy titkosítva van, mint a teljes blokkok. Titkosított szöveg alatt azt értem, hogy a titkosítási funkció bizonyos mennyiségű adaton, amelyet a felhasználó titkosításra adott be. Más szóval, a titkosított szöveg a titkosítás végeredménye.

A blokk-rejtjelek fejlődésének története a 70-es évek elejéhez kötődik, amikor az IBM, felismerve az információk védelmének szükségességét a számítógépes kommunikációs csatornákon történő adatátvitel során, megkezdte a megvalósítást. saját program tudományos kutatás az elektronikus hálózatokban található információk védelmére, beleértve a kriptográfiát is.

A kutatók egy csoportját - az IBM cég fejlesztőit, amely szimmetrikus kulcssémával kezdte el tanulmányozni a titkosítási rendszereket, Dr. Horst Feistel.

2.1 Feistel hálózatok

A klasszikus irodalomban Feistel által javasolt új titkosítási módszer architektúráját „Feistel Architecture”-nak nevezték, de Ebben a pillanatban az orosz és a külföldi irodalomban egy megalapozottabb kifejezést használnak - "Feistel hálózata" vagy Feistel hálózata. Ezt követően ennek az architektúrának megfelelően megépült a "Lucifer" rejtjel, amelyet később publikáltak, és általánosságban új érdeklődési hullámot váltott ki a kriptográfia iránt.

A Feistel hálózati architektúra ötlete a következő: a bemeneti információfolyam n bites méretű blokkokra van felosztva, ahol n páros szám. Minden blokk két részre van osztva - L és R, majd ezeket a részeket betáplálják egy iteratív blokk titkosításba, amelyben a j-edik szakasz eredményét az előző szakasz j-1 eredménye határozza meg! Ezt egy példával illusztrálhatjuk:

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 bonyolultabb megjelenésű, több egyszerű művelet sorozata - modulo összeadás, balra eltolás, elemcsere stb., összesen ezek egyszerű lépéseket alkotják az úgynevezett - a kriptotranszformáció fő lépését.

Megjegyzendő, hogy a funkció kulcselemei a kulcselemek beszerzése és az XOR művelet, és hogy mennyire átgondolt ezek a műveletek, az a rejtjel egészének kriptográfiai erősségéről beszél.

Annak érdekében, hogy a Feistel-hálózatok ötlete teljesen világos legyen, vegye figyelembe a 2. ábrán látható legegyszerűbb esetet. rizs. 1, ahol az A - függvényben a „mod 2” („xor”) műveleteket hajtják végre, de ez protozoon súlyosabb helyzetben, például országos jelentőségű információk elrejtése esetén az A funkció bonyolultabb lehet (amennyire én láttam, az A funkció valóban nagyon bonyolult lehet):

Kiinduló adatok:

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

Szerezzen titkosított szöveget

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 lépéseinket:

1. Ez a művelet összeadás mod 2 4 . A gyakorlatban egy ilyen művelet egy egyszerű összeadásban merül ki, ahol két számot kell hozzáadnunk, és figyelmen kívül kell hagynunk az 5. számjegyhez való átvitelt. Mivel ha egy szám bináris reprezentációjának számjegyei fölé kitevőket teszünk, akkor az ötödik számjegy felett négyes mutató lesz, nézzük meg az alábbi ábrát, amely a műveletünk műveleteit mutatja:

Rizs. 2

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

2. Ezt a műveletet az irodalomban mod 2-nek hívják, assembly nyelven a parancs valósítja meg XOR. De neki inkább helyes név mod 2 1 . Az egyedülálló művelet nélkül aligha lehet gyors, könnyen megvalósítható titkosítási algoritmust felépíteni, ugyanakkor meglehetősen kripto-ellenálló. Ennek a műveletnek az egyedisége abban rejlik, hogy önmagának a fordítottja! Például, ha az A számot B számmal XOR-ezzük, akkor az eredmény C lesz, a jövőben elég a B és C számokat együtt újra XOR-ozni, hogy megkapjuk A korábbi értékét!

Ebben a műveletben 1010-et kaptunk 1110 és 0100 számmal, az 1110 visszaadásához elég a 0100 és 1010 számokat XOR-ba rakni! Erről a műveletről további részletek az oldalra beágyazott cikkben találhatók. www.wasm.ru, « Elemi útmutató aCRC_hibaészlelő algoritmusok» a szerző, aki Ross N. Williams. Ebben a műben van egy bekezdés - " 5. Bináris aritmetikaátutalások nélkül". Ez a cikk ismerteti a műveletet xor! Felkiáltok, mert ebben a cikkben ez a művelet úgy van leírva, hogy az olvasó nem csak megérti, hogyan működik ez a művelet, hanem még elkezdi is. látni, hallani és érezni!

3. Erre a műveletre azért van szükség, hogy a titkosított szövegből történő visszafejtéskor megkaphassa az eredeti értékeket.

2.2 GOST 28147-89 blokk titkosítás

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

Ahhoz, hogy az algoritmus ezen módszere működjön, az információt 64 bites méretű blokkokra kell bontani. Generálja vagy írja be a titkosítási rendszerbe a következő kulcsinformációkat: kulcs és helyettesítési táblázat. A titkosításhoz szükséges kulcs és helyettesítő tábla megválasztását nagyon komolyan kell venni, mert. ez az Ön adatai biztonságának alapja. A kulcsra vonatkozó követelményekről és a helyettesítések táblázatáról lásd a "Kulcsinformációkra vonatkozó követelmények" című részt.

A módszer mérlegelésekor nem erre koncentrálunk, mert. ezt a cikket, amint fentebb említettem, azzal a céllal írták, hogy megtanítsák az olvasónak az adatok titkosítását az egyszerű helyettesítési módszerrel ezt az algoritmust titkosítást, de mindenképpen érinteni fogjuk ezt a kérdést a cikk végén.

elméleti minimum.

3.1 Főbb információk

Mint fentebb említettem, a következők aktívan részt vesznek az adattitkosításban:

3.1.1. A kulcs nyolc elemből álló sorozat, egyenként 32 bites. Továbbá jelöljük a K szimbólumot és az elemeket, amelyekből áll - k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 A helyettesítési táblázat nyolc sorból és tizenhat oszlopból álló mátrix, a továbbiakban Hij. Minden elem az i sor és a j oszlop metszéspontjában 4 bitet vesz igénybe.

3.2 A kriptotranszformáció fő lépése

A titkosítási folyamat fő művelete a kriptotranszformáció fő lépése. Ez nem más, mint az adatok titkosítása egy bizonyos algoritmussal, csak a fejlesztők által bevezetett név volt túl nehézkes.

A titkosítás megkezdése előtt a blokkot két L és R részre osztják, mindegyik 32 bites. A kulcselem kiválasztásra kerül, és csak ezután a blokk e két része kerül betáplálásra, a kulcselem a helyettesítési táblázat a fő lépésfüggvénybe, a fő lépés eredménye pedig az alapciklus egy iterációja, amelyről a következő részben lesz szó. következő bekezdés. A fő lépés a következő lépésekből áll:

1. Az R blokk összeadási része hozzáadódik a K mod 2 32 kulcselemhez. Fentebb leírtam egy hasonló műveletet, itt ugyanaz, csak a kitevő nem „4”, hanem „32” - ennek a műveletnek az eredményét a jövőben Smod fogja jelölni.
2. A korábban kapott Smod eredményt négy s7,s6,s5,s4,s3,s2,s1,s0 bitelemre osztjuk és betápláljuk a helyettesítő függvénybe. A csere a következőképpen történik: a Smod - s i elemet választjuk ki, elölről a legalacsonyabb elemtől indulunk, és az i - sor és oszlop helyettesítési táblázatából az s i elem értékével jelzett értékre cseréljük. Áttérünk az s i +1 elemre, és ugyanezt tesszük, és addig folytatjuk, amíg az utolsó Smod elem értékét le nem cseréljük - ennek a műveletnek az eredménye Ssimple lesz.
3. Ebben a műveletben az Ssimple értékét ciklikusan 11 bittel balra toljuk, és Srol-t kapunk.
4. Kiválasztjuk az L blokk második részét, és hozzáadjuk a mod 2-t a Srol-lal, ennek eredményeként Sxor-t kapunk.
5. Ebben a szakaszban a blokk L része egyenlővé válik az R rész értékével, az R rész pedig az Sxor eredményével inicializálódik, és ezzel befejeződik a fő lépésfüggvény!

3.3 Alapciklusok: „32-Z”, „32-R”.

Az információ titkosításához 64 bites méretű blokkokra kell bontani, természetesen az utolsó blokk 64 bitnél is kisebb lehet. Ez a tény ennek az „egyszerű helyettesítési” módszernek az Achilles-sarka. Mivel a 64 bites kiegészítése nagyon fontos feladat a rejtjelezett szöveg kriptográfiai erősségének növelése érdekében, ez az érzékeny hely, ha az információtömbben jelen van, de lehet, hogy nincs (például egy 512 bájt méretű fájl !), nagy felelősséggel kell kezelni!

Miután az információkat blokkokra bontotta, a kulcsot elemekre kell bontania:

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

Maga a titkosítás az úgynevezett alapciklusok használatából áll. Ami viszont magában foglalja az alapvető kriptotranszformációs lépések n-edik számát.

Az alapciklusokat, hogy is mondjam, jelöljük: n - m. Ahol n az alapvető kriptotranszformációs lépések száma az alaphurokban, m pedig az alaphurok "típusa", azaz. miről van szó, az adatok "Z" vagy "R" titkosításáról.

A 32–3. alapvető titkosítási ciklus 32 alapvető kriptográfiai lépésből áll. Az N blokk és a K kulcs eleme betáplálva van a lépés műveleteit megvalósító függvénybe, és az első lépés k1-el történik, a második az eredmény fölött a k2 elemmel 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 folyamat hasonló módon megy végbe, de a kulcselemek fordított sorrendben kerülnek betáplálásra:

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 kriptotranszformáció fő lépésének megvalósítása

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

Kiinduló adatok:

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

L = 01020304h, R = 05060708h, vegye a kulcsot:

K=' as28 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 Total Commander gomb megnyomása" F3", majd 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 figyelembe 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.

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

A "Kiinduló adatok" használatával meg kell kapnia a kriptotranszformáció fő lépésének eredményét.

1. Válassza ki az R = 05060708h alkatrészt és a k1 kulcselemet = 'as28', hexadecimális formában a kulcselem így fog kinézni: 61733238h. Most elvégezzük a 2 32 összegzési mód műveletét:

Rizs. 4

Amint az ábrán is látható, nem tértünk át a pirossal jelölt 33 bitre és a kitevővel 32 ". És ha az R-nek és a kulcselemnek más értékeink is lennének, akkor ez megtörténhet, és akkor figyelmen kívül hagynánk, és a jövőben csak a sárgával jelölt biteket használnánk.

Ilyen műveletet az assembler paranccsal hajtok végre add hozzá:

; eax=R, ebx='as28'

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

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

Rizs. 5

Megpróbáltam megjeleníteni az ábrán a Smod elemeket, de azért elmagyarázom:

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

Most a legalacsonyabb s0 elemtől kezdve cserét végzünk. Emlékezés a bekezdésre 3.2 A kriptotranszformáció fő lépése» i egy sor, s i egy oszlop, értéket keresünk 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 helyettesítését, azaz. négy. Az első sor és a negyedik oszlop használata (s1= 4!). Nézzük a képet:

Rizs. 7

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

A következő bekezdésben, miután a kiterjesztett tábláról beszélek, arról, hogyan lehet ezt a legkönnyebben megvalósítani assembler parancsok formájában.

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

Rizs. 8

Amint láthatja, ez a művelet meglehetősen egyszerű, és egyetlen assembly nyelvi paranccsal hajtják végre - tekercsés ennek a Srol műveletnek az eredménye 0819288Fh.

4. Most az XOR információs blokkunk L része marad Srol értékkel. Számológépet veszek a w2k sp4-ből, és megkapom az Sxor = 091b2b8bh-t.

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

Végeredmény:

L=091b2b8bh, R=01020304h

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

Most beszéljünk az algoritmus sebesség optimalizálásáról. Egy projekt megvalósításánál figyelembe kell venni, hogy a regiszterekkel gyakrabban, mint memóriával működő program működik a leggyorsabban, és itt ez az ítélet is nagyon fontos, mert. egy információtömbön keresztül, akár 32 titkosítási lépés!

Amikor implementáltam a titkosítási algoritmust a programomban, a következőket tettem:

1. Az L blokk kiválasztott része az eax regiszterben, és R az edx-ben.

2. Inicializálva az esi regiszterbe a kiterjesztett kulcs címével, erről bővebben alább.

3. A kiterjesztett helyettesítő tábla címének értékét az ebx regiszterhez rendeltem, erről lentebb

4. Az 1, 2, 3 pontok információit átadta a 32 - Z vagy a 32 - R alapciklus függvényének, helyzettől függően.

Ha megnézi a kulcselemek megadásának sémáját a " Alapciklusok: „32-Z”, „32-R””, akkor a 32 - Z alapciklushoz tartozó kulcsunk 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. az elejétől menjen k1,k2,k3,k4,k5,k6,k7,k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1' Ezt a sorozatot háromszor megismételjük. 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ömbben lévő elemeket előre elrendeztem a 32 - Z szerinti kiszolgálási sorrendben. Így megnöveltem a kulcsonkénti memóriaigényt, de megkíméltem magam néhány olyan gondolkodási folyamattól, amelyekre nincs szükségem, és megnöveltem a algoritmus, a memória-elérési idő csökkentésével! Itt csak a 32 - Z kulcsát írtam le, a 32 - R ciklusnál ugyanezt tettem, de más sémát használtam az elemek ellátására, amelyet szintén leírtam a " bekezdésben Alapciklusok: „32-Z”, „32-R».

Itt az ideje, hogy leírjam a helyettesítő funkció megvalósítását, ahogy fent ígértem. Nem tudtam korábban leírni, mert. ehhez egy új koncepció – egy kiterjesztett helyettesítési táblázat – bevezetésére van szükség. Nem tudom elmagyarázni, hogy mi az. Ehelyett megmutatom, és te magad is megfogalmazhatod, hogy mi is az - egy kiterjesztett helyettesítési táblázat?

Tehát ahhoz, hogy megértsük, mi az a kiterjesztett helyettesítési tábla, szükségünk van egy helyettesítési táblára, például az ábrán láthatót veszem. 3.

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

Rizs. 9

Ha most vesszük az s1,s0 elemeket, azaz. alacsony bájt, akkor a helyettesítő függvény eredménye 25h lesz! Miután elolvasta Andrey Vinokurov cikkét, amelyet a bekezdésben idéztem Felhasznált irodalom jegyzéke”, akkor valójában azt találja majd, hogy ha két sort vesz, akkor kap egy tömböt, amely lehetővé teszi, hogy gyorsan megtalálja a helyettesítő elemeket egy assembler paranccsal xlat. Azt mondják, hogy ez más módon is lehetséges, gyorsabban, de Andrey Vinokurov körülbelül négy évet töltött a GOST megvalósításának gyors algoritmusainak kutatásával! Szerintem ne találd fel újra a kereket, amikor már létezik.

Tehát a tömbről:

Vegyük az első két sort, a nullát és az elsőt, és hozzunk létre egy 256 bájtos tömböt. Most megfigyeljük az egyik jellemzőt, hogy ha 00h-t kell konvertálnia, akkor az eredmény 75h lesz (3. ábra alapján) - ezt az értéket tedd a tömbbe a 00h eltolásnál. Felvesszük a 01h értéket, a cserefüggvény eredménye 79h, 01 eltolásnál tesszük a tömbbe, és így tovább 0FFh-ig, ami 0FCh-t kap, amit 0FFh eltolásnál teszünk a tömbbe. Így kaptunk egy kiterjesztett táblázatot az első karakterlánc-csoport helyettesítéseiről: az első és a nulla. De még mindig van három csoport: a második oldal 2, 3 oldal, harmadik oldal 4, 5 oldal, negyedik oldal 6, 7 oldal. Ezzel a három csoporttal ugyanúgy járunk el, mint az elsővel. Az eredmény egy kiterjesztett helyettesítési táblázat!

Most implementálhat egy algoritmust, amely végrehajtja a cserét. Ehhez vesszük azokat a forráskódokat, amelyeket Andrey Vinokurov tett közzé az oldalán, lásd " Bibliográfia».

lea ebx,extented_table_simple

mov eax, [adja be a cserélendő számot]

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

sub ebx,300h ; hogy a jövőben az ebx a táblázatra mutasson

Most még egy funkció, nemcsak lecseréltük a korábbi műveleteket, hanem a számot is 8 bittel balra toltuk! Csak el kell tolnunk a számot további 3 bittel balra:

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

Az optimalizáláshoz nem tudok többet hozzáfűzni, az egyetlen dolog, amit fentebb mondtam, az az, hogy gyakrabban használjunk regisztereket, mint memóriaeléréseket. Szerintem ezek a szavak csak kezdőknek szólnak, a tapasztalt emberek ezt nagyon jól megértik az én szavaim nélkül is.

Főbb információs követelmények.

Amint azt Andrej Vinokurov cikkében kifejtette, a kulcsot két kritérium szerint választják ki:

A bitek egyenlő valószínűségű eloszlásának kritériuma az 1 és 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 ("khi-négyzet").

Ez a kulcsot jelenti, elvileg bármilyen szám lehet. Vagyis a kulcs következő bitjének kialakításakor annak eggyel vagy nullával történő inicializálásának valószínűsége 50/50!

Felhívjuk figyelmét, hogy a kulcs nyolc elemből áll, mindegyik 32 bites, tehát összesen 32 * 8 = 256 bit van a kulcsban és a számban lehetséges kulcsok 2256! Nem tűnik fel?

sorozat kritériumai.

Ha megnézzük a kulcsunkat, amelyet a bekezdésben adtam meg 4.1 A kriptotranszformáció fő lépésének megvalósítása", akkor észreveszi, hogy a következő bejegyzés igaz:

Rizs. 10

Egy mondatban a k 1 értéke nem ismétlődik meg sem k 2 -ben, sem a kulcs bármely más elemében.

Vagyis az általunk a titkosítási algoritmus szempontjául választott kulcs jól megfelel a fenti két kritériumnak.

Most a helyettesítő 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ési táblák kiválasztásának fő követelménye az egyenként 4 bites méretű elemek "megismételhetetlenségének" jelensége. Mint fentebb láthatta, 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 egy példányban tartalmazza a 0h, 1h, 2h, ... , 0fh értékeket és minden ilyen értéket. Például a sorrend:

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

Ennek a követelménynek teljes mértékben megfelel, de akkor is! Nem ajánlott egy ilyen sorozatot karakterláncként kiválasztani. Mert ha egy ilyen karakterláncra támaszkodó függvény bemenetére értéket adsz, akkor a kimeneten is ugyanazt az értéket kapod! Nem hiszed? Ezután vegye a 332DA43Fh számot és nyolc ilyen sort helyettesítő táblázatként. Hajtsa végre a csereműveletet, és biztosíthatom, hogy a kimenet a 332DA43Fh szám lesz! Vagyis ugyanaz, amit a művelet bemenetére adott! És ez nem a jó forma jele a titkosításban, és így volt?

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

Hogyan tűnik könnyebbnek? És így választottuk ki például az s0 = 0Fh, 01111b elemet a fenti számból. Annak a valószínűsége, hogy most az első bitet egyre vagy nullára cseréljük, 0,5! Annak a valószínűsége, hogy a második, harmadik és negyedik bitet külön-külön vizsgálva egyesekkel vagy nullákkal cseréljük le, szintén 0,5. Az s1 = 0Eh kiválasztásakor azt a valószínűséget cseréljük le, hogy nulla bitek vagyunk, és ez „0” , nullával vagy eggyel is egyenlő - 0,5! Így e kritérium szerint az s0, s1 elemek nulla bitjeinek cseréje között nincs szabályosság! Igen, lehet helyettesíteni egyeseket, de lehet nullákat is tenni.

A táblázat e kritérium szerinti értékeléséhez összeállíthat egy táblázatot a következő képlettel 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 bitek bármely kombinációja esetén a bemeneten;

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 egyenlő valószínűséggel veszi fel a 0 és 1 értéket az i bemeneti bit bármely rögzített értékére.

Vegyünk egy egysoros példát:

Bontsuk komponensekre:

Kiszámolunk egy együtthatót a fenti képlet segítségével. Hogy könnyebb legyen megérteni, hogyan történik ez, részletesebben elmagyarázom:

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

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

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

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

Egy ilyen sorrendben végrehajtott XOR műveletek szekvenciális végrehajtása után megszámoljuk az összes nem nulla érték számát, így a 6 értéket kapjuk. Így P 00 = 1-(6/2 4-1) = 0,25. Így kiderült, hogy a 0. bit értéke a kimeneten megegyezik a 0. bit értékével a bemeneten 16-ból 4 esetben;

Végső oddstábla:

Amint az a korrelációs együtthatók táblázatából látható, a 3. bit a bemeneten 16-ból 14 esetben invertálódik a 0. bithez képest a kimeneten, ami 87,5% Ez a normál titkosítási rendszerek esetében már nem elfogadható. A változatosság kedvéért vegyünk egy másik példát:

Az együtthatók táblázata a következő lesz (aki 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 kriptoanalitikusnak van hova megfordulnia Mindezeket a követelményeket figyelembe véve egy egyszerű felsorolás ("fejes") a megadott elméletnek megfelelő permutációs táblázatokat talált (ma - 1276 kombináció). Íme néhány ezek közül:

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

Felhasznált irodalom jegyzéke.

1. Andrej Vinokurov cikke:

A GOST 28147-89 titkosítási algoritmus, használata és megvalósítása

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

Itt vannak a titkosítási algoritmus megvalósításának forráskódjai.

1. Horst Feistel cikke:

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

(az előző cikkel azonos címen található)

1. Ross N. Williams:

Útmutató a CRC hibaészlelési algoritmusokhoz

Felkerült az oldalra www.wasm.hu.

Kösz.

Szeretném kifejezni köszönetemet a www.wasm.ru fórum minden látogatójának. De külön szeretném megköszönni ChS-nek, aki jelenleg SteelRat néven ismert, segített megértenem olyan dolgokat, amelyeket valószínűleg soha nem fogok megérteni, valamint segített megírni a bekezdést: " Főbb információs követelmények”, ennek a bekezdésnek a fő részét ő írta. Mélyen hálás vagyok a KSTU alkalmazottjának is. A.N. Tupolev Anikin Igor Vjacseszlavovics és bűn lenne nem megemlíteni Chris Kasperskyt, mert ő az, és Volodya / wasm.ru az utasításaiért. Ó, és kapok tőle. Azt is szeretném megjegyezni, hogy a Sega-Zero / Callipso egy matematikai dzsungelt juttat az eszembe.

Talán ez minden, amit el szeretnék mondani.

Hálás lennék a cikkhez kapcsolódó kritikákért, kérdésekért, vagy csak tanácsért. Elérhetőségem: [e-mail védett], ICQ - 337310594.

Üdvözlettel: Evil`s Interrupt.

P.S.: Nem próbáltam senkit felülmúlni ezzel a cikkel. Azzal a szándékkal íródott, hogy megkönnyítse a GOST tanulmányozását, és ha nehézségei vannak, ez nem jelenti azt, hogy én vagyok a hibás. Légy ésszerű és türelmes, minden jót neked!

„Amíg élsz, ne halj meg, nézd ezt a világot.
Itt sokaknak halott a lelke – belül halottak.
De sétálnak és nevetnek, nem tudván, hogy nincsenek ott,
Ne siesd el a halálodat – mondta nekem.

Aria, "Fenn"

1. Bevezetés

1. Bevezetés a blokkolt titkosításba

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 kriptotranszformáció fő lépése

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

1. Gyakorlat

4.1 A kriptotranszformáció fő lépésének megvalósítása
4.2 Az algoritmus sebességének növelése
5.
6. Felhasznált irodalom jegyzéke
7. Kösz.

Bevezetés.

Ez a dokumentum arra tesz kísérletet, hogy leírjam a GOST 28147-89 titkosítási algoritmus egyszerű helyettesítésének módszerét a legegyszerűbb, de technikailag művelt nyelven. Hogy mennyire sikerült, arról az olvasó az első hat pont elolvasása után mondja el véleményét.

Annak érdekében, hogy munkám hasznosabb legyen, javaslom, hogy a felhasznált irodalom jegyzékében feltüntetett szerzők munkáival fegyverkezzen fel. Számológép is javasolt, hogy legyen funkciója a művelet kiszámításához XOR, mert a cikk olvasása feltételezi, hogy az olvasó ezt a titkosítási algoritmust tanulmányozta. Bár referenciaeszköznek is alkalmas, ezt a cikket pontosan oktatóanyagként írtam.

Bevezetés a blokkolt titkosításba.

Mielőtt elkezdenénk megvizsgálni az algoritmust, meg kell ismerkednünk az ilyen típusú rejtjel létrehozásának történetével. Az algoritmus a blokk titkosítások kategóriájába tartozik, amelyek architektúrájában az információ véges számú blokkra van felosztva, a végső természetesen nem lehet teljes. A titkosítási folyamat pontosan a teljes blokkokon megy végbe, amelyek a titkosított szöveget alkotják. Az utolsó blokkot, ha hiányos, kiegészítik valamivel (a hozzáadás árnyalatairól alább beszélek), és ugyanúgy titkosítva van, mint a teljes blokkok. Titkosított szöveg alatt azt értem, hogy a titkosítási funkció bizonyos mennyiségű adaton, amelyet a felhasználó titkosításra adott be. Más szóval, a titkosított szöveg a titkosítás végeredménye.

A blokk-rejtjelek fejlődésének története a 70-es évek elejéhez kötődik, amikor az IBM, felismerve az információ védelmének szükségességét a számítógépes kommunikációs csatornákon történő adatátvitel során, elkezdte saját kutatási programját végrehajtani az elektronikus információk védelmére. hálózatok, beleértve a kriptográfiát is.

A kutatók egy csoportját - az IBM cég fejlesztőit, amely szimmetrikus kulcssémával kezdte el tanulmányozni a titkosítási rendszereket, Dr. Horst Feistel.

2.1 Feistel hálózatok

A Feistel által javasolt új titkosítási módszer architektúráját a klasszikus irodalomban "Feistel-architektúrának" nevezték, de jelenleg az orosz és a külföldi irodalomban egy megalapozottabb kifejezést használnak - "Feistel hálózata" vagy Feistel hálózata. Ezt követően ennek az architektúrának megfelelően megépült a Lucifer-rejtjel, amelyet később publikáltak, és általánosságban új érdeklődési hullámot váltott ki a kriptográfia iránt.

A Feistel hálózati architektúra ötlete a következő: a bemeneti információfolyam n bites méretű blokkokra van felosztva, ahol n páros szám. Minden blokk két részre van osztva - L és R, majd ezeket a részeket betáplálják egy iteratív blokk titkosításba, amelyben a j-edik szakasz eredményét az előző szakasz j-1 eredménye határozza meg! Ezt egy példával illusztrálhatjuk:

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 az XOR művelet, vagy lehet bonyolultabb formája, több egyszerű művelet sorozata - modulo összeadás, balra eltolás, elemcsere stb., összességében ezek az egyszerű műveletek alkotják az úgynevezett - a kriptotranszformáció fő lépését.

Megjegyzendő, hogy a funkció kulcselemei a kulcselemek beszerzése és az XOR művelet, és hogy mennyire átgondolt ezek a műveletek, az a rejtjel egészének kriptográfiai erősségéről beszél.

Annak érdekében, hogy a Feistel-hálózatok ötlete teljesen világos legyen, vegye figyelembe a 2. ábrán látható legegyszerűbb esetet. rizs. 1, ahol az A - függvényben a „mod 2” („xor”) műveleteket hajtják végre, de ez protozoon súlyosabb helyzetben, például országos jelentőségű információk elrejtése esetén az A funkció bonyolultabb lehet (amennyire én láttam, az A funkció valóban nagyon bonyolult lehet):

Kiinduló adatok:

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

Szerezzen titkosított szöveget

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 lépéseinket:

1. Ez a művelet a 2 4. mód. A gyakorlatban egy ilyen művelet egy egyszerű összeadásban merül ki, ahol két számot kell hozzáadnunk, és figyelmen kívül kell hagynunk az 5. számjegyhez való átvitelt. Mivel ha egy szám bináris reprezentációjának számjegyei fölé kitevőket teszünk, akkor az ötödik számjegy felett négyes mutató lesz, nézzük meg az alábbi ábrát, amely a műveletünk műveleteit mutatja:

Rizs. 2

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

1. Ezt a műveletet az irodalomban mod 2-nek hívják, assembly nyelven a parancs valósítja meg XOR. De a helyesebb neve mod 2 1 . Az egyedülálló művelet nélkül aligha lehet gyors, könnyen megvalósítható titkosítási algoritmust felépíteni, ugyanakkor meglehetősen kripto-ellenálló. Ennek a műveletnek az egyedisége abban rejlik, hogy önmagának a fordítottja! Például, ha az A számot B számmal XOR-ezzük, akkor az eredmény C lesz, a jövőben elég a B és C számokat együtt újra XOR-ozni, hogy megkapjuk A korábbi értékét!

Ebben a műveletben 1010-et kaptunk 1110 és 0100 számmal, az 1110 visszaadásához elég a 0100 és 1010 számokat XOR-ba rakni! Erről a műveletről további részletek az oldalra beágyazott cikkben találhatók. www.wasm.ru, « Elemi útmutató aCRC_hibaészlelő algoritmusok» a szerző, aki Ross N. Williams. Ebben a műben van egy bekezdés - 5. Bináris aritmetika hordozók nélkül". Ez a cikk ismerteti a műveletet xor! Felkiáltok, mert ebben a cikkben ez a művelet úgy van leírva, hogy az olvasó nem csak megérti, hogyan működik ez a művelet, hanem még elkezdi is. látni, hallani és érezni!

1. Erre a műveletre azért van szükség, hogy a titkosított szövegből történő visszafejtéskor megkaphassa az eredeti értékeket.

2.2 GOST 28147-89 blokk titkosítás

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

Ahhoz, hogy az algoritmus ezen módszere működjön, az információt 64 bites méretű blokkokra kell bontani. Generálja vagy írja be a titkosítási rendszerbe a következő kulcsinformációkat: kulcs és helyettesítési táblázat. A titkosításhoz szükséges kulcs és helyettesítő tábla megválasztását nagyon komolyan kell venni, mert. ez az Ön adatai biztonságának alapja. A kulcsra vonatkozó követelményekről és a helyettesítések táblázatáról lásd a "Kulcsinformációkra vonatkozó követelmények" című részt.

A módszer mérlegelésekor nem erre koncentrálunk, mert. Ezt a cikket, amint 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ével, de mindenképpen érinteni fogjuk ezt a kérdést a cikk végén.

elméleti minimum.

3.1 Főbb információk

Mint fentebb említettem, a következők aktívan részt vesznek az adattitkosításban:

3.1.1. A kulcs nyolc elemből álló sorozat, egyenként 32 bites. Továbbá jelöljük a K szimbólumot és az elemeket, amelyekből áll - k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 A helyettesítési táblázat nyolc sorból és tizenhat oszlopból álló mátrix, a továbbiakban Hij. Minden elem az i sor és a j oszlop metszéspontjában 4 bitet vesz igénybe.

A titkosítási folyamat fő művelete a kriptotranszformáció fő lépése. Ez nem más, mint az adatok titkosítása egy bizonyos algoritmus szerint, csak a fejlesztők által bevezetett név volt túl nehézkes :).

A titkosítás megkezdése előtt a blokkot két L és R részre osztják, mindegyik 32 bites. A kulcselem kiválasztásra kerül, és csak ezután a blokk e két része kerül betáplálásra, a kulcselem a helyettesítési táblázat a fő lépésfüggvénybe, a fő lépés eredménye pedig az alapciklus egy iterációja, amelyről a következő részben lesz szó. következő bekezdés. A fő lépés a következő lépésekből áll:

1. Az R blokk összeadási része hozzáadódik a K mod 2 32 kulcselemhez. Fentebb leírtam egy hasonló műveletet, itt ugyanaz a dolog, csak a kitevő nem „4”, hanem „32” - ennek a műveletnek az eredményét a jövőben az Smod fogja jelölni.
2. A korábban kapott Smod eredményt négy s7,s6,s5,s4,s3,s2,s1,s0 bitelemre osztjuk és betápláljuk a helyettesítő függvénybe. A csere a következő: a Smod - s i elem kerül kiválasztásra, elölről a legfiatalabb elemtől indulunk, és a helyettesítések táblázatában szereplő értékre cseréljük i - az s i elem értékével jelzett sor és oszlop . Áttérünk az s i +1 elemre, és ugyanezt tesszük, és addig folytatjuk, amíg az utolsó Smod elem értékét le nem cseréljük - ennek a műveletnek az eredménye Ssimple lesz.
3. Ebben a műveletben az Ssimple értékét ciklikusan 11 bittel balra toljuk, és Srol-t kapunk.
4. Kiválasztjuk az L blokk második részét, és hozzáadjuk a mod 2-t a Srol-lal, ennek eredményeként Sxor-t kapunk.
5. Ebben a szakaszban a blokk L része egyenlővé válik az R rész értékével, az R rész pedig az Sxor eredményével inicializálódik, és ezzel befejeződik a fő lépésfüggvény!

3.3 Alapciklusok: „32-Z”, „32-R”.

Az információ titkosításához 64 bites méretű blokkokra kell bontani, természetesen az utolsó blokk 64 bitnél is kisebb lehet. Ez a tény ennek az „egyszerű helyettesítési” módszernek az Achilles-sarka. Mivel a 64 bites kiegészítése nagyon fontos feladat a rejtjelezett szöveg kriptográfiai erősségének növelése érdekében, ez az érzékeny hely, ha az információtömbben jelen van, de lehet, hogy nincs (például egy 512 bájt méretű fájl !), nagy felelősséggel kell kezelni!

Miután az információkat blokkokra bontotta, a kulcsot elemekre kell bontania:

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

Maga a titkosítás az úgynevezett alapciklusok használatából áll. Ami viszont magában foglalja az alapvető kriptotranszformációs lépések n-edik számát.

Az alapciklusokat, hogy is mondjam, jelöljük: n - m. Ahol n az alapvető kriptotranszformációs lépések száma az alaphurokban, m pedig az alaphurok "típusa", azaz. miről van szó, az adatok "Z" vagy "R" titkosításáról.

A 32–3. alapvető titkosítási ciklus 32 alapvető kriptográfiai lépésből áll. Az N blokk és a K kulcs eleme betáplálva van a lépés műveleteit megvalósító függvénybe, és az első lépés k1-el történik, a második az eredmény fölött a k2 elemmel 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 folyamat hasonló módon megy végbe, de a kulcselemek fordított sorrendben kerülnek betáplálásra:

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ó titkosításának elméletével, ideje megnézni, hogyan működik a titkosítás a gyakorlatban.

Kiinduló adatok:

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

L = 01020304h, R = 05060708h, vegye a kulcsot:

K=' as28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (ezek ASCII kódok, a hexadecimális ábrázolás megtekintéséhez ezt a fájlt megtekintheti a Total Commanderben, ha megnyomja a " F3", majd 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 figyelembe 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.

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

A "Kiinduló adatok" használatával meg kell kapnia a kriptotranszformáció fő lépésének eredményét.

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

Rizs. 4

Amint az ábrán is látható, nem tértünk át a pirossal jelölt 33 bitre és a kitevővel 32 ". És ha az R-nek és a kulcselemnek más értékeink is lennének, akkor ez megtörténhet, és akkor figyelmen kívül hagynánk, és a jövőben csak a sárgával jelölt biteket használnánk.

Ilyen műveletet az assembler paranccsal hajtok végre add 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 ijesztő, mint amilyennek elsőre tűnik. Képzeljük el a Smodot a következő formában:

MINTA NEM MENTÉSE

Rizs. 5

Megpróbáltam megjeleníteni az ábrán a Smod elemeket, de azért elmagyarázom:

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

Most a legalacsonyabb s0 elemtől kezdve cserét végzünk. Emlékezés a bekezdésre 3.2 A kriptotranszformáció fő lépése» i egy sor, s i egy oszlop, értéket keresünk 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 helyettesítését, azaz. négy. Az első sor és a negyedik oszlop használata (s1= 4!). Nézzük a képet:

Rizs. 7

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

A következő bekezdésben, miután a kiterjesztett tábláról beszélek, arról, hogyan lehet ezt a legkönnyebben megvalósítani assembler parancsok formájában.

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

Rizs. 8

Amint láthatja, ez a művelet meglehetősen egyszerű, és egyetlen assembly nyelvi paranccsal hajtják végre - tekercsés ennek a Srol műveletnek az eredménye 0819288Fh.

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

Végeredmény:

L=091b2b8bh, R=01020304h

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

Most beszéljünk az algoritmus sebesség optimalizálásáról. Egy projekt megvalósításánál figyelembe kell venni, hogy a regiszterekkel gyakrabban, mint memóriával működő program működik a leggyorsabban, és itt ez az ítélet is nagyon fontos, mert. egy információtömbön keresztül, akár 32 titkosítási lépés!

Amikor implementáltam a titkosítási algoritmust a programomban, a következőket tettem:

1. Válassza az L blokk egy részét az eax regiszterbe, az R blokkot pedig az edx-be.
2. Az esi regiszterbe inicializálva a kiterjesztett kulcs címével, erről bővebben alább.
3. A kiterjesztett helyettesítési tábla címének értékét az ebx regiszterhez rendeltem, erről lentebb
4. Az 1, 2, 3 pontok információit átadta a 32 - Z vagy a 32 - R alapciklus függvényének, helyzettől függően.

Ha megnézi a kulcselemek megadásának sémáját a " Alapciklusok: „32-Z”, „32-R””, akkor a 32 - Z alapciklushoz tartozó kulcsunk 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. az elejétől menjen k1,k2,k3,k4,k5,k6,k7,k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1' Ezt a sorozatot háromszor megismételjük. 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ömbben lévő elemeket előre elrendeztem a 32 - Z szerinti kiszolgálási sorrendben. Így megnöveltem a kulcsonkénti memóriaigényt, de megkíméltem magam néhány olyan gondolkodási folyamattól, amelyekre nincs szükségem, és megnöveltem a algoritmus, a memória-elérési idő csökkentésével! Itt csak a 32 - Z kulcsát írtam le, a 32 - R ciklusnál ugyanezt tettem, de más sémát használtam az elemek ellátására, amelyet szintén leírtam a " bekezdésben Alapciklusok: „32-Z”, „32-R».

Itt az ideje, hogy leírjam a helyettesítő funkció megvalósítását, ahogy fent ígértem. Nem tudtam korábban leírni, mert. ehhez egy új koncepció – egy kiterjesztett helyettesítési táblázat – bevezetésére van szükség. Nem tudom elmagyarázni, hogy mi az. Ehelyett megmutatom, és te magad is megfogalmazhatod, hogy mi is az - egy kiterjesztett helyettesítési táblázat?

Tehát ahhoz, hogy megértsük, mi az a kiterjesztett helyettesítési tábla, szükségünk van egy helyettesítési táblára, például az ábrán láthatót veszem. 3.

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

MINTA NEM MENTÉSE

Rizs. 9

Ha most vesszük az s1,s0 elemeket, azaz. alacsony bájt, akkor a helyettesítő függvény eredménye 25h lesz! Miután elolvasta Andrey Vinokurov cikkét, amelyet a bekezdésben idéztem Felhasznált irodalom jegyzéke”, akkor valójában azt találja majd, hogy ha két sort vesz, akkor kap egy tömböt, amely lehetővé teszi, hogy gyorsan megtalálja a helyettesítő elemeket egy assembler paranccsal xlat. Azt mondják, hogy ez más módon is lehetséges, gyorsabban, de Andrey Vinokurov körülbelül négy évet töltött a GOST megvalósításának gyors algoritmusainak kutatásával! Szerintem ne találd fel újra a kereket, amikor már létezik.

Tehát a tömbről:

Vegyük az első két sort, a nullát és az elsőt, és hozzunk létre egy 256 bájtos tömböt. Most megfigyeljük az egyik jellemzőt, hogy ha 00h-t kell konvertálnia, akkor az eredmény 75h lesz (3. ábra alapján) - ezt az értéket tedd a tömbbe a 00h eltolásnál. Felvesszük a 01h értéket, a cserefüggvény eredménye 79h, 01 eltolásnál tesszük a tömbbe, és így tovább 0FFh-ig, ami 0FCh-t kap, amit 0FFh eltolásnál teszünk a tömbbe. Így kaptunk egy kiterjesztett táblázatot az első karakterlánc-csoport helyettesítéseiről: az első és a nulla. De még mindig van három csoport: a második oldal 2, 3 oldal, harmadik oldal 4, 5 oldal, negyedik oldal 6, 7 oldal. Ezzel a három csoporttal ugyanúgy járunk el, mint az elsővel. Az eredmény egy kiterjesztett helyettesítési táblázat!

Most implementálhat egy algoritmust, amely végrehajtja a cserét. Ehhez vesszük azokat a forráskódokat, amelyeket Andrey Vinokurov tett közzé az oldalán, lásd " Bibliográfia».

lea ebx,extented_table_simple

mov eax, [adja be a cserélendő számot]

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

sub ebx,300h ; hogy a jövőben az ebx a táblázatra mutasson

Most még egy funkció, nemcsak lecseréltük a korábbi műveleteket, hanem a számot is 8 bittel balra toltuk! Csak el kell tolnunk a számot további 3 bittel balra:

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

Az optimalizáláshoz nem tudok többet hozzáfűzni, az egyetlen dolog, amit fentebb mondtam, az az, hogy gyakrabban használjunk regisztereket, mint memóriaeléréseket. Szerintem ezek a szavak csak kezdőknek szólnak, tapasztalt emberek ezt nagyon jól megértik az én szavaim nélkül is :).

Főbb információs követelmények.

Amint azt Andrej Vinokurov cikkében kifejtette, a kulcsot két kritérium szerint választják ki:

- a bitek egyenlő valószínűségű eloszlásának kritériuma 1 és 0 között. Általában a Pearson-kritérium ("khi-négyzet") a bitek egyenlő valószínűségű eloszlásának kritériumaként működik.

Ez a kulcsot jelenti, elvileg bármilyen szám lehet. Vagyis a kulcs következő bitjének kialakításakor annak eggyel vagy nullával történő inicializálásának valószínűsége 50/50!

Felhívjuk figyelmét, hogy a kulcs nyolc elemből áll, mindegyik 32 bites, tehát összesen 32 * 8 = 256 bit van a kulcsban, és a lehetséges kulcsok száma 2 256! Nem tűnik fel? 🙂

— sorozatkritérium.

Ha megnézzük a kulcsunkat, amelyet a bekezdésben adtam meg 4.1 A kriptotranszformáció fő lépésének megvalósítása", akkor észreveszi, hogy a következő bejegyzés igaz:

Rizs. 10

Egy mondatban a k 1 értéke nem ismétlődik meg sem k 2 -ben, sem a kulcs bármely más elemében.

Vagyis az általunk a titkosítási algoritmus szempontjául választott kulcs jól megfelel a fenti két kritériumnak.

Most a helyettesítő 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ési táblák kiválasztásának fő követelménye az egyenként 4 bites méretű elemek "megismételhetetlenségének" jelensége. Mint fentebb láthatta, 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 egy példányban tartalmazza a 0h, 1h, 2h, ... , 0fh értékeket és minden ilyen értéket. Például a sorrend:

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

Ennek a követelménynek teljes mértékben megfelel, de akkor is! Nem ajánlott egy ilyen sorozatot karakterláncként kiválasztani. Mert ha egy ilyen karakterláncra támaszkodó függvény bemenetére értéket adsz, akkor a kimeneten is ugyanazt az értéket kapod! Nem hiszed? Ezután vegye a 332DA43Fh számot és nyolc ilyen sort helyettesítő táblázatként. Hajtsa végre a csereműveletet, és biztosíthatom, hogy a kimenet a 332DA43Fh szám lesz! Vagyis ugyanaz, amit a művelet bemenetére adott! És ez nem a jó forma jele a titkosításban, és így volt? 🙂

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

Hogyan tűnik könnyebbnek? És így választottuk ki például az s0 = 0Fh, 01111b elemet a fenti számból. Annak a valószínűsége, hogy most az első bitet egyre vagy nullára cseréljük, 0,5! Annak a valószínűsége, hogy a második, harmadik és negyedik bitet külön-külön vizsgálva egyesekkel vagy nullákkal cseréljük le, szintén 0,5. Az s1 = 0Eh kiválasztásakor azt a valószínűséget cseréljük le, hogy nulla bitek vagyunk, és ez „0” , nullával vagy eggyel is egyenlő - 0,5! Így e kritérium szerint az s0, s1 elemek nulla bitjeinek cseréje között nincs szabályosság! Igen, lehet helyettesíteni egyeseket, de lehet nullákat is tenni. 🙂

A táblázat e kritérium szerinti értékeléséhez összeállíthat egy táblázatot a következő képlettel 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 bitek tetszőleges kombinációja esetén a bemeneten;

— ha p = -1, akkor a j bit értéke a kimeneten mindig az i bemeneti bit inverziója;

— ha p = 0, akkor a j kimeneti bit egyenlő valószínűséggel veszi fel a 0 és 1 értéket az i bemeneti bit bármely fix értékére.

Vegyünk egy egysoros példát:

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

Bontsuk komponensekre:

Kiszámolunk egy együtthatót a fenti képlet segítségével. Hogy könnyebb legyen megérteni, hogyan történik ez, részletesebben elmagyarázom:

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

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

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

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

Egy ilyen sorrendben végrehajtott XOR műveletek szekvenciális végrehajtása után megszámoljuk az összes nem nulla érték számát, így a 6 értéket kapjuk. Így P 00 = 1-(6/2 4-1) = 0,25. Így kiderült, hogy a 0. bit értéke a kimeneten megegyezik a 0. bit értékével a bemeneten 16-ból 4 esetben;

Végső oddstábla:

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

	Bejárat
Kijárat		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 kriptoanalitikusnak van hova megfordulnia 🙂 Mindezeket a követelményeket figyelembe véve egy egyszerű felsorolás („head-on”) a megadott elméletnek megfelelő permutációs táblázatokat talált (ma - 1276 kombináció) Íme néhány ezek közül:

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

Felhasznált irodalom jegyzéke.

1. Andrej Vinokurov cikke:

A GOST 28147-89 titkosítási algoritmus, használata és megvalósítása

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

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

Itt vannak a titkosítási algoritmus megvalósításának forráskódjai.

1. Horst Feistel cikke:

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

(az előző cikkel azonos címen található)

1. Ross N. Williams:

Útmutató a CRC hibaészlelési algoritmusokhoz

Felkerült az oldalra www.wasm.hu.

Kösz.

Szeretném kifejezni köszönetemet a www.wasm.ru fórum minden látogatójának. De külön szeretném megköszönni ChS-nek, aki jelenleg SteelRat néven ismert, segített megértenem olyan dolgokat, amelyeket valószínűleg soha nem fogok megérteni, valamint segített megírni a bekezdést: " Főbb információs követelmények”, ennek a bekezdésnek a fő részét ő írta. Mélyen hálás vagyok a KSTU alkalmazottjának is. A.N. Tupolev Anikin Igor Vjacseszlavovics és bűn lenne nem megemlíteni Chris Kasperskyt, mert ő az, és Volodya / wasm.ru az utasításaiért. Ja, és kapok tőle :). Azt is szeretném megjegyezni, hogy a Sega-Zero / Callipso egy matematikai dzsungelt juttat az eszembe.

Talán ez minden, amit el szeretnék mondani.

Hálás lennék a cikkhez kapcsolódó kritikákért, kérdésekért, vagy csak tanácsért. Elérhetőségem: [e-mail védett], ICQ - 337310594.

Üdvözlettel: Evil`s Interrupt.

P.S.: Nem próbáltam senkit felülmúlni ezzel a cikkel. Azzal a szándékkal íródott, hogy megkönnyítse a GOST tanulmányozását, és ha nehézségei vannak, ez nem jelenti azt, hogy én vagyok a hibás. Légy ésszerű és türelmes, minden jót neked!

A társadalomban jól ismert "processzorteljesítmény" kifejezés egy objektív, kiszámított paraméter, amelyet flopokban mérnek. A többség azonban gigahertzben méri, naivan azt hiszi, hogy ez ugyanaz. Senki sem ismeri a "kódteljesítmény" kifejezést, és azonnal elmagyarázom, miért.

Ennek az az oka, hogy csak nemrég jöttem rá, és még nem beszéltem róla senkinek. A kódteljesítmény azonban, akárcsak a processzor teljesítménye, objektív jellemzőkkel rendelkezik, amelyek mérhetők. Ez a cikk kifejezetten a processzormag által végrehajtott kód teljesítményéről szól.

Hogyan mérhető a kód teljesítménye? Mivel erről én beszéltem először, ezért a felfedező jogán RTT-mérlegben fogom mérni;).

Most komolyan. A modern processzorokban a fő átalakítások a 32 bites számokon végzett műveletek, minden más nagyjából egzotikus. Ezért figyelembe vesszük a legfontosabb dolgot - a 32 bites számokkal végzett műveleteket. Mit gondol, hány 32 bites műveletet tud egyszerre végrehajtani egy modern processzor magja?

A diák azt válaszolja - egy, a tanára azt gondolja, és azt mondja, hogy négy, a szakember -, hogy eddig csak tizenkét műtét van.

Tehát egy olyan programkód, amely a processzor összes végrehajtó eszközét egyszerre tölti be a teljes kódvégrehajtási idő alatt, 12 RTT NIS teljesítményű lesz. Maximális! Őszintén szólva, még soha nem írtam ilyen kódot, de ebben a cikkben megpróbálok erőfeszítéseket tenni magamon.

Bebizonyítom, hogy lehetséges tizenkét 32 bites művelet egyidejű végrehajtásával rendelkező kód

A processzormagban egy végrehajtási egységet használó programkód természetesen 1 RTT teljesítményű lesz. A nyelvi fordítók által generált programok "büszkélkedhetnek" ilyen kódteljesítménnyel. magas szintés tolmácsok virtuális gépek. Nem szabad azt feltételezni, hogy az operációs rendszer feladatkezelőjében látható CPU-használati mutató objektív kritériumként szolgálhat a kód hatékonyságához. A processzor magterhelése 100% lehet, de a programkód egy végrehajtó eszközt fog használni benne (teljesítmény 1 RTT). Ebben az esetben 100%-os terhelés mellett a processzormag maximális teljesítményének 1/12-ével fog működni. Más szóval, amikor a Windows Feladatkezelő a maximális CPU-használatot mutatja, a tényleges teljesítménye 1 és 12 RTT között változhat. Látva a teljesítményablakban 100%-os terhelést bármely processzormagon, téves azt feltételezni, hogy minden végrehajtó eszköz ebben a magban működik, semmi esetre sem!

Az egyetlen kritérium a processzormag működésének közvetett értékeléséhez maximális teljesítmény lehet az energiafogyasztása és ennek eredményeként a hűtő zaja. Most, ha a hűtő zajos, akkor igen - a terhelés a maximumra ment. Ideje azonban befejezni az általános fogalmakat, és áttérni a kemény gyakorlatra.

A GOST 28147-89 hagyományos végrehajtása

Nem vagyok profi a területen információ biztonság, de még mindig ismeri a titkosítás témáját. Az általam mélyen tisztelt professzionális kriptográfussal folytatott beszélgetéseim inspiráltak arra, hogy belevágjak a kifejezetten szimmetrikus adatfolyam-titkosításba. És miután felvettem ezt a témát, igyekeztem jól csinálni, és nem csak jól, hanem gyorsan is, időegységenként maximális számú műveletet végrehajtva. Vagyis azzal a feladattal álltam szemben, hogy a programkódot a maximális RTT értékkel írjam meg.

A GOST 28147-89 szerinti kriptográfiai konverziót a kommunikációs csatornákon és a lemezmeghajtókon lévő információk titkosítására használják.

Jelenleg ennek a GOST-nak a RON-on történő szoftveres megvalósítását széles körben használják. CPU. A GOST megvalósításának jól ismert módszereiben minden titkos információ (titkosítási kulcsok, csereblokkok) bekerül véletlen hozzáférésű memória. Ez csökkenti a titkosítás megbízhatóságát, mivel a RAM-kiíratással teljesen felfedhető a kriptotranszformáció összes titkos eleme. Ezenkívül a módszer sebességkorlátozásokkal rendelkezik a kriptotranszformáció fő objektumainak az OP-ban való elhelyezkedése és az ALU végrehajtó eszközök nem teljes betöltése miatt. A modern processzorok, amelyek jól ismert módszerrel valósítják meg a titkosítási eljárást, másodpercenként 40-60 megabájt titkosítási sebességet biztosítanak. És ha valóban a végére érti, akkor a kripto konvertálás alacsony teljesítményének és gyenge biztonságának oka a helyettesítő blokk szoftveres megvalósítása. Lásd a leírását a GOST-ban az ábrán. 1.

A GOST 1.2 szakasza szerint ez a blokk tetrad (négy bites) permutációt valósít meg egy 32 bites szóban, de az x86 / 64 processzor architektúra és annak utasításkészlete nem képes hatékonyan manipulálni a tetradokat.

A helyettesítő blokk szoftveres megvalósításához speciális RAM-táblákat használnak, amelyeket a kriptofunkció inicializálásának szakaszában készítenek el. Ezek a táblák a szomszédos tetrádok helyettesítési csomópontjait 8 × 8 bites bájtos táblákká egyesítik, így a RAM-ban négy 256 bájtos tábla található.

A fejlettebb megvalósításokban ezek a táblázatok 1024 bájt méretűek (négy bájtból 256 szó). Ez azért történik, hogy a táblázatokban a helyettesítés eredményeként kapott 32 bites szó 11 pozíciójával további ciklikus eltolást hajtsanak végre (a konverziós algoritmus következő művelete a GOST szerint). Példa a GOST végrehajtására a szerint ez a módszer mellékletben látható (lemezen).

A helyettesítő blokk információi a kriptofunkció titkos összetevője (ahogyan a GOST-ban megfogalmazva, lásd a 2. ábrát).

Ezeknek a tábláknak a helyettesítési blokk kulcsaival való elhelyezése az OP-ban ellentmond a GOST követelményeinek (1.7. pont), mivel titkos információ válik hozzáférhetővé a felhasználók számára. harmadik féltől származó programok számítógépes telepítésen dolgozik. Az FSB, amely a titkosítás GOST szerinti szoftveres megvalósításait is tanúsítja, finoman szólva is lekezelően nézi ezt a jogsértést. Ha a kulcsokat az OP-ba helyezi, az FSB továbbra is „fügefalevelet” igényel - a kulcsokat XOR művelettel takarja el, akkor az OP-ban semmi sem szükséges a csereblokkokhoz, azokat tiszta szövegben tárolják.

Röviden, az FSB kihagyja a kriptoeljárás ilyen szoftveres megvalósításait, annak ellenére, hogy egy ilyen megoldás erőssége nyilvánvalóan csökken, és a GOST szerint (1.7. szakasz) megsérti saját követelményeit. És ez annak ellenére, hogy a titkosítások feltörésére jól ismert módszereket használnak egy memóriakiírás eltávolításával ...

A processzor belső regisztereiben való kulcsok és csereblokkok tárolásának kérdésére kicsit később visszatérünk (van egy szép és gyors megoldás), de egyelőre csak MMX regiszterekben tároljuk a titkosítási kulcsokat, ez megbízhatóbb.

De elég a dalszövegekből, a vizsgált téma keretein belül fontos, hogy ennek a programkódnak a teljesítménye 1 RTT-shku. Most írjunk egy kódot, amelynek teljesítménye 2 RTT.

A GOST 28147-89 többszálú megvalósítása

A titkosítási eljárások felgyorsításának egyetlen módja az ismert algoritmusban a többszálú feldolgozás bevezetése. Az algoritmus megvalósításának ilyen változtatásának az a jelentése, hogy egyszerre több adatblokkot számoljunk ki párhuzamosan.

A legtöbb programozó a párhuzamos feldolgozás alatt csak több processzormag munkáját érti, amelyeket megszakításokkal és a memóriában lévő szemaforokkal szinkronizálnak.

Van azonban egy másik változata a párhuzamos adatfeldolgozásnak egyetlen processzormagon. Hadd magyarázzam el ezt a nem nyilvánvaló gondolatot.

A modern processzorok legalább két, sőt három-hat aritmetikai logikai egységet tartalmaznak. Ezek az ALU-k (FPU-k, címaritmetikai egységek stb.) egymástól függetlenül is működhetnek, párhuzamos működésük egyetlen feltétele az átfedés nélküli szoftverobjektumok, amelyeken működnek. Más szóval, az ALU-t egyidejűleg végrehajtó utasításokban a memóriacímeknek és a regiszterszámoknak eltérőnek kell lenniük. Vagy nem szabad írási műveleteket végrehajtani a processzor különféle végrehajtó eszközei által elért közös regiszterekre és memóriacímekre.

Az összes ALU munkájának betöltését egy speciális hardverblokk vezérli a processzormagban - az ütemező, amely a végrehajtható kódon keresztül néz előre, 32-64 bájt mélységig. Ha az ütemező olyan parancsokat talál, amelyek ütközések nélkül futtathatók az ALU-n, akkor azokat egyidejűleg futtatja különböző végrehajtási egységeken. Ebben az esetben a végrehajtott parancsok számlálója a végrehajtható parancsra mutat (ilyen sémában több is van), amely után már minden parancs végrehajtásra került.

A legtöbb automatikusan (fordítók által) generált programsorozat nem tudja betölteni a processzormagban található összes ALU-t és FPU-t. Ebben az esetben a processzor hardvere tétlen, ami jelentősen csökkenti a teljesítményét. A processzorfejlesztők megértik ezt, és olyan módokat vezetnek be, amelyek növelik a magfrekvenciát, ha a berendezés nincs teljesen kihasználva. A Hyper kereskedési rendszereket is erre tervezték, ezzel a rendszerrel fogom a jövőben maximálisan „nyomni” a kódot.

A fordítók, még a leginkább optimalizáltak is, és még inkább a virtuális gépek motorjai, nem tudnak teljesítmény szempontjából optimalizált kódot generálni. Ilyen optimalizált kódot csak mérnöki ismeretekkel rendelkező programozó tud írni, az írási eszköz pedig kizárólag az assembler.

A több független programszál egy processzormagon való végrehajtásának lehetőségének jellemző példája a GOST implementáció, amely egyetlen processzormagon két szálban fut le. A kód ötlete egyszerű: két adatblokk van a titkosításra/dekódolásra, de egy processzormag végzi el az átalakítást. E két adatblokk átalakítása egymás után is végrehajtható, és ez eddig is megtörtént. Ebben az esetben az átalakítások végrehajtásához szükséges idő megduplázódik.

De tehet másként is: különböző adatblokkok feldolgozásához kapcsolódó alternatív parancsok. Grafikusan ezeket a lehetőségeket az ábra mutatja. 3.

Az ábrán a felső példa két független adatblokk feldolgozási sorrendjét mutatja be. Először az első blokk feldolgozása történik meg, majd a processzor továbblép a második blokk feldolgozására. Az így kapott idő természetesen megegyezik egy blokk feldolgozásához szükséges idő kétszeresével, és a processzormag végrehajtási egységei nincsenek teljesen betöltve.

Az alábbiakban bemutatunk egy példát különböző feldolgozási szálakból származó interleaving parancsokkal. Ebben az esetben a különböző adatblokkokhoz kapcsolódó parancsok interleavelve vannak. Az ütemező kiválasztja az egymástól független utasításokat, és végrehajtásra továbbítja az ALU1-nek és ALU2-nek. Az első és a második szál parancsainak csoportosítása ezeken az ALU-kon automatikusan megtörténik, mivel az ütemező műveleti algoritmusa tartalmazza a parancsok csoportosítását áttétellel ugyanazon a végrehajtó eszközön lévő közös adatok szerint.

Ahhoz, hogy az ilyen programkód ALU tétlenségi idő nélkül működjön, minden programszálnak saját regiszterkészlettel kell működnie. A gyorsítótár ebben a sémában szűk keresztmetszetté válik (csak két adatkimeneti portja van), ezért a kulcsokat MMX regiszterekben tároljuk. Mivel ebben az esetben a helyettesítő (és shift) csomópontok csak olvashatóak a memóriában, mindkét programszál megoszthatja őket.

Ez természetesen egy nagyon leegyszerűsített magyarázata a programszálak párhuzamos végrehajtásának elvének egyetlen magon, a valóságban minden sokkal bonyolultabb. A gyakorlatban figyelembe kell venni a végrehajtási egységek pipeline architektúráját, a gyorsítótárhoz és a RON-regiszterek blokkjához való egyidejű hozzáférés korlátozásait, a címaritmetikai csomópontok, kapcsolók jelenlétét és még sok minden mást... Tehát ez egy téma olyan szakemberek számára, akik ... egy kéz ujjain megszámolhatók.

A párhuzamos titkosítási módszert csak a 64 bites processzor üzemmódban valósítják meg hatékonyan, mivel ebben az üzemmódban van elegendő RON (akár 16 darab!). A GOST e módszer szerinti megvalósításának példája a 2. függelékben látható (lemezen).

Nyilvánvaló, hogy ennek a GOST-nak a kódteljesítménye 2 RTT. Most nézzük meg, hogyan befolyásolja ez a végrehajtási időt.

Egy adatfolyam titkosítási ciklusa (1. függelék) 352 ciklus, és ezalatt 8 bájt adatot számítanak ki, a GOST kétfolyamos megvalósításához (2. melléklet) 416 processzorciklus szükséges, de 16 bájtot számítanak ki. Így a kapott konverziós sebesség 80-ról 144 megabájtra nő egy 3,6 GHz-es processzornál.

Érdekes képet kapunk: a kód pontosan kétszer annyi utasítást tartalmaz, és csak 15%-kal tovább tart, de azt hiszem, az olvasók már megértették ennek a jelenségnek az okát ...

Elméletileg a második példából származó kódot ugyanannyi ciklusban kellene végrehajtani, mint az első példában szereplő kódot, de az ütemező csomópont fejlesztés alatt áll, annak ellenére, hogy a mérnökök az Intel által, hanem az emberek is, és mindannyian messze vagyunk a tökéletestől. Így lehetőség nyílik létrehozásuk hatékonyságának értékelésére. Ez a kód AMD processzoron is működik, és összehasonlíthatja az eredményeiket.

Ha valaki nem fogad szót, akkor az ilyen hitetleneknek óraszámlálós tesztprogramok vannak a lemezen. Programok be forráskódok, természetesen assemblerben, így lehetőség nyílik szavaim ellenőrzésére, és egyben a professzionális kódolás trükkjeire is.

A modern processzorok SSE-regisztereinek és AVX-parancsainak használata a GOST 28147-89 végrehajtásához

A modern x86/64 architektúra processzorok 16 bájtos SSE regisztereket és speciális FPU-kat (legalább kettőt) tartalmaznak, amelyek különféle műveleteket hajtanak végre ezeken a regisztereken. Lehetőség van a GOST megvalósítására ezen a berendezésen, és ebben az esetben a cserecsomópontok nem táblázatok formájában helyezhetők el a RAM-ban, hanem közvetlenül a dedikált SSE regiszterekben.

Egy SSE-regiszteren egyszerre két 16 soros tábla helyezhető el. Így négy SSE regiszter teljes mértékben befogadja az összes helyettesítő táblát. Az ilyen elhelyezés egyetlen feltétele az interleaving követelmény, amely szerint az azonos bájt tetradjait különböző SSE regiszterekben kell elhelyezni. Ezenkívül a bemeneti bájtok alsó és felső tetradjait célszerű az SSE regiszterek alsó és felső tetradjaiba helyezni.

Ezeket a követelményeket a meglévő AVX-parancskészlet optimalizálása határozza meg. Így az SSE regiszter minden bájtja a helyettesítő blokk bemeneti regiszterének különböző bájtjainak megfelelő két tetradot tartalmaz majd, míg a bájt pozíciója az SSE regiszterben egyedileg megfelel a helyettesítési blokk helyettesítési táblájában szereplő indexnek.

Az SSE regiszterekben a helyettesítő csomópontok egyik lehetséges elhelyezésének diagramja az 1. ábrán látható. 4.

A helyettesítő csomópontok titkos információinak az SSE-regiszterekben való elhelyezése növeli a kriptoeljárás biztonságát, de ezeknek a titkos információknak a teljes elkülönítése a következő feltételek mellett lehetséges:

• A processzormagot hipervizor gazdamódba helyezték, és a megszakítási blokkot (APIC) erőszakkal letiltották. Ebben az esetben a processzormag teljesen el van szigetelve az operációs rendszertől és a számítástechnikai telepítésen futó alkalmazásoktól.
• Az SSE regiszterek betöltése és a számítási mag elkülönítése az operációs rendszer indítása előtt megtörténik, optimális, ha ezeket az eljárásokat a megbízható rendszerindítási modulból (TDM) hajtjuk végre.
• A GOST szerinti kriptoeljárások programjai a számítási egység (BIOS vagy MDZ flash memória) nem módosítható memóriaterületére kerülnek.

Ezeknek a követelményeknek való megfelelés biztosítja a teljes elszigeteltséget és megváltoztathatatlanságot programkód kriptoeljárásokat és az azokban használt titkos információkat.

A tetradok SSE regisztereiből való hatékony mintavételhez az FPU-kban elérhető több bemenetű bájtkapcsolókat használják. Ezek a kapcsolók lehetővé teszik az átvitelt a forrás bármely bájtjáról a cél bármely bájtjára, egy speciális SSE indexregiszterben található indexek segítségével. Ezenkívül az átvitel párhuzamosan történik az SSE-regiszter-vevő mind a 16 bájtján.

Az SSE regisztereken lévő helyettesítő tároló csomópontok és az FPU egységek több bemenetes kapcsolója révén lehetőség van a következő transzformáció megszervezésére a helyettesítő egységben (5. ábra).

Ebben a sémában az egyes tetrádok bemeneti regisztere beállítja a megfelelő kapcsoló címét, amely információt továbbít a cserecsomópont-meghajtóktól a kimeneti regiszterhez az adatbuszon keresztül. Egy ilyen rendszer háromféleképpen szervezhető meg:

• Készítsen megfelelő chiptervet, de ez fantasztikus számunkra.
• A mikrokód átprogramozása és saját processzorutasítás létrehozása ennek a funkciónak a meglévő processzorokon való megvalósításához már nem képzelet, de sajnos a jelenlegi körülmények között irreális.
• Írjon programot a hivatalos AVX parancsokkal. A lehetőség, bár nem túl hatékony, de „itt és most” megvalósíthatjuk. Tehát ezt fogjuk csinálni a következőben.

A kapcsolókat egy speciális háromcímes AVX VPSHUFB parancs vezérli. Első operandusa a kapcsolókról érkező információ vevője, a második pedig a forrás, amelyhez a kapcsolók bemenetei csatlakoznak. A harmadik operandus a kapcsolók vezérlőregisztere, amelynek minden bájtja egy megfelelő kapcsolóhoz van társítva; a benne lévő érték megadja annak az iránynak a számát, ahonnan a kapcsoló információt olvas. A parancs leírását a hivatalos Intel dokumentációból lásd a 2. ábrán. 5. Az ábrán A 6. ábra mutatja ennek a parancsnak a működését - az SSE regisztereknek csak a fele látható, a második felében minden hasonló.

A kapcsoló csak a legkisebb jelentőségű négy bitet használja a kapcsolási irány meghatározásához, minden bájt utolsó bitje a megfelelő vevő bájt nullára kényszerítésére szolgál, de erre a kapcsoló funkcióra esetünkben még nincs szükség.

Írtak egy programot FPU-kapcsolókon keresztül válogatott notebookokkal, de még csak nem is tettem bele az alkalmazásba - túl rossz. 128 bites regiszter és csak 32 bit használata nem professzionális.

Ahogy mondani szokták: „A mi befejezésünk a horizont”, hát úgy nyomkodd ki... megnyomjuk és zacskóba rakjuk!

Ez nem játék a szavakkal, hanem egy durva FPU-valóság – az SSE regiszterek egyenlő részekre oszthatók, és ezeken a részeken ugyanazok a transzformációk hajthatók végre egyetlen paranccsal. Annak érdekében, hogy a processzor megértse ezt, van egy "P" varázsbetű - egy csomag, amely a parancs-mnemonika elé kerül, és nem kevésbé mágikus "Q", "D", "W", "B" betűk. végére kerülnek, és deklarálják, hogy az SSE regiszterek milyen részekre vannak felosztva ebben a parancsban.

Érdekel minket a kötegelt mód az SSE regiszter négy 32 bites blokkra bontásával; ennek megfelelően minden parancs előtagja "P" lesz, és egy "D" szimbólum fejeződik be. Ez lehetővé teszi négy 32 bites blokk párhuzamos feldolgozását egy processzorutasítással, azaz négy adatblokk párhuzamos kiszámítását.

Az ezt a módszert megvalósító program a 3. függelékben található, ott minden magyarázat megtalálható.

Azonban nyomj, hát nyomj! A modern processzorok legalább két FPU-val rendelkeznek, és ezek teljes betöltéséhez két független utasításfolyam használható. Ha megfelelően beilleszti a független adatfolyamokból származó parancsokat, akkor teljesen betöltheti mindkét FPU-t, és egyszerre nyolc párhuzamosan feldolgozott adatfolyamot kaphat. Egy ilyen programot írtak, és a 4. függelékben láthatja, de alaposan meg kell néznie - megőrülhet. Ezt hívják úgy, hogy "a kód nem mindenkinek szól...".

Kibocsátási ár

Az SSE regiszterek használata a cserecsomópontok tárolására érthető - bizonyos garanciát ad a titkos információk izolálására, de magának a kriptofunkciónak az FPU-n történő kiszámításának értelme nem nyilvánvaló. Ezért a szabványos eljárások végrehajtási idejét a GOST szerinti közvetlen helyettesítési módszerrel mértük négy és nyolc adatfolyamra.

Négy szálnál 472 processzorciklus végrehajtási sebességet kaptunk. Így egy 3,6 GHz-es processzornál egy szál 59 megabájt/s, négy szál pedig 236 megabájt/s sebességgel számít.

Nyolc szálnál 580 processzorciklus végrehajtási sebességet kaptunk. Így egy 3,6 GHz-es processzornál egy szál 49 megabájt/másodperc, nyolc szál pedig 392 megabájt/s sebességgel számít.

Ahogy az olvasó észreveheti, a 3. példában szereplő kód 4 RTT, míg a 4. példában szereplő kód 8 RTT átviteli sebességgel rendelkezik. Ezekben a példákban az SSE regisztereken a minták ugyanazok, mint a RON használatakor, csak az ütemező csökkentette a hatékonyságát. Most 20%-kal hosszabb időtartamot biztosít a kód hosszának kétszeresére.

Ezen túlmenően ezeket az eredményeket a mindkettőben elérhető univerzális AVX parancsok használatával kaptuk Intel processzorokés AMD processzorokban. Ha AMD processzorra optimalizál, az eredmény sokkal jobb lesz. Ellentrendnek hangzik, de mégis igaz, és itt van, miért: AMD processzorok rendelkezik egy további utasításkészlettel, az úgynevezett XOP kiterjesztéssel, és ebben kiegészítő készlet vannak olyan parancsok, amelyek nagyban leegyszerűsítik a GOST algoritmus megvalósítását.

Ez a byte-ok logikai csomageltolása és a dupla szavak csomagciklikus eltolása parancsaira vonatkozik. A 3. és 4. függelékben szereplő példák univerzális parancssorokat használnak, amelyek végrehajtják a szükséges átalakítást: az első esetben egy "extra" parancs, a másik esetben pedig négy extra parancs egyszerre. Tehát vannak optimalizálási tartalékok, és jelentősek.

Ha további optimalizálásról beszélünk, érdemes megjegyezni a 256 bites regiszterek (YMM-regiszterek) jelenlétét, amelyek segítségével elméletileg megduplázható a számítási sebesség. De ez egyelőre csak perspektíva, jelenleg a processzorok nagyon lelassulnak a 256 bites utasítások végrehajtása során (az FPU-k útszélessége 128 bit). Kísérletek kimutatták, hogy a modern processzorokon az YMM regisztereken lévő 16 szál számlálása nem ad nyereséget. De ez csak egyelőre, az új processzormodelleken kétségtelenül megnő a 256 bites utasítások sebessége, majd a 16 párhuzamos szál alkalmazása válik célszerűvé és a kriptoeljárás sebességének még nagyobb növekedéséhez vezet.

Elméletileg másodpercenként 600-700 megabájt sebességgel számolhatunk, ha a processzor két FPU-val rendelkezik, egyenként 256 bites munkaút-szélességgel. Ebben az esetben 16 RTT hatékonyságú kódírásról beszélhetünk, és ez nem fantázia, hanem a közeljövő.

vegyes mód

Ismét felmerül a regiszterek számának kérdése, ezek nem elegendőek egy ilyen algoritmus előmozdításához. De a hiper kereskedési mód segíteni fog nekünk. A processzormag egy második regiszterkészlettel rendelkezik logikai processzor módban. Ezért ugyanazt a kódot egyszerre két logikai processzoron hajtjuk végre. Ebben a módban természetesen nem lesz több végrehajtó eszközünk, de a váltakozás miatt az összes végrehajtó eszközből teljes terhelést kaphatunk.

50%-os növekedéssel itt nem lehet számolni, a szűk keresztmetszet a cache memória, ahol a technológiai maszkokat tárolják, de így is 100 megabájt plusz növekedést kaphatunk. Ez az opció nem szerepel a mellékletekben (a makrók megegyeznek a 8 RTT kódban használtakkal), de elérhető program fájlok. Tehát ha valaki nem hisz az 500 megabájtos másodpercenkénti titkosítás lehetőségében egyetlen processzormagon, futtassa le a tesztfájlokat. Vannak megjegyzésekkel ellátott szövegek is, hogy ne gondolja senki, hogy ravasz vagyok.

Ez a fókusz csak az Intel processzorokon lehetséges, az AMD-nek csak két FPU-ja van két processzormodulonként (a hiperkereskedési módhoz hasonlóan). De van még négy ALU, amelyeket bűn nem használni.

A Bulldozer processzormoduljait a hiper kereskedési módhoz hasonló módba hajthatja, de az egyik szálban különböző modulokon futtathatja a RON-ra, egy másik szálban SSE-regiszterekre, és ugyanazt a 12 RTT-t kapja. Nem teszteltem ezt a lehetőséget, de úgy gondolom, hogy a 12 RTT kódja hatékonyabban fog működni AMD-n. Aki szeretne, az kipróbálhatja, a tesztprogramok könnyen beállíthatók a "buldózereken" való működésre.

Kinek van rá szüksége?

Komoly kérdés, de egyszerű válasz – mindenkinek szüksége van rá. Hamarosan mindannyian leülünk a felhőkre, ott tároljuk az adatokat és a programokat is, és ott, ó, hogy szeretnéd felszerelni a saját, privát sarkodat. Ehhez titkosítania kell a forgalmat, és a kriptokonverzió sebessége lesz a fő meghatározó tényező a felhőben való kényelmes munkavégzésben. A titkosítási algoritmusaink közül kicsi a választék – akár GOST, akár AES.

Sőt, furcsa módon a processzorokba épített AES algoritmus titkosítása jóval lassabbnak bizonyul, a tesztek 100-150 megabájtos másodpercenkénti sebességet mutatnak, és ez az algoritmus hardveres megvalósításával van így! A probléma az egyszálú számlálásban és a bájtokkal működő helyettesítő blokkban van (egy 256 soros táblázat). Tehát a GOST hatékonyabbnak bizonyult az x86 / 64 architektúrán való megvalósításban, ki gondolta volna ...

Ez akkor van, ha a titkosítási sebesség elért szintjéről beszélünk. És ha szem előtt tartjuk az elméleti finomításokat a kód hatékonyságának javítása terén, akkor valószínűleg senkinek sincs szüksége rá. Gyakorlatilag nincsenek 3-6 RTT szintű szakemberek, a fordítók általában 1-2,5 RTT szintű kódot generálnak, és a programozók többsége nem ismeri az assemblert, és ha ismeri a helyesírását, akkor nem érti a készülék eszközét. modern processzor. És ezen ismeretek nélkül mi az assembler, mi a valamiféle SI-sharp - mindegy.

De nem minden olyan szomorú: az "alsó sorban" egy hét álmatlan éjszakát követően van egy új algoritmus a GOST végrehajtására, amelyet bűn nem szabadalmaztatni. A szabadalmi kérelmeket pedig (akár hármat is) már elkészítették és be is nyújtották, szóval, uraim, üzletemberek, álljatok sorba - nőknek és gyerekeknek kedvezmény jár.

Ez az algoritmus titkosítási algoritmusként való használatához kötelező kormányzati szervezetek RF és számos kereskedelmi.

Az algoritmus leírása

Az algoritmus sémája 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 szoftveres vagy hardveres megvalósítását.

A GOST 28147-89 algoritmus 64 bites blokkokban titkosítja az információkat, amelyek két 32 bites alblokkra (N1 és N2) vannak osztva. Az N1 alblokkot meghatározott módon dolgozzák fel, majd hozzáadják az értéket

az N2 alblokk értékkel (az összeadás modulo 2 történik), akkor az alblokkok felcserélődnek. Az ilyen transzformációt 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 (leírjuk alább). Minden körben a következő műveleteket hajtják végre:

1. Kulcsfedés. A /VI alblokk tartalma modulo 2 32 hozzáadásra kerül a kulcs Kx részéhez.

A GOST 28147-89 algoritmus titkosítási kulcsának mérete 256 bit, a Kx pedig 32 bites része, azaz egy 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 folyamat során a körszámtól és az algoritmus működési módjától függően ezek közül az alkulcsok egyikét használjuk.

Rizs. 3.1. A GOST 28147- algoritmus sémája

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

2. Táblázatos csere. A kulcs átfedése után a /VI alblokk 8, 4 bites részre van felosztva, amelyek mindegyikének értéke egyedileg cserélődik az alblokk ezen részének helyettesítési táblázata szerint. A táblahelyettesítéseket (Substitution box, S-box) gyakran alkalmazzák a modern titkosítási algoritmusok, ezért érdemes ezeket részletesebben is átgondolni.

A táblapótlást így használjuk: egy bizonyos dimenziójú (jelen esetben 4 bites) adatblokk kerül a bemenetre, amelynek numerikus ábrázolása határozza meg a kimeneti érték számát. Például van egy S-boxunk a következő formájú:

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

Jöjjön a 4 bites „0100” blokk a bemenetre, azaz az értéke 4. 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átható, az algoritmus sémája nagyon egyszerű, ami azt jelenti, hogy az adattitkosítás legnagyobb terhe a helyettesítő táblákra hárul. Sajnos az algoritmusnak megvan az a tulajdonsága, hogy vannak "gyenge" helyettesítési táblák, amelyek segítségével kriptoanalitikus módszerekkel feltárható az algoritmus. 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ódok

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

□ egyszerű csere mód;

□ gamma mód;

P játékmód visszajelzéssel;

□ melléklet-utánzatok gyártási módja.

Ezek a módok némileg eltérnek az általánosan elfogadott módoktól (lásd az 1.4. fejezetben), ezért érdemes ezeket részletesebben is megvizsgálni.

Ezeknek a módoknak más a célja, de ugyanazt a titkosítási átalakítást használják, mint fentebb leírtuk.

Egyszerű csere mód

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

□ KO, Kl, K2, K3, K4, K5, Kb, AG7, KO, ATI stb. - 1-24. körben;

□ K1, Kb, K5, K4, K3, K2, K\, KO - a 25-32. körben.

Az egyszerű helyettesítési módban a visszafejtés pontosan ugyanúgy történik, de az alkulcsok használatának kissé eltérő sorrendjében:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - 1-8 körben;

□ KP, Kb, K5, K4, K3, K2, K\, KO, K1, Kb stb. - 9-től 32-ig.

A standard EKB módhoz hasonlóan a blokkok külön titkosítása miatt az egyszerű csere mód a tényleges adatok titkosítására kifejezetten nem javasolt; csak más titkosítási kulcsok titkosításához használható többkulcsos sémákban.

Gamma mód

Gamma módban (3.3. ábra) a nyílt szöveg minden egyes blokkja modulo 2 bitenként hozzáadódik a titkosítás 64 bites gamma blokkjához. A gamma titkosítás egy speciális sorozat, amelyet a fent leírt transzformációk segítségével állítanak elő az alábbiak szerint:

1. Az N1 és N2 regiszterekben a kezdeti kitöltést írják - egy 64 bites értéket, amelyet "szinkron üzenetnek" neveznek (a szinkronizálási üzenet valójában az inicializálási vektor analógja CBC, CFB és OFB módban ).

2. A /VI és N2 regiszterek tartalma (jelen esetben a szinkron üzenetek) titkosításra kerül az egyszerű csere módban.

3. Az N1 tartalmát modulo (2 32 - 1) adjuk hozzá a CI = 2 24 + 2 16 + 2 8 + 4 konstanssal, az összeadás eredménye a /VI regiszterbe kerül.

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

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

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

A visszafejtéshez ugyanúgy gamma generálódik, majd ismét az XOR műveletet alkalmazzuk a rejtjelezett szövegre és a gamma bitekre.

Ugyanazon gamma titkosítás létrehozásához a kriptogramot visszafejtő felhasználónak ugyanazzal a kulccsal és ugyanazzal a szinkronizálási üzenet értékkel kell rendelkeznie, mint az információ titkosításához. Ellenkező esetben nem fogja tudni lekérni az eredeti szöveget a titkosított szövegről.

A GOST 28147-89 algoritmus legtöbb megvalósításában a szinkronizálási üzenet nem titkos elem, de a szinkronizálási üzenet ugyanolyan titkos lehet, mint a titkosítási kulcs. Ebben az esetben úgy tekinthetjük, hogy az algoritmus kulcsának effektív hosszát (256 bit) a szinkronüzenet további 64 bitjével növeljük, ami további kulcselemnek tekinthető.

Visszacsatolás gamma mód

A visszacsatoló gamma módban a 2. blokktól kezdve a /VI és az L/2 regiszterek nem az előző gamma blokkal töltődnek fel, hanem az előző nyílt szöveg blokk titkosításának eredményével (3.4. ábra). Az első blokk ebben a módban pontosan ugyanúgy jön létre, mint az előző.

Rizs. 3.4. A gamma titkosítás generálása gamma módban visszajelzéssel

Imitátorgenerálási mód

A hamis egy titkosítási kulcs segítségével kiszámított kriptográfiai ellenőrző összeg, amelyet az üzenetek integritásának ellenőrzésére terveztek. Kiszámításához a GOST 28147-89 algoritmus speciális módja van.

Az utánzat előtag generálása a következőképpen történik:

1. Az első 64 bites információblokkot, amelyre a megszemélyesítő számít, az N1 és N2 regiszterekbe írjuk, és redukált egyszerű helyettesítési módban titkosítjuk, amelyben a 32-ből az első 16 kört végrehajtjuk.

2. A kapott eredményt modulo 2 összegzi a következő információblokkkal, az eredményt N1-be és N2-be mentve.

3. M és N2 ismét az egyszerű csere redukált módjában van titkosítva, és így tovább az utolsó információblokkig.

Előtagnak tekintjük az N1 és N2 regiszterek 64 bites eredő tartalmát vagy annak egy részét. Leggyakrabban 32 bites utánzó előtagot használnak, vagyis a regiszterek tartalmának felét. Ez elég, mert mint minden ellenőrző összeg, az utánzó előtag elsősorban az információ véletlen torzulása elleni védelmet szolgálja. Az adatok szándékos módosítása elleni védelem érdekében más - elsősorban elektronikus - kriptográfiai módszereket alkalmaznak digitális aláírás(lásd az 1.1 pontot).

Az utánzat előtag a következőképpen használatos:

1. Bármilyen információ titkosításakor a rendszer kiszámítja a nyílt szöveg imitátort, és a titkosított szöveggel együtt elküldi.

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

3. Ha a számított és az elküldött utánzati előtagok nem egyeznek, akkor a titkosított szöveg torzult az átvitel során, vagy hibás kulcsokat használtak a visszafejtés során.

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

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

Az algoritmus kriptográfiai erőssége

1994-ben a GOST 28147-89 algoritmus leírását lefordították angolra és közzétették; ezt követően kezdtek megjelenni külföldi szakértők által végzett elemzésének eredményei; azonban jelentős ideig nem találtak megvalósítható támadást.

□ nagy kulcshossz - 256 bit; a titkos szinkronizálási üzenettel együtt az effektív kulcshossz 320 bitre nő;

□ 32 átalakítási kör; már 8 kör után eléri a bemeneti adatok szórásának teljes hatását: a nyílt szöveg blokk egy bitjének megváltoztatása a titkosított szöveg blokk összes bitjét érinti, és fordítva, azaz többszörös biztonsági ráhagyás van.

Tekintsük a GOST 28147-89 algoritmus kriptográfiai elemzésének eredményeit.

A helyettesítési táblák elemzése

Mivel a helyettesítési táblázatok nem szerepelnek a szabványban, számos munka (például in) azt sugallja, hogy egy „illetékes szervezet” „jó” és „rossz” helyettesítési táblázatokat is kiadhat. A híres szakértő, Bruce Schneier azonban „pletykáknak” nevezi az ilyen feltételezéseket. Jól látható, hogy az algoritmus kriptográfiai erőssége nagymértékben függ a felhasznált helyettesítési táblák tulajdonságaitól, illetve vannak gyenge helyettesítési táblák (lásd fentebb egy példát), amelyek használata egyszerűsítheti az algoritmus támadását. Mindazonáltal a különböző helyettesítési táblák használatának lehetősége nagyon érdemes ötletnek tűnik, amit a következő két tény támaszt alá 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ési táblák sajátos tulajdonságait használják; más táblák használatakor a kriptoanalízist elölről kell kezdeni;

□ Kísérleteket tettek a DES megerősítésére a lineáris és differenciális kriptoanalízis ellen erősebb helyettesítési táblák használatával; ilyen, valóban stabilabb táblázatokat 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 a szabványban mereven definiáltak, illetve az algoritmus implementációi valószínűleg nem támogatják a táblák más táblákra való cseréjét.

Számos munkában (például , és ) tévesen arra a következtetésre jutottak, hogy a GOST 28147-89 algoritmus titkos helyettesítési táblái a kulcs részét képezhetik, és növelhetik annak effektív hosszát (ami nem jelentős, mivel az algoritmusnak van egy nagyon nagy 256 bites kulcs). A munka azonban bebizonyítja, hogy a titkos helyettesítési táblák kiszámíthatók a következő, gyakorlatilag is alkalmazható támadás segítségével:

1. Állítsa be a null kulcsot, és keresse meg a "null vektort", azaz a z = /(0) értéket, ahol /() az algoritmus kerek függvénye. Ez a szakasz körülbelül 2 titkosítási műveletet vesz igénybe.

2. A nulla vektor segítségével kiszámítjuk a helyettesítési táblázatok értékeit, ami legfeljebb 2 11 műveletet vesz igénybe.

Algoritmusmódosítások és elemzésük

A munkában a GOST 28147-89 algoritmus módosításainak kriptoanalízisét végezték el:

□ a GOST-H algoritmus, amelyben az eredeti algoritmushoz képest megváltozik az alkulcsok használatának sorrendje, azaz körökben a 25.-től a 32. részkulcsig direkt sorrendben, azaz az előzőhöz hasonló módon kerül felhasználásra. az algoritmus körei ;

□ 20 körből álló GOST® algoritmus, amely XOR-t használ a modulo 2 32 helyett a kulcs átfedéséhez.

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ő rendelkezik gyenge kulcsosztályokkal. Érdemes megjegyezni, hogy a GOST© kriptoanalízis szempontjából a munka szóról szóra megismétli a GOST 28147-89 algoritmus kriptoanalízissel foglalkozó részét, amely 2000-ben jelent meg egy jól ismert műben (az eredetire való hivatkozás nélkül). Ez megkérdőjelezi a mű szerzőinek szakmai felkészültségét és egyéb eredményeit.

A munka egy nagyon érdekes módosítását javasolja az algoritmusnak: az S \ ... Ss tábláknak szükségszerűen eltérőnek kell lenniük; az algoritmus minden körében ezeket egy bizonyos törvény szerint permutálni kell. Ez a permutáció függhet a titkosítási kulcstól, vagy lehet titkos (azaz egy nagyobb titkosítási kulcs része, mint az eredeti 256 bites kulcs). Mindkét lehetőség szerzőik szerint jelentősen növeli az algoritmus ellenállását a lineáris és differenciális kriptoanalízissel szemben.

És a munka még egy, a helyettesítési táblákhoz kapcsolódó módosítást tartalmaz, amelyben a helyettesítési táblák titkosítási kulcson alapuló kiszámításának egyik lehetséges módszerét elemzik. 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 lehetséges sebezhetőségéhez vezet.

Teljeskörű algoritmus-elemzés

Vannak támadások a teljes körű GOST 28147-89 ellen is, minden módosítás nélkül. Az egyik első nyitott munka, amelyben az algoritmus elemzését elvégezték, egy jól ismert munka, olyan támadásoknak szentelték, amelyek számos jól ismert titkosítási algoritmus kulcsbővítési eljárásának gyengeségeit használják ki. Különösen a GOST 28147-89 teljes körű algoritmus bontható meg differenciális kriptográfiai elemzéssel összekapcsolt kulcsokon, de csak akkor, ha gyenge helyettesítési táblákat használnak. Az algoritmus 24 körös változata (amelyből az első 8 kör hiányzik) ugyanúgy megnyílik bármely helyettesítési táblához, de az erős helyettesítési táblázatok (például a -ban megadottak) teljesen kivitelezhetetlenné teszik az ilyen támadást.

A hazai tudósok, A. G. Rostovtsev és E. B. Makhovenko 2001-ben egy alapvetően új kriptoanalízis-módszert javasoltak (a szerzők szerint ez lényegesen hatékonyabb, mint a lineáris és differenciális kriptoanalízis), azáltal, hogy a titkosított szövegnek és a kívánt értéknek megfelelő ismert nyílt szövegből objektív függvényt alkotnak. és megtaláljuk a kulcs valódi értékének megfelelő szélsőértékét. 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öveggel és a megfelelő titkosított szövegekkel, meglehetősen alacsony bonyolultsággal. Az algoritmus kriptoanalízise a munkában folytatódik.

2004-ben koreai szakértők egy csoportja olyan támadást javasolt, amellyel a kapcsolódó kulcsok differenciális kriptoanalízise segítségével 91,7%-os valószínűséggel 12 bitnyi titkos kulcsot lehet megszerezni. A támadáshoz 235 kiválasztott egyszerű szövegre és 236 titkosítási műveletre van szükség. Mint látható, ezt a támadást, gyakorlatilag használhatatlan az algoritmus valódi megnyitásához.