AES

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

AES (de la Advanced Encryption Standard - în limba engleză, Standard Avansat de Criptare), cunoscut și sub numele de Rijndael, este un algoritm standardizat pentru criptarea simetrică, pe blocuri, folosit astăzi pe scară largă în aplicații și adoptat ca standard de organizația guvernamentală americană NIST.[1] Standardul oficializează algoritmul dezvoltat de doi criptografi belgieni, Joan Daemen și Vincent Rijmen și trimis la NIST pentru selecție sub numele Rijndael.

Origine[modificare | modificare sursă]

Vincent Rijmen, coautor al algoritmului Rijndael

Deoarece DES devenise vulnerabil din cauza lungimii prea mici a cheii, NIST a recomandat utilizarea 3DES, un algoritm care constă în esență în aplicarea de trei ori a DES. Deși 3DES s-a dovedit a fi un algoritm puternic, el este relativ lent în implementările software,[2] motiv pentru care NIST a lansat în 1997 o cerere de propuneri pentru un algoritm care să-l înlocuiască. S-a pornit de la 21 de propuneri acceptate inițial, apoi prin eliminări numărul lor a fost redus la 15, și apoi la 5, din care a fost ales în cele din urmă algoritmul propus de doi criptografi belgieni, Joan Daemen și Vincent Rijmen. La votarea finală, algoritmul, denumit de autorii săi Rijndael, a învins la vot patru alte propuneri, printre care și algoritmul RC6, propus de o echipă de criptografi în care se afla și reputatul informatician Ron Rivest.

Criteriile pe baza cărora au fost evaluate propunerile pentru AES au fost securitatea (rezistența la atacuri criptanalitice), costurile (eficiența computațională, complexitatea spațială, precum și licențierea liberă și gratuită) și particularitățile algoritmului (flexibilitatea, simplitatea, și ușurința de realizare a implementărilor atât software cât și hardware).[3]

Algoritmul[modificare | modificare sursă]

În propunerea avansată NIST, cei doi autori ai algoritmului Rijndael au definit un algoritm de criptare pe blocuri în care lungimea blocului și a cheii puteau fi independente, de 128 de biți, 192 de biți, sau 256 de biți. Specificația AES standardizează toate cele trei dimensiuni posibile pentru lungimea cheii, dar restricționează lungimea blocului la 128 de biți.[4] Astfel, intrarea și ieșirea algoritmilor de criptare și decriptare este un bloc de 128 de biți. În publicația FIPS numărul 197, operațiile AES sunt definite sub formă de operații pe matrice, unde atât cheia, cât și blocul sunt scrise sub formă de matrice.[5] La începutul rulării cifrului, blocul este copiat într-un tablou denumit stare (în engleză state), primii patru octeți pe prima coloană, apoi următorii patru pe a doua coloană, și tot așa până la completarea tabloului.[5]

Algoritmul modifică la fiecare pas acest tablou de numere denumit state, și îl furnizează apoi ca ieșire. Funcționarea sa este descrisă de următorul pseudocod:[6]

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
 begin
   byte state[4,Nb]
   state = in
   AddRoundKey(state, w[0, Nb-1])
   for round = 1 step 1 to Nr–1
      SubBytes(state)
      ShiftRows(state)
      MixColumns(state)
      AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
   end for
   SubBytes(state)
   ShiftRows(state)
   AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
   out = state
 end

Aici, Nb este numărul de coloane al stării, în varianta standardizată acesta fiind întotdeauna 4. Se observă din descrierea algoritmului că o anumită secvență este realizată iterativ, de un număr de Nr ori. Acest Nr depinde de lungimea cheii și este 10, 12 sau 14, pentru chei pe 128, 192, respectiv 256 biți.[7]

Pasul SubBytes[modificare | modificare sursă]

La pasul SubBytes, fiecare octet din blocul state este înlocuit cu un altul, conform unui cifru cu substituţie

Pasul SubBytes este un cifru cu substituție, fără punct fix, denumit Rijndael S-box, care rulează independent pe fiecare octet din state. Această transformare este neliniară și face astfel întreg cifrul să fie neliniar, ceea ce îi conferă un nivel sporit de securitate.

Fiecare octet este calculat astfel:

b_i^\prime = b_i \oplus b_{(i+4) mod 8} \oplus b_{(i+5) mod 8} \oplus b_{(i+6) mod 8} \oplus b_{(i+7) mod 8} \oplus c_i

unde bi este bitul corespunzător poziției i din cadrul octetului, iar ci este bitul corespunzător poziției i din octetul ce reprezintă valoarea hexazecimală 63, sau, pe biți, 01100011.[8] Maparea octeților se poate reține într-un tabel, explicitat în FIPS PUB 197, în care este specificat rezultatul operației de mai sus efectuată pe fiecare din cele 256 de valori posibile reprezentabile pe un octet.[9]

Pasul ShiftRows[modificare | modificare sursă]

Pasul ShiftRows

Pasul ShiftRows operează la nivel de rând al matricii de stare state. Pasul constă în simpla deplasare ciclică a octeților de pe rânduri, astfel: primul rând nu se deplasează; al doilea rând se deplasează la stânga cu o poziție; al treilea rând se deplasează la stânga cu două poziții; al patrulea se deplasează la stânga cu trei poziții.[10] Rezultatul acestui pas este că fiecare coloană din tabloul state rezultat este compusă din octeți de pe fiecare coloană a stării inițiale. Acesta este un aspect important, din cauză că tabloul state este populat inițial pe coloane, iar pașii ulteriori, inclusiv AddRoundKey în care este folosită cheia de criptare, operațiile se efectuează pe coloane.[11]

Pasul MixColumns[modificare | modificare sursă]

În pasul MixColumns, fiecare coloană este înmulţită cu un polinom, notat în figură cu c(x)

În acest pas, fiecare coloană a tabloului de stare este considerată un polinom de gradul 4 peste corpul Galois F_{2^8}. Fiecare coloană, tratată ca polinom, este înmulțită, modulo x^4+1 cu polinomul a(x)=3x^3 + x^2 + x + 2. Operația se poate scrie ca înmulțire de matrice astfel:[12]

\begin{bmatrix}s_0^{\prime}\\s_1^{\prime}\\s_2^{\prime}\\s_3^{\prime}\end{bmatrix} =
\begin{bmatrix}
2&3&1&1 \\
1&2&3&1 \\
1&1&2&3 \\
3&1&1&2 \end{bmatrix} \begin{bmatrix}s_0\\s_1\\s_2\\s_3\end{bmatrix}

unde s_i^{\prime} sunt elementele de pe un vector coloană rezultate în urma înmulțirii, iar s_i sunt elementele de pe același vector înaintea aplicării pasului.

Rezultatul are proprietatea că fiecare element al său depinde de toate elementele de pe coloana stării dinaintea efectuării pasului. Combinat cu pasul ShiftRows, acest pas asigură că după câteva iterații, fiecare octet din stare depinde de fiecare octet din starea inițială (tabloul populat cu octeții mesajului în clar).[13] Acești doi pași, împreună, sunt principala sursă de difuzie în algoritmul Rijndael. Coeficienții polinomului a(x) sunt toți 1, 2 și 3, din motive de performanță, criptarea fiind mai eficientă atunci când coeficienții sunt mici. La decriptare, coeficienții pasului corespunzător acestuia sunt mai mari și deci decriptarea este mai lentă decât criptarea. S-a luat această decizie pentru că unele din aplicațiile în care urma să fie folosit algoritmul implică numai criptări, și nu și decriptări, deci criptarea este folosită mai des.[13]

Pasul AddRoundKey și planificarea cheilor[modificare | modificare sursă]

În pasul AddRoundKey, se efectuează o operaţie de sau exclusiv pe biţi între octeţii stării şi cei ai cheii de rundă

Pasul AddRoundKey este pasul în care este implicată cheia. El constă într-o simplă operație de „sau” exclusiv pe biți între stare și cheia de rundă (o cheie care este unică pentru fiecare iterație, cheie calculată pe baza cheii secrete). Operația de combinare cu cheia secretă este una extrem de simplă și rapidă, dar algoritmul rămâne complex, din cauza complexității calculului cheilor de rundă (Key Schedule), precum și a celorlalți pași ai algoritmului.[14]

