Khufu

Khufu
Creator Ralph Merkle
Creată 1990
publicat 1990
Dimensiunea cheii 512 biți
Dimensiunea blocului pe 64 de biți
Numărul de runde 8-32 (până la 64)
Tip de Rețeaua Feistel

Khufu  este un algoritm criptografic bloc simetric pe 64 de biți dezvoltat de Ralph Merkle în 1990, numit după faraonul egiptean Keops .

Context istoric

La momentul creării algoritmului (sfârșitul anului 1990), marea majoritate a algoritmilor de criptare simetrică care existau la acel moment erau adaptați pentru implementări hardware, în ciuda faptului că implementarea hardware a algoritmului de criptare este, în primul rând , mai scump decât software-ul, adică mai puțin accesibil pentru marea majoritate a potențialilor utilizatori.

Așadar, la sfârșitul anilor 1990, un grup de criptografi de la compania Xerox a dezvoltat un cifr - Khufu, numit după faraonul egiptean Keops. Algoritmul a fost prezentat în continuare în 1990 la conferința CRYPTO .

În anul următor (1991), Xerox Corporation a primit un brevet pentru algoritmii Khufu și Khafre, în urma căruia utilizarea lor comercială a fost interzisă de titularul brevetului [1] .

Cerințe preliminare pentru crearea unui algoritm

Algoritmul Khufu este un algoritm bloc bazat pe rețeaua Feistel , construit pe baza următoarelor postulate:

Baza teoretică a algoritmului Khufu este experiența acumulată în dezvoltarea algoritmului DES . Prin urmare, la proiectarea algoritmului, au fost luate în considerare următoarele condiții preliminare [3] :

  1. Dimensiunea cheii DES pe 56 de biți este prea mică și ar trebui mărită.
  2. Utilizarea intensă a permutărilor în DES este convenabilă doar pentru implementările hardware, dar face implementările software dificile. Cele mai rapide implementări ale DES realizează permutări într-un mod tabelar. Căutările în tabele pot oferi aceleași caracteristici de „împrăștiere” ca și permutările în sine și pot face implementarea mai flexibilă.
  3. S-box-urile din DES, cu doar 64 de elemente pe 4 biți, sunt prea mici, așa că S - box-urile trebuie mărite. Mai mult, toate cele opt cutii S sunt utilizate simultan. Acest lucru este convenabil pentru hardware, dar pentru implementarea software pare o limitare inutilă, deci este mai potrivit să implementați o dimensiune S - box mai mare. În plus, trebuie implementată utilizarea în serie (mai degrabă decât în ​​paralel) a cutiilor S în timpul înlocuirilor.
  4. Permutările inițiale și finale sunt lipsite de sens criptografic, așa că trebuie eliminate.
  5. Toate implementările rapide DES precalculează cheile pentru fiecare pas. În această condiție, nu are rost să complicăm aceste calcule.
  6. Criteriile de proiectare pentru cutiile S ar trebui să fie disponibile publicului.

Algoritm

Parametrii algoritmului

Algoritmul criptează datele în blocuri, dimensiunea blocului este de 64 de biți. Apoi, în timpul procesului de criptare, fiecare bloc este împărțit în 2 sub-blocuri, fiecare cu dimensiunea de 32 de biți.

Deși părți ale cheii (subcheile K 0 ..K 3 ) sunt folosite doar pentru a adăuga subblocuri la începutul și la sfârșitul algoritmului, scopul principal al cheii este de a genera S -box- uri. Algoritmul oferă o modalitate de a genera cutii S cu ajutorul tastei [3] .

Algoritmul are următorii parametri [4] [3] :

  1. Dimensiunea blocului de criptare este de 64 de biți.
  2. Dimensiunea cheii de criptare trebuie să fie între 64 și 512 biți. În acest caz, dimensiunea cheii trebuie să fie un multiplu de 64.
  3. Blocul S are 8 biți de intrare și 32 de biți de ieșire. Este variabilă. Fiecare octet folosește propria sa S - box [1] .

