Menu

Introdução à codificação DES

Última modificação: terça 15 dezembro 2020 à 04:43 por Ana Spadari.

DES - Data Encryption Standard é um algoritmo de criptografia de chave simétrica. Ela trabalha com blocos de 64 bits com chaves também de 64 bits, embora a chave real seja de 56 bits, já que 8 desses bits são redundantes. Assim, são possíveis 256 chaves diferentes, algo como 1016 chaves. O algoritmo executa várias operações, como combinações, substituições e permutações, para criptografar dados onde, um conjunto de operações, é aplicado 16 vezes em cada bloco de dados.

DES - A codificação com chave secreta

No dia 15 de maio de 1973, o NBS (National Institute of Standards and Technology) lançou um apelo ao Federal Register (equivalente nos Estados Unidos ao Diário Oficial) para a criação de um algoritmo de codificação que respondesse aos seguintes critérios: possuir um elevado nível de segurança ligado a uma pequena chave para codificação e descodificação, ser compreensível, não depender da privacidade do algoritmo, ser adaptável e econômico e ser eficaz e exportável.

No final de 1974, a IBM propôs o Lucifer que, graças à NSA (National Security Agency), foi alterado no dia 23 de novembro de 1976 para lançar o DES (Data Encryption Standard). O DES foi finalmente aprovado em 1978 pela NBS. O DES foi padronizado pelo ANSI (American National Standard Institute) sob o nome de ANSI X3.92, mais conhecido como DEA (Data Encryption Algorithm).

Qual é o princípio do DES

DES é um sistema de codificação simétrico por blocos de 64 bits, dos quais 8 bits (um byte) servem de teste de paridade (para verificar a integridade da chave). Cada bit de paridade da chave (1 em cada 8 bits) serve para testar um dos bytes da chave por paridade ímpar, ou seja, cada bit de paridade é ajustado de forma a ter um número ímpar de '1' no byte ao qual ele pertence. Assim, a chave possui um comprimento útil de 56 bits, o que significa que só 56 bits são realmente usados no algoritmo.

O algoritmo efetua combinações, substituições e permutações entre o texto a ser codificado e a chave, de modo com que as operações possam ser feitas nos dois sentidos (para a descodificação). A combinação entre substituições e permutações chama-se código do produto.

A chave é codificada em 64 bits e formada por 16 blocos de 4 bits, geralmente notados k1 a k16. Já que apenas 56 bits são efetivamente usados para calcular, pode haver até 256 (isto é, 7.2*1016) chaves diferentes.

O algoritmo do DES

As grandes linhas do algoritmo são o fracionamento do texto em blocos de 64 bits (8 bytes), a permuta inicial dos blocos, a partição dos blocos em duas partes: esquerda e direita, chamadas G e D, respectivamente; as fases de permuta e substituição repetidas 16 vezes (chamadas ‘voltas’) e o colamento das partes esquerda e direita e a permutação inicial inversa:

algorítmo do DES

Fracionamento do texto

Permutação inicial

Inicialmente, cada bit de um bloco é sujeito à permuta inicial, podendo ser representado pela seguinte matriz de permutação inicial (PI):

PI
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

Esta matriz de permutação indica, percorrendo a matriz da esquerda para a direita e , em seguida, de cima para baixo, que o 58º bit do bloco de texto de 64 bits reaparece em primeira posição, o 50º em segunda, e assim, sucessivamente.

Cisão em blocos de 32 bits

Depois de realizar a permuta inicial, o bloco de 64 bits é dividido em dois blocos de 32 bits, respectivamente G e D (para esquerda e direita, que, em francês, se escrevem como gauche e droit). Marcamos G0 e D0 como estado inicial destes dois blocos:

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

É interessante observar que G0 contém todos os bits com uma posição par na mensagem inicial, enquanto o D0 contém os bits de posição ímpar.

Voltas

Os blocos Gn e Dn são sujeitos a um conjunto de transformações iterativas chamadas voltas, explicadas nesta imagem, e cujos detalhes são dados mais abaixo:

voltas

Função de expansão

Os 32 bits do bloco D0 são estendidos a 48 bits graças a uma tabela (matriz) chamada tabela de expansão (marcada como ‘E’), onde os 48 bits são misturados e apenas 16 serão duplicados:

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

Assim, o último bit de D0 (quer dizer, o 7º bit do bloco de origem) torna-se o primeiro, o primeiro torna-se o segundo, etc. Além disso, os bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 e 29 de D0 (respectivamente 57,33,25, l, 59,35,27,3,6l, 37,29,5,63,39,31 e 7 do bloco de origem) são duplicados e disseminados na matriz.

OU exclusivo com a chave

A matriz resultante de 48 bits é chamada D'0 ou E[D0]. Em seguida, o algoritmo DES procede a um OU exclusivo entre a primeira chave K1 e E[D0]. O resultado deste OU exclusivo é uma matriz de 48 bits que chamaremos de D0 por conveniência (não se trata do D0 do início).

Função de substituição

Em seguida, D0 é dividido em 8 blocos de 6 bits, notado D0i. Cada um destes blocos passa por funções de seleção (chamadas, às vezes, de caixas de substituição ou funções de compressão), marcadas geralmente como Si.

