Standard de criptare a datelor interne. Standard de criptare a datelor interne Algoritm de conversie criptografică GOST 28147 89

Scurtă descriere a cifrului

GOST 28147-89 - Standardul sovietic și rus pentru criptarea simetrică, introdus în 1990, este, de asemenea, un standard CIS. Nume complet - „GOST 28147-89 Sisteme de procesare a informațiilor. Protecție criptografică. Algoritmul de transformare criptografică”. Algoritm de cifrare bloc. Când se utilizează metoda de criptare cu gamma, poate îndeplini funcțiile unui algoritm de criptare de flux.

GOST 28147-89 este un cifr de bloc cu o cheie de 256 de biți și 32 de cicluri de conversie, care funcționează cu blocuri de 64 de biți. Baza algoritmului de cifrare este Rețeaua Feistel. Modul de criptare de bază conform GOST 28147-89 este modul de înlocuire simplu (de asemenea, sunt definite moduri mai complexe - gamma, gamma cu părereși modul de inserare simulat).

Cum funcționează algoritmul

Algoritmul nu este fundamental diferit de DES. Conține și cicluri de criptare (sunt 32) conform schemei Feistel (Fig. 2.9.).

Orez. 2.9. Runde de criptare ale algoritmului GOST 28147-89.

Pentru a genera subchei, cheia originală de 256 de biți este împărțită în opt blocuri de 32 de biți: k 1 …k 8 . Cheile k 9 ... k 24 sunt o repetare ciclică a tastelor k 1 ... k 8 (numerotate de la cei mai puțin semnificativi biți la cei mai semnificativi). Cheile k 25 ...k 32 sunt cheile k 1 ...k 8 mergând în ordine inversă.

După ce toate cele 32 de runde ale algoritmului sunt finalizate, blocurile A 33 și B 33 sunt lipite împreună (rețineți că A 33 devine bitul cel mai semnificativ, iar B 33 devine bitul cel mai puțin semnificativ) - rezultatul este rezultatul algoritmului.

Funcţie f(A i ,K i) se calculează după cum urmează: A i și Ki sunt adăugate modulo 2 32 , apoi rezultatul este împărțit în opt subsecvențe de 4 biți, fiecare dintre acestea fiind alimentată la intrarea proprie. nodul tabel de substituție(în ordinea crescătoare a priorității biților), numită mai jos S-bloc. Numărul total de blocuri GOST S este de opt, adică același cu numărul de subsecvențe. Fiecare S-bloc reprezintă o permutare a numerelor de la 0 la 15. Prima subsecvență de 4 biți cade pe intrarea primei S-box, a doua - pe intrarea celei de-a doua, etc. Ieșirile tuturor celor opt S-box sunt combinate în un cuvânt de 32 de biți, apoi întregul cuvânt este deplasat ciclic la stânga (la cei mai semnificativi biți) cu 11 biți. Toate cele opt cutii S pot fi diferite. De fapt, ele pot fi un material cheie suplimentar, dar cel mai adesea sunt un parametru de schemă care este comun unui anumit grup de utilizatori. Textul standardului indică faptul că livrarea de umplere a unităților de înlocuire (blocuri S) se efectuează în modul prescris, de exemplu. dezvoltator de algoritmi. Comunitatea dezvoltatorilor rusi CIPF a fost de acord asupra nodurilor de înlocuire utilizate pe Internet.

Decriptarea se realizează în același mod ca și criptarea, dar ordinea subcheilor k i este inversată.

Moduri de funcționare ale algoritmului GOST 28147-89

Algoritmul GOST 28147-89 are patru moduri de funcționare.

1. Modulînlocuire simplă acceptă date ca intrare, a căror dimensiune este un multiplu de 64 de biți. Rezultatul criptării este textul de intrare, convertit în blocuri de 64 de biți în cazul criptării cu ciclul „32-3”, iar în cazul decriptării - cu ciclul „32-P”.

2. Modulscalare acceptă date de orice dimensiune ca intrare, precum și un parametru suplimentar de 64 de biți - mesaj de sincronizare. În timpul funcționării, mesajul de sincronizare este convertit în ciclul „32-Z”, rezultatul este împărțit în două părți. Prima parte se adaugă modulo 2 32 cu o valoare constantă de 1010101 16 . Dacă a doua parte este egală cu 2 32 -1, atunci valoarea sa nu se modifică, altfel se adaugă modulo 2 32 -1 cu o valoare constantă de 1010104 16 . Valoarea obținută prin combinarea ambelor părți convertite, numită gamma cifră, intră în bucla „32-3”, rezultatul acesteia este adăugat pe bit modulo 2 cu un bloc de date de intrare de 64 de biți. Dacă acesta din urmă este mai mic de 64 de biți, atunci biții suplimentari ai valorii primite sunt eliminați. Valoarea rezultată este trimisă la ieșire. Dacă încă sunt date primite, atunci acțiunea se repetă: blocul compus din părți de 32 de biți este convertit în părți și așa mai departe.

3. Modulscalare cu feedback acceptă, de asemenea, date de orice dimensiune și un mesaj de sincronizare ca intrare. Blocul de date de intrare este adăugat pe biți modulo 2 cu rezultatul transformării în ciclul „32-3” a mesajului de sincronizare. Valoarea rezultată este trimisă la ieșire. Valoarea mesajului de sincronizare este înlocuită în cazul criptării cu blocul de ieșire, iar în cazul decriptării - cu intrarea, adică criptată. Dacă ultimul bloc de date primite este mai mic de 64 de biți, atunci biții suplimentari ai gamma (ieșirea buclei „32-3”) sunt eliminați. Dacă încă există date primite, atunci acțiunea se repetă: cifrul gamma este format din rezultatul criptării valorii înlocuite și așa mai departe.

4. Modul de producțieinserții de imitație preia date de intrare care au o dimensiune de cel puțin două blocuri complete de 64 de biți și returnează un bloc de date de 64 de biți, numit uzurpare a inserției. Valoarea temporară de 64 de biți este setată la 0, apoi, în timp ce există date de intrare, este adăugată pe biți modulo 2 cu rezultatul executării ciclului "16-3", a cărui intrare este blocul de date de intrare . După încheierea introducerii, valoarea temporară este returnată ca rezultat.

Criptanaliză a cifrului

Cifrul GOST 28147-89 utilizează o cheie de 256 de biți, iar dimensiunea spațiului de cheie este 2256 . Niciun computer de uz general care există în prezent nu poate ghici o cheie în mai puțin de multe sute de ani. Standardul rus GOST 28147-89 a fost proiectat cu o marjă mare și depășește standardul DES american cu multe ordine de mărime, cu dimensiunea sa reală a cheii de 56 de biți și volumul spațiului cheie de numai 2 56 .

Există, de asemenea, atacuri asupra rundei complete GOST 28147-89 fără modificări. Unul dintre primii lucrări deschise, în care a fost efectuată analiza algoritmului, folosește punctele slabe ale procedurii de extindere a cheilor a unui număr de algoritmi de criptare bine-cunoscuți. În special, algoritmul complet GOST 28147-89 poate fi rupt folosind criptoanaliza diferențială pe chei legate, dar numai dacă sunt utilizate tabele de substituție slabe. Versiunea de 24 de runde a algoritmului (căreia îi lipsesc primele 8 runde) este deschisă în același mod pentru orice mese de înlocuire, cu toate acestea, tabelele de înlocuire puternice fac un astfel de atac complet nepractic.

Oamenii de știință autohtoni A.G. Rostovtsev și E.B. Makhovenko a propus în 2001 o metodă fundamental nouă de criptoanaliza prin formarea unei funcții obiective dintr-un text simplu cunoscut, textul cifrat corespunzând acestuia și valoarea dorită a cheii și găsirea extremului său corespunzător valorii adevărate a cheii. Ei au găsit, de asemenea, o clasă mare de chei slabe ale algoritmului GOST 28147-89, care vă permit să deschideți algoritmul folosind doar 4 texte clare selectate și textele cifrate corespunzătoare cu o complexitate destul de scăzută.

În 2004, un grup de experți din Coreea a propus un atac prin care, folosind criptoanaliza diferențială a cheilor asociate, este posibil să se obțină o cheie secretă de 12 biți cu o probabilitate de 91,7%. Atacul necesită 235 de texte clare alese și 236 de operațiuni de criptare. După cum puteți vedea, acest atac este practic inutil pentru deschiderea reală a algoritmului.

Tabelul de substituție este un element cheie pe termen lung, adică este valabil pentru mult mai mult termen lung decât o singură cheie. Se presupune că este comun tuturor nodurilor de criptare din cadrul unui sistem de protecție criptografică. Calitatea acestui tabel determină calitatea cifrului. Cu un tabel de substituție „puternic”, puterea cifrului nu scade sub o anumită limită acceptabilă, chiar dacă este dezvăluită. În schimb, utilizarea unui tabel „slab” poate reduce puterea cifrului la o limită inacceptabil de scăzută. Nu există informații despre calitatea tabelului de substituții în sigiliu deschis Rusia nu a fost publicată, dar existența tabelelor „slabe” este fără îndoială – un exemplu este tabelul de substituție „trivial”, conform căruia fiecare valoare este înlocuită de la sine. Într-o serie de lucrări, se ajunge la concluzia eronată că tabelele secrete de substituție ale algoritmului GOST 28147-89 pot face parte din cheie și pot crește lungimea efectivă a acesteia (ceea ce nu este semnificativ, deoarece algoritmul are o cheie foarte mare de 256 de biți). ).

Algoritm de criptare GOST 28147-89. Metodă simplă de înlocuire. — Arhiva WASM.RU

„Cât timp ești în viață, nu muri, uită-te la această lume.
Mulți aici au un suflet mort - sunt morți în interior.
Dar ei merg și râd, fără să știe că nu sunt acolo,
Nu te grăbi cu moartea, mi-a spus ea.

Aria, „Acolo sus”

2.1 rețele Feistel.
2.2 Cifra bloc GOST 28147-89

3.1 Informatie cheie
3.2 Pasul principal al transformării cripto

3.3 Cicluri de bază:“ 32-З” , “ 32-R” .

4.1 Implementarea etapei principale a transformării cripto
4.2 Creșterea vitezei algoritmului
5. Cerințe de informații cheie
6. Lista literaturii folosite
7. Mulțumiri.

Introducere.

Acest document este încercarea mea de a descrie metoda de înlocuire pur și simplu a algoritmului de criptare GOST 28147-89 în cel mai simplu limbaj, dar, cu toate acestea, alfabetizat din punct de vedere tehnic. Cât de bine am reușit, cititorul își va da cu părerea după ce a citit primele șase puncte.

Pentru ca munca mea să dea mai mult beneficiu Vă recomand să vă înarmați cu lucrările autorilor indicați în lista literaturii folosite. Se recomanda si un calculator, astfel incat sa aiba o functie de calcul al operatiei XOR, deoarece citirea articolului presupune că cititorul și-a propus să studieze acest algoritm de criptare. Deși este potrivit și ca instrument de referință, am scris acest articol tocmai ca tutorial.

Introducere în cifrurile bloc.

Înainte de a începe să luăm în considerare algoritmul, trebuie să ne familiarizăm cu istoria creării acestui tip de cifru. Algoritmul aparține categoriei de cifruri bloc, în arhitectura cărora informația este împărțită într-un număr finit de blocuri, cel final poate să nu fie complet. Procesul de criptare are loc exact peste blocurile complete, care formează textul cifrat. Blocul final, dacă este incomplet, este completat cu ceva (voi vorbi mai jos despre nuanțele adăugării lui) și este criptat în același mod ca și blocurile complete. Prin text cifrat, vreau să spun - rezultatul acțiunii funcției de criptare asupra unei anumite cantități de date pe care utilizatorul le-a trimis pentru criptare. Cu alte cuvinte, textul cifrat este rezultatul final al criptării.

Istoria dezvoltării cifrurilor bloc este asociată cu începutul anilor 70, când IBM, realizând nevoia de a proteja informațiile la transmiterea datelor prin canalele de comunicație computerizate, a început să implementeze program propriu cercetare științifică dedicat protecției informațiilor în rețelele electronice, inclusiv criptografia.

Un grup de cercetători - dezvoltatori ai companiei IBM, care a început să studieze sisteme de criptare cu o schemă de chei simetrice, a fost condus de Dr. Horst Feistel.

2.1 Rețele Feistel

Arhitectura noii metode de criptare propusă de Feistel în literatura clasică a fost numită „Arhitectura Feistel”, dar pe acest momentîn literatura rusă și străină, se folosește un termen mai consacrat - „rețeaua lui Feistel” sau rețeaua lui Feistel. Ulterior, conform acestei arhitecturi, a fost construit cifrul „Lucifer” – care a fost publicat ulterior și a provocat un nou val de interes în criptografie în general.

Ideea arhitecturii rețelei Feistel este următoarea: fluxul de informații de intrare este împărțit în blocuri de n biți în dimensiune, unde n este un număr par. Fiecare bloc este împărțit în două părți - L și R, apoi aceste părți sunt introduse într-un cifr de bloc iterativ, în care rezultatul etapei j-a este determinat de rezultatul etapei anterioare j-1! Acest lucru poate fi ilustrat cu un exemplu:

Orez. unu

Unde, funcția A este acțiunea principală a cifrului bloc. Poate fi o acțiune simplă, cum ar fi o operație XOR, sau poate avea un aspect mai complex, poate fi o secvență a unui număr de acțiuni simple - adăugare modulo, deplasare la stânga, înlocuire de elemente etc., în total acestea pași simpli formează așa-numitul - pasul principal al cripto-transformării.

Trebuie remarcat faptul că elementele cheie ale funcției sunt furnizarea de elemente cheie și operația XOR și cât de bine gândită este munca acestor operațiuni, vorbește despre puterea criptografică a cifrului în ansamblu.

