RaSol: AES - sumar

Wednesday, January 04, 2006

AES - sumar

cripteaza blocuri de 128 biti utilizand chei de 128, 192 sau 256 biti, operatiile fiind realizate la nivel de octet; fiecare octet este privit ca un element al GF(2⁸) la care polinomul ireductibil este x⁸+x⁴+x³+x+1
intrarea si iesirea sunt vectori unidimensionali obtinuti prin partitionarea mesajului in octeti cu adresarea in[i] sau out[i] unde 0 ≦ i ≦ 4Nb-1 si Nb=N/32=4 (N este lungimea mesajului)
operatiile intermediare se efectueaza asupra unui vector bidimensional ce are 4 randuri si Nb coloane denumit State
corespondenta intre intrare si stare respectiv stare si iesire este de forma:
s[r, c] = in [r+4c] cu 0 ≦ r ≦ 4 si 0 ≦ c < Nb
out[r+4c] = s[r, c]
lungimea cheii este reprezentata prin Nk = 4, 6 sau 8
numarul de runde este Nr =10, 12 sau 14
lungimea cheii (Nk cuvinte) lungimea blocului (Nb cuvinte) numarul de runde (Nr)

AES-128 4 4 10

AES-192 6 4 12

AES-256 8 4 14

expandarea cheii
genereaza Nb(Nr+1) cuvinte pornind de la Nb cuvinte (de 4 octeti), fiecare din cele Nr runde necesitand Nb cuvinte; cheile rezulta sub forma unui vector unidimensional [w_i] cu 0 ≦ i ≦ Nb(Nr+1)
KeyExpansion (byte key[4*Nk], word w[Nb*(Nr+1)], Nk)