Os primeiros e últimos bits de cadaD0i determina (em binário) a linha da função de seleção, os outros bits (respectivamente 2, 3, 4 e 5) determinam a coluna. A seleção da linha, fazendo-se sobre duas bits, tem 4 possibilidades (0,1,2,3). A seleção da coluna sendo feita em 4 bits, tem 16 possibilidades (de 0 a 15). Graças a esta informação, a função de seleção “seleciona” um valor codificado em 4 bits.

Veja a primeira função de substituição, representada por uma matriz de 4 por 16:

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

Suponhamos que D01 é igual a 101110. Os primeiros e últimos bits dão 10, ou seja, 2 em binário. Os bits 2, 3, 4 e 5 dão 0111, seja 7 em binário. O resultado da função de seleção é, então, o valor situado na linha n° 2, na coluna n° 7. Trata-se do valor 11, ou 111 em binário.

Cada um dos 8 blocos de 6 bits passou para a função de seleção correspondente, o que deu, no final, 8 valores de 4 bits cada. Veja as outras funções de seleçã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
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
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
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
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
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
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
1 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Assim, cada bloco de 6 bits é substituído em um bloco de 4 bits. Estes bits são reunidos para formar um bloco de 32 bits.

Permuta

Por último, o bloco de 32 bits obtido é submetido a uma permuta P cuja tabela é a seguinte:

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

OU exclusivo

O conjunto destes resultados em saída de P é submetido a um OU exclusivo com o G0 inicial (como indicado no primeiro esquema) para dar D1, enquanto o D0 inicial dá G1.

Iteração

O conjunto das etapas precedentes (voltas) é reiterado 16 vezes.

Permuta inicial inversa

No fim das iterações, os dois blocos G16 e D16 são recolados e, em seguida, sujeitos à permuta inicial inversa:

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

O resultado de saída é um texto codificado de 64 bits.

Geração das chaves

Já que o algoritmo do DES, apresentado acima, é público, toda a segurança se baseia na complexidade das chaves de codificação.

O algoritmo abaixo mostra como obter, a partir de uma chave de 64 bits (composta de 64 caracteres alfanuméricos quaisquer) 8 chaves diversificadas de 48 bits, cada uma servindo no algoritmo do DES:

Algoritmo de geração das chaves DES
Inicialmente, os bits de paridade da chave são eliminados a fim de obter uma chave com um comprimento útil de 56 bits.

A primeira etapa consiste numa permuta notada CP-1 , cuja matriz é apresentada abaixo:

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

Na verdade, esta matriz pode ser escrita na forma de duas matrizes Gi (esquerda) e Di (direita) compostas por 28 bits, cada uma:

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

Marca-se como G0 e D0 o resultado desta primeira permuta.

Em seguida, estes dois blocos sofrem uma rotação à esquerda, de tal maneira que os bits em segunda posição tomam a primeira posição, os em terceira posição a segunda, etc. Os bits em primeira posição passam para a última posição.

Depois disso, os 2 blocos de 28 bits são agrupados num bloco de 56 bits. Este passa por uma permuta, notada CP-2, fornecendo em saída um bloco de 48 bits, representando a chave Ki:

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

Iterações do algoritmo permitem dar as 16 chaves K1 a K16 utilizadas no algoritmo do DES:

LS
1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28

TDES, uma alternativa para o DES

Em 1990, Eli Biham e Adi Shamir afinaram a criptoanálise diferencial que procura pares de texto normal e pares de texto codificados. Este método funciona até um número de voltas inferior a 15, ora um número de 16 voltas está presente no algoritmo apresentado acima.

Por outro lado, mesmo se uma chave de 56 bits dá um número enorme de possibilidades, vários processadores permitem calcular mais de 106 chaves por segundo. Assim, utilizados paralelamente em um elevado número de máquinas, torna-se possível para um grande organismo (um Estado, por exemplo) encontrar a chave certa.

Uma solução a curto prazo consiste em encadear três codificações DES com a ajuda de duas chaves de 56 bits (o que equivale a uma chave de 112 bits). Este método é chamado de Triplo DES, notado TDES (às vezes 3DES ou 3-DES):

Triplo DES - 3DES
O TDES permite aumentar significativamente a segurança, contudo tem a grande desvantagem de solicitar mais recursos para a codificação e a descodificação.

Habitualmente, distinguimos vários tipos de codificação tripla DES: DES-EEE3: três codificações DES com 3 chaves diferentes; DES-EDE3: uma chave diferente para cada uma das 3 operações DES (codificação, descodificação, codificação); DES-EEE2 e DES-EDE2: uma chave diferente para a segunda operação (descodificação).

Em 1997, o NIST lançou um novo apelo para um projeto de elaboração do AES(Advanced Encryption Standard), um algoritmo de codificação destinado a substituir o DES.

O sistema de codificação DES foi atualizado todos os 5 anos. Em 2000, durante a última revisão, após um processo de avaliação que durou 3 anos, o algoritmo desenvolvido por dois candidatos belgas, Vincent Rijmen e Joan Daemen, foi escolhido como novo padrão pelo NIST. Este novo algoritmo chamado RIJNDAEL pelos seus inventores, substituirá o DES.

Foto: © 123rf.com, Unsplash.com

Nosso conteúdo é produzido em colaboração com especialistas em tecnologia da informação sob o comando de Jean-François Pillou, fundador do CCM.net. CCM é um site sobre tecnologia líder em nível internacional e está disponível em 11 idiomas.
Este documento, intitulado 'Introdução à codificação DES', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.
Criptografia
Codificação simples

Assine nossa newsletter!
Assine nossa newsletter!