Pentru ca ideea rețelelor Feistel să fie complet clară, luați în considerare cel mai simplu caz prezentat în Fig. orez. unu, unde în funcția A - vor efectua operațiunile „mod 2” (“xor”), dar aceasta protozoar caz, într-o situație mai gravă, de exemplu, ascunderea informațiilor de importanță națională, funcția A poate fi mai complexă (din câte am văzut, funcția A poate fi într-adevăr foarte complicată):

Date inițiale:

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

Obțineți un text cifrat

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

Să explicăm pașii noștri:

1. Această operație este modul de adăugare 2 4 . În practică, o astfel de operație se rezumă la o simplă adunare, în care trebuie să adunăm două numere și să ignorăm transportul la a 5-a cifră. Deoarece, dacă punem exponenți peste cifrele reprezentării binare a unui număr, va exista un indicator de patru peste a cincea cifră, aruncați o privire la figura de mai jos, care arată acțiunile operației noastre:

Orez. 2

Aici am indicat exponenții cu o săgeată, după cum puteți vedea, rezultatul ar fi trebuit să fie 10100, dar deoarece transportul este ignorat în timpul operațiunii mod 2 4, obținem 0100.

2. Această operație în literatură se numește mod 2, în limbaj de asamblare este implementată de comandă XOR. Dar ea mai mult nume corect mod 2 1 . Fără această operațiune unică, cu greu este posibil să se construiască un algoritm de criptare rapid, ușor de implementat și, în același timp, să fie destul de rezistent la criptografie. Unicitatea acestei operațiuni constă în faptul că este inversul în sine! De exemplu, dacă numărul A este XOR cu numărul B, rezultatul va fi C, în viitor este suficient să re-XOR numerele B și C împreună pentru a obține valoarea anterioară a lui A!

În această operație, am obținut 1010 având numerele 1110 și 0100, pentru a obține înapoi 1110, este suficient să XOR numerele 0100 și 1010 împreună! Mai multe detalii despre această operațiune găsiți în articol, care este încorporat pe site. www.wasm.ru, « Ghid elementar pentruAlgoritmi de detectare CRC_error» autorul care Ross N. Williams. Există un paragraf în această lucrare - " 5. Aritmetică binară excluzând transferurile". În acest articol este descrisă operația xor! Exclam pentru că în acest articol această operațiune este descrisă în așa fel încât cititorul nu doar să înțeleagă cum funcționează această operațiune, ci chiar să o înceapă vezi, auzi si simti!

3. Această acțiune este necesară pentru ca atunci când decriptați din textul cifrat, să puteți obține valorile originale.

2.2 Cifrul bloc GOST 28147-89

Algoritmul de criptare GOST 28147 - 89 aparține categoriei de cifruri bloc care operează pe arhitectura de rețea echilibrată Feistel, unde două părți ale blocului de informații selectat sunt de dimensiuni egale. Algoritmul a fost dezvoltat în adâncul celui de-al optulea departament al KGB, acum transformat în FAPSI, și a fost fixat ca standard de criptare. Federația Rusăîn 1989 sub URSS.

Pentru ca această metodă a algoritmului să funcționeze, este necesar să spargeți informațiile în blocuri de 64 de biți. Generați sau introduceți în sistemul de criptare următoarele informații cheie: cheie și tabel de înlocuire. Alegerea cheii și a tabelului de înlocuire pentru criptare ar trebui luată foarte în serios, deoarece. acesta este fundamentul securității informațiilor dvs. Despre ce cerințe sunt impuse cheii și tabelul de substituții, consultați paragraful „Cerințe pentru informațiile cheie”.

Când luăm în considerare metoda, nu ne vom concentra asupra acestui lucru, deoarece. acest articol, așa cum am spus mai sus, a fost scris cu scopul de a învăța cititorul cum să cripteze datele folosind metoda pur și simplu de înlocuire a acestui algoritm de criptare, dar cu siguranță vom aborda această problemă la sfârșitul articolului.

minim teoretic.

3.1 Informații cheie

După cum am spus mai sus, următorii sunt implicați activ în criptarea datelor:

3.1.1. Cheia este o secvență de opt elemente a câte 32 de biți fiecare. Mai departe, vom nota simbolul K și elementele din care constă - k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 Tabelul de substituție este o matrice de opt rânduri și șaisprezece coloane, denumită în continuare Hij. Fiecare element de la intersecția rândului i și coloanei j are 4 biți.

3.2 Etapa principală a transformării cripto

Acțiunea principală în procesul de criptare este pasul principal al transformării cripto. Aceasta nu este altceva decât o acțiune de criptare a datelor folosind un anumit algoritm, doar numele introdus de dezvoltatori a fost prea greoi.

Înainte de a începe criptarea, blocul este împărțit în două părți L și R, câte 32 de biți fiecare. Elementul cheie este selectat și numai atunci aceste două părți ale blocului sunt alimentate, elementul cheie este tabelul de înlocuire în funcția pasului principal, rezultatul pasului principal este o iterație a ciclului de bază, care va fi discutată în paragraful următor. Pasul principal constă din următorii pași:

1. Partea de adăugare a blocului R este adăugată elementului cheie K mod 2 32 . Am descris o operație similară mai sus, aici același lucru este doar că exponentul nu este „4”, ci „32” - rezultatul acestei operații va fi notat de Smod în viitor.
2. Împărțim rezultatul Smod obținut anterior în patru elemente de biți s7,s6,s5,s4,s3,s2,s1,s0 și îl introducem în funcția de înlocuire. Înlocuirea este următoarea: se selectează elementul Smod - s i, de la început pornim de la elementul cel mai de jos, și îl înlocuim cu valoarea din tabelul de înlocuire pentru rândul și coloana i indicată de valoarea elementului s i . Trecem la s i +1 element și facem același lucru și continuăm până când înlocuim valoarea ultimului element Smod - rezultatul acestei operații va fi notat ca Ssimple.
3. În această operație, valoarea lui Ssimple este deplasată ciclic la stânga cu 11 biți și obținem Srol.
4. Selectăm a doua parte a blocului L și adăugăm mod 2 cu Srol, ca urmare avem Sxor.
5. În această etapă, partea L a blocului devine egală cu valoarea părții R, iar partea R la rândul ei este inițializată cu rezultatul Sxor, iar aceasta completează funcția pasului principal!

3.3 Cicluri de bază: „32-Z”, „32-R”.

Pentru a cripta informațiile, este necesar să le împărțiți în blocuri de 64 de biți, desigur, ultimul bloc poate fi mai mic de 64 de biți. Acest fapt este călcâiul lui Ahile al acestei metode de „înlocuire simplă”. Deoarece adăugarea sa la 64 de biți este o sarcină foarte importantă pentru a crește puterea criptografică a textului cifrat, acest loc sensibil, dacă este prezent în matricea de informații, dar este posibil să nu fie (de exemplu, un fișier de 512 octeți în dimensiune !), trebuie tratat cu mare responsabilitate!

După ce ați împărțit informațiile în blocuri, ar trebui să împărțiți cheia în elemente:

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

Criptarea în sine constă în utilizarea așa-numitelor cicluri de bază. Care, la rândul lor, includ al n --lea număr de pași de bază de cripto-transformare.

Ciclurile de bază sunt, cum să spun, marcate: n - m. Unde n este numărul de pași de cripto-transformare de bază din bucla de bază și m este „tipul” buclei de bază, adică despre ce este vorba, criptarea „Z” sau criptarea „R” a datelor.

Ciclul de criptare de bază 32–3 constă din 32 de pași criptografici de bază. Blocul N și elementul tastei K sunt introduse în funcția care implementează acțiunile pasului, iar primul pas are loc cu k1, al doilea peste rezultat cu elementul k2 etc. conform următoarei scheme:

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

Procesul de decriptare 32-P decurge într-un mod similar, dar elementele cheie sunt alimentate în ordine inversă:

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

Practică.

4.1 Implementarea etapei principale de transformare cripto

După ce ne-am familiarizat cu teoria modului de criptare a informațiilor, este timpul să vedem cum funcționează criptarea în practică.

Date inițiale:

Să luăm un bloc de informații N = 0102030405060708h, aici părțile L și R sunt egale:

L = 01020304h, R = 05060708h, luați cheia:

K=' ca28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (acestea sunt coduri ASCII, pentru a vizualiza reprezentarea hexazecimală, puteți deschide acest fișier în modul de vizualizare în Comandant total apăsând tasta " F3” și apoi tasta ” 3 "). În această cheie, valorile elementului vor fi:

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

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

Luați, de asemenea, următorul tabel de înlocuire:

Orez. 3

Aici rândurile sunt numerotate de la 0 la 7, coloanele de la 0 la F.

Avertizare: Toate informațiile, inclusiv cheia cu tabelul de substituție, sunt luate ca exemplu pentru luarea în considerare a algoritmului!

Folosind „Date inițiale”, trebuie să obțineți rezultatul acțiunii pasului principal al transformării cripto.

1. Selectați partea R = 05060708h și elementul cheie k1 = ‘as28’, în formă hexazecimală elementul cheie va arăta astfel: 61733238h. Acum facem operația modului de însumare 2 32:

Orez. patru

După cum puteți vedea în figură, nu am transferat la 33 de biți marcați cu roșu și cu exponentul " 32 ". Și dacă am avea alte valori ale lui R și elementul cheie, acest lucru s-ar putea întâmpla și atunci l-am ignora, iar în viitor am folosi doar biții marcați cu galben.

Eu efectuez o astfel de operație cu comanda assembler adăuga:

; eax=R, ebx='as28'

Rezultatul acestei operațiuni este Smod = 66793940h

2. Acum cea mai complicată operație, dar dacă te uiți cu atenție, nu mai este atât de înfricoșătoare pe cât pare la început. Să ne imaginăm Smod în următoarea formă:

Orez. 5

Am încercat să vizualizez elementele Smod din figură, dar voi explica oricum:

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

Acum, pornind de la elementul cel mai de jos s0, facem o înlocuire. Amintind paragraful 3.2 Etapa principală a transformării cripto» i este un rând, s i este o coloană, căutăm o valoare în rândul zero și coloana zero:

Fig.6

Deci valoarea actuală a Smod nu este 6679394 0 h și 6679394 5 h.

Procedăm la înlocuirea s1, adică. patru. Folosind primul rând și a patra coloană (s1= 4!). Să ne uităm la imagine:

Orez. 7

Acum valoarea este Smod, nu 667939 4 5h, 667939 2 5h. Presupun că acum algoritmul de înlocuire este clar pentru cititor și pot spune că după rezultatul final al lui Ssimple va avea următoarea valoare - 11e10325h.

Voi vorbi despre modul în care acest lucru este cel mai ușor de implementat sub formă de comenzi de asamblare mai târziu în paragraful următor, după ce voi vorbi despre tabelul extins.

1. Trebuie să deplasăm valoarea Ssimple rezultată cu 11 biți la stânga.

Orez. opt

După cum puteți vedea, această acțiune este destul de simplă și este implementată de o comandă în limbaj de asamblare - rostogolire iar rezultatul acestei operațiuni Srol este 0819288Fh.

4. Acum rămâne partea L a blocului nostru de informații către XOR cu valoarea Srol. Iau calculator de la w2k sp4 și primesc Sxor = 091b2b8bh.

5. Această acțiune este finală și pur și simplu atribuim, curățăm R valoarea părții L și inițializam partea L cu valoarea lui Sxor.

Rezultat final:

L=091b2b8bh, R=01020304h

4.2 Creșterea vitezei algoritmului

Acum să vorbim despre optimizarea algoritmului pentru viteză. La implementarea unui proiect, trebuie să ținem cont de faptul că un program care funcționează cu registre mai des decât cu memorie funcționează cel mai rapid și aici această judecată este și ea foarte importantă, deoarece. peste un bloc de informații până la 32 de pași de criptare!

Când am implementat algoritmul de criptare în programul meu, am făcut următoarele:

1. Partea selectată a blocului L în registrul eax și R în edx.

2. Inițializat în registrul esi cu adresa cheii extinse, mai multe despre aceea de mai jos.

3. Am atribuit registrului ebx valoarea adresei tabelului de substituție extins, mai multe despre asta mai jos

4. A trecut informațiile de la punctele 1,2, 3 la funcția ciclului de bază 32 - Z sau 32 - R, în funcție de situație.

Dacă vă uitați la schema de furnizare a elementelor cheie din paragraful „ Cicluri de bază: „32-Z”, „32-R””, atunci cheia noastră pentru ciclul de bază 32 - Z poate fi reprezentată după cum urmează:

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'

Acestea. de la început mergi k1,k2,k3,k4,k5,k6,k7,k8 - ‘ ca28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1' Această secvență se repetă de trei ori. Apoi elementele merg în ordine inversă, adică: k8,k7,k6,k5,k4,k3,k2,k1 - „ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.

Am pre-aranjat elementele din matrice în ordinea în care ar trebui să fie servite în 32 - Z. Astfel, am crescut memoria necesară per tastă, dar m-am salvat de unele procese de gândire de care nu aveam nevoie și am crescut viteza algoritm, pentru reducerea timpului de acces la memorie! Aici am descris doar cheia pentru 32 - Z, pentru ciclul 32 - R am făcut același lucru, dar folosind o schemă diferită pentru furnizarea elementelor, pe care am descris-o și în paragraful " Cicluri de bază: „32-Z”, „32-R».

Este timpul să descriem implementarea funcției de înlocuire, așa cum am promis mai sus. Nu aș putea descrie mai devreme, pentru că. aceasta necesită introducerea unui nou concept - un tabel de substituție extins. Nu pot să-ți explic ce este. În schimb, vă voi arăta și vă puteți formula singur ce este - un tabel extins de înlocuire?

Deci, pentru a înțelege ce este un tabel de substituție extins, avem nevoie de un tabel de înlocuire, de exemplu, îl voi lua pe cel prezentat în Fig. 3.

