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:
- Cifra: são os algoritmos de criptografia e decriptografia
- 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###
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###
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
ou {01}{1b} na notação hexadecimal.
Por exemplo, 57 ⊗ 83 = c1, pois:
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:
- 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.
- Aplica-se uma transformação afim, que pode ser expressa de forma de matriz como:
###Transformação afim do Rijndael S-Box###
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###
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###
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:
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:
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:
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###
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###
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###
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###
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:#
A referência original do algoritmo pode ser obtida através do 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) 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.
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 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.