Transcript AES S-Boxes in depth

AES S-box How and Why?
Notes
• The general math review slides are taken from a variety of internet
sources. I tried to be diligent in citing, but given the nature of basic
math, I may have missed some citation
• This presentation assumes you are comfortable with symmetric
ciphers as well as the details of AES.
Basic Math Review: Represent decimals as
polynomials
Basic Math Review: Fields, groups, rings
• In mathematics, and more specifically in abstract algebra, the term
algebraic structure generally refers to a set with one or more
operations defined on it
• A group is an algebraic system consisting of a set, an identity element, one
operation and its inverse operation.
• A ring is an algebraic system consisting of a set, an identity element, two
operations and the inverse operation of the first operation.
• A field is an algebraic system consisting of a set, an identity element for each
operation, two operations and their respective inverse operations.
• GF(p) for any prime, p, this Galois Field has p elements which are the residue
classes of integers modulo p.
Basic Math Review: Galois Fields
The order of the field is given by pn while p is called the characteristic
of the field example:
gf(5) = (0; 1; 2; 3; 4)
which consists of 5 elements where each of them is a polynomial of
degree 0(a constant) while
gf(23) = (0; 1; 2; 2 + 1; 22; 22 + 1; 22 + 2; 22 + 2 + 1)
= (0; 1; 2; 3; 4; 5; 6; 7)
which consists of 23 = 8 elements where each of them is a polynomial
of degree at most 2 evaluated at 2.
5
Basic Math Review: Galois Field Addition
Basic Math Review: Galois Field Addition
Basic Math Review: Galois Field Multiplication
Basic Math Review: First refresh your memory
on polynomial multiplication
Basic Math Review: Polynomial Division
For additional review of basic polynomial math http://www.doc.ic.ac.uk/~mrh/330tutor/ch04s02.html
Basic Math Review: Galois Field Multiplication
Basic Math Review: Polynomial Arithmetic
• Can compute using polynomials
• Several alternatives available
• ordinary polynomial arithmetic
• poly arithmetic with coords mod p
Basic Math Review: Polynomial Arithmetic
• add or subtract corresponding coefficients
• multiply all terms by each other
• For example:
• let f(x) = x3 + x2 + 2 and g(x) = x2 – x + 1
f(x) + g(x) = x3 + 2x2 – x + 3
f(x) – g(x) = x3 + x + 1
f(x) x g(x) = x5 + 3x2 – 2x + 2
Basic Math Review: Polynomial Arithmetic
• when computing value of each coefficient do calculation modulo some
value could be modulo any prime but we are most interested in mod 2
• ie all coefficients are 0 or 1
• eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1
f(x) + g(x) = x3 + x + 1
f(x) x g(x) = x5 + x2
Basic Math Review: Polynomial Arithmetic
• can write any polynomial in the form:
• f(x) = q(x) g(x) + r(x)
• can interpret r(x) as being a remainder
• r(x) = f(x) mod g(x)
• if have no remainder say g(x) divides f(x)
• if g(x) has no divisors other than itself & 1 say it is irreducible (or prime)
polynomial
• arithmetic modulo an irreducible polynomial forms a field
Basic Math Review: Polynomial Arithmetic
• can compute in field GF(2n)
• polynomials with coefficients modulo 2
• whose degree is less than n
• hence must reduce modulo an irreducible poly of degree n (for multiplication only)
• Form a finite field
Basic Math Review: Polynomial Arithmetic
• Find the results of
(x5+x2+x) * (x7+x4+x3+x2+x )
in GF(28) with irreducible polynomial x8+x4+x3+x+1
Basic Math Review: Polynomial Arithmetic
Answer
• Multiply the two polynomials
• (x5+x2+x) * x7+x4+x3+x2+x = x5 * (x7+x4+x3+x2+x ) + x2 * (x7+x4+x3+x2+x ) + x *
(x7+x4+x3+x2+x ) = (x12+x7+x2)
• Get the results of
• (x12+x7+x2) mod (x8+x4+x3+x+1) = (x5+x3+x2+x+1)
x4 1
x 8  x 4  x 3  x  1 x12  x 7  x 2
x12  x 8  x 7  x 5  x 4
x8  x 5  x 4  x 2
x8  x 4  x 3  x  1
Re m ainderx 5  x 3  x 2  x  1
Basic Math Review: Polynomial Arithmetic Polynomial Algebra
• Operation of addition is performed using an XOR operation denoted by . For example, all
notations below are equivalent: 
(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2 + 0
[polynomial notation];
{01010111} {10000011} = {11010100} [binary notation].

• Multiplication in Rijndael is the multiplication of polynomials modulo the irreducible
polynomial. For example, in the polynomial notation:
(x6 + x4 + x2 + x + 1) • (x7 + x + 1)
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1,
and
(x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) mod (x6 + x4 + x2 + x + 1)
= x7 + x + 1.
The set of 256 possible byte values, with XOR used as addition,
and the multiplication  defined as above, has the structure of the
finite field GF(28).
19
Basic Math Review: Matrix multiplication
• Here is a key
point: You
cannot just
multiply each
number by
the
correspondin
g number in
the other
matrix.
Matrix
multiplication
is not like
addition or
subtraction.
From: http://www.freemathhelp.com/matrix-multiplication.html
Basic Math Review: Matrix Multiplication
Continued
• The first two steps
From: http://www.freemathhelp.com/matrix-multiplication.html
Basic Math Review: Matrix Multiplication
• Steps 3 & 4
From: http://www.freemathhelp.com/matrix-multiplication.html
Basic Math Review: Matrix Multiplication
• Step 5
From: http://www.freemathhelp.com/matrix-multiplication.html
Basic Math Review: Matrix Multiplication


Matrix Multiplication is NOT Commutative!
Order matters!
You can multiply matrices only if the number
of columns in the first matrix equals the
number of rows in the second matrix.
2 columns
3
2
 5 6    1

  3
 9 7 
2
4
0
5 
2 rows
Basic Math Review: Matrix Determinants
To find the determinant of a 2 x 2 matrix,
multiply diagonal #1 and subtract the product
of diagonal #2.
Diagonal 2 = -2
3 1

2 4
Diagonal 1 = 12
12  (2)  14
Basic Math Review: Matrix Determinants
To find the determinant of a 3 x 3 matrix, first
recopy the first two columns. Then do 6
diagonal products.
18
5
2
60
6 5
16
2
2 1 4 2 1
3 3 4 3 3
-20
-24
36
Basic Math Review: Inverse Matrices
 When you multiply a matrix and its
inverse, you get the identity matrix.
 3 1  2 1   1 0 
 5 2   5 3   0 1 


 

Basic Math Review: Inverse Matrices
 Not all matrices have an inverse!
 To find the inverse of a 2 x 2 matrix,
first find the determinant.
a) If the determinant = 0, the inverse does
not exist!
 The inverse of a 2 x 2 matrix is the