De exemplu, trebuia să înlocuim numărul 66793940h. O voi prezenta sub următoarea formă:

Orez. 9

Acum, dacă luăm elementele s1,s0, i.e. octet mic, atunci rezultatul funcției de înlocuire va fi 25h! După ce am citit articolul lui Andrey Vinokurov, pe care l-am citat în paragraful „ Lista literaturii folosite”, veți descoperi de fapt că dacă luați două linii, puteți obține o matrice care vă permite să găsiți rapid elemente de înlocuire folosind o comandă de asamblare xlat. Ei spun că este posibil într-un alt mod, mai rapid, dar Andrey Vinokurov a petrecut aproximativ patru ani cercetând algoritmi rapizi pentru implementarea GOST! Nu cred că ar trebui să reinventezi roata când există deja.

Deci, despre matrice:

Să luăm primele două linii, zero și prima, și să creăm o matrice de 256 de octeți. Acum observăm o caracteristică că, dacă trebuie să convertiți 00h, atunci rezultatul va fi 75h (pe baza Fig. 3) - puneți această valoare în matrice la offset 00h. Luăm valoarea 01h, rezultatul funcției de înlocuire este 79h, o punem în matrice la offset 01 și tot așa până la 0FFh, care ne va da 0FCh, pe care îl vom pune în matrice la offset 0FFh. Așa că am obținut un tabel extins de înlocuiri pentru primul grup de șiruri: primul și zero. Dar mai sunt trei grupuri: a doua pagina 2, pagina 3, a treia pagina 4, pagina 5, a patra pagina 6, pagina 7. Cu aceste trei grupuri procedăm în același mod ca și cu primul. Rezultatul este un tabel de înlocuire extins!

Acum puteți implementa un algoritm care va efectua înlocuirea. Pentru a face acest lucru, luăm codurile sursă pe care Andrey Vinokurov le-a postat pe pagina sa, vezi „ Bibliografie».

lea ebx,extented_table_simple

mută eax,[pune numărul de înlocuit]

adăugați ebx,100h; mergeți la următoarele două noduri

sub ebx,300h ; astfel încât în ​​viitor ebx să indice tabelul

Acum încă o caracteristică, nu numai că am înlocuit acțiunile anterioare, dar am deplasat și numărul cu 8 biți la stânga! Trebuie doar să mutam numărul încă 3 biți la stânga:

si obtinem rezultatul operatiei rol eax,11!

Nu mai pot adăuga nimic despre optimizare, singurul lucru pe care pot sublinia ceea ce am spus mai sus este să folosesc registrele mai des decât accesele de memorie. Cred că aceste cuvinte sunt doar pentru începători, oamenii cu experiență înțeleg acest lucru foarte bine fără cuvintele mele.

Cerințe privind informațiile cheie.

După cum se precizează în articolul lui Andrey Vinokurov, cheia este selectată în funcție de două criterii:

Criteriul pentru distribuția equiprobabilă a biților între valorile 1 și 0. De obicei, criteriul pentru distribuția equiprobabilă a biților este criteriul lui Pearson ("chi-pătrat").

Aceasta înseamnă cheia, în principiu orice număr poate. Adică, atunci când se formează următorul bit al cheii, probabilitatea inițializării acestuia cu unu sau zero este 50/50!

Vă rugăm să rețineți că cheia are opt elemente, fiecare de 32 de biți, deci sunt 32 * 8 = 256 de biți în total în cheie și numărul chei posibile 2256! Nu te lovește?

criterii de serie.

Dacă ne uităm la cheia noastră, pe care am dat-o în paragraful " 4.1 Implementarea etapei principale de transformare cripto”, atunci veți observa că următoarea intrare este adevărată:

Orez. zece

Într-o frază, valoarea lui k 1 nu trebuie repetată nici în k 2 , nici în niciun alt element al cheii.

Adică, cheia pe care am ales-o ca luare în considerare a algoritmului de criptare, îndeplinește bine cele două criterii de mai sus.

Acum despre alegerea tabelului de înlocuire:

Acum să vorbim despre cum să alegeți tabelul de înlocuire potrivit. Principala cerință pentru alegerea tabelelor de substituție este fenomenul de „nerepetabilitate” a elementelor, fiecare dintre ele având o dimensiune de 4 biți. După cum ați văzut mai sus, fiecare rând al tabelului de înlocuire este format din valorile 0h, 1h, 2h, 3h, ..., 0fh. Deci, principala cerință este ca fiecare linie să conțină valorile 0h, 1h, 2h, ... , 0fh și fiecare astfel de valoare într-o singură copie. De exemplu, secvența:

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

Îndeplinește pe deplin această cerință, dar totuși! Nu este recomandat să selectați o astfel de secvență ca șir. Pentru că dacă furnizați o valoare intrării unei funcții care se bazează pe un astfel de șir, atunci veți obține aceeași valoare la ieșire! Nu crezi? Apoi luați numărul 332DA43Fh și opt astfel de linii ca tabel de înlocuire. Efectuați operația de înlocuire și vă asigur că ieșirea va fi numărul 332DA43Fh! Adică același lucru pe care l-ați supus la intrarea operației! Și acesta nu este un semn de bună formă în criptare, și nu-i așa?

Aceasta a fost o cerință, următorul criteriu spune că - fiecare bit al blocului de ieșire trebuie să fie independent statistic de fiecare bit al blocului de intrare!

Cum arată mai ușor? Și iată cum, de exemplu, am ales elementul s0 = 0Fh, 01111b din numărul de mai sus. Probabilitatea ca acum să înlocuim primul bit cu unul sau cu zero este 0,5! Probabilitatea înlocuirii celui de-al doilea, al treilea și al patrulea bit, fiecare bit, considerat separat, cu unuri sau zerouri este, de asemenea, de 0,5. Atunci când alegem s1 = 0Eh, vom înlocui probabilitatea că suntem un bit zero, iar acesta este „0” , cu zero sau unul prea este egal - 0,5! Astfel, conform acestui criteriu, nu există o regularitate între înlocuirea biților zero ai elementelor s0, s1! Da, ai putea înlocui cu unele, dar ai putea pune și zerouri.

Pentru a evalua tabelul conform acestui criteriu, puteți construi un tabel de coeficienți de corelație calculati prin formula:

Dacă p = 1, atunci valoarea bitului j la ieșire este egală cu valoarea bitului i la intrare pentru orice combinație de biți la intrare;

Dacă p = -1, atunci valoarea bitului j la ieșire este întotdeauna inversul bitului i de intrare;

Dacă p = 0, atunci bitul de ieșire j ia valorile 0 și 1 cu probabilitate egală pentru orice valoare fixă ​​a bitului de intrare i.

Să luăm un exemplu cu o singură linie:

Să-l împărțim în componente:

Calculăm un coeficient folosind formula de mai sus. Pentru a înțelege mai ușor cum se face acest lucru, voi explica mai detaliat:

Luăm bitul 0 al numărului 0 (0) la intrare și bitul 0 al numărului 0 la ieșire (1) și efectuăm operația 0 XOR 1 = 1.

Luăm al 0-lea bit al primului număr (1) la intrare și al 0-lea bit al primului număr la ieșire (1) și efectuăm operația 1 XOR 1 = 0.

Luăm al 0-lea bit al celui de-al 2-lea număr (0) la intrare și al 0-lea bit al celui de-al 2-lea număr la ieșire (0) și efectuăm operația 0 XOR 0 = 0.

Luăm al 0-lea bit al celui de-al 3-lea număr (1) la intrare și al 0-lea bit al celui de-al 3-lea număr la ieșire (1) și efectuăm operația 1 XOR 1 = 0.

După efectuarea secvenţială a operaţiilor XOR într-o astfel de secvenţă, numărăm numărul tuturor valorilor diferite de zero, obţinem valoarea 6. Prin urmare, P 00 = 1-(6/2 4-1) = 0,25. Deci, s-a dovedit că valoarea bitului 0 la ieșire este egală cu valoarea bitului 0 la intrare în 4 cazuri din 16;

Tabelul final de cote:

După cum se poate vedea din tabelul coeficienților de corelație, bitul 3 la intrare este inversat față de bitul 0 la ieșire în 14 cazuri din 16, ceea ce este 87,5% Acest lucru nu mai este acceptabil pentru sistemele de criptare normale. Pentru o schimbare, să luăm un alt exemplu:

Tabelul de coeficienți va fi după cum urmează (cui nu-i lene să recalculeze)

Ei bine, lucrurile stau și mai rău în acest tabel - biții 1 și 2 ai grupului rămân neschimbați! Criptoanalistul are unde să se întoarcă Ținând cont de toate aceste cerințe, o simplă enumerare („head-on”) a găsit tabele de permutare corespunzătoare teoriei specificate (azi - 1276 de combinații) Iată câteva dintre ele:

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

Lista literaturii folosite.

1. Articol de Andrey Vinokurov:

Algoritmul de criptare GOST 28147-89, utilizarea și implementarea acestuia

pentru calculatoare Platforme Intel x86.

Iată codurile sursă pentru implementarea algoritmului de criptare.

1. Articol de Horst Feistel:

Criptografie și securitate informatică.

(poate fi găsit la aceeași adresă ca articolul precedent)

1. Ross N. Williams:

Un ghid elementar pentru algoritmii de detectare a erorilor CRC

Postat pe site www.wasm.ro.

Mulțumiri.

Aș dori să-mi exprim recunoștința tuturor vizitatorilor forumului www.wasm.ru. Dar aș vrea să îi mulțumesc în special lui ChS, care în prezent este cunoscut sub numele de SteelRat, el m-a ajutat să înțeleg lucruri pe care probabil nu le-aș înțelege niciodată, precum și m-a ajutat să scriu paragraful: „ Cerințe de informații cheie”, partea principală a acestui paragraf a fost scrisă de el. De asemenea, îi sunt profund recunoscător angajatului KSTU. UN. Tupolev Anikin Igor Vyacheslavovich și ar fi un păcat să nu mai vorbim de Chris Kaspersky, pentru faptul că este, și Volodya / wasm.ru pentru instrucțiunile sale. Oh, și primesc de la el. De asemenea, vreau să remarc Sega-Zero / Callipso pentru că mi-au adus niște junglă matematică în minte.

Acesta este poate tot ce aș vrea să vă spun.

Aș fi recunoscător pentru critici sau întrebări legate de acest articol sau doar sfaturi. Datele mele de contact: [email protected], ICQ - 337310594.

Cu stimă, Evil's Interrupt.

P.S.: Nu am încercat să întrec pe nimeni cu acest articol. A fost scris cu intenția de a facilita studiul GOST, iar dacă aveți dificultăți, asta nu înseamnă că eu sunt de vină pentru asta. Fii rezonabil și ai răbdare, toate cele bune pentru tine!

„Cât timp ești în viață, nu muri, uită-te la această lume.
Mulți aici au un suflet mort - sunt morți în interior.
Dar ei merg și râd, fără să știe că nu sunt acolo,
Nu te grăbi cu moartea, mi-a spus ea.

Aria, „Acolo sus”

1. Introducere

1. Introducere în cifrurile bloc

2.1 rețele Feistel.
2.2 Cifra bloc GOST 28147-89

1. Minimum teoretic

3.1 Informatie cheie
3.2 Pasul principal al transformării cripto

3.3 Cicluri de bază:“ 32-З” , “ 32-R” .

1. Practică

4.1 Implementarea etapei principale a transformării cripto
4.2 Creșterea vitezei algoritmului
5.
6. Lista literaturii folosite
7. Mulțumiri.

Introducere.

Acest document este încercarea mea de a descrie metoda de înlocuire pur și simplu a algoritmului de criptare GOST 28147-89 în cel mai simplu limbaj, dar, cu toate acestea, alfabetizat din punct de vedere tehnic. Cât de bine am reușit, cititorul își va da cu părerea după ce a citit primele șase puncte.

Pentru ca munca mea să fie mai utilă, recomand să vă înarmați cu lucrările autorilor indicați în lista literaturii folosite. Se recomanda si un calculator, astfel incat sa aiba o functie de calcul al operatiei XOR, deoarece citirea articolului presupune că cititorul și-a propus să studieze acest algoritm de criptare. Deși este potrivit și ca instrument de referință, am scris acest articol tocmai ca tutorial.

Introducere în cifrurile bloc.

Înainte de a începe să luăm în considerare algoritmul, trebuie să ne familiarizăm cu istoria creării acestui tip de cifru. Algoritmul aparține categoriei de cifruri bloc, în arhitectura cărora informația este împărțită într-un număr finit de blocuri, cel final poate să nu fie complet. Procesul de criptare are loc exact peste blocurile complete, care formează textul cifrat. Blocul final, dacă este incomplet, este completat cu ceva (voi vorbi mai jos despre nuanțele adăugării lui) și este criptat în același mod ca și blocurile complete. Prin text cifrat, vreau să spun - rezultatul acțiunii funcției de criptare asupra unei anumite cantități de date pe care utilizatorul le-a trimis pentru criptare. Cu alte cuvinte, textul cifrat este rezultatul final al criptării.

Istoria dezvoltării cifrurilor bloc este asociată cu începutul anilor 70, când IBM, realizând nevoia de a proteja informațiile la transmiterea datelor prin canale de comunicații computerizate, a început să desfășoare propriul program de cercetare dedicat protecției informațiilor în format electronic. rețele, inclusiv criptografie.

Un grup de cercetători - dezvoltatori ai companiei IBM, care a început să studieze sisteme de criptare cu o schemă de chei simetrice, a fost condus de Dr. Horst Feistel.

2.1 Rețele Feistel

Arhitectura noii metode de criptare propusă de Feistel în literatura clasică a fost numită „Arhitectura Feistel”, dar în prezent în literatura rusă și străină este folosit un termen mai consacrat – „rețeaua lui Feistel” sau Rețeaua lui Feistel. Ulterior, conform acestei arhitecturi, a fost construit cifrul Lucifer - care a fost publicat ulterior și a provocat un nou val de interes în criptografie în general.

