M
AES is a cryptographic primitive designed to compose symmetric cipher and deciphering systems (i.e. the same key to cipher and decipher). It is a block cipher, i.e. it operates in fixed size blocks (128 bits, or 16 bytes). Like every block cipher, it can be transformed into a http://pt.wikipedia.org/wiki/Cifra_de_fluxo (so as to operate in arbitrary size data) through a http://pt.wikipedia.org/wiki/Modo_de_opera%C3%A7%C3%A3o_%28criptografia%29 But that's not the case here. It can work with 128, 192 or 256-bit keys (the Rijndael algorithm, which originated the AES, allows more key sizes).In other words, it is an algorithm whose direct function (crying) receives as inputs a 128-bit block (the message) and a key of the chosen size, and returns a 128-bit output (the cipher). The reverse function (deciphering) receives as input a 128-bit block (the cipher) and returns as output a 128-bit block. If the key is the correct key, this output will be identical to the original message.The goal of a successful cipher is to be impractical if you discover the original message if you only have the ciphered message, but not the encryption key. For this, it is sought to minimize any visible correlation between input and output, so that the same (and/or key) can be deduced by simply observing a very large number of ciphers (or message/cipher pairs). For this, a series of "rodadas" (or rounds) where bytes undergo non-linear but reversible transformations (i.e. to decipher, simply the reverse of the same operations is carried out, in reverse order).Finite BodyAll AES operations treat entry bytes as a http://pt.wikipedia.org/wiki/Corpo_finito (finite fields, or Galois fields) in 28. That means:There is a set [0,255] (which are all possible values for a byte) and one of these elements is called "zero" (in the case, the 0);There is an operation, which we will call "adition", which applies to any two elements in this set and whose result is also an element of that set. This operation needs to be associative, commutative, possess neutral element, and each element must have a reverse;
In this case, we define the "addition" as the "exclusive O" - XOR.There is an operation, which we will call "multiplication", with characteristics similar to "addition". Except for the "zero" element, which has no reverse (and the neutral element of multiplication is called "one"). The multiplication also needs to be distributive in relation to addition.
The "multiplication" will be set forth.For those who have no experience with mathematics, it is good to stress that we are setting "addition", "multiplication", "zero" and "one" - these names do not necessarily have anything to do with the usual arithmetic operations we do in the set of Natural or Royal numbers (the Natural or Inteiros, for example, do not form bodies with the + and * usual, because there is no x inside these sets such that 2*x=1; the Royals form a body, only infinite). There is no "subtraction", "division", etc.The addition, as already said, was defined as the XOR. The multiplication is more complex: first treat each operand as if it were a polynomial based on its binary representation (e.g.: 6 - 110 - Turn x^2 + x, and 11 - 1011 - Turn x^3 + x + 1), multiply them, then divide the result by a "reductive agent". The rest of the division (interpreted again as a number) will then be the result of multiplication. In the case of AES, the chosen reducing agent was:x^8 + x^4 + x^3 + x + 1
To multiply 6 by 11 is the same as doing(x^2 + x)*(x^3 + x + 1) mod (x^8 + x^4 + x^3 + x + 1)
=[(x^5 + x^3 + x^2) + (x^4 + x^2 + x)] mod (x^8 + x^4 + x^3 + x + 1)
=(x^5 + x^4 + x^3 + x) mod (x^8 + x^4 + x^3 + x + 1)
=111010 mod 100011011
=111010
=58
Note that the coefficients are "sounded" using XOR, not the common sum: when added x^2 with x^2 the result is zero, and not 2*x^2. Think of this sum as 1*x^2 + 1*x^2 = (1 xor 1)*x^2 = 0*x^2 = 0. The body GF(2^8) was built based on GF(2) ( binary body, where the sum is XOR and multiplication is AND), so that its polynomials have only 0 or 1 as coefficients. For more details, English Wikipedia has an article on http://en.wikipedia.org/wiki/Finite_field_arithmetic , including a specific subsection on Rijndael.Wikipedia has a http://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael.27s_finite_field that is equivalent to this multiplication of polynomials, but much less costly (see at the end of the section).That is, an AES [not optimized] implementation could for example create a distinct type of data to represent each byte of inputs/outputs/keys and give its own implementation of "addition" and "multiplication" (overloading the usual ones if the programming language allows). This would simplify logic at the expense of performance.big disclaimer: No I'm suggesting that lay people implement AES [to use in practice] - I don't trust myself to implement cryptographic algorithms, much less in anyone reading this... I put this only for didactic purposes, a real implementation needs to worry even about things like http://en.wikipedia.org/wiki/Side_channel_attack (e.g.: http://en.wikipedia.org/wiki/Timing_attack and http://en.wikipedia.org/wiki/Differential_fault_analysis ).Note: From now on, whenever I speak of "add" or "multiply" I refer to operations in GF(28), except when there is.Rijndael S-BoxBased on this finite body arithmetic, a query table was conceived (lookup table) call http://en.wikipedia.org/wiki/Rijndael_S-box , intended to transform a byte into another different, in a non-linear way. Two tables are used: one for direct function and another for reverse.First, it is calculated the inverse multiplicative of byte (i.e. a byte such that multiplied by it results in "one"). The zero has no reverse, so it maps to zero even.Then the eight bits of the result are submitted to a http://pt.wikipedia.org/wiki/Transforma%C3%A7%C3%A3o_afim , to make the method more resistant against http://en.citizendium.org/wiki/Algebraic_attack :[1 0 0 0 1 1 1 1][b0] [1]
[1 1 0 0 0 1 1 1][b1] [1]
[1 1 1 0 0 0 1 1][b2] [0]
[1 1 1 1 0 0 0 1][b3] + [0]
[1 1 1 1 1 0 0 0][b4] [0]
[0 1 1 1 1 1 0 0][b5] [1]
[0 0 1 1 1 1 1 0][b6] [1]
[0 0 0 1 1 1 1 1][b7] [0]
This table was designed to be resistant to cryptanalysis http://en.wikipedia.org/wiki/Linear_cryptanalysis or http://en.wikipedia.org/wiki/Differential_cryptanalysis , and allowing the replacement of the affin transformation by another if you discover any backdoor in the future. For practical purposes, it is an invertible function whose output does not resemble anything in the input (i.e. small changes in the input produce apparently random differences in the output).Key ExpansionAs it was said, AES has several rounds of calculation, which part of the original message, applies a series of transformations in it, and reaches the final result (the cipher). I will call the data being worked "state" (stateestado = mensagem
estado = round(estado)
estado = round(estado)
estado = round(estado)
...
estado = round(estado)
cifra = estado
In each state, it is not used the original encryption key, but rather a series of keys derived from it. This derivation uses an algorithm called http://en.wikipedia.org/wiki/Rijndael_key_schedule , and it is complex by itself to be fully explained here (despite the https://github.com/bitwiseshiftleft/sjcl/blob/master/core/aes.js ). I'll just give an overview, so:AES operates in 128-bit blocks, as seen, but uses 128, 192 or 256-bit keys; the key expansion algorithm therefore produces a set of 128-bit sub-keys - one for each round of the algorithm (which by signal also depends on the size of the key: are 10, 12 or 14 rounds, respectively).Starting from the original key, a series of operations involving rotation (shift) of the last 4 bytes, its transformation according to the S-Box, and the addition with a power of 2. There is a small variation in the steps as the key size used.
By "power of 2", I mean 2 multiplied by itself N times, in GF(28). How can you see http://en.wikipedia.org/wiki/Rijndael_key_schedule#Rcon , the values are quite different from arithmetic in whole numbers.Since there was enough bytes for all rounds of the algorithm, the expansion of the key is concluded.RoundThe algorithm works in rounds, or rounds, so that in each of them a series of reversible operations is made upon the state. The goal is that each input byte is "combined" with several key bytes, so that small changes in both key and message cause significant changes in the cipher (see http://en.wikipedia.org/w/index.php?title=Confusion_and_diffusion ). In other words, if you want to avoid that part of the cipher depends only on part of the key, which would allow you to break the problem of deciphering a large key in deciphering several minor keys (which could be done by brute force).Note: State bytes are commonly represented in a 4x4 matrix. This matrix is by column, not by line (as in most popular programming languages). That is, the 16 bytes are arranged as follows:b0 b4 b8 b12
b1 b5 b9 b13
b2 b6 b10 b14
b3 b7 b11 b15
When mentioned "line" or "column", it refers to the 4 bytes of the state corresponding to the above representation.In the first round, the state is added to the key of that round;estado = estado ^ chave(0)
In the subsequent rounds:each byte of the state is transformed according to the S-Box;para cada byte b no estado:
estado[b] = S(estado[b])
Then the lines are rotated to the left, as follows:a00 a01 a02 a03 <<0 a00 a01 a02 a03
a10 a11 a12 a13 <<1 a11 a12 a13 a10
a20 a21 a22 a23 <<2 a22 a23 a20 a21
a30 a31 a32 a33 <<3 a33 a30 a31 a32
Then in each column of the matrix your bytes are combined with all other bytes of the same column; this step No occurs in last round.The detailed description of this step can be seen http://en.wikipedia.org/wiki/Rijndael_mix_columns . What is done is take each column of the matrix and multiply it by a fixed matrix, resulting in the new values of the column:[a00] [2 3 1 1][a00]
[a10] = [1 2 3 1][a10]
[a20] [1 1 2 3][a20]
[a30] [3 1 1 2][a30]
a00 = 2a00 ^ 3a10 ^ 1a20 ^ 1a30
a10 = 1a00 ^ 2a10 ^ 3a20 ^ 1a30
a20 = 1a00 ^ 1a10 ^ 2a20 ^ 3a30
a30 = 3a00 ^ 1a10 ^ 1a20 ^ 2a30
... (idem pras demais colunas)
By my understanding, multiplication continues to be multiplication in GF(28), but in this case there is a simpler description of the same: x1 é x, x2 é x<<1 and x*3 é x<<1 ^ x. If the result is greater than 255, do x ^ 0x1B.Finally, the key of the round to the state is added.estado = estado ^ chave(i) # onde i é o número da rodada
SummaryThis series of operations (add key, replace, mix/lost) is called http://en.wikipedia.org/wiki/Substitution-permutation_network , or SP-network. Here is a graphical representation of the process, with 3 rounds:DecipheringThe process of deciphering is simply the application of the reverse of these same operations, in the reverse order naturally. It often changes nothing between ciphering and deciphering (e.g.: a xor b xor b = a), in others some adaptation is necessary:Instead of starting with estado = mensagem and end with cifra = estado, now we start with estado = cifra and we end with mensagem = estado;The expansion of the key is equal; at the beginning of each round if you add the corresponding round key (remember that we are now doing the rounds back forward), and in the end the key of the first round;To undo step 3 (column mix) of each round in which it applies (i.e. all except the first and the last), the reverse matrix is used to that described previously:[a00] [14 11 13 9][a00]
[a10] = [ 9 14 11 13][a10]
[a20] [13 9 14 11][a20]
[a30] [11 13 9 14][a30]
(as this time there is no "shorts" for multiplication, it is common to use another lookup table instead of making the bill on time. http://en.wikipedia.org/wiki/Rijndael_mix_columns#Galois_Multiplication_lookup_tables has the relevant tables.)Step 2 is simply one shift right instead of left...To undo step 1, one uses lookup table which corresponds to the reverse of the S-Box.