56

Gostaria de entender como funciona o algoritmo de criptografia AES (Advanced Encryption Standard). Procuro respostas didáticas, que me façam compreender os processos utilizados pelo algoritmo passo-a-passo, dando ênfase a parte lógica e matemática, e se possível, as operações com bits.

Note que não peço exemplos de código, embora sejam válidos para a explicação.

0

3 Respostas 3

77
+100

O AES é uma primitiva criptográfica destinada a compor sistemas de cifragem e decifragem simétrica (i.e. mesma chave para cifrar e decifrar). É uma cifra de bloco, ou seja, opera em blocos de tamanho fixo (128 bits, ou 16 bytes). Como toda cifra de bloco, pode ser transformada numa cifra de fluxo (de modo a operar em dados de tamanho arbitrário) através de um modo de operação, mas isso não vem ao caso aqui. Pode trabalhar com chaves de 128, 192 ou 256 bits (o algoritmo Rijndael, que originou o AES, permite mais tamanhos de chaves).

Em outras palavras, é um algoritmo cuja função direta (cifragem) recebe como entradas um bloco de 128 bits (a mensagem) e uma chave do tamanho escolhido, e devolve uma saída também de 128 bits (a cifra). A função inversa (decifragem) recebe como entrada um bloco de 128 bits (a cifra) e devolve como saída um bloco de 128 bits. Se a chave for a chave correta, essa saída será idêntica à mensagem original.

O objetivo de uma cifra bem sucedida é que seja impraticável se descobrir a mensagem original caso somente se possua a mensagem cifrada, mas não a chave de criptografia. Para isso, busca-se minimizar qualquer correlação visível entre a entrada e a saída, de modo que a mesma (e/ou a chave) possa ser deduzida simplesmente observando-se um número muito grande de cifras (ou de pares mensagem/cifra). Para isso, usa-se uma série de "rodadas" (ou rounds) em que os bytes sofrem transformações não lineares, porém reversíveis (i.e. para decifrar, simplesmente se executa o inverso das mesmas operações, em ordem inversa).

Corpos Finitos

Todas as operações no AES tratam os bytes de entrada como um corpo finito (finite fields, ou Galois fields) em 28. Isso significa que:

  • Há um conjunto [0,255] (que são todos os valores possíveis para um byte) e um desses elementos é chamado "zero" (no caso, o próprio 0);
  • Há uma operação, que chamaremos de "adição", que se aplica a quaisquer dois elementos nesse conjunto e cujo resultado também é um elemento desse conjunto. Essa operação precisa ser associativa, comutativa, possuir elemento neutro, e cada elemento deve ter um inverso;
    • Nesse caso, definimos a "adição" como o "OU exclusivo" - XOR.
  • Há uma operação, que chamaremos de "multiplicação", com características semelhantes à "adição". Exceto pelo elemento "zero", que não tem inverso (e o elemento neutro da multiplicação é chamado de "um"). A multiplicação também precisa ser distributiva em relação à adição.
    • A "multiplicação" será definida adiante.

Para quem não tem experiência com matemática, é bom frisar que estamos definindo "adição", "multiplicação", "zero" e "um" - esses nomes não têm necessariamente nada a ver com as operações aritméticas usuais que fazemos no conjunto dos números Naturais ou Reais (os Naturais ou Inteiros, por exemplo, não formam corpos com o + e * usuais, pois não existe x dentro desses conjuntos tal que 2*x=1; os Reais formam um corpo, só que infinito). Não há "subtração", "divisão", etc.

A adição, como já foi dito, foi definida como sendo o XOR. A multiplicação é mais complexa: primeiro trate cada operando como se fosse um polinômio com base na sua representação binária (ex.: 6 - 110 - vira x^2 + x, e 11 - 1011 - vira x^3 + x + 1), multiplique-os, depois divida o resultado por um "agente redutor". O resto da divisão (interpretado novamente como um número) será então o resultado da multiplicação. No caso do AES, o agente redutor escolhido foi:

x^8 + x^4 + x^3 + x + 1

De modo que multiplicar 6 por 11 é o mesmo que fazer