Ideea arhitecturii rețelei Feistel este următoarea: fluxul de informații de intrare este împărțit în blocuri de n biți în dimensiune, unde n este un număr par. Fiecare bloc este împărțit în două părți - L și R, apoi aceste părți sunt introduse într-un cifr de bloc iterativ, în care rezultatul etapei j-a este determinat de rezultatul etapei anterioare j-1! Acest lucru poate fi ilustrat cu un exemplu:

Orez. unu

Unde, funcția A este acțiunea principală a cifrului bloc. Poate fi o acțiune simplă, cum ar fi operația XOR, sau poate avea o formă mai complexă, poate fi o succesiune a unui număr de acțiuni simple - adăugare modulo, deplasare la stânga, înlocuire de elemente etc., în agregat, aceste acțiuni simple formează așa-numitul - pasul principal al transformării cripto.

Trebuie remarcat faptul că elementele cheie ale funcției sunt furnizarea de elemente cheie și operația XOR și cât de bine gândită este munca acestor operațiuni, vorbește despre puterea criptografică a cifrului în ansamblu.

Pentru ca ideea rețelelor Feistel să fie complet clară, luați în considerare cel mai simplu caz prezentat în Fig. orez. unu, unde în funcția A - vor efectua operațiunile „mod 2” (“xor”), dar aceasta protozoar caz, într-o situație mai gravă, de exemplu, ascunderea informațiilor de importanță națională, funcția A poate fi mai complexă (din câte am văzut, funcția A poate fi într-adevăr foarte complicată):

Date inițiale:

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

Obțineți un text cifrat

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

Să explicăm pașii noștri:

1. Această operație este modul de adăugare 2 4 . În practică, o astfel de operație se rezumă la o simplă adunare, în care trebuie să adunăm două numere și să ignorăm transportul la a 5-a cifră. Deoarece, dacă punem exponenți peste cifrele reprezentării binare a unui număr, va exista un indicator de patru peste a cincea cifră, aruncați o privire la figura de mai jos, care arată acțiunile operației noastre:

Orez. 2

Aici am indicat exponenții cu o săgeată, după cum puteți vedea, rezultatul ar fi trebuit să fie 10100, dar deoarece transportul este ignorat în timpul operațiunii mod 2 4, obținem 0100.

1. Această operație în literatură se numește mod 2, în limbaj de asamblare este implementată de comandă XOR. Dar numele său mai corect este mod 2 1 . Fără această operațiune unică, cu greu este posibil să se construiască un algoritm de criptare rapid, ușor de implementat și, în același timp, să fie destul de rezistent la criptografie. Unicitatea acestei operațiuni constă în faptul că este inversul în sine! De exemplu, dacă numărul A este XOR cu numărul B, rezultatul va fi C, în viitor este suficient să re-XOR numerele B și C împreună pentru a obține valoarea anterioară a lui A!

În această operație, am obținut 1010 având numerele 1110 și 0100, pentru a obține înapoi 1110, este suficient să XOR numerele 0100 și 1010 împreună! Mai multe detalii despre această operațiune găsiți în articol, care este încorporat pe site. www.wasm.ru, « Ghid elementar pentruAlgoritmi de detectare CRC_error» autorul care Ross N. Williams. Există un paragraf în această lucrare - 5. Aritmetică binară fără transporturi". În acest articol este descrisă operația xor! Exclam pentru că în acest articol această operațiune este descrisă în așa fel încât cititorul nu doar să înțeleagă cum funcționează această operațiune, ci chiar să o înceapă vezi, auzi si simti!

1. Această acțiune este necesară pentru ca atunci când decriptați din textul cifrat, să puteți obține valorile originale.

2.2 Cifrul bloc GOST 28147-89

Algoritmul de criptare GOST 28147 - 89 aparține categoriei de cifruri bloc care operează pe arhitectura de rețea echilibrată Feistel, unde două părți ale blocului de informații selectat sunt de dimensiuni egale. Algoritmul a fost dezvoltat în măruntaiele celui de-al optulea departament al KGB, acum transformat în FAPSI și a fost consacrat ca standard de criptare al Federației Ruse încă din 1989 sub URSS.

Pentru ca această metodă a algoritmului să funcționeze, este necesar să spargeți informațiile în blocuri de 64 de biți. Generați sau introduceți în sistemul de criptare următoarele informații cheie: cheie și tabel de înlocuire. Alegerea cheii și a tabelului de înlocuire pentru criptare ar trebui luată foarte în serios, deoarece. acesta este fundamentul securității informațiilor dvs. Despre ce cerințe sunt impuse cheii și tabelul de substituții, consultați paragraful „Cerințe pentru informațiile cheie”.

Când luăm în considerare metoda, nu ne vom concentra asupra acestui lucru, deoarece. acest articol, așa cum am spus mai sus, a fost scris cu scopul de a învăța cititorul cum să cripteze datele folosind metoda pur și simplu de înlocuire a acestui algoritm de criptare, dar cu siguranță vom aborda această problemă la sfârșitul articolului.

minim teoretic.

3.1 Informații cheie

După cum am spus mai sus, următorii sunt implicați activ în criptarea datelor:

3.1.1. Cheia este o secvență de opt elemente a câte 32 de biți fiecare. Mai departe, vom nota simbolul K și elementele din care constă - k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 Tabelul de substituție este o matrice de opt rânduri și șaisprezece coloane, denumită în continuare Hij. Fiecare element de la intersecția rândului i și coloanei j are 4 biți.

Acțiunea principală în procesul de criptare este pasul principal al transformării cripto. Aceasta nu este altceva decât o acțiune de criptare a datelor după un anumit algoritm, doar numele introdus de dezvoltatori a fost prea greoi :).

Înainte de a începe criptarea, blocul este împărțit în două părți L și R, câte 32 de biți fiecare. Elementul cheie este selectat și numai atunci aceste două părți ale blocului sunt alimentate, elementul cheie este tabelul de înlocuire în funcția pasului principal, rezultatul pasului principal este o iterație a ciclului de bază, care va fi discutată în paragraful următor. Pasul principal constă din următorii pași:

1. Partea de adăugare a blocului R este adăugată elementului cheie K mod 2 32 . Am descris o operație similară mai sus, aici este același lucru, doar că exponentul nu este „4”, ci „32” - rezultatul acestei operații va fi notat de Smod în viitor.
2. Împărțim rezultatul Smod obținut anterior în patru elemente de biți s7,s6,s5,s4,s3,s2,s1,s0 și îl introducem în funcția de înlocuire. Înlocuirea este următoarea: se selectează elementul Smod - s i, de la început pornim de la cel mai tânăr element și îl înlocuim cu valoarea din tabelul de înlocuiri prin i - rândul și coloana indicate de valoarea elementului s i . Trecem la s i +1 element și facem același lucru și continuăm până când înlocuim valoarea ultimului element Smod - rezultatul acestei operații va fi notat ca Ssimple.
3. În această operație, valoarea lui Ssimple este deplasată ciclic la stânga cu 11 biți și obținem Srol.
4. Selectăm a doua parte a blocului L și adăugăm mod 2 cu Srol, ca urmare avem Sxor.
5. În această etapă, partea L a blocului devine egală cu valoarea părții R, iar partea R la rândul ei este inițializată cu rezultatul Sxor, iar aceasta completează funcția pasului principal!

3.3 Cicluri de bază: „32-Z”, „32-R”.

Pentru a cripta informațiile, este necesar să le împărțiți în blocuri de 64 de biți, desigur, ultimul bloc poate fi mai mic de 64 de biți. Acest fapt este călcâiul lui Ahile al acestei metode de „înlocuire simplă”. Deoarece adăugarea sa la 64 de biți este o sarcină foarte importantă pentru a crește puterea criptografică a textului cifrat, acest loc sensibil, dacă este prezent în matricea de informații, dar este posibil să nu fie (de exemplu, un fișier de 512 octeți în dimensiune !), trebuie tratat cu mare responsabilitate!

După ce ați împărțit informațiile în blocuri, ar trebui să împărțiți cheia în elemente:

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

Criptarea în sine constă în utilizarea așa-numitelor cicluri de bază. Care, la rândul lor, includ al n --lea număr de pași de bază de cripto-transformare.

Ciclurile de bază sunt, cum să spun, marcate: n - m. Unde n este numărul de pași de cripto-transformare de bază din bucla de bază și m este „tipul” buclei de bază, adică despre ce este vorba, criptarea „Z” sau criptarea „R” a datelor.

Ciclul de criptare de bază 32–3 constă din 32 de pași criptografici de bază. Blocul N și elementul tastei K sunt introduse în funcția care implementează acțiunile pasului, iar primul pas are loc cu k1, al doilea peste rezultat cu elementul k2 etc. conform următoarei scheme:

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

Procesul de decriptare 32-P decurge într-un mod similar, dar elementele cheie sunt alimentate în ordine inversă:

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

Practică.

După ce ne-am familiarizat cu teoria modului de criptare a informațiilor, este timpul să vedem cum funcționează criptarea în practică.

Date inițiale:

Să luăm un bloc de informații N = 0102030405060708h, aici părțile L și R sunt egale:

L = 01020304h, R = 05060708h, luați cheia:

K=' ca28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (acestea sunt coduri ASCII, pentru a vizualiza reprezentarea hexazecimală, puteți deschide acest fișier în modul vizualizare în Total Commander apăsând butonul " F3” și apoi tasta ” 3 "). În această cheie, valorile elementului vor fi:

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

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

Luați, de asemenea, următorul tabel de înlocuire:

Orez. 3

Aici rândurile sunt numerotate de la 0 la 7, coloanele de la 0 la F.

Avertizare: Toate informațiile, inclusiv cheia cu tabelul de substituție, sunt luate ca exemplu pentru luarea în considerare a algoritmului!

Folosind „Date inițiale”, trebuie să obțineți rezultatul acțiunii pasului principal al transformării cripto.

1. Selectăm partea R = 05060708h și elementul cheie k1 = ‘as28’, în hexazecimal elementul cheie va arăta astfel: 61733238h. Acum facem operația modului de însumare 2 32:

Orez. patru

După cum puteți vedea în figură, nu am transferat la 33 de biți marcați cu roșu și cu exponentul " 32 ". Și dacă am avea alte valori ale lui R și elementul cheie, acest lucru s-ar putea întâmpla și atunci l-am ignora, iar în viitor am folosi doar biții marcați cu galben.

Eu efectuez o astfel de operație cu comanda assembler adăuga:

; eax=R, ebx='as28'

Rezultatul acestei operațiuni este Smod = 66793940h

1. Acum cea mai complicată operație, dar dacă te uiți cu atenție, nu mai este atât de înfricoșătoare pe cât pare la început. Să ne imaginăm Smod în următoarea formă:

MODEL NU SALVARE

Orez. 5

Am încercat să vizualizez elementele Smod din figură, dar voi explica oricum:

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

Acum, pornind de la elementul cel mai de jos s0, facem o înlocuire. Amintind paragraful 3.2 Etapa principală a transformării cripto» i este un rând, s i este o coloană, căutăm o valoare în rândul zero și coloana zero:

Fig.6

Deci valoarea actuală a Smod nu este 6679394 0 h și 6679394 5 h.

Procedăm la înlocuirea s1, adică. patru. Folosind primul rând și a patra coloană (s1= 4!). Să ne uităm la imagine:

Orez. 7

Acum valoarea este Smod, nu 667939 4 5h, 667939 2 5h. Presupun că acum algoritmul de înlocuire este clar pentru cititor și pot spune că după rezultatul final al lui Ssimple va avea următoarea valoare - 11e10325h.

Voi vorbi despre modul în care acest lucru este cel mai ușor de implementat sub formă de comenzi de asamblare mai târziu în paragraful următor, după ce voi vorbi despre tabelul extins.

1. Trebuie să deplasăm valoarea Ssimple rezultată cu 11 biți la stânga.

Orez. opt

După cum puteți vedea, această acțiune este destul de simplă și este implementată de o comandă în limbaj de asamblare - rostogolire iar rezultatul acestei operațiuni Srol este 0819288Fh.

1. Acum rămâne partea L a blocului nostru de informații către XOR cu valoarea Srol. Iau calculator de la w2k sp4 și primesc Sxor = 091b2b8bh.
2. Această acțiune este finală și pur și simplu atribuim, curățăm R valoarea părții L și inițializam partea L cu valoarea lui Sxor.

Rezultat final:

L=091b2b8bh, R=01020304h

4.2 Creșterea vitezei algoritmului

Acum să vorbim despre optimizarea algoritmului pentru viteză. La implementarea unui proiect, trebuie să ținem cont de faptul că un program care funcționează cu registre mai des decât cu memorie funcționează cel mai rapid și aici această judecată este și ea foarte importantă, deoarece. peste un bloc de informații până la 32 de pași de criptare!

Când am implementat algoritmul de criptare în programul meu, am făcut următoarele:

1. Alegeți o parte a blocului L în registrul eax și R în edx.
2. Inițializat în registrul esi cu adresa cheii extinse, mai multe despre asta mai jos.
3. Am atribuit valoarea adresei tabelului de substituție extins registrului ebx, mai multe despre asta mai jos
4. A trecut informațiile de la punctele 1,2, 3 la funcția ciclului de bază 32 - Z sau 32 - R, în funcție de situație.

Dacă vă uitați la schema de furnizare a elementelor cheie din paragraful „ Cicluri de bază: „32-Z”, „32-R””, atunci cheia noastră pentru ciclul de bază 32 - Z poate fi reprezentată după cum urmează:

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'

Acestea. de la început mergi k1,k2,k3,k4,k5,k6,k7,k8 - ‘ ca28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1' Această secvență se repetă de trei ori. Apoi elementele merg în ordine inversă, adică: k8,k7,k6,k5,k4,k3,k2,k1 - „ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.

