Kioskea
Recherche

Introdução à codificação DES

Março 2015

DES, A codificação com chave secreta

A 15 de Maio de 1973 o NBS (National Institute of Standards and Technology) lançou um apelo no Federal Register (o equivalente, nos Estado-Unidos, do Diário da República, em Portugal) 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 chave pequena que sirva para a codificação e descodificação
  • ser compreensível
  • não depender da confidencialidade do algoritmo
  • ser adaptável e económico
  • ser eficaz e exportável



No final de 1974, a IBM propõe “Lucifer” que, graças ao NSA (National Security Agency), é alterada a 23 de Novembro de 1976 para dar origem ao DES (Data Encryption Standard). O DES foi finalmente aprovado em 1978 pelo NBS. O DES foi normalizado pelo ANSI (American National Standard Institute) sob o nome de ANSI X3.92, mais conhecido sob a denominação DEA (Data Encryption Algorithm).

Princípio do DES

Trata-se de um sistema de codificação simétrico por blocos de 64 bits, dos quais8 bits (um octet) 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, quer dizer que cada um dos bits de paridade é ajustado de forma a ter um número ímpar “de 1” no byte a que pertence. A chave possui então um comprimento “útil” de 56 bits, o que significa que só 56 bits servem realmente no algoritmo.

O algoritmo consiste em efetuar combinações, substituições e permutações entre o texto a codificar e a chave, fazendo de modo a que as operações possam fazer-se nos dois sentidos (para a descodificação). A combinação entre substituições e permutações chama-se código produzido.

A chave é codificada em 64 bits e formada por 16 blocos de 4 bits, geralmente notados k1 à k16. Já que “apenas” 56 bits servem efectivamente para calcular, podem existir 256 (quer dizer 7.2*1016) chaves diferentes!

O algoritmo do DES

As grandes linhas do algoritmo são as seguintes:

  • Fraccionamento do texto em blocos de 64 bits (8 octetos);
  • Permuta inicial dos blocos;
  • Corte dos blocos em duas partes: esquerda e direita, nomeadas G e D;
  • Etapas de permuta e de substituição repetidas 16 vezes (chamadas voltas);
  • Recolamento das partes esquerda e direita, seguidamente permutação inicial inversa.



algorithme du DES

Fraccionamento do texto


Permutação inicial

Inicialmente, cada bit de um bloco é sujeito à permuta inicial, podendo ser representada pela matriz de permuta inicial (notada PI) seguinte:


PI
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157



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

Cisão em blocos de 32 bits

Uma vez realizada a permuta inicial, o bloco de 64 bits é cindido em dois blocos de 32 bits, notados respectivamente G e D (para esquerda e direita, a notação anglo-saxónica é L e R para Left and Right). Marcamos como G0 e D0 o estado inicial destes dois blocos:


G0
585042342618102
605244362820124
625446383022146
645648403224168




D0
57494133251791
595143352719113
615345372921135
635547393123157




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

Rondas

Os blocos Gn e Dn são sujeitos a um conjunto de transformações iterativas chamadas voltas, esclarecidas neste esquema, e cujos detalhes são dados abaixo:

rondes

Função de expansão

Os 32 bits do bloco D0 são estendidos até 48 bits graças a uma tabela (matriz) chamada tabela de expansão (marcada como E), na qual os 48 bits são misturados e 16 dentre eles sã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,…
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]. O algoritmo procede seguidamente a um OU exclusivo entre a primeira chave K1 e E[D0]. O resultado deste OU exclusivo é uma matriz de 48 bits que chamaremos D0 por conveniência (não se trata do D0 do início!).

Função de substituição

