First of all, my reply merely seeks to add content to the reply from mgibsonbr, which is already quite complete. I had to make a theoretical foundation for my Course Completion Work. I think it would be very selfish of me to leave everything I wrote on paper, so I decided to share what I wrote with the community. Some improvements are still needed and I think I may have made some mistakes, because the algorithm is very complex. If this happens, feel free to edit my answer.
1 - Cryptography
According to Bond et al. (2003), encrypting data means converting it so that it can only be deciphered and read by authorized users, so data encryption requires an algorithm to be applied to this data.
The way of writing logic is called an algorithm, which, according to Cormen et al. (2002, p. 3), is nothing more than any well-defined computational procedure that takes some value or set of values as input and produces some value or set of values as output. Therefore, an algorithm is a sequence of computational steps that transform the input into the output. In this way, an encryption algorithm is a mathematical procedure that contains an input, the data to be encrypted, performs a processing
mathematician based on a key, and generates a output: encrypted data (KUROSE; ROSS, 2010; BOND et al., 2003; RAPPAPORT, 2009; STALLINGS, 2008; FOROUZAN; FEGAN, 2008). Forouzan and Fegan (2008) explains some terms used when referring to cryptography, according to him:
- Cipher: are the encryption and decryption algorithms
- Key: is a number or set of numbers on which the cipher operates.
2 - Symmetric Encryption
Symmetric encryption is the type of encryption that uses the same key to encrypt and decrypt the data (FOROUZAN; FEGAN, 2008). Generally symmetric encryption algorithms are quite sophisticated and use 56-bit or 128-bit keys. Due to the size and mathematical probability of the number and complexity of the key, an encryption algorithm cannot be easily reversed, meaning that without the key, the encrypted data would take hundreds of years to be deciphered in a brute force attack, if, only if, the algorithm that encrypted this data is sufficiently robust (BOND et al., 2003).
Symmetric encryption is used to guarantee the confidentiality of certain data and ensures that only authorized recipients, those who know the decryption key, can recover the original data (BOND et al., 2003).
An example of symmetric cipher is the AES algorithm, Advanced Encryption Standard, which is an evolution of DES and was developed because the DES key was too short. AES is a very complex cyclic cipher and has been designed with three key sizes: 128, 192 or 256 bits (FOROUZAN; FEGAN, 2008).
3 - Asymmetric Cryptography
Asymmetric cryptography is one that uses different algorithms of symmetric cryptography and requires the use of two keys: the private key, which is kept secret by the owner and used to encrypt data, and the public key, which is known to persons authorised by the private key owner and is used to decrypt the data (FOROUZAN; FEGAN, 2008). However, if a data is encrypted with the public key, only the private key owner can decipher this data (BOND et al., 2003)
4 - The AES algorithm
The Advanced Encryption Standard algorithm, or simply AES, is a 128-bit (16-byte) block symmetric encryption algorithm, developed since 1997 by Vincent Rijmen and Joan Daemen, and announced on 26 November 2001 by NIST, (National Institute of Standards and Technology) US National Institute of Standards and Technology in free translation (NIST, 2001)1.
The AES algorithm has 128-bit keys, 192 or 256 bits or 16, 24 and 32 bytes respectively. Key means the digital data set on which the cipher operates (FOROUZAN; FEGAN, 2008). Because it is a symmetric encryption algorithm with 128-bit blocks, the encryption function, which is the function responsible for transforming and shuffling the data, takes 16-byte (128-bit) blocks at a time and also returns 16 bytes per
time. It is called the set of blocks that will be encrypted from "message", and the set returned by the "cipher" encryption function. The decryption process is done analogously, however, contrary to the encryption process, and therefore receives a set of encrypted blocks (cipher) and returns the identical message to the original, if only if the key is the same as the one used
to encrypt the data. The encryption process can also be called encryption or even "cryptography", in the same way that the decryption process is synonymous with "decryption"or "decryption"(NIST, 2001). Figure 1 shows a pseudocode of the AES algorithm, the steps of the algorithm are explained later.
Figure 1 - AES pseudo code
Source: Adapted from NIST (2001, our translation)
5 - The State
Internally, AES algorithm operations are performed on a two-dimensional array of bytes called "State" (s). The state consists of an array organized in 4 columns of bytes, each containing 4 bytes, 16 bytes in total, and the values of each byte vary from 0 to 255. During the encryption or decryption process, the 128-bit (16-byte) blocks are copied to this array so that responsible operations are performed
the functioning of the algorithm in this copy (NIST, 2001). Figure 2 illustrates the input blocks, the State array and the output blocks, and each item corresponds to one byte:
Figure 2 - Input Blocks, State and Output Blocks
Source: Adapted from NIST (2001, our translation)
6 - Addition operation
The addition is nothing more than a sum of the bits, known as the XOR operation (OR
Exclusive), also called "exclusive disjunction". It is a logical operation between two operands that results in a true logical value if, and only if, exactly one of the operands has true value. It can be synthesized as a difference detector between two logical operands (NIST, 2001) and is represented by.
7 - Multiplication operation
In the case of the AES algorithm, multiplication is the polynomial representation GF(28) (indicated by ), that is, corresponds to the multiplication of modulo polynomials in irreducible polynomials of degree 8. A polynomial is irreducible if its only divisors are one and the same (NIST, 2001, our translation). For the AES algorithm, this irreducible polynomial is: 2
or {01}{1b} in hexadecimal notation.
For example, 57 83 = C1 because:
The x7 + x6 + 1, obtained as a result, can be written as x7 + x6 + 0x + 0x + 0x + 0x + 0x + 1 corresponds to: {11000001} in binary, which is equivalent to {C1} hexadecimal.
Agents 2x2 and 2x were cut because these polynyms only have 0 and 1 as factors, so even factors saw 0 and odd factors saw 1.
The modular reduction by m(x) ensures that the result will be a polynomial binary of degree less than 8, and thus can be represented by one byte. Unlike this, there is no single byte-level operation that corresponds to this multiplication (NIST, 2001, our translation)3.
Therefore, in a simple way, it is understood that the multiplication operation is the representation of the polynomial in its binary representation, made a multiplication of the agents of this equation and later divided by the reducing agent (module operation). The rest of this division will then be the result of the multiplication operation. In the case of AES, the
reducing agent mentioned in Equation 2.1
8 - Rijndael S-Box and the Subbyte Step
The Rijndael S-Box, or simply S-Box, is a square, non-linear matrix, used as a substitution table in several byte transformations. It is also used in one-to-one byte key expansion routines. In the AES algorithm it is used in the Subbytes step and during the key expansion (Key Expansion)4 (NIST, 2001, our translation).
The Subbytes step, or Subbytes transformation, is a non-linear substitution that operates independently in each byte of the state array using the Rijndael S-Box substitution table (NIST, 2001, our translation). The Rijndael S-Box is revertible, and is constructed by the composition of two transformations5:
- The multiplicative inverse of the byte is calculated, that is, one byte such that multiplied by
itself, results in 1. Element 0 (zero) is mapped to itself.
- An affine transformation is applied, which can be expressed as a matrix:
Similar transformation of the Rijndael S-Box
Source: Adapted from NIST (2001)
During the Subbytes step, the bytes of the State array are replaced from the S-Box, generating different and apparently random values. The S-Box used in this stage is shown in Figure 3.
Figure 3 - S-Box in hexadecimal notation
Source: Adapted from NIST (2001)
For example, if we have the State position1,1 = {53}, then the value of the substitution will be determined by the intersection of the index line 5 and index column 3 illustrated in Figure 3. Therefore, the result of the substitution in the State position1,1 will be {ed}.
9 - Shiftrows stage
In the Shiftrows step, the bytes of the last three lines of the state are moved cyclically along different numbers of bytes (offsets) 6 (NIST, 2001, our translation). Only the first line is not moved. Figure 4 illustrates this process and highlights the bytes that have been transposed.
Figure 4 - The Shiftrows step
Source: Adapted from NIST (2001)
10 - Mixcolumns Step
The Mixcolumns step operates on the State column by column, and treats each column as a four-term polynomial (NIST, 2001, our translation), according to the following equation7:
The columns are considered as polynomials and multiplied by the module x4 + 1 with a fixed polynomial a(x), given by the equation:
Therefore, the result of the Mixcolumns step over the State array, which is represented by s (x), is the multiplication of the polynomial described in Equation 2.9 by elements of the array of states s(x) which may be written as:
Being a(x) and s(x) the representation of matrices, and elements of these matrices, it is possible to represent Equation 2.10 in the form of a matrix multiplication, as in the NIST article on AES, so the equivalent representation can be seen in Figure 5 (NIST, 2001).
Figure 5 - Matrix-shaped representation for the Mixcolumns step
Source: Adapted from NIST (2001)
With the result of this multiplication, the four bytes of a column are replaced, element by element, as shown in Figure 6, right after:
Figure 6 - Elements to be replaced in the Mixcolumns step
Source: Adapted from NIST (2001)
After multiplication, the elements s0,c , s1,c , s2,c and s3,c of the State array, which together form a column c, shall be replaced by the following:'0,c , s'1,c , s'2,c and s'3,c , concluding the stage
Mixcolumns, as shown in Figure 7.
Figure 7 - The Mixcolumns step
Source: NIST (2001)
11 - Addroundkey stage
The Addroundkey step consists of adding a subkey to each byte of the array
Status, by means of a bit-by-bit XOR operation (addition). The key is expanded each round using the AES key expansion, so each round uses a different key derived from the original key, as seen in Figure 8.
Figure 8 - The Addroundkey step
Source: NIST (2001)
12 - Decryption
Decryption consists of a process analogous to encryption, but following the reverse order. The AES algorithm receives the encrypted content and if the key is the same as the one used to encrypt, the final result will be the original message. All ESA operations are easily invertible. In a simple way, it is possible, for example, to rotate the columns to the original State in the Shiftrows step, or know what the original byte is by checking the
row and column containing the byte in the Subbytes step and reconnecting the previous state.
Notes:
The original reference of the algorithm can be obtained through the link: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
In the polynomial representation, multiplication in GF(28) (denoted by ) Corresponds with the multiplication of polynomials modulo an irreducible polynomial of Degree 8. A polynomial is irreducible if its only divisors are one and itself. For the AES Algorithm, this irreducible polynomial is:
The modular reduction by m(x) Nsures that the result will be a Binary polynomial of Degree Less than 8, and Thus can be represented by a byte. Unlike addition, there is no simple Operation at the byte level that Corresponds to this multiplication.
Non-linear substitution table used in several byte substitution Transformations and in the Key Expansion routine to perform a one-for-one substitution of a byte value.
The Subbytes() Transformation is a Non-linear byte substitution that operates independently on each byte of the State using a substitution table (S-box). This S-box (Fig. 7), which is invertible, is constructed by composing
two Transformations.
In the Shiftrows() Transformation, the bytes in the last three Rows of the State are Cyclically shifted over Different Numbers of bytes (offsets). The first Row, r = 0, is not shifted.
The Mixcolumns() Transformation operates on the State column-by-column, treating each column as a fourterm polynomial as described in Sec. 4.3. The Columns are considered as polynomials over GF(28 ) and multiplied module x 4 + 1 with a Fixed polynomial a(x), Given by:
Sources:
BOND, Martin et al. Learn J2EE in 21 days. [S.l.]: Pearson Education do Brasil, 2003.
CORMEN, Thomas H. et al. Algorithms: theory and practice. Rio de Janeiro: Ed. Elsevier, 2002.
FOROUZAN, Behrouz A.; FEGAN, Sophia Chung. Data Communication and Network
Computers. [S.l.]: Mcgraw-Hill, 2008.
KUROSE, James F.; ROSS, Keith W. Computer Network and the Internet: a top-down approach. [S.l.]: Pearson Education, 2010.
RAPPAPORT, Theodore S. Wireless communication: principles and applications. [S.l.]: Pearson Prentice Hall, 2009.
NIST. Announcing the Advanced Encryption standard (aes). Federal Information - Processing Standards Publication 197, n. 197, p. 51, 2001. Available at: <csrc.nist.Gov/Publications/Fips/fips197/Fips-197.pdf>.
Thanks:
To the user mgibsonbr who initially answered this question and showed solidarity by removing my doubts in the comments and in the private chat. Very grateful! Without your knowledge and solidarity, I would never have prepared this answer and my knowledge about the AES algorithm (which is not yet complete and still need to study a lot) would tend to zero.
WOW! When I asked for a detailed explanation, I didn’t expect anyone to answer in such detail. First of all, thank you very much for the time you have spent answering and for all your attention and commitment to help with my question. I have already given you an upvote and I will study your answer during the next week before accepting it as correct. I am also giving a bonus. It’s a small bonus, but it’s what I can offer at the moment. Very grateful! Your reply was excellent!
– Avelino
@Avelino Thanks! Cryptography is a complex subject, it is difficult to give an answer that covers all the relevant points. I would have liked to pay more attention to the S-Box, which is the "heart" of the AES, the main responsible for the non-linearity of the substitution phase, but as I commented in another question of yours, this is much closer to pure mathematics (something I have no experience) than computing. Anyway, it was good because I learned a lot trying to answer your question. This weekend I’ll study the S-Box better and, if successful, I’ll add a little extra to the answer.
– mgibsonbr
Have a very interesting animation about AES: goo.Gl/ceEKsr.
– Lucas Lima
@mgibsonbr Could you, please, indicate me some references (books, articles, theses)? I need to explain the algorithm in detail in my Course Completion Work and I have to indicate some authors. Thankful. I found the NIST article but I was looking for something more didactic. I’ve looked at the Wikipedia links.
– Avelino
@Avelino Unfortunately, my main reference to compose this answer was Wikipedia itself. Everything I know about the AES comes from following discussions on [security.se] and these things I read on Wikipedia. Even, there are some things that I myself did not understand very well (this multiplication in a body of Galois), and I do not know where to look for more information (except for the formal specifications, which as you noticed yourself are somewhat arid).
– mgibsonbr
I think the NIST article will do. It’s all well explained there, just not in a didactic way as your answer :)
– Avelino
Could you help me in a basic math question? During multiplication, why 2x² + 2x are cut? I noticed that 2x² is cut into your example as well. I didn’t understand what you meant by:
esses polinônimos possuem somente 0 ou 1 como fatores, de modo que fatores pares viram 0 e fatores ímpares viram 1
and the reason for this property to "nullify" the polynomials of the equation.– Avelino
@Avelino It’s because the group
GF(2^8)
is built upon theGF(2)
, then the coefficients of the polynomial are only0
or1
and "adding" them means doing thexor
. So there’s no such thing as2x
, if you add up1x
with1x
you’re in reality doing(1 xor 1)x = 0x = nada
. In other words, "normal" arithmetic does not apply, what counts is arithmetic inGF(2)
, where+
isxor
and*
isand
. When I wrote this answer I didn’t understand it 100%, but after rereading the Wikipedia article along with my father (who is a mathematician) it became a little clearer for me rsrs.– mgibsonbr
What about
GF(2⁸)
andGF(2)
what these terms mean?GF(2)
is binary andGF(8)
octal? That acronym means something?– Avelino
@Avelino
GF
means "Galois Field", that in Portuguese would be "Corpo de Galois" ("corpo" mesmo, not "campo"). A field is: a) a set; b) an associative commutative operation with a neutral element in which each element has an inverse, closed in the set (i.e. the result of this operation between members of the set will always produce another member within the set); c) another commutative, associative, distributive operation in relation tob
, with neutral element and all elements have inverse, except the neutral element ofb
, also closed ina
. Convenciona-se chamarb
of "more" andc
...– mgibsonbr
...of "times", but as I said this does not necessarily have anything to do with the usual operations of arithmetic.
GF(2)
is simply a body with two elements (which I called0
and1
, but it could beelefante
andgirafa
and everything would be all right...).GF(2^8)
is a body with256
elements, and in this case are all octuplets formed of elements inGF(2)
(i and..11010011
or "elephant, elephant, giraffe, elephant..."). It is more or less around, but to know more just reading some article on mathematics (try to know what is a ring and a group, it will help to understand the body).– mgibsonbr
I understood. Very grateful for the information, they were very enlightening :) I was breaking my head with the
2*(x² + x)
and trying to eliminate this from the equation :P Sorry to take your time, but you are the only person I have found able to answer these questions.– Avelino