(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 que os coeficientes são "somados" usando o XOR, não a soma comum: quando se somou x^2 com x^2 o resultado é zero, e não 2*x^2. Pense nessa soma como 1*x^2 + 1*x^2 = (1 xor 1)*x^2 = 0*x^2 = 0. O corpo GF(2^8) foi construído com base no GF(2) (corpo binário, onde a soma é XOR e a multiplicação é AND), de modo que seus polinômios possuem somente 0 ou 1 como coeficientes. Para mais detalhes, a Wikipedia em inglês possui um artigo sobre aritmética em corpos finitos, inclusive uma subseção específica sobre o Rijndael.

A Wikipedia possui um algoritmo simplificado que é equivalente a essa multiplicação de polinômios, porém bem menos custosa (veja no final da seção).

Ou seja, uma implementação [não otimizada] do AES poderia por exemplo criar um tipo de dado distinto para representar cada byte das entradas/saídas/chaves e dar sua própria implementação da "adição" e "multiplicação" (sobrecarregando as usuais, se a linguagem de programação permitir). Isso simplificaria a lógica, às custas da performance.

big disclaimer: não estou sugerindo que leigos implementem AES [para usar na prática] - eu não confio em mim mesmo pra implementar algoritmos criptográficos, muito menos em quem estiver lendo isso... Coloquei isso apenas para fins didáticos, uma implementação real precisa se preocupar inclusive com coisas como side channel attacks (ex.: timing e fault).

  • Nota: A partir de agora, sempre que eu falar em "adicionar" ou "multiplicar" eu me refiro a operações em GF(28), exceto quando houver indicação em contrário.

Rijndael S-Box

Com base nessa aritmética em corpo finito, foi concebida uma tabela de consulta (lookup table) chamada Rijndael S-Box, destinada a transformar um byte em outro diferente, de uma forma não linear. Duas tabelas são usadas: uma para a função direta e outra pra inversa.

  • Em primeiro lugar, calcula-se o inverso multiplicativo do byte (i.e. um byte tal que multiplicado por ele resulta em "um"). O zero não tem inverso, então ele mapeia pra zero mesmo.

  • Em seguida, os oito bits do resultado são submetidos a uma transformação afim, para tornar o método mais resistente contra ataques algébricos:

    [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]
    

Essa tabela foi projetada com o objetivo de ser resistente à criptanálise linear ou diferencial, e permitindo a substituição da transformação afim por outra caso se descubra algum backdoor no futuro. Para efeitos práticos, é uma função invertível cuja saída não se assemelha em nada à entrada (i.e. pequenas alterações na entrada produzem diferenças aparentemente aleatórias na saída).

Expansão da Chave

Como foi dito, o AES possui várias rodadas de cálculo, que parte da mensagem original, aplica uma série de transformações na mesma, e chega ao resultado final (a cifra). Chamarei os dados sendo trabalhados de "estado" (state):

estado = mensagem
estado = round(estado)
estado = round(estado)
estado = round(estado)
...
estado = round(estado)
cifra = estado

Em cada estado, não se usa a chave original de criptografia, mas sim uma série de chaves derivada da mesma. Essa derivação usa um algoritmo chamado Rijndael Key Schedule, e é complexo por si só para ser totalmente explicado aqui (apesar da implementação ser aparentemente curta). Darei apenas uma visão geral, portanto:

  • O AES opera em blocos de 128 bits, como visto, mas usa chaves de 128, 192 ou 256 bits; o algoritmo de expansão de chaves produz portanto um conjunto de sub-chaves de 128 bits - uma para cada round do algoritmo (que por sinal também depende do tamanho da chave: são 10, 12 ou 14 rounds, respectivamente).
  • Partindo-se da chave original, é feita uma série de operações envolvendo a rotação (shift) dos últimos 4 bytes, sua transformação conforme o S-Box, e a adição com uma potência de 2. Há uma pequena variação nas etapas conforme o tamanho de chave utilizado.
    • Por "potência de 2", me refiro a 2 multiplicado por si mesmo N vezes, em GF(28). Como se pode ver nessa tabela, os valores são bem diferentes da aritmética em números inteiros.
  • Uma vez que se produziu bytes suficientes para todos os rounds do algoritmo, conclui-se a expansão da chave.

Rodadas

O algoritmo funciona em rodadas, ou rounds, de modo que em cada uma delas uma série de operações reversíveis é feita em cima do estado. O objetivo é que cada byte da entrada seja "combinado" com vários bytes da chave, de modo que pequenas alterações tanto na chave quanto na mensagem provoquem mudanças significativas na cifra (ver confusion and diffusion). Em outras palavras, se quer evitar que parte da cifra dependa somente de parte da chave, o que permitiria quebrar o problema de decifrar uma chave grande em se decifrar várias chaves menores (o que poderia ser feito por força bruta).

Nota: os bytes do estado são comumente representados em uma matriz 4x4. Essa matriz é por coluna, não por linha (como na maioria das linguagens de programação populares). Ou seja, os 16 bytes são dispostos da seguinte forma:

b0   b4   b8   b12
b1   b5   b9   b13
b2   b6   b10  b14
b3   b7   b11  b15

Quando for mencionado "linha" ou "coluna", refere-se aos 4 bytes do estado correspondentes à representação acima.

  1. Na primeira rodada, o estado é adicionado à chave daquela rodada;

    estado = estado ^ chave(0)
    
  2. Nas rodadas subsequentes:

    1. cada byte do estado é transformado conforme o S-Box;

      para cada byte b no estado:
          estado[b] = S(estado[b])
      
    2. Depois as linhas são rotacionadas à esquerda, da seguinte forma:

      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
      
    3. Depois em cada coluna da matriz seus bytes são combinados com todos os outros bytes da mesma coluna; essa etapa não ocorre na última rodada.

      A descrição detalhada essa etapa pode ser vista aqui. O que é feito é pegar cada coluna da matriz e multiplicá-la por uma matriz fixa, resultando nos novos valores da coluna:

      [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 = 2*a00 ^ 3*a10 ^ 1*a20 ^ 1*a30
      a10 = 1*a00 ^ 2*a10 ^ 3*a20 ^ 1*a30
      a20 = 1*a00 ^ 1*a10 ^ 2*a20 ^ 3*a30
      a30 = 3*a00 ^ 1*a10 ^ 1*a20 ^ 2*a30
      
      ... (idem pras demais colunas)
      

      Pelo meu entendimento, a multiplicação continua sendo a multiplicação em GF(28), mas nesse caso há uma descrição mais simples da mesma: x*1 é x, x*2 é x<<1 e x*3 é x<<1 ^ x. Se o resultado for maior que 255, fazer x ^ 0x1B.

    4. Por fim, soma-se a chave da rodada ao estado.

      estado = estado ^ chave(i)   # onde i é o número da rodada
      

Resumo

Essa série de operações (adicionar chave, substituir, misturar/permutar) é chamada "Substitution-Permutation Network", ou SP-network. Aqui está uma representação gráfica do processo, com 3 rounds:

Diagrama representando a SP-network

Decifragem

O processo de decifrar consiste simplesmente na aplicação do inverso dessas mesmas operações, na ordem inversa naturalmente. Muitas vezes não muda nada entre cifrar e decifrar (ex.: a xor b xor b = a), em outras é necessário alguma adaptação:

  1. Em vez de começar com estado = mensagem e terminar com cifra = estado, agora começamos com estado = cifra e terminamos com mensagem = estado;

  2. A expansão da chave é igual; no início de cada round se adiciona a chave do round correspondente (lembrando que agora estamos fazendo os rounds de trás pra frente), e no final se adiciona a chave do primeiro round;

  3. Para se desfazer a etapa 3 (mistura de colunas) de cada round em que ela se aplica (i.e. todos exceto o primeiro e o último), usa-se a matriz inversa àquela descrita anteriormente:

    [a00]   [14  11  13   9][a00]
    [a10] = [ 9  14  11  13][a10]
    [a20]   [13   9  14  11][a20]
    [a30]   [11  13   9  14][a30]
    

    (como dessa vez não há "atalhos" para a multiplicação, é comum se utilizar outra lookup table em vez de se fazer a conta na hora. Aqui tem as tabelas relevantes.)

  4. A etapa 2 é simplesmente um shift pra direita em vez da esquerda...

  5. Para se desfazer a etapa 1, usa-se uma lookup table que corresponde ao inverso da S-Box.

12
  • 5
    WOW! Quando pedi uma explicação detalhada, não esperava que alguém fosse responder de forma tão detalhada assim. Primeiramente, muito grato pelo tempo que você gastou respondendo e por toda atenção e empenho em ajudar com minha dúvida. Já te dei um upvote e estudarei sua resposta durante a próxima semana antes de aceitá-la como correta. Também estou dando uma bonificação. É uma bonificação pequena, mas é o que posso oferecer no momento. Muito grato! Sua resposta foi excelente!
    – Avelino
    Commented 12/12/2014 às 4:33
  • 4
    @Avelino Obrigado! Criptografia é um assunto complexo, é difícil dar uma resposta que cubra todos os pontos relevantes. Gostaria de ter dado mais atenção ao S-Box, que é o "coração" do AES, o principal responsável pela não linearidade da fase de substituição, mas como comentei em outra pergunta sua isso está bem mais próximo da matemática pura (coisa que não tenho experiência) do que da computação. De todo modo, foi bom porque aprendi bastante ao tentar responder sua pergunta. Nesse fim de semana vou estudar melhor o S-Box e, se tiver sucesso, dou um complemento a mais à resposta.
    – mgibsonbr
    Commented 12/12/2014 às 7:13
  • 6
    Tem uma animação bem interessante sobre AES: goo.gl/ceEKsr.
    – Lucas Lima
    Commented 16/12/2014 às 18:23
  • 1
    @Avelino É porque o grupo GF(2^8) é construído em cima do GF(2), então os coeficientes do polinômio são somente 0 ou 1 e "somar" os mesmos significa fazer o xor. Então não existe isso de 2x, se você soma 1x com 1x você está na realidade fazendo (1 xor 1)x = 0x = nada. Em outras palavras, a aritmética "normal" não se aplica, o que vale é a aritmética em GF(2), onde + é xor e * é and. Quando escrevi essa resposta também não tinha entendido 100%, mas depois relendo o artigo da Wikipedia junto com meu pai (que é matemático) aí ficou um pouco mais claro pra mim rsrs.
    – mgibsonbr
    Commented 8/06/2015 às 19:45
  • 1
    @Avelino GF significa "Galois Field", que em português seria "Corpo de Galois" ("corpo" mesmo, não "campo"). Um corpo é: a) um conjunto; b) uma operação comutativa, associativa, com elemento neutro e em que cada elemento tem um inverso, fechada no conjunto (i.e. o resultado dessa operação entre membros do conjunto sempre produzirá outro membro dentro do conjunto); c) outra operação comutativa, associativa, distributiva em relação à b, com elemento neutro e todos os elementos têm inverso, exceto o elemento neutro de b, também fechada em a. Convenciona-se chamar b de "mais" e c...
    – mgibsonbr
    Commented 8/06/2015 às 19:55
