Transcript a+b

Number Theory and
Advanced Cryptography
1. Finite Fields and AES
Part I: Introduction to Number Theory
Part II: Advanced Cryptography
Chih-Hung Wang
Sept. 2011
1
Group


A set of elements or “numbers”
obeys:





(A1) Closure: If a and b belong to G, then ab is also in G.
(A2) Associative: (ab) c = a(b c)
(A3) Identity element: There is an element e in G such
that a e = e a = a
(A4) Inverses element: For each a in G there is an element
a’ in G such that a a’ = a’ a = e
If commutative (A5) a b = b a for all a, b in G then
forms an abelian group
2
Cyclic Group

Define exponentiation as repeated application of
operator




Define identity: e=a0
a-n=(a’)n
A group is cyclic if every element is a power of
some fixed element


example: a-3 = a a a
ie b = ak for some a and every b in group G
a is said to generate the group G or to be a generator
of G.
3
Ring





A set of “numbers” with two operations (addition + and
multiplication ) which are:
An abelian group with addition operation (A1-A5)
Multiplication:
 (M1) Closure
 (M2) Associative: a(bc)=(ab)c
 (M3) Distributive law: a(b+c) = ab + ac
If multiplication operation is commutative, it forms a commutative
ring
 (M4) Commutativity of multiplication: ab=ba
If multiplication operation has identity and no zero divisors, it
forms an integral domain
 (M5) Multiplicative identity: There is an element 1 in R such that
a1=1a =a
 (M6) No zero divisors: If a,b in R and ab=0, then either a=0 or 4
b=0.
Field

A set of numbers with two operations:
Abelian group for addition (A1-A5)
 Abelian group for multiplication (ignoring 0) (M1M6)
 (M7) Multiplicative inverse: For each a in F,
except 0, there is an element a-1 in F such that
aa-1=(a-1)a =1.

5
Group, Ring and Field
6
Modular Arithmetic


Define modulo operator a mod n to be remainder
when a is divided by n
Use the term congruence for: a ≡ b mod n



r is called the residue of a mod n


when divided by n, a & b have the same remainder
eg. 73 ≡ 4 mod 23
since with integers can always write: a = qn + r
Usually have 0 <= b <= n-1

-12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7
7
The Relationship
a = qn + r, 0r<n
8
Modulo 7 Example
...
-21 -20 -19 -18 -17 -16 -15
-14 -13 -12 -11 -10 -9 -8
-7 -6 -5 -4 -3 -2 -1
0
1
2
3
4
5
6
7
8
9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 32 33 34
...
9
Divisors





Say a non-zero number b divides a if for
some m have a=mb (a,b,m are all integers)
That is b divides into a with no remainder
Denote this b|a
Also say that b is a divisor of a
eg. all of 1,2,3,4,6,8,12,24 divide 24
10
Modular Arithmetic Operations




is 'clock arithmetic'
uses a finite number of values, and loops back
from either end
modular arithmetic is when do addition &
multiplication and modulo reduce answer
can do reduction at any point, ie



a+b mod n = [(a mod n) + (b mod n)] mod n
a-b mod n = [(a mod n) – (b mod n)] mod n
ab mod n = [(a mod n)  (b mod n)] mod n
11
Property
a  b mod n if n | (a  b)
a  b mod n implies b  a mod n
a  b mod n and b  c mod n imply a  c mod n
12
Modular Arithmetic




Can do modular arithmetic with any group of
integers: Zn = {0, 1, … , n-1}
form a commutative ring for addition
with a multiplicative identity
note some peculiarities
if (a+b)≡(a+c) mod n then b≡c mod n
 but (ab)≡(ac) mod n then b≡c mod n only if a is
relatively prime to n

13
Relatively Prime


Relative prime: their only common positive
integer factor is 1.
An integer has a multiplicative inverse in Zn if that
integer is relatively prime to n.
(( a 1 )ab)  (( a 1 )ac) mod n
b  c mod n

Example:



63=18 ≡ 2 mod 8
67=42 ≡ 2 mod 8
3 ≡ 7 mod 8
6 and 8 are not relatively prime
14
Residue Class

The residue classes modulo n as


