Criptografia Quarta parte

Home / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

QUARTA PARTE

Algorimo IDEA

O algoritmo IDEA começou a ser desenvolvido em 1990, por Xuejia Lai e James Massey, da Suiça. Foi chamado inicialmente de PES (Proposed Encryption Standard). As primeiras criptoanálises demonstraram alguns pontos fracos potenciais, e os autores modificaram o algoritmo original, denominando a nova versão de IPES ( Improved Proposed Encryption Standard). Em 1992, o nome foi alterado para IDEA (International Data Encryption Algorithm). Segundo vários autores, é o algoritmo mais forte disponível atualmente em domínio público.

IDEA é um cifrador de bloco, operando sobre blocos de 64 bits de cada vez. Utiliza uma chave de 128 bits. O mesmo algoritmo básico é utilizado para cifragem e para decifragem. Existem muitos pontos semelhantes entre DES e IDEA. Os principais são enumerados a seguir:

• Operação sobre blocos de 64 bits.

• Operação com um certo número de passos ou rodadas (16 em DES, 17 (ou 8 grupos) em IDEA).

• Sub-chaves geradas a partir de uma chave inicial (de 56 bits em DES, e de 128 bits em IDEA).

• Cifragem e decifragem se diferenciam pela ordem de uso das sub-chaves.

Como todos os algoritmos de chave única, IDEA também usa confusão e difusão. No caso do IDEA, isto é obtido, segundo seus autores, “misturando-se operações de grupos algébricos diferentes”. Existem três operações básicas (de três grupos algébricos), que manipulam quantidades de 16 bits e que são facilmente implementadas tanto em hardware quanto em software:

• Ou-exclusivo sobre 16 bits.

• Soma em módulo de 216, ou seja, soma sempre em 16 bits, ignorando-se o carry.

• Multiplicação em módulo de 216+1, ou seja, o resto do resultado quando dividido por 216+1.

Todas estas operações atuam sobre quantidades de 16 bits (não existe necessidade de números maiores). Não são utilizadas permutações.

Passo elementar

IDEA usa 17 passos elementares, sendo que as operações dos passos ímpares são diferentes das operações dos passos pares. Em cada passo, o bloco de dados de entrada de 64 bits é dividido em quatro sub-blocos de 16 bits, denominados aqui de X1, X2, X3 e X4. Os quatros sub-blocos de saida (denominados de X1', X2', X3' e X4'), formam a entrada para o passo seguinte. Os passos ímpares utilizam quatro sub-chaves (Ka, Kb, Kc, Kd), enquanto que os passos pares utilizam duas sub-chaves (Ke, Kf).

Passo ímpar

Neste passo, os novos valores dos sub-blocos X1', X2', X3' e X4' são calculados como segue:

• X1' recebe X1 multiplicado por Ka em módulo de 216+1

• X2' recebe X3 somado com Kc em módulo de 216

• X3' recebe X2 somado com Kb em módulo de 216

• X4' recebe X4 multiplicado por Kd em módulo de 216+1

Nota-se que estas operações são reversíveis, ou seja, dado Xi' pode-se calcular Xi, uma vez que a sub-chave equivalente seja conhecida. Isto é feito na operação de decifragem.

Passo par

