Detalhes

Categoria: Exercícios on line

Atualização: Quinta, 14 Janeiro 2010 12:11

Autor: vovó Vicki

Acessos: 13793

Não existe forma melhor de entender e aprender alguma coisa do que pondo a mão na massa. Aliás, "por a mão na massa" é uma expressão perfeita quando se trata do algoritmo criptográfico DES: o processo usado pelo algoritmo mais parece uma massa de dados sendo sovada.

Se você sabe o que é o DES, tudo bem - continue a leitura. Se você não tem idéia do que vem a ser o DES, talvez seja melhor dar uma lida em O algoritmo DES ilustrado e em O algoritmo DES ilustrado II antes de continuar.

Neste exercício faremos a cifragem da mensagem "Criptologia sempre NumaBoa" e usaremos a chave DES "0E 32 92 32 EA 6D 0D 73".

PREPARANDO AS SUB-CHAVES

Precisamos criar 16 subchaves de acordo com as tabelas de substituição de bits mas, antes disso, precisamos transformar nossa chave K em binário:

          0    E    3    2    9    2    3    2    E    A    6    D    0    D    7    3
         0000 1110 0011 0010 1001 0010 0011 0010 1110 1010 0110 1101 0000 1101 0111 0011
              |     |     |     |      |     |     |     |      |     |     |     |
bits          5    10    15    20     25    30    35    40     45    50    55    60

A tabela de permutação PC-1 nos indica qual a nova sequência de bits para a chave K+ constituída por 8 sequências de 7 bits dando um total de 56 bits:

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
---------------------------------------
K+ = 0001010 0101100 0010111 0101000 1001111 1011000 0101110 0011110

Observe que o bit 57 é 0, o bit 49 é 0, o bit 41 é 0, o bit 33 é 1 e assim sucessivamente.

Agora dividimos a chave em duas partes iguais de 28 bits, C₀ e D₀:

C0 = 0001010 0101100 0010111 0101000
D0 = 1001111 1011000 0101110 0011110

Sabendo que os pares 1, 2, 9 e 16 devem receber 1 deslocamento à esquerda e os pares restantes 2 deslocamentos, obtemos o seguinte:

← 1 shift E
C1 = 0010100101100001011101010000
D1 = 0011111011000010111000111101
← 1 shift E
C2 = 0101001011000010111010100000
D2 = 0111110110000101110001111010
← 2 shift E
C3 = 0100101100001011101010000001
D3 = 1111011000010111000111101001
← 2 shift E
C4 = 0010110000101110101000000101
D4 = 1101100001011100011110100111
← 2 shift E
C5 = 1011000010111010100000010100
D5 = 0110000101110001111010011111
← 2 shift E
C6 = 1100001011101010000001010010
D6 = 1000010111000111101001111101
← 2 shift E
C7 = 0000101110101000000101001011
D7 = 0001011100011110100111110110
← 2 shift E
C8 = 0010111010100000010100101100
D8 = 0101110001111010011111011000
← 1 shift E
C9 = 0101110101000000101001011000
D9 = 1011100011110100111110110000
← 2 shift E
C10 = 0111010100000010100101100001
D10 = 1110001111010011111011000010
← 2 shift E
C11 = 1101010000001010010110000101
D11 = 1000111101001111101100001011
← 2 shift E
C12 = 0101000000101001011000010111
D12 = 0011110100111110110000101110
← 2 shift E
C13 = 0100000010100101100001011101
D13 = 1111010011111011000010111000
← 2 shift E
C14 = 0000001010010110000101110101
D14 = 1101001111101100001011100011
← 2 shift E
C15 = 0000101001011000010111010100
D15 = 0100111110110000101110001111
← 1 shift E
C16 = 0001010010110000101110101000
D16 = 1001111101100001011100011110

Agora concatenamos os pares obtidos através dos deslocamentos para a esquerda e, dos 56 bits, "pescamos" apenas 48 de acordo com a tabela P-2:

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

C1D1 = 00101001011000010111010100000011111011000010111000111101
K1 = 001101100001010001100100011110001110000111100001

C2D2 = 01010010110000101110101000000111110110000101110001111010
K2 = 010000001011110100010001011101101110100011111101

C3D3 = 01001011000010111010100000011111011000010111000111101001
K3 = 010001011010010001110011001000111001110111011011

C4D4 = 00101100001011101010000001011101100001011100011110100111
K4 = 111001111100010010000010100011111011010100110011

C5D5 = 10110000101110101000000101000110000101110001111010011111
K5 = 011110101000001110000010011011110100111101100100

C6D6 = 11000010111010100000010100101000010111000111101001111101
K6 = 001110001001000000011011010110001100100111011110