[0], [1], [2], …, [n-1] where
[r] = {a: a is an integer, a ≡ r mod n}
Z8
0
1
2
3
4
5
6
7
6
0
6
12
18
24
30
36
42
Residues
0
6
4
2
0
6
4
2
15
Multiplicative Inverse

Z8
0
1
2
3
4
5
6
7
5
0
5
10
15
20
25
30
35
Residues
0
5
2
7
4
1
6
3
If p is a prime number, then all the elements of Zp
are relatively prime to p

Multiplicative inverse (w-1)
For each w  Z p there exists a z such that w z 1 mod p
 For each w Z n and gcd(w,n)=1, there exists a z such that w
z 1 mod n

16
Modulo 8 Example (1)
17
Modulo 8 Example (2)
18
Properties of Modular Arithmetic for
Integer Zn
19
Greatest Common Divisor (GCD)


A common problem in number theory
GCD (a,b) of a and b is the largest number
that divides evenly into both a and b


eg GCD(60,24) = 12
Often want no common factors (except 1)
and hence numbers are relatively prime
eg GCD(8,15) = 1
 hence 8 & 15 are relatively prime

20
Euclid's GCD Algorithm


An efficient way to find the GCD(a,b)
uses theorem that:
GCD(a,b) = GCD(b, a mod b)
 gcd(55,22)=gcd(22,55 mod 22)=gcd(22,11)=11


Euclid's Algorithm to compute GCD(a,b):
EUCLID(a,b)
1. A a; B b
2. If B=0 return A=gcd(a,b)
3. R = A mod B
4. A  B
5. B  R
6. goto 2
21
Example GCD(1970,1066)
1970 = 1 x 1066 + 904
1066 = 1 x 904 + 162
904 = 5 x 162 + 94
162 = 1 x 94 + 68
94 = 1 x 68 + 26
68 = 2 x 26 + 16
26 = 1 x 16 + 10
16 = 1 x 10 + 6
10 = 1 x 6 + 4
6=1x4+2
4=2x2+0
gcd(1066, 904)
gcd(904, 162)
gcd(162, 94)
gcd(94, 68)
gcd(68, 26)
gcd(26, 16)
gcd(16, 10)
gcd(10, 6)
gcd(6, 4)
gcd(4, 2)
gcd(2, 0)
22
Galois Fields





Finite fields play a key role in cryptography
Can show number of elements in a finite field
must be a power of a prime pn
Known as Galois fields
Denoted GF(pn)
In particular often use the fields:
GF(p)
 GF(2n)

23
Galois Fields GF(p)


GF(p) is the set of integers {0,1, … , p-1}
with arithmetic operations modulo prime p
These form a finite field


since have multiplicative inverses
Hence arithmetic is “well-behaved” and can
do addition, subtraction, multiplication, and
division without leaving the field GF(p)
24
Example GF(7) -- (1)
25
Example GF(7) -- (2)
26
Finding Inverses (1)