14

Antes de mais nada, minha resposta pretende apenas acrescentar conteúdo a resposta do mgibsonbr, que já é bem completa. Eu tive que fazer uma fundamentação teórica para o meu Trabalho de Conclusão de Curso. Penso que seria muito egoísmo meu, deixar tudo o que eu escrevi somente no papel, então, portanto, resolvi compartilhar o que escrevi com a comunidade. Ainda são necessários alguns aprimoramentos e penso que posso ter cometido alguns deslizes, pois o algoritmo é muitíssimo complexo. Se isto acontecer, sinta-se livre para editar a minha resposta.

1 - Criptografia

Segundo Bond et al. (2003), criptografar dados significa convertê-los de modo que só possam ser decifrados e lidos por usuários autorizados, portanto, a criptografia dos dados exige que um algoritmo seja aplicado a estes dados. A forma de escrever a lógica é denominada de algoritmo, que, segundo Cormen et al. (2002, p. 3), nada mais é do que qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída. Portanto, um algoritmo é uma sequência de passos computacionais que transformam a entrada na saída. Desta forma, um algoritmo de criptografia é um procedimento matemático que contém uma entrada, os dados a serem criptografados, efetua um processamento matemático com base em uma chave, e gera uma saída: os dados criptografados (KUROSE; ROSS, 2010; BOND et al., 2003; RAPPAPORT, 2009; STALLINGS, 2008; FOROUZAN; FEGAN, 2008). Forouzan e Fegan (2008) explica alguns termos utilizados quando nos referimos a criptografia, segundo ele:

  1. Cifra: são os algoritmos de criptografia e decriptografia
  2. Chave: é um número ou conjunto de números sobre o qual a cifra opera.