C7D7 = 00001011101010000001010010110001011100011110100111110110
K7 = 001001010000000001011110110001011101010010011101

C8D8 = 00101110101000000101001011000101110001111010011111011000
K8 = 001001100100100010010100110010110011011011101001

C9D9 = 01011101010000001010010110001011100011110100111110110000
K9 = 010101000101010101000001011110011111011000110011

C10D10 = 01110101000000101001011000011110001111010011111011000010
K10 = 010000111100100101000101001111110100110000101110

C11D11 = 11010100000010100101100001011000111101001111101100001011
K11 = 000010011110000110000111100011000111100111010110

C12D12 = 01010000001010010110000101110011110100111110110000101110
K12 = 001100010000010110101011101001011110001011110101

C13D13 = 01000000101001011000010111011111010011111011000010111000
K13 = 111100010000000010100001111100111000111011000011

C14D14 = 00000010100101100001011101011101001111101100001011100011
K14 = 100100011000101010010100100111101000011100011111

C15D15 = 00001010010110000101110101000100111110110000101110001111
K15 = 000101000011001010010110000111110111011111000100

C16D16 = 00010100101100001011101010001001111101100001011100011110
K16 = 011000000110111100000100010011000011101011100111

PREPARANDO A MENSAGEM

A primeira providência a ser tomada é transformar os caracteres da mensagem em texto claro nos seus valores ASCII hexadecimais:

       C  r  i  p  t  o  l  o  g  i  a     s  e  m  p  r  e     N  u  m  a  B  o  a
      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

A seguir adicionamos os caracteres ASCII "0D" (retorno) e "0A" (quebra de linha) para indicar o final da mensagem e separamos os caracteres em blocos de 64 bits (ou 16 dígitos hexadecimais). Além disso, completamos o último bloco com zeros para ajustar seu tamanho para 64 bits.

     43726970746F6C6F  6769612073656D70  7265204E756D6142  6F610D0A00000000

Desta forma, nossa mensagem agora é composta por 4 blocos de 16 dígitos hexadecimais. Podemos então transformar cada um dos blocos em binário, obtendo os 64 bits de cada um deles.

      4    3    7    2    6    9    7    0    7    4    6    F    6    C    6    F
     0100 0011 0111 0010 0110 1001 0111 0000 0111 0100 0110 1111 0110 1100 0110 1111

      6    7    6    9    6    1    2    0    7    3    6    5    6    D    7    0
     0110 0111 0110 1001 0110 0001 0010 0000 0111 0011 0110 0101 0110 1101 0111 0000

      7    2    6    5    2    0    4    E    7    5    6    D    6    1    4    2
     0111 0010 0110 0101 0010 0000 0100 1110 0111 0101 0110 1101 0110 0001 0100 0010

      6    F    6    1    0    D    0    A    0    0    0    0    0    0    0    0
     0110 1111 0110 0001 0000 1101 0000 0101 0000 0000 0000 0000 0000 0000 0000 0000

FAZENDO A MISTURA DA MASSA DE DADOS

De posse das 16 sub-chaves de 48 bits e dos 4 blocos de mensagem de 64 bits podemos começar a "sovar" a mensagem para chegar ao texto cifrado. Neste exercício mostro apenas o trabalho feito com o primeiro bloco. O restante fica por sua conta - pode fazer o exercício na unha, correndo o risco de errar algum bit, ou utilizar o programa desenvolvido pelo Laboratório de Criptologia da Aldeia que você encontra nos Downloads de Criptologia.

Na deste exercício você pode acompanhar o processo. Divirta-se ;)))

Agradecimento

Quero agradecer ao Robson Lages, de São Vicente - SP, por me alertar que os shifts para se obter as sub-chaves não estavam corretos. Pior do que isto, não só neste texto como também no programa DES, disponibilizado para download. Ambos já foram corrigidos.

Obrigada, Robson, um abraço da vó Vicki

O caminho das pedras

1º bloco da mensagem (m₁)
0100001101110010011010010111000001110100011011110110110001101111

Permutação IP

Inicialmente vamos fazer a permutação IP no primeiro bloco da mensagem. A Tabela IP nos dá as permutações. Observe que este processo nada mais é do que a transposição de bits: o 58º torna-se o primeiro, o 50º o segundo e o 7º será o último.

Tabela 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
-----------------------------------------
    m1 = 0100001101110010011010010111000001110100011011110110110001101111
IP(m1) = 1111111100011010111100001010010100000000111111101110010010100011

Divisão de IP(m₁) em L₀ e R₀

Agora dividimos IP(m1) em duas partes iguais de 32 bits, L₀ e R₀:

IP(m1) = 1111111100011010111100001010010100000000111111101110010010100011
L0 = 11111111000110101111000010100101
R0 = 00000000111111101110010010100011

Expansão E