Am pre-aranjat elementele din matrice în ordinea în care ar trebui să fie servite în 32 - Z. Astfel, am crescut memoria necesară per tastă, dar m-am salvat de unele procese de gândire de care nu aveam nevoie și am crescut viteza algoritm, pentru reducerea timpului de acces la memorie! Aici am descris doar cheia pentru 32 - Z, pentru ciclul 32 - R am făcut același lucru, dar folosind o schemă diferită pentru furnizarea elementelor, pe care am descris-o și în paragraful " Cicluri de bază: „32-Z”, „32-R».

Este timpul să descriem implementarea funcției de înlocuire, așa cum am promis mai sus. Nu aș putea descrie mai devreme, pentru că. aceasta necesită introducerea unui nou concept - un tabel de substituție extins. Nu pot să-ți explic ce este. În schimb, vă voi arăta și vă puteți formula singur ce este - un tabel extins de înlocuire?

Deci, pentru a înțelege ce este un tabel de substituție extins, avem nevoie de un tabel de înlocuire, de exemplu, îl voi lua pe cel prezentat în Fig. 3.

De exemplu, trebuia să înlocuim numărul 66793940h. O voi prezenta sub următoarea formă:

MODEL NU SALVARE

Orez. 9

Acum, dacă luăm elementele s1,s0, i.e. octet mic, atunci rezultatul funcției de înlocuire va fi 25h! După ce am citit articolul lui Andrey Vinokurov, pe care l-am citat în paragraful „ Lista literaturii folosite”, veți descoperi de fapt că dacă luați două linii, puteți obține o matrice care vă permite să găsiți rapid elemente de înlocuire folosind o comandă de asamblare xlat. Ei spun că este posibil într-un alt mod, mai rapid, dar Andrey Vinokurov a petrecut aproximativ patru ani cercetând algoritmi rapizi pentru implementarea GOST! Nu cred că ar trebui să reinventezi roata când există deja.

Deci, despre matrice:

Să luăm primele două linii, zero și prima, și să creăm o matrice de 256 de octeți. Acum observăm o caracteristică că, dacă trebuie să convertiți 00h, atunci rezultatul va fi 75h (pe baza Fig. 3) - puneți această valoare în matrice la offset 00h. Luăm valoarea 01h, rezultatul funcției de înlocuire este 79h, o punem în matrice la offset 01 și tot așa până la 0FFh, care ne va da 0FCh, pe care îl vom pune în matrice la offset 0FFh. Așa că am obținut un tabel extins de înlocuiri pentru primul grup de șiruri: primul și zero. Dar mai sunt trei grupuri: a doua pagina 2, pagina 3, a treia pagina 4, pagina 5, a patra pagina 6, pagina 7. Cu aceste trei grupuri procedăm în același mod ca și cu primul. Rezultatul este un tabel de înlocuire extins!

Acum puteți implementa un algoritm care va efectua înlocuirea. Pentru a face acest lucru, luăm codurile sursă pe care Andrey Vinokurov le-a postat pe pagina sa, vezi „ Bibliografie».

lea ebx,extented_table_simple

mută eax,[pune numărul de înlocuit]

adăugați ebx,100h; mergeți la următoarele două noduri

sub ebx,300h ; astfel încât în ​​viitor ebx să indice tabelul

Acum încă o caracteristică, nu numai că am înlocuit acțiunile anterioare, dar am deplasat și numărul cu 8 biți la stânga! Trebuie doar să mutam numărul încă 3 biți la stânga:

si obtinem rezultatul operatiei rol eax,11!

Nu mai pot adăuga nimic despre optimizare, singurul lucru pe care pot sublinia ceea ce am spus mai sus este să folosesc registrele mai des decât accesele de memorie. Cred că aceste cuvinte sunt doar pentru începători, oamenii cu experiență înțeleg acest lucru foarte bine fără cuvintele mele :).

Cerințe privind informațiile cheie.

După cum se precizează în articolul lui Andrey Vinokurov, cheia este selectată în funcție de două criterii:

- criteriul distribuției echiprobabile a biților între valorile 1 și 0. De obicei, criteriul lui Pearson ("chi-pătrat") acționează ca un criteriu al distribuției echiprobabile a biților.

Aceasta înseamnă cheia, în principiu orice număr poate. Adică, atunci când se formează următorul bit al cheii, probabilitatea inițializării acestuia cu unu sau zero este 50/50!

Vă rugăm să rețineți că cheia are opt elemente, fiecare de 32 de biți, deci sunt 32 * 8 = 256 de biți în total în cheie și numărul de chei posibile este de 2 256! Nu te lovește? 🙂

— criteriul seriei.

Dacă ne uităm la cheia noastră, pe care am dat-o în paragraful " 4.1 Implementarea etapei principale de transformare cripto”, atunci veți observa că următoarea intrare este adevărată:

Orez. zece

Într-o frază, valoarea lui k 1 nu trebuie repetată nici în k 2 , nici în niciun alt element al cheii.

Adică, cheia pe care am ales-o ca luare în considerare a algoritmului de criptare, îndeplinește bine cele două criterii de mai sus.

Acum despre alegerea tabelului de înlocuire:

Acum să vorbim despre cum să alegeți tabelul de înlocuire potrivit. Principala cerință pentru alegerea tabelelor de substituție este fenomenul de „nerepetabilitate” a elementelor, fiecare dintre ele având o dimensiune de 4 biți. După cum ați văzut mai sus, fiecare rând al tabelului de înlocuire este format din valorile 0h, 1h, 2h, 3h, ..., 0fh. Deci, principala cerință este ca fiecare linie să conțină valorile 0h, 1h, 2h, ... , 0fh și fiecare astfel de valoare într-o singură copie. De exemplu, secvența:

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

Îndeplinește pe deplin această cerință, dar totuși! Nu este recomandat să selectați o astfel de secvență ca șir. Pentru că dacă furnizați o valoare intrării unei funcții care se bazează pe un astfel de șir, atunci veți obține aceeași valoare la ieșire! Nu crezi? Apoi luați numărul 332DA43Fh și opt astfel de linii ca tabel de înlocuire. Efectuați operația de înlocuire și vă asigur că ieșirea va fi numărul 332DA43Fh! Adică același lucru pe care l-ați supus la intrarea operației! Și acesta nu este un semn de bună formă în criptare, și nu-i așa? 🙂

Aceasta a fost o cerință, următorul criteriu spune că - fiecare bit al blocului de ieșire trebuie să fie independent statistic de fiecare bit al blocului de intrare!

Cum arată mai ușor? Și iată cum, de exemplu, am ales elementul s0 = 0Fh, 01111b din numărul de mai sus. Probabilitatea ca acum să înlocuim primul bit cu unul sau cu zero este 0,5! Probabilitatea înlocuirii celui de-al doilea, al treilea și al patrulea bit, fiecare bit, considerat separat, cu unuri sau zerouri este, de asemenea, de 0,5. Atunci când alegem s1 = 0Eh, vom înlocui probabilitatea că suntem un bit zero, iar acesta este „0” , cu zero sau unul prea este egal - 0,5! Astfel, conform acestui criteriu, nu există o regularitate între înlocuirea biților zero ai elementelor s0, s1! Da, ai putea înlocui cu unele, dar ai putea pune și zerouri. 🙂

Pentru a evalua tabelul conform acestui criteriu, puteți construi un tabel de coeficienți de corelație calculati prin formula:

— dacă p = 1, atunci valoarea bitului j la ieșire este egală cu valoarea bitului i la intrare pentru orice combinație de biți la intrare;

— dacă p = -1, atunci valoarea bitului j la ieșire este întotdeauna inversarea bitului i de intrare;

— dacă p = 0, atunci bitul de ieșire j ia valorile 0 și 1 cu probabilitate egală pentru orice valoare fixă ​​a bitului de intrare i.

Să luăm un exemplu cu o singură linie:

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

Să-l împărțim în componente:

Calculăm un coeficient folosind formula de mai sus. Pentru a înțelege mai ușor cum se face acest lucru, voi explica mai detaliat:

- luăm bitul 0 al numărului 0 (0) la intrare și bitul 0 al numărului 0 la ieșire (1) executăm operația 0 XOR 1 = 1.

- luăm bitul 0 al primului număr (1) la intrare și al 0-lea bit al primului număr la ieșire (1) executăm operația 1 XOR 1 = 0.

- luăm bitul 0 al numărului 2 (0) la intrare și bitul 0 al numărului 2 la ieșire (0) executăm operația 0 XOR 0 = 0.

- luăm bitul 0 al numărului 3 (1) la intrare și bitul 0 al numărului 3 la ieșire (1) executăm operația 1 XOR 1 = 0.

După efectuarea secvenţială a operaţiilor XOR într-o astfel de secvenţă, numărăm numărul tuturor valorilor diferite de zero, obţinem valoarea 6. Prin urmare, P 00 = 1-(6/2 4-1) = 0,25. Deci, s-a dovedit că valoarea bitului 0 la ieșire este egală cu valoarea bitului 0 la intrare în 4 cazuri din 16;

Tabelul final de cote:

Tabelul de coeficienți va fi după cum urmează (cui nu-i lene să recalculeze)

	Intrare
Ieșire		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

Ei bine, lucrurile stau și mai rău în acest tabel - biții 1 și 2 ai grupului rămân neschimbați! Criptoanalistul are unde să se întoarcă 🙂 Ținând cont de toate aceste cerințe, o simplă enumerare („head-on”) a găsit tabele de permutare corespunzătoare teoriei specificate (azi - 1276 de combinații) Iată câteva dintre ele:

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

Lista literaturii folosite.

1. Articol de Andrey Vinokurov:

Algoritmul de criptare GOST 28147-89, utilizarea și implementarea acestuia

pentru computerele cu platformă Intel x86.

(poate fi găsit la: http://www.enlight.ru/crypto/frame.htm).

Iată codurile sursă pentru implementarea algoritmului de criptare.

1. Articol de Horst Feistel:

Criptografie și securitate informatică.

(poate fi găsit la aceeași adresă ca articolul precedent)

1. Ross N. Williams:

Un ghid elementar pentru algoritmii de detectare a erorilor CRC

Postat pe site www.wasm.ro.

Mulțumiri.

Aș dori să-mi exprim recunoștința tuturor vizitatorilor forumului www.wasm.ru. Dar aș vrea să îi mulțumesc în special lui ChS, care în prezent este cunoscut sub numele de SteelRat, el m-a ajutat să înțeleg lucruri pe care probabil nu le-aș înțelege niciodată, precum și m-a ajutat să scriu paragraful: „ Cerințe de informații cheie”, partea principală a acestui paragraf a fost scrisă de el. De asemenea, îi sunt profund recunoscător angajatului KSTU. UN. Tupolev Anikin Igor Vyacheslavovich și ar fi un păcat să nu mai vorbim de Chris Kaspersky, pentru faptul că este, și Volodya / wasm.ru pentru instrucțiunile sale. Oh, și primesc de la el :). De asemenea, vreau să remarc Sega-Zero / Callipso pentru că mi-au adus niște junglă matematică în minte.

Acesta este poate tot ce aș vrea să vă spun.

Aș fi recunoscător pentru critici sau întrebări legate de acest articol sau doar sfaturi. Datele mele de contact: [email protected], ICQ - 337310594.

Cu stimă, Evil's Interrupt.

P.S.: Nu am încercat să întrec pe nimeni cu acest articol. A fost scris cu intenția de a facilita studiul GOST, iar dacă aveți dificultăți, asta nu înseamnă că eu sunt de vină pentru asta. Fii rezonabil și ai răbdare, toate cele bune pentru tine!

Cunoscutul termen „performanță procesorului” în societate este un parametru obiectiv, calculat, care se măsoară în flops. Cu toate acestea, majoritatea îl măsoară în gigaherți, crezând naiv că acesta este același lucru. Nimeni nu cunoaște termenul de „performanță de cod”, și voi explica imediat de ce.

Motivul este că abia recent am venit cu el și încă nu am spus nimănui despre asta. Totuși, performanța codului, ca și performanța procesorului, are caracteristici obiective care pot fi măsurate. Acest articol este în special despre performanța codului executat de nucleul procesorului.

Cum se măsoară performanța codului? Deoarece am fost primul care a vorbit despre asta, atunci prin dreptul descoperitorului o voi măsura în scale RTT;).

Acum serios. În procesoarele moderne, principalele transformări sunt operațiunile pe numere de 32 de biți, totul este, în mare, exotic. Prin urmare, vom lua în considerare principalul lucru - operațiunile cu numere de 32 de biți. Câte operații pe 32 de biți credeți că poate executa nucleul unui procesor modern simultan?

Elevul va răspunde - unul, profesorul său va gândi și va spune că patru, profesionistul - că sunt doar douăsprezece operații până acum.

Deci, un cod de program care încarcă simultan toate dispozitivele executive ale procesorului pe toată durata de execuție a codului va avea o performanță de 12 RTT NIS. Maxim! Sincer să fiu, nu am mai scris un astfel de cod până acum, dar în acest articol voi încerca să fac un efort asupra mea.

Voi demonstra că codul cu executarea simultană a douăsprezece operațiuni pe 32 de biți este posibil

Codul de program care folosește o unitate de execuție în nucleul procesorului va avea în mod natural o performanță de 1 RTT. Programele generate de compilatoarele de limbaje se pot "lauda" cu o astfel de performanta a codului. nivel inalt, și interpreți mașini virtuale. Nu trebuie să presupunem că indicatorul de utilizare a procesorului, care poate fi văzut în managerul de activități OS, poate servi drept criteriu obiectiv pentru eficacitatea codului. Sarcina de bază a procesorului poate fi de 100%, dar codul programului va folosi un dispozitiv de execuție în el (performanță 1 RTT). În acest caz, la încărcare de 100%, nucleul procesorului va funcționa la 1/12 din performanța maximă. Cu alte cuvinte, atunci când Windows Task Manager arată utilizarea maximă a procesorului, performanța sa reală poate varia de la 1 la 12 RTT. Văzând în fereastra de performanță încărcare de 100% pe orice nucleu de procesor, este greșit să presupunem că toate dispozitivele executive funcționează în acest nucleu, în niciun caz!

