Algoritmul de criptografie AES

Articol postat de:

AES

AES (de la Advanced Encryption Standard – in limba engleza, Standard Avansat de Criptare), cunoscut si sub numele de Rijndael, este un algoritm standardizat pentru criptarea simetrica, pe blocuri, folosit astazi pe scara larga in aplicatii si adoptat ca standard de organizatia guvernamentala americana NIST. Standardul oficializeaza algoritmul dezvoltat de doi criptografi belgieni, Joan Daemen si Vincent Rijmen si trimis la NIST pentru selectie sub numele Rijndael.

Deoarece DES devenise vulnerabil din cauza lungimii prea mici a cheii, NIST a recomandat utilizarea 3DES, un algoritm care consta in esenta in aplicarea de trei ori a DES. Desi 3DES s-a dovedit a fi un algoritm puternic, el este relativ lent in implementarile software, motiv pentru care NIST a lansat in 1997 o cerere de propuneri pentru un algoritm care sa-l inlocuiasca. S-a pornit de la 21 de propuneri acceptate initial, apoi prin eliminari numarul lor a fost redus la 15, si apoi la 5, din care a fost ales in cele din urma algoritmul propus de doi criptografi belgieni, Joan Daemen si Vincent Rijmen. La votarea finala, algoritmul, denumit de autorii sai Rijndael, a invins la vot patru alte propuneri, printre care si algoritmul RC6, propus de o echipa de criptografi in care se afla si reputatul informatician Ron Rivest.

Criteriile pe baza carora au fost evaluate propunerile pentru AES au fostsecuritatea (rezistenta la atacuri criptanalitice), costurile (eficienta computationala, complexitatea spatiala, precum si licentierea libera si gratuita) si particularitatile algoritmului (flexibilitatea, simplitatea, si usurinta de realizare a implementarilor atat software cat si hardware).

Algoritmul

In propunerea avansata NIST, cei doi autori ai algoritmului Rijndael au definit un algoritm de criptare pe blocuri in care lungimea blocului si a cheii puteau fi independente, de 128 de biti, 192 de biti, sau 256 de biti. Specificatia AES standardizeaza toate cele trei dimensiuni posibile pentru lungimea cheii, dar restrictioneaza lungimea blocului la 128 de biti. Astfel, intrarea si iesirea algoritmilor de criptare si decriptare este un bloc de 128 de biti. In publicatia FIPS numarul 197, operatiile AES sunt definite sub forma de operatii pe matrice, unde atat cheia, cat si blocul sunt scrise sub forma de matrice. La inceputul rularii cifrului, blocul este copiat intr-un tablou denumit stare (in engleza state), primii patru octeti pe prima coloana, apoi urmatorii patru pe a doua coloana, si tot asa pana la completarea tabloului.

Algoritmul modifica la fiecare pas acest tablou de numere denumitstate, si il furnizeaza apoi ca iesire. Functionarea sa este descrisa de urmatorul pseudocod:

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 numarul de coloane al starii, in varianta standardizata acesta fiind intotdeauna 4. Se observa din descrierea algoritmului ca o anumita secventa este realizata iterativ, de un numar de Nr ori. AcestNr depinde de lungimea cheii si este 10, 12 sau 14, pentru chei pe 128, 192, respectiv 256 biti.

Pasul SubBytes

AES

Pasul SubBytes este un cifru cu substitutie, fara punct fix, denumitRijndael S-box, care ruleaza independent pe fiecare octet din state. Aceasta transformare este neliniara si face astfel intreg cifrul sa fie neliniar, ceea ce ii confera un nivel sporit de securitate.

Fiecare octet este calculat astfel:

unde bi este bitul corespunzator pozitiei i din cadrul octetului, iar ci este bitul corespunzator pozitiei i din octetul ce reprezinta valoarea hexazecimala 63, sau, pe biti, 01100011. Maparea octetilor se poate retine intr-un tabel, explicitat in FIPS PUB 197, in care este specificat rezultatul operatiei de mai sus efectuata pe fiecare din cele 256 de valori posibile reprezentabile pe un octet.

Pasul ShiftRows

AES

Pasul ShiftRows opereaza la nivel de rand al matricii de stare state. Pasul consta in simpla deplasare ciclica a octetilor de pe randuri, astfel: primul rand nu se deplaseaza; al doilea rand se deplaseaza la stanga cu o pozitie; al treilea rand se deplaseaza la stanga cu doua pozitii; al patrulea se deplaseaza la stanga cu trei pozitii. Rezultatul acestui pas este ca fiecare coloana din tabloul state rezultat este compusa din octeti de pe fiecare coloana a starii initiale. Acesta este un aspect important, din cauza ca tabloul state este populat initial pe coloane, iar pasii ulteriori, inclusiv AddRoundKey in care este folosita cheia de criptare, operatiile se efectueaza pe coloane.