D0é cindido seguidamente em 8 blocos de 6 bits, notado D0i. Cada um destes blocos passa por funções de selecção (chamadas às vezes caixas de substituição ou funções de compressão), marcadas geralmente como Si.
Os primeiros e últimos bits de cada D0idetermina (em binário) a linha da função de selecção, os outros bits (respectivamente 2,3,4 e 5) determinam a coluna. A selecção da linha, fazendo-se sobre duas bits, dá 4 possibilidades (0,1,2,3). A seleção da coluna que se faz-se em 4 bits tem 16 possibilidades (0 a 15). Graças a esta informação, a função de selecção “selecciona” um valor codificado em 4 bits.


Eis 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, quer dizer, 2 binário. Os bits 2,3,4 e 5 dão 0111, quer dizer 7 binário. O resultado da função de selecção é então o valor situado na linha n°2, na coluna n°7. Trata-se do valor 11, ou em binário 111.


Cada um dos 8 blocos de 6 bits passou na função de selecção correspondente, o que dá no final 8 valores de 4 bits cada um. Eis as outras funções de selecçã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



Cada bloco de 6 bits assim é substituído num bloco de 4 bits. Estes bits são agrupados para formar um bloco de 32 bits.

Permuta

O bloco de 32 bits obtido é por último 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 é sujeito a um OU Exclusivo com o G0 de partida (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 seguidamente sujeitos à permuta inicial inversa:


PI-1
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725




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

Geração das chaves

Dado que o algoritmo do apresentado acima é público, toda a segurança assenta 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 que servem no algoritmo do DES :

algorithme de generation des cles 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




Esta matriz pode, com efeito, escrever-se sob forma de duas matrizes Gi e Di (para esquerda e direita) compostas cada um de 28 bits:


Gi
5749413325179
1585042342618
1025951433527
1911360524436




Di
63554739312315
7625446383022
1466153453729
211352820124



Marca-se como G0 e D0o resultado desta primeira permuta.

Estes dois blocos sofrem seguidamente 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,…Os bits em primeira posição passam para última posição.

Os 2 blocos de 28 bits são agrupados seguidamente 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 chavesK1 à K16 utilizadas no algoritmo de DES.

LS
124681012141517192123252728

TDES, uma alternativa ao DES

Em 1990, Eli Biham e Adi Shamir afinaram a criptaná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á um presente no algoritmo apresentado acima.

Por outro lado, mesmo se uma chave de 56 bits dá um número enorme de possibilidades, numerosos processadores permitem calcular mais de 106 chaves por segundo; assim, utilizados paralelamente num elevado número de máquinas, é 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ção DES com a ajuda de duas chaves de 56 bits (o que equivale a uma chave de 112 bits). Este método é chamado Triplo DES, notado TDES (às vezes 3DES ou 3-DES).

Triple DES - 3DES



O TDES permite aumentar significativamente a segurança, contudo tem o inconveniente essencial de pedir igualmente mais recursos para a codificação e descodificação.

Distinguem-se habitualmente vários tipos de codificação tripla DES :

  • DES-EEE3 :3 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 et DES-EDE2 : uma chave diferente para a segunda operação (descodificação).




Em 1997 o NIST lançou um novo apelo para um projecto 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 actualizado todos os 5 anos. Em 2000, aquando da última revisão, após um processo de avaliação que durou 3 anos, o algoritmo concebido conjuntamente por dois candidatos belgas, Vincent Rijmen e Joan Daemen, foi escolhido como novo standard pelo NIST. Este novo algoritmo baptizado RIJNDAEL devido aos seus inventores, substituirá doravante o DES.

Mais informações

Para uma leitura offline, é possível baixar gratuitamente este artigo no formato PDF:
Introducao-a-codificacao-des.pdf

A ver igualmente


Introduction to encryption with DES
Introduction to encryption with DES
Introducción al cifrado mediante DES
Introducción al cifrado mediante DES
Chiffrierung mit DES
Chiffrierung mit DES
Introduction au chiffrement avec DES
Introduction au chiffrement avec DES
Introduzione alla cifratura con DES
Introduzione alla cifratura con DES
Este documento, intitulado « Introdução à codificação DES »a partir de Kioskea (pt.kioskea.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.