Singurul criteriu de evaluare indirectă a funcționării unui nucleu de procesor cu performanță maximă poate fi consumul de energie și, ca urmare, zgomotul răcitorului. Acum, dacă răcitorul este zgomotos, atunci da - sarcina a ajuns la maxim. Cu toate acestea, este timpul să terminăm cu conceptele generale și să trecem la o practică dură.

Implementarea tradițională a GOST 28147-89

Nu sunt un profesionist in domeniu securitatea informatiei, dar încă familiarizat cu subiectul criptării. Conversațiile mele cu un criptograf profesionist pe care îl respect profund m-au inspirat să intru în criptarea fluxului specific simetrică. Și, după ce am abordat acest subiect, am încercat să o fac bine, și nu doar bine, ci și rapid, efectuând numărul maxim de operații pe unitatea de timp. Cu alte cuvinte, m-am confruntat cu sarcina de a scrie codul programului cu valoarea RTT maximă.

Conversia criptografică conform GOST 28147-89 este utilizată pentru criptarea în flux a informațiilor în canalele de comunicare și pe unitățile de disc.

În prezent, implementarea software a acestui GOST pe RON este utilizată pe scară largă. CPU. În metodele binecunoscute de implementare a GOST, toate informațiile secrete (chei de criptare, blocuri de înlocuire) sunt plasate în memorie cu acces aleator. Acest lucru reduce fiabilitatea criptării, deoarece, având un dump RAM, este posibil să se dezvăluie complet toate elementele secrete ale transformării cripto. În plus, metoda are limitări de viteză datorită locației principalelor obiecte de cripto-transformare în OP și încărcării incomplete a dispozitivelor executive ALU. Procesoarele moderne, care implementează o procedură criptografică folosind o metodă binecunoscută, pot oferi o viteză de criptare de 40–60 megaocteți pe secundă. Și dacă înțelegeți cu adevărat până la sfârșit, atunci motivul performanței scăzute și al securității slabe a conversiei cripto este implementarea software a blocului de substituție. Vezi descrierea sa în GOST în fig. unu.

Conform clauzei 1.2 din GOST, acest bloc implementează permutări tetrade (patru biți) într-un cuvânt de 32 de biți, dar arhitectura procesorului x86 / 64 și setul său de instrucțiuni nu sunt capabile să manipuleze eficient tetradele.

Pentru implementarea software a blocului de substituție, se folosesc tabele speciale în RAM, care sunt pregătite în etapa de inițializare a criptofuncției. Aceste tabele combină nodurile de substituție ale tetradelor adiacente în tabele de 8 × 8 biți, deci există patru tabele de 256 de octeți în RAM.

În implementările mai avansate, aceste tabele au o dimensiune de 1024 de octeți (256 de cuvinte de patru octeți). Acest lucru se face pentru a implementa în tabele o deplasare ciclică suplimentară cu 11 poziții a cuvântului de 32 de biți obținut ca urmare a înlocuirii (următoarea operație a algoritmului de conversie conform GOST). Un exemplu de implementare a GOST conform aceasta metoda prezentat în anexa 1 (pe disc).

Informația blocului de substituție este o componentă secretă a criptofuncției (așa cum este formulată în GOST, vezi Fig. 2).

Amplasarea acestor tabele cu cheile blocului de substituție în OP contrazice cerințele GOST (clauza 1.7), deoarece informațiile secrete devin disponibile pentru programe de la terți lucrând la instalarea unui computer. FSB, care certifică, de asemenea, implementările software de criptare conform GOST, analizează această încălcare, ca să o spunem ușor, condescendent. Dacă pentru a plasa cheile în OP, FSB-ul necesită în continuare o „frunză de smochin” - mascarea cheilor cu operația XOR, atunci nu este necesar nimic pentru blocurile de înlocuire din OP, acestea sunt stocate în text clar.

Pe scurt, FSB omite astfel de implementări software ale criptoprocedurii, în ciuda scăderii evidente a puterii unei astfel de soluții și a încălcării directe a propriilor cerințe conform GOST (clauza 1.7). Și asta în ciuda metodelor binecunoscute de spargere a cifrurilor prin eliminarea unui depozit de memorie...

Vom reveni la problema stocării cheilor și a blocurilor de înlocuire în registrele interne ale procesorului puțin mai târziu (există o soluție frumoasă și rapidă), dar deocamdată vom stoca doar cheile de criptare în registrele MMX, aceasta este mai fiabilă.

Dar destule versuri, este important în cadrul subiectului luat în considerare ca acest cod de program să aibă o performanță de 1 RTT-shku. Acum să scriem un cod cu o performanță de 2 RTT-uri.

Implementarea multithreaded a GOST 28147-89

Singura modalitate de a accelera cripto-procedurile în algoritmul cunoscut este introducerea multithreading-ului. Sensul unei astfel de modificări în implementarea algoritmului este de a calcula mai multe blocuri de date în paralel simultan.

Majoritatea programatorilor înțeleg prin procesare paralelă doar munca mai multor nuclee de procesor, sincronizate prin întreruperi și semafore din memorie.

Cu toate acestea, există o altă variantă de procesare paralelă a datelor pe un singur nucleu de procesor. Permiteți-mi să explic această idee neevidentă.

Procesoarele moderne includ cel puțin două și chiar trei până la șase unități logice aritmetice. Aceste ALU-uri (FPU, unități aritmetice de adrese și așa mai departe) pot funcționa independent unele de altele, singura condiție pentru funcționarea lor paralelă este obiectele software care nu se suprapun pe care operează. Cu alte cuvinte, în instrucțiunile care execută simultan ALU, adresele de memorie și numerele de registru trebuie să fie diferite. Sau, nu trebuie efectuate operațiuni de scriere în registrele comune și adresele de memorie accesate de diferite dispozitive executive ale procesorului.

Încărcarea lucrărilor tuturor ALU-urilor este controlată de un bloc hardware special din interiorul nucleului procesorului - planificatorul, care privește înainte prin codul executabil, la o adâncime de 32-64 de octeți. Dacă planificatorul găsește comenzi care pot fi executate pe ALU fără conflicte, atunci le rulează simultan pe diferite unități de execuție. În acest caz, contorul comenzilor executate indică comanda executabilă (există mai multe dintre ele într-o astfel de schemă), după care toate comenzile au fost deja executate.

Majoritatea secvențelor de programe generate automat (de către compilatori) nu pot încărca toate ALU-urile și FPU-urile care se află în nucleul procesorului. În acest caz, hardware-ul procesorului este inactiv, ceea ce reduce semnificativ performanța rezultată. Dezvoltatorii de procesoare înțeleg acest lucru și introduc moduri pentru a crește frecvența de bază atunci când echipamentul nu este utilizat pe deplin. Sistemele de hypertrading sunt, de asemenea, concepute pentru asta și voi folosi acest sistem pentru a „apăsa” codul la maximum în viitor.

Compilatorii, chiar și cei mai optimizați, și cu atât mai mult - motoarele de mașini virtuale, nu pot genera cod optimizat din punct de vedere al vitezei. Doar un programator cu cunoștințe de inginerie poate scrie un astfel de cod optimizat, iar instrumentul pentru scrierea acestuia este exclusiv un asamblator.

O ilustrare caracteristică a posibilității de a executa mai multe fire de execuție independente pe un nucleu de procesor este implementarea GOST, care este executată în două fire de execuție pe un singur nucleu de procesor. Ideea codului este simplă: există două blocuri de date pentru criptare/decriptare, dar un nucleu de procesor care va efectua conversia. Este posibil să se efectueze transformarea pentru aceste două blocuri de date secvenţial, iar acest lucru s-a făcut până acum. În acest caz, timpul necesar pentru efectuarea transformărilor este dublat.

Dar puteți face altfel: comenzi alternative legate de procesarea diferitelor blocuri de date. Grafic, aceste opțiuni sunt prezentate în Fig. 3.

În figură, exemplul de sus arată ordinea obișnuită în care sunt procesate două blocuri de date independente. Mai întâi, primul bloc este procesat, apoi procesorul trece la procesarea celui de-al doilea bloc. Desigur, timpul rezultat este egal cu dublul timpului necesar procesării unui bloc, iar unitățile de execuție ale nucleului procesorului nu sunt încărcate complet.

Următoarele arată un exemplu cu intercalarea comenzilor din diferite fire de procesare. În acest caz, comenzile legate de diferite blocuri de date sunt intercalate. Planificatorul selectează instrucțiuni care sunt independente unele de altele și le transmite ALU1 și ALU2 pentru execuție. Gruparea comenzilor primului și celui de-al doilea fir de execuție pe aceste ALU-uri se realizează automat, deoarece algoritmul de funcționare al planificatorului include gruparea comenzilor cu angrenaj în funcție de date comune de pe același dispozitiv executiv.

Pentru ca un astfel de cod de program să funcționeze fără timp de inactivitate ALU, este necesar ca fiecare fir de program să funcționeze cu propriul set de registre. Cache-ul din această schemă devine un blocaj (are doar două porturi de ieșire a datelor), așa că stocăm cheile în registre MMX. Deoarece în acest caz nodurile de înlocuire (și de schimbare) sunt doar pentru citire în memorie, acestea pot fi partajate de ambele fire de execuție a programului.

Aceasta, desigur, este o explicație foarte simplificată a principiului execuției paralele a firelor de execuție a programului pe un singur nucleu, în realitate totul este mult mai complicat. În practică, este necesar să se țină cont de arhitectura pipeline a unităților de execuție, restricțiile privind accesul simultan la cache și blocul de registre RON, prezența nodurilor aritmetice de adrese, comutatoare și multe altele... Deci, acesta este un subiect pentru profesioniști care se pot număra pe degetele de la... o mână.

Metoda de criptare paralelă este implementată efectiv doar pentru modul de funcționare a procesorului pe 64 de biți, deoarece în acest mod există o cantitate suficientă de RON (până la 16 bucăți!). Un exemplu de implementare a GOST conform acestei metode este prezentat în Anexa 2 (pe disc).

Este clar că această implementare GOST are o performanță de cod de 2 RTT-uri. Acum să vedem cum afectează acest lucru timpul de execuție.

Ciclul de criptare pentru un flux (Anexa 1) este de 352 de cicluri, iar în acest timp se calculează 8 octeți de date, pentru o implementare în două fluxuri a GOST (Anexa 2) sunt necesare 416 cicluri de procesor, dar se calculează 16 octeți. Astfel, viteza de conversie rezultată crește de la 80 la 144 de megaocteți pentru un procesor de 3,6 GHz.

Se obține o imagine interesantă: codul conține exact de două ori mai multe instrucțiuni și durează doar cu 15% mai mult, dar cred că cititorii au înțeles deja motivul acestui fenomen...

Teoretic, codul din al doilea exemplu ar trebui să fie executat în același număr de cicluri ca și codul din primul exemplu, dar deși nodul de planificare este dezvoltat de inginerii Intel, ei sunt și ei oameni și suntem cu toții departe de a fi perfecți. Deci există o oportunitate de a evalua eficiența creării lor. Acest cod va funcționa și pe un procesor AMD și le puteți compara rezultatele.

Dacă cineva nu mă crede pe cuvânt, atunci programele de testare cu contoare de ceas sunt incluse pe disc pentru astfel de necredincioși. Programe în codurile sursă, desigur în assembler, deci există o oportunitate de a-mi verifica cuvintele și, în același timp, de a arunca o privire asupra unor trucuri de codare profesională.

Utilizarea registrelor SSE și comenzilor AVX ale procesoarelor moderne pentru implementarea GOST 28147-89

Procesoarele moderne cu arhitectură x86/64 includ un set de registre SSE de 16 octeți și FPU-uri specializate (cel puțin două) pentru a efectua diverse operațiuni pe aceste registre. Este posibil să se implementeze GOST pe acest echipament și, în acest caz, nodurile de înlocuire pot fi plasate nu sub formă de tabele în RAM, ci direct pe registrele SSE dedicate.

Pe un singur registru SSE, puteți plasa două tabele de 16 rânduri simultan. Astfel, patru registre SSE vor găzdui complet toate tabelele de înlocuire. Singura condiție pentru o astfel de plasare este cerința de intercalare, conform căreia tetradele aceluiași octet trebuie plasate în registre SSE diferite. În plus, este indicat să plasați tetradele joasă și înaltă ale octeților de intrare, respectiv, în tetradele scăzute și înalte ale registrelor SSE.

Aceste cerințe sunt determinate de optimizare pentru setul existent de comenzi AVX. Astfel, fiecare octet al registrului SSE va conține două tetrade corespunzătoare octeților diferiți ai registrului de intrare al blocului de substituție, în timp ce poziția octetului în registrul SSE corespunde unic cu indexul din tabelul de înlocuire al blocului de substituție.

În fig. patru.

Plasarea informațiilor secrete ale nodurilor de substituție pe registrele SSE crește securitatea criptoprocedurii, dar izolarea completă a acestor informații secrete este posibilă în următoarele condiții:

• Miezul procesorului a fost pus în modul gazdă hypervisor și blocul de întrerupere (APIC) a fost dezactivat forțat. În acest caz, nucleul procesorului este complet izolat de sistemul de operare și de aplicațiile care rulează pe instalația de calcul.
• Încărcarea registrelor SSE și izolarea nucleului de calcul se realizează înainte de pornirea sistemului de operare; este optim să se efectueze aceste proceduri din modulul de boot de încredere (TDM).
• Programele de criptoproceduri conform GOST sunt plasate în zona de memorie nemodificabilă a unității de calcul (fie BIOS, fie memoria flash MDZ).

