Advanced Encryption Standard

Entendendo o Rijndael

Por Rafael Santiago

• Sobre o algoritmo

O Rijndael foi o vencedor do concurso proposto pelo NIST o AES. Que tinha como objetivo adotar como padrão de criptografia (substituto do DES) o algoritmo vencedor. O Rijndael foi adotado a partir de outubro de 2001. Ele encripta blocos de 128, 192 ou 256 bits, o tamanho da chave pode ser de 128, 192 ou 256 bits. A diferença é no total de iterações durante o processo de cifragem. Nesse texto será explicada a versão 128 bit. Que incluem 10 iterações.

O Rijndael é imune pelo menos até agora, a qualquer tipo de criptoanálise, sendo que o único ataque possível é o brute force. Ou seja, tentar quebrar o criptograma testando todo o espaço de chaves possíveis do algoritmo.

Ele foi criado por Vincent Rijmen e Joan Daemen.

Os algoritmos que concorreram com o Rijndael foram: MARS, RC6, Serpent e Twofish.

Expansão das chaves

Bom, a expansão das chaves não é muito complexa... Vamos inicializar o Rijndael com a seguinte chave: 172637263716273627162736ddbdeffa. Note que a chave tem 128 bits. Que dá 32 caracteres hexadecimais. 4 X 32 = 128. Pois cada caractere Hexa expressa um valor de 4 bits. A expansão das chaves faz uso de uma Caixa-S 16X16 com 256 valores hexadecimais, que serão mostrados mais adiante, e também usa uma matriz 4X10 chamada Rcon, com valores também previamente setados.

Com isso em mente beleza. Agora vou passar a chave hexadecimal para formato binário. Para poder explicar tudo com mais detalhes.

K=172637263716273627162736ddbdeffa

K=00010111001001100011011100100110001101110001011000100111001101100010011100010110001001110011011011011101101111011110111111111010

É mais fácil você jogar a chave em uma matriz 4X4, eu vou fazer isso.

17 37 27 dd 26 16 16 bd 37 27 27 ef 26 36 36 fa

Nossa chave em binário no formato 4 x 4

00010111001101110010011111011101 00100110000101100001011010111101 00110111001001110010011111101111 00100110001101100011011011111010

Note na primeira linha que 0001 = 1 e 0111 = 7 e 0011 = 3 e 0111=7, basta pegar cada número da linha e converter para hexadecimal de 4 bits, visto que cada digito hexadecimal pode ser expresso usando-se 4 bits.

Com base na nossa matriz binária, pega-se a 4ª coluna:

00010111001101110010011111011101 00100110000101100001011010111101 00110111001001110010011111101111 00100110001101100011011011111010

E realiza uma rotação cíclica para esquerda(ShiftRows). Ou seja, o elemento de cima passa a ser o de baixo de todos e o segundo agora será o primeiro.

11011101 10111101 11101111 11111010

Após a rotação

10111101 11101111 11111010 11011101

Note que o valor dd foi para baixo e bd está no topo da coluna.

Logo em seguida realiza-se a operação SubBytes, que com base em uma S-Box. Substitui os elementos dessa coluna.

Pegando o primeiro elemento da coluna. Que é 10111101. Você deve dividi-lo em duas parte de 4 bits e L=1011 C=1101. Essas duas frações serão usadas para endereçar a Sbox, lá nesse endereço terá um valor, o que você tem que fazer é substituir o valor inicial 10111101 da coluna por SBOX[L][C]. Realizar essa operação com os outros 3 valores da coluna...

Nesse exemplo 10111101 será substitido por S-BOX[L][C]=7A que em binário é expresso como 01111010. Após essa transformação a coluna terá essa configuração.

01111010 11011111 00101101 11000001

Depois você deve fazer um XOR desse resultado com a primeira coluna.

01111010110111110010110111000001(4ª coluna transformada) 00010111001001100011011100100110 (1ª coluna) 01101101111110010001101011100111(resultado)

