Microsoft PowerPoint – 17crypto_L07.ppt [Compatibility Mode]
Polynomial Arithmetic
and AES
Crypto & SecDev 2017 © Ron Poet:
Lecture 7
1
and AES
Polynomial Arithmetic
� Polynomial arithmetic is more convenient than integers
mod n when converting to and from a bit string.
�AES uses polynomial arithmetic.
� Integers mod n must be used when actual numbers are � Integers mod n must be used when actual numbers are
being used.
�Public Key algorithms such as RSA and Diffie-
Hellman use integers mod n.
2Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Integers Mod 2
� Polynomial arithmetic, as used in cryptography, is based
on integers mod 2.
� There are only 2 values, 0 and 1.
� Addition and subtraction are both the same and equal to � Addition and subtraction are both the same and equal to
exclusive or.
0+0=0, 0-0=0, 0⊕0=0
0+1=1, 0-1=-1=1, 0⊕1=1
1+0=1, 1-0=1, 1⊕0=1
1+1=2=0, 1-1=0, 1⊕1=0
3Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Polynomials
� A polynomial involves terms in x, x2, x3 and so on.
�We are not interested in actually calculating x.
�We just want to use polynomial arithmetic to produce
new polynomials.new polynomials.
� We are interested in a special form of polynomial where
the coefficients of the powers of x are integers mod 2.
�Either 1 or 0.
� So a typical polynomial would be 1 + x2 + x5
�Or 1 + 0*x + 1*x2 + 0*x3 + 0*x4 + 1*x5 + 0*x6 …
4Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Binary ↔ Polynomial
� Converting from a binary number to a polynomial is very
easy.
�The bits, starting with the least significant bit, are the
coefficients of the powers of x.coefficients of the powers of x.
11012 → 1 + x2 + x3
� Converting back is also straightforward.
x + x3 → 10102
� The operations, +, -, *, % , for encryption and decryption
operations can be done with polynomial arithmetic.
5Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Polynomial Arithmetic
� Addition and subtraction is straightforward.
�Subtraction is the same as addition! Both are xor.
1 + x2 + x3
+ x + x3
= 1 + x + x2
� Multiplication is also straightforward but leads to bigger
polynomials.
(1+x2+x3)(x+x3)
= x + x3 + x4
+ x3 + x5 + x6
= x + x4 + x5 + x6
6Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Remainder after Division
� We can reduce the size of polynomials produced by
multiplication by taking the remainder after dividing one
polynomial by another.
�The same trick as integers mod n.�The same trick as integers mod n.
� If we wanted the highest power to be x3 then we divide by
a polynomial with highest power x4.
� Polynomial division is complicated, even though taught in
high school maths.
� It is a lot easier with polynomials based on integers mod 2.
7Crypto & SecDev 2017 © Ron Poet:
Lecture 7
‘Prime’ Polynomials
� Some polynomials are ‘prime’
�They can’t be written as factors of smaller polynomials.
�They are called irreducible polynomials.
� If we do polynomial arithmetic mod an irreducible � If we do polynomial arithmetic mod an irreducible
polynomial, then all polynomials will have inverses.
� Some irreducible polynomials:
3 bit numbers: x3 + x + 1
4 bit numbers: x4 + x + 1
6 bit numbers: x6 + x + 1
8 bit numbers: x8 + x4 + x3 + x + 1
8Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Example with 3 bit Polynomials
� The irreducible polynomial is x3 + x + 1.
� The eight possible polynomials are:
0 = 0002 = 0 4 = 1002 = x
2
1 = 001 = 1 5 = 101 = x2 + 1
9
1 = 0012 = 1 5 = 1012 = x
2 + 1
2 = 0102 = x 6 = 1102 = x
2 + x
3 = 0112 = x + 1 7 = 1112 = x
2 + x + 1
9Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Calculating Inverses
� The algorithm for calculating polynomial inverses is
similar to that for integers mod n.
�Let p be a polynomial.
�Let z be the inverse of p. Also a polynomial.
10
�Let z be the inverse of p. Also a polynomial.
�pz = 1 mod irreducible polynomial
�Polynomial arithmetic is used.
� The calculations are more complex, and so for small
polynomials, it is easier to create a multiplication table.
10Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Multiplication Table for 3-bit
polynomials
1 2 3 4 5 6 7 Inverse
1: 1 2 3 4 5 6 7 1 (1 * 1 = 1)
2: 2 4 6 3 1 7 5 5 (2 * 5 = 1)
3: 3 6 5 7 4 1 2 6 (3 * 6 = 1)
11
4: 4 3 7 6 2 5 1 7 (4 * 7 = 1)
5: 5 1 4 2 7 3 6 2 (5 * 2 = 1)
6: 6 7 1 5 3 2 4 3 (6 * 3 = 1)
7: 7 5 2 1 6 4 3 4 (7 * 4 = 1)
11Crypto & SecDev 2017 © Ron Poet:
Lecture 7
8-bit Polynomials
� Will work on bytes.
� Results can be stored in a lookup table.
�There are 28 = 256 different polynomials.
�A table is needed for *, there are 216 = 64k values.
12
�Also for inverses, there are 28 = 256 values.
�Each value is 1 byte.
12Crypto & SecDev 2017 © Ron Poet:
Lecture 7
Terminology – Galois Fields
� The mathematical name for using integers mod n and
polynomials mod an irreducible polynomial is computing
with Galois Fields (GF).
�Doesn’t it seem harder all ready!
13
�Doesn’t it seem harder all ready!
� Integers mod n are GF(n).
� Polynomials of degree n are GF(2n).
� Don’t be put off by terminology!
13Crypto & SecDev 2017 © Ron Poet:
Lecture 7
AES – Rjindael
14Crypto & SecDev 2017 © Ron Poet:
Lecture 7
The Rjindael Algorithm
� Similar to DES, but used calculations involving
polynomials rather than table lookups.
� Most arithmetic is performed with 8 bit values, and uses
polynomials mod the irreducible polynomial
Crypto & SecDev 2017 © Ron Poet:
Lecture 7
15
polynomials mod the irreducible polynomial
�x8 + x4 + x3 + x + 1.
Rjindael Blocks and States
� The algorithm can be used with data lengths of 128, 192 or
256 bits, and also key lengths of 128, 192 or 256 bits.
� We will just consider the 128, 128 version.
� Other versions are similar but have more rounds.
Crypto & SecDev 2017 © Ron Poet:
Lecture 7
16
� Other versions are similar but have more rounds.
� The algorithms for encryption and decryption are related
but different.
� Each 128 bit block of data is called a state (S) in Rjindael
terminology.
� The (128, 128) version of the algorithm has 10 rounds,
each with its own 128 bit subkey K[i].
Encryption Algorithm
AddRoundKey(S, K[0]);
for (int round = 1; round <= 10; round++) { SubBytes(S); Crypto & SecDev 2017 © Ron Poet: Lecture 7 17 ShiftRows(S); if (r != 10) MixColumns(S); AddRoundKey(S, K[round]); } AddRoundKey(S, K) � This is very simple. � S and K are xored bit by bit, and the result left in S. Crypto & SecDev 2017 © Ron Poet: Lecture 7 18 SubBytes(S) � The following is applied to each of the 16 bytes s in the state. � 8 bit polynomial arithmetic is used. � s, x, y are all 8-bit values. � -1 where the inverse of 0 is 0. Crypto & SecDev 2017 © Ron Poet: Lecture 7 19 � x = s-1 where the inverse of 0 is 0. � y = Mx, where the matrix M has single bit entries: 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 � y now replaces the old value of s. The Matrix M � This simple structure of the matrix M allows a formal proof that the algorithm is resilient to attacks by differential and linear cryptanalysis. � This contrasts with the choice of S boxes in the DES Crypto & SecDev 2017 © Ron Poet: Lecture 7 20 � This contrasts with the choice of S boxes in the DES algorithm, which was made secretly, leaving the suspicion that they were engineered with hidden trap doors. � This was probably done in DES to suppress knowledge of differential and linear cryptanalysis. � European countries used similar Feistal algorithms that were vulnerable to differential cryptanalysis. ShiftRows(S) � The ShiftRows and MixColumns subroutines ensure that all bytes interact with each other in the algorithm. � They both treat the 16 bytes of the state S as a 4x4 matrix. � ShiftRows is just a simple shift of the 4 bytes in each Crypto & SecDev 2017 © Ron Poet: Lecture 7 21 � ShiftRows is just a simple shift of the 4 bytes in each row. s00 s01 s02 s03 → s00 s01 s02 s03 s10 s11 s12 s13 → s11 s12 s13 s10 s20 s21 s22 s23 → s22 s23 s20 s21 s30 s31 s32 s33 → s33 s30 s31 s32 MixColumns(S) � The 16 bytes can be represented as a 4x4 matrix. � Each column of 4 bytes is treated as a cubic polynomial in X, with 8 bit coefficients, the 0th column becomes: �P(s00) + P(s10)X + P(s20)X 2 +P(s30)X 3 Crypto & SecDev 2017 © Ron Poet: Lecture 7 22 �P(s00) + P(s10)X + P(s20)X +P(s30)X � These polynomials are reduced mod another polynomial X4 + 1 �This is not irreducible, and so care has to be taken to choose numbers that have inverses. � Naturally, each 8 bit coefficient also uses polynomial arithmetic! It is based on integers mod 2. MixColumns (2) � Each column is multiplied by a polynomial in X, with coefficients based on the following polynomials in x. �P1 = 1, P2 = x, P3 = x + 1. � Then reduced mod X4 + 1, take the remainder after Crypto & SecDev 2017 © Ron Poet: Lecture 7 23 � Then reduced mod X + 1, take the remainder after dividing by this polynomial. � The polynomials used are different for each column: col 0) P2 + P3X + P1X 2 + P1X 3 col 1) P1 + P2X + P3X 2 + P1X 3 col 2) P1 + P1X + P2X 2 + P3X 3 col 3) P3 + P1X + P1X 2 + P2X 3 Decryption � Inverse operations are performed in the reverse order. � MixColumns, ShiftRows and SubBytes each have a simple inverse operation that can undo its effects. � AddRoundKey is its own inverse. Crypto & SecDev 2017 © Ron Poet: Lecture 7 24 � AddRoundKey is its own inverse. � InverseSubBytes multiplies by the reverse 8 bit matrix, and then calculates the polynomial inverse. � InverseShiftRows shifts left rather than right. � InverseMixColumns inverts the column matrix and performs the same calculations. Sub Key Generation � We need to produce 11 round keys, each of 128 bits, from the initial 128 bit key. � The key can be thought of as a 4x4 matrix of 16 bytes, just as the data state S that we considered earlier. � Each 4 byte column of the matrix is then treated as a 32 bit Crypto & SecDev 2017 © Ron Poet: Lecture 7 25 � Each 4 byte column of the matrix is then treated as a 32 bit word Cj, so the key consists of 4 such words �Ki = {C0[i], C1[i], C2[i], C3[i] where 0 ≤ i ≤ 10}. � The initial values with i = 0 are taken from the key, and the rest generated using the following algorithm. Sub Key Generation (2) for (i = 1; i <= 10; i++) { T = RotBytes(C3[i-1]) SubBytes2(T); Crypto & SecDev 2017 © Ron Poet: Lecture 7 26 T = T ⊕ RC[i]; C0[i] = C0[i-1] ⊕ T; C1[i] = C1[i-1] ⊕ C0[i]; C2[i] = C2[i-1] ⊕ C1[i]; C3[i] = C3[i-1] ⊕ C2[i]; } Sub Key Generation (3) � RotBytes rotates a word by 8 bits to the left (one byte) and returns the result. � SubBytes2 is similar to the previous SubBytes, but applied to a single word of 4 bytes, rather than a matrix of 16 bytes. Crypto & SecDev 2017 © Ron Poet: Lecture 7 27 16 bytes. � RC[i] = xi mod (x8 + x4 + x3 + x + 1)