Algoritm pentru construirea S-box-urilor

Algoritmul constă în generarea de subchei și a unui tabel de înlocuire standard. Pe baza tabelului de substituție standard, cutiile S sunt construite pentru fiecare octet de transformare.

Construirea unui tabel de înlocuire standard
  • La începutul acestei proceduri, este inițializat un tabel de 256 de rânduri pe 5 coloane. Prima coloană conține toate valorile posibile de octeți (de la 00 la FF, respectiv). Celelalte patru coloane sunt umplute cu valori similare. Mai jos este un fragment dintr-un astfel de tabel, care indică linia 1, 2 și respectiv 256 [5] .
Fragment de tabel standard inițializat
octet 4 octeți
00 00 00 00 00
01 01 01 01 01
FF FF FF FF FF
  • Într-o coloană, apar permutări de octeți (procedura este similară cu permutarea octeților din caseta S când a fost creată), unde un set de un milion de numere aleatoare de la RAND Corporation, publicat în 1995, este folosit ca pseudo -secventa aleatorie.
Fragment din tabelul standard după iterații
octet 4 octeți
00 FA A1 22 41
01 71 88 B3 cincisprezece
FF 44 unsprezece C4 E1
  • După aceste iterații, se formează un tabel de substituție standard. Un fragment din acest tabel este prezentat mai sus.
Generarea de subchei și S-box-uri

Ideea principală a algoritmului Khufu este că subcheile și casetele S depind de cheia rotundă, în timp ce în timpul fiecărei runde, algoritmul Khufu utilizează o singură înlocuire a ultimilor 8 biți ai subblocului din stânga cu 32 de biți, spre deosebire de algoritmul DES. Luați în considerare algoritmul pentru construirea S -box-urilor și subcheilor. Este construit în mai multe etape [6] :

  1. În prima etapă, cheia este scrisă pe cei 64 de octeți alocați pentru aceasta, în timp ce biții neutilizați sunt setați la zero (reamintim că dimensiunea posibilă a cheii variază de la 8 la 64 de octeți).
  2. În a doua etapă, acest bloc este criptat de algoritmul Khufu în modul de înlănțuire a blocurilor de criptare. Secvența zero este luată ca subchei ( K 0 .. K 3 ) pentru fiecare bloc, iar tabelul standard, care a fost descris mai sus, este luat ca tabele de substituție. Ieșirea este o secvență pseudo-aleatorie de 64 de octeți care depinde doar de cheia de criptare. Este posibil să fie necesari mai mulți octeți pentru a genera tabele și subchei, astfel încât acest pas poate fi repetat de mai multe ori.
  3. În a treia etapă, valorile subcheilor ( K 0 .. K 3 ) sunt selectate din setul de biți dat .
  4. La a patra etapă, cutiile S sunt construite pentru fiecare octet de transformare:
    • Fiecare S -box calculată este inițializată cu tabelul de înlocuire standard original, care este descris mai sus.
    • În tabelul standard original de substituții, într-un ciclu prin coloane (de la 0 la 3 octet, respectiv), se efectuează un ciclu pe rânduri (de la 0 la 255 octet), în care fiecare octet curent (octetul de la intersecția rândul curent și coloana curentă) este schimbat cu unul dintre următorii octeți ai aceleiași coloane, determinati aleatoriu (depinde de octetul curent al secvenței pseudoaleatoare); rezultatul este tabelul original cu octeți rearanjați „haotic” ai fiecărei coloane [4] .

Procedura de criptare

Criptarea are loc pe un singur bloc de date de 64 de biți. La începutul procedurii, pe acest bloc sunt efectuate următoarele acțiuni:

  • Un bloc de date pe 64 de biți este împărțit în două blocuri a câte 32 de biți fiecare (în continuare le vom numi L și respectiv R).
  • Fiecare dintre subblocuri este XOR pe biți cu subblocurile K 0 și respectiv K 1 (pentru subblocul stâng - K 0 , pentru dreapta - K 1 ).