Logo depois pega-se esse resultado e faz um XOR com a primeira coluna de RCon, que no caso é 01,00,00,00.

01101101111110010001101011100111(4ª coluna transformada) 00000001000000000000000000000000(1ª coluna de RCon) 01101100111110010001101011100111(resultado)

Esse resultado passa a ser a primeira coluna de Round Key 1, que será a primeira sub-chave das 10 sub-chaves usadas.

Primeira coluna de Round Key 1

01101100 11111001 00011010 11100111

Logo depois pega-se a segunda coluna da nossa chave.

00110111 00010110 00100111 00110110

E faz um XOR com a 1ª coluna de Round Key 1

01101100111110010001101011100111 00110111000101100010011100110110 01011011111011110011110111010001

Esse resultado passa a ser a segunda coluna de Round Key 1

01011011 11101111 00111101 11010001

Depois pega-se a 2ª coluna de Round Key 1 e XOR com a 3ª coluna da chave.

01011011111011110011110111010001 00100111000101100010011100110110 01111100111110010001101011100111

Esse resultado passa a ser a 3ª coluna de Round Key 1

01111100 11111001 00011010 11100111

Depois pega-se essa 3ª coluna de Round Key 1 e XOR com a 4ª coluna da chave.

01111100111110010001101011100111 11011101101111011110111111111010 10100001010001001111010100011101

Esse resultado passa a ser a 4ª coluna de Round Key 1 e com isso você terá obtido a primeira das 10 sub-chaves.

4ª coluna de Round Key 1

10100001 01000100 11110101 00011101

Round Key 1 completo com diferenciação de cores haha!

01101100010110110111110010100001 11111001111011111111100101000100 00011010001111010001101011110101 11100111110100011110011100011101

Agora para você gerar a segunda, Round Key você terá que pegar a 4ª coluna da Round Key 1 fazer uma rotação cíclica(RoundShift) para esquerda, enfim tudo que você fez para conseguir a Round Key 1 só que agora ao invés de usar a chave você usará a Round Key 1, também é importante dizer que quando você for fazer o XOR com a coluna de RCon você deverá pegar a próxima coluna, no caso para gerar a segunda Round Key você usará a coluna 2. Ai depois para conseguir Round Key 3 repete tudo usando Round Key 2 e a 3ª coluna de RCon... Assim até você conseguir as 10 sub-chaves.

Vou colocar aqui a configuração de Rcon.

01 02 04 08 10 20 40 80 1b 36 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

E os valores da S-BOX… Importante ressaltar que você deve usar as posições [0][0] da matriz, isso é legal dizer para quem está acostumado a programar em linguagens que não é de costume fazer isso, como o Pascal/Object Pascal por exemplo. Onde rotineiramente se declara array[1..10] of integer... declare array[0..9] of integer...(EXEMPLO!) ;)

S-Box

63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Em relação à expansão das chaves é só... Agora vamos entender como o Rijndael cifra um bloco.

Rijndael Cifrando um bloco

Na cifragem se utiliza as duas transformações envolvidas na expansão das chaves, a rotação cíclica para esquerda(ShiftRows) e a busca na S-BOX(SubBytes). Além dessas duas também existem outras duas transformações: o AddRoundKey(um XOR entre o plaintext e a chave corrente) e MixColumns(Uma multiplicação por uma matriz pré-configurada). Mais a frente todas essas operações serão tratadas com mais detalhes.

Por hora você deve entender que o cifrador recebera um texto plano(plaintext) de 128 bits. E utilizará a chave e também as outras 10 sub-chaves.

Vamos cifrar o seguinte texto: “That was so real”

Que em hexadecimal ficará: 546861742077617320736F207265616C

Lembrando que o cifrador já foi inicializado com a chave do exemplo...

Texto para binário:

01010100011010000110000101110100001000000111011101100001011100110010000001110011011011110010000001110010011001010110000101101100

Para ficar mais fácil como a chave e as sub-chaves, vamos jogar o texto plano em uma matriz 4X4.

