• Samedi 22 novembre 2008 - 21:07:47
• inscrits : 1074157
• connectés : 55270
• questions/jour : 4836
• Taux de réponse : 75.07%

Criptologia Criptografia Codificação por substituição Codificação simples Codificação por transposição Codificação simétrica Chaves privadas Codificação assimétrica Chaves públicas Chaves de sessão Assinatura electrónica Public Key Infractructure (PKI) Certificados Cryptosystemes Chiffrement Vigenère Enigma DES RSA PGP Legislação Legislação Protocolos protegidos Secure Sockets Layers (SSL) Secure Shell (SSH) S-HTTP Protocolo SET S/MIME Mais informações Vírus Cavalo de Troia Spyware Hoax Firewall FAQ Sécurtié; FAQ Internet

DES, A codificação à chave secreta

15 de maio de 1973 o NBS (National Institute of Standards and Technology) lançou uma chamada Federal Register (o equivalente a Estado-Unix do Jornal Oficial em França) para a criação de um algoritmo de codificação que responde aos critérios seguintes:

• possuir um elevado nível de segurança ligado à uma chave pequena que serve à codificação e déchiffrement
• ser compreensível
• não depender da confidencialidade do algoritmo
• ser adaptável e económico
• ser eficaz e exportável

Fim 1974, IBM propõe “Lucifer”, que, graças ao NSA (National Security Agency), é alterado 23 de novembro de 1976 para dar o DES (Datar Encriptação Standard). O DES foi finalmente verão aprovado em 1978 pelo NBS. O DES foi normalizado pelo ANSI (American Cidadão 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, das quais de 8 bits (um byte) servem de teste de paridade (para verificar a integridade da chave). Cada bit de paridade da chave (1 todas as 8 bits) serve a testar um dos bytes da chave por paridade ímpar, quer dizer que cada uma das bits de paridade é ajustado de forma a ter um número ímpar “de 1” no byte à quem pertence. A chave possui por conseguinte um comprimento “útil” de 56 bits, que significa que únicas 56 bits servem realmente no algoritmo.

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

A chave é codificada das 64 bits e formada de 16 blocos de 4 bits, geralmente notados k₁ à k₁₆. Já que as“únicas” 56 bits servem certamente a calcular, pode existir 2⁵⁶ (quer dizer 7.2*10¹⁶) chaves diferentes!

O algoritmo do DES

As grandes linhas do algoritmo são as seguintes:

• Fracionamento do texto em blocos de 64 bits (8 bytes);
• Permutação inicial dos blocos;
• Corte dos blocos em duas partes: esquerda e direita, nomeadas G e D;
• Etapas de permutação e de substituição repetidas 16 vezes (chamados redondos);
• Recollement das partes esquerdo e direita seguidamente permutação inicial oposto.

Fracionamento do texto

Permutação inicial

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

Esta matriz de permutação indica, percorrendo a matriz da esquerda para a direita seguidamente de parte superior inferior, que o 58ème bit do bloco de texto de 64 bits reencontra-se em primeira posição, o 50ème em segunda posição e assim de sequência.

Scindement em blocos de 32 bits

Uma vez a permutação inicial realizada, o bloco de 64 bits é cindido em dois blocos de 32 bits, notadas respetivamente G e D (para esquerda e direita, a notação anglo-saxona L e R para Left and Right). Nota-se G₀ e D₀ o estado inicial destes dois blocos:

É interessante observar que G₀ contem todas as bits que possuem uma posição igual na mensagem inicial, enquanto D₀ contem as bits de posição ímpar.

Rondas

Os blocos G_n e D_n são apresentados um conjunto de transformação iterativos chamados redondos, esclarecidos neste esquema, e cujos detalhes são dados plus bas:

Função de expansão

As 32 bits do bloco D₀ são estendidas à 48 bits graças à uma mesa (matriz) chamadas conta de expansão (notado E), na qual as 48 bits são misturadas e 16 entre eles são duplicados:

Assim, a última bit de D₀ (quer dizer a 7.a bit do bloco de origem) torna-se o primeiro, o primeiro torna-se o segundo,…
De mais, as bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 e 29 de D₀ (respetivamente 57,33,25, l, 59,35,27,3,6l, 37,29,5,63,39,31 e 7 do bloco de origem) são duplicadas e disseminação na matriz.

OU exclusivo com a chave

A matriz resultante de 48 bits é chamada D'₀ ou E[D₀]. O algoritmo procede de seguidamente às OU exclusivo entre a primeira chave K₁ et E[D₀]. O resultado deste OU exclusivo é uma matriz de 48 bits que chamaremos D₀ por conveniência (não se age do D₀ de partida!).

Função de substituição

D₀é cindido seguidamente em 8 blocos de 6 bits, notado D_0i. Cada um destes blocos passa por funções de seleção (chamados às vezes caixas de substituição ou funções de compressão), notadas geralmente S_i.
As primeiras e últimas bits de cada D_0idetermina (binário) a linha da função de seleção, as outras bits (respetivamente 2,3,4 e 5) determinam a coluna. A seleção da linha que faz-se sobre duas bits, ele lá A4 possibilidades (0,1,2,3). A seleção da coluna que faz-se das 4 bits, há 16 possibilidades (0 à 15). Graças à esta informação, a função de seleção “seleciona” um valor codificado das 4 bits.

Eis a primeira função de substituição, representado por uma matriz de 4 por 16:

quer dizer D₀₁ igual à 101110. As primeiras e últimas bits dão 10, quer dizer 2 binário. As bits 2,3,4 e 5 dão 0111, quer dizer 7 binário. O resultado da função de seleção é por conseguinte o valor situado à linha n°2, na coluna n°7. Trata-se do valor 11, quer dizer do 111.

Cada um dos 8 blocos de 6 bits passou na função de seleção correspondente, que dá em saída 8 valores de 4 bits cada uma. Eis as outras funções de seleção:

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

Permutação

O bloco de 32 bits obtido por último é apresentado à uma permutação P incluindo eis a mesa:

Exclusivo

O conjunto destes resultados em saída de P é apresentado às OU Exclusivo com o G₀ de partida (como indicado sobre o primeiro esquema) para dar D1, enquanto o D₀ inicial dá G₁.

Iteração

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

Permutation initiale inverse

No fim das iterações, os dois blocos G₁₆ e D₁₆“recollés, seguidamente apresentados à permutação inicial oposto:

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

Geração das chaves

Já que o algoritmo do apresentado acima é público, toda a segurança descansa sobre a complexidade chaves de codificação.

O algoritmo abaixo mostra como obter partir de uma chave de 64 bits (composto de 64 caráteres alfanuméricos quaisquer) 8 chaves diversificadas de 48 bits cada uma que serve no algoritmo do DES :

Inicialmente as bits de paridade da chave são eliminadas a fim de obter uma chave de um comprimento útil de 56 bits.

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

Esta matriz pode com efeito escrever-se sob forma de dois matriz G_i e D_i (para esquerda e direita) compostas cada um de 28 bits:

Nota-se G₀ e D₀o resultado desta primeira permutação.

Estes dois blocos sofrem seguidamente uma rotação à esquerda, de tais maneiras que as bits em segunda posição tomam a primeira posição, os em terceira posição o segundo,…As bits em primeira posição passam em última posição.

Os 2 blocos de 28 bits são agrupados seguidamente num bloco de 56 bits. Este passa por uma permutação, notada CP-2, fornecendo em saída um bloco de 48 bits, representando a chave K_i.

Iterações do algoritmo permitem dar as 16 chavesK₁ à K₁₆ utilizadas no algortihme.

TDES, uma alternativa o DES

Em 1990 de Eli Biham e Adi Shamir puseram ao ponto o cryptanalyse diferencial que procura pares de texto em claridade e pares de texto calculados. Este método anda até a um número de rondas inferior à 15, ora número de 16 rondas está um presente no algoritmo apresentado acima.

Por outro lado, ainda que uma chave de 56 bits dá um número enorme de possibilidades, numerosos processadores permitem calcular mais de 106 chaves por segundo, assim, utilizados a paralelamente sobre um elevado número de máquinas, possível para um grande organismo (um Estado por exemplo) encontrar a boa chave…

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

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

Distingue-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, déchiffrement, codificação);
• DES-EEE2 et DES-EDE2 : uma chave diferente para a segunda operação (déchiffrement).

Em 1997 o NIST lançou uma nova chamada à projeto para elaborar o AES (Advanced Encryption Standard), um algoritmo de codificação destinado a substituir o DES.

O sistema de codificação DES trazido 5 todos os 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, Senhores Vincent Rijmen e Joan Daemen era escolhidos como novo standard pelo NIST. Este novo algoritmo baptizado RIJNDAEL pelos seus inventores, substituirá doravante o DES.

Mais informações

• http://csrc.nist.gov/encryption/tkencryption.html - Especificações dos algoritmos DES do TDES e do AES (síte do NIST);
• RFC 2420 RFC 2420 The PPP Triplo- da Encriptação Protocol (3DESE)