2 - Criptografia Simétrica

A criptografia simétrica é o tipo de criptografia que utiliza a mesma chave para cifrar e decifrar os dados (FOROUZAN; FEGAN, 2008). Geralmente algoritmos de criptografia simétrica são bastante sofisticados e utilizam chaves de 56 ou 128 bits. Devido ao tamanho e a probabilidade matemática do número e complexidade da chave, um algoritmo de criptografia não pode ser revertido com facilidade, isto significa que, sem a chave, o dado criptografado demoraria centenas de anos para ser decifrado em um ataque de força bruta, isto se, somente se, o algoritmo que criptografou este dado for suficientemente robusto (BOND et al., 2003).

A criptografia simétrica é usada para garantir a confidencialidade de determinado dado e garante que apenas os destinatários autorizados, aqueles que conheçam a chave de decifração, possam recuperar os dados originais (BOND et al., 2003).

Um exemplo de cifra simétrica é o algoritmo AES, do inglês: Advanced Encryption Standard, que é uma evolução do DES e foi desenvolvido porque a chave do DES era muito curta. O AES é uma cifra cíclica muito complexa e foi projetado com três tamanhos de chave: 128, 192 ou 256 bits (FOROUZAN; FEGAN, 2008).

3 - Criptografia Assimétrica