Cheia de rundă este calculată după algoritmul următor:[15]

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
 begin
  word temp
  i = 0
  while (i < Nk)
   w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
   i = i+1
  end while
  i = Nk
  while (i < Nb * (Nr+1)]
   temp = w[i-1]
   if (i mod Nk = 0)
     temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
   else if (Nk > 6 and i mod Nk = 4)
     temp = SubWord(temp)
   end if
   w[i] = w[i-Nk] xor temp
   i = i + 1
  end while
 end

Acest algoritm lucrează pe cheia algoritmului, de lungime Nk cuvinte de 4 octeți (4, 6 sau 8, conform standardului), populând un tabel de Nb \times (Nr + 1) cuvinte, Nb fiind numărul de cuvinte al blocului (în versiunea standardizată, 4), iar Nr numărul de runde (iterații), dependent de lungimea cheii. Algoritmul de planificare a cheilor folosește transformarea SubWord, care este o substituție a octeților identică cu cea din pasul SubBytes.[16] RotWord este o rotație ciclică la stânga cu un octet a octeților dintr-un cuvânt.[16] Cu Rcon[i] se notează în algoritm un cuvânt format din octeții \left[2^{i-1}, \{00\}, \{00\}, \{00\}\right]. Operația de ridicare la putere este aici cea valabilă în corpul Galois F_{2^8}.[16] Tabloul w conține la finalul prelucrării cuvintele de pe coloanele cheilor de rundă, în ordinea în care urmează să fie aplicate.

Securitatea[modificare | modificare sursă]

Rijndael, ca și toți ceilalți algoritmi ajunși în etapa finală de selecție pentru standardul AES, a fost revizuit de NSA și, ca și ceilalți finaliști, este considerat suficient de sigur pentru a fi folosit la criptarea informațiilor guvernamentale americane neclasificate. În iunie 2003, guvernul SUA a decis ca AES să poată fi folosit pentru informații clasificate. Până la nivelul SECRET, se pot folosi toate cele trei lungimi de cheie standardizate, 128, 192 și 256 biți. Informațiile TOP SECRET (cel mai înalt nivel de clasificare) pot fi criptate doar cu chei pe 256 biți.[17]

Atacul cel mai realizabil împotriva AES este îndreptat împotriva variantelor Rijndael cu număr redus de iterații. AES are 10 iterații la o cheie de 128 de biți, 12 la cheie de 192 de biți și 14 la cheie de 256 de biți. La nivelul anului 2008, cele mai cunoscute atacuri erau accesibile la 7, 8, respectiv 9 iterații pentru cele trei lungimi ale cheii.[18]

Note[modificare | modificare sursă]

  1. ^ NIST reports measurable success of Advanced Encryption Standard - News Briefs - National Institute of Standards and Technology - Brief Article”. Journal of Research of the National Institute of Standards and Technology, May-June, 2002. http://findarticles.com/p/articles/mi_m0IKZ/is_3_107/ai_90984479. 
  2. ^ Stallings, p. 137
  3. ^ Stallings, p. 138
  4. ^ Stallings, p. 140
  5. ^ a b FIPS PUB 197, cap. 3.2, p. 9
  6. ^ FIPS PUB 197, cap. 5.1, p. 15
  7. ^ FIPS PUB 197, cap. 5, p. 14
  8. ^ FIPS PUB 197, cap. 5.1.1, p. 15
  9. ^ FIPS PUB 197, cap. 5.1.1, p. 16
  10. ^ FIPS PUB 197, cap. 5.1.2, p. 17
  11. ^ Stallings, p. 150
  12. ^ FIPS PUB 197, cap. 5.1.3, pp. 16-17
  13. ^ a b Stallings, p. 154
  14. ^ Stallings, p. 155
  15. ^ FIPS PUB 197, cap. 5.2, p. 20
  16. ^ a b c FIPS PUB 197, cap. 5.2, p. 19
  17. ^ National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information” (în engleză). Comitetul pentru Sisteme de Securitate Naționale, SUA. iunie 2003. http://www.cnss.gov/Assets/pdf/cnssp_15_fs.pdf. Accesat la 27 mai 2008. 
  18. ^ John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, Doug Whiting (2000). „Improved Cryptanalysis of Rijndael, Fast Software Encryption Workshop”. Springer-Verlag. http://www.schneier.com/paper-rijndael.html. 

Bibliografie[modificare | modificare sursă]