Apoi se realizează criptarea. Numărul de repetări ale pașilor este egal cu numărul de runde ale algoritmului.

  • În prima etapă, octetul inferior (ultimii 8 biți) al subblocului din stânga este trecut prin blocul S , din care se obține o valoare de 4 octeți (32 de biți). Mai mult, în fiecare octet de operații se folosește un bloc S , destinat acestui octet.
  • În al doilea pas, valoarea obținută în pasul precedent este adăugată bit cu bit (XOR) cu subblocul de text din dreapta.
  • Al treilea pas se rotește la stânga cu un număr diferit de biți ai subblocului din stânga, care depinde de numărul rotund din octet:
    1. 8 - dacă numărul este 3 sau 4
    2. 24 - dacă numărul este 7 sau 8
    3. 16 - în toate celelalte cazuri
  • În al patrulea pas, subblocurile din stânga și din dreapta sunt schimbate.

După aceea, toți pașii sunt repeți din nou, inclusiv schimbarea blocului S la fiecare 8 runde.

La sfârşitul procedurii, după parcurgerea tuturor rundelor prevăzute, adunarea se realizează similar cu adunarea cu subcheile K 0 şi K 1 , dar cu alte subcheile K 2 şi respectiv K 3 [7] .

Utilizare și durabilitate

Dependența de S - box-uri și subchei le face secrete pentru criptoanalist, ceea ce crește semnificativ securitatea algoritmului împotriva criptoanalizei diferențiale. Aceasta implică specificația principală a acestui algoritm: algoritmul Khufu ar trebui utilizat acolo unde este necesară criptarea de mare viteză a cantităților mari de date cu o schimbare rară a cheii [8] .

Comparația algoritmului cu DES

Pentru ca fiecare bit de ieșire să depindă de fiecare intrare în algoritmul DES, trebuie efectuate 5 runde. În algoritmul Khufu, o dependență similară necesită 9 runde. În acest caz, factorul de securitate este egal cu următoarea expresie: , unde parametrii  sunt numărul de runde ,  este numărul de runde necesare pentru criptarea completă . Astfel, pentru algoritmul DES și pentru algoritmul Khufu, parametrul corespunzător este . În acest caz, în ceea ce privește această comparație, algoritmul Khufu este inferior algoritmului DES. Cu toate acestea, casetele S ale algoritmului Khufu sunt secrete, spre deosebire de algoritmul DES [9] .

Atacurile asupra cifrului

Cel mai bun [10] atac asupra cifrului Khufu este al lui Gilbert și Showo. Atacul a fost făcut pe un Khufu cu 16 runde. Pentru a dezvălui complet informațiile ascunse, au fost necesare 231 de texte clare selectate. Dar acest rezultat nu a putut fi extins la mai multe runde. Dacă se folosește o cheie mai mare, algoritmul va fi pur și simplu ineficient [10] .

Cifrul este rezistent la atacurile cu forță brută. Cheia de 512 biți oferă o dificultate de cracare de 2512, ceea ce face ca cifrul să fie rezistent la această metodă [3] .

Vezi și

  • Un milion de cifre aleatorii cu 100.000 de abateri

Note

  1. ↑ 1 2 Panasenko, 2009 .
  2. ↑ Panasenko, 2009 , p. 288-289.
  3. ↑ 1 2 3 4 Schneier Bruce. capitolul 13. p.7. // Criptografia aplicată.
  4. ↑ 1 2 Panasenko, 2009 , p. 289-290.
  5. ↑ Panasenko, 2009 , p. 291-292.
  6. ↑ Panasenko, 2009 , p. 290-292.
  7. ↑ Panasenko, 2009, 289-290 .
  8. ↑ Panasenko, 2009 , p. 293-294.
  9. ↑ Merkle, 1991 .
  10. ↑ 1 2 Biham, Biryukov, Shamir, 1999 , pp. 131-137.

Literatură

 Criptosisteme simetrice
Cifruri în flux
Rețeaua Feistel
Rețeaua SP
Alte