BROASCĂ
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 29 mai 2017; verificările necesită 3 modificări . Acest articol este despre algoritmul de criptare. Pentru o metodă de măsurare a anvelopei și fazei impulsurilor laser ultrascurte, consultați articolul Gatere optică rezolvată în frecvență .| BROASCĂ | |
|---|---|
| Creator | D. Georgoudis, D. Leroux și B. Chavet |
| Creată | 1998 _ |
| Dimensiunea cheii | 128/192/256 biți |
| Dimensiunea blocului | 128 de biți |
| Numărul de runde | opt |
| Tip de | propriu |
FROG este un cifr bloc simetric cu o structură neortodoxă, unul dintre participanții la competiția americană AES , dezvoltată de compania costaricană TecApro Internacional.
Istoricul creației
Algoritmul FROG a fost creat în 1998 de trei specialiști de la Tecnologia Apropriada (TesArgo) din micul stat latino-american Costa Rica (necunoscut anterior pentru evoluțiile sale în domeniul criptografiei ): Dianelos Georgoudis, Damian Leroux și Billy Simon Chavez Simon Chaves
Varianta de criptare depusă la concurs respectă cerințele AES, având un bloc egal cu 128 de biți și o lungime a cheii de 128, 192 sau 256 de biți. Algoritmul în sine, teoretic, permite chei de la 40 la 1000 de biți lungime.
Concurs AES
Cifrul FROG a fost scos la concurs de TecApro Internacional, o companie internațională înregistrată în Costa Rica. Dezvoltatorii algoritmului - D. Georgoudis, D. Leroux și B. Chaves - oameni, ca să spunem ușor, puțin cunoscuți în lumea criptografică. Potrivit autorilor, FROG este „un nou cifr cu o structură neortodoxă”. Baza puterii cifrului este cheia internă secretă a unui design complex, în timp ce operațiunile de criptare/decriptare în sine sunt extrem de simple.
În august, echipa TWOFISH (Wagner, Ferguson și Schneier) a arătat că cheia de cifră FROG ar putea fi spartă cu aproximativ 257 de muncă .
În ceea ce privește puterea cifrurilor, acest indicator este mult mai dificil de verificat. Pe parcursul etapei de evaluare preliminară a primei runde, un număr semnificativ de rezultate criptoanalitice au fost prezentate pe site-ul NIST și direct la conferința AES2, într-un fel sau altul au „pătat” reputația aproape tuturor cifrurilor candidate. Cu toate acestea, dacă nu vorbim despre străinii evidente LOKI , FROG , MAGENTA și HPC , atunci nu au fost găsite slăbiciuni evidente în algoritmi.
Caracteristicile de bază și structura algoritmului
Competiția AES a cerut ca algoritmii participanți la competiție să accepte o dimensiune de bloc de 128 de biți de date criptate, precum și chei de criptare de 128, 192 și 256 de biți. Cu toate acestea, dezvoltatorii algoritmului FROG au propus un set mai larg de valori pentru acești parametri:
- este permisă utilizarea cheilor cu dimensiuni cuprinse între 5 și 125 de biți (adică de la 40 la 1000 de biți);
- dimensiunea blocului poate varia de la 8 la 128 de biți, adică de la 64 la 1024 de biți (totuși, în descrierea algoritmului de către autor, în conformitate cu cerințele AES, apare o dimensiune de bloc de 16 octeți).
Indiferent de dimensiunea cheii și a blocului, criptarea se realizează în 8 runde. În fiecare rundă, pe fiecare octet al blocului criptat sunt efectuate următoarele acțiuni (presupunând că blocurile au o dimensiune de 16 octeți):
- Valoarea octetului curent (N-lea) este adăugată modulo 2 la valoarea aceluiași octet din prima parte a tastei rotunde (procedura de extindere a cheii este descrisă mai jos).
- A doua parte a tastei rotunde este un tabel de permutare. Din acest tabel este selectat un octet, al cărui număr de serie este egal cu valoarea calculată în primul pas. Valoarea octetului selectat înlocuiește valoarea octetului curent al blocului de date criptat.
- Valoarea următorului octet (N + 1) este modulo 2 cu valoarea selectată în pasul 2. Rezultatul obținut înlocuiește vechea valoare a octetului N + 1 al blocului de date criptat.
- A treia parte a cheii rotunde este tabelul index. Valoarea octetului N al tabelului de index definește un alt octet modificabil al blocului de date criptat, care este modificat exact în același mod ca și octet N + 1 (adică la valoarea obținută la pasul 2 se adaugă modulo 2) .
Procedura de extindere a cheii
Această procedură ar trebui să obțină 8 chei rotunde de la cheia de criptare - una pentru fiecare rundă a algoritmului. Cheia rotundă constă din trei subchei:
- 16-byte prima parte;
- tabel de permutare de 256 de octeți;
- tabel de index de 16 octeți.
Astfel, pentru ca algoritmul să funcționeze, este necesar să se genereze 2304 octeți de informații cheie.
- Prin „propagarea” cheii de criptare (adică valoarea cheii de criptare se repetă de numărul necesar de ori, iar cheia de criptare a acestui algoritm, așa cum s-a menționat mai sus, are o dimensiune de la 5 la 125 de octeți), primul 2304 -byte matrice de date temporare este generată. Octeții ultimei copii „replicate” a cheii care depășesc limita matricei necesare de 2304 de octeți (de exemplu, ultimii 71 de octeți ai unei chei de 125 de octeți - cheia cu dimensiunea maximă) sunt eliminați.
- O „multiplicare” similară a fragmentului de cheie principală de 251 de octeți formează a doua matrice de date temporare de 2304 de octeți. Cheia principală este o constantă special selectată de 251 de octeți. Valoarea octetului cheii master (începând de la octetul mic) este prezentată în tabel.
- Prin aplicarea adăugării modulo 2 la biții corespunzători celor două matrice generate în pașii 1 și 2, se obține o cheie extinsă temporară.
- Formatarea cheii obținute la pasul 3 (adică împărțirea în 8 segmente - după numărul de runde - 16 + 256 + 16 octeți în dimensiune, precum și procesarea suplimentară, care va fi descrisă mai târziu), oferă cheia extinsă preliminară a algoritmul.
- Cheia pre-împrăștiată este folosită pentru a cripta o matrice de 2304 de octeți plină cu zerouri. Criptarea este efectuată în modul de înlănțuire a blocurilor de criptare, în care primii 16 octeți ai cheii de criptare originale sunt utilizați ca vector de inițializare (IV), primul fiind, de asemenea, adăugat modulo 2 cu un număr egal cu dimensiunea criptării. tastați în octeți (acest lucru este necesar pentru a obține un IV diferit pentru chei de dimensiuni diferite, dar cu aceiași primi 16 octeți). Rezultatul operației este o cheie extinsă plină cu informații pseudo-aleatoare.
- Similar cu pasul 4, cheia extinsă este formatată pentru a obține opt chei rotunde cu structura necesară.
Formatarea tastelor
Pașii 4 și 6 ai algoritmului de extindere a cheilor sunt formatarea unei secvențe pseudo-aleatoare de 2304 de octeți pentru a produce 8 chei rotunde. Dacă prima parte a tastei rotunde utilizată pentru adăugarea modulo 2 poate avea o structură complet aleatorie, atunci tabelul corect de permutare trebuie să fie format din 256 de valori care nu se repetă de la 0 la 255, iar cerințele suplimentare sunt impuse pentru cei 16 octeți. tabel index.
Astfel, la formatare, se efectuează următoarele acțiuni:
- Împărțirea unei matrice de 2304 de octeți în 8 fragmente de 16 + 256 + 16 octeți.
- Primii 16 octeți ai fragmentului devin prima parte a cheii rotunde, neschimbate.
- Următorii 256 de octeți (să numim acest fragment A) sunt procesați printr-o procedură specială pentru a obține tabelul de permutare corect. Această procedură arată astfel:
- se creează o matrice t/ de 256 de octeți care conține valori consecutive de la 0 la 255;
- într-un ciclu de la 0 la 255 /-lea octet al tabelului de permutare T este determinat de formula:
![{\displaystyle T[i]=U[(index[i-1]+A[i])modL]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca0f1d0af88b783a9539e7a6df51181531179b99)
- index[il] este numărul elementului matricei t/ utilizat în pasul precedent (pentru pasul zero se ia egal cu 0), iar L este dimensiunea curentă a tabloului U\
- octetul utilizat al matricei U este aruncat, iar elementele matricei U situate după acesta sunt deplasate cu 1 octet la începutul matricei; astfel, valoarea lui L în fiecare trecere a acestui ciclu este redusă cu 1;
- dacă tabelul de permutare este creat pentru operația de decriptare, atunci acesta este inversat.
- Similar cu pasul 3, este creat un tabel index de 16 octeți.
- Sunt analizate lanțurile de legături din tabelul de index; dacă tabelul este format din mai multe lanțuri, tabelul se modifică pentru a obține un lanț de verigi, a cărui lungime va fi egală cu dimensiunea mesei.
- Tabelul este analizat din nou pentru a găsi indecși care îndeplinesc următoarea condiție:
![I[i]=i+1](https://wikimedia.org/api/rest_v1/media/math/render/svg/094ef96574929d429be5a2c3ae5527c328d27d6d)
dacă astfel de elemente de tabel există, valoarea lor se schimbă în
![I[i]=i+2](https://wikimedia.org/api/rest_v1/media/math/render/svg/737056e0004f440eb23b3b661ced1dbb4f546624)
Pașii 3-5 ai procedurii de formatare merită luați în considerare cu un exemplu. Să presupunem că un tabel de index de 6 octeți este creat din următorul fragment de 6 octeți al unei secvențe pseudo-aleatoare:
21.247.199.108.66.239
În bucla de la 0 la 5 (pasul 4), octetul /-lea al tabelului de index I este determinat de formula:
![I[i]=U[(index[i-1]+A[i])mod L]](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab73234787f5037aeda42dcd1d7214047b77015e)
care în exemplul secvenței de mai sus arată ca cel prezentat în tabel:
Rezultatul este un tabel index:
3,2,5,1,0,4
3,0,5,1,2,4
Analiza tabelului (pasul 5) ne permite să aflăm că acest tabel este format din două lanțuri de verigi:
3→1→2→5→4→2→0→3
3→1→0→3 și 5→4→2→5
Cu toate acestea, pentru a obține puterea criptografică maximă a algoritmului, tabelul index trebuie să conțină un lanț de dimensiunea maximă. Algoritmul efectuat la pasul 5 vă permite să combinați mai multe lanțuri într-unul singur.
Avantajele și dezavantajele algoritmului
La fel ca mulți algoritmi precum AES (Rijndael) sau SAFER+, FROG este orientat pe octeți. Cu toate acestea, spre deosebire de transformările utilizate în acești algoritmi explicate și explicate de autorii lui Rijndael și SAFER +, autorii algoritmului FROG s-au limitat la a explica că o astfel de structură rotundă neobișnuită a fost aleasă pentru a asigura cea mai rapidă dispersie a date de intrare (adică asigurarea influenței fiecărui bit de date criptate asupra fiecărui biți de text cifrat dintr-un bloc).
Cu toate acestea, FROG a fost recunoscut drept unul dintre cei mai slabi participanți la competiția AES; a găsit multe neajunsuri, în special:
- o parte destul de mare din setul de chei posibile ale algoritmului s-a dovedit a fi slabă (datorită unei proceduri de extindere a cheilor foarte complexe) la diferite tipuri de atacuri;
- algoritmul s-a dovedit a fi lent și chiar în comparație cu algoritmii cunoscuți înainte de competiția AES, de exemplu, Blowfish și RC5;
- algoritmul FROG s-a dovedit a fi foarte solicitant pe RAM - are nevoie de aproximativ 2500 de octeți dacă cheile rotunde sunt generate în avans și sunt necesari aproximativ 5000 de octeți pentru algoritmul cu funcții complete, care include procedura de extindere a cheilor; aceste cerințe sunt foarte mari (mai ales în comparație cu alți algoritmi - participanți la competiția AES) pentru implementarea acestui algoritm în cardurile inteligente;
- există o serie de chei slabe pentru acest algoritm. Procedura de setare a cheilor este relativ lentă datorită mecanismului complex de generare a tabelelor de transformare. Cifrul în sine are o performanță relativ scăzută, deși după instalarea cheii, 8 runde de conversie sunt efectuate destul de rapid - implementat în 8086 assembler FROG rulează la o viteză de 2,2 MB/s pe un PC cu procesor Pentium 200;
- criptoanalistii au atras atentia si asupra vulnerabilitatii functiei de decriptare si a difuzarii ei destul de lente ;
- alți participanți la AES au arătat că cheia de cifră Frog este spartă folosind 257 de operații.
Astfel, algoritmul FROG nu a ajuns în finala competiției AES.
Literatură
- Curs „Securitatea Informației”, Departamentul de Inginerie Radio, Institutul de Fizică și Tehnologie din Moscova (MIPT), eseu „Review of AES Candidates”, Lipatiev, 2004
- http://crypto.pp.ua/2010/12/algoritm-frog/
| Criptosisteme simetrice | |
|---|---|
| Cifruri în flux | |
| Rețeaua Feistel | |
| Rețeaua SP | |
| Alte | |