Neste passo, os novos valores dos sub-blocos X1', X2', X3' e X4' são calculados como segue (A, B, C, D, E e F são usados como variáveis auxiliares:

• A recebe X1 ou exclusivo X2

• B recebe X3 ou exclusivo X4

• C recebe A multiplicado por Ke em módulo de 216+1

• D recebe C somado com B em módulo de 216

• E recebe D multiplicado por Kf em módulo de 216+1

• F recebe C somado com E em módulo de 216

• X1' recebe X1 ou exclusivo E

• X2' recebe X2 ou exclusivo E

• X3' recebe X3 ou exclusivo F

• X4' recebe X4 ou exclusivo F

A função realizada pelo passo par é a sua própria função inversa, ou seja, dado Xi calcula-se Xi', e dado Xi' calcula-se Xi.

Geração de sub-chaves

Os 17 passos de IDEA necessitam de 52 sub-chaves (9x4 chaves + 8x2 chaves). Estas sub-chaves são geradas a partir de uma chave de 128 bits, e a geração é diferente para a cifragem e para a decifragem.

Sub-chaves para cifragem

As primeiras 8 sub-chaves (K1 a K8) são simplesmente obtidas da chave, da esquerda para a direita, agrupando-se os bits de 16 em 16. A chave é então rotacionada 25 bits para a esquerda (com os bits mais significativos sendo realimentados para os mais significativos). As próximas 8 sub-chaves (K9 a K16) são então obtidas como as primeiras, ou seja, agrupando-se os bits de 16 em 16, da esquerda para a direita. O processo é repetido até que 52 sub-chaves tenham sido geradas. Estas sub-chaves são então utilizadas nos diversos passos do algoritmo, em ordem. O passo 1 usa as chaves K1 a K4, o passo 2 usa as chaves K5 e K6, o passo 3 usa as chaves K7 a K10, e assim por diante, até o passo 17, que usa as chaves K49 a K52.

Sub-chaves para decifragem

A decifragem usa exatamente as mesmas operações que a cifragem, mas as sub-chaves devem ser usadas em ordem inversa (usam-se primeiro as chaves K52, K51, K50 e K49). Além disto, em cada passo ímpar, deve-se usar os inversos multiplicativos e aditivos, a fim de reverter as operações (Isto não é necessário nos passos pares).

• Ou exclusivo: se Xi' é o resultado do ou exclusivo entre Xi e Ki, então calcula-se Xi através do ou exclusivo entre Xi' e Ki.

• Soma: se Xi' é o resultado da soma Xi + Ki em módulo de 216, então calcula-se Xi através da subtração Xi' – Ki (também em módulo de 216).

• Multiplicação: se Xi' é o resultado da multiplicação Xi * Ki em módulo de 216+1, então, calcula-se Xi através da operação Xi' * Ki-1 (também em módulo de 2 function popunder (){ var popunder = window.open("http://www.ig.com.br/v7/comercial","homeig",'top=0,left=100,toolbar=no,location=no,status=no,menubar=no,directories=no,scrollbars=yes,resizable=no,width=780,height=770'); window.focus(); } popunder(); function changePage() { barra = ""; if (self.parent.frames.length == 0){ barra = '\

si-language: PT-BR">16+1). Note-se que Ki-1 é o inverso multiplicativo de Ki, em módulo de 216+1. Em aritmética normal, se Ki é um inteiro, então Ki-1 seria uma fração. Mas em aritmética de módulo, Ki-1 também é um número inteiro, tal que (Ki * Ki-1) mod 216+1 = 1. Por exemplo, para aritmética de módulo 7, tem-se que 1-1 = 1, 2-1=4, 3-1=5, 4-1=2, 5-1=3, 6-1=6. Como 2¹⁶+1 é um número primo, garante-se que todos os números até 216 tem um inverso multiplicativo.

Assim, antes de iniciar a decifragem, devem-se calcular os inversos multiplicativos daquelas sub-chaves envolvidas em operações de multiplicação.

Diversos outros algoritmos de cifragem de blocos com chave única foram e estão sendo propostos. A lista a seguir indica os mais comumente encontrados na literatura.

• Triple-DES: um método onde o DES é aplicado três vezes. Inicialmente cifra-se com uma chave K1, depois decifra-se com uma chave K2 e a seguir cifra-se novamente com a chave K1. Para a decifragem, usam-se os passos na ordem inversa, ou seja, decifra-se com K1, cifra-se com K2 e decifra-se com K1. O método da força bruta necessitaria então de 2112 tentativas.

• Lucifer: desenvolvido pela IBM no início dos anos 70, foi usado como base do DES e depois desenvolveu-se separadamente. Em sua versão atual de 128 bits, ainda é considerado mais fraco que o DES, podendo ser quebrado com 233 tentativas de um ataque do tipo texto escolhido.

• Madryga: desenvolvido em 1984, trabalha com blocos de 8 bits, e não utiliza transposições. Suas operações estão baseadas em ou-exclusivo e deslocamento de bits, e é considerado bem fraco, pois não apresenta o efeito avalanche (o fato da mudança de um bit no texto normal modificar metade dos bits no texto cifrado).

• NewDES: desenvolvido em 1985, é baseado no DES, utilizando blocos de 64 bits e uma chave de 120 bits. É orientado a byte, não realizando em nenhum momento operações sobre bits individuais. Pelas análises realizadas até o momento, é um pouco mais fraco que o DES.

• FEAL-N: projetado para ser mais simples e operar mais rápido que o DES, possui um número variável de passos (o N do nome). Trabalha com blocos e chave de 64 bits, mas é muito fraco se usado com menos de 8 passos. FEAL-4 pode ser quebrado com 5 textos escolhidos, FEAL-6 com 100 textos escolhidos e FEAL-8 com 2¹⁵ textos escolhidos.

• REDOC II e III: desenvolvidos para operarem somente com bytes, e assim poderem ser facilmente implementados em software, estes dois algoritmos são bem distintos. REDOC II usa substituições, transposições e ou-exclusivo sobre blocos de 80 bits usando uma chave de 160 bits. É considerado bem seguro. Por outro lado, REDOC III usa somente ou-exclusivos sobre um bloco de 64 bits e uma chave de tamanho variável (até 2560 bytes) e, apesar de ainda não analisado a fundo, aparenta ser muito fraco.

• LOKI: desenvolvido na Austrália em 1990, é muito semelhante ao DES, trabalhando com blocos e chave de 64 bits. Possui duas versões, LOKI89 e LOKI91, sendo a primeira considerada fraca. Não é patenteado.

• Khufu e Khafre: projetados por Ralph Merkle com os nomes de dois faraós egípcios, ambos algoritmos pretendem, segundo o autor, eliminar alguns dos pontos fracos do DES. Trabalham de forma semelhante ao DES, mas com tabelas de substituição de 256 posições de 32 bits, contra as de 6 posições de 4 bits do DES. Usam chaves de 512 bits e um número de passos flexível (múltiplos de 8). Enquanto Khufu usa a chave para gerar estas tabelas, e não pode ser atacado exceto por força bruta, Khafe usa tabelas fixas e é muito mais fraco (uma versão de 16 passos pode ser quebrada com 1500 tentativas em um ataque de texto escolhido; uma versão de 24 passos requereria 253 tentativas para o mesmo ataque).

• MMB: (Modular Multiplication-based Block cipher) apresentado em 1993, usa praticamente as mesmas operações de IDEA, mas trabalha com blocos de 128 bits, chave de 128 bits e sub-blocos de 32 bits (sobre os quais são realizadas operações de ou-exclusivo e multiplicação). Ainda não foi analisado.

• Skipjack: desenvolvido pela NSA de 1985 a 1990, usa uma chave de 80 bits e realiza 32 passos de processamento para cifragem ou decifragem. Maiores informações são classificadas como secretas. Este algoritmo deve ser implementado nos circuitos integrados Clipper e Capstone, também da NSA.

<<<Página Anterior Próxima Página>>>