01010100001000000010000001110010 01101000011101110111001101100101 01100001011000010110111101100001 01110100011100110010000001101100

Pronto!... a primeira coisa a fazer é realizar a transformação AddRoundKey. Que consiste em um XOR entre o texto plano e a chave daquele passo.

O RoundKey inicial não é efetuado com nenhuma sub-chave mas sim com a chave, que se originaram todas as outras sub-chaves.

Então:

(Texto Plano) 01010100001000000010000001110010 01101000011101110111001101100101 01100001011000010110111101100001 01110100011100110010000001101100 (Chave) XOR 00010111001101110010011111011101 00100110000101100001011010111101 00110111001001110010011111101111 00100110001101100011011011111010 (Resultado) 01000011000101110000011110101111 01001110011000010110010111011000 01010110010001100100100010001110 01010010010001010001011010010110

Basta XOREAR Linha n do Texto Plano com Linha n da Chave...

Depois você entrará no Passo 2 da encriptação que serão usadas as 10 sub-chaves, a partir da Round Key 1.

A primeira transformação a ser realizada é o SubBytes, que substitui um byte no texto plano por um byte encontrado em um endereço linha e coluna na S-BOX, essa linha e coluna é ditada pelo próprio valor no texto plano a ser substituído.

01000011000101110000011110101111 01001110011000010110010111011000 01010110010001100100100010001110 01010010010001010001011010010110

Pegando o primeiro byte 01000011 você o divide em duas frações de 4 bits 0100|0011. A primeira fração endereça a linha da S-BOX e a segunda endereça a coluna. O valor que estiver neste endereço substitui o byte no texto plano.

Neste caso 01000011 será substituído por 00011010. Com isso você deverá fazer essa transformação em todos os bytes subseqüentes do plaintext.

Essa operação já foi explicada na geração de chaves, só falei de novo para fixar melhorrr... haha! Podre!

Logo depois da transformação SubBytes o texto plano terá esta “aparência”.

00011010111100001100010101111001 00101111111011110100110101100001 10110001010110100101001000011001 00000000011011100100011110010000

A próxima transformação a ser efetuada é a ShifRows, que consiste em fazer um deslocamento cíclico à esquerda com cada linha da matriz de texto plano. A primeira linha não sofre nenhum deslocamento, a 2ª linha sofrerá o deslocamento de 1 byte, a 3ª de 2 bytes e a 4ª de 3 bytes.

Como aqui na nossa “estrutura de dados” de exemplo, o texto plano está representado bit a bit nos “miiiiinimos detalhes”. Deslocar 1 byte à esquerda significa deslocar 8 vezes(bits) a esquerda. Logo 2 bytes 16 vezes e 3 bytes 24 vezes.

Após essa transformação o texto plano terá esta configuração:

00011010111100001100010101111001 11101111010011010110000100101111 01010010000110011011000101011010 10010000000000000110111001000111

Note que a primeira linha não foi mexida hein?...

Agora vem a multiplicação, essa transformação é chamada de MixColumns. Com base em uma matriz com valores pré-setados, você multiplica cada 32 bytes por ela, logo cada coluna da matriz de texto plano, sendo que em cada coluna você deve pegar 1 byte(8 bits). Existem várias formas de realizar esta multiplicação, talvez esta não seja a mais eficiente, porém funciona...

Matriz M 02 01 01 03 03 02 01 01 01 03 02 01 01 01 02 03

O jeito que vou explicar utiliza a matriz M neste formato. Você apenas pega uma coluna do texto plano. E multiplica cada bit dela por cada bit de cada linha.

