|| Author: Cyberdude || Back to articles ||
Author: Ferraro Giuseppe aka Cyberdude
Mailto: viromarquantbello[at]libero[dot]it
Date : December 2006
Modulate Arithmetic + Galois Field finished space base knowledges and use of their for AES ciphrature
------------------------------------------------------------------------------------------------------
[0x0] Base Knowledge about Modulate Arithmetic
[0x1] Euclide's Greatest common divisor algorithm and asm implementation
[0x2] The Modulate Polinomial Arithmetic in the Galois Field form GF(p^n)
[0x3] The Rijndael Advanced Encryption Standard ciphrature's structure introduction
[0x3x1] The subphases of a single encryption phase
[0x3x2] The Aes key's expansion from 4 to 44 words procedure
----------------------------------------------------[ 0x0 - Base Knowledge about Modulate Arithmetic ]
If I have an integer 'n' and another integer 'a' that we can imangine n = 3 and a = 7, if I divide a/n
I obtain another integer that I can call 'q' and another integer that I can call 'r'. This 4 integer
have the next relaction : a/n = q+r, if I want do an exemple I can say that 7/3 = 2+1 since 3 * 2 = 6
and 6+1 = 7. If I want write the operation that I did, I can write in this way 7mod3 = 1. The value
'mod' rapresents the value r that remain when I divide 7/3. Now I do another exemple so all people can
understend this simple concept:
How I can obtain 10mod3?? I must multiply 3 for several time while I can't obtain the value 10 ora a
value that is approaching to 10. So I have that
3*1 = 3 that is < 10
3*2 = 6 that is < 10
3*3 = 9 that is < 10
3*4 = 12 that is > 10
since 3*4 is 12 and 12 is > 10 I must return to 3*3 = 9. Since 9+1 = 10 I have that 10mod3 = 1!For the
same motive I have that
+5 mod 2 = 1
+15 mod 12 = 3
+20 mod 5 = 0
-11 mod 7 = since I have -11 I take you an exemple how to resolve it :
7 * -1 = -7 that is > -11
7 * -2 = -14 that is < -11
since -14 is the first value < -11 I have found my mod since -14 + 3 = -11!! So -11 mod 7 = 3. In the
same way I can say that -10 mod 5 = 0 since 5 * -2 = -10
An interesting caracteristic of the modulate arithmetic is that if I have an operation as the next:
[(11mod8) + (15mod8)]mod8 I can resolve it in this way:
11 mod 8 = 3
15 mod 8 = 7
(3+7) = 10
since he want that the result of this sum is calcoulated in mod 8 I have that 10mod8 = 2 and in this
case the result of this operation is 2 but is possible that I have an operation between differents mod
for exemple the same operation [(11mod8) + (15mod8)]mod8 have a different result if I change only a
single one mod, so if I want obtain the result of [(11mod7) + (15mod8)]mod8 I have that:
11 mod 7 = 4
15 mod 8 = 7
and the sum between 4 and 7 is 11 and 11mod8 is 3 and not 2.
After that I have explain it to you we can return at the case in witch several operations are execute
with the same mod, so we return to consider this : [(11mod8) + (15mod8)]mod8. If I want resolte this
operation is not necessary that I do 11mod8 and 15mod8 but I can do (11+15)mod8 and the result is the
same that we have seid in the first time since 26mod8 = 8*3 =24 and 24+2=26 so 26mod8 = 2. In general
we have that:
[(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 = (a*b)mod n
When we work in modulate arithmetic we work with a limitate group of integer. To explain this concept
I report you an exeple: if I work in mod8 all value that I can obtain are all value x where 0<=x<8, in
generale when we work in mod n we have a group of x value where 0<=x<n, but return at the case where
we work in mod 8 and try to calcoulate the big number mod 8 to control if we obtain results >=8 :
1 mod 8 = 8*0 + 1 and 0 + 1 = 1 so 1 mod 8 = 1
2 mod 8 = 8*0 = 0 and 0 + 2 = 2 so 2 mod 8 = 2
10 mod 8 = 8*1 = 8 and 8 + 2 = 10 so 10 mod 8 = 2
15 mod 8 = 8*1 = 8 and 8 + 7 = 15 so 15 mod 8 = 7
30 mod 8 = 8*3 = 24 and 24 + 6 = 30 so 30 mod 8 = 6
32 mod 8 = 8*4 = 32 and 32 + 0 = 32 so 32 mod 8 = 0
51 mod 8 = 8*6 = 48 and 48 + 3 = 51 so 51 mod 8 = 3
as you can say the min value that we have obtenuted is 0 and the max is 7 since we consider a modulate
arithmetic in 8.
We can obtain several class of value for all mod n that we want. To explain this concept I consider an
exemple in witch I use a mod4 arithmetic. As we have seid in the prev strings, since we work in mod4
we can obtain only 4 different results and this possible results are = 0 1 2 and 3. If I want create a
class in witch are there all value that in mod4 return the result 0 I must do a simple operation as
showed next :
[0] = 0 + 04 + 04 + 04 + 04 + 04 ...
[0] = 0 04 08 12 16 20 ...
and
[0] = ... - 04 - 04 - 04 - 04 - 04 - 0
[0] = ... -20 -16 -12 -08 -04 0
so for the result = 0 we have this class :
[0] = { ... -20 -16 -12 -8 -4 0 4 8 12 16 20 ... }
And if you try
0mod4, 4mod4, -4mod4, 8mod4, -8mod4, 12mod4, -12mod4, 16mod4, -16mod4 etc, the result is the same and
in this case is 0. In the same way we can obtain the classo of resuts [1] [2] and [3].
[0] = { ... -20 -16 -12 -8 -4 0 4 8 12 16 20 ... }
[1] = { ... -19 -15 -11 -7 -3 1 5 9 13 17 21 ... }
[2] = { ... -18 -14 -10 -6 -2 2 6 10 14 18 22 ... }
[3] = { ... -17 -13 -9 -5 -1 3 7 11 15 19 23 ... }
After that we can create several tables that show the resoutls of several operation in mod n. Imagine
that we want obtain the table of results of addition operation in mod 8, we know that in mod 8 we have
8 possible value: 0,1,2,3,4,5,6,7 so we can create our table in this way:
+|0|1|2|3|4|5|6|7|
-----------------
0| | | | | | | | |
1| | | | | | | | |
2| | | | | | | | |
3| | | | | | | | |
4| | | | | | | | |
5| | | | | | | | |
6| | | | | | | | |
7| | | | | | | | |
We know that (0+0)mod8 = 0 and (0+1)mod8 = 1 and (0+2)mod8 = 2 etc so the first row is rapresentated
by the succession 0 1 2 3 4 5 6 7 as showed next and the other rows are very similar to it
+|0|1|2|3|4|5|6|7|
-----------------
0|0|1|2|3|4|5|6|7|
1|1|2|3|4|5|6|7|0|
2|2|3|4|5|6|7|0|1|
3|3|4|5|6|7|0|1|2|
4|4|5|6|7|0|1|2|3|
5|5|6|7|0|1|2|3|4|
6|6|7|0|1|2|3|4|5|
7|7|0|1|2|3|4|5|6|
In the same way we can rapresent the table of multiplication:
x|0|1|2|3|4|5|6|7|
-----------------
0|0|0|0|0|0|0|0|0|
1|0|1|2|3|4|5|6|7|
2|0|2|4|6|0|2|4|6|
3|0|3|6|1|4|7|2|5|
4|0|4|0|4|0|4|0|4|
5|0|5|2|7|4|1|6|3|
6|0|6|4|2|0|6|4|2|
7|0|7|6|5|4|3|2|1|
If we read the table showed up, we can say an important particoular :
(6x3) mod 8 = 2 since 6x3 = 18 and 18 = 8*2 = 16 + [2] = 18
but
(6x7) mod 8 = 2 too since 6x7 = 42 and 8*5 = 40 + [2] = 42
but 3mod8 is different from 7mod8, 3mod8 is 3 and 7mod8 is 7. The "problem" stay in the number 6 since
when we do a multiplication operation with a generic number x (in our exemple x is 6) if x have one or
several factor equals with the mod number (in our case 8) the 'r' values (the results of module) can
obtain the same result for differents value. To understend this concept you can read the next exemple:
We consider the mod8 and the number 6; 8 and 6 have the value 2 in their factor since 8:2 is possible
and 6:2 is possible, this particoular is the cause of this :
mod 8 value : 00 01 02 03 04 05 06 07
number 6 multiply : 00 06 12 18 24 30 36 42
results of mod : 00 06 04 02 00 06 04 02
As we can see in the exemple (6x2)mod8 and (6x5)mod8 have as result 6 but 2mod8 = 2 and 5mod8 = 5!! If
we consider the value 5 and not 6, we obtain 8 different results for the first 8 multiply of 5 since
the number 8 and the number 5 have all factor different; 8 is divisible for 2 for 4 and for 8, 5 is
divisible only fo 5 (the value 1 is not considered). If we try to repeat the same operation that we
have execute for the value 6 we obtain this
mod 8 value : 00 01 02 03 04 05 06 07
number 5 multiply : 00 05 10 15 20 25 30 35
results of mod : 00 05 02 07 04 01 06 03
As we can see everyone result of the multiplication of 5 with the first 8 value < of 8 in mod 8 is
no like everyone of the others result.
--------------------------[ 0x1 - Euclide's Greatest common divisor algorithm and asm implementation ]
An interesting use of the modulate arithmetic is rapresentated by the Euclide's Algorithm. Euclide use
the mod arithmetic to obtain the Greatest common divisor between two number, if you don't know what is
the greatest common divisor (that now we name as gcd) i do a little exemple. If I have two number, for
exemple 24 and 18 I can say that the gcd between 24 and 18 is 6 becouse :
24 : 2 = 12 | 18 : 2 = 9
12 : 2 = 6 | 9 : 3 = 3
6 : 2 = 3 | 3 : 3 = 1
3 : 3 = 1 |
so I can say that:
-> 24 = 2 * 2 * 2 * 3
-> 18 = 2 * 3 * 3
the factor that 24 and 18 have in common are only 2*3 = 6 so... I can divide 24:6 and 18:6 and 6 is
the gcd between 24 and 18. If I have the value 24/18 I know that the maximum semplification of it is:
4/3 that is 24/6 = 4 and 18/6 = 3.
To obtain this gcd Euclide use a modulate arithmetic, in particoular, when we have two number, for
exemple 55 and 22 the algorithm find the max between they (in this case 55) and do:
=> minValue mod (maxValue mod minValue)
and repeat this operation while the minValue is different from 0 or while the two value are the same.
To understend this operation we can try to solve the gcd between 55 and 22 as showed in this
procedure:
phase[1] max = 55 min = 22 -> 22 mod (55mod22) -> 22mod(11)
phase[2] max = 22 min = 11 -> 11 mod (22mod11) -> 11mod(11)
phase[3] max == min -> gcd = 11
The pseudocode of the Euclide algorithm used to find the gcd using the modulate arithmetic is this:
EUCLIDE(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
I have implementated it in assembler AT&T and I have thinked the next implementation but everyone can
try to implmenet it as he want and using the lenguage that he preferred:
The Code structure that I have thinked is composit of three principal function and everyone function
have several procedure, the most important is the main procedure that is the function runned when the
process started. The procedure module is the procude that apply the modulate arithmetic (that in the
pseudocode we have named gcd between a and b) and the control procedure is used to transform negativ
value (for exemple -3) in positiv (in this case 3). This control procedure is correct becouse the two
number that are gived in input by the user can be positiv or negativ but the algorithm consider the
absolute value of they since gcd(60,24) == gcd(60,-24) == 12.
[ module ] [ control ] [ main ]
|_[module] |_[control] |_[main]
|_[execute] |_[change] |_[takeValues]
|_[compare] |_[returnValue] |_[controlValues]
|_[findMax]
|_[isLessThan]
|_[areEquals]
|_[continue]
|_[while]
|_[printgcd]
|_[quit]
When the asm binary compiled code is runned the main procedure is called.
[main]-->[takeValues]
|
--> the user insert value 1 ---
--> the user insert value 2 -- |
||
\/
[controlValues]-->[control]
| |
V V
(else)<--(if value 1 or value 1 is < 0)
| |
(the two values are positiv)<---------- | |
| V |
[returnValue]<--[change]<--|
| |
| --------->(transform -3 to 3)
V
-----------------------(now we have 2 positiv values)
|
| |--->(excange the position of value 1 and value 2)
V |
[findMax]-->(if value 1 is < value 2)-->[isLessThan]-->(now I have value 1 > value 2)
| |
| |--->(print one of their) |
V | |
(else if are Equals)-->[printgcd]-->[quit] |
| | -->(start the while procedure)
V V |
(else)--------------------------------------->[while]-->(if is finished)
^ | |
| | |
------------------------- | |
| | |
| -----------------(else)<--| |
| | V
| V [printgcd]
| [module] |
| | V
| V [quit]
| [compare]-----
| | |
| V -->(control if the values are different)
-----[execute]
|
---> (calcoulate the module)
------[ Euclide.s - compile it using gcc Euclide.s ]--------------------------------------------------
------------------------------CUT HERE----------------------------------------------------------------
caption: .string "[ Euclide's Greatest common divisor algorithm - asm implementation ]"
value1: .string "\t[I]nsert the first value: "
value2: .string "\t[I]nsert the second value: "
input: .string "%d"
gcd: .string "\n --> GCD = %d\n"
.globl module
module:
pushl %ebp /* Here I alloc the space that I use */
movl %esp, %ebp /* in the my function named module! */
subl $16, %esp
movl $0, -8(%ebp) /* Now I store the value 0 in -8(%ebp) */
movl 12(%ebp), %eax /* and take the value stored in 12(%ebp) */
movl %eax, -4(%ebp) /* and move it in %eax after I move this */
jmp compare /* value in -4(%ebp) and jump to compare */
execute:
movl -8(%ebp), %eax /* Here I move the value stored in -8(%ebp) */
imull -4(%ebp), %eax /* in %eax and multiply it with the value in */
movl %eax, 12(%ebp) /* -4(%ebp), the result is stored in 12(%ebp)*/
leal -8(%ebp), %eax /* After that leal the space from -8(%ebp) in %eax*/
addl $1, (%eax) /* And increment the counter (stored in -8(%ebp)*/
compare:
movl 12(%ebp), %eax /* Here I take another time the value */
cmpl 8(%ebp), %eax /* stored in 12(%ebp) and compare it with */
jl execute /* 8(%ebp), if the value in 12(%ebp) is < */
/* of the value in 8(%ebp) I jump to execute */
/* procedure */
leal -8(%ebp), %eax /* If it isn't < of 8(%ebp) I leal the counter */
subl $2, (%eax) /* and decrement it of 2 integer */
movl -4(%ebp), %eax /* After move the value stored in -4(%ebp) in %eax*/
imull -8(%ebp), %eax /* And multiply it with the value stored in -8(%ebp)*/
movl %eax, 12(%ebp) /* Store the result in 12(%ebp) and move it in %edx*/
movl 12(%ebp), %edx /* After move 8(%ebp) in %eax and do a subtraction */
movl 8(%ebp), %eax /* After that return the value that is the result*/
subl %edx, %eax /* of subtraction operation and here end the module */
leave /* method */
ret
.globl control
control:
pushl %ebp /* Here I alloc the space that I will use in */
movl %esp, %ebp /* the control method */
subl $4, %esp
cmpl $0, 8(%ebp) /* After that I compare the value 0 with the */
jle change /* value stored in 8(%ebp) and if it is <0 I */
/* jump to change procedure */
movl 8(%ebp), %eax /* Else I move the value stored in 8(%ebp) in %eax */
movl %eax, -4(%ebp) /* And move this value in -4(%ebp) becouse this is */
jmp returnValue /* the value that the returnValue procedure must return */
change:
movl 8(%ebp), %eax /* Here I move the 8(%ebp) value in %eax and */
negl %eax /* do -(value) so if the value is -10 I do -(-10)*/
movl %eax, -4(%ebp) /* that is 10 and move the result in -4(%ebp) */
returnValue:
movl -4(%ebp), %eax /* After that move this value in %eax and return */
leave /* it to the main function */
ret
.globl main
main:
pushl %ebp /* In the first time I alloc the space that I use */
movl %esp, %ebp /* in the main procedure */
subl $56, %esp
pushl $caption /* After that push the string caption in (%esp) */
call puts /* and print it to screen */
pushl $value1 /* Now print the string value1 */
call printf
takeValues:
leal -16(%ebp), %eax /* leal -16(%ebp) in %eax and push this space */
pushl %eax /* in the stack, after push the pointer to int */
pushl $input /* And receiv the first input from the user */
call scanf /* with the printf procedure */
pushl $value2 /* Here I do the same that I do in the first time */
call printf /* with the value1 string, here I obtain the value */
/* of the second integer */
leal -20(%ebp), %eax
pushl %eax
pushl $input
call scanf
controlValues:
movl -16(%ebp), %eax /* Now I move the first value obtenuted in %eax */
pushl %eax /* and take it in input to the control procedure */
call control
movl %eax, -16(%ebp) /* I refresh the value stored in -16(%ebp) with the */
/* output of the control procedure */
movl -20(%ebp), %eax /* Here I do the same with the second value */
pushl %eax
call control
movl %eax, -20(%ebp)
findMax:
movl -16(%ebp), %edx /* Now I move the two values in %edx and %eax */
movl -20(%ebp), %eax /* And if -20(%ebp) is <= of -16(%ebp) i jump */
cmpl %eax, %edx /* to the isLessThan procedure */
jle isLessThan
movl -16(%ebp), %eax /* Else I move the value stored in -16(%ebp) and */
movl %eax, -12(%ebp) /* -20(%ebp) in -12(%ebp) and -8(%ebp) a copy of */
movl -20(%ebp), %eax /* the two value and jump to the while procedure */
movl %eax, -8(%ebp)
jmp while
isLessThan:
movl -20(%ebp), %edx /* Here I compare the two values to know if */
movl -16(%ebp), %eax /* are different or equals, if they are equals */
cmpl %eax, %edx /* I jump to the areEquals procedure */
jle areEquals
movl -20(%ebp), %eax /* Else if are different I move the two values in */
movl %eax, -12(%ebp) /* -12(%ebp) and -8(%ebp), two copy of this value */
movl -16(%ebp), %eax /* and jump to the while procedure*/
movl %eax, -8(%ebp)
jmp while
areEquals:
movl -16(%ebp), %eax /* If the two values are the same I move one of they */
pushl %eax /* in %eax so i push it in (%esp) stack and push the */
pushl $gcd /* gcd string too and call the printf procedure */
call printf
movl $0, -36(%ebp) /* After that move che value 0 in -36(%ebp) and call */
jmp quit /* the quit procedure*/
continue:
movl -8(%ebp), %eax /* Here I push the two values and jump to the module */
pushl %eax /* procedure to obtain the mod about the two values */
movl -12(%ebp), %eax
pushl %eax
call module
movl %eax, -4(%ebp) /* I store the restults of this module procedure */
movl -8(%ebp), %eax /* -4(%ebp) to refresh his value, after refresh the */
movl %eax, -12(%ebp) /* value stored in -12(%ebp) and in -8(%ebp) */
movl -4(%ebp), %eax
movl %eax, -8(%ebp)
while:
cmpl $0, -8(%ebp) /* In this procedure I compare the value stored in */
jle printgcd /* -8(%ebp) with the value 0 and if it is <0 jump */
/* to the printgcd procedure */
movl -8(%ebp), %eax /* else compare the two values and jump to continue */
cmpl -12(%ebp), %eax
jl continue
printgcd:
movl -16(%ebp), %eax /* Here I push the two value in the stack and call */
movl -12(%ebp), %edx /* the module procedure to obtain a mod between the */
pushl %edx /* two values */
pushl %eax
call module
pushl %eax /* Push the result of this module in the stack and */
pushl $gcd /* push the gcd string too so call the printf */
call printf
movl $0, -36(%ebp) /* After set to 0 the value storedi in -36(%ebp) */
quit:
movl -36(%ebp), %eax /* I Move this value in -36(%ebp) in %eax and call */
leave /* the return(0) procedure to exit */
ret
------------------------------CUT HERE----------------------------------------------------------------
-------------------------[ 0x2 - The Modulate Polinomial Arithmetic in the Galois Field form GF(p^n) ]
A very important arithmetich used in the encryption study is the modulate polinomial arithmetic. This
particoular arithmetic lets to obtain the same number of number different from 0 in a finished
modulate space. You can understend this concept in the second time, for the moment I continue.The poly
arithmetic consist in a polinomial rapresentation of binary values and several operation between there
We can imagine that want obtain the table of addition and moultiplication value in a modulate 8 space.
So all my values must be rapresentated mod8. A normal modulate table can be this:
+ [0][1][2][3][4][5][6][7]
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
we can insert a value in this table as we have seed in the prev paragraphe, for exemple 7+7 = 14 and
we know that 14mod8 = 8*1 = 8 + [6] = 14 so 14mod8=6... if we apply this modulate 8 arithmetic to all
values we obtain this table:
+ [0][1][2][3][4][5][6][7]
[0][0][1][2][3][4][5][6][7]
[1][1][2][3][4][5][6][7][0]
[2][2][3][4][5][6][7][0][1]
[3][3][4][5][6][7][0][1][2]
[4][4][5][6][7][0][1][2][3]
[5][5][6][7][0][1][2][3][4]
[6][6][7][0][1][2][3][4][5]
[7][7][0][1][2][3][4][5][6]
For the moultiplication table is the same 7x7 = 49 and 49mod8 = 1, so the moultiplication table in
mod8 is showed next
x [0][1][2][3][4][5][6][7]
[0][0][0][0][0][0][0][0][0]
[1][0][1][2][3][4][5][6][7]
[2][0][2][4][6][0][2][4][6]
[3][0][3][6][1][4][7][2][5]
[4][0][4][0][4][0][4][0][4]
[5][0][5][2][7][4][1][6][3]
[6][0][6][4][2][0][6][4][2]
[7][0][7][6][5][4][3][2][1]
At this point you can understand the concept that I have explained first, as you can see the odds
columns contains all value of mod8, the evens repeat several times the same value, for exemple the row
1 contain this values: [0][1][2][3][4][5][6][7] and the row 2 contain this: [0][2][4][6][0][2][4][6]
We can see that in the row number 2 there aren't the value 1 3 5 and 7 but are repetuted several times
0 2 4 and 6. The same happened for all evens rows. As I have seid in the first time the modulate
arithmetic polinomial in GF(2^n) solve this problem. In the first time all value are interpreted in
binary form, this form is used to convert the value in polynomial form. The next table show all values
that I can obtain usign 3 bit (since I have used a mod(8) in my prev exemple)
=> 000 = 0
=> 001 = 1
=> 010 = 2
=> 011 = 3
=> 100 = 4
=> 101 = 5
=> 110 = 6
=> 111 = 7
As you can see with 3 bits I obtain all values that belongs to mod(8) finished space since the binary
arithmetic is an arithmetic that use a base = 2 and 2^3 = 8. After that we can rapresents the binary
values in polinomial form, this "transformation" is very simple as showed next:
=> 000 = 0(x^2)+0(x^1)+0 = 0 = 0
=> 001 = 0(x^2)+0(x^1)+1 = 1 = 1
=> 010 = 0(x^2)+1(x^1)+1 = x = 2
=> 011 = 0(x^2)+1(x^1)+1 = x+1 = 3
=> 100 = 1(x^2)+0(x^1)+0 = x^2 = 4
=> 101 = 1(x^2)+0(x^1)+1 = x^2+1 = 5
=> 110 = 1(x^2)+1(x^1)+0 = x^2+x = 6
=> 111 = 1(x^2)+1(x^1)+1 = x^2+x+1 = 7
After that we have obtenuted the polynomial values of a bin rapresentation of mod(8) numbers we can
use they to operate addition, moultiplication and division operations that will be used in several
encryption algorithms.
The sum operation: Imagine that we want do
operation : 7 + 4
binary form : (111) + (100)
poly form : (x^2+x+1) + (x^2)
execution : x^2+x+1+x^2 (the same values are deleted) : x+1 = 011 = 3
result : 3
The mul operation: Imagine that we want do
operation : 7 * 4
binary form : (111) * (100)
poly form : (x^2+x+1) * (x^2)
execution : we must sum the exponents : x^4 + x^3 + x^2 = 11100 = 28
result : 28
The div operation: (for this exemple we use other numbers since 4/7 is very simple)
operation : 11 / 16
binary form : (1011) / (10000)
poly form : (x^3+x+1) / (x^4)
execution : In the first time I must "transform" the x^3+x+1 equals to the max value of 16 (in this
case I must transform x^3+x+1 to x^4 so I can multiply all exepression x^3+x+1 for x and
obtain x^4+x^2+x)
x^4 == 16
x^4 + x^2 + x == my x^3+x+1 trasformed
-------------- I must remove the same values
// + x^2 + x = 110 = 6
result : 6
Don't warry if in your mathematic 11 / 16 is different from 6 becouse this is another mathematic :p
After that I have showed you as you can solve elementary operation of addition moultiplication and
division we can calcoulate out table in GF(2^n) that since first we have calcoulated in mod(8) now we
must work on GF(2^3) finished space.
The addition table
+ [0][1][2][3][4][5][6][7]
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
in GF(2^3) is this :
+ [0][1][2][3][4][5][6][7]
[0][0][1][2][3][4][5][6][7]
[1][1][0][3][2][5][4][7][6]
[2][2][3][0][1][6][7][4][5]
[3][3][2][1][0][7][6][5][4]
[4][4][5][6][7][0][1][2][3]
[5][5][4][7][6][1][0][3][2]
[6][6][7][4][5][2][3][0][1]
[7][7][6][5][4][3][2][1][0]
You can calcoulate it as showed first, for exemple 6+2 = 110 + 010 = (x^2+x)+(x) = x^2 = 100 = 4
The moultiplication table is this:
x [0][1][2][3][4][5][6][7]
[0][0][0][0][0][0][0][0][0]
[1][0][1][2][3][4][5][6][7]
[2][0][2][4][6][3][1][7][5]
[3][0][3][6][5][7][4][1][2]
[4][0][4][3][7][6][2][5][1]
[5][0][5][1][4][2][7][3][6]
[6][0][6][7][1][5][3][2][4]
[7][0][7][5][2][1][6][4][3]
To obtain this values you must apply the moultiplication operation first and, if the resoult value is
greater than 7 (since we are working in mod(8) the values that we can accept are only 0,1,2,3,4,5,6,7)
you must divide this value with the poly x^3+x+1 that is a irriducible polinomy of grade 3 ( since we
use in our exemple three bits). For exemple if you have 7x7 this operation is:
7x7 = (111)*(111) = x^2+x+1 * x^2+x+1 = x^4+x^3+x^2+x^3+x^2+x+x^2+x+1 = x^4+x^2+1 = 10101
since x^4 > x^2 we must do x^3+x+1 / x^4+x^2+1
pass[1] (x^3 +x +1) *x = x^4+x^2+x
pass[2] (x^4+x^2+ +1)
(x^4+x^2+x )
-------------
/ + / +x+1 = 011 = 3
To the end we have obtenuted this two matrix of addition and multiplication operation of all values in
a finished space GF(2^3)
Addition matrix Moultiplication matrix
----------------------------- ---------------------------
| | | |
+ [0][1][2][3][4][5][6][7] x [0][1][2][3][4][5][6][7]
[0][0][1][2][3][4][5][6][7] [0][0][0][0][0][0][0][0][0]
[1][1][0][3][2][5][4][7][6] [1][0][1][2][3][4][5][6][7]
[2][2][3][0][1][6][7][4][5] [2][0][2][4][6][3][1][7][5]
[3][3][2][1][0][7][6][5][4] [3][0][3][6][5][7][4][1][2]
[4][4][5][6][7][0][1][2][3] [4][0][4][3][7][6][2][5][1]
[5][5][4][7][6][1][0][3][2] [5][0][5][1][4][2][7][3][6]
[6][6][7][4][5][2][3][0][1] [6][0][6][7][1][5][3][2][4]
[7][7][6][5][4][3][2][1][0] [7][0][7][5][2][1][6][4][3]
In this two matrix we can find the additive and multiplicative inverse for everyone of values in the
finished space mod(8). The additive inverse value are the value that in the table have as results 0,
the multiplicative inverse values are rapresentated from the values that have as results 1. So we know
that :
------- ------------- -------------
| value | add inverse | mul inverse |
------- ------------- -------------
| 0 | 0 | / |
| 1 | 1 | 1 |
| 2 | 2 | 5 |
| 3 | 3 | 6 |
| 4 | 4 | 7 |
| 5 | 5 | 2 |
| 6 | 6 | 3 |
| 7 | 7 | 4 |
------- ------------- -------------
This values are used very frequently in a encryption algorithms
---------------[ 0x3 - The Rijndael Advanced Encryption Standard ciphrature's structure introduction ]
The Aes ciphrature is a particoular ciphrature that use a modulate arithmetic to obtain a ciphrate
text. There are several implementation of this ciphrature algorithm, one of this is named Rijndael AES
ciphrature. This ciphrature is different from the DES algorithm since AES don't use the Feistel
structure in witch the block of text are divided in two part and only one of this is used to encript;
in the Rijndael implementation, all the bits of input text are ciphrated in parallels way. The input
key can have three different dimension : 128, 192 or 256 bits that are equals to 4,6 or 8 word since
8bits = 1 byte and 4 byte = 1 word. The input text can be only of 128 bits. In this text we consider
that the key is composit of 128bits too. When the AES algorithm take the 128 bits of key (a key of 4
word) it cerat 44 differents word of 32 bits that are equals to 10 different keys since we must
repeat 10 times the same phase. The Aes algorithm can be interpretated in this way: we have a 128 bits
of input text, in the first time this text go in input with one key of 4 words, the ouput of this
procedure go in input to the first phase that are composit by four different subphases that we see in
the second time, the output of the first phase go in input to the second phase that is the same of the
first. This operation,that are util to create confusion but not to incremet the security level since
don't use the key, are repetuted for 9 times, only one of the 4 subphases use the key and it is the
most important of their. After that we send the oputut of they in input to another phase the
phase number 10 that is the last; this phase is composit only of 3 subphases and the last of this
three phases is the same procedure that we have executed when the procedure is started. Now we can
imagine the AES encrypt and decrypt procedures as showed next:
[ Encrypt procedure ] [ Decrypt procedure ]
-------------------------- ---------------------------
| | | |
-------[Input text]------- -------[Output text]-------
| -----[key] ^
| | | | -------------
V | V | | p
[Add round key]<---------|--- w[0,3] ------------->[Add round key] | h
| V ^ | a
- - - - - - - - [key expansion] | | s
------- | | [Inverse sub bytes] | e
| V | ^ |
p | [Substitute bytes] | | | 1
h | | | [Inverse shift rows] | 0
a | V | ^ -------------
s | [Shift rows] | | | p
e | | | [Inverse mix columns] | h
| V |------- ^ | a
1 | [Mix columns] | | | | s
| | | | ------->[Add round key] | e
| V | V | ^ |
| [Add round key]<---------|--- w[4,7]------ | | 9
| | | [Inverse sub bytes] |
------- V | ^ |
... | | |
------- | | [Inverse shift rows] |
| V | ^ -------------
p | [Substitute bytes] | |
h | | | ...
a | V | ^ -------------
s | [Shift rows] | | | p
e | | | [Inverse mix columns] | h
| V |------- ^ | a
9 | [Mix columns] | | | | s
| | | | ----->[Add round key] | e
| V | V | ^ |
| [Add round key]<---------|--- w[36,39]------ | | 1
| | | [Inverse sub bytes] |
------- V | ^ |
p | [Substitute bytes] | | |
h | | | [Inverse shift rows] |
a | V ------- ^ -------------
s | [Shift rows] | |
e | | | ----->[Add round key]
| V V | ^
1 | [Add round key]<------------ w[40,43]------ |
0 | | |
------- V |
[Ciphred text] [Ciphred text]
As you can see the ciphrature procedure and the deciphrature procedure are composit of 10 phases. The
phase number 10 is composit of 3 subphases and the others phase are composit of 4 subphases for boot
the procedure. In the ciphrature execution the key used in the first phase is the 128 bits that the
user insert in input, the others keys are all keys of 4 words but are created from the original. In
the deciphration execution (that started from the bottom in the right section of the image) the first
key used is the last used in the ciphrature procedure. The subphases used in the ciphrature procedure
are : Substitute bytes, Shift rows, Mix columns and Add round key; in the decript procedure this
subphase are named Inverse Substitute bytes, Inverse Shift rows, Inverse Mix Columns and Add round key
In the ciphrature and deciphrature procedure are exchanged the order of execution between Add round
key and Mix columns/Inverse Mix columns. In this text we consider that the key insert in input by the
user is composit by 128 bits that are 16 byte that are equals to 4 word; as we can see in the image,
this key in used to obtain 10 different keys so if one key is rapresentated by 4 words, the algorithm
must generate 44 different words to obtain a different key for every one of the 10 phases. The next
table show the case in witch we want implements this algorithm using 192 or 256 bits for the key:
---------------------------------------------------- ------------ ------------ ------------
| Key dimension (words,byte,bits) | (4/16/128) | (6/24/192) | (8/32/256) |
| Input text dimension(w,b,b) | (4/16/128) | (4/16/128) | (4/16/128) |
| Phase's number | 10 | 12 | 14 |
| Dimension of the Key for a single phase (w,b,b) | (4/16/128) | (4/16/128) | (4/16/128) |
| Dimension of extension key (w,b) | (44 / 176) | (52 / 208) | (60 / 240) |
---------------------------------------------------- ------------ ------------ ------------
When we insert the 128 bits of original text that we want encrypt, this bits are stored in a quadrate
matrix. It is a byte quadrate matrix that are copied in a array named State, during the phases
execution this array are changed and in the end it contain the ciphred text. During the deciphration
procedure is the same. So we can imagine the 128 bits stored in this way: (128 bits are equals to 16
bytes and 16 bytes rapresents 4 words)
(word 1) (word 2) (word 3) (word 4)
| | | |
V V V V -----
--------- --------- --------- --------- |
| input00 | input04 | input08 | input12 | |
--------- --------- --------- --------- | 4x4 words array : every one of the input parts is
| input01 | input05 | input09 | input13 | | composit of 1 byte (8 bits)
--------- --------- --------- --------- |
| input02 | input06 | input10 | input14 | |
--------- --------- --------- --------- |
| input03 | input07 | input11 | input15 | |
--------- --------- --------- --------- |
-----
During the 10 phases this matrix is changed as we can see in the next image :
[ input ] [ phase 1 ] [ phase 10 ] [ output ]
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
|in00|in04|in08|in12| |s0,0|s0,1|s0,2|s0,3| |s0,0|s0,1|s0,2|s0,3| |ou00|ou04|ou08|ou12|
|in01|in05|in09|in13|--->|s1,0|s1,1|s1,2|s1,3|.....>|s1,0|s1,1|s1,2|s0,3|--->|ou01|ou05|ou09|ou13|
|in02|in06|in10|in14| |s2,0|s2,1|s2,2|s2,3| |s2,0|s2,1|s2,2|s0,3| |ou02|ou06|ou10|ou14|
|in03|in07|in11|in15| |s3,0|s3,1|s3,2|s3,3| |s3,0|s3,1|s3,2|s0,3| |ou03|ou07|ou11|ou15|
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
The same happened for the key that is composit of 128 bits, so we can imagine that it is stored in
this way:
----- ----- ----- -----
| k00 | k04 | k08 | k12 |
| k01 | k05 | k09 | k13 |
| k02 | k06 | k10 | k14 |
| k03 | k07 | k11 | k15 |
----- ----- ----- -----
------------------------------------------------[ 0x3x1 - The subphases of a single encryption phase ]
As we have seid in the prev paragraphe a single phase of AES ciphrature algorithm is composit of 4
differents subphases. One of they use the key and increment the security level, the others are used
only to create confusion.
The first subphase that we see is named Substitute bytes. This procedure use a 16x16 matrix named
s-box in witch are presents all possible permutations that we can obtain exchenging of position 8 bits
Since we have 8 bits we can obtain 256 differents values. The best way to store the value in a 16x16
matrix is using a value rapesentated in hexadecimal form. In the first time the s-box is composit in
this way:
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B | 1C | 1D | 1E | 1F |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 2A | 2B | 2C | 2D | 2E | 2F |
| 30 | 31 | 32 | 03 | 34 | 35 | 36 | 37 | 38 | 39 | 3A | 3B | 3C | 3D | 3E | 3F |
| 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 4A | 4B | 4C | 4D | 4E | 4F |
...
| 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 9A | 9B | 9C | 9D | 9E | 9F |
| A0 | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | AA | AB | AC | AD | AE | AF |
| B0 | B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8 | B9 | BA | BB | BC | BD | BE | BF |
| C0 | C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | CA | CB | CC | CD | CE | CF |
...
| F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | FA | FB | FC | FD | FE | FF |
After that we must substitute every one element of this s-box with its multiplicative inverse (that we
have seed in the prev paragraphe). The multiplicative inverse is calcoulated on GF(2^8) finished space
and not GF(2^3) as we did in our exemple in the first paragraphe. After that we have exchanged all
values of the matrix with their multiplicative inverse values, since all values are rappresentable
with 8 bits we must obtain a new value apply for every one value this operation:
b(i) = b(i) (+) b(i+4)mod(8) (+) b(i+5)mod(8) (+) b(i+6)mod(8) (+) b(i+7)mod(8) (+) c(i)
where (+) = xor operation bit to bit and c = 01100011. To understend this operation I take you an
exemple. Immagine that in one position of our matrix after the change we have obtenuted the hex values
A6 that in binary is 10100110 so we know that
b[0] = 0
b[1] = 1
b[2] = 1
b[3] = 0
b[4] = 0
b[5] = 1
b[6] = 0
b[7] = 1
and we must apply for every one bit of A6 the operation showed first. So :
b[4] = b[4] (xor) b[0] (xor) b[1] (xor) b[2] (xor) b[3] (xor) c[4]
b[4] = 0 (xor) 0 (xor) 1 (xor) 1 (xor) 0 (xor) 0
b[4] = 0
If you think that for this operation is necessary a lot of time, you must think that this operation
is execute by a calcoulatore and a xor operation is one of base operation that a calcoulator execute.
The results of this operations is the next matrix:
columns
----------------------------------------------------------------------------------
| |
--- | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F |
| | 00 | 63 | 7C | 77 | 7B | F2 | 6B | 6F | C5 | 30 | 01 | 67 | 2B | FE | D7 | AB | 76 |
| | 01 | CA | 82 | C9 | 7D | FA | 59 | 47 | F0 | AD | D4 | A2 | AF | 9C | A4 | 72 | C0 |
r | | 02 | B7 | FD | 93 | 26 | 36 | EF | F7 | CC | 34 | A5 | ES | F1 | 71 | D8 | 31 | 15 |
o | | 03 | 04 | C7 | 23 | C3 | 18 | 96 | 05 | 9A | 07 | 12 | 80 | E2 | EB | 27 | B2 | 75 |
w | | 04 | 09 | 83 | 2C | 1A | 1B | 6E | 5A | A0 | 52 | 3B | D6 | B3 | 29 | E3 | 2F | 84 |
s | | 05 | 53 | D1 | 00 | ED | 20 | FC | B1 | 5B | 6A | CB | BE | 39 | 4A | 4C | 58 | CF |
| | 06 | D0 | EF | AA | FB | 43 | 4D | 33 | 85 | 45 | F9 | 02 | 7F | 50 | 3C | 9F | A8 |
| | 07 | 51 | A3 | 40 | 8F | 92 | 9D | 38 | FA | BC | B6 | DA | 21 | 10 | FF | F3 | D2 |
| | 08 | CD | 0C | 13 | EC | 5F | 97 | 44 | 17 | C4 | A7 | 7E | 3D | 64 | 5D | 19 | 73 |
| | 09 | 60 | 81 | 4F | DC | 22 | 2A | 90 | 88 | 46 | EE | B8 | 14 | DE | 5E | 0B | DB |
| | 0A | E0 | 32 | 3A | 0A | 49 | 06 | 24 | 5C | C2 | D3 | AC | 62 | 91 | 95 | E4 | 79 |
| | 0B | E7 | C8 | 37 | 6D | 8D | D5 | 4E | A9 | 6C | 56 | F4 | EA | 65 | 7A | AE | 08 |
| | 0C | BA | 78 | 25 | 2E | 1C | A6 | B4 | C6 | E8 | DD | 74 | 1F | 4B | BD | 8B | 8A |
| | 0D | 70 | 3E | B5 | 66 | 48 | 03 | F6 | 0E | 61 | 35 | 57 | B9 | 86 | C1 | 1D | 9E |
| | 0E | E1 | F8 | 98 | 11 | 69 | D9 | 8E | 94 | 9B | 1E | 87 | E9 | CE | 55 | 28 | DF |
| | 0F | 8C | A1 | 89 | 0D | BF | E6 | 42 | 68 | 41 | 99 | 2D | 0F | B0 | 54 | BB | 16 |
---
We know that the inputs of AES ciphrature algorithm are a key of 128bits and a text input that we want
entrypt of 128bits too. This 128bits of text are stored in a matrix and copied in a array named State.
During the execution of Substitute bytes procedure this array is changed using the s-box. We can
imagine an input matrix as showed in the next image:
word1 word2 word3 word4
| | | |
V V V V
------ ------ ------ ------
| EA | 04 | 65 | 85 |
| 83 | 45 | 5D | 96 |
| 5C | 33 | 98 | B0 |
| F0 | 2D | AD | C5 |
------ ------ ------ ------
The value stored in it are rapresentated in hex form since we must interact with the s-box matrix that
is a 16x16 matrix. The hexadecimal value EA is 234 in decimal rapresentation and 11101010 in binary
The Substitute bytes change the value EA in this way: the first 4 bits 1110 that in decimal is 14 and
in hexadecimal is E rapresents the row of s-box and the second 4bits 1010 that is 10 in decimal and A
in hexadecimal rapresents the column of s-box. The value stored in the s-box at the index
{row = E, column = A} is 87 in hexadecimal value that in decimal is 135 and in binary is 10000111. So
the value EA is sobstituted by the value 87. The same operation is repetuted for all hex value stored
in the 4x4 word matrix (that is the array State, that is the input text of 128bits). When all values
are exchanged the final matrix is this:
------ ------ ------ ------
| 87 | F2 | 4D | 97 |
| EC | 6E | 4C | 90 |
| 4A | C3 | 46 | E7 |
| 8C | D8 | 95 | A6 |
------ ------ ------ ------
The next image can help you to understend this very simple concept
-------column 5---------------
| |
| V
---- ---- ---- ---- | [00][01][02][03][04][05][06][07][08][09][0A][0B][0C][0D][0E][0F]
| | | | | | [01][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| | ----- | | | [02][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
---- /| |- ---- | [03][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| | | 45 -------------row 4-->[04][ ][ ][ ][ ][6E][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| |/ ----- | | [05][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
---- ---- ---- ---- [06][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| | | | | [07][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| | | | | [08][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
---- ---- ---- ---- [09][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| | | | | [0A][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
| | | | | [0B][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
---- ---- ---- ---- [0C][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[0D][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[0E][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[0F][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
As you can see in the image that rapresent the full aes execution, during the decryption execution it
is a subphase named inverse sub bytes that take in input the encrypted matrix and return in output the
original value of the matrix in the time first that it was encrypted by the substitute bytes. For
exemple we know that the aes algorithm is composit by 10 phase and every one phase have a subphase
named substitute bytes. But the substitute bytes procedure of phase 5 take in input a matrix different
from the matrix that take in input the phase number 7 and return an output different, so the output of
substitute bytes of the phase 9 in encryption process is the same matrix that we give in input to the
second phase of decription procedure; the output of this decryptation inverse sub bytes is the same
matrix that we give in input to the phase number 9 to the substitute bytes during the encryption phase
The procedure used to exchange the value from input to output matrix is the same used in substitute
bytes,but the invese procedure use a 16x16 matrix in witch the elements are the invese of the elements
that we have seed in a 16x16 s-box matrix. The inverse s-box is showed next:
columns
----------------------------------------------------------------------------------
| |
--- | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F |
| | 00 | 52 | 09 | 6A | D5 | 30 | 36 | A5 | 38 | BF | 40 | A3 | 9E | 81 | F3 | D7 | FB |
| | 01 | 7C | E3 | 39 | 82 | 9B | 2F | FF | 87 | 34 | 8E | 43 | 44 | C4 | DE | E9 | CB |
r | | 02 | 54 | 7B | 98 | 32 | A6 | C2 | 23 | 3D | EE | 4C | 95 | 0B | 42 | FA | C3 | 4E |
o | | 03 | 08 | 2E | A1 | 66 | 28 | D9 | 24 | B2 | 76 | 5B | A2 | 49 | 6D | 8B | D1 | 25 |
w | | 04 | 72 | F8 | F6 | 64 | 86 | 68 | 98 | 16 | D4 | A4 | 5C | CC | 5D | 65 | B6 | 92 |
s | | 05 | 6C | 70 | 48 | 50 | FD | ED | B9 | DA | 5E | 15 | 46 | 57 | A7 | 8D | 9D | 84 |
| | 06 | 90 | D8 | AB | 00 | 8C | BC | D3 | 0A | F7 | E4 | 58 | 05 | B8 | B3 | 45 | 06 |
| | 07 | D0 | 2C | 1E | 8F | CA | 3F | 0F | 02 | C1 | AF | BD | 03 | 01 | 13 | 8A | 6B |
| | 08 | 3A | 91 | 11 | 41 | 4F | 67 | DC | EA | 97 | F2 | CF | CE | F0 | B4 | E6 | 73 |
| | 09 | 96 | AC | 74 | 22 | E7 | AD | 35 | 85 | E2 | F9 | 37 | E8 | 1C | 75 | DF | 6E |
| | 0A | 47 | F1 | 1A | 71 | 1D | 29 | C5 | 89 | 6F | B7 | 62 | 0E | AA | 18 | BE | 18 |
| | 0B | FC | 56 | 3E | 4B | C6 | D2 | 79 | 20 | 9A | DB | C0 | FE | 78 | CD | 5A | F4 |
| | 0C | 1F | DD | A8 | 33 | 88 | 07 | C7 | 31 | B1 | 12 | 10 | 59 | 27 | 80 | EC | 5F |
| | 0D | 60 | 51 | 7F | A9 | 19 | B5 | 4A | 0D | 2D | E5 | 7A | 9F | 93 | C9 | 9C | EF |
| | 0E | A0 | E0 | 3B | 4D | AE | 2A | F5 | B0 | C8 | EB | BB | 3C | 83 | 53 | 99 | 61 |
| | 0F | 17 | 2B | 04 | 7E | BA | 77 | D6 | 26 | E1 | 69 | 14 | 63 | 55 | 21 | 0C | 7D |
---
If you don't know how to convert binary to hexadecimal and vice versa you can use the table showed
next:
-------------
| bin | hex |
|------|------|
| 0000 | 0 |
| 0001 | 1 |
| 0010 | 2 |
| 0011 | 3 |
| 0100 | 4 |
| 0101 | 5 |
| 0110 | 6 |
| 0111 | 7 |
| 1000 | 8 |
| 1001 | 9 |
| 1010 | A |
| 1011 | B |
| 1100 | C |
| 1101 | D |
| 1110 | E |
| 1111 | F |
-------------
so if I have a binary value 10101101 and I want convert it to hex value, I must divide it in group of
4 bits for each; in this case I have two group of 4 bits : 1010 and 1101. After that I find it in the
table, 1010 = A and 1101 = D so I know that 10101101 = AD
To obtain the binary value from an hex value I must execute the inverse operation so in the first time
show in the table that A = 1010 and D = 1101 and I know that AD = 10101101
The second subphase that we see in this text is named Shift Row, it is very simple and very useful.The
execution of this procedure consist in a succession of shift operation. At this point of text we know
that the 128 bits of text are stored in a 4x4 word matrix where the first column is the first word
of input, the second column is the second word etc... So when we insert in input a text, this text is
interpretated by the calculator as a succession of 128 bits and this bits are interpretated in hex
rapresentation by the algorithm. Now we can consider the same input obtenuted in sostitute bytes
procedure: 87 EC 4A 8C F2 6E C3 D8 4D 4C 46 95 97 90 E7 A6; we know that this input of 128 bits is
stored in a 4x4 matrix in this way:
------ ------ ------ ------
| 87 | F2 | 4D | 97 |
| EC | 6E | 4C | 90 |
| 4A | C3 | 46 | E7 |
| 8C | D8 | 95 | A6 |
------ ------ ------ ------
where the first column is the first word since 87 is a sigle byte that is equals to 8 bits. We know
that every word is composit by 4 byte that are 32 bits. Now If we work on the rows and not on the
columns we change all senses of the clear text. You must remeber that this byte array is the output of
the first subphase (the substitute byte). The Shift Row procedure don't change the first row but apply
a left shift at the rows number 2,3 and 4. For the second row we apply a left shift of a single byte,
for the row number three we apply a shift of two bytes and for the last row we apply a left shift of
three bytes. When this procedure is finished the output of it is a new 4x4 matrix where the 4 words
are shuffled as showed next :
------ ------ ------ ------
| 87 | F2 | 4D | 97 |
| 6E | 4C | 90 | EC |
| 46 | E7 | 4A | C3 |
| A6 | 8C | D8 | 95 |
------ ------ ------ ------
The third subphases as you can see in the image rapresentated in the cap 0x3 is named Mix Columns,this
procedure is used to adding other confusion exchanging the value stored in a 4x4 matrix working on the
columns of it. To execute the exchange, the mic columns procedure use another 4x4 matrix :
------ ------ ------ ------
| 02 | 03 | 01 | 01 |
| 01 | 02 | 03 | 01 |
| 01 | 01 | 02 | 03 |
| 03 | 01 | 01 | 02 |
------ ------ ------ ------
This procedure create confusion apply a moultiplication operation in the finished space GF(2^8) using
the polinomy x^8+x^4+x^3+x+1 as irriducible value. The mix column operation can be rapresentated as
showed in the next image :
------ ------ ------ ------ ------- ------- ------- -------
| 02 | 03 | 01 | 01 | | S00 | S01 | S02 | S03 |
| 01 | 02 | 03 | 01 | | S10 | S11 | S12 | S13 |
| 01 | 01 | 02 | 03 | | S20 | S21 | S22 | S23 |
| 03 | 01 | 01 | 02 | | S30 | S31 | S32 | S33 |
------ ------ ------ ------ ------- ------- ------- -------
Where the matrix with the elements s00 s01 s02 etc is our input state matrix that is the output of the
two subphases executed in the prev times. So After the substitute bytes and shift row procedure we
have the next matrix multiplication for the execution of the third procedure of a single phase:
------ ------ ------ ------ ------ ------ ------ ------
| 02 | 03 | 01 | 01 | | 87 | F2 | 4D | 97 |
| 01 | 02 | 03 | 01 | | 6E | 4C | 90 | EC |
| 01 | 01 | 02 | 03 | | 46 | E7 | 4A | C3 |
| 03 | 01 | 01 | 02 | | A6 | 8C | D8 | 95 |
------ ------ ------ ------ ------ ------ ------ ------
The multiplication between this two matrix is execute following this rules:
-> S0J = (2*S0J) (+) (3*S1J) (+) S2J (+) S3J
-> S1J = S0J (+) (2*S1J) (+) (3*S2J) (+) S3J
-> S2J = S0J (+) S1J (+) (2*S2J) (+) (3*S3J)
-> S3J = (3*S0J) (+) S1J (+) (2*S3J)
for exemple the element S00 =
--> (2*S00) (+) (3*S10) (+) S20 (+) S30
--> (2*87) (+) (3*6E) (+) 46 (+) A6
--> (00000010 * 10000111) xor (00000011 * 01101110) xor 01000110 xor 10100110
--> [x * (x^7+x^2+x+1)] xor [(x+1) * (x^6+x^5+x^3+x^2+x)] xor x^6+x^2+x xor x^7+x^5+x^2+x
--> x^8+x^3+x^2+x xor x^7+x^4+x^5+x xor x^6+x^2+x xor x^7+x^5+x^2+x
--> x^8+x^4+x^3+ +x+1
x^8+ +x^3+x^2+x xor x^7+x^4+x^5+x xor x^6+x^2+x xor x^7+x^5+x^2+x
--> x^4+ +x^2+ +1 xor x^7+x^5+x^4+x xor x^6+x^2+x xor x^7+x^5+x^2+x
--> 10101 xor 10110010 xor 1000110 xor 10100110
--> 1000111 == 47
If you execute this operations on all matrix we obtain this:
------ ------ ------ ------
| 47 | 40 | A3 | 4C |
| 37 | D4 | 70 | 9F |
| 94 | E4 | 3A | 42 |
| ED | A5 | A6 | BC |
------ ------ ------ ------
The inverse procedure of it named Inverse Mix Columns used in the decryption phase apply the same
sistem and the same operations but using the matrix showed next to reobtain the initial matrix value:
------ ------ ------ ------
| 0E | 0B | 0D | 09 |
| 09 | 0E | 0B | 0D |
| 0D | 09 | 0E | 0B |
| 0B | 0D | 09 | 0E |
------ ------ ------ ------
The last phase that we see is the most important since use the key of phase to add a security level to
a state matrix. The operation is very simple, the array state is an array of 128bits and the key is
composit of 128 bits too so we can create another matrix that is a matrix that rapresents a courrent
key generated from the original key (you must remember that we use a different key for every one of
the 10 phases). This procedure, named Add Round key is only a xor bit to bit between the two matrix,
the matrix of state that contain the courrent state of the text, and the matrix of the courrent key
that contain one of all subkeys generated during the several phases. The inverse procedure used in
decryption phase don't change since the xor operation is invertible in fact: 10 xor 2 = 8 and 8 xor 2
= 10. Using the last array state obtenuted by the mix Columns procedure I take you an exemple of a Add
Round key execution using a casual key of 128 bits and rapresentated in a 4x4 byte array:
------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------
| 47 | 40 | A3 | 4C | | AC | 19 | 28 | 57 | | EB | 59 | 8B | 1B |
| 37 | D4 | 70 | 9F | xor | 77 | FA | D1 | 5C | = | 40 | 2E | A1 | C3 |
| 94 | E4 | 3A | 42 | | 66 | DC | 29 | 00 | | F2 | 38 | 13 | 42 |
| ED | A5 | A6 | BC | | F3 | 21 | 41 | 6A | | 1E | 84 | E7 | D2 |
------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------
---------------------------------------[0x3x2 - The Aes key's expansion from 4 to 44 word procedure ]
In the prevs paragraphes we said that only one of four subphases use a key to increment the security
level of ciphrature and that the key used during the execution of the 10 phases is not the same but it
change for every one different phase. There is an algorithm that use the key of 128 bits that the user
insert in input to generate all 10 subkey of 128bits. We know that 128 bits are 4 word, the algorithm
is used to generate 44 words. Imagine that the input key of 128bits rapresentated in hex form is this
original key of 128 bits / 16 bytes / 4 words
----------------------------------------------------
| word 1 word 2 word 4 word 4 |
| ----------- ----------- ----------- ----------- |
| || || || |
--> EA D2 73 21 B5 8D BA D2 31 2B F5 60 7F BD 29 2F
This key is composit of 4 words, every word is composit of 4 byte end every byte is composit of 8 bits
so every word is composit of 32 bits. To generate other 40 words to obtain 44 words, one for every one
phase of aes encryption, the algorithm works in this way:
pass[1] -> expand the arrey that contain the 4 words of key to an array that have the space to preserv
44 words. The new array is composit by 1408 bits that are 176 byte that are equals to 44
words.
pass[2] -> create a temp-word that are equals to the word prev of it so temp = 7F BD 29 2F
pass[3] -> execution of RotWord procedure that apply a left shift of one byte so temp = BD 29 2F 7F
pass[4] -> execution of SubWord that exchange the value of a single byte using the s-box showed in the
prev chapter so temp = 5D A5 15 D2
pass[5] -> execution of Rcon(1) that is a xor operation between the courrent value of temp and a value
of RC[j] where j is the number of subkey that we must create (in this case we are creating
the subkey for the first phase so we must apply the xor between the courrent value of temp
and the value of RC[1]. So temp = 46 A5 15 D2
The next table show the value of RC[j]:
RC[01] = 01 00 00 00
RC[02] = 02 00 00 00
RC[03] = 04 00 00 00
RC[04] = 08 00 00 00
RC[05] = 10 00 00 00
RC[06] = 20 00 00 00
RC[07] = 40 00 00 00
RC[08] = 80 00 00 00
RC[09] = 1B 00 00 00
RC[10] = 36 00 00 00
pass[6] -> execute a xor operation between the courrent value of temp and the 4 word prev of it. In
this case EA D2 73 21 xor 46 A5 15 D2 so temp = AC 77 66 F3 (this is the first word of the
new key.
Now we can create the complete key from the original:
word 1 word 2 word 3 word 4
------------ ------------ ------------ ------------
EA D2 73 21 B5 8D BA D2 31 2B F5 60 7F BD 29 2F
new key :
word 5 word 6 word 7 word 8
------------ ------------ ------------ ------------
[ ][ ][ ][ ] [ ][ ][ ][ ] [ ][ ][ ][ ] [ ][ ][ ][ ]
------------ ------------ ------------ ------------
Temp RootWord SubWord RC(1) xor word(i)-4 finalword
word5 = 7F BD 29 2F 8D 29 2F 7F 5D A5 15 D2 1B 00 00 00 46 A5 15 D2 EA D2 73 21 AC 77 66 F3
word6 = AC 77 66 F3 77 66 F3 AC FA 33 0D 91 1B 00 00 00 E1 33 0D 91 B5 8D BA D2 54 BE B7 43
word7 = 54 BE B7 43 BE B7 43 54 AE A9 1A 20 1B 00 00 00 B5 A9 1A 20 31 2B F5 60 84 82 EF 40
word8 = 84 82 EF 40 82 EF 40 84 13 DF 09 5F 1B 00 00 00 08 DF 09 5F 7F BD 29 2F 77 62 20 70
the new key that the AES use in phase 1 is this: AC 77 66 F3 53 BE B7 43 84 82 EF 40 77 62 20 70