1
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.23
Block ciphers-AES
Advanced Encryption Standard
2
Security
Software
Efficiency
Hardware
Efficiency
Flexibility
Origins of AES
3
? Additional key-sizes and block-sizes
? Ability to function efficiently and securely in a wide
variety of platforms and applications
low-end smartcards,wireless,small memory requirements
IPSec,ATM – small key setup time in hardware
B-ISDN,satellite communication – large encryption speed
Flexibility
4
15 Candidates
from USA,Canada,Belgium,
France,Germany,Norway,UK,Israel,
Korea,Japan,Australia,Costa Rica
June 1998
August 1999
October 2000
1 winner,Rijndael
Belgium
5 final candidates
Mars,RC6,Rijndael,Serpent,Twofish
Round 1
Round 2
Security
Software efficiency
Flexibility
Security
Hardware efficiency
AES Contest 1997-2001
5
AES
? In 1999,NIST issued a new standard that said
3DES should be used
– 168-bit key length
– Algorithm is the same as DES
? 3DES had drawbacks
– Algorithm is sluggish in software
– Only uses 64-bit block size
? In 1997,NIST issued a calls for proposals for the
new Advanced Encryption Standard (AES)
– security strength >= 3DES
– improved efficiency
– must be a symmetric block cipher (128-bit)
– key lengths of 128,192,and 256 bits
6
AES Evaluation
? Criteria used by NIST to evaluate potential
candidates
– Initial Criteria,
? Security
? Cost
? Algorithm characteristics
– Final Criteria,
?General Security
?Software Implementations
?Restricted-space environments
?Flexibility
?Hardware Implementations
?Attacks on Implementations
?Encryption vs,Decryption
?Key agility
7
NESSIE Project
New European Schemes for Signatures,
Integrity,and Encryption
2000-2002
CRYPTREC Project
2000-2002
Europe
Japan
8
Multiple types of transformations,
Development of methodology of a fair evaluation and
comparison of algorithms belonging to the same class,
including
software and hardware efficiency
? Symmetric-key block ciphers
? Stream ciphers
? Hash functions
? MACs
? Asymmetric encryption schemes
? Asymmetric digital signature schemes
? Asymmetric identification schemes
NESSIE,CRYPTREC
9 0
10
20
30
40
50
60
70
80
90
100
Serpent Rijndael Twofish RC6 Mars
Survey filled by 167 participants of
the Third AES Conference,April 2000 # votes
10 0
50
100
150
200
250
300
350
400
450
500
Serpent Rijndael Twofish RC6 Mars
Speed of the final AES candidates in hardware
Speed [Mbit/s] K.Gaj,P,Chodowiec,AES3,April,2000
11 0
5
10
15
20
25
30
Serpent Rijndael Twofish RC6 Mars
Efficiency in software,NIST-specified platform
128-bit key
192-bit key
256-bit key
200 MHz Pentium Pro,Borland C++
Speed [Mbits/s]
12
Security Margin
Complexity
High
Adequate
Simple Complex
NIST Report,Security
Rijndael
MARS Serpent
Twofish
RC6
13
Security,Theoretical attacks better
than exhaustive key search
0 5 10 15 20 25 30 35
Twofish
Serpent
Rijndael
RC6
Mars without 16 mixing rounds
# of rounds in the attack/total # of rounds
6 16
32 9
7 10
15 20
16 11
23
10
5
3
5
14
0 10 20 30 40 50 60 70 80 90 100
Twofish
Serpent
Rijndael
RC6
Mars
Security,Theoretical attacks better
than exhaustive key search
# of rounds in the attack/total # of rounds ? 100%
28% 72%
38% 62%
69% 31%
70% 30%
75% 25%
15
Feistel Networks Modified Feistel Network
Substitution-
Linear Transformation
Networks
Others
AES,Types of candidate algorithms
Twofish
E2
DFC
Deal
LOKI97
Magenta
RC6
MARS
CAST-256
Rijndael
Serpent
Safer+
Crypton
Frog
HPC
16
Number of rounds
Complexity of a round
Triple DES
DES
Serpent
Rijndael
Mars
RC6
Twofish
Number vs,complexity of a round
10
20
30
40
50
17
Mathematicians
Computer
scientists
Computer
Engineers
Security
Software
efficiency
Hardware
efficiency
Flexibility
18
Number theory
? a divides b if there exists c s.t,b = ac
(denoted by a|b)
? properties for all a,b,c ? Z
– a|a
– if a|b and b|c,then a|c
– if a|b and a|c,then a|(bx+cy) for all x,y ? Z
– if a|b and b|a,then a = ?b
19
Division in Z
? let a,b ? Z with b ≠ 0,then there exist q and
r s.t,a = qb+r,where 0 ? r < |b|
? q is the quotient q = a div b and r is the
remainder r = a mod b
? c is a common divisor of a and b if c|a and
c|b
20
gcd and lcm
? gcd(a,b) is the largest positive integer that
divides both a and b
? lcm(a,b) is the smallest positive integer
divisible by both a and b
? lcm(a,b)=a*b/gcd(a,b)
? a and b are said to be relatively prime or
coprime if gcd(a,b)=1
? p ≥ 2 is prime if its only positive divisors
are 1 and p
21
Properties of prime
? if p|ab than either p|a or p|b (or both)
? there an infinite number of prime numbers
? Prime number theorem,
– let ?(x) denote the number of prime numbers ?
x,then
1
ln
)(
lim ?
??
x
x
x
x
?
22
Euler phi function
? For n ≥ 1,let ?(n) denote the number of
integers in the interval [1,n] which are
relatively prime to n,The function phi is
called Euler phi function
– if p is a prime then ?(p)=p-1
– ? is multiplicative,That is if gcd(m,n)=1 then
?(m*n)= ?(n)* ?(m)
23
Euclidean algorithm for the gcd
? given a and b with a ≥ b
– gcd(a,b) = gcd(b,a mod b)
? Algorithm
– Input,2 non-negative integers a & b with a ≥ b
– Output,gcd(a,b)
– while b ≠ 0
? Set r?a mod b,a ? b,b ? r
– return (a)
? Extended Euclidean Algorithm
– Output,d = gcd(a,b) and integers x,y satisfying ax+by
= d
24
Integers modulo n
? the integers modulo n denoted by Zn is the
set of (equivalence classes of) integers
0,1,2...n-1,Addition,subtraction and
multiplication are performed modulo n
? let a ? Zn,the multiplicative inverse of a is
an integer x ? Zn,s.t,ax ? 1 (mod n),a is
invertible iff gcd(a,n) = 1
? ax+bn=1(Extended Euclidean Algorithm)
25
Chinese remainder theorem (CRT)
? If n1,n2,...nk are pair-wise coprime,then the
system of equations,
– x ? a1 (mod n1 )
– x ? a2 (mod n2 )
–,..,
– x ? ak (mod nk )
has a unique solution modulo n= n1*n2*...nk
26
? the multiplicative group of Zn is
Zn*={ a ? Zn | gcd(a,n)=1},If n is a
prime then
Zn*={ a ? Zn | 1 ? a ? n-1}
? the order of Zn* is defined to be the
number of element in Zn* namely |Zn*|
27
Euler’s theorem
? Let n ≥ 2 be an integer,
– (Euler’s theorem) If a ? Zn*,then a ?(n) =1
(mod n)
? Fermat’s (little) theorem
– Let p be a prime
– if gcd(a,p)=1 then a p-1 ?1 (mod p)
28
Order of an element
? Let a ? Zn*,The order of a (ord(a)) is the
least positive t s.t,
a t ≡ 1 (mod n)
? t must divide ?(n)
? if t= ?(n) then a is said to be a generator of
Zn*,If Zn* has a generator then it is said to
be cyclic
29
Properties of generator
? Zn* has a generator iff n=2,4,pk or 2pk where
p is an odd prime
? if a is a generator then Zn*= {ai mod n | 0 ? i ?
phi(n)}
? if a is a generator,b = ai mod n is also a
generator iff gcd(i,phi(n))=1,If Zn* is cyclic it
has phi(phi(n)) generators
? a is a generator iff a phi(n)/p ≠ 1 mod n for each
prime divisor p of phi(n)
30
Quadratic residue
? Let a ? Zn*,a is said to be a quadratic residue(qr)
if there exists a x ? Zn*,s.t,x2 ≡ a mod n (Qn)
? if n=p and let b be the generator,then a is a qr iff
a=bi with i even,It follows that there are (p-1)/2
qr in Zp*,
? if n=pq,Then a is a qr iff a ? Qp and a ? Qq,
| Qn | = | Qp|.| Qq | = (p – 1) (q – 1) / 4
Number of square roots,
if p is a odd prime and a ? Qp then a has exactly
two square roots
if n= p*q and a ? Qn then a has 4 distinct square
roots,
31
Legendre symbol
? let p be an odd prime and a an integer,The
Legendre symbol is defined to be
?
?
?
?
?
??
????
?
?
??
?
?
p
p
Qa
Qa
ap
p
a
if,1
if,1
| if,0
32
Jacobi symbol
? let n ≥ 3 be odd with prime factorization
? then the Jacobi symbol is defined to be
ke
k
ee
p
a
p
a
p
a
n
a
???
?
???
?
???
?
???
?
???
?
???
?
??
?
??
?
?,..
21
21
kekee pppn,..21 21?
33
Blum Integers
? If p and q are two primes,and both are
congruent to 3 modulo 4,then n = pq is
sometimes called a Blum integer,
34
Abstract algebra
? Groups
? Rings
? Fields
35
Groups
? Definition:A set G and operator *,(G,*) is a
group if,
? Closure,for all x,y in G,x * ? G
? Associativity,for all x,y,z in G,(x * y) * z =
x * (y * z)
? Identity,$ I ? G such that for all x ? G,I * x
= x
? Inverse,for all x ? G,$ inverse element x-1 ?
G such that x-1 * x = I
? Definition,A group (G,* ) is Abelian if,
? Commutativity,for all x,y ? G,x * y=y * x
36
Groups
? Definition,An element g ? G is a group generator of
group (G,* ) if for all x ? G,$ i such that
x=gi = g * g * g * … * g (i times)
In other words,G = <g>
? Definition,A group (G,* ) is cyclic if a group generator
exists!
? Definition,Group order of a group (G,* ) is the size of
set G,i.e.,|G| or #{G} or ord(G)
? Definition,Group (G,* ) is finite if ord(G) is fixed,
? Example,the set Zn with addition modulo n is a group,
Zn with multiplication modulo n is not a group,Zn* is a
group of order phi(n)
37
Rings & Fields
? Definition,A structure (R,+,*) is a ring if (R,+) is an
abelian group and,
* Closure,for all x,y ? R,x * y ? R
* Associativity,for all x,y,z ? R,(x*y)*z = x*(y*z)
* Identity,$ I ? R such that for all x ? R,I*x = x
* Commutativity,for all x,y ? R,x*y=y*x
* Distribution,for all x,y,z ? R,(x+y)*z =
x*z+y*z
? Definition,A structure (F,+,*) is a field if (F,+,*) is a
ring and,
* Inverse,for all x ? R,$ inverse element x-1 ? R
such that x-1*x = I
38
Polynomial rings
? if R is an commutative ring then a polynomial
over R is an expression f(x)=anxn+...+ a2x2 +
a1x+ a0 where each ai is in R and n ≥ 0,If the
leading coefficient is equal to 1 then f is said
to be monic
? f is said to be irreducible over F if it cannot
be written as the product of two polynomials
each of positive degree
39
Analogy
? if we introduce the division algorithm for
polynomial (g=h*q+r where r is a
polynomial over F[x] and deg r < deg h)
? and we choose a pol,f(x) over F then
F[x]/f(x) is a commutative ring (like Zn)
– if f(x) is irreducible then F[x]/f(x) is a field
(like Zp)
40
Usefulness of polynomials
? give us a representation which permits
efficient calculation in GF(pm )
? it is possible to generalize the Discrete
Logarithm problem
? you need an irreducible pol,f(x) (eq,of p)
over Zp of degree m
then Zp[x]/f(x) is a finite field of order pm
41
Preliminaries
? The field GF(28)
Example,(57)16?x6+x4+x2+x+1
– Addition
– Multiplication
– Multiplication by x
? Polynomials with coefficients in GF(28)
– Multiplication by x
42
Addition
? The sum of two elements is the polynomial with
coefficients that are given by the sum modulo 2
(i.e.,1+1=0) of the coefficients of the two terms,
? Example,’57’+’83’=‘D4’
– (x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2
43
Multiplication
? Multiplication in GF(28) corresponds with
multiplication of polynomials modulo an
irreducible binary polynomial of degree 8,For
Rijndael,this polynomial is called m(x) and given
by,m(x)=x8+x4+x3+x+1 or (11B)16,
? Example,’57’?’83’=‘C1’
– (x6+x4+x2+x+1) ?(x7+x+1) =
x13+x11+x9+x8+x6+x5+x4+x3+1
– x13+x11+x9+x8+x6+x5+x4+x3+1 modulo
x8+x4+x3+x+1 = x7+x6+1
44
The extended algorithm of Euclid
? The multiplication defined above is
associative and there is a neutral element
(‘01’),For any binary polynomial b( x ) of
degree below 8,the extended algorithm of
Euclid can be used to compute polynomials
a( x ),c( x ) such that
b( x ) a( x ) + m( x ) c( x ) = 1,
? Hence,a(x)?b(x) mod m(x)= 1 or
b-1(x)=a(x) mod m(x),
45
The extended algorithm of Euclid
? Moreover,it holds that
a(x)?(b(x)+c(x))=a(x)?b(x)+a(x)?c(x),
? It follows that the set of 256 possible byte values,
with the EXOR as addition and the multiplication
defined as above has the structure of the finite
field GF(28),
46
Multiplication by x
? If we multiply b(x) by the polynomial x,we have,
b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x
? x?b(x) is obtained by reducing the above result
modulo m(x),If b7=0,the reduction is identity
operation; if b7=1,m(x) must be subtracted (i.e,
EXORed),
? That is,multiplication by x (‘02’) can be
implemented by a left shift and a conditional
EXOR with’1B’,
47
Algorithm of multiplication by x or xtime(a(x))
? Input,a(x),m(x)
? Output,b(x) = (a(x) * x) mod m(x)
? Procedure,
b(x)=a7x8+ a6x7+ a5x6+ a4x5+ a3x4+ a2x3+ a1x2+ a0x
( by left shift one bit of a(x) )
if (a7 ==0) then
return b(x)
else
return b(x)-m(x)
( or XOR (a6 a5 a4 a3 a2 a1 a0) with ‘1B’ )
Multiplication by x
48
Example
? ‘ 57’ ? ‘ 13’ =‘ FE’
‘57’ ?’02’=xtime(57)=‘AE’
‘57’ ?’04’=xtime(AE)=‘47’
‘57’ ?’08’=xtime(47)=‘8E’
‘57’ ?’10’=xtime(8E)=‘07’
‘57’ ? ‘13’ =‘57’?(‘01’?’02’?’10’) =
‘57’?’AE’?’07’=‘FE’
49
Polynomials with coefficients in
GF(28)
? Assume we have two polynomials over
GF(28),
a(x)=a3x3+a2x2+a1x+a0
b(x)=b3x3+b2x2+b1x+b0
50
Polynomials with coefficients in
GF(28)
? Their product
c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0
c0=a0 ? b0
c1=a1 ? b0 ? a0 ? b1
c2=a2 ? b0 ? a1 ? b1 ? a0 ? b2
c3=a3 ? b0 ? a2 ? b1 ? a1 ? b2+ ? a0 ? b3
c4=a3 ? b1 ? a2 ? b2 ? a1 ? b3
c5=a3 ? b2 ? a2 ? b3
c6=a3 ? b3
51
Polynomials with coefficients in
GF(28)
? By reducing c(x) modulo a polynomial of degree 4,
the result can be reduced to a polynomial of
degree below 4,In Rijndael,the polynomial
M(x)=x4+1,
As xi mod x4+1=xi mod 4,
52
Polynomials with coefficients in
GF(28)
? The modular product of a( x ) and b( x ),denoted
by d( x ) = a( x ) ??b( x ) is given by d( x ) =
d3x3+d2x2+d1x+d0 with
d0 = a0??b0 ??a3??b1 ??a2??b2 ??a1??b3
d1 = a1??b0 ??a0??b1 ??a3??b2 ??a2??b3
d2 = a2??b0 ??a1??b1 ??a0??b2 ??a3??b3
d3 = a3??b0 ??a2??b1 ??a1??b2 ??a0??b3
53
Polynomials with coefficients in
GF(28)
The operation consisting of multiplication by a
fixed polynomial a( x ) can be written as matrix
multiplication where the matrix is a circulant
matrix,We have,
54
Multiplication by x
? If we multiply b( x ) by the polynomial x,we have,
b3x4+b2x3+b1x2+b0x
? x ??b( x ) is obtained by reducing the above result
modulo 1+x4,This gives b2x3+b1x2+b0x+b3
? The multiplication by x is equivalent to
multiplication by a matrix as above with all ai
=‘00’ except a1 =‘01’,Let c( x ) = x?b( x ),We
have,
55
Multiplication by x
56
The AES Cipher
? Noteworthy features,
– NOT a Feistel structure
? processes entire block in parallel during each round
using substitutions and permutations
– The key that is provided as input is expanded
? Array of forty-four 32-bit words (w[i])
? Four distinct words serve as round key (128 bits)
57
The AES Cipher
– Four different stages (1 permutation,3
substitution)
? Substitute bytes- Uses S-box to perform byte by byte
substitution of the block
? Shift rows- A simple permutation
? Mix columns- Substitution over GF(28)
? Add round key- bitwise XOR of current block and
portion of expanded key
– For both encryption and decryption,
? Start with add round key followed by nine rounds of
four stages,plus tenth round of three stages
58
The AES Cipher
– Only Add round key makes use of the key
? All other stages reversible without knowledge of
key
– Add round key alone is not formidable
? The other three stages add diffusion,confusion,and
nonlinearity
– Each stage is reversible
? SB,SR and MC use inverse function
? ARK uses XOR
– Decryption uses expanded keys in reverse order
59
AES Encryption Round
60
? Rounds, depend on block size and key length
Block size
Key size
128 bits
(Nb=4)
192 bits
(Nb=6)
256 bits
(Nb=8)
128 bits (Nk=4) 10 12 14
192 bits (Nk=6) 12 12 14
256 bits (Nk=8) 14 14 14
The AES Cipher
61
? State, A 4× Nb matrix,
Ex,An initial state with 192 bits(Nb=6),
0 4 8 123 128 123
1 5 9 124 164 15
2 6 10 233 24 255
3 7 11 54 67 34
Nb
The AES Cipher
4
62
The AES Cipher
in2
in1
in6
in9
in7
in13
in15 in3
in5
in0 in8
in10
in11
in14
in12 s0,0
s1,0
s0,2
s2,0
s1,1 s1,2
s0,3
s1,3
s0,1
s2,1 s2,2 s2,3
s3,0 s3,2 s3,3
s0,0
s1,0 s1,1
s3,3
s0,2 s0,3 s0,1
s3,1
s2,0
s3,0
s2,1
s1,2 s1,3
s2,2 s2,3
s3,2
in4 out0
out10
out8 out12
out1 out5 out9 out13
out2 out6
out4
out14
out3 out7 out11 out15 s3,1
63
? Cipher Key, A 4× Nk matrix,
Ex,cipher key with 128 bits(Nk=4),
K0,0 K0,1 K0,2 K0,3
K1,0 K1,1 K1,2 K1,3
K2,0 K2,1 K2,2 K2,3
K3,0 K3,1 K3,2 K3,3
Nk
The AES Cipher
4
64
Structure of Rijndael
B, ByteSub(State)
S, ShiftRow(State)
M, MixColumn(State)
A, AddRoundKey(State,
RoundKey)
plaintext (initial state)
AddRoundKey( )
ciphertext
KeyExpansion Key
RoundKey 0
B S M A round1 RoundKey 1
B S M A round(Nr-1) RoundKey Nr-1
B S A RoundKey Nr roundNr
65
Encryption Flow
Rijnadel(State,CipherKey) {
KeyExpansion( CipherKey,ExpandedKey );
AddRoundKey( State,ExpandedKey );
for(i =1; i < Nr; i++) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey (State,ExpandedKey );
}
ByteSub(State);
ShiftRow(State);
AddRoundKey (State,ExpandedKey );
}
intermediate
round
final
round
initialization
66
AddRoundKey
? AddRoundKey(State,RoundKey)
K0,0 K0,1 K0,2 K0,3
K1,0 K1,1 K1,2 K1,3
K2,0 K2,1 K2,2 K2,3
K3,0 K3,1 K3,2 K3,3
A0,0 A0,1 A0,2 A0,3
A1,0 A1,1 A1,2 A1,3
A2,0 A2,1 A2,2 A2,3
A3,0 A3,1 A3,2 A3,3
b0,0 b0,1 b0,2 b0,3
b1,0 b1,1 b1,2 b1,3
b2,0 b2,1 b2,2 b2,3
b3,0 b3,1 b3,2 b3,3
? =
State (Nb=4) RoundKey
67
ByteSub
? ByteSub(State) 0 4 8 123 128 123
1 5 9 124 164 15
2 6 10 233 24 255
3 7 11 54 67 34
99 242 48,.,.,,
124 107 1,.,.,,
119 111 103,.,.,,
123 197 43,.,.,,
X
Y
,2
)G F ( 2u n d er ][ F in d 1,81
,
?
ji
X
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
1
0
0
0
1
1
11111000
01111100
00111110
00011111
10001111
11000111
11100011
11110001
7
6
5
4
3
2
1
0
7
6
5
4
3
2
1
0
x
x
x
x
x
x
x
x
y
y
y
y
y
y
y
y
68
ByteSub
ai,0*ai,0-1=1mod m(x),m(x)=x8+x4+x3+x+1 (11B)16
b
i,0=Cai,0-1
For Example
ai,0 ai,0-1 bi,0
00000000 00000000 01100011
00000001 00000001 01111100
00000010 10001101 01110111
69
The S-box used in the SubBytes() transformation is presented
in hexadecimal form in Fig,
Figure,S-box,substitution values for the byte xy (in
hexadecimal format),
70
ShiftRow
? ShiftRow(State)
Nb 4 6 8
Row2 1 1 1
Row3 2 2 3
Row4 3 3 4
99 242 48,.,.,,
124 107 1,.,.,,
119 111 103,.,.,,
123 197 43,.,.,,
99 242 48,.,.,,
107 1,.,.,,124
103,.,.,,119 111
..,.,,123 197 43
71
ShiftRow
For Example Nb=4,after shift row A[16]transform to B[16]
m n o p
j k l m
d e f g
w x y z
m n o p
k l m j
f g d e
z w x y
B[16]= A[16]=
72
MixColumn
? MixColumn(State)
b(x)=c(x) a(x) mod
c(x)=
a(x)=
b(x)=
?
''x''x''x'' 02010103 23 ???
14 ?x
012233 axaxaxa ???
012233 bxbxbxb ???
32103
32102
32101
32100
02010103
03020101
01030201
01010302
a''a''a''a''b
a''a''a''a''b
a''a''a''a''b
a''a''a''a''b
????????
????????
????????
????????
b(x) c(x) a(x)
73
MixColumn
? MixColumn(State)
? Inverse of MixColumn, d(x)
c(x) d(x)=‘01’
=> d(x)=
?
'E'x''x'D'x'B' 00900 23 ???
74
Key Schedule
? For Example Nb=4,Nk=4,total expandedkey
We need are 4*(10+1)=44 words
Key[0] Key[4] Key[8] Key[12]
Key[1] Key[5] Key[9] Key[13]
Key[2] Key[6] Key[10] Key[14]
Key[3] Key[7] Key[11] Key[15]
W’0 W’1 W’2 W’3
Cipher Key
W’0
W’1
W’2
W’3
Word0 Word43
Expanded Key
Round key 0 Round key 1 Round key 10
Word4 Word40
75
Key Schedule
? Key Expansion
– Length, block size × (Nr+1) bits
Ex,block size=128 bits,key length=128 bits
128 bits × (10+1)=1408 bits,
– Using a linear array of 4-byte words to save the
expanded key and is denoted by W[Nb*(Nr+1)],
76
Key Schedule
? Key Expansion for Nk≦ 6 (i.e,
128,192 bits)
Key length,128 bits (Nk=4)
Block size,192 bits (Nb=6)
Round Key 0 Round Key 1
?
RotByte()
SubByte()
Rcon[i/Nk]
Nk i=4
?
Nk i=9
32bits
If (i%Nk=0)
If (i%Nk≠0)
77
Key Schedule
? Key Expansion(cont.)
– RotByte(W[i])
(a,b,c,d) -> (b,c,d,a)
– Rcon[i] =(RC[i],’00’,’00’,’00’)
RC[i]=xi-1 representing an element in GF(28)
RC[1]=1 (i.e,’01’)
RC[2]=x (i.e,’02’)
RC[3]=x2 (i.e,’04’)
78
Key Schedule
KeyExpansion(For Nk ??6)
for( i=0; i< Nk; i++ )
W[i]= ( Key[4*i],key[4*i+1],key[4*i+2],key[4*i+3] );
for( i= Nk; i<Nb * (Nr + 1); i++ )
{ temp = W[i - 1];
if (i % Nk == 0)
temp = SubByte(RotByte(temp)) ^
Rcon[i / Nk];
W[i] = W[i - Nk] ^ temp; } }
round0
The rest
round
79
Key Schedule
KeyExpansion(For Nk > 6)
for( i=0; i< Nk; i++ )
W[i]= ( Key[4*i],key[4*i+1],key[4*i+2],key[4*i+3] );
for( i= Nk; i<Nb * (Nr + 1); i++ )
{ temp = W[i - 1];
if (i % Nk == 0)
temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];
else if (i % Nk == 4)
temp = SubByte(temp);
W[i] = W[i - Nk] ^ temp; }
}
round0
The rest
round
80
Inverse Cipher
InvCipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
AddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1])
for round = Nr-1 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state,w[round*Nb,(round+1)*Nb-1])
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state,w[0,Nb-1])
out = state
end
81
Add Round Key
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Mix Columns
Shift Rows
Add Round Key
Inverse sub bytes
Inverse shift rows
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Substitute Bytes
Add round key
Shift Rows
Substitute Bytes
Add round key
Substitute Bytes
Shift Rows
Mix Columns
Expand Key
.,
,
.,
,
w[0,3]
w[4,7]
w[36,39]
w[40,43]
Plaintext Plaintext
Ciphertext Ciphertext
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
82
References
? NIST fips-197 ADVANCED
ENCRYPTION STANDARD (AES)
http://csrc.nist.gov/publications/fips/fips197
/fips-197.pdf 2001.11
? Joan Daemen,Vincent Rijmen,AES
Proposal,Rijndael
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.23
Block ciphers-AES
Advanced Encryption Standard
2
Security
Software
Efficiency
Hardware
Efficiency
Flexibility
Origins of AES
3
? Additional key-sizes and block-sizes
? Ability to function efficiently and securely in a wide
variety of platforms and applications
low-end smartcards,wireless,small memory requirements
IPSec,ATM – small key setup time in hardware
B-ISDN,satellite communication – large encryption speed
Flexibility
4
15 Candidates
from USA,Canada,Belgium,
France,Germany,Norway,UK,Israel,
Korea,Japan,Australia,Costa Rica
June 1998
August 1999
October 2000
1 winner,Rijndael
Belgium
5 final candidates
Mars,RC6,Rijndael,Serpent,Twofish
Round 1
Round 2
Security
Software efficiency
Flexibility
Security
Hardware efficiency
AES Contest 1997-2001
5
AES
? In 1999,NIST issued a new standard that said
3DES should be used
– 168-bit key length
– Algorithm is the same as DES
? 3DES had drawbacks
– Algorithm is sluggish in software
– Only uses 64-bit block size
? In 1997,NIST issued a calls for proposals for the
new Advanced Encryption Standard (AES)
– security strength >= 3DES
– improved efficiency
– must be a symmetric block cipher (128-bit)
– key lengths of 128,192,and 256 bits
6
AES Evaluation
? Criteria used by NIST to evaluate potential
candidates
– Initial Criteria,
? Security
? Cost
? Algorithm characteristics
– Final Criteria,
?General Security
?Software Implementations
?Restricted-space environments
?Flexibility
?Hardware Implementations
?Attacks on Implementations
?Encryption vs,Decryption
?Key agility
7
NESSIE Project
New European Schemes for Signatures,
Integrity,and Encryption
2000-2002
CRYPTREC Project
2000-2002
Europe
Japan
8
Multiple types of transformations,
Development of methodology of a fair evaluation and
comparison of algorithms belonging to the same class,
including
software and hardware efficiency
? Symmetric-key block ciphers
? Stream ciphers
? Hash functions
? MACs
? Asymmetric encryption schemes
? Asymmetric digital signature schemes
? Asymmetric identification schemes
NESSIE,CRYPTREC
9 0
10
20
30
40
50
60
70
80
90
100
Serpent Rijndael Twofish RC6 Mars
Survey filled by 167 participants of
the Third AES Conference,April 2000 # votes
10 0
50
100
150
200
250
300
350
400
450
500
Serpent Rijndael Twofish RC6 Mars
Speed of the final AES candidates in hardware
Speed [Mbit/s] K.Gaj,P,Chodowiec,AES3,April,2000
11 0
5
10
15
20
25
30
Serpent Rijndael Twofish RC6 Mars
Efficiency in software,NIST-specified platform
128-bit key
192-bit key
256-bit key
200 MHz Pentium Pro,Borland C++
Speed [Mbits/s]
12
Security Margin
Complexity
High
Adequate
Simple Complex
NIST Report,Security
Rijndael
MARS Serpent
Twofish
RC6
13
Security,Theoretical attacks better
than exhaustive key search
0 5 10 15 20 25 30 35
Twofish
Serpent
Rijndael
RC6
Mars without 16 mixing rounds
# of rounds in the attack/total # of rounds
6 16
32 9
7 10
15 20
16 11
23
10
5
3
5
14
0 10 20 30 40 50 60 70 80 90 100
Twofish
Serpent
Rijndael
RC6
Mars
Security,Theoretical attacks better
than exhaustive key search
# of rounds in the attack/total # of rounds ? 100%
28% 72%
38% 62%
69% 31%
70% 30%
75% 25%
15
Feistel Networks Modified Feistel Network
Substitution-
Linear Transformation
Networks
Others
AES,Types of candidate algorithms
Twofish
E2
DFC
Deal
LOKI97
Magenta
RC6
MARS
CAST-256
Rijndael
Serpent
Safer+
Crypton
Frog
HPC
16
Number of rounds
Complexity of a round
Triple DES
DES
Serpent
Rijndael
Mars
RC6
Twofish
Number vs,complexity of a round
10
20
30
40
50
17
Mathematicians
Computer
scientists
Computer
Engineers
Security
Software
efficiency
Hardware
efficiency
Flexibility
18
Number theory
? a divides b if there exists c s.t,b = ac
(denoted by a|b)
? properties for all a,b,c ? Z
– a|a
– if a|b and b|c,then a|c
– if a|b and a|c,then a|(bx+cy) for all x,y ? Z
– if a|b and b|a,then a = ?b
19
Division in Z
? let a,b ? Z with b ≠ 0,then there exist q and
r s.t,a = qb+r,where 0 ? r < |b|
? q is the quotient q = a div b and r is the
remainder r = a mod b
? c is a common divisor of a and b if c|a and
c|b
20
gcd and lcm
? gcd(a,b) is the largest positive integer that
divides both a and b
? lcm(a,b) is the smallest positive integer
divisible by both a and b
? lcm(a,b)=a*b/gcd(a,b)
? a and b are said to be relatively prime or
coprime if gcd(a,b)=1
? p ≥ 2 is prime if its only positive divisors
are 1 and p
21
Properties of prime
? if p|ab than either p|a or p|b (or both)
? there an infinite number of prime numbers
? Prime number theorem,
– let ?(x) denote the number of prime numbers ?
x,then
1
ln
)(
lim ?
??
x
x
x
x
?
22
Euler phi function
? For n ≥ 1,let ?(n) denote the number of
integers in the interval [1,n] which are
relatively prime to n,The function phi is
called Euler phi function
– if p is a prime then ?(p)=p-1
– ? is multiplicative,That is if gcd(m,n)=1 then
?(m*n)= ?(n)* ?(m)
23
Euclidean algorithm for the gcd
? given a and b with a ≥ b
– gcd(a,b) = gcd(b,a mod b)
? Algorithm
– Input,2 non-negative integers a & b with a ≥ b
– Output,gcd(a,b)
– while b ≠ 0
? Set r?a mod b,a ? b,b ? r
– return (a)
? Extended Euclidean Algorithm
– Output,d = gcd(a,b) and integers x,y satisfying ax+by
= d
24
Integers modulo n
? the integers modulo n denoted by Zn is the
set of (equivalence classes of) integers
0,1,2...n-1,Addition,subtraction and
multiplication are performed modulo n
? let a ? Zn,the multiplicative inverse of a is
an integer x ? Zn,s.t,ax ? 1 (mod n),a is
invertible iff gcd(a,n) = 1
? ax+bn=1(Extended Euclidean Algorithm)
25
Chinese remainder theorem (CRT)
? If n1,n2,...nk are pair-wise coprime,then the
system of equations,
– x ? a1 (mod n1 )
– x ? a2 (mod n2 )
–,..,
– x ? ak (mod nk )
has a unique solution modulo n= n1*n2*...nk
26
? the multiplicative group of Zn is
Zn*={ a ? Zn | gcd(a,n)=1},If n is a
prime then
Zn*={ a ? Zn | 1 ? a ? n-1}
? the order of Zn* is defined to be the
number of element in Zn* namely |Zn*|
27
Euler’s theorem
? Let n ≥ 2 be an integer,
– (Euler’s theorem) If a ? Zn*,then a ?(n) =1
(mod n)
? Fermat’s (little) theorem
– Let p be a prime
– if gcd(a,p)=1 then a p-1 ?1 (mod p)
28
Order of an element
? Let a ? Zn*,The order of a (ord(a)) is the
least positive t s.t,
a t ≡ 1 (mod n)
? t must divide ?(n)
? if t= ?(n) then a is said to be a generator of
Zn*,If Zn* has a generator then it is said to
be cyclic
29
Properties of generator
? Zn* has a generator iff n=2,4,pk or 2pk where
p is an odd prime
? if a is a generator then Zn*= {ai mod n | 0 ? i ?
phi(n)}
? if a is a generator,b = ai mod n is also a
generator iff gcd(i,phi(n))=1,If Zn* is cyclic it
has phi(phi(n)) generators
? a is a generator iff a phi(n)/p ≠ 1 mod n for each
prime divisor p of phi(n)
30
Quadratic residue
? Let a ? Zn*,a is said to be a quadratic residue(qr)
if there exists a x ? Zn*,s.t,x2 ≡ a mod n (Qn)
? if n=p and let b be the generator,then a is a qr iff
a=bi with i even,It follows that there are (p-1)/2
qr in Zp*,
? if n=pq,Then a is a qr iff a ? Qp and a ? Qq,
| Qn | = | Qp|.| Qq | = (p – 1) (q – 1) / 4
Number of square roots,
if p is a odd prime and a ? Qp then a has exactly
two square roots
if n= p*q and a ? Qn then a has 4 distinct square
roots,
31
Legendre symbol
? let p be an odd prime and a an integer,The
Legendre symbol is defined to be
?
?
?
?
?
??
????
?
?
??
?
?
p
p
Qa
Qa
ap
p
a
if,1
if,1
| if,0
32
Jacobi symbol
? let n ≥ 3 be odd with prime factorization
? then the Jacobi symbol is defined to be
ke
k
ee
p
a
p
a
p
a
n
a
???
?
???
?
???
?
???
?
???
?
???
?
??
?
??
?
?,..
21
21
kekee pppn,..21 21?
33
Blum Integers
? If p and q are two primes,and both are
congruent to 3 modulo 4,then n = pq is
sometimes called a Blum integer,
34
Abstract algebra
? Groups
? Rings
? Fields
35
Groups
? Definition:A set G and operator *,(G,*) is a
group if,
? Closure,for all x,y in G,x * ? G
? Associativity,for all x,y,z in G,(x * y) * z =
x * (y * z)
? Identity,$ I ? G such that for all x ? G,I * x
= x
? Inverse,for all x ? G,$ inverse element x-1 ?
G such that x-1 * x = I
? Definition,A group (G,* ) is Abelian if,
? Commutativity,for all x,y ? G,x * y=y * x
36
Groups
? Definition,An element g ? G is a group generator of
group (G,* ) if for all x ? G,$ i such that
x=gi = g * g * g * … * g (i times)
In other words,G = <g>
? Definition,A group (G,* ) is cyclic if a group generator
exists!
? Definition,Group order of a group (G,* ) is the size of
set G,i.e.,|G| or #{G} or ord(G)
? Definition,Group (G,* ) is finite if ord(G) is fixed,
? Example,the set Zn with addition modulo n is a group,
Zn with multiplication modulo n is not a group,Zn* is a
group of order phi(n)
37
Rings & Fields
? Definition,A structure (R,+,*) is a ring if (R,+) is an
abelian group and,
* Closure,for all x,y ? R,x * y ? R
* Associativity,for all x,y,z ? R,(x*y)*z = x*(y*z)
* Identity,$ I ? R such that for all x ? R,I*x = x
* Commutativity,for all x,y ? R,x*y=y*x
* Distribution,for all x,y,z ? R,(x+y)*z =
x*z+y*z
? Definition,A structure (F,+,*) is a field if (F,+,*) is a
ring and,
* Inverse,for all x ? R,$ inverse element x-1 ? R
such that x-1*x = I
38
Polynomial rings
? if R is an commutative ring then a polynomial
over R is an expression f(x)=anxn+...+ a2x2 +
a1x+ a0 where each ai is in R and n ≥ 0,If the
leading coefficient is equal to 1 then f is said
to be monic
? f is said to be irreducible over F if it cannot
be written as the product of two polynomials
each of positive degree
39
Analogy
? if we introduce the division algorithm for
polynomial (g=h*q+r where r is a
polynomial over F[x] and deg r < deg h)
? and we choose a pol,f(x) over F then
F[x]/f(x) is a commutative ring (like Zn)
– if f(x) is irreducible then F[x]/f(x) is a field
(like Zp)
40
Usefulness of polynomials
? give us a representation which permits
efficient calculation in GF(pm )
? it is possible to generalize the Discrete
Logarithm problem
? you need an irreducible pol,f(x) (eq,of p)
over Zp of degree m
then Zp[x]/f(x) is a finite field of order pm
41
Preliminaries
? The field GF(28)
Example,(57)16?x6+x4+x2+x+1
– Addition
– Multiplication
– Multiplication by x
? Polynomials with coefficients in GF(28)
– Multiplication by x
42
Addition
? The sum of two elements is the polynomial with
coefficients that are given by the sum modulo 2
(i.e.,1+1=0) of the coefficients of the two terms,
? Example,’57’+’83’=‘D4’
– (x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2
43
Multiplication
? Multiplication in GF(28) corresponds with
multiplication of polynomials modulo an
irreducible binary polynomial of degree 8,For
Rijndael,this polynomial is called m(x) and given
by,m(x)=x8+x4+x3+x+1 or (11B)16,
? Example,’57’?’83’=‘C1’
– (x6+x4+x2+x+1) ?(x7+x+1) =
x13+x11+x9+x8+x6+x5+x4+x3+1
– x13+x11+x9+x8+x6+x5+x4+x3+1 modulo
x8+x4+x3+x+1 = x7+x6+1
44
The extended algorithm of Euclid
? The multiplication defined above is
associative and there is a neutral element
(‘01’),For any binary polynomial b( x ) of
degree below 8,the extended algorithm of
Euclid can be used to compute polynomials
a( x ),c( x ) such that
b( x ) a( x ) + m( x ) c( x ) = 1,
? Hence,a(x)?b(x) mod m(x)= 1 or
b-1(x)=a(x) mod m(x),
45
The extended algorithm of Euclid
? Moreover,it holds that
a(x)?(b(x)+c(x))=a(x)?b(x)+a(x)?c(x),
? It follows that the set of 256 possible byte values,
with the EXOR as addition and the multiplication
defined as above has the structure of the finite
field GF(28),
46
Multiplication by x
? If we multiply b(x) by the polynomial x,we have,
b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x
? x?b(x) is obtained by reducing the above result
modulo m(x),If b7=0,the reduction is identity
operation; if b7=1,m(x) must be subtracted (i.e,
EXORed),
? That is,multiplication by x (‘02’) can be
implemented by a left shift and a conditional
EXOR with’1B’,
47
Algorithm of multiplication by x or xtime(a(x))
? Input,a(x),m(x)
? Output,b(x) = (a(x) * x) mod m(x)
? Procedure,
b(x)=a7x8+ a6x7+ a5x6+ a4x5+ a3x4+ a2x3+ a1x2+ a0x
( by left shift one bit of a(x) )
if (a7 ==0) then
return b(x)
else
return b(x)-m(x)
( or XOR (a6 a5 a4 a3 a2 a1 a0) with ‘1B’ )
Multiplication by x
48
Example
? ‘ 57’ ? ‘ 13’ =‘ FE’
‘57’ ?’02’=xtime(57)=‘AE’
‘57’ ?’04’=xtime(AE)=‘47’
‘57’ ?’08’=xtime(47)=‘8E’
‘57’ ?’10’=xtime(8E)=‘07’
‘57’ ? ‘13’ =‘57’?(‘01’?’02’?’10’) =
‘57’?’AE’?’07’=‘FE’
49
Polynomials with coefficients in
GF(28)
? Assume we have two polynomials over
GF(28),
a(x)=a3x3+a2x2+a1x+a0
b(x)=b3x3+b2x2+b1x+b0
50
Polynomials with coefficients in
GF(28)
? Their product
c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0
c0=a0 ? b0
c1=a1 ? b0 ? a0 ? b1
c2=a2 ? b0 ? a1 ? b1 ? a0 ? b2
c3=a3 ? b0 ? a2 ? b1 ? a1 ? b2+ ? a0 ? b3
c4=a3 ? b1 ? a2 ? b2 ? a1 ? b3
c5=a3 ? b2 ? a2 ? b3
c6=a3 ? b3
51
Polynomials with coefficients in
GF(28)
? By reducing c(x) modulo a polynomial of degree 4,
the result can be reduced to a polynomial of
degree below 4,In Rijndael,the polynomial
M(x)=x4+1,
As xi mod x4+1=xi mod 4,
52
Polynomials with coefficients in
GF(28)
? The modular product of a( x ) and b( x ),denoted
by d( x ) = a( x ) ??b( x ) is given by d( x ) =
d3x3+d2x2+d1x+d0 with
d0 = a0??b0 ??a3??b1 ??a2??b2 ??a1??b3
d1 = a1??b0 ??a0??b1 ??a3??b2 ??a2??b3
d2 = a2??b0 ??a1??b1 ??a0??b2 ??a3??b3
d3 = a3??b0 ??a2??b1 ??a1??b2 ??a0??b3
53
Polynomials with coefficients in
GF(28)
The operation consisting of multiplication by a
fixed polynomial a( x ) can be written as matrix
multiplication where the matrix is a circulant
matrix,We have,
54
Multiplication by x
? If we multiply b( x ) by the polynomial x,we have,
b3x4+b2x3+b1x2+b0x
? x ??b( x ) is obtained by reducing the above result
modulo 1+x4,This gives b2x3+b1x2+b0x+b3
? The multiplication by x is equivalent to
multiplication by a matrix as above with all ai
=‘00’ except a1 =‘01’,Let c( x ) = x?b( x ),We
have,
55
Multiplication by x
56
The AES Cipher
? Noteworthy features,
– NOT a Feistel structure
? processes entire block in parallel during each round
using substitutions and permutations
– The key that is provided as input is expanded
? Array of forty-four 32-bit words (w[i])
? Four distinct words serve as round key (128 bits)
57
The AES Cipher
– Four different stages (1 permutation,3
substitution)
? Substitute bytes- Uses S-box to perform byte by byte
substitution of the block
? Shift rows- A simple permutation
? Mix columns- Substitution over GF(28)
? Add round key- bitwise XOR of current block and
portion of expanded key
– For both encryption and decryption,
? Start with add round key followed by nine rounds of
four stages,plus tenth round of three stages
58
The AES Cipher
– Only Add round key makes use of the key
? All other stages reversible without knowledge of
key
– Add round key alone is not formidable
? The other three stages add diffusion,confusion,and
nonlinearity
– Each stage is reversible
? SB,SR and MC use inverse function
? ARK uses XOR
– Decryption uses expanded keys in reverse order
59
AES Encryption Round
60
? Rounds, depend on block size and key length
Block size
Key size
128 bits
(Nb=4)
192 bits
(Nb=6)
256 bits
(Nb=8)
128 bits (Nk=4) 10 12 14
192 bits (Nk=6) 12 12 14
256 bits (Nk=8) 14 14 14
The AES Cipher
61
? State, A 4× Nb matrix,
Ex,An initial state with 192 bits(Nb=6),
0 4 8 123 128 123
1 5 9 124 164 15
2 6 10 233 24 255
3 7 11 54 67 34
Nb
The AES Cipher
4
62
The AES Cipher
in2
in1
in6
in9
in7
in13
in15 in3
in5
in0 in8
in10
in11
in14
in12 s0,0
s1,0
s0,2
s2,0
s1,1 s1,2
s0,3
s1,3
s0,1
s2,1 s2,2 s2,3
s3,0 s3,2 s3,3
s0,0
s1,0 s1,1
s3,3
s0,2 s0,3 s0,1
s3,1
s2,0
s3,0
s2,1
s1,2 s1,3
s2,2 s2,3
s3,2
in4 out0
out10
out8 out12
out1 out5 out9 out13
out2 out6
out4
out14
out3 out7 out11 out15 s3,1
63
? Cipher Key, A 4× Nk matrix,
Ex,cipher key with 128 bits(Nk=4),
K0,0 K0,1 K0,2 K0,3
K1,0 K1,1 K1,2 K1,3
K2,0 K2,1 K2,2 K2,3
K3,0 K3,1 K3,2 K3,3
Nk
The AES Cipher
4
64
Structure of Rijndael
B, ByteSub(State)
S, ShiftRow(State)
M, MixColumn(State)
A, AddRoundKey(State,
RoundKey)
plaintext (initial state)
AddRoundKey( )
ciphertext
KeyExpansion Key
RoundKey 0
B S M A round1 RoundKey 1
B S M A round(Nr-1) RoundKey Nr-1
B S A RoundKey Nr roundNr
65
Encryption Flow
Rijnadel(State,CipherKey) {
KeyExpansion( CipherKey,ExpandedKey );
AddRoundKey( State,ExpandedKey );
for(i =1; i < Nr; i++) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey (State,ExpandedKey );
}
ByteSub(State);
ShiftRow(State);
AddRoundKey (State,ExpandedKey );
}
intermediate
round
final
round
initialization
66
AddRoundKey
? AddRoundKey(State,RoundKey)
K0,0 K0,1 K0,2 K0,3
K1,0 K1,1 K1,2 K1,3
K2,0 K2,1 K2,2 K2,3
K3,0 K3,1 K3,2 K3,3
A0,0 A0,1 A0,2 A0,3
A1,0 A1,1 A1,2 A1,3
A2,0 A2,1 A2,2 A2,3
A3,0 A3,1 A3,2 A3,3
b0,0 b0,1 b0,2 b0,3
b1,0 b1,1 b1,2 b1,3
b2,0 b2,1 b2,2 b2,3
b3,0 b3,1 b3,2 b3,3
? =
State (Nb=4) RoundKey
67
ByteSub
? ByteSub(State) 0 4 8 123 128 123
1 5 9 124 164 15
2 6 10 233 24 255
3 7 11 54 67 34
99 242 48,.,.,,
124 107 1,.,.,,
119 111 103,.,.,,
123 197 43,.,.,,
X
Y
,2
)G F ( 2u n d er ][ F in d 1,81
,
?
ji
X
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
1
0
0
0
1
1
11111000
01111100
00111110
00011111
10001111
11000111
11100011
11110001
7
6
5
4
3
2
1
0
7
6
5
4
3
2
1
0
x
x
x
x
x
x
x
x
y
y
y
y
y
y
y
y
68
ByteSub
ai,0*ai,0-1=1mod m(x),m(x)=x8+x4+x3+x+1 (11B)16
b
i,0=Cai,0-1
For Example
ai,0 ai,0-1 bi,0
00000000 00000000 01100011
00000001 00000001 01111100
00000010 10001101 01110111
69
The S-box used in the SubBytes() transformation is presented
in hexadecimal form in Fig,
Figure,S-box,substitution values for the byte xy (in
hexadecimal format),
70
ShiftRow
? ShiftRow(State)
Nb 4 6 8
Row2 1 1 1
Row3 2 2 3
Row4 3 3 4
99 242 48,.,.,,
124 107 1,.,.,,
119 111 103,.,.,,
123 197 43,.,.,,
99 242 48,.,.,,
107 1,.,.,,124
103,.,.,,119 111
..,.,,123 197 43
71
ShiftRow
For Example Nb=4,after shift row A[16]transform to B[16]
m n o p
j k l m
d e f g
w x y z
m n o p
k l m j
f g d e
z w x y
B[16]= A[16]=
72
MixColumn
? MixColumn(State)
b(x)=c(x) a(x) mod
c(x)=
a(x)=
b(x)=
?
''x''x''x'' 02010103 23 ???
14 ?x
012233 axaxaxa ???
012233 bxbxbxb ???
32103
32102
32101
32100
02010103
03020101
01030201
01010302
a''a''a''a''b
a''a''a''a''b
a''a''a''a''b
a''a''a''a''b
????????
????????
????????
????????
b(x) c(x) a(x)
73
MixColumn
? MixColumn(State)
? Inverse of MixColumn, d(x)
c(x) d(x)=‘01’
=> d(x)=
?
'E'x''x'D'x'B' 00900 23 ???
74
Key Schedule
? For Example Nb=4,Nk=4,total expandedkey
We need are 4*(10+1)=44 words
Key[0] Key[4] Key[8] Key[12]
Key[1] Key[5] Key[9] Key[13]
Key[2] Key[6] Key[10] Key[14]
Key[3] Key[7] Key[11] Key[15]
W’0 W’1 W’2 W’3
Cipher Key
W’0
W’1
W’2
W’3
Word0 Word43
Expanded Key
Round key 0 Round key 1 Round key 10
Word4 Word40
75
Key Schedule
? Key Expansion
– Length, block size × (Nr+1) bits
Ex,block size=128 bits,key length=128 bits
128 bits × (10+1)=1408 bits,
– Using a linear array of 4-byte words to save the
expanded key and is denoted by W[Nb*(Nr+1)],
76
Key Schedule
? Key Expansion for Nk≦ 6 (i.e,
128,192 bits)
Key length,128 bits (Nk=4)
Block size,192 bits (Nb=6)
Round Key 0 Round Key 1
?
RotByte()
SubByte()
Rcon[i/Nk]
Nk i=4
?
Nk i=9
32bits
If (i%Nk=0)
If (i%Nk≠0)
77
Key Schedule
? Key Expansion(cont.)
– RotByte(W[i])
(a,b,c,d) -> (b,c,d,a)
– Rcon[i] =(RC[i],’00’,’00’,’00’)
RC[i]=xi-1 representing an element in GF(28)
RC[1]=1 (i.e,’01’)
RC[2]=x (i.e,’02’)
RC[3]=x2 (i.e,’04’)
78
Key Schedule
KeyExpansion(For Nk ??6)
for( i=0; i< Nk; i++ )
W[i]= ( Key[4*i],key[4*i+1],key[4*i+2],key[4*i+3] );
for( i= Nk; i<Nb * (Nr + 1); i++ )
{ temp = W[i - 1];
if (i % Nk == 0)
temp = SubByte(RotByte(temp)) ^
Rcon[i / Nk];
W[i] = W[i - Nk] ^ temp; } }
round0
The rest
round
79
Key Schedule
KeyExpansion(For Nk > 6)
for( i=0; i< Nk; i++ )
W[i]= ( Key[4*i],key[4*i+1],key[4*i+2],key[4*i+3] );
for( i= Nk; i<Nb * (Nr + 1); i++ )
{ temp = W[i - 1];
if (i % Nk == 0)
temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];
else if (i % Nk == 4)
temp = SubByte(temp);
W[i] = W[i - Nk] ^ temp; }
}
round0
The rest
round
80
Inverse Cipher
InvCipher(byte in[4*Nb],byte out[4*Nb],word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
AddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1])
for round = Nr-1 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state,w[round*Nb,(round+1)*Nb-1])
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state,w[0,Nb-1])
out = state
end
81
Add Round Key
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Mix Columns
Shift Rows
Add Round Key
Inverse sub bytes
Inverse shift rows
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Substitute Bytes
Add round key
Shift Rows
Substitute Bytes
Add round key
Substitute Bytes
Shift Rows
Mix Columns
Expand Key
.,
,
.,
,
w[0,3]
w[4,7]
w[36,39]
w[40,43]
Plaintext Plaintext
Ciphertext Ciphertext
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
82
References
? NIST fips-197 ADVANCED
ENCRYPTION STANDARD (AES)
http://csrc.nist.gov/publications/fips/fips197
/fips-197.pdf 2001.11
? Joan Daemen,Vincent Rijmen,AES
Proposal,Rijndael
