Criptografia Numaboa
O algoritmo DES ilustrado II
|
Seg 29 Ago 2005 01:53 |
- Detalhes
- Categoria: Cifras de bloco
- Atualização: Segunda, 20 Abril 2009 13:37
- Autor: vovó Vicki
- Acessos: 37105
No artigo "O algoritmo DES ilustrado" você encontra um pouco da história do DES. Neste artigo, vamos fazer uma radiografia deste algoritmo, bit a bit 
Exemplos preliminares de DES
O DES trabalha com bits ou números binários - os 0s e 1s dos computadores digitais. Cada grupo de 4 bits corresponde a um valor hexadecimal, cuja base é 16. O binário "0001" corresponde ao número hexadecimal "1", o binário "1000" é igual ao número hexadecimal "8", "1001" é igual ao hexadecimal "9", "1010" é igual a o hexadecimal "A" e "1111" é igual ao hexadecimal "F".
O DES funciona encriptando grupos de 64 bits de mensagem, o que significa 16 números hexadecimais. Para realizar a encriptação, o DES utiliza "chaves" com comprimento aparente de 16 números hexadecimais, ou comprimento aparente de 64 bits. Entretanto, no algoritmo DES, cada oitavo bit da chave é ignorado, de modo que a chave acaba tendo o comprimento de 56 bits. Mas, para todos os efeitos, o DES é organizado baseando-se no número redondo de 64 bits (16 dígitos hexadecimais).
Por exemplo, se tomarmos a mensagem clara hexadecimal 8787878787878787 e a encriptarmos com a chave DES hexadecimal 0E329232EA6D0D73, obteremos o texto cifrado hexadecimal 0000000000000000. Se o criptograma for decifrado com a mesma chave secreta, o resultado será o texto claro original 8787878787878787 hexadecimal.
Este exemplo é limpo e metódico porque nosso texto claro tinha o comprimento de exatos 64 bits. O mesmo seria verdade caso nosso texto claro tivesse um comprimento múltiplo de 64 bits. Mas a maioria das mensagens não cairá nesta categoria. Não serão um múltiplo exato de 64 bits (isto é, um múltiplo exato de 16 números hexadecimais).
Por exemplo, considere a seguinte mensagem: "Criptologia sempre NumaBoa". Esta mensagem clara possui 28 bytes (56 dígitos hexadecimais) de comprimento. Neste caso, para encriptar a mensagem, seu comprimento precisa ser ajustado com a adição de alguns bytes extras no final. Depois de decifrar a mensagem, estes bytes extras são descartados. É lógico que existem vários esquemas diferentes para adicionar bytes. Aqui nós iremos adicionar apenas zeros no final, de modo que a mensagem total seja um múltiplo de 8 bytes (ou 16 dígitos hexadecimais, ou 64 bits).
O texto claro "Criptologia sempre NumaBoa" é, em hexadecimal,
43 72 69 70 74 6F 6C 6F
67 69 61 20 73 65 6D 70
72 65 20 4E 75 6D 61 42
6F 61 0D 0A
Note que os primeiros 54 dígitos hexadecimais representam a mensagem em Português, enquanto que "0D" é o hexadecimal para Retorno (Carriage Return) e "0A" é o hexadecimal para Quebra de Linha (Line Feed), indicando que o arquivo de mensagem chegou ao fim. Completamos então a mensagem com alguns zeros no final para obter um total de 64 dígitos hexadecimais:
43 72 69 70 74 6F 6C 6F
67 69 61 20 73 65 6D 70
72 65 20 4E 75 6D 61 42
6F 61 0D 0A 00 00 00 00
Se cifrarmos agora a mensagem clara em blocos de 64 bits (16 dígitos hexadecimais), usando a mesma chave DES "0E329232EA6D0D73", obtemos o seguinte texto cifrado:
A1 BF 4C 8C 1F 44 6A 4C
CA 4D E4 28 6E DE 99 50
F5 59 66 2B B5 09 D9 3C
4B A7 70 FA E2 4B B3 C2
Este é o código secreto que pode ser transmitido ou armazenado. Decifrando o texto encriptado restaura a mensagem original "Criptologia sempre NumaBoa".
Fluxograma simplificado
O DES em detalhes
Se você tem algum conhecimento da criptografia clássica, não vai ser difícil perceber que o DES utiliza somente cifras tradicionais como a substituição e a transposição. A diferença é que, com a ajuda do computador, não se trabalha mais com letras e sim com bits. Os princípios, porém, são os mesmos.
O DES é uma cifra de bloco, o que significa que atua sobre blocos de texto claro de determinado tamanho (64 bits) e retorna blocos de texto cifrado do mesmo tamanho. Portanto, o DES resulta numa permutação entre os 264 (leia como "2 elevado a 64") arranjos possíveis de 64 bits, cada um deles podendo ser 0 ou 1. Cada bloco de 64 bits é dividido em dois blocos de 32 bits, um sub-bloco esquerdo L e um sub-bloco direito R (esta divisão é usada apenas em certas operações).
Exemplo: Seja M o texto claro da mensagem M = 0123456789ABCDEF, onde M está no formato hexadecimal (base 16). Reescrevendo M em formato binário obtemos o bloco de texto de 64 bits:
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
L = 0000 0001 0010 0011 0100 0101 0110 0111
R = 1000 1001 1010 1011 1100 1101 1110 1111
O primeiro bit de M é "0" e o último bit é "1". Lemos da esquerda para a direita.
O DES atua sobre blocos de 64 bits usando tamanhos de chave de 56 bits. Na realidade, as chaves são armazenadas com 64 bits mas, passando por um processo que "retira" 8 bits, são reduzidas para 56 bits. Estes 8 bits estão presentes nas chaves para garantir a integridade das mesmas, ou seja, o último bit de cada um dos 8 bytes da chave é um bit verificador, chamado de bit de paridade. Bits de paridade indicam quantos bits estão setados (têm valor 1) nos sete primeiros bits do byte. Quando este número for par (daí paridade), o último bit recebe o valor 1, caso contrário, recebe o valor 0. Por exemplo, o byte 00010011 possui 2 bits setados nos primeiros sete bits, por isso o byte é completado com 1; o byte 00110100 possui três bits setados nos primeiros sete bits, por isso o byte é completado com 0. Apesar dos bits de paridade serem retirados, nos cálculos a seguir vamos sempre numerar os bits de 1 a 64, indo da esquerda para a direita.
Exemplo: seja K a chave hexadecimal K = 133457799BBCDFF1. Isto nos dá a chave binária (substituindo 1 = 0001, 3 = 0011, etc agrupados em oito bits):
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
O algoritmo DES usa vários passos até obter o resultado final. Leia a seguir.
Passo 1: A partir da chave de 56 bits, criar 16 subchaves de 48 bits
A chave de 64 bits é permutada de acordo com a tabela a seguir, PC-1. Observe que nesta tabela os bits de paridade foram excluídos (os bits 8, 16, 24, 32, 40, 48, 56 e 64 estão ausentes) portanto, esta operação só é efetuada depois da verificação de integridade da chave. Como a primeira entrada da tabela é "57", isto significa que o 57º bit da chave original K torna-se o primeiro bit da chave permutada K+. O 49º bit da chave original transforma-se no segundo bit da chave permutada. O 4º bit da chave original é o último bit da chave permutada. Observe que apenas 56 bits da chave original aparecem na chave permutada.
PC-1 --------------------------------------- 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 ---------------------------------------
Exemplo: Da chave original de 64 bits
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
obtemos a permutação de 56 bits
K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111
A seguir, dividimos esta chave em duas metades, esquerda C0 e direita D0, onde cada metade tem 28 bits.
Exemplo: Da chave permutada K+ obtemos
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111
Com C0 e D0 definidas, criamos dezesseis blocos Cn e Dn, 1<=n<=16. Cada par de blocos Cn e Dn é formado pelo par anterior Cn-1 e Dn-1, respectivamente para n = 1, 2, ..., 16, usando o seguinte esquema de "deslocamentos para a esquerda" ("left shift") no bloco anterior. Para fazer um deslocamento à esquerda, mova cada bit uma posição para a esquerda, exceto o primeiro bit, o qual é deslocado para o final do bloco.
Número de Iterações Número de deslocamentos à esquerda ---------------------------------------------------------- 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1
Isto significa que, por exemplo, C3 e D3 são obtidos de C2 e D2, respectivamente, com dois deslocamentos à esquerda, e C16 e D16 são obtidos de C15 e D15, respectivamente, com um deslocamento à esquerda. Em todos os casos, um único deslocamento à esquerda significa uma rotação dos bits uma posição para a esquerda de modo que, após um deslocamento à esquerda, os bits nas 28 posições sejam os bits que previamente estavam nas posições 2, 3, ..., 28, 1.
Exemplo: Do par original C0 e D0 obtemos:
C0 = 1111000011001100101010101111 D0 = 0101010101100110011110001111 C1 = 1110000110011001010101011111 D1 = 1010101011001100111100011110 C2 = 1100001100110010101010111111 D2 = 0101010110011001111000111101 C3 = 0000110011001010101011111111 D3 = 0101011001100111100011110101 C4 = 0011001100101010101111111100 D4 = 0101100110011110001111010101 C5 = 1100110010101010111111110000 D5 = 0110011001111000111101010101 C6 = 0011001010101011111111000011 D6 = 1001100111100011110101010101 C7 = 1100101010101111111100001100 D7 = 0110011110001111010101010110 C8 = 0010101010111111110000110011 D8 = 1001111000111101010101011001 C9 = 0101010101111111100001100110 D9 = 0011110001111010101010110011 C10 = 0101010111111110000110011001 D10 = 1111000111101010101011001100 C11 = 0101011111111000011001100101 D11 = 1100011110101010101100110011 C12 = 0101111111100001100110010101 D12 = 0001111010101010110011001111 C13 = 0111111110000110011001010101 D13 = 0111101010101011001100111100 C14 = 1111111000011001100101010101 D14 = 1110101010101100110011110001 C15 = 1111100001100110010101010111 D15 = 1010101010110011001111000111 C16 = 1111000011001100101010101111 D16 = 0101010101100110011110001111
Agora montamos as chaves Kn, para 1<=n<=16, aplicando a seguinte tabela de permutação em cada um dos pares concatenados CnDn. Cada par possui 56 bits, porém PC-2 usa apenas 48 deles.
PC-2 ---------------------------------- 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 ----------------------------------
Portanto, o primeiro bit de Kn é o 14º bit de CnDn, o segundo bit o 17º, e assim sucessivamente, terminando com o 48º bit de Kn sendo o 32º de CnDn.
Exemplo: Para a primeira chave temos
C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110
a qual, após aplicarmos a permutação PC-2 transforma-se em
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
Para as outras chaves temos
K2 = 011110 011010 111011 011001 110110 111100 100111 100101 K3 = 010101 011111 110010 001010 010000 101100 111110 011001 K4 = 011100 101010 110111 010110 110110 110011 010100 011101 K5 = 011111 001110 110000 000111 111010 110101 001110 101000 K6 = 011000 111010 010100 111110 010100 000111 101100 101111 K7 = 111011 001000 010010 110111 111101 100001 100010 111100 K8 = 111101 111000 101000 111010 110000 010011 101111 111011 K9 = 111000 001101 101111 101011 111011 011110 011110 000001 K10 = 101100 011111 001101 000111 101110 100100 011001 001111 K11 = 001000 010101 111111 010011 110111 101101 001110 000110 K12 = 011101 010111 000111 110101 100101 000110 011111 101001 K13 = 100101 111100 010111 010001 111110 101011 101001 000001 K14 = 010111 110100 001110 110111 111100 101110 011100 111010 K15 = 101111 111001 000110 001101 001111 010011 111100 001010 K16 = 110010 110011 110110 001011 000011 100001 011111 110101
Em relação às subchaves é só. Agora vamos dar uma olhada na mensagem.
Passo 2: Codificar cada bloco de 64 bits de dados
Existe uma permutação inicial IP dos 64 bits de dados da mensagem M. Isto rearranja os bits de acordo com a seguinte tabela, onde as entradas da tabela mostram o novo arranjo de bits a partir da ordenação inicial. O 58º bit de M torna-se o primeiro bit de IP. O 50º bit de M passa a ser o segundo bit de IP. O 7º bit de M será o último bit de IP.
IP ----------------------------------------- 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 -----------------------------------------
Exemplo: Aplicando a permutação inicial ao bloco de texto M citado anteriormente obtemos
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
Aqui, o 58º bit de M é "1" e se torna o primeiro bit de IP. O 50º bit de M também é "1" e torna-se o segundo bit de IP. O 7º bit de M é "0", o qual se torna o último bit de IP.
Em seguida dividimos o bloco permutado IP numa metade esquerda L0 de 32 bits e numa metade direita R0 de 32 bits.
Exemplo: Obtemos L0 e R0 de IP
L0 = 1100 1100 0000 0000 1100 1100 1111 1111 R0 = 1111 0000 1010 1010 1111 0000 1010 1010
Agora prosseguimos com 16 iterações, para 1<=n<=16, usando uma função f que opera em dois blocos - no bloco de dados de 32 bits e na chave Kn de 48 bits - para produzir um bloco de 32 bits. Seja + uma adição XOR (adição bit-a-bit módulo 2) então, para n variando de 1 a 16, calculamos
Ln = Rn-1 Rn = Ln-1 + f(Rn-1,Kn)
O resultado aparece num bloco final, para n = 16, de L16R16. Isto é, em cada iteração, pegamos os 32 bits da direita do resultado anterior e transformamo-os nos 32 bits da esquerda do passo atual. Para os 32 bits da direita do passo atual nós fazemos um XOR dos 32 bits da esquerda do passo anterior através do cálculo de f.
Exemplo: Para n = 1 temos
K1 = 000110 110000 001011 101111 111111 000111 000001 110010 L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010 R1 = L0 + f(R0,K1)
Falta explicar como funciona a função f. Para calcular f, primeiramente expandimos cada bloco Rn-1 de 32 bits para 48 bits (para se ajustar ao tamanho das sub-chaves). Isto é feito usando uma tabela de seleção que repete alguns dos bits em Rn-1. Chamaremos o uso desta tabela de seleção de função E. Portanto, E(Rn-1) tem um bloco de entrada de 32 bits e um bloco de saída de 48 bits.
Seja E tal que os 48 bits de saída, escritos em 8 blocos de 6 bits cada, sejam obtidos através da seleção de bits nas suas entradas de acordo com a seguinte tabela:
Tabela E de Seleção de bits ---------------------------------- 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 ----------------------------------
Portanto, os primeiros três bits de E(Rn-1) são os bits das posições 32, 1 e 2 de Rn-1, enquanto que os dois últimos bits de E(Rn-1) são os bits da posição 32 e 1.
Exemplo: Calculamos E(R0) de R0 da seguinte maneira:
R0 = 1111 0000 1010 1010 1111 0000 1010 1010 E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
(Note que cada bloco de 4 bits originais foi expandido para um bloco de 6 bits de saída).
A seguir, no cálculo de f, fazemos um XOR na saída E(Rn-1) com a chave Kn. O motivo de se utilizar o XOR lógico é porque este é reversível. Se A xor B = C, então A xor C = B e B xor C = A. A reversibilidade é importante para podermos reverter o processo quando quisermos decifrar a mensagem cifrada.
Kn + E(Rn-1)
Exemplo: Para K1, E(R0), temos
K1 = 000110 110000 001011 101111 111111 000111 000001 110010 E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101 K1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111
Ainda não terminamos o cálculo da função f. Até este ponto, expandimos Rn-1 de 32 para 48 bits, usando a tabela de seleção E, e XORamos o resultado com a chave Kn. Com este processo obtivemos 48 bits ou oito grupos de 6 bits. Agora fazemos uma coisa meio estranha com cada grupo de seis bits: usamo-os como endereços em tabelas denominadas "S boxes", ou "caixas S". Cada grupo de seis bits nos dará um endereço numa caixa S diferente. Um número de 4 bits estará localizado neste endereço. Este número de 4 bits irá substituir os 6 bits originais. O principal resultado é que os oito grupos de 6 bits são transformados em oito grupos de 4 bits (as saídas de 4 bits das caixas S) num total de 32 bits.
Escrevemos o resultado anterior, que tem 48 bits, na forma:
Kn + E(Rn-1) = B1B2B3B4B5B6B7B8
onde cada Bi é um grupo de seis bits. Agora calculamos
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
onde Si(Bi) se refere à iésima saída da caixa S.
Repetindo, cada uma das funções S1, S2, ..., S8, pega um bloco de 6 bits como entrada e devolve um bloco de 4 bits como saída. A tabela para determinar S1 é mostrada e explicada abaixo:
Função S1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 | 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 | 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 | 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Se S1 é a função definida nesta tabela e B é um bloco de 6 bits, então S1(B) é determinada da seguinte maneira: O primeiro e o último bit de B representam um número na base 2 com valor decimal entre 0 e 3 (ou binário 00 a 11). Que este número seja i. Os 4 bits centrais de B representam um número na base 2 com valor decimal entre 0 e 15 (ou binário de 0000 a 1111). Que este número seja j. Procure o número na tabela localizado na j-ésima coluna e na i-ésima linha. É um número que varia de 0 a 15 e é unicamente representado por um bloco de 4 bits. Este bloco é a saída S1(B) de S1 para a entrada B. Por exemplo, para o bloco de entrada B = 011011, o primeiro bit é "0" e o último é "1", indicando a linha 01. Os quatro bits centrais são "1101". Este é o equivalente binário do decimal 13, de modo que a coluna será a de número 13. Na linha 1, coluna 13, aparece 5. Isto determina a saída; 5 é o binário 0101, de modo que a saída é 0101. Portanto, S1(011011) = 0101.
As tabelas definindo as funções S2, ..., S8 são as seguintes:
Função S2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 1 | 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 2 | 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 3 | 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 Função S3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 1 | 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 2 | 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 | 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 Função S4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 1 | 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 2 | 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 | 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
Função S5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 1 | 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 2 | 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 3 | 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 Função S6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 1 | 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 2 | 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 3 | 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 Função S7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 1 | 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 2 | 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 3 | 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 Função S8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | -------------------------------------------------------------- 0 | 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 | 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 2 | 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 3 | 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Exemplo: Para a primeira rodada, obtemos como saída das oito caixas S:
K1 + E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111
O estágio final do cálculo de f é fazer uma permutação P da saída da caixa S para obter o valor final de f:
f = P(S1(B1)S2(B2)...S8(B8))
A permutação P é definida pela tabela a seguir. P devolve uma saída de 32 bits a partir de uma entrada de 32 bits permutando os bits do bloco de entrada.
P ------------------ 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 ------------------
Exemplo: Da saída das oito caixas S
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111
obtemos
f = 0010 0011 0100 1010 1010 1001 1011 1011
Agora possuimos todos os elementos necessários para calcular R1, ou seja, R1 = L0 + f(R0 ,K1)
L0 = 1100 1100 0000 0000 1100 1100 1111 1111 f(R0, K1) + 0010 0011 0100 1010 1010 1001 1011 1011 R1 = 1110 1111 0100 1010 0110 0101 0100 0100
Na próxima rodada obteremos L2 = R1, que é o sub-bloco que acabamos de calcular, e depois precisamos calcular R2 = L1 + f(R1, K2) e assim sucessivamente por 16 rodadas. No final da décima sexta rodada temos os sub-blocos L16 e R16. Invertemos então a ordem dos dois sub-blocos num bloco de 64 bits, ou seja, R16L16, e aplicamos a permutação final IP-1 definida na seguinte tabela:
IP-1 --------------------------------------------- 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 ---------------------------------------------
É isto aí, a saída do algoritmo possui o bit 40 do bloco de pre-saída como seu primeiro bit, bit 8 como seu segundo bit, e assim sucessivamente, até o bit 25 do bloco de pre-saída como seu último bit.
Exemplo: Se processarmos todos os 16 blocos usando o método definido previamente, obteremos, na 16ª rodada
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1010 0100 1100 1101 1001 1001 0101
Invertendo a ordem destes dois blocos e aplicando a permutação final em
R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100
IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101
o que, em formato hexadecimal, é 85E813540F0AB405.
Portanto, a forma cifrada de M = 0123456789ABCDEF é C = 85E813540F0AB405.
Decifrar é simplesmente o inverso de cifrar, seguindo os mesmos passos acima descritos porém invertendo a ordem das sub-chaves aplicadas.
MODOS DE OPERAÇÃO DO DES
O algoritmo DES transforma um bloco de mensagem M de 64 bits num bloco cifrado C. Se cada bloco de 64 bits for cifrado individualmente, então o modo de encriptação é denominado Electronic Code Book (ECB). Existem outros dois modos de cifragem DES, os modos Chain Block Coding (CBC) e Cipher Feedback (CFB), os quais tornam cada bloco cifrado dependente de todos os outros blocos de mensagem anteriores através de uma operação inicial de XOR.
QUEBRANDO O DES
Antes que o DES fosse adotado como padrão nacional (estadunidense), durante o período em que o NBS estava solicitando comentários sobre o algoritmo proposto, os criadores da criptografia de chave pública, Martin Hellman e Whitfield Diffie, registraram algumas objeções quanto ao uso do DES como algoritmo de encriptação. Hellman escreveu: "Whit Diffie e eu ficamos preocupados com o fato de que o padrão de encriptação de dados proposto, enquanto provavelmente seguro em relação a assaltos comerciais, pode ser extremamente vulnerável a ataques efetuados por uma organização de inteligência" (carta ao NBS, 22 de Outubro de 1975).
Diffie e Hellman planejaram então um ataque de "força bruta" ao DES ("força bruta" significa aplicar sequencialmente as 256 chaves possíveis até encontrar a chave correta que decifra a mensagem cifrada). Propuseram o uso específico de "computadores paralelos usando um milhão de chips para testar um milhão de chaves cada um" por segundo e estimaram o custo de uma máquina deste tipo em US$ 20 milhões.
Um salto para 1998. Sob a direção de John Gilmore do EFF, uma equipe gastou menos do que US$ 250.000 para construir uma máquina que analisou todo o espaço de chaves de 56 bits do DES e precisou, em média, 4.5 dias para completar a tarefa. Em 17 de Julho de 1998 eles anunciaram que haviam quebrado uma chave de 56 bits em 46 horas. O computador, chamado de Deep Crack, usa 27 placas, cada uma com 64 chips, e é capaz de testar 90 bilhões de chaves por segundo.
Apesar disso, em 8 de Junho de 1998, Robert Litt, principal representante procurador geral do Departamento de Justiça dos Estados Unidos, negou que fosse possível o FBI quebrar o DES: "Deixe-me colocar o problema técnico no contexto: foram precisos 14.000 computadores Pentium trabalhando durante quatro meses para decifrar uma única mensagem... Não estamos falando apenas do FBI e da NSA [precisando de um poder de processamento maciço], estamos falando a respeito de cada departamento de polícia."
Respondeu o especialista em criptografia Bruce Schneier: "... o FBI ou é incompetente ou está mentindo, ou ambos". Schneier continua: "A única solução neste caso é pegar um algoritmo com uma chave maior; não existe silício suficiente na galáxia ou tempo suficiente antes do sol se apagar para quebrar com força bruta o triple-DES" (Crypto-Gram, Counterpane Systems, 15 de Agosto de 1998).
TRIPLE-DES
O triple-DES é apenas o DES com duas chaves de 56 bits aplicadas. Dada uma mensagem em texto claro, a primeira chave é usada para cifrar a mensagem em DES. A segunda chave é usada para decifrar o DES da mensagem cifrada. Como a segunda chave não é a correta para decifrar, esta decifração apenas embaralha ainda mais os dados. A mensagem duplamente embaralhada é, então, cifrada novamente com a primeira chave para se obter o criptograma final. Este procedimento em três etapas é chamado de triple-DES ou triplo DES.
Triple-DES é apenas o DES efetuado três vezes com duas chaves usadas numa determinada ordem. O triple-DES também pode ser feito usando-se três chaves diferentes, ao invés de apenas duas. No primeiro caso, o espaço das chaves é de 2112, no segundo, é de 2168.
Agradecimentos
- Agradeço ao daimao por ter me alertado sobre os bits de paridade da chave.
- Agradeço ao Luis Cláudio por ter me alertado a respeito do espaço das chaves.
Texto publicado pela primeira vez na Aldeia em 5 de Agosto de 2003.