Respectarea acestor cerințe va asigura izolarea completă și imuabilitatea codul programului criptoprocedurile și informațiile secrete utilizate în acestea.

Pentru eșantionarea eficientă din registrele SSE ale tetradelor, sunt utilizate comutatoarele de octeți cu mai multe intrări disponibile în FPU-uri. Aceste comutatoare permit transferuri de la orice octet al sursei la orice octet al destinației, prin indecși aflați într-un registru special de index SSE. Mai mult, transferul se realizează în paralel pentru toți cei 16 octeți ai receptorului-registru-SSE.

Având noduri de stocare de substituție pe registrele SSE și un comutator cu mai multe intrări în unitățile FPU, este posibil să se organizeze următoarea transformare în unitatea de substituție (Fig. 5).

În această schemă, registrul de intrare din fiecare tetradă setează adresa comutatorului corespunzător, care transferă informații de la unitățile de nod de înlocuire la registrul de ieșire prin intermediul magistralei de date. O astfel de schemă poate fi organizată în trei moduri:

• Creați un design de cip adecvat, dar asta este fantastic pentru noi.
• Reprogramarea microcodului și crearea propriei instrucțiuni de procesor pentru a implementa această funcție pe procesoarele existente nu mai este o fantezie, dar, din păcate, este nerealist în condițiile actuale.
• Scrieți un program folosind comenzile oficiale AVX. Opțiunea, deși nu foarte eficientă, dar o putem implementa „aici și acum”. Deci asta vom face în continuare.

Comutatoarele sunt controlate de o comandă specială cu trei adrese AVX VPSHUFB. Primul său operand este receptorul de informații de la comutatoare, al doilea este sursa la care sunt conectate intrările comutatoarelor. Al treilea operand este un registru de control pentru comutatoare, fiecare octet fiind asociat cu un comutator corespunzător; valoarea din ea specifică numărul direcției din care comutatorul citește informații. Pentru o descriere a acestei comenzi din documentația oficială Intel, vezi fig. 5. În fig. Figura 6 arată funcționarea acestei comenzi - sunt afișate doar jumătate din registrele SSE, pentru a doua jumătate totul este similar.

Comutatorul folosește doar cei mai puțin semnificativi patru biți pentru a determina direcția de comutare, ultimul bit din fiecare octet este folosit pentru a forța octetul receptor corespunzător la zero, dar această funcție de comutare nu este încă necesară în cazul nostru.

A fost scris un program cu o selecție de notebook-uri prin comutatoarele FPU, dar nici măcar nu l-am introdus în aplicație - este prea sărac. A avea un registru de 128 de biți și a folosi doar 32 de biți în el este neprofesionist.

Așa cum se spune, „Terminul nostru este orizontul”, așa că strângeți-l așa... îl vom apăsa și îl vom pune în pungi!

Acesta nu este un joc de cuvinte, ci o realitate dură FPU - registrele SSE pot fi împărțite în părți egale și aceleași transformări pot fi efectuate pe aceste părți cu o singură comandă. Pentru ca procesorul să înțeleagă acest lucru, există o literă magică „P” - un pachet care este plasat înaintea mnemonicului de comandă și nu mai puțin litere magice „Q”, „D”, „W”, „B”, care sunt plasate la sfârșit și declară, în ce părți sunt împărțite registrele SSE în această comandă.

Suntem interesati de modul lot cu o defalcare a registrului SSE în patru blocuri de 32 de biți; în consecință, toate comenzile vor fi prefixate cu „P” și terminate cu simbolul „D”. Acest lucru face posibilă procesarea a patru blocuri de 32 de biți în paralel cu o instrucțiune de procesor, adică calcularea a patru blocuri de date în paralel.

Programul care implementează această metodă este disponibil în Anexa 3, există toate explicațiile.

Totuși, apăsați, așa că apăsați! Procesoarele moderne au cel puțin două FPU și două fluxuri de instrucțiuni independente pot fi folosite pentru a le încărca complet. Dacă intercalați corect comenzi din fluxuri independente, atunci puteți încărca complet ambele FPU și puteți obține opt fluxuri de date procesate în paralel simultan. Un astfel de program a fost scris și îl puteți vedea în Anexa 4, dar trebuie să vă uitați cu atenție - puteți înnebuni. Acesta este ceea ce se numește „codul nu este pentru toată lumea...”.

Prețul de emisiune

Utilizarea registrelor SSE pentru a stoca nodurile de înlocuire este de înțeles - oferă o anumită garanție a izolării informațiilor secrete, dar sensul calculării criptofuncției în sine pe FPU nu este evident. Prin urmare, s-au efectuat măsurători ale timpului de execuție a procedurilor standard folosind metoda înlocuirii directe în conformitate cu GOST pentru patru și opt fluxuri.

Pentru patru fire de execuție s-a obținut o viteză de execuție de 472 de cicluri de procesor. Astfel, pentru un procesor cu o frecvență de 3,6 GHz, un fir este considerat la o viteză de 59 megaocteți pe secundă, și, respectiv, patru fire, la o viteză de 236 megaocteți pe secundă.

Pentru opt fire de execuție s-a obținut o viteză de execuție de 580 de cicluri de procesor. Astfel, pentru un procesor de 3,6 GHz, un thread este considerat la o viteză de 49 megabytes pe secundă, iar opt fire la o viteză de 392 megabytes pe secundă.

După cum cititorul poate observa, codul din exemplul #3 are un randament de 4 RTT, în timp ce codul din exemplul #4 are un randament de 8 RTT. În aceste exemple, pe registrele SSE, modelele sunt aceleași ca atunci când se folosește RON, doar planificatorul și-a redus eficiența. Acum oferă o creștere de 20% a duratei pentru o creștere de două ori a lungimii codului.

Mai mult, aceste rezultate au fost obținute folosind comenzile universale AVX disponibile atât în procesoare Intel, și în procesoarele AMD. Dacă optimizați pentru un procesor AMD, rezultatul va fi mult mai bun. Sună contra tendință, dar este totuși adevărat și iată de ce: procesoare AMD au un set suplimentar de instrucțiuni, așa-numita extensie XOP, și în aceasta set suplimentar există comenzi care simplifică foarte mult implementarea algoritmului GOST.

Aceasta se referă la comenzile de deplasare logică a pachetului de octeți și deplasarea ciclică a pachetului de cuvinte duble. Exemplele date în Anexele 3 și 4 folosesc secvențe de comenzi universale care implementează transformarea necesară: în primul caz, o comandă „în plus”, iar în celălalt caz, patru comenzi în plus deodată. Deci există rezerve de optimizare, și considerabile.

Dacă vorbim de optimizare ulterioară, merită să ne amintim prezența registrelor de 256 de biți (registruri YMM), folosindu-se teoretic de dublarea vitezei de calcul. Dar, deocamdată, aceasta este doar o perspectivă, momentan, procesoarele încetinesc mult atunci când execută instrucțiuni pe 256 de biți (FPU-urile au o lățime a căii de 128 de biți). Experimentele au arătat că pe procesoarele moderne, un număr de 16 fire de execuție pe registrele YMM nu oferă niciun câștig. Dar asta doar pentru moment, pe modelele noi de procesoare, viteza instrucțiunilor pe 256 de biți va fi, fără îndoială, crescută, iar apoi utilizarea a 16 fire paralele va deveni oportună și va duce la o creștere și mai mare a vitezei criptoprocedurii.

Teoretic, puteți conta pe o viteză de 600-700 de megaocteți pe secundă dacă procesorul are două FPU-uri cu o lățime a căii de lucru de 256 de biți fiecare. În acest caz, putem vorbi despre scrierea codului cu o eficiență de 16 RTT, iar aceasta nu este fantezie, ci viitorul apropiat.

mod mixt

Din nou, se pune problema numărului de registre, acestea nu sunt suficiente pentru a promova un astfel de algoritm. Dar modul de hiper tranzacționare ne va ajuta. Nucleul procesorului are un al doilea set de registre disponibile în modul procesor logic. Prin urmare, vom executa același cod pe două procesoare logice simultan. În acest mod, desigur, nu vom avea mai multe dispozitive executive, dar datorită alternanței, putem obține o încărcătură completă a tuturor dispozitivelor executive.

Nu poți conta pe o creștere de 50% aici, blocajul este memoria cache în care sunt stocate măștile tehnologice, dar poți obține totuși o creștere cu 100 de megaocteți suplimentari. Această opțiune nu este listată în anexe (macrocomenzile sunt aceleași cu cele utilizate în codul 8 RTT), dar este disponibilă în fișiere de program. Deci, dacă cineva nu crede în posibilitatea criptării la o viteză de 500 de megaocteți pe secundă pe un singur nucleu de procesor, lăsați-l să ruleze fișierele de testare. Sunt si texte cu comentarii ca sa nu creada nimeni ca sunt viclean.

Această focalizare este posibilă doar pe procesoarele Intel, AMD are doar două FPU-uri la două module de procesor (analog cu modul de hiper-trading). Dar mai sunt patru ALU, care sunt un păcat de a nu folosi.

Puteți conduce modulele de procesor ale Bulldozerului într-un mod similar cu modul de tranzacționare hiper, dar rulați conversia în RON pe module diferite într-un fir și în registrele SSE într-un alt thread și obțineți aceleași 12 RTT. Nu am testat această opțiune, dar cred că codul din 12 RTT va funcționa mai eficient pe AMD. Cei care doresc pot încerca, programele de testare pot fi ajustate pentru a funcționa pe „Bulldozere” destul de ușor.

Cine are nevoie?

O întrebare serioasă, dar cu un răspuns simplu - toată lumea are nevoie de ea. În curând ne vom așeza cu toții pe nori, vom stoca acolo atât datele, cât și programele și acolo, oh, cum doriți să vă echipați propriul colț privat. Pentru a face acest lucru, va trebui să criptați traficul, iar viteza de conversie cripto va fi principalul factor determinant în munca confortabilă în cloud. Alegerea noastră de algoritm de criptare este mică - fie GOST, fie AES.

Mai mult decât atât, în mod ciudat, criptarea algoritmului AES încorporată în procesoare se dovedește a fi mult mai lentă, testele arată o viteză de 100-150 de megaocteți pe secundă, iar asta cu implementarea hardware a algoritmului! Problema constă în numărarea cu un singur thread și în blocul de înlocuire, care operează pe octeți (un tabel de 256 de rânduri). Deci GOST se dovedește a fi mai eficient în implementarea pe arhitectura x86 / 64, cine ar fi crezut...

Asta dacă vorbim despre nivelul atins de viteză de criptare. Și dacă ținem cont de perfecționările teoretice în domeniul îmbunătățirii eficienței codului, atunci cel mai probabil nimeni nu are nevoie de el. Practic nu există specialiști de nivel 3–6 RTT, compilatorii generează în general cod la nivelul 1–2,5 RTT, iar majoritatea programatorilor nu cunosc asamblare, iar dacă îi cunosc ortografia, nu înțeleg dispozitivul unui procesor modern. Și fără această cunoaștere, ce este asamblatorul, ce este un fel de SI-sharp - nu contează.

Dar nu totul este atât de trist: în „concluzia” după o săptămână de nopți nedormite există un nou algoritm pentru implementarea GOST, ceea ce este un păcat să nu brevetezi. Și cererile de brevete (până la trei) au fost deja întocmite și depuse, așa că, domnilor, oameni de afaceri, line up - femeile și copiii au reducere.

Acest algoritm este obligatoriu pentru utilizare ca algoritm de criptare în organizatii guvernamentale RF și o serie de altele comerciale.

Descrierea algoritmului

Schema algoritmului este prezentată în fig. 3.1. După cum puteți vedea, schema acestui algoritm este destul de simplă, ceea ce simplifică fără ambiguitate implementarea software sau hardware.

Algoritmul GOST 28147-89 criptează informațiile în blocuri de 64 de biți, care sunt împărțite în două subblocuri de 32 de biți (N1 și N2). Subblocul N1 este procesat într-un anumit mod, după care se adaugă valoarea acestuia

cu valoarea subblocului N2 (adăugarea se realizează modulo 2), apoi subblocurile sunt schimbate. O astfel de transformare se realizează pentru un anumit număr de runde: 16 sau 32, în funcție de modul de funcționare al algoritmului (descris mai jos). În fiecare rundă se efectuează următoarele operații:

1. Suprapunerea tastelor. Conținutul subblocului /VI este adăugat modulo 2 32 la partea Kx a cheii.

Cheia de criptare a algoritmului GOST 28147-89 are o dimensiune de 256 de biți, iar Kx este partea sa de 32 de biți, adică o cheie de criptare de 256 de biți este reprezentată ca o concatenare a subcheilor de 32 de biți (Fig. 3.2):

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

În timpul procesului de criptare, se utilizează una dintre aceste subchei, în funcție de numărul rotund și de modul de funcționare al algoritmului.

Orez. 3.1. Schema algoritmului GOST 28147-

Orez. 3.2. Cheia de criptare a algoritmului GOST 28147-89

2. Înlocuire tabulară. După suprapunerea cheii, subblocul /VI este împărțit în 8 părți de 4 biți, valoarea fiecăruia fiind înlocuită individual în conformitate cu tabelul de înlocuire pentru această parte a subblocului. Înlocuirile de tabele (Cutie de substituție, S-box) sunt adesea folosite în algoritmii moderni de criptare, așa că merită să le luați în considerare mai detaliat.

Înlocuirea tabelului este utilizată în acest fel: un bloc de date de o anumită dimensiune (în acest caz, 4 biți) este alimentat la intrare, a cărui reprezentare numerică determină numărul valorii de ieșire. De exemplu, avem o S-box de următoarea formă:

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

Lăsați blocul de 4 biți „0100” să vină la intrare, adică valoarea este 4. Conform tabelului, valoarea de ieșire va fi 15, adică. „1111” (0 este înlocuit cu 4, 1 este înlocuit cu 11, valoarea lui 2 nu este schimbată etc.).

