AES - Advanced Encryption Standard

Diogo Ventura Nomiya

Algoritmo AES

UFRJ—Redes de Computadores

 

                 O algoritmo Rijndael foi projetado para suportar tamanhos de chave e de bloco variando entre 128, 160, 192, 224 e 256 bits. Apesar disso, o padrão AES utiliza apenas blocos de 128 bits e chaves de 128, 192 e 256 bits.

                 No AES, os blocos de dados são tratados conforme uma matriz bidimensional (de 4 linhas e Nb colunas) de bytes, chamada de estado. Como um bloco de 128 bits equivale a 16 bytes, uma matriz de 16 posições e 4 linhas só pode ter Nb=4 colunas. Como cada coluna representa 4 bytes, ou 32bits, tem-se que Nb=(tamanho_do_bloco/32). Segue abaixo a representação de um estado, onde B_ij é o byte correspondente à linha i e coluna j:

                 Será utilizanda a notação hexadecimal para melhor visualização, onde cada byte é representado por 2 dígitos hexadecimais, como no exemplo:

                 Da mesma forma, o tamanho da chave é Nk=(tamanho_da_chave/32). Assim, para os 3 diferentes tamanhos de chave temos Nk=4, 6 ou 8. O número de rodadas do algoritmo também depende do tamanho da chave. Sendo assim, Nr=10, 12 ou 14.

                 O algoritmo aplica diversas transformações repetidas vezes (Nr vezes) sobre a matriz de estado. A cada rodada, são realizadas 4 operações, chamadas de SubBytes, ShiftRows, MixColumns e AddRoundKey. Todas as rodadas são iguais, com exceção da última, onde não é feita a operação MixColumns. Além disso, a transformação AddRoundKey também é aplicada antes da primeira rodada.

 

Observação

 

                 As multiplicações de 8 bits que forem utilizadas no algoritmo correspondem a multiplicações polinomiais no Campo de Galois ( GF(2⁸) ), representadas por · . Essa operação corresponde à multiplicação dos polinômios seguida do cálculo do resto da divisão por um polinômio irredutível de grau 8. Para o algoritmo AES esse poilnômio irredutível é:

m(x) = x⁸ + x⁴ + x³ + x + 1

                 O resultado da multiplicação, ao ser dividido pelo polinômio m(x), deixa um resto de grau necessariamente menor que 8, podendo então ser representado em um byte.

 

Cifra

                 AddRoundKey

                 Para rodada = 1 até Nr-1

                                  SubBytes

                                  ShiftRows

                                  MixColumns

                                  AddRoundKey

                 Fim Para

                 SubBytes

                 ShiftRows

                 AddRoundKey

Fim Cifra

 

SubBytes

 

                 A transformação SubBytes substitui cada byte da matriz de estado por outro byte, de acordo com uma tabela de substituição, também chamada de S-box. Essa tabela é montada pegando-se o inverso multiplicativo de cada elemento e em seguida aplicando-se a transformação:

                 a_i = b_i Å b_(i+4) Å b_(i+5) Å b_(i+6) Å b_(i+7) Å c_i

                 onde i é o índice de cada bit pertencente a um byte (), B=b₇b₆b₅b₄b₃b₂b₁b₀ é o byte de entrada, A=a₇a₆a₅a₄a₃a₂a₁a₀ é o byte de saída da operação e C é um byte constante de valor 63h, ou 01100011. Esta transformação também pode ser representada da forma matricial:

                 Assim, dado um byte representado por 2 dígitos hexadecimais xy, a substituição é dada de acordo com a tabela:

S-box, contida nas especificações do AES, obtida em [4]

 

                 Como exemplo vamos tomar o byte 01. Ele é seu próprio inverso multiplicativo, já que 01 · 01 mod m(x) = 1

                 Sendo assim, temos que B=000000001 e o byte A é calculado de acordo com:

                 Desta forma, temos que A = 01111100 = 7c, como pode ser visto na S-box.

 

ShiftRows

 

                 Nessa transformação os bytes de cada linha são trocados, de acordo com uma rotação para a esquerda, sendo que o tamanho da rotação depende do número da linha. Considerando-se r o número da linha (contando a partir de zero), isto é, 0 , o número de rotações para uma dada linha é r. Sendo assim, a primeira linha não é rotacionada. A transformação ShiftRows pode ser visualida abaixo:

                 Ou por exemplo:

MixColumns

 

                 A transformação MixColumns opera em cada coluna da matriz de estado, multiplicando-as por uma matriz fixa. A operação é mostrada abaixo:

                 Onde B_i,j corresponde à coluna j de bytes de entrada e A_i,j corresponde à coluna j de saída da operação. Desta forma, o elemento A_0,j por exemplo corresponde a:

                 De forma mais abrangente, temos que :

 

AddRounKey

 

                 Nesta transformação, é adicionada à matriz de estado as Nk chaves da rodada. Cada uma dessas chaves é adicionada a uma coluna diferente do estado, através de uma operação XOR bit a bit. Como o próprio nome já diz, as chaves da rodada mudam a cada rodada. Todas essas chaves são geradas a partir de uma chave principal, conforme será visto adiante.

                 Chamando de R o número da rodada, e considerando , onde R=0 equivale à aplicação da transformação AddRoundKey que ocorre antes da primeira rodada, temos que o número total de chaves usadas é Nb(Nr+1). Considerando-se que essas chaves w_i estão numeradas a partir de zero, temos que o número da chave a ser aplicada à coluna j durante a rodada R é w_k+j, onde k = R*Nb. Esta transformação é ilustrada abaixo:

Expansão da Chave

 

                 Como foi mencionado, o algoritmo AES faz uma expansão da chave principal em Nb(Nr+1) chaves menores, isto é, . Cada uma dessas chaves menores tem o tamanho de 4 bytes, equivalente ao tamanho da coluna. Como exemplo, será considerada uma chave de 128 bits, sendo assim, Nk=4:

                 As Nk primeiras chaves, que são usadas na rodada 0, são formada pela simples divisão da chave principal (128bits = 16 bytes) em Nk chaves menores de 4 bytes cada uma.

                 Todas as outras chaves são geradas iterativamente a partir das iniciais, de acordo com as seguintes funções:

                 SubWord – Análogo ao SubBytes. Transforma cada um dos 4 bytes da palavra segundo a S-box já apresentada, gerando uma palavra também de 4 byes.

                 RotWord – Rotaciona a palabra um byte à esquerda.

                 Rcon(R) – Possui um valor constante a acada rodada, dado por [(02)^R-1 00 00 00] (valores em hexadecimal), onde R é o número da rodada. Deve-se notar que na rodada zero essa função não é utilizada, por isso R-1 nunca é negativo.

                 Assim, para um dado w_i tal que i>3, e Nk= 4 ou 6 (o processo para Nk=8 é um pouco diferente):

                 - se i não for múltiplo de Nk, então w_i = w_i-1 Å w_i-Nk

                 - se i for múltiplo de Nk, então w_i = SubWord(RotWord(w_i-1)) Å Rcon(R) Å w_i-Nk