Introdução à codificação DES

Junho 2017

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
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157


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
585042342618102
605244362820124
625446383022146
645648403224168


D0
57494133251791
595143352719113
615345372921135
635547393123157


É 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
3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321



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
0123456789101112131415
01441312151183106125907
10157414213110612119538
24114813621115129731050
31512824917511314100613


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
0123456789101112131415
01518146113497213120510
13134715281412011069115
20147111041315812693215
31381013154211671205149



S3
0123456789101112131415
01009146315511312711428
11370934610285141211151
21364981530111212510147
31101306987415143115212



S4
0123456789101112131415
07131430691012851112415
11381156150347212110149
21069012117131513145284
331506101138 94511127214



S5
0123456789101112131415
02124171011685315130149
11411212471315015103986
24211110137815912563014
31181271142136150910453



S6
0123456789101112131415
01211015926801334147511
11015427129561131401138
29141552812370410113116
34321295151011141760813



S7
0123456789101112131415
04112141508133129751061
11301174911014351221586
21411131237141015680592
36111381410795015142312



S8
0123456789101112131415
01328461511110931450127
11151381037412561101492
17114191214206101315358
12114741081315129035611


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
167202129122817
11523265183110
282414322739
19133062211425

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
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725


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
57494133251791585042342618
10259514335271911360524436
635547393123157625446383022
1466153453729211352820124


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


Gi
5749413325179
1585042342618
1025951433527
1911360524436



Di
63554739312315
7625446383022
1466153453729
211352820124


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
14171124153281562110
23191242681672720132
415231374755304051453348
444939563453464250362932


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


LS
124681012141517192123252728

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.

Veja também


Introduction to encryption with DES
Introduction to encryption with DES
Introducción al cifrado mediante DES
Introducción al cifrado mediante DES
Introduction au chiffrement avec DES
Introduction au chiffrement avec DES
Introduzione alla cifratura con DES
Introduzione alla cifratura con DES
Última modificação: 22 de maio de 2017 às 15:09 por Pedro.Saude.
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.