După cum puteți vedea, schema algoritmului este foarte simplă, ceea ce înseamnă că cea mai mare povară a criptării datelor cade pe tabelele de înlocuire. Din păcate, algoritmul are proprietatea că există tabele de substituție „slabe”, folosindu-se de care algoritmul poate fi dezvăluit prin metode criptoanalitice. Cele slabe includ, de exemplu, un tabel în care rezultatul este egal cu intrarea:

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

3. Deplasare ciclică la stânga pe biți cu 11 biți.

Moduri de algoritm

Algoritmul GOST 28147-89 are 4 moduri de funcționare:

□ mod simplu de înlocuire;

□ modul gamma;

P mod de joc cu feedback;

□ mod de producție a atașamentelor de imitație.

Aceste moduri sunt oarecum diferite de cele general acceptate (descrise în Secțiunea 1.4), așa că merită să le analizăm mai detaliat.

Aceste moduri au scopuri diferite, dar folosesc aceeași transformare de criptare descrisă mai sus.

Mod de schimb ușor

În modul de înlocuire simplă, cele 32 de runde descrise mai sus sunt efectuate pur și simplu pentru a cripta fiecare bloc de informații pe 64 de biți. Subcheile pe 32 de biți sunt utilizate în următoarea secvență:

□ KO, Kl, K2, K3, K4, K5, Kb, AG7, KO, ATI etc. - în rundele 1 la 24;

□ K1, Kb, K5, K4, K3, K2, K\, KO - în rundele 25 până la 32.

Decriptarea în modul de înlocuire simplă se face exact în același mod, dar cu o secvență ușor diferită de utilizare a subcheilor:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - în rundele 1 la 8;

□ KP, Kb, K5, K4, K3, K2, K\, KO, K1, Kb etc. - în rundele 9 până la 32.

Similar cu modul standard ECB, datorită criptării separate a blocurilor, modul de înlocuire simplă nu este recomandat pentru criptarea datelor reale; ar trebui folosit doar pentru a cripta alte chei de criptare în scheme cu mai multe chei.

Modul Gamma

În modul gamma (Fig. 3.3), fiecare bloc al textului simplu este adăugat bit cu bit modulo 2 la blocul gamma al cifrului cu o dimensiune de 64 de biți. Cifrul gamma este o secvență specială care este generată folosind transformările descrise mai sus, după cum urmează:

1. În registrele N1 și N2 se scrie umplerea lor inițială - o valoare de 64 de biți, numită „mesaj de sincronizare” (un mesaj de sincronizare, de fapt, este un analog al vectorului de inițializare în modurile CBC, CFB și OFB ).

2. Conținutul registrelor /VI și N2 (în acest caz, mesajele de sincronizare) este criptat în modul de înlocuire simplă.

3. Conținutul lui N1 se adaugă modulo (2 32 - 1) cu constanta CI = 2 24 + 2 16 + 2 8 + 4 , rezultatul adunării se scrie în registrul /VI.

4. Conținutul lui N2 se adaugă modulo 2 cu constanta C2 = 2 24 + 2 16 + 2 8 +1, rezultatul adunării se scrie în registrul N2.

5. Conținutul registrelor /VI și N2 este scos ca un bloc gamma de 64 de biți (adică, în acest caz, /VI și N2 formează primul bloc gamma).

6. Dacă este necesar următorul bloc gamma (adică criptarea sau decriptarea trebuie să continue), reveniți la pasul 2.

Pentru decriptare, un gamma este generat în același mod, apoi operația XOR este din nou aplicată textului cifrat și biților gamma.

Pentru a genera aceeași cifră gamma, utilizatorul care decriptează criptograma trebuie să aibă aceeași cheie și aceeași valoare a mesajului de sincronizare care au fost folosite pentru a cripta informațiile. În caz contrar, nu veți putea obține textul original din cel criptat.

În majoritatea implementărilor algoritmului GOST 28147-89, mesajul de sincronizare nu este un element secret, dar mesajul de sincronizare poate fi la fel de secret ca și cheia de criptare. În acest caz, putem considera că lungimea efectivă a cheii algoritmului (256 de biți) este mărită cu încă 64 de biți ai mesajului de sincronizare, ceea ce poate fi considerat ca un element cheie suplimentar.

Modul gamma de feedback

În modul feedback gamma, pornind de la al 2-lea bloc, registrele /VI și L/2 sunt umplute nu cu blocul gamma anterior, ci cu rezultatul criptării blocului text simplu anterior (Fig. 3.4). Primul bloc din acest mod este generat exact în același mod ca și cel anterior.

Orez. 3.4. Generarea cifrului gamma în modul gamma cu feedback

Modul de generare a imitatorului

O falsificare este o sumă de control criptografică calculată folosind o cheie de criptare și concepută pentru a verifica integritatea mesajelor. Pentru a-l calcula, există un mod special al algoritmului GOST 28147-89.

Generarea prefixului de imitație se realizează după cum urmează:

1. Primul bloc de informații de 64 de biți, pentru care se calculează imitatorul, este scris în registrele N1 și N2 și criptat în modul de înlocuire simplă redusă, în care sunt efectuate primele 16 runde din 32.

2. Rezultatul obținut se însumează modulo 2 cu următorul bloc de informații, salvând rezultatul în N1 și N2.

3. M și N2 sunt din nou criptate în modul redus de înlocuire simplă și așa mai departe până la ultimul bloc de informații.

Un prefix este considerat conținutul rezultat pe 64 de biți al registrelor N1 și N2 sau o parte a acestuia. Cel mai adesea, se folosește un prefix de imitație de 32 de biți, adică jumătate din conținutul registrelor. Acest lucru este suficient, deoarece, ca orice sumă de control, prefixul de imitație este destinat în primul rând să protejeze împotriva distorsiunii accidentale a informațiilor. Pentru a proteja împotriva modificării deliberate a datelor, sunt utilizate alte metode criptografice - în primul rând electronice semnatura digitala(vezi secțiunea 1.1).

Prefixul de imitație este utilizat după cum urmează:

1. La criptarea oricărei informații, imitatorul de text simplu este calculat și trimis împreună cu textul cifrat.

2. După decodare, prefixul de imitație este din nou calculat și comparat cu cel trimis.

3. Dacă prefixele de imitație calculate și trimise nu se potrivesc, textul cifrat a fost distorsionat în timpul transmiterii sau au fost folosite chei incorecte în timpul decriptării.

Prefixul de imitație este util în special pentru a verifica decriptarea corectă a informațiilor cheie atunci când se utilizează scheme cu mai multe chei.

Prefixul de imitație este un analog al codului de autentificare a mesajului MAC calculat în modul CBC; diferența este că calculul prefixului nu folosește un mesaj de sincronizare, în timp ce calculul MAC folosește un vector de inițializare.

Puterea criptografică a algoritmului

În 1994, descrierea algoritmului GOST 28147-89 a fost tradusă în engleză și publicată; după aceasta au început să apară rezultatele analizelor sale efectuate de experți străini; cu toate acestea, nu au fost găsite atacuri care se apropie de practic pentru o perioadă semnificativă de timp.

□ lungime cheie mare - 256 biți; împreună cu mesajul de sincronizare secretă, lungimea efectivă a cheii crește la 320 de biți;

□ 32 de runde de transformări; deja după 8 runde, se obține efectul complet de dispersie a datelor de intrare: schimbarea unui bit din blocul de text simplu va afecta toți biții din blocul de text cifrat și invers, adică există o marjă de securitate multiplă.

Luați în considerare rezultatele criptoanalizei algoritmului GOST 28147-89.

Analiza tabelelor de substituție

Deoarece tabelele de substituție nu sunt date în standard, o serie de lucrări (de exemplu, în) sugerează că o „organizație competentă” poate emite atât tabele de substituție „bune” cât și „rele”. Cu toate acestea, celebrul expert Bruce Schneier numește astfel de presupuneri „zvonuri”. Este clar că puterea criptografică a algoritmului depinde în mare măsură de proprietățile tabelelor de substituție utilizate, respectiv, există tabele de substituție slabe (vezi mai sus pentru un exemplu), a căror utilizare poate simplifica atacul algoritmului. Cu toate acestea, posibilitatea utilizării diferitelor tabele de substituție pare a fi o idee foarte demnă, susținută de următoarele două fapte din istoria standardului de criptare DES (a se vedea Secțiunea 3.15 pentru detalii):

□ atacurile care utilizează atât criptoanaliza liniară, cât și diferențială a algoritmului DES utilizează caracteristici specifice tabelelor de substituție; atunci când utilizați alte tabele, criptoanaliza va trebui să o ia de la capăt;

□ S-au făcut încercări de consolidare a DES împotriva criptoanalizei liniare și diferențiale prin utilizarea tabelelor de substituție mai puternice; astfel de tabele, care sunt într-adevăr mai stabile, au fost propuse, de exemplu, în algoritmul s 5 DES; dar, din păcate, a fost imposibil să înlocuim DES cu s 5 DES, deoarece tabelele de înlocuire sunt definite rigid în standard, respectiv, implementările algoritmului probabil nu suportă capacitatea de a schimba tabelele cu altele.

Într-o serie de lucrări (de exemplu, , și ) se concluzionează în mod eronat că tabelele de substituție secrete ale algoritmului GOST 28147-89 pot face parte din cheie și pot crește lungimea efectivă a acesteia (ceea ce nu este semnificativ, deoarece algoritmul are o cheie foarte mare de 256 de biți). Cu toate acestea, lucrarea demonstrează că tabelele de substituție secretă pot fi calculate folosind următorul atac, care poate fi aplicat practic:

1. Setați cheia nulă și căutați „vectorul nul”, adică valoarea z = /(0), unde /() este funcția rotundă a algoritmului. Această etapă necesită aproximativ 2 operațiuni de criptare.

2. Folosind vectorul zero, se calculează valorile tabelelor de substituție, care nu necesită mai mult de 2 11 operații.

Modificări de algoritm și analiza acestora

În cadrul lucrării, a fost efectuată o criptoanaliza a modificărilor algoritmului GOST 28147-89:

□ algoritmul GOST-H, în care, în raport cu algoritmul inițial, se modifică ordinea de utilizare a subcheilor, și anume, în runde de la a 25-a la a 32-a subchei sunt folosite în ordine directă, adică în același mod ca în precedenta runde ale algoritmului;

□ Un algoritm GOST® cu 20 de runde care utilizează XOR în loc de modulo 2 32 pentru suprapunerea cheilor.

Pe baza rezultatelor analizei, s-a ajuns la concluzia că GOST-H și GOST© sunt mai slabe decât algoritmul GOST 28147-89 original, deoarece ambele au clase de chei slabe. Este de remarcat faptul că în ceea ce privește criptoanaliza GOST©, lucrarea repetă cuvânt cu cuvânt secțiunea despre criptoanaliza algoritmului GOST 28147-89, publicată în 2000 într-o lucrare binecunoscută (fără nicio referire la original). Aceasta pune sub semnul întrebării profesionalismul autorilor lucrării și celelalte rezultate ale acesteia.

În lucrare se propune o modificare foarte interesantă a algoritmului: tabelele S \ ... Ss trebuie neapărat să fie diferite; în fiecare rundă a algoritmului, acestea trebuie permutate conform unei anumite legi. Această permutare poate depinde de cheia de criptare sau poate fi secretă (adică să facă parte dintr-o cheie de criptare mai mare decât cheia originală de 256 de biți). Ambele opțiuni, potrivit autorilor lor, cresc semnificativ rezistența algoritmului împotriva criptoanalizei liniare și diferențiale.

Și încă o modificare legată de tabelele de substituție este dată în lucrare, în care este analizată una dintre metodele posibile de calculare a tabelelor de substituție pe baza cheii de criptare. Autorii lucrării au concluzionat că o astfel de dependență slăbește algoritmul, deoarece duce la prezența unor chei slabe și la unele potențiale vulnerabilități ale algoritmului.

Analiza algoritmului complet

Există, de asemenea, atacuri asupra rundei complete GOST 28147-89 fără modificări. Una dintre primele lucrări deschise în care a fost efectuată analiza algoritmului, o lucrare binecunoscută, este dedicată atacurilor care exploatează punctele slabe ale procedurii de extindere a cheilor a unui număr de algoritmi de criptare cunoscuți. În special, algoritmul complet GOST 28147-89 poate fi rupt folosind criptoanaliza diferențială pe chei legate, dar numai dacă sunt utilizate tabele de substituție slabe. Versiunea de 24 de runde a algoritmului (căreia îi lipsesc primele 8 runde) este deschisă în același mod pentru orice tabel de înlocuire, dar tabelele de înlocuire puternice (de exemplu, date în ) fac un astfel de atac absolut nepractic.

Oamenii de știință autohtoni A. G. Rostovtsev și E. B. Makhovenko au propus în 2001 o metodă fundamental nouă de criptoanaliza (conform autorilor, este semnificativ mai eficientă decât criptoanaliza liniară și diferențială) prin formarea unei funcții obiective dintr-un text simplu cunoscut corespunzător textului cifrat și valoarea dorită. a cheii și găsirea extremului acesteia corespunzător valorii adevărate a cheii. Ei au găsit, de asemenea, o clasă mare de chei slabe ale algoritmului GOST 28147-89, care vă permit să deschideți algoritmul folosind doar 4 texte clare selectate și textele cifrate corespunzătoare cu o complexitate destul de scăzută. Criptanaliza algoritmului este continuată în lucrare.

În 2004, un grup de experți din Coreea a propus un atac prin care, folosind criptoanaliza diferențială pe chei asociate, este posibil să se obțină cu o probabilitate de 91,7% 12 biți ai unei chei secrete. Atacul necesită 235 de texte clare alese și 236 de operațiuni de criptare. După cum puteți vedea, acest atac este practic inutil pentru deschiderea reală a algoritmului.