Understanding Cryptography: Basics to Galois Fields

This is where you should be at this point in class 1. Base 2,8,16 and conversion among them 2. The difference between binary and ASCII encoded 3. Basic command line navigation 4. File permissions 5. The nature of the shell 6. command line arguments 7. The use of ssh, scp, and tar 8. Encryption 9. Historical 10. Caesar cipher 11. Viginere cipher 12. Playfair cipher 13. transposition, substitution diffusion, confusion 14. symmetric vs asymmetric 15. stream vs block 16. LFRS 17. DES

SECURITY Cryptology cryptanalysis cryptography symmetric asymmetric protocols stream block ciphers ciphers We are here LFSR DES, 3DES, AES

Galois Fields Motivation groups, rings, fields Finite/Galois fields Prime fields Extension Fields, GF(256) AES algorithm in depth

Motivation Why bother with Galois fields? Arbitrary application of substitution/transposition (Claude s confusion & diffusion) is not enough. Even with computers scrambling a lot an insane speeds, we need to understand the resulting probability distributions to ease worry over frequency analysis

Motivation Galois fields (GF(256)) provide the mathematical basis for AES so we have a reasonable handle on what it s doing We need just enough understanding for AES Math courses in abstract algebra, groups rings and fields, field theory, etc. can fill out the pictures for interested in deeper details

Groups, Rings, Fields Groups closed set under binary operation + associative identity inverse

Groups, Rings, Fields Closed: If a and b are in the group, then a op b = c is also in the group The op is associative: a op (b op c) == (a op b) op c There is an identity element i such that a op i == i op a == a for all a For each element there exists an inverse element a-1 such that a op a-1 == a-1 op a == i

Consider integers under + Add any two, get another integer - closed a + (b + c) = (a + b) + c for all a,b,c - associative identity = 0; a + 0 = 0 + a = a for all a For all a there exists a-1 such that a + a-1 = a -1 + a = 0 identity (in other words - a + -a, or a-a)

Groups, Rings, Fields Rings Add a second binary operation * Not all elements need have an inverse under op2

Groups, Rings, Fields Group + (-) Ring + (-) * Field + (-), * (/) (two groups) Very informally A closed set of elements where you can add, subtract, multiply & divide

Groups, Rings, Fields Two groups: all elements form an additive group: +, identity = 0 all elements != 0 form a multiplicative group: *, identity = 1 Distributive law holds when you mix operations a * (b + c) = (a * b) + (a * c)

Groups, Rings, Fields Real numbers are a field Complex numbers are a field Integers?

Finite/Galois Fields We care about Finite Fields finite fields must have pm elements p a prime m a positive integer

Finite/Galois Fields We write: GF(13) p == 13, m==1 We write: GF (121) or GF(112 ) p == 11, m==2

Finite/Galois Fields GF(2) {0, 1} - a field? (all ops are mod 2) closed? plus, times, identity, inverse, associative, distributive when ops are mixed?

Finite/Galois Fields GF(12) ? GF(11) ? GF(256) ?

Finite/Galois Fields GF(256) = GF(28 ) is the Galois field used by AES

Prime Fields If m == 1 we call it a prime field If (m > 1) we call it an extension field GF(pm ) Extension field Prime field GF(p) m == 1 GF(pm ) m>1

Prime Fields Both prime fields and extension fields are of interest in crypto but mostly, and for us, GF(2m)

Prime Fields GF(p) = {0, 1, 2, , p-1} since it is finite, we use (mod p) to wrap back around then +, * as usual: a + b c mod p a * b d mod p

Prime Fields consider GF(5) p==5, m==1 {0, 1, 2, 3, 4}, +,identity = 0 Inverse satisfies a + a-1 ? say you have GF(5) {0, 1, 2, 3, 4} what is the additive inverse of each?

Prime Fields GF(5) additive group {0, 1, 2, 3, 4}, +,identity = 0 {0, 1, 2, 3, 4}, +,identity = 0 what is the additive inverse of each? 4 + 1 = 1 + 4 0 mod p 3 + 2 = 2 + 3 0 mod p 2 + 3 = 3 + 2 0 mod p 1 + 4 = 4 + 1 0 mod p 0 ? What s the general form?

Prime Fields GF(5) additive group: {0, 1, 2, 3, 4}, +,identity = 0 For a, a-1 = (p a) mod p

Prime Fields GF(5) multiplicative group: {0, 1, 2, 3, 4}, *,identity = 1 {0, 1, 2, 3, 4}, *,identity = 1 what is the multiplicative inverse of each? 4 * ? = ? * 4 1 mod 5 3 * ? 2 * ? 1 * ?

Prime Fields GF(5) multiplicative group: {0, 1, 2, 3, 4}, *,identity = 1 {0, 1, 2, 3, 4}, *,identity = 1 what is the multiplicative inverse of each? 4 * 4 = 16, 16 mod 5 = 1, which is the identity 3 * 2 = 6, 6 mod 5 = 1 2 * 3 = 6, 6 mod 5 = 1 1 * 1 = 1, 1 mod 5 = 1 what about 0?

Prime Fields GF(5) multiplicative group: {0, 1, 2, 3, 4}, *,identity = 1 What s the general form? a * a-1 = a-1 * a 1 mod p finding multiplicative inverse can be non-trivial, it took a minute of two with our small GF(5) example the Extended Euclidean Algorithm can do it for us

Extension Fields The elements of GF(2m), m>1, are polynomials am-1 xm-1 + am-2 xm-2+ + a1x + a0 ai GF(2)

Extension Fields GF(23) the polynomials are the 8: a2x2 + a1x + a0 {0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 } 0 0 0

Extension Fields So how do the binary operations work? ? 1?????? ai + bimod 2 a(x) + b(x) = c(x) = ?=0 ? 1?????? ai- bi ai + bimod 2 a(x) - b(x) = c(x) = ?=0 +,- add coefficients term by term ((mod 2) of course)

Extension Fields X2+1 X ------------- X2 + X + 1 Q Q GF(23) X2 + 1 Q ----------------------- -----------

Extension Fields How does multiplication work? (X2+1) * (X2 + X + 1) X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1 but of course

Extension Fields Mod reduction, we want the remainder when divided by when divided by what? In a prime field what = m In an extension field, what = some divisor prime polynomial irreducible polynomial (can t be factored)

Extension Fields so c(x) a(x) * b(x) mod p(x) For GF(23): p(x) = x3 + x + 1 For AES, GF(28): p(x) = x8 + x4 + x3 + x + 1 (you ll always have >= 1 p(x))

Extension Fields How does multiplication work? (X2+1) * (X2 + X + 1) X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1 but of course

Extension Fields X3+ X + 1 X4 + X3 + X + 1

Extension Fields X3+ X + 1 X4 + X3 + X + 1 r = X2 + X

Extension Fields (X2+1)*(X2 + X + 1) = X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1 mod x3 + x + 1 = X2 + X

Extension Fields a-1(x) * a(x) 1 mod p(x)

Galois Field summary A Galois field must have pmelements if m==1, we call it a prime field and the elements of the field are integers. In AES we use the prime field GF(2) for the polynomial term coefficients for a prime field we use modulo the set size to wrap our otherwise too big product or sum, back into the field if (m>1), we call it an extension field and the elements of the field are polynomials. In AES we use the extension field GF(256) elements of GF(256) represent all the possible byte values for the extension field GF(256) we use modulo the irreducible polynomial x8 + x4 + x3 + x + 1 to wrap our otherwise too-big product, back into the field