Matriz M 01000000110000001000000010000000 00100000011000000100000001000000 00010000001100000010000000100000 10001000100110000001000000010000 10000100100011000000100000001000 00000010000001100000010000000100 10000001100000110000001000000010 10000000100000010000000100000001 10000000010000001100000010000000 01000000001000000110000001000000 00100000000100000011000000100000 00010000100010001001100000010000 00001000100001001000110000001000 00000100000000100000011000000100 00000010100000011000001100000010 00000001100000001000000100000001 10000000100000000100000011000000 01000000010000000010000001100000 00100000001000000001000000110000 00010000000100001000100010011000 00001000000010001000010010001100 00000100000001000000001000000110 00000010000000101000000110000011 00000001000000011000000010000001 11000000100000001000000001000000 01100000010000000100000000100000 00110000001000000010000000010000 10011000000100000001000010001000 10001100000010000000100010000100 00000110000001000000010000000010 10000011000000100000001010000001 10000001000000010000000110000000

00011010111011110101001010010000(Coluna 1 do texto plano) 01000000110000001000000010000000(Linha 1 Matriz M) 00000000110000000000000010000000(Resultado)

Note que a multiplicação é apenas uma operação AND. Depois você deve realizar um XOR entre os bits do Resultado do AND entre Linha de M e Coluna do Texto Plano.

0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 1 XOR 1 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 1 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 = 1

Uma forma mais fácil de você fazer esta operação é simplesmente contar a quantidade de bits setados (em 1) no resultado da multiplicação. Se for múltiplo de 2 (deixa resto 0 na divisão por dois) o resultado é 0 pois em uma operação de XOR os bits setados se anularão, caso não seja múltiplo de 2 o resultado será 1.

Resumo: PAR = 1 IMPAR = 0

O Bit desde calculo será o nosso primeiro bit do resultado do MixColumns, porém você deve calcular os outros 31 bits. Procedendo da mesma forma, usando a mesma coluna do texto plano, só que agora com a 2ª linha da Matriz M. Isso lhe dará o segundo bit... até o 32ª bit. Com isso você deverá pegar este valor de 32 bits e substituir pela coluna 1 do texto plano, em seguida fazer o mesmo cálculo com todas as 3 colunas restantes do texto plano.

Após a transformação MixColumns a primeira coluna do texto plano será:

11011100 10111001 11111010 10101000

A configuração final do texto plano após o MixColumns transformar todas as 4 colunas será:

11011100001101011110110110011110 10111001010000011010000110001110 11111010100011110110111100101011 10101000010111110101100001110000

A próxima transformação é a AddRoundKey, que foi a primeira transformação realizada, usando a chave. Só que agora ao invés de usar a chave para fazer um XOR com o texto plano usaremos a Round Key 1, ou seja, nossa primeira sub-chave.

(Texto Plano) 11011100001101011110110110011110 10111001010000011010000110001110 11111010100011110110111100101011 10101000010111110101100001110000 (Round Key 1) 01101100010110110111110010100001 11111001111011111111100101000100 00011010001111010001101011110101 11100111110100011110011100011101 (Resultado) 10110000011011101001000100111111 01000000101011100101100011001010 11100000101100100111010111011110 01001111100011101011111101101101

Depois você deve refazer tudo de novo a partir do passo 2. Só que agora no AddRoundKey, você usará a próxima sub-chave, que no exemplo seria a Round Key 2, pois estaríamos na 2ª rodada do algoritmo. Isso você deve fazer até o 9º Round, no 10º você não faz a transformação mixColumns. No 10º você apenas fará: SubBytes, ShiftRows e AddRoundKey.

Após as 10 iterações o texto plano será igual a:

11100010111101011011001100000110 11000000011101111001100111010000 10111101111011101111110101000000 00101111100000010001001100100010

Que em hexadecimal é: E2C0BD2FF577EE81B399FD1306D04022.

Na decifragem você deve utilizar as chaves em modo inverso. Bem como o inverso do SubBytes(usando a S-BOX com a configuração inversa) e também o inverso da MixColumns(usando a matriz inversa para poder voltar o resultado que gerou o produto), também se deve evetuar o ShiftRows inverso voltando o quanto foi deslocado.

S-BOX inversa: 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06 d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d