Vamos inicialmente trabalhar com R₀, expandindo este sub-bloco de 32 bits para 48 bits utilizando para isto a Tabela de Expansão E:

Tabela de Expansão E
--------------------
 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
 -------------------
 
 R0 = 00000000111111101110010010100011
E(R0) = 100000000001011111111101011100001001010100000110

XOR com a sub-chave

XOR é uma operação lógica de OU EXCLUSIVO, ou seja, valores diferentes se excluem e valores iguais não. Isto é o mesmo que fazer a pergunta: são valores diferentes? Se verdadeiro, o valor é 1; se falso, o valor é 0.

Utilizando a primeira sub-chave, K1, faremos um XOR com o resultado obtido até agora, ou seja, K1 xor E(R₀)

            E(R0) = 100000 000001 011111 111101 011100 001001 010100 000110
               K1 = 001101 100001 010001 100100 011110 001110 000111 100001
      K1 xor E(R0) = 101101 100000 001110 011001 000010 000111 010011 100111

As Caixas S - voltando para 32 bits

Fracionamos os 48 bits obtidos em 8 grupos de 6 bits. Para cada grupo existe uma Caixa S:

     grupo B1: 101101      00 01 02 03 04 05 06 07 08 09 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

Observe como o grupo de 6 bits é reduzido para 4 bits: o primeiro e o último bit do grupo podem ser 00, 01, 10 e 11 (o que corresponde em decimal a 0, 1, 2 e 3) - indicam o número da linha; os 4 bits centrais variam de 0000 a 1111 (de 0 a 15 decimal) - indicam o número da coluna.

O primeiro e o último bit do nosso primeiro grupo são 11, ou seja, decimal 3. Os quatro bits centrais são 0110, decimal 6. O valor encontrado na Caixa S1, na linha 3, coluna 6 é o decimal 1 que, expresso em binário de 4 bits corresponde a 0001. Este valor substituirá o grupo 1, ou seja: B1 = 101101 → S1(B1) = 0001

A seguir estão as outras Caixas S. Repita o processo com os demais grupos para finalizar esta etapa.

     grupo B2: 100000      00 01 02 03 04 05 06 07 08 09 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

     grupo B3: 001110      00 01 02 03 04 05 06 07 08 09 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

     grupo B4: 011001      00 01 02 03 04 05 06 07 08 09 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

     grupo B5: 000010      00 01 02 03 04 05 06 07 08 09 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

     grupo B6: 000111      00 01 02 03 04 05 06 07 08 09 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

     grupo B7: 010011      00 01 02 03 04 05 06 07 08 09 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

     grupo B8: 100111      00 01 02 03 04 05 06 07 08 09 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

Passando os oito grupos pelas respectivas caixas S, obtemos o seguinte resultado: 0001 1001 1100 0111 1101 0111 0001 1101. Este valor corresponde a S(K₁ xor E(R₀)) e é composto novamente por 32 bits.

A Tabela P

Tabela 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
 --------------------------

A Tabela P orienta mais uma permutação. Utilizando-a estamos aplicando a função P(S(K₁ xor E(R₀))) e obtemos o seguinte resultado: 10101011011011010111100100101010

XOR com o sub-grupo correspondente

R₀ está prestes a se transformar em R₁. Falta um último XOR, o qual será efetuado com seu correspondente S₀:

     P(S(K1 xor E(R0))) = 10101011011011010111100100101010
                     L0 = 11111111000110101111000010100101
                     R1 = 01010100011101111000100110001111

Repetindo o ciclo

O trabalhoso foi obter o valor de R₁. Para obter os L é bico: L₁ = R₀, L₂ = R₁ etc.

Precisamos repetir o ciclo 16 vezes para finalmente obter os valores de R₁₆ e L₁₆. Se você tiver a devida paciência... prossiga fazendo à mão. Se você conseguir, garanto que estará tão familiarizado com o sistema binário quanto costumamos estar com o decimal

Em todo caso, aqui está o resultado:

L16 é 10011110011001111100000000011011
R16 é 10010001000011100100001111100001

Inverter os sub-blocos e aplicar IP^-1

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

Para terminar de cifrar o primeiro bloco da mensagem basta inverter L₁₆ e R₁₆ e depois aplicar a Tabela IP^-1

Aplicando a Tabela IP^-1 obtemos finalmente os bits cifrados que correspondem ao primeiro bloco da mensagem:

Esta tripa de bits corresponde ao bloco Criptolo da mensagem original cifrada com a chave 0E329232EA6D0D73. Quer encarar cifrar o restante da mensagem? Não? Ainda bem que existem os computadores para fazer este trabalho chato... só que os mesmos computadores quebram esta cifra com relativa facilidade, mesmo sem conhecer a chave!