begin
	word temp
	i = 0
	while (i < Nk)
		w[i] = word(key[4i], key[4i+1], key(4i+2), key[4i+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

SubWord() este o functie care aplica Sbox cate unui cuvant o data
RotWord() este o functie care transforma un cuvant [a₀, a₁, a₂, a₃] in cuvantul [a₁, a₂, a₃, a₀]
Rcon[i] = ( a^i-1, '00', '00', '00'), a fiind un element generator al lui GF(2⁸)

algoritm criptare
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[roundNb, (round+1)Nb-1])
	end for
	SubBytes(state)
	ShiftRows(state)
	AddRoundKey(state, w[NrNb, (Nr+1)Nb-1)
	out = state
end

functia de runda este compusa din 4 transformari orientate octet:
- susbstitutie SubBytes(state)
  neliniara, fiecare octet al starii este substituit independent, ce foloseste o tabela de substitutie formata prin compunerea a doua transformari
  - orice byte nenul se inlocuieste cu inversul sau in GF(2₈)
  - rezultatul este modificat printr-o transformare afina peste Z₂
    
    y₀ 1 0 0 0 1 1 1 1 x₀ 1
    
    y₁ 1 1 0 0 0 1 1 1 x₁ 1
    
    y₂ 1 1 1 0 0 0 1 1 x₂ 0
    
    y₃ = 1 1 1 1 0 0 0 1 x₃ + 0
    
    y₄ 1 1 1 1 1 0 0 0 x₄ 0
    
    y₅ 0 1 1 1 1 1 0 0 x₅ 1
    
    y₆ 0 0 1 1 1 1 1 0 x₆ 1
    
    y₇ 0 0 0 1 1 1 1 1 x₇ 0
  rezultand o matrice inversabila de substitutie (Sbox)
  
  0 1 2 3 4 5 6 7 8 9 a b c d e f
  
  0 63 7c
  
  1 ca 82
  
  2 b7 fd
  
  3 04 c7
  
  4 09 83
  
  5 53 d1
  
  6 d0 ef
  
  7 51 a3
  
  8 cd 0c
  
  9 60 81
  
  a e0 32
  
  b e7 c8
  
  c ba 78
  
  d 70 3e
  
  e e1 f8
  
  f 8c a1
- alunecare la nivel de rand ShiftRows(state)
  primul rand se lasa neschimbat iar pentru ultimele trei randuri se face o alunecare
  s[r, c] = s[r, (c+shift(r, Nb))mod Nb] unde 0 < r < 4, 0 ≦ c < Nb
  si shift(r, Nb) este dat de
  
  Nb/r 1 2 3
  
  4 1 2 3
  
  6 1 2 3
  
  8 1 3 4
- mixare pe coloana MixColumns(state)
  opereaza asupra starii, coloana cu coloana, tratand fiecare coloana ca un polinom de grad 3 cu coeficienti in GF(2⁸) care este inmultit modulo x⁴+1 cu un polinom fix a(x)='03'x³+'01'x²+'01'x+'02'
  sub forma matriciala
  
  s_{0, c} '02' '03' '01' '01' s_{0, c}
  
  s_{1, c} = '01' '02' '03' '01' s_{1, c}
  
  s_{2, c} '01' '01' '02' '03' s_{2, c}
  
  s_{3, c} '03' '01' '01' '02' s_{3, c}
- adaugarea unei chei de runda AddRoundKey(...)
  XOR intre stare si cheia de runda; fiecare cheie de runda consta in Nb cuvinte
  [s_{0, c}, s_{1, c}, s_{2, c}, s_{3, c}] = [s_{0, c}, s_{1, c}, s_{2, c}, s_{3, c}] ⊕ [w_{runda * Nb + c}] unde 0 ≦ c < Nb, 0 ≦ runda < Nr

algoritm decriptare
InvCipher( byte in[4*Nb] , byte out[4*Nb] , word w[Nb*(Nr+1)])

begin
	byte state [4, Nb]
	state = in
	AddRoundKey (state, w[NrNb, (Nr+1)Nb-1])
	for round = Nr-1 step -1 downto 1
		InvShiftRows(state)
		InvSubBytes(state)
		AddRoundKey(state, w[roundNb, (round+1)Nb-1])
		InvMixColumns(state)
	end for
	InvShiftRows(state)
	InvSubBytes(state)
	AddRoundKey(state, w[0, Nb-1)
	out = state
end

functia de runda este compusa din 4 transformari
- InvShiftRows()
  este inversa transformarii ShiftRows() astfel ca s[r, (c+shift(r, Nb)) mod Nb] = s[r, c]
- InvSubBytes este inversa SubBytes()
- InvMixColumns() este inversa transformarii MixColumns()
  
  s_{0, c} '0e' '0b' '0d' '09' s_{0, c}
  
  s_{1, c} = '09' '0e' '0b' '0d' s_{1, c}
  
  s_{2, c} '0d' '09' '0e' '0b' s_{2, c}
  
  s_{3, c} '0b' '0d' '09' '0e' s_{3, c}
- AddRoundKey() este aceeasi (este propria inversa)
cheile de runda sunt identice cu cele folosite la criptare

algoritm decriptare echivalent
EqInvCipher( byte in[4*Nb] , byte out[4*Nb] , word w[Nb*(Nr+1)])

begin
	byte state [4, Nb]
	state = in
	AddRoundKey (state, dw[NrNb, (Nr+1)Nb-1])
	for round = Nr-1 step -1 downto 1
		InvSubBytes(state)
		InvShiftRows(state)
		InvMixColumns(state)
		AddRoundKey(state, dw[roundNb, (round+1)Nb-1])
	end for
	InvSubBytes(state)
	InvShiftRows(state)
	AddRoundKey(state, dw[0, Nb-1)
	out = state
end

functia de runda este compusa din 4 transformari
- InvShiftRows()
  este inversa transformarii ShiftRows() astfel ca s[r, (c+shift(r, Nb)) mod Nb] = s[r, c]
- InvSubBytes este inversa SubBytes()
- InvMixColumns() este inversa transformarii MixColumns()
  
  s_{0, c} '0e' '0b' '0d' '09' s_{0, c}
  
  s_{1, c} = '09' '0e' '0b' '0d' s_{1, c}
  
  s_{2, c} '0d' '09' '0e' '0b' s_{2, c}
  
  s_{3, c} '0b' '0d' '09' '0e' s_{3, c}
- AddRoundKey() este aceeasi (este propria inversa)
algoritmul pentru chei se modifica prin adaugarea urmatoarelor linii

for i = 0 step 1 to (Nr+1)*Nb-1

dw[i] = w[i]

end for

for round = 1 step 1 to Nr-1

InvMixColumns(dw[round*Nb, (round+1)*Nb-1])

end for

FIPS 197

# posted by Sorin Badescu @ 5:45 PM

Comments:

good start

# posted by

Anonymous : 9:39 AM

RaSol

Wednesday, January 04, 2006

AES - sumar

About Me

Links

archives

	lungimea cheii (Nk cuvinte)	lungimea blocului (Nb cuvinte)	numarul de runde (Nr)
AES-128	4	4	10
AES-192	6	4	12
AES-256	8	4	14

y₀		1	0	0	0	1	1	1	1	x₀		1
y₁		1	1	0	0	0	1	1	1	x₁		1
y₂		1	1	1	0	0	0	1	1	x₂		0
y₃	=	1	1	1	1	0	0	0	1	x₃	+	0
y₄		1	1	1	1	1	0	0	0	x₄		0
y₅		0	1	1	1	1	1	0	0	x₅		1
y₆		0	0	1	1	1	1	1	0	x₆		1
y₇		0	0	0	1	1	1	1	1	x₇		0

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	63	7c
1	ca	82
2	b7	fd
3	04	c7
4	09	83
5	53	d1
6	d0	ef
7	51	a3
8	cd	0c
9	60	81
a	e0	32
b	e7	c8
c	ba	78
d	70	3e
e	e1	f8
f	8c	a1

s_{0, c}		'02'	'03'	'01'	'01'	s_{0, c}
s_{1, c}	=	'01'	'02'	'03'	'01'	s_{1, c}
s_{2, c}		'01'	'01'	'02'	'03'	s_{2, c}
s_{3, c}		'03'	'01'	'01'	'02'	s_{3, c}

s_{0, c}		'0e'	'0b'	'0d'	'09'	s_{0, c}
s_{1, c}	=	'09'	'0e'	'0b'	'0d'	s_{1, c}
s_{2, c}		'0d'	'09'	'0e'	'0b'	s_{2, c}
s_{3, c}		'0b'	'0d'	'09'	'0e'	s_{3, c}

for i = 0 step 1 to (Nr+1)*Nb-1
	dw[i] = w[i]
end for
for round = 1 step 1 to Nr-1
	InvMixColumns(dw[roundNb, (round+1)Nb-1])
end for

Nb/r	1	2	3
4	1	2	3
6	1	2	3
8	1	3	4

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	63	7c
1	ca	82
2	b7	fd
3	04	c7
4	09	83
5	53	d1
6	d0	ef
7	51	a3
8	cd	0c
9	60	81
a	e0	32
b	e7	c8
c	ba	78
d	70	3e
e	e1	f8
f	8c	a1

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	63	7c
1	ca	82
2	b7	fd
3	04	c7
4	09	83
5	53	d1
6	d0	ef
7	51	a3
8	cd	0c
9	60	81
a	e0	32
b	e7	c8
c	ba	78
d	70	3e
e	e1	f8
f	8c	a1