A criptografia assimétrica é aquela que utiliza algoritmos diferentes de criptografia simétrica e exige o uso de duas chaves: a chave privada, que é mantida em segredo pelo proprietário e utilizada para criptografar dados, e a chave pública, que é conhecida por pessoas autorizadas pelo proprietário da chave privada e é utilizada para decifrar os dados (FOROUZAN; FEGAN, 2008). Porém, se um dado é criptografado com a chave pública, somente o proprietário da chave privada pode decifrar este dado (BOND et al., 2003)

4 - O Algoritmo AES

O algoritmo Advanced Encryption Standard, ou simplesmente AES, é um algoritmo de criptografia simétrica por blocos de 128 bits (16 bytes), desenvolvido desde 1997 por Vincent Rijmen e Joan Daemen, e anunciado em 26 de novembro de 2001 pelo NIST, (National Institute of Standards and Technology) Instituto Nacional de Padrões e Tecnologia dos EUA em tradução livre (NIST, 2001)1.

O algoritmo AES possui chaves de 128 bits, 192 ou 256 bits ou 16, 24 e 32 bytes respectivamente. Entende-se por chave o conjunto de dados digitais sobre o qual a cifra opera (FOROUZAN; FEGAN, 2008). Por se tratar de um algoritmo de criptografia simétrica com blocos de 128 bits, a função de cifragem, que é a função responsável por transformar e embaralhar os dados, recebe blocos de 16 bytes (128 bits) por vez e devolve, também, 16 bytes por vez. Chama-se o conjunto de blocos que será encriptado de "mensagem", e o conjunto retornado pela função de cifragem de "cifra". O processo de decifragem é feito de forma análoga, porém, contrária ao de cifragem e, portanto, recebe um conjunto de blocos cifrados (cifra) e devolve a mensagem idêntica a original, se, somente se, a chave for a mesma que foi utilizada para encriptar os dados. O processo de cifragem também pode ser chamado de encriptação ou mesmo "criptografia", da mesma forma que o processo de decifragem é sinônimo de "decriptação"ou "descriptografia"(NIST, 2001). A Figura 1 mostra um pseudocódigo do algoritmo AES, as etapas do algoritmo são explicadas posteriormente.

