AES - Advanced Encryption Standard

How AES Works



This is only describes the 128-bit version, but the 192-bit and 256-bit key versions are similar.
AES is designed to work on bytes. However, each byte is interperted as a representation of the polynomial:

b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0
Where each bi is either 0 or 1.

Addition and Multiplication

Addition then becomes exclusive-or, but multiplication is defined as polynomial multiplication modulo x8 + x4 + x3 + x + 1. For example 2d * a3 would be calculated as follows (remembering xy + xy = 0):

2d = 00101101 = x5 + x3 + x2 + 1
a3 = 10100011 = x7 + x5 + x + 1
2d * a3 = (x12 + x10 + x9 + x7) + (x10 + x8 + x7 + x5) + (x6 + x4 + x3 + x) + (x5 + x3 + x2 + 1)
= x12 + x9 + x8 + x6 + x4 + x2 + x + 1
- modulus * x4 = x9 + x7 + x6 + x5 + x2 + x + 1
- modulus * x = x7 + x6 + x4 + 1
2d * a3 = 11010001 = d1

Although this seems not efficient, all multiplications are by a constant, so they can be calculated in advance and turned into a simple table lookup.

Algorithm State

The 128-bit state can be represented as a 4 by 4 table of bytes. The cipher will perform various operations on this array.

Encryption Algorithm (128-bit version)

Cipher(byte in[16], byte out[16], word w[44])
begin
byte state[4,4]
state = in
AddRoundKey(state, w[0, 3])
for round = 1 step 1 to 10
SubBytes (state)
ShiftRows (state)
MixColumns (state)
AddRoundKey (state, w[round*4, (round+1)*4-1])
end for
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, w[40, 43])
out = state
end

SubBytes Routine

In this routine, each byte of the state is replaced according to the following formula:
For each bit i, set bi to bi xor b(i+4) mod 8 xor b(i+5) mod 8 xor b(i+6) mod 8 xor b(i+7) mod 8 + ci where c = 63 hex.
As with multiplication, this is usually implemented as a table lookup.

ShiftRows Routine

This routine modifies each row of the state matrix. The top row is not changed, the next row is rotated left one position, the following row two positions, and the bottom row three positions.

MixColumns Routine

This function mixes up the data in each column according to the following formulas:
• Set s0,c to 2*s0,c xor 3*s1,c xor s2,c xor s3,c
• Set s1,c to 0,c xor 2*s1,c xor 3*s2,c xor s3,c
• Set s2,c to s0,c xor s1,c xor 2*s2,c xor 3*s3,c
• Set s3,c to 3*s0,c xor s1,c xor s2,c xor 2*s3,c



AddRoundKey Routine

This function does an XOR between each column of the state and a 32-bit word from the key schedule.

Key Expansion

The key schedule w is generated in the following form:
• The first four words (w[0] through w[3]) of the key are the incoming cipher key.
• To calculate w for i from 4 to 43:
o Set temp = w
o If i = 4, 8, 12, 16, ..., 40 (multiples of 4)
 Rotate this word left one byte
 Replace each byte (using the same substitution function as SubBytes.
 Do an exclusive-or with the round constant Rcon
o Set w = w xor temp

AES Decryption

Decryption basically consists of performing each of the encryption steps in reverse, using the following algorithm:
InvCipher(byte in[16], byte out[16], word w[44])])
begin
byte state[4,4]
state = in
AddRoundKey(state, w[40, 43])
for round = 9 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[round*3, (round+1)*3-1]) InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[0, 3])
out = state
end

Each of the Inv... functions is the inverse of the corresponding encryption function. InvSubBytesbecomes another table lookup, and the equations for InvMixColumns are:
• Set s0,c to 0x0e*s0,c xor 0x0b*s1,c xor 0x0d*s2,c xor 0x09*s3,c
• Set s1,c to 0x09*s0,c xor 0x0e*s1,c xor 0x0b*s2,c xor 0x0d*s3,c
• Set s2,c to 0x0d*s0,c xor 0x09*s1,c xor 0x0e*s2,c xor 0x0b*s3,c
• Set s3,c to 0x0b*s0,c xor 0x0d*s1,c xor 0x09*s2,c xor 0x0e*s3,c

The algorithm can be rewritten so it looks similar to the encryption algorithm, with a few simple modifications.

SubBytes Table

This article describes the S-box used by the Rijndael cryptographic algorithm.

The S-box is generated by determining the multiplicative inverse for a given number in Rijndael's finite field. The multiplicative inverse is then transformed using the following affine transformation:
[1 0 0 0 1 1 1 1][X0]+[1]
[1 1 0 0 0 1 1 1][X1]+[1]
[1 1 1 0 0 0 1 1][X2]+[0]
[1 1 0 1 0 0 0 1][X3]+[0]
[1 1 0 0 1 0 0 0][X4]+[0]
[0 1 1 1 1 1 0 0][X5]+[1]
[0 0 1 1 1 1 1 0][X6]+[1]
[0 0 0 1 1 1 1 1][X7]+[0]

where [x0, ..., x7] is multiplicative inverse as a vector.

The matrix multiplication can be calculated by the following algorithm:

Store the multiplicative inverse of the input number in two 8-bit unsigned temporary variables: s and x
Rotate the value s one bit to the left; if the value of s had a high bit (eight bit from the left) of one, make the low bit of s one; otherwise the low bit of s is zero.
Exclusive or the value of x with the value of s, storing the value in x
For three more iterations, repeat steps two and three; steps two and three are done a total of four times.
The value of x will now have the result of the multiplication.
After the matrix multiplication is done, exclusive or the value by the decimal number 99 (the hexadecimal number 0x63).

This will generate the following S-box, which is represented here with hexadecimal notation:
---| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| a| b| c| d| e| f|
00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Here the column is determined by the least significant nybble, and the row is determined by the most significant nybble. For example, the value 0x9a is converted in to 0xb8 by Rijndael's S-box.

The inverse S-box is simply the S-box run in reverse. For example, the inverse S-box of 0xdb is 0x9f. The following table represents Rijndael's inverse S-box:

---| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| a| b| c| d| e| f|
00 |52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
10 |7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
20 |54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
30 |08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
40 |72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
50 |6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
60 |90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
70 |d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
80 |3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
90 |96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
a0 |47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
b0 |fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
c0 |1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
d0 |60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
e0 |a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
f0 |17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d


Attachments as follow:
1.How AES Works in .pdf
2.AES in general.zip.......learn more about AES
3.AES and Java Technology.zip.......learn more about AES
4.AES Encryption Software.zip.....the software is DEMO Version  if you like it,you buy it







[privitak je izbrisao admin]