reciprocal of the determinant times the
matrix with the main diagonal swapped
and the other terms multiplied by -1.
Basic Math Review: Inverse Matrices
Example 1: A   3 1
 5 2 


det(A)  6  (5)  1
1 2 1 2 1
A  


1  5 3  5 3
1
Basic Math Review: Scalar Multiplication
To do this, multiply each entry in the
matrix by the number outside (called the
scalar). This is like distributing a
number to a polynomial.
Example:
 2 4   8 16 




4  5 0    20 0 
 1 3   4 12 
AES – Rijndael mathematics
• Rijndael is defined in the Galois field GF (28)
by the irreducible polynomial
P = x8 + x4 +x3 +x +1
• In HEX this is 11B, in binary it is 100011011
• Why this one?” The polynomial m(x) (‘11B’) for the
multiplication in GF(28) is the first one of the list of
irreducible polynomials of degree 8, given in [LiNi86, p.
378].” page 22 of AES Proposal: Rijndael
• LiNi86 is R. Lidl and H. Niederreiter, Introduction to finite
fields and their applications, Cambridge University Press,
1986)
Irreducible Polynomials
A polynomial is irreducible in GF(p) if it does not factor over GF(p).
Otherwise it is reducible.
Examples:
The same polynomial is reducible in Z5 but irreducible in Z2.
Are there other irreducible polynomials of power 8? Yes of course, the only list I
am aware of is in the book cited by the inventors of Rijndael
Irreducible Polynomials
You can check the same source that was cited by the inventors of Rijndael. In fact on
Amazon, there is the ‘look inside’ option and with a bit of work you can find the
table. To save you some time, here are a few irreducible polynomials from that list (in
binary form, you may place them in polynomial or hex form if you wish)
100101011
100111001
100111111
101001101
101011111
101110111
110001011
OK why degree 8 (9 digits) isn’t that one too many? “Clearly, the result will be a
binary polynomial of degree below 8. Unlike for addition, there is no simple
operation at byte level.” – page ¾ of the specification
The reason an irreducible but not primitive polynomial is used is that we are trying to make a
non-linear permutation function that has diffusion, spreading input bits to output bits in an
non-linear way.
The Finite Field
8
GF(2 ).
• The case in which n is greater than one is much more difficult to describe. In
cryptography, one almost always takes p to be 2 in this case. This section just
treats the special case of p = 2 and n = 8, that is. GF(28), because this is the field
used by Advanced Encryption Standard (AES).
• The AES works primarily with bytes (8 bits), represented from the right as:
• b7b6b5b4b3b2b1b0.The 8-bit elements of the field are regarded as polynomials with
coefficients in the field Z2:
• b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x1 + b0.
The field elements will be denoted by their sequence of bits, using two hex digits.
The multiplicative inverse
• Multiplication in Galois Field, however, requires more tedious work.
Suppose f(p) and g(p) are polynomials in gf(pn) and let m(p) be an
irreducible polynomial (or a polynomial that cannot be factored) of degree
at least n in gf(pn). We want m(p) to be a polynomial of degree at least n so
that the product of two f(p) and g(p) does not exceed 11111111 = 255 as
the product needs to be stored as a byte. If h(p) denotes the resulting
product then
• h(p) = (f(p) * g(p)) (mod m(p))
• On the other hand, the multiplicative inverse of f(p) is given by a(p) such
• that
• (f(p) * a(p)) (mod m(p)) = 1
The multiplicative inverse
Note that calculating the product of two polynomials and the multiplicative inverse
of a polynomial requires both reducing coeficients modulo p and reducing
polynomials modulo m(p). The reduced polynomial can be calculated easily with
long division while the best way to compute the multiplicative inverse is by using
Extended Euclidean Algorithm. The details on the calculations in gf(28) is best
explained in the following example.
Princeton University offers this calculator for multiplicative inverse
http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?n=9&p=8
We will look at two methods for calculating multiplicative inverse later in this
lesson, but you can also use this calculator if you prefer, or the multiplicative
inverse table I have provided.
There is also a calculator online that does all modular arithmetic
http://ptrow.com/perl/calculator.pl
More on Galois Fields
• Galois Field sizes can be defined with various field sizes like GF(16) or
GF(256). AES is not the only cryptographic algorithm to use these
finite fields. Quad also uses finite fields under a polynomial modulus
Implementing GF(p^k) arithmetic
Theorem: Let f(x) be an irreducible polynomial
of degree k over Zp.
The finite field GF(pk) can be realized as the set
of degree k-1 polynomials over Zp, with addition
and multiplication done modulo f(x).
Example: Implementing GF(2^k)
By the theorem the finite field GF(25) can be realized as
the set of degree 4 polynomials over Z2, with addition
and multiplication done modulo the irreducible polynomial
f(x)=x5+x4+x3+x+1.
The coefficients of polynomials over Z2 are 0 or 1.
So a degree k polynomial can be written down by k+1 bits.
For example, with k=4:
x3+x+1
x4+ x3+x+1
(0,1,0,1,1)
(1,1,0,1,1)
Implementing GF(2^k)
Addition: bit-wise XOR (since 1+1=0)
x3+x+1
(0,1,0,1,1)
+
x4+ x3+x
(1,1,0,1,0)
------------------------------x4
+1
(1,0,0,0,1)
Implementing GF(2^k)
Multiplication: Polynomial multiplication, and then
remainder modulo the defining polynomial f(x):
(1,1,0,1,1) *(0,1,0,1,1)
= (1,1,0,0,1)
For small size finite field, a lookup table is the most efficient
method for implementing multiplication.
Mathematical background(Cont.)
• 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:
What is a multiplicative inverse?
• In mathematics, the reciprocal, or multiplicative inverse, of a number
x is the number which, when multiplied by x, yields 1. The
multiplicative inverse for the real numbers, for example, is 1/x. To
avoid confusion by writing the inverse using set specific notation, we
generally write x-1.
• Zero does not have a reciprocal, as division by 0 is undefined
Multiplication of polynomials
• Finite field multiplication is more difficult than addition and is
achieved by multiplying the polynomials for the two elements
concerned and collecting like powers of x in the result. Since each
polynomial can have powers of x up to 7, the result can have powers
of x up to 14 and will no longer fit within a single byte.
• This situation is handled by replacing the result with the remainder
polynomial after division by a special eighth order irreducible
polynomial, which, for Rijndael, is:
• m(x) = x8 + x4 + x3 + x +1
Note: we will discuss why this irreducible polynomial in just a little
while.
Multiplication Polynomials by Repeated Shifts
• The finite field element {00000010} is the polynomial x, which means that
multiplying another element by this value increases all it’s powers of x by 1. This
is equivalent to shifting its byte representation up by one bit so that the bit at
position i moves to position i+1. If the top bit is set prior to this move it will
overflow to create an x8 term, in which
• case the modular polynomial is added to cancel this additional bit, leaving a
result that fits within a single byte.
• For example, multiplying {11001000} by x, that is {00000010}, the initial result is
• 1{10010000}. The ‘overflow’ bit is then removed by adding 1{00011011}, the
modular
• polynomial, using an exclusive-or operation to give a final result of {10001011}.
NOTE: This why the implementation of creating the S-boxes includes four steps of
shifting. This is in essence, multiplying.
Affine Transformation What is it
This concept originates in graphics, and is also used in transforming graphics. Moving pixels in
one direction or another is very similar to moving a value in a matrix, so the concept gets
applied to matrices (as in AES)
In geometry, an affine transformation or affine map or an affinity (from the Latin, affinis,
"connected with") between two vector spaces (strictly speaking, two affine spaces) consists of
a linear transformation followed by a translation:
In general, an affine transform is composed of linear transformations (rotation, scaling or
shear) and a translation (or "shift"). Several linear transformations can be combined into a
single one, so that the general formula given above is still applicable. For our purposes it is
just a word for a linear transformation. This video also gives a good explanation:
http://www.youtube.com/watch?v=4vrYNxlkrpI
Now what are linear transformation? Well for more detail
http://www.samiam.org/galois.html
Rijndael Galois
• The Rijndael Block Chiper uses finite field arithmetic in the field of GF( 28 )
or the Galois
• Field. For Rijndael we show this eld as a polynomial where each b is a bit in
a byte that can contain the binary value of either 1 or 0.
• b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0
• The values used in Rijndael are displayed in hexadecimal value form and
each hexadecimal value correspond to a polynomial representation. Fore
example: Here is a byte containing the hexadecimal value of 57 and it
corresponding binary and polynomial representations
• Binary = 01010111 Polynomial = x6 + x4 + x2 + x + 1
Rijndael Galois
• The s-box is generated by determining the multiplicative inverse for a given
number in the Galois led, zero would be set to zero. The multiplicative inverse is
transformed using the following affine transformation
• where [x0, ..., x7] is the multiplicative inverse as a vector.
• Now you can do this with matrix mathematics, first multiplying the matrix by the
vectors, then xoring with the values in the final column. This affine
transformation is the sum of multiple rotations of the byte as a vector, where
addition is the XOR operation. NOTE This is what we are duplicating in the
function to create this transform that we did earlier this week
Why these choices?
• We don’t know all the why’s of these choices, but we do
know some.
• The last vector that is xord in is meant to prevent the generation of
a fixed point In other words S-box(a)=a
• The matrix obviously has meaning. Now they did not state it, but
looking at it even briefly reveals a pattern.
• Look at the next slide to analyze the choices
AES S-Box Design
• The S-box is generated by determining the multiplicative inverse for a
given number in Rijndael's Galois field. The multiplicitive inverse is
then transformed using the following affine transformation matrix
• GF(28) = GF(2)[x]/(x8 + x4 + x3 + x + 1)
Now you can do this with matrix math we already described, or you can
do it with the function we provided to you yesterday (and is also at the
end of this presentation)
Why these choices?
• In the submission of Rijndael Joan Daemen & Vincent Rijmen stated reasons for
many things, such as the particular modulus to use. But questions still may be in
your mind?
• Why this matrix for the affine transform and not some other?
• Why this particular vector for the affine transform and not some other?
• Here are the only answers they gave, and the following is a quote
directly from their submission.
How to calculate this yourself
• Unfortunately, no, it is not the same as computing the inverse of a
matrix. Also, there are at least two issues involved here. One is what
are elements of this finite field GF(2^8)? The other is how are they
represented on the computer (i.e. in binary)? And then we can get to
the question of how to invert them.
• First of all, an element of GF(2^8) is a polynomial of degree less than
8 over GF(2) (with coefficients in GF(2)) modulo an irreducible
polynomial of degree 8. So the first thing you have to do is pick a
polynomial of degree 8, and use this as your field modulus. The AES
standard says what this modulus is.
How to calculate the Multiplicative inverse
• The multiplicative inverse for an element a of a finite field can be
calculated a number of different ways:
• By multiplying a by every number in the field until the product is one. This is a
Brute-force search.
• By using the Extended Euclidean algorithm
• By making a logarithm table of the finite field, and performing subtraction in
the table. Subtraction of logarithms is the same as division.
Compute multiplicative inverse
• Remember that in modular arithmetic, the modular multiplicative
inverse of x is the number a such that ax ≡ 1 (mod n). This
multiplicative inverse exists if and only if a and n are coprime. For
example, the inverse of 3 modulo 11 is 4 because it is the solution to
3x ≡ 1 (mod 11).
• Put another way you are trying to find a number that is coprime to x
mod n.
• The extended Euclidean algorithm may be used to compute it. In fact
this is probably the most common way to compute it.
Extended Euclidean
The extended Euclidean algorithm is a version of the Euclidean
algorithm; its input are two integers a and b and the algorithm
computes their greatest common divisor (GCD) as well as integers x and
y such that ax + by = gcd(a,b). This works because the steps of Euclid's
algorithm always deal with sums of multiples of a and b.
We are going to look first at a video demonstration of this, then at an
example here in this presentation, then at a second and different video
demonstration. The hope is that seeing it done three different times,
should assist you in understanding it. Here is the first video demo
http://www.youtube.com/watch?v=fz1vxq5ts5I very clear, easy to
follow
Extended Euclidean
Consider as an example the computation of gcd(120,23) with Euclid's algorithm:
•
•
•
•
•
120 / 23 = 5 remainder 5
23 / 5 = 4 remainder 3
5 / 3 = 1 remainder 2
3 / 2 = 1 remainder 1
2 / 1 = 2 remainder 0
• In this case, the remainder in the second-to-last line indicates that the gcd is 1; that is,
120 and 23 are coprime.
Extended Euclidean step 2
Now do a little algebra on each of the above lines:
120 / 23 = 5 r 5 => 5 = 120 - 5*23
23 / 5 = 4 r 3 => 3 = 23 - 4*5
5 / 3 = 1 r 2 => 2 = 5 - 1*3
3 / 2 = 1 r 1 => 1 = 3 - 1*2
2 / 1 = 2 r 0 => 0 = 2 - 2*1
Now observe that the first line contains multiples of 120 and 23. Also, the rightmost values are in each case the remainders
listed on the previous line, and the left side of the differences are the residues from two lines up. We can thus
progressively calculate each successive remainder as sums of products of our two original values.
Here we rewrite the second equations in the above table:
5 = 120 - 5*23 = 1*120
- 5*23
3 = 23 - 4*5 = 1*23
- 4*(1*120 - 5*23) = -4*120 + 21*23
2 = 5 - 1*3 = (1*120 - 5*23) - 1*(-4*120 + 21*23) = 5*120 - 26*23
1 = 3 - 1*2 = (-4*120 + 21*23) - 1*(5*120 - 26*23) = -9*120 + 47*23
Notice that the last line says that 1 = -9*120 + 47*23, which is what we wanted: x = -9 and y = 47.
This means that -9 is the multiplicative inverse of 120 modulo 23, because 1 = -9 * 120 (mod 23).
Extended Euclidean step 3
So remember the original formula? ax + by = gcd(a,b). That means in this case b is the modulo, a is
the number you are trying to find the multiplicative inverse for. Here is an example ( too see this
entire example online http://www.fact-index.com/e/ex/extended_euclidean_algorithm.html
Euclid’s Greatest Common Divisor Algorithm
• Since m mod n = m - m/nn, We can now apply statement 4
and statement 3 to see that gcd(m,n) = gcd(m mod n, n) =
gcd(n, m mod n)
5. For integers m and n with n > 0, gcd(m,n) = gcd(n, m mod n).
• We can apply statement 5 to derive an algorithm for computing
- greatest common divisors
• Euclid’s Algorithm:
• Input:
integers m and n, not both zero
Output:
d = gcd(m,n)
• If n == 0
d = |m|
else
while n  0
c=n
n = m mod n
m=c
d=m
return d
Euclid’s Greatest Common Divisor Algorithm
• One of the special properties of the greatest common
divisor of two numbers is that it can be written as an
integer linear combination of the numbers
• Example 2: gcd(32,24) = 8
• 32 = 124 + 8
• Thus 8 = 132 + (-1)24
• Example 3: gcd(54,42)
54 = 142 + 12
42 = 312 + 6
12 = 26 + 0, so 6 = gcd(54,42)
Using back-substitution:
6 = 142 - 312 and 12 = 154 - 142
Thus 6 = 142 - 3(154 - 142 ) = 442 + (-3)54
Euclidean VIDEO Tutorials
• http://www.youtube.com/watch?v=fz1vxq5ts5I very clear, easy to
follow
• http://www.youtube.com/watch?v=shaQZg8bqUM This is a little
longer, but a pretty good one.
Here is another method method
One divided by a given number is the multiplicative inverse of that number. To find the
multiplicative inverse of the number a:
•Find the logarithm for a
•Subtract 255 by a's logarithm
•Take the anti-log of the resulting number
•This is the multiplicative inverse (In other words, 1 / a)
Here is some code which uses the above log and anti-log tables to calculate the multiplicative
inverse: unsigned char gmul_inverse(unsigned char in) {
/* 0 is self inverting */
if(in == 0)
return 0;
else
return atable[(255 - ltable[in])];
}
This example comes from http://www.samiam.org/galois.html
Rijendael step by step- The s-box
• This is the standard s-box
Multiplicative inverse
• The S-box is generated by determining the multiplicative inverse for a
given number in GF(28) = GF(2)[x]/(x8 + x4 + x3 + x + 1), Rijndael's
finite field (zero, which has no inverse, is set to zero). Rijndael uses a
characteristic 2 finite field with 256 elements, which can also be
called the Galois field GF(28). It employs the following reducing
polynomial for multiplication: x8 + x4 + x3 + x + 1.
• The multiplicative inverse is then transformed using the following
affine transformation:
S-box Derivation
The S-box maps byte x to byte z via the function z = Ax-1+b:
Input byte x: x7x6x5x4x3x2x1x0
Compute the inverse in GF(28): y7y6y5y4y3y2y1y0
(use 0 as inverse of 0)
(non-linear, vs. attacks)
Compute this linear function z in GF(28):
(to complicate attacks)
(A is simple to implement)
b chosen so
z  x and z  x
Calculate the multiplicative inverse
• Recall that the multiplicative inverse in a modulo n world is defined as being the
number, a-1, such that
• (a)(a-1) ≡ 1 (mod n)
• Thus, for example, 3 and 7 are multiplicative inverses of each other in a mod 10 world
while 5 and 11 are multiplicative inverses of each other in a mod 27 world.
• For very small moduli, finding the multiplicative inverse of a number is not terribly
difficult to do via exhaustive search since, by definition,
(a)(a-1) = kn + 1
• So it becomes a simple matter of writing this as
(a-1) = (kn + 1)/a
• and trying successive values of k until one is found that results in the right hand side
being an integer. All that is then left is to reduce the resulting integer modulo n. But as
the modulus grows, this process quickly becomes unwieldy and impractical. What is
needed is a more systematic means of finding a-1.
Calculate the multiplicative inverse
We have to find x such that ax ≡ 1 (mod m)
Above equivalence can be stated alternatively as:
ax = pm + 1
or ax + my = 1 known as Bézout’s identity
Table of Multiplicative inverses
Generating the standard S-Box
• The next slides provide this. However if you wish to alter the s-box
you should attempt the following:
• Find a different irreducible polynomial to use as the mod operation.
• Find a different affine transform, that simply means a different matrix to
multiple the multiplicative inverse by. This changes the shifts/operations
you see in the following slides.
Rijendael step by step- The s-box
• This will generate the Rijndael (AES) S-box, which is represented here
with hexadecimal notation:
Rijendael step by step- step one
• Take a number for GF(28) lets pick 2. Looking at the multiplicative
inverse table that gives us 8d in hex or 10001101 in binary
• Now we need to do four iterations of the process of affine
transformation. We start by putting the multiplicative inverse into
two variables s and x:
• s = 10001101
• x = 10001101
Rijendael step by step- step two (first
iteration)
• Rotate s(10001101) to the left = 00011010
•
If the high bit is one make the low bit 1
•
else low bit is 0
Now in this case the high bit WAS 1 so we change the low bit
• so s is 00011011
xor with x so 00011011 xor 10001101= 10010110
s = 00011011 x = 10010110
Rijendael step by step- step three (second
iteration)
•
•
•
•
rotate s (00011011 )to the left = 00110110
If then(shown above) still gives us 00110110
xor with x so 00110110 xor 10010110 = 10100000
s = 00110110 x = 10100000
Rijendael step by step- step four (third
iteration)
•
•
•
•
rotate s(00110110) to the left = 01101100
if then (shown above ) still gives us 01101100
xor with x so 01101100 xor 10100000= 11001100
so s = 01101100 x = 11001100
Rijendael step by step- step five(fourth
iteration)
•
•
•
•
rotate s(01101100) to the left = 11011000
if then (shown above) still gives us 11011000
xor with x so 01101100 xor 11001100= 00010100
so s = 11011000 x = 00010100
Rijendael step by step- step six
• Now x (00010100) gets xor'd with decimal 99 (hex x63 binary
1100011) = 1110111 or 77
And if we check the s-box table for what 2 should give us we get
So what are we seeing?
• The output is actually the multiplicative invers of the input then put
through this affine transform.
• Still not convinced lets see it again?
Rijendael step by step- step one
• Take a number for GF(28) lets pick 7. Looking at the multiplicative
inverse table that gives us d1 in hex or 11010001 in binary
• Now we need to do four iterations of the process of affine
transformation. We start by putting the multiplicative inverse into
two variables s and x:
• s = 11010001
• x = 11010001
Rijendael step by step- step two (first
iteration)
• Rotate s(11010001) to the left = 10100010
•
If the high bit is one make the low bit 1
•
else low bit is 0
Now in this case the high bit WAS 1 so we change the low bit
• so s is 10100011
xor with x so 10100011 xor 11010001 = 1110010
s = 10100011 x = 1110010
Rijendael step by step- step three (second
iteration)
•
rotate s(10100011) to the left = 01000110
•
If then(shown above)
• gives us 01000111
•
xor with x so 01000111 xor 1110010 = 00110101
•
s = 01000111 x = 00110101
Rijendael step by step- step four (third
iteration)
•
•
•
•
rotate s(01000111) to the left = 10001110
if then (shown above ) still gives us 10001110
xor with x so 10001110 xor 00110101 = 10111011
so s = 10001110 x = 10111011
Rijendael step by step- step five(fourth
iteration)
•
rotate s(10001110) to the left = 00011100
•
if then (shown above)
• gives us 00011101
•
xor with x so 00011101 xor 10111011 = 10100110
•
so s = 00011101 x = 10100110
Rijendael step by step- step six
• Now x (10100110) gets xor'd with decimal 99 (hex x63 binary
1100011) = 11000101 or c5
And if we check the s-box table for what 7 should give us we get
That is IT!!
• That is how you generate the entire Rijndael s box!
• Is this clearer? Well lets reiterate the basics:
1. Use GF(28) and look at each possible value in that filed one at a
time.
2. Find the multiplicative inverse, then compute the transform.
3. That takes four steps, and gives us the output for the s box
But wait…
• What was the matrix we saw earlier? Well that is an alternative way
to do this. You can put all the GF(28) values in a matrix, and use the
matrix we saw to produce the multiplicative inverse of the GF(28)
matrix…OR you can use the formula we just did!
• What does this mean? Well either method works, but I think you will
find the formula method easier to code in any programming language
and easier to alter.
Alter it? How
• Some obvious solutions come into play
• What about different shifts? Left or right, or by more than one? Will that
affect the output?
• Of course a different value of GF(28) perhaps GF(29) for 512 bits?
• Perhaps building this output table (this s box) then xoring it with the round
key so there is a different s-box each round? And it is semi key dependent?
• Of course you could construct an entirely different affine transform.
How to change an AES s-box
• Remember you want the entire cipher to meet
• Strict Avalanche Criteria
• Bit independence criteria
• Balance
• As much as possible the s-box should fulfill this. So when making any
change, we know that we must make certain our change meets these
criteria
So what changes can we make
• Isomorphic fields to the underlying field can be generated by using different
irreducible polynomials of the same degree. There are a total of 30 irreducible
polynomials of degree 8 to choose from. This gives you 29 alternatives to the
traditional s-box for AES, each with well tested security. (note for more details
you can look into Rabin’s test for irreducibility).
• Change the affine transform. This is a little more tricky but safe if you simply alter
parameters within the existing transform. Section 5.2 of “ Algebraic Construction
and Cryptographic Properties of Rijndael Substitution” discusses this in detail.
• Change the translation vector (the final number you xor with). Obviously there
are 255 possible variations.
Comments on changing the affine transform
• “We propose to increase the complexity and security of AES S-box by
modifying the affine transformation and adding an affine
transformation”
• -AN IMPROVED AES S-BOX AND ITS PERFORMANCE ANALYSIS
“improved AES s-box performance.pdf”