Figura 1 - Pseudo código do AES

inserir a descrição da imagem aqui

Fonte: Adaptado de NIST (2001, tradução nossa)

5 - O Estado

Internamente, as operações do algoritmo AES são realizadas em uma matriz bidimensional de bytes chamadas de "Estado" (s). O Estado consiste em um array organizado em 4 colunas de bytes, cada uma contendo 4 bytes, 16 bytes ao todo, sendo que os valores de cada byte variam de 0 a 255. Durante o processo de cifragem ou decifragem, os blocos de 128 bits (16 bytes) são copiados para este array, para que sejam efetuadas as operações responsáveis pelo funcionamento do algoritmo nesta cópia (NIST, 2001). A Figura 2 ilustra os blocos de entrada, o array Estado e os blocos de saída, sendo que cada item corresponde a um byte:

Figura 2 - Blocos de entrada, Estado e blocos de saída

inserir a descrição da imagem aqui

Fonte: Adaptado de NIST (2001, tradução nossa)

6 - Operação de adição ⊕

A adição nada mais é do que uma soma dos bits, conhecida como operação XOR (OU Exclusivo), também chamada de "disjunção exclusiva". É uma operação lógica entre dois operandos que resulta em um valor lógico verdadeiro se, e somente se, exatamente um dos operandos possui valor verdadeiro. Pode ser sintetizado como um detector de diferenças entre dois operandos lógicos (NIST, 2001) e é representada por ⊕.

7 - Operação de multiplicação ⊗

Em se tratando do algoritmo AES a multiplicação é a representação polinominal GF(28) (indicado por ⊗), ou seja, corresponde a multiplicação de polinômios modulo em polinômios irredutíveis de grau 8. Um polinômio é irredutível se seus únicos divisores são um e ele mesmo (NIST, 2001, tradução nossa). Para o algoritmo AES, este polinômio irredutível é: 2

inserir a descrição da imagem aqui

ou {01}{1b} na notação hexadecimal.

Por exemplo, 57 ⊗ 83 = c1, pois:

inserir a descrição da imagem aqui

O x7 + x6 + 1, obtido como resultado, pode ser escrito como x7 + x6 + 0x + 0x + 0x + 0x + 0x + 1 corresponde a: {11000001} em binário, que é equivalente a {c1} hexadecimal.

Os agentes 2x2 e 2x foram cortados pois estes polinônimos só possuem 0 e 1 como fatores, de modo que fatores pares viram 0 e fatores ímpares viram 1.

A redução modular por m(x) garante que o resultado será um binário polinomial de grau inferior a 8, e, assim, pode ser representado por um byte. Ao contrário disso, não há nenhuma operação simples no nível de byte que corresponde a esta multiplicação (NIST, 2001, tradução nossa)3.

Portanto, de forma simples, entende-se que a operação de multiplicação é a representação do polinômio na sua representação binária, feito uma multiplicação dos agentes dessa equação e posteriormente divididos pelo agente redutor (operação de módulo). O resto desta divisão será então o resultado da operação de multiplicação. No caso do AES, foi escolhido o agente redutor citado na Equação 2.1

8 - Rijndael S-Box e a Etapa de SubBytes

O Rijndael S-Box, ou simplesmente S-Box, trata-se de uma matriz quadrada, não-linear, utilizada como tabela de substituição em diversas transformações de byte. Também é utilizada em rotinas de expansão de chaves de valores um-para-um em bytes. No algoritmo AES é utilizada na etapa de SubBytes e durante a expansão de chave (Key Expansion)4 (NIST, 2001, tradução nossa).

A etapa de SubBytes, ou transformação de SubBytes, é uma substituição não linear que opera de forma independente em cada byte do array de estado usando a tabela de substituição Rijndael S-Box (NIST, 2001, tradução nossa). A Rijndael S-Box é revertível, e é construída pela composição de duas transformações5:

  1. Calcula-se o inverso multiplicativo do byte, ou seja, um byte tal que multiplicado por ele mesmo, resulta em 1. O elemento 0 (zero) é mapeado para ele mesmo.
  2. Aplica-se uma transformação afim, que pode ser expressa de forma de matriz como:

