2.7. Advanced Encryption Standard

1. mora biti simetričan

2. mora biti blokovni

3. treba raditi sa 128-bitnim blokovima i ključevima s tri duljine: 128, 192 i 256 bitova.

• 3DES koristi 48 rundi da bi postigao sigurnost za koju je vjerojatno dovoljno 32 runde.
• Softverske implementacije 3DES-a su prespore za neke primjene, posebno za digitalne video podatke.
• 64-bitni blokovi nisu najefikasniji u nekim primjenama.

Natječaj je zaključen 15.6.1998. Od 21 pristigle prijave, 15 ih je zadovoljilo NIST-ove kriterije. U kolovozu 1999. NIST je objavio 5 finalista: MARS, RC6, RIJNDAEL, SERPENT i TWOFISH. Recimo nekoliko riječi o ovih 5 finalista.

MARS (IBM), RC6 (RSA Security Inc.) i TWOFISH (Counterpane Systems) spadaju u Feistelove šifre. Podsjetimo se da je Feistelova šifra blokovna šifra u kojoj u i-toj rundi koristi formule L_i = R_{i -1}, R_i = L_{i -1} ⊕ f (R_{i -1}, K_i) (dakle, isto kao kod DES-a). MARS spada u nebalansirane Feistelove šifre jer se blokovi ne dijele na 2, već na 4 dijela. MARS ima 32 runde, RC6 ima 20 rundi, dok TWOFISH ima 16 rundi. Specifičnost kriptosustava RC6 (koji je dosta sličan RC5) jesu korištenje funkcije f(x) = x(2x+1), koja daje difuziju, te rotacija koje ovise o podacima, koje daju otpornost na diferencijalnu i linearnu kriptoanalizu. Specifičnost TWOFISH-a je da se S-kutije dinamički mijenjaju u ovisnosti o ključu, što komplicira diferencijalnu i linearnu kriptoanalizu.

SERPENT su konstruirali kriptografi iz Engleske, Izraela i Danske. Spada u supstitucijsko-permutacijske šifre. Ima 32 runde i, što je za njega specifično, u svakoj rundi paralelno koristi 32 identične S-kutije.

RIJNDAEL su razvili belgijski kriptografi. Razlikuje se od ostalih finalista po tome što se u konstrukciji S-kutija koriste operacije u konačnom polju GF(2⁸).

Konačno, 2000. godine objavljeno je da je pobjednik natječaja za AES RIJNDAEL (čitaj: rejn dol). Standard AES objavljen je kao FIPS 197 2001. godine. Godine 2023. FIPS 197 je ažuriran, ali bez tehničkih promjena u samom AES algoritmu. Rijndael je u izvornoj specifikaciji dopuštao i druge duljine blokova, dok standard AES koristi isključivo blokove duljine 128 bitova i ključeve duljine 128, 192 ili 256 bitova. RIJNDAEL su razvili belgijski kriptografi Joan Daemen i Vincent Rijmen s Katoličkog sveučilišta Leuven, po kojima je i dobio ime.

Kako smo već napomenuli, jedna od njegovih specifičnosti je korištenje konačnog polja GF(2⁸) (alternativna oznaka je F_2⁸). Preciznije, elementi od GF(2⁸) su polinomi oblika a₇x⁷ + a₆x⁶ + ... + a₁x + a₀, a_i ∈ {0, 1}, a operacije su zbrajanje i množenje polinoma iz Z₂[X] modulo fiksni ireducibilni polinom g(x) = x⁸ + x⁴ + x³ + x + 1. Dakle, uzimamo da je GF(2⁸) = Z₂[X] / (g(x)). Elemente od GF(2⁸) možemo prikazati i kao bajtove (nizove od 8 bitova). Npr. polinomu x⁶ + x⁴ + x² + x + 1 odgovara bajt 01010111 ili 57 u heksadecimalnom zapisu.

Primjer 2.6: Pomnožiti polinome x⁶ + x⁴ + x² + x + 1 i x⁷ + x + 1 iz polja GF(2⁸).

Najprije pomnožimo ova dva polinoma u prstenu Z₂[X]:

(x⁶ + x⁴ + x² + x + 1) · (x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1.

U RIJNDAEL-u se također koriste i operacije na polinomima s koeficijentima iz GF(2⁸) stupnja manjeg od 4. Svaki takav polinom možemo reprezentirati kao 4-bajtni vektor. Zbrajanje takvih polinoma se svodi na zbrajanje koeficijenata uz iste potencije (zbrajanje u GF(2⁸) smo već definirali). Da bi kod množenja dobili kao rezultat polinom stupnja manjeg od 4, moramo produkt reducirati modulo neki polinom četvrtog stupnja. U RIJNDAEL-u je za to izabran polinom X⁴ + 1. Polinom X⁴ + 1 je izabran da bi množenje bilo što jednostavnije za implementirati. Pritom polinom X⁴ + 1 nije ireducibilan nad Z₂[X], jer u Z₂[X] vrijedi: X⁴+1=(X+1)⁴. Stoga neće svi polinomi imati inverz. No, to ovdje nije ni nužno. Zapravo, vidjet ćemo da se postojanje inverza zahtijeva samo za jedan konkretan polinom, za kojeg ćemo postojanje inverza provjeriti u sljedećem primjeru. Uz ovaj izbor, množenje polinoma se može matrično zapisati ovako:

d0 d1 d2 d3

=

a0 a3 a2 a1 a1 a0 a3 a2 a2 a1 a0 a3 a3 a2 a1 a0

b0 b1 b2 b3

Ovdje je polinom d(X) = d₃X³ + d₂X² + d₁X+ d₀ rezultat množenja polinoma a(X) = a₃X³ + a₂X² + a₁X+ a₀ i b(X) = b₃X³ + b₂X² + b₁X+ b₀, u oznaci d(X) = a(X) ⊗ b(X).

Primjer 2.7: Izračunati:

(03 X³ + 01 X² + 01 X + 02) ⊗ (0B X³ + 0D X² + 09 X + 0E).

d₃ = 03 · 0E + 01 · 09 + 01 · 0D + 02 · 0B.

03 · 0E = (x + 1) · (x³ + x² + x) = x⁴ + x = 12,

01 · 09 = 09,       01 · 0D = 0D,

02 · 0B = x · (x³ + x + 1) = x⁴ + x² + x = 16.

d₃ = 12 + 09 + 0D + 16 = (x⁴ + x) + (x³ + 1) + (x³ + x² + 1) + (x⁴ + x² + x) = 00.

Ovaj račun objašnjava zašto se u inverznoj transformaciji MixColumns pojavljuju konstante 0E, 0B, 0D i 09.

RIJNDAEL šifrira blokove od 128 bitova = 16 bajtova. Svaki takav blok se može shvatiti kao 16 elemenata polja, koji se reprezentiraju pomoću 4 × 4 matrice s elementima iz GF(2⁸). Tu matricu ćemo zvati aes-blok. Ključ također ima 128 bitova (postoje i varijante sa 192 i 256 bitova). RIJNDAEL ima 10 rundi (uz 128-bitni ključ). Za ključeve duljine 192 i 256 bitova AES ima 12, odnosno 14 rundi. Svaka runda se sastoji od 4 operacije:

        SubBytes
        ShiftRows
        MixColumns
        AddRoundKey

Prije prve runde provodi se inicijalno dodavanje ključa (AddRoundKey), a u posljednjoj rundi se izostavlja transformacija MixColumns. Jedna runda AES-a ilustrirana je na slici (prema [Savard: A Cryptographic Compendium]).

1. svaki element aes-bloka (matrice) se zamijeni svojim inverzom u GF(2⁸) (s time da element 00, jedini koji nema inverz, ostaje nepromijenjen),

2. primijeni se fiksna afina transformacija

   b'_i = b_i ⊕ b_{(i+4) mod 8} ⊕ b_{(i+5) mod 8} ⊕ b_{(i+6) mod 8} ⊕ b_{(i+7) mod 8} ⊕ c_i,

   gdje je c = 01100011.

ShiftRows - ciklički pomiče elemente i-tog retka aes-bloka za i mjesta ulijevo (i = 0,1,2,3).

MixColumns - Stupci matrice se shvate kao polinomi nad GF(2⁸). Dakle, stupac A_i = (a_0i, a_1i, a_2i, a_3i) se shvati kao polinom a_3iX³ + a_2iX² + a_1iX + a_0i. Sada se ti polinomi pomnože s polinomom 03 X³ + 01 X² + 01 X + 02 (u skladu s ranije definiranim operacijama nad polinomima, rezultat se računa modulo X⁴ + 1).

AddRoundKey je XOR aes-bloka s međuključem koji odgovara trenutnoj rundi.

S-kutije (operacija SubBytes) su dizajnirane tako da bi kriptosustav bio što otporniji na diferencijalnu i linearnu kriptoanalizu, dok su ShiftRows i MixColumns zaslužni za difuziju.

U konstrukciji međuključeva se najprije ključ proširi korištenjem XOR-a i cikličkog pomaka. Prošireni ključ se sastoji od 44 riječi (4-bajtnih vektora). Međuključevi se dobivaju iz proširenog ključa tako da se prvi međuključ sastoji od prve četiri riječi, drugi od sljedeće četiri, itd.

Preostalo je još opisati malo detaljnije postupak proširivanja ključa. Prve 4 riječi proširenog ključa predstavlja zadani ključ. Svaku sljedeću riječ r_i dobijemo iz prethodne riječi r_{i -1} tako da primijenimo XOR s r_{i -4}. Ako je i višekratnik od 4, onda prije operacije XOR izvršimo operacije RotWord (rotira riječ jedno mjesto ulijevo, tj. [r₀r₁r₂r₃] promijeni u [r₁r₂r₃r₀]), SubWord (uzima jedan po jedan bajt iz riječi i na svakog od njih primijeni S-kutiju), te XOR s riječi [02^{(i -4)/4},00,00,00], gdje se potenciranje računa u GF(2⁸).

Dešifriranje se odvija po istom algoritmu kao i šifriranje, osim što se umjesto transformacija SubBytes, ShiftRows i MixColumns koriste njihovi inverzi. Primijetimo da smo u Primjeru 2.7 dokazali da polinom 03 X³ + 01 X² + 01 X + 02 ima inverz 0B X³ + 0D X² + 09 X + 0E (svi ostali dijelovi algoritma za šifriranje su očito invertibilni).

AES je i danas osnovni široko prihvaćeni standard za simetrično blokovno šifriranje. U suvremenim primjenama sigurnost ne ovisi samo o samoj blokovnoj šifri, nego i o pravilnom izboru načina djelovanja i zaštiti integriteta poruke.