How AES works

What is this article about

For a long time, I believed that cryptographic encryption and hashing algorithms, like AES and MD5, are very difficult and it is not easy to write them, even with full documentation at hand. Entangled implementations of these algorithms in different programming languages only strengthened this opinion. But recently, I have a lot of free time and I decided to understand these algorithms and write them. It turned out that they are very simply arranged and need very little time to implement them.

In this article I will write how the AES encryption algorithm (sometimes called Rijndael) works and write it in JavaScript. Why on javascript? To run the program in this language, you only need a browser in which you read this article. To run a program, say on C, you need a compiler and there are very few people willing to spend time compiling code from an article. At the end there is a link by which you can download an archive with an html page and several js files - this is an example of AES implementation in JavaScript.
')

How to apply AES

This algorithm converts one 128-bit block to another, using the secret key needed for such a conversion. To decrypt the received 128-bit block, use the second transformation with the same secret key. It looks like this:

cipher = encrypt(block, key) //  block   key block = decrypt(cipher, key) //  cipher   key

The block size is always 128 bits. The key size also has a fixed size. To encrypt a random text with any password, you can do this:

get password hash
convert hash to key according to the rules described in the AES standard
break the text into blocks of 128 bits
encrypt each block with cipher

This can be written as:

 hash = md5(password) // MD5    128  key = keyexpansion(hash) //     blocks = split(text, 16) //      16  for (i = 0; i < blocks.length; i++) cipher[i] = encrypt(blocks[i], key)

To decrypt an array of cipher blocks, you need to apply decrypt to each block:

 hash = md5(password) key = keyexpansion(hash) for (i = 0; i < cipher.length; i++) blocks[i] = decrypt(cipher[i], key) text = merge(blocks) //

Of course, the length of the text may not be a multiple of 128 bits. In such cases, you can add text to the zeros to the desired length, and add a few bytes to the encrypted data with the size of the original text that is encrypted. The aes.encrypt and aes.decrypt functions in the aes.js file in the example use this approach.

GF field (2 ⁸ )

AES actively uses the so-called finite field GF (2 ⁸ ). To write AES in JavaScript it is not necessary to know what the field is, but if you want to better understand AES, read this section.

The field GF (2 ⁸ ) is the numbers 0..255 for which we determined a special multiplication and a special addition. Take some number from this field and represent it in the form of eight bits: a = a ₇ a ₆ a ₅ a ₄ a ₃ a ₂ a ₁ a ₀ . Similarly, we represent the number b. The addition of a and b is the known bitwise operation xor:

a + b = a xor b

Adding has simple properties:

a + a = 0 -a = 0 - a = a a - b = a + (-b) = a + b

Multiplication is more difficult. We write the polynomials with the coefficients of the bits of these numbers:

p = a ₇ x ⁷ + a ₆ x ⁶ + a ₅ x ⁵ + a ₄ x ⁴ + a ₃ x ³ + a ₂ x ² + a ₁ x + a ₀ q = b ₇ x ⁷ + b ₆ x ⁶ + b ₅ x ⁵ + b ₄ x ⁴ + b ₃ x ³ + b ₂ x ² + b ₁ x + b ₀

Now multiply these two polynomials and find the remainder of the division by m:

m = x ⁸ + x ⁴ + x ³ + x + 1 r = pq mod (m)

Why was chosen such a m? This polynomial has only two polynomial dividers into which it is divided without remainder: the unit and itself. By analogy with prime numbers, the m polynomial is “prime”. The remainder of the division can also be found as for ordinary numbers: to do this, it is enough to be able to multiply, add and subtract polynomials; moreover, addition and subtraction are performed according to the rules of GF (2 ⁸ ), i.e. addition and subtraction of polynomials is xor between each pair of coefficients. Here are two examples:

x ³ + x ² + 1 mod (x ³ + 1) = x ² // x ³ +1 x ³ + x ² + 1 mod (x ² + 1) = (x ³ + x ² + 1) - (x + 1)(x ² + 1) = -x

We represent the polynomial r as

r = r ₇ x ⁷ + r ₆ x ⁶ + r ₅ x ⁵ + r ₄ x ⁴ + r ₃ x ³ + r ₂ x ² + r ₁ x + r ₀

Its 8 coefficients are an 8-bit number from the GF (2 ⁸ ) field and this number is called the product a • b. Unlike addition, multiplication cannot be found by a pair of simple bitwise operations. However, multiplication by an arbitrary polynomial in the field GF (2 ⁸ ) can be reduced to multiplication by the polynomial x, and multiplied by x can be done by several bitwise operations, which will be discussed below.

To denote polynomials in GF (2 ⁸ ) use hexadecimal digits. for example

m = x ⁸ + x ⁴ + x ³ + x + 1 = 100011011 = 0x011b = {01}{1b}

Multiply by the polynomial x = {02} in the field GF (2 ⁸ ) is very simple. Consider the product:

xp = x(a ₇ x ⁷ + a ₆ x ⁶ + a ₅ x ⁵ + a ₄ x ⁴ + a ₃ x ³ + a ₂ x ² + a ₁ x + a ₀ ) = a ₇ x ⁸ + a ₆ x ⁷ + a ₅ x ⁶ + a ₄ x ⁵ + a ₃ x ⁴ + a ₂ x ³ + a ₁ x ^<2 + a ₀ x p = a ₇ a ₆ a ₅ a ₄ a ₃ a ₂ a ₁ a ₀ xp = a ₇ a ₆ a ₅ a ₄ a ₃ a ₂ a ₁ a ₀ 0 //

Now you need to find the remainder of the division by m. If the bit a ₇ = 1, then you need to subtract m once. If a ₇ = 0, then nothing needs to be subtracted. So:

r = xp mod (m) = xp - m a ₇ = 1 r = xp mod (m) = xp a ₇ = 0

Multiplication by x can be written with the following function:

 gf.xtime = function(b) { var highbit = b & 0x80 var shl = (b << 1) & 0xff return highbit == 0 ? shl : shl ^ 0x1b }

Knowing how to multiply by x can be multiplied by any other polynomial. For example, we find a • b where a = {3c}, b = {a1}:

b = {a1} = 10100001 = {80} + {20} + {01} a•b = a•{80} + a•{20} + a•{01} = a•x ⁷ + a•x ⁵ + a = a•{02}•{02}•{02}•{02}•{02}•{02}•{02} + a•{02}•{02}•{02}•{02}•{02} + a = {29} + {c1} + {3c} = {d4}

There is only one simple operation left in the GF (2 ⁸ ) field. Any byte b, except for zero, has a reverse byte a = b ^-1 which has the property a • b = {01}. All three functions for working with a field — multiplying by x, multiplying two arbitrary bytes, and finding the opposite — I compiled into a small gf javascript library.

SBox table

This table is a 256-byte array and is used to replace one byte with another. It is not necessary to understand how it works, because you can simply copy this array into the code. To find out what the SBox [b] element is equal to, you need three steps:

find the reverse byte to b in the field GF (2 ⁸ ) (leave zero unchanged)
multiply the eight-bit result by an 8 × 8 matrix of 64 bits
add {63}

In sum, these three actions give an affine transformation:

It is easy to understand how this matrix is built of bits. To multiply the bits, use “and”, for addition - “xor”. For example:

r ₀ = b ₀ + b ₄ + b ₅ + b ₆ + b ₇ + 1

I wrote the sbox function like this:

 aes.sbox = function(b) { var m = 0xf8 var r = 0 var q = gf.inv(b) || 0 for (var i = 0; i < 8; i++) { r = (r << 1) | bits.xorbits(q & m) m = (m >> 1) | ((m & 1) << 7) } return r ^ 0x63 }

The constructed table looks like this:

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

It can be simply copied into the code, as they often do, or it can be calculated using the sbox function as needed.

InvSBox table

To decrypt text, AES uses a table inverse to SBox. The table InvSBox has one property: InvSBox [SBox [i]] = i. InvSBox looks like this:

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

Types of AES

The AES algorithm converts a block of 128 bits to another block of the same length. For conversion, the key schedule w is used, which is obtained from the key. A 128-bit block in AES is represented as a 4 × N _b matrix. The standard allows only one value N _b = 4, so the block length is always 128 bits, although the algorithm can work with any N _b . The key length is 4N _k bytes. The block encryption algorithm consists of Nr rounds — applying the same transform group to a 128-bit data block. The standard allows the following combinations of these three parameters:

	N _k	N _b	N _r
AES-128	four	four	ten
AES-192	6	four	12
AES-256	eight	four	14

KeyExpansion conversion

To encrypt text, AES does not use a password or password hash, but the so-called “key schedule” obtained from the key. This schedule can be represented as N _r + 1 matrices of size 4 × N _b . The encryption algorithm takes N _r + 1 steps and at each step, among other actions, it takes one 4 × N _b matrix from the “schedule” and elementwise adds it to the data block.

Data block encryption

The encryption algorithm receives an input 128-bit data block input and a schedule of keys w, which is obtained after KeyExpansion. It writes the 16-byte input as a 4 × N _b matrix s, which is called the AES state, and then applies 4 transformations N times. At the end, he writes the matrix as an array and feeds it to the output — this is an encrypted block. Each of the four transformations is very simple.

AddRoundKey takes one 4 × N _b matrix from the key schedule and adds it element by element to the state matrix. If you use AddRoundKey twice, then nothing will change, so the transformation inverse to AddRoundKey is it itself.
SubBytes replaces each element of the state matrix with the corresponding element of the SBox table: s _ij = SBox [s _ij ]. SubBytes conversion is reversible. The reverse to it is using the InvSBox table.
ShiftRows shifts the i-th row of the matrix s by i positions to the left, counting i from zero. Inverse transformation InvShiftRows shifts rows to the right.
MixColumns multiplies each column of the matrix s from the left by a special 4 × 4 matrix:

For encryption, use [abcd] = [{02} {03} {01} {01}]. You can verify that the inverse mapping to MixColumns [{02} {03} {01} {01}] is MixColumns [{0e} {0b} {0d} {09}].

Schematically, encryption can be represented as:

 AddRoundKey(0) for (var i = 1; i <= Nr - 1; i++) { SubBytes() ShiftRows() MixColumns([0x02, 003, 0x01, 0x01]) AddRoundKey(i) } SubBytes() ShiftRows() AddRoundKey(Nr)

Decryption

As you can see, to encrypt a data block, AES consistently applies many reversible transformations to it. For decoding, you need to apply the inverse transform in the reverse order.

Little optimization

The sbox function has a total of 256 possible input values and 256 possible output values. In order not to calculate the sbox many times for one argument, you need to cache the results. In JavaScript, this is easy to do even without changing the code written earlier. To do this, just add below this:

 Function.prototype.cached = function() { var old = this var cache = {} return function(x) { if (cache[x] !== undefined) return cache[x] cache[x] = old(x) return cache[x] } } aes.sbox = aes.sbox.cached()

This code replaces sbox with a function that caches sbox results. The same can be done for any function, for example for invsbox and rcon. The same technique can be applied to the function gf.mul which multiplies two bytes in the GF (2 ⁸ ) field, but in this case the cache size will be equal to 256 × 256 elements, which is quite a lot.

Links

The AES documentation in English is called FIPS 197.

Source: https://habr.com/ru/post/112733/

All Articles