Transformação afim do Rijndael S-Box

inserir a descrição da imagem aqui

Fonte: Adaptado de NIST (2001)

Durante a etapa de SubBytes, os bytes do array Estado são substituídos a partir da S-Box, gerando valores diferentes e, aparentemente aleatórios. A S-Box utilizada nesta etapa é apresentada na Figura 3.

Figura 3 - S-Box em notação hexadecimal

inserir a descrição da imagem aqui Fonte: Adaptado de NIST (2001)

Por exemplo, se temos a posição Estado1,1 = {53}, então o valor da substituição será determinado pela intersecção da linha de índice 5 e coluna de índice 3, ilustradas na Figura 3. Portanto, o resultado da substituição na posição Estado1,1 será de {ed}.

9 - Etapa de ShiftRows

Na etapa ShiftRows, os bytes das três últimas linhas do Estado são deslocados ciclicamente ao longo de diferentes números de bytes (offsets) 6 (NIST, 2001, tradução nossa). Somente a primeira linha, não é deslocada. A Figura 4 ilustra este processo e destaca os bytes que foram transpostos.

Figura 4 - A etapa ShiftRows

inserir a descrição da imagem aqui

Fonte: Adaptado de NIST (2001)

10 - Etapa MixColumns

A etapa MixColumns opera sobre o Estado coluna por coluna, e trata cada coluna como um polinômio de quatro termos (NIST, 2001, tradução nossa), conforme a equação a seguir7:

inserir a descrição da imagem aqui

As colunas são consideradas como polinômios e multiplica-se pelo módulo x4 + 1 com um polinômio fixo a(x), dada pela equação:

inserir a descrição da imagem aqui

Portanto, o resultado da etapa MixColumns sobre o array Estado, que é representado por s´(x), é a multiplicação do polinômio descrito na Equação 2.9 por elementos do array de Estados s(x) que pode ser escrito como:

inserir a descrição da imagem aqui

Sendo a(x) e s(x) a representação de matrizes, e elementos dessas matrizes, é possível representar a Equação 2.10 em forma de uma multiplicação de matrizes, tal qual como no artigo do NIST sobre o AES, assim sendo, a representação equivalente pode ser vista na Figura 5 (NIST, 2001).

Figura 5 - Representação em forma de matriz para a etapa MixColumns

inserir a descrição da imagem aqui

Fonte: Adaptado de NIST (2001)

Com o resultado desta multiplicação, os quatro bytes de uma coluna são substituídos, elemento a elemento, como é mostrada na Figura 6, logo a seguir:

Figura 6 - Elementos a serem substituídas na etapa MixColumns

inserir a descrição da imagem aqui

Fonte: Adaptado de NIST (2001)

Após a multiplicação, os elementos s0,c , s1,c , s2,c e s3,c do array Estado, que juntos formam uma coluna c, são substituídos pelos elementos s'0,c , s'1,c , s'2,c e s'3,c , concluindo a etapa MixColumns, como é mostrado na Figura 7.

Figura 7 - A etapa MixColumns

inserir a descrição da imagem aqui

Fonte: NIST (2001)

11 - Etapa AddRoundKey

A etapa AddRoundKey consiste em adicionar uma sub-chave em cada byte do array Estado, por meio de uma operação XOR bit a bit (adição). A chave é expandida a cada rodada usando a expansão de chaves do AES, de forma que em cada rodada utiliza-se uma chave diferente, derivada da chave original, conforme é visto na Figura 8.

Figura 8 - A etapa AddRoundKey

inserir a descrição da imagem aqui

Fonte: NIST (2001)

12 - Decriptação