Can extend Euclid’s algorithm:
EXTENDED EUCLID(m, b)
1. (A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 / B3
5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
27
Finding Inverses (2)
mT1  bT2  T3
mA1  bA2  A3
mB1  bB2  B3
mB1  bB2  B3
mB1  bB2  1
bB2  1  mB1
bB2  1 mod m
28
Inverse of 550 in GF(1759)
3
1759
1650
550
545
109
5
5
29
Polynomial Arithmetic

Ordinary polynomial arithmetic

A polynomial with degree n
n
n
n 1
f ( x)  an x  an 1 x  ...  a1 x  a0   ai x i
i 0
n
m
i 0
i 0
f ( x)   ai x i , g ( x)   bi x i , n  m
m
f ( x)  g ( x)   (ai  bi ) x i 
i 0
n
i
a
x
 i
i  m 1
nm
f ( x)  g ( x)   ci x i , where
i 0
ck  a0bk  a1bk 1  ...  ak 1b1  ak b0
30
Polynomial Arithmetic with
Coefficients in Zp


Polynomial ring
Example of GF(2)
31
Example of GF(2)
32
Irreducible


A polynomial f(x) over a field F is called irreducible
if and only if f(x) cannot be expressed as a product
of two polynomials.
The polynomial f ( x)  x 4  1 over GF(2) is reducible
because x 4  1  ( x  1)( x 3  x 2  x  1)
x3  x  1
is irreducible
33
Finding the GCD

EUCLID Algorithm
34
Finite Fields of the Form GF(2n)


To work with integers that fit exactly into a given
number of bits, with no wasted bit patterns. (for
implementation efficiency)
Arithmetic in GF(23)

Addition
35
Arithmetic in GF(23)

Multiplication
36
Arithmetic in GF(23)

Additive and multiplicative inverses
37
Modular Polynomial Arithmetic

Consider the set S of all polynomials of degree n-1
or less over the field Zp. Thus, each polynomial has
the form
n 1
f ( x)   ai x i
i 1
where each ai takes on a value in the set {0,1,…,p-1}.
There are a total of pn different polynomials in S.
38
Arithmetic Operations



Arithmetic follows the ordinary rules of polynomial
arithmetic using the basic rules of algebra, with the
following refinements.
Arithmetic on the coefficients is performed modulo p.
That is, we use the rules of arithmetic for the finite field
Z p.
If multiplication results in a polynomial of degree
greater than n-1, than the polynomial is reduced modulo
some irreducible polynomial m(x) of degree n. That is,
we divide by m(x) and keep the remainder. For a
polynomial f(x), the remainder is expressed as
r(x)=f(x) mod m(x).
39
Example of GF(28) – in AES (1)
40
Example of GF(28) – in AES (2)
41
Construction of GF(23)

Two irreducible
polynomials in GF(23)
x3  x 2  1
x3  x  1
42
Polynomial Arithmetic Modulo
3
x  x  1 (1)
43
Polynomial Arithmetic Modulo
3
x  x  1 (2)
44
Finding the Multiplicative Inverse
45
Implementation Considerations (1)

Addition
46
Implementation Considerations (2)

Multiplication (1)
47
Implementation Considerations (3)

Multiplication (2)
48
Implementation Considerations (4)

Multiplication (3)
49
AES (Advanced Encryption Standard)




Next generation encryption standard of
NIST/FIPS
It will replace the use of DES in the following
30 years
The sensitive information protected by AES
can not be revealed within 100 years
It is selected by the competition from
international selection process
50
Calendar of AES
Announcement
Requirements workshop
Final requirements
Pre-submission
Submission
AES conference 1-presentation
AES conference 2-analysis
Selection of 5 finalists
AES conference 3
Final AES selection
January 1997
April 1997
September 1997
April 15,1998
June15,1998
August 20-22,1998
March 22-23,1999
April 15,1999
Beginning of 2000?
October 2, 2000
51
AES Requirements







Block cipher
128-bit block
128/192/256-bit keys
It is equal to Triple DES at least on security and is
more efficient
Provide descriptions and analysis
Provide three implementations in two languages
(reference and optimized in C，optimized in Java)
IF selected, royalty free world wide
52
The 15 Submission for AES (1)
Cipher
Submitted
Country
CAST-256
Entrust
Canada
Crypton
Future
Korea
Deal
Outerbridge
Canada
DFC
ENS-CNRS
France
E2
NTT
Japan
Frog
TecApro
Costa Rica
HPC
Schroeppel
USA
LOKI97 Brown,Pieprzyk,Seberry Australia
53
The 15 Submission for AES (2)
Magenta
* Mars
* RC6
* Rijndael
Safer+
* Serpent
* Twofish
Deutsche
Germany
IBM
USA
RSA
USA
Daeman,Rijmen
Belgium
Cylink
USA
Anderson，Biham UK，Israel
，Kundsen
，Norway
Counterpane
USA
54
Final AES Selection

Rijndael
Block cipher with block size 128 bits
 Accept 128-, 192-, 256-bit length keys
 Easy to implement in H/W

55
The Implementation of Crypto
Algorithms (W32)

http://www.cryptosoft.com



Crypto++: a C++ Class Library of Cryptographic
Primitives



Different platforms: win16, win32, linux, OS/2,…
Triple DES, Rijndael, Safer+, Blowfish, Cast-128, …
Version 3.0 1/1/1999
http://www.eskimo.com/~weidai/cryptlib.html
Microsoft CryptoAPI
56
More AES Information

NIST AES Homepage

http://csrc.nist.gov/encryption/aes/






Rijndael Specification Those who are interested in the
AES specification (i.e., what will be in the standard)
should refer to the Draft FIPS for the AES.
Test Values
Supporting Documentation
Rijndael Developers' Contact Information
Rijndael Code: C/C++/Java/Visual Basic
Rijndael Homepage

http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
57
The AES Cipher

AES Parameters
58
The AES Cipher - Rijndael



Designed by Rijmen-Daemen in Belgium
128/192/256 bit keys, 128 bit data
An iterative rather than feistel cipher
treats data in 4 groups of 4 bytes
 operates an entire block in every round


Designed to be:
resistant against known attacks
 speed and code compactness on many CPUs
 design simplicity

59
Rijndael


Processes data as 4 groups of 4 bytes (state)
Steps





byte substitution (uses an S-box to perform a byte-by-byte
substitution of the block)
shift rows (a simple permutation)
mix columns (substitution uses arithmetic over GF(28))
add round key (a simple bitwise XOR of the current block
with a portion of the expanded key)
All operations can be combined into XOR and table
lookups - hence very fast & efficient
60
Rijndael
61
AES Data Structure
62
Byte Substitution



A simple substitution of each byte
Uses one table of 16x16 bytes containing a
permutation of all 256 8-bit values
Each byte of state is replaced by byte in row (left 4bits) & column (right 4-bits)




eg. byte {95} is replaced by row 9 col 5 byte
which is the value {2A}
S-box is constructed using a defined transformation
of the values in GF(28)
Designed to be resistant to all known attacks
63
Example of the SubBytes
64
S-box of AES (1)
65
S-box of AES (2)
66
AES Byte-Level Operations (1)
67
AES Byte-Level Operations (2)
68
Construction of the S-box (1)
69
Construction of the S-box (2)
70
Construction of the S-box (3)
{95}-1 in GF(28) = {8A} = {10001010}
71
Construction of the S-box (4)

Inverse substitute byte transformation
72
Construction of the S-box (5)
73
Shift Rows (1)

A circular byte shift in each each
 1st
row is unchanged
 2nd row does 1 byte circular shift to left
 3rd row does 2 byte circular shift to left
 4th row does 3 byte circular shift to left


Decrypt does shifts to right
Since state is processed by columns, this step
permutes bytes between the columns
74
Shift Rows (2)
75
Mix Columns (1)



Each column is processed separately
Each byte is replaced by a value dependent on
all 4 bytes in the column
Effectively a matrix multiplication in GF(28)
using prime polynomial m(x) =x8+x4+x3+x+1
76
Mix Columns (2)
77
Example of the MixColumns (1)
78
Example of the MixColumns (2)
79
Inverse MixColumns (1)
80
Inverse MixColumns (2)
81
Add Round Key




XOR state with 128-bits of the round key
Again processed by column (though
effectively a series of byte operations)
Inverse for decryption is identical since XOR
is own inverse, just with correct round key
Designed to be as simple as possible
82
AES Round
83
Example of Add Round Key
84
AES Key Expansion



Takes 128-bit (16-byte) key and expands into
array of 44/52/60 32-bit words
Start by copying key into first 4 words
Then loop creating words that depend on
values in previous & 4 places back
in 3 of 4 cases just XOR these together
 every 4th has S-box + rotate + XOR constant of
previous before XOR together


Designed to resist known attacks
85
Algorithm (1)
86
Algorithm (2)
87
Example of AES Key Expansion
88
AES Decryption (1)


AES decryption is not identical to encryption
since steps done in reverse
But can define an equivalent inverse cipher
with steps as for encryption
but using inverses of each step
 with a different key schedule


Works since result is unchanged when
swap byte substitution & shift rows
 swap mix columns & add (tweaked) round key

89
AES Decryption (2) Equivalent Inverse
90
Implementation Aspects

Can efficiently implement on 8-bit CPU
byte substitution works on bytes using a table of
256 entries
 shift rows is simple byte shifting
 add round key works on byte XORs
 mix columns requires matrix multiply in GF(28)
which works on byte values, can be simplified to
use a table lookup

91
Implementation Aspects

Can efficiently implement on 32-bit CPU
redefine steps to use 32-bit words
 can precompute 4 tables of 256-words
 then each column in each round can be computed
using 4 table lookups + 4 XORs
 at a cost of 4*(1024 bytes) to store tables


Designers believe this very efficient
implementation was a key factor in its
selection as the AES cipher
92