In the previous video we looked at the specification of as
algorithm and detailed the
steps that compose each of its rounds.
We saw that mixed columns and adron key
steps involve some arithmetic at the
bite level.
In this video, we'll clarify this arithmetic.
They would be some mathematics over polynomials, but no worries.
We'll go through it step by step and we'll see
together plenty of examples.
We all use arithmetic in our daily life
when we manage our money or when we
do shopping for example.
These arithmetic involves real numbers and operations
like addition subtraction multiplication
or division.
That we or our calculator or our
Excel sheet apply over these numbers.
As inventors Richmond and Daemon use another
type of arithmetic for the bytes.
These arithmetic is a bit different from the usual arithmetic
over real numbers. It is called
arithmetic over finite fields.
Let's see its properties first before seeing
how it works.
Three numbers is infinite. And this
is the first major difference with finite fields.
The set of elements in finite Fields is finite.
And gf2 to
the power of 8, which is one instance of finite Fields
is composed of two to the
power of 8 elements.
2 to the power of 8 is 256 which
exactly corresponds to the number of values
that byte can take
finite Fields have special property that
operations such as addition subtraction
multiplication or division.
On elements always cause the result to remain
in that fit.
So when we add multiply elements in
gf228.
the result remains in gf228
Which is exactly what we want when doing arithmetic on
bytes.
We don't want when we add two bytes to obtain a value
that cannot be represented on a bite and can only be
represented on 16-bit Word.
If this was not the case would have to worry about
overflow problems.
So the fact that we have the finite set
of numbers.
and the properties that
the operations
provide us members that remain in
the same field are the two interesting properties of
finite fields.
Let's see how we map the bytes to these
elements of gf228.
A bite B can be represented as a
bit string as you see here. We have
8 Bits going from B7 to b0.
in gf28
this bit string is a represented as
a polynomial.
with binary coefficients
this B7 B6 Etc all the way
to be zeros.
And each of these B can
take the value 0 or 1 exactly like
a bit.
So for example
5A is written as the
speed string 0 1 0 1
1 0 1 0.
it will be mapped to the following polynomial 0x7
plus 1 x 6
plus 0x5 plus 1 x 4
plus 1 x 3 plus 0 x 2 plus
1 X plus u
the monomials with zero coefficients can
be removed.
So this polynomial is exactly corresponds
to this.
polynomial X6 plus X4 plus X3
plus X
We provide two more examples.
Feel free to stop the video and take your time to
check each of them.
Each polynomial in gf28 is
of degree at most 7.
For example the polynomial corresponding to
the value FF is exactly of
degree 7.
As its largest non-zero monomial is X7.
while the polynomial corresponding to
the value to C is of degree 5 as
you see we don't have coefficients for
X6 and X7
There is no purpose from defining the real
numbers if we don't Define how to
add.
multiply subtract or divide
them
Similarly, we need to Define how to do arithmetic
operations for the gf28
elements.
Let's start with addition.
to add elements in gf28
we do addition of the polynomials.
And then in the result, we replace every two
by zero.
Why because as we said in the previous slide in
element of gf28 is polynomial with
binary coefficients.
So coefficients take either 0 or
1 so we cannot have value 2
so we will replace it with zero.
Because 2 and 0 have the same parity.
Let's see an example of how we do
addition.
So we'll take the previous bytes.
The previous values that we have seen 5A and
2C.
So these are their corresponding polynomials.
So to do the addition we need just need to add the
polynomials. So the polynomial corresponding to
the
To the addition is the following X6 plus
X5.
Let's X4 plus 2 X 3 because each
of 5A and
to CL has X3 plus X2.
plus X
and as we said the two will be
replaced by 0. So the monomial will
disappear from the result. So the result
is then is the
following polynomial X6 plus
X5 plus X4 plus X2 plus
X.
This is corresponding to the following bit string
0 1 1.
0 1 1 0 which corresponds
to the value 76 so
5A plus 2C is
equal to 76.
you might have noticed that actually this addition in gf28 is
actually actually just a bitwise xor
because when we xor we do it component
wise like for polynomials.
and also for xor
one xor 1 gives you which is
exactly what we have done here by replacing the
two is you
So you can check here on the xor operation.
that the addition in gf28 is simply in xor
let's now move to multiplication.
To multiply in gf228. We multiply
the polynomials.
Then we do reduction module polynomial of
degree 8 the following degree 8
polynomial X8 plus X4
plus X3 plus X Plus
1.
This reduction is what gives us the interesting property that
we have seen when we introduce the finite fields.
Which is that the result always remain in
the field?
What does it mean reduction module or
another polynomial?
It means that whenever we obtain a polynomial
of degree strictly larger than 7
for example polynomial of degree 8 or 9. We have
to reduce it by this degree 8
polynomial.
To bring it back of degree at
most 7, so it is still representable in
gf28.
Let's see some examples to clarify this idea.
We start with the trivial example of multiplying
with the byte 00.
So we have again our byte 5A and
we will multiply it with a byte 00. So this
is the polynomial of 5A when we multiply
with a polynomial zero. We obtain the
polynomial zero so multiplication of
the byte 5A by the by 0 0 gives
the byte 0 0
the next trivial example is multiplication with
a byte01.
So when we multiply with the byteser 1
we will multiply actually the polynomial with
the polynomial one.
Which gives us exactly the same polynomial X6
plus X4 plus X3
plus X.
These polynomial is of degree 6, so
it does not require a reduction so we are
done.
So the result of the multiplication of the byte
5A with the by Tier 1 is the
same byte 5A.
We will skip the multiplication is zero two and
zero three on purpose because they're very similar
to the multiplication with zero one.
the respective results remain small of
degree
less than 8 and do not need
to be reduced.
You can double check that by doing the multiplication by
yourself.
However, things get interesting when we multiply
with the value 0 4.
Okay, so
After multiplying with X2 which corresponds
to the byte04. We obtain
a polynomial of degree 8
the following X8 plus X6 plus
X5 plus X3.
So now we need to do a reduction module this
polynomial here.
the trick is that
to perform this reduction. We just need to replace X8.
the monomial X8 by the following polynomial X4
plus X3 plus X Plus 1
So we just need to plug that into our result
polynomial.
So we replace the X8 with this polynomial.
And we keep the the other monomials
of multiplication.
And now we obtain the following polynomial X6 plus
X5 plus 2 x 3.
plus X4 plus X Plus 1
as usual the two needs to be replaced by
0. So this monomial this monomial would
disappear and we obtain X6 plus X5 plus
X4 plus X Plus 1 which corresponds to
the bit string 0 1 1
0 0 1 1
which is the value 73 in
bytes, so the byte 5a multiplied
by the byte04 gives the byte
73
you might be saying okay this time we could
solve it as we obtained the monomial X8
after the product.
But what if we obtain the monomial X9 or
another larger?
See for X9 first and then you will
get the mechanic of doing it.
Actually X9.
can be written as X8 times x
and as we said the X8 can be
replaced with X4 plus X3 plus X Plus
1. So we just need to plug X8 here.
And this gives us following polynomial X5
plus X4 plus X2 plus
X.
So whenever we see X9, we just need
to replace it with the following polynomial.
And similarly we can obtain expressions for
extend X11 Etc.
So, let's see an example when we will multiply
the byte 5A with a byte 08.
We have the following polynomials X6
plus X4 plus X3 plus
X multiplied by X3.
Which gives us X9 plus X7 plus
X6 plus X4.
We replace X9 with its.
Corresponding polynomial X5 plus X4 plus
X2 plus X and we keep the previous
monobles.
And we replace the two which gives
us the following final polynomial X7
plus X6 plus X5 plus
X2 plus X.
Which corresponds to the value E6 so
5A times zero eight gives
E6.
We have seen in this video how we can
do addition and multiplication in gf28.
In the same way we Define the addition we can
Define subtraction and in the same
way we Define multiplication we can also Define
division.
finite fields are not only used in as
they are the Cornerstone of constructing the arithmetic
needed in many cryptographic algorithms.
Due to their interesting property that any operation performed
with elements returns an element contained
in the original set.
They're also very efficient to implement both in
hardware and software.
And they can be easily customized to the need of your Construction.
For example, we have seen gf28 to do arithmetic with
bytes. We can also have gf24 to
do arithmetic with nibbles. So a bit
strings of four bits or with a
larger GF to represent.
larger bit shrinks
we reach the end of this section.
We describe several aspects of symmetric key
cryptography from the protocol all the
way to the underlying arithmetic.
So far we focused on confidentiality.
On the next section, we will continue with the symmetric
key cryptography, but we look at how we
can achieve integrity and Authentication.
So see you in the next section.