Matriz M inversa: 01110000110100001011000010010000 10111000111010001101100011001000 01011100111101000110110011100100 00101110111110101011011001110010 01100111001011011110101110101001 01000011110001100100010111000100 00100001111000111010001001100010 11100000101000010110000100100001 10010000011100001101000010110000 11001000101110001110100011011000 11100100010111001111010001101100 01110010001011101111101010110110 10101001011001110010110111101011 11000100010000111100011001000101 01100010001000011110001110100010 00100001111000001010000101100001 10110000100100000111000011010000 11011000110010001011100011101000 01101100111001000101110011110100 10110110011100100010111011111010 11101011101010010110011100101101 01000101110001000100001111000110 10100010011000100010000111100011 01100001001000011110000010100001 11010000101100001001000001110000 11101000110110001100100010111000 11110100011011001110010001011100 11111010101101100111001000101110 00101101111010111010100101100111 11000110010001011100010001000011 11100011101000100110001000100001 10100001011000010010000111100000

O ShiftRows inverso, tem gente que prefere deslocar para direita voltando assim os bits. Mas você pode continuar deslocando para a esquerda, mudando apenas a quantidade de bytes em cada linha. Eu faço assim.

Exemplo:

Na encriptação a 2ª linha é deslocada 1 byte à esquerda. Na desencriptação, você deve deslocar 3 bytes(24 bits) à esquerda, para voltar o que foi feito na cifragem. De forma semelhante a 3ª linha você deverá deslocar 2 bytes(16 bits). E a 4ª linha 1 byte(8 bits).

Note que apenas a 3ª linha é deslocada o mesmo tanto, na cifragem e na decifragem. As outras duas linhas trocam entre si o grau de deslocamento do processo de cifragem no de decifragem.

Agora a ordem das sub-chaves... Na decifragem o AddRoundKey entre o texto plano e a chave. Será a última coisa a ser feita. Na decifragem você já entra no Passo 2, só que utilizando a 10ª Round Key, tomando cuidado para não esquecer que com a 10ª Sub-chave não há a transformação MixColumns, apenas da 9ª em diante... Lembre-se de usar o inverso das transformações: SubBytes, Shift-Rows e Mix-Columns. O inverso do XOR é só fazer de novo. Oh....

Além do inverso das transformações, você também deve usá-las em ordem invertida.

Na cifragem você usa:

SubBytes|ShiftRows|MixColumns|AddRoundKey

Na decifragem você usá:

AddRoundKey|MixColumns|ShiftRows|SubBytes

A ordem de ShiftRows e SubBytes, não influem em nada...

Pra quem se interessou

Disponibilizei uma versão do algoritmo em C, com o executável caso queira apenas utilizar o programa e com o fonte caso queira estudar. Se alterar o fonte, altere contanto que preserve os meus créditos e que documente suas alterações e também coloque o seu nome no fonte.

Existe também uma animação em flash na net que explica de forma bem visual o funcionamento do algoritmo, caso já esteja familiarizado com algum algoritmo criptográfico, contemporâneo, em especial block ciphers, acho que você não terá problemas em entender o processo. Cuidado apenas no “KeySchendule”(Expansão das chaves), a 2ª coluna, se não me engano do Round Key 1 foi representada de maneira errada, porém o exemplo de cifragem, e cada passo das transformações, estão corretas. É bem legal e vale a pena. O exemplo abordado é o mesmo presente nos documentos do NIST explicando o algoritmo.

Bibliografia & Sites

“Rijndael Cipher” – Animação por Enrique Zabala/Universidade CRT/Montevideo/Uruguay.

Relatório “Criptanálise Diferencial do Cifrador Rijndael” – Mehran Mishagi/São Paulo – 11/2003.

Relatório técnico “Rijndael – Um Algoritmo no Estilo DES” – Jorge de A. Lambert/José Antônio M. Xéxeo/Almir Paz de Lima – 02/2003.

Sites:

http://wikipedia.org http://google.com http://pt.wikipedia.org/wiki/Lista_de_Algoritmos