Pasul MixColumns 

AES

In acest pas, fiecare coloana a tabloului de stare este considerata un polinom de gradul 4 peste corpul Galois F28. Fiecare coloana, tratata ca polinom, este inmultita, modulo x4 + 1 cu polinomul a(x) = 3x3 + x2 +x + 2. Operatia se poate scrie ca inmultire de matrice astfel:

unde si sunt elementele de pe un vector coloana rezultate in urma inmultirii, iar si sunt elementele de pe acelasi vector inaintea aplicarii pasului.

Rezultatul are proprietatea ca fiecare element al sau depinde de toate elementele de pe coloana starii dinaintea efectuarii pasului. Combinat cu pasul ShiftRows, acest pas asigura ca dupa cateva iteratii, fiecare octet din stare depinde de fiecare octet din starea initiala (tabloul populat cu octetii mesajului in clar). Acesti doi pasi, impreuna, sunt principala sursa de difuzie in algoritmul Rijndael. Coeficientii polinomului a(x) sunt toti 1, 2 si 3, din motive de performanta, criptarea fiind mai eficienta atunci cand coeficientii sunt mici. La decriptare, coeficientii pasului corespunzator acestuia sunt mai mari si deci decriptarea este mai lenta decat criptarea. S-a luat aceasta decizie pentru ca unele din aplicatiile in care urma sa fie folosit algoritmul implica numai criptari, si nu si decriptari, deci criptarea este folosita mai des.

Pasul AddRoundKey si planificarea cheilor 

AES

Pasul AddRoundKey este pasul in care este implicata cheia. El consta intr-o simpla operatie de „sau” exclusiv pe biti intre stare si cheia de runda (o cheie care este unica pentru fiecare iteratie, cheie calculata pe baza cheii secrete). Operatia de combinare cu cheia secreta este una extrem de simpla si rapida, dar algoritmul ramane complex, din cauza complexitatii calculului cheilor de runda (Key Schedule), precum si a celorlalti pasi ai algoritmului.

Cheia de runda este calculata dupa algoritmul urmator:

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 lucreaza pe cheia algoritmului, de lungime Nk cuvinte de 4 octeti (4, 6 sau 8, conform standardului), populand un tabel de Nb(Nr+1) cuvinte, Nb fiind numarul de cuvinte al blocului (in versiunea standardizata, 4), iar Nr numarul de runde (iteratii), dependent de lungimea cheii. Algoritmul de planificare a cheilor foloseste transformarea SubWord, care este o substitutie a octetilor identica cu cea din pasul SubBytesRotWord este o rotatie ciclica la stanga cu un octet a octetilor dintr-un cuvant. Cu Rcon[i] se noteaza in algoritm un cuvant format din octetii [2i-1,{00}, {00}, {00}]. Operatia de ridicare la putere este aici cea valabila in corpul Galois F28. Tabloul w contine la finalul prelucrarii cuvintele de pe coloanele cheilor de runda, in ordinea in care urmeaza sa fie aplicate.

Securitatea

Rijndael, ca si toti ceilalti algoritmi ajunsi in etapa finala de selectie pentru standardul AES, a fost revizuit de NSA si, ca si ceilalti finalisti, este considerat suficient de sigur pentru a fi folosit la criptarea informatiilor guvernamentale americane neclasificate. In iunie 2003, guvernul SUA a decis ca AES sa poata fi folosit pentru informatii clasificate. Pana la nivelul SECRET, se pot folosi toate cele trei lungimi de cheie standardizate, 128, 192 si 256 biti. Informatiile TOP SECRET(cel mai inalt nivel de clasificare) pot fi criptate doar cu chei pe 256 biti.

Atacul cel mai realizabil impotriva AES este indreptat impotriva variantelor Rijndael cu numar redus de iteratii. AES are 10 iteratii la o cheie de 128 de biti, 12 la cheie de 192 de biti si 14 la cheie de 256 de biti. La nivelul anului 2008, cele mai cunoscute atacuri erau accesibile la 7, 8, respectiv 9 iteratii pentru cele trei lungimi ale cheii.

Sursa: Wikipedia


Add Comment Register



Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile necesare sunt marcate *


*

Poți folosi aceste etichete HTML și atribute: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>