A decriptação consiste em um processo análogo ao de encriptação, porém seguindo a ordem inversa. O algoritmo AES recebe o conteúdo encriptado e se a chave for a mesma que a utilizada para encriptar, o resultado final será a mensagem original. Todas as operações do AES são facilmente invertíveis. De uma forma simples, é possível, por exemplo, rotacionar as colunas ao Estado original na etapa de ShiftRows, ou saber qual o byte original verificando a linha e coluna que contém o byte na etapa de SubBytes e recontruindo o Estado anterior.

Notas:

  1. A referência original do algoritmo pode ser obtida através do link: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

  2. 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:

  3. The modular reduction by m(x) ensures 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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 modulo x 4 + 1 with a fixed polynomial a(x), given by:

Fontes:

BOND, Martin et al. Aprenda J2EE em 21 dias. [S.l.]: Pearson Education do Brasil, 2003.

CORMEN, Thomas H. et al. Algoritmos: teoria e prática. Rio de Janeiro: Ed. Elsevier, 2002.

FOROUZAN, Behrouz A.; FEGAN, Sophia Chung. Comunicação de Dados e Rede de Computadores. [S.l.]: McGraw-Hill, 2008.

KUROSE, James F.; ROSS, Keith W. Rede de Computadores e a Internet: uma abordagem top-down. [S.l.]: Pearson Education, 2010.

RAPPAPORT, Theodore S. Comunicação sem fio: princípios e aplicações. [S.l.]: Pearson Prentice Hall, 2009.

NIST. Announcing the advanced encryption standard (aes). Federal Information - Processing Standards Publication 197, n. 197, p. 51, 2001. Disponível em: <csrc.nist.gov/publications/fips/fips197/fips-197.pdf>.

Agradecimentos:

Ao usuário mgibsonbr que respondeu inicialmente esta pergunta e se mostrou solidário tirando minhas dúvidas nos comentários e no chat privado. Muitíssimo grato! Sem o seu conhecimento e a sua solidariedade, jamais teria elaborado essa resposta e meu conhecimento sobre o algoritmo AES (que ainda não é completo e ainda preciso estudar muito) tenderia a zero.

1

Em criptografia, o Advanced Encryption Standard (AES, ou Padrão de Criptografia Avançada em português), também conhecido por Rijndael, é uma cifra de bloco adotada como padrão de criptografia pelos EUA.

Espera-se que seja utilizado em todo o mundo e analisado extensivamente, assim como foi seu predecessor, o data Encryptation Standard (DES). O AES foi anunciado pelo NIST (Instituto Nacional de Padrões e Tecnologia dos EUA) como U.S. FIPS PUB (FIPS 197) em 26 de novembro de 2001, depois de 5 anos de um processo de padronização. Tornou-se um padrão efetivo em 26 de maio de 2002. Em 2006, o AES já é um dos algoritmos mais populares usados para criptografia de chave simétrica.

O AES tem um tamanho de bloco em 128 bits e uma chave com tamanho de 28, 192 ou 256 bits, enquanto o Rijndael pode ser espeficiado com chaves e tamanhos de bloco de qualquer múltiplo de 32 bits, com um mínimo de 128 bits e um máximo de 256 bits.

A chave é expandida usando-se o agendamento de chaves do Rijndael. A maioria dos cálculos do AES é feita em um campo finito próprio. O AES opera sobre um arranjo bidimensional de bytes com 4x4 posições, denominado estado (as versões do Rijndael com um tamanho de bloco maior têm colunas adicionais no estado).

Para criptografar, cada turno do AES (exceto o último) consiste em quatro estágios (como já estão ilustrados nas demais respostas):

  1. AddRoundKey - cada byte do estado é combinado com a subchave própria do turno (RoundKey); cada subchave é derivada da chave principal usando o algoritmo de agendamento de chaves.

  2. SubBytes - é uma etapa de substituição não linear onde cada byte é substituído por outro de acordo com uma tabela de referência.

  3. ShiftRows - é uma etapa de transposição onde cada fileira do estado é deslocada de um determinado número de posições.

  4. MixColumns - é uma operação de mescla que opera nas colunas do estado e combina os quatro bytes de cada coluna usando uma transformação linear. O turno final substitui o estágio de MixColumns por um novo estágio de AddRoundKey.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .