AES

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

Vincent Rijmen, coautor al algoritmului Rijndael

Deoarece DES devenise vulnerabil datorită 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

Î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

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:

unde b_i este bitul corespunzător poziţiei i din cadrul octetului, iar c_i 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

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

Î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 . Fiecare coloană, tratată ca polinom, este înmulţită, modulo x⁴ + 1 cu polinomul a(x) = 3x³ + x² + x + 2. Operaţia se poate scrie ca înmulţire de matrice astfel:^[12]

unde 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

Î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 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 . Operaţia de ridicare la putere este aici cea valabilă în corpul Galois .^[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

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

Bibliografie

• William Stallings (2005). Cryptography and Network Security, 4th edition. Prentice Hall. ISBN 0-13-187319-3.
• Publicaţia FIPS 197 (în engleză). Federal Information Processing Standards (26 noiembrie 2001).

Accesat la data de 2008-05-26.

Acest articol din domeniul informaticii este deocamdată un ciot. Puteţi ajuta Wikipedia prin dezvoltarea lui.