Criptografia Numaboa

O algoritmo IDEA ilustrado

Dom

Set

2005

17:16

(21 votos, média 4.81 de 5)

Detalhes: Categoria: Cifras de bloco; Atualização: Terça, 14 Abril 2009 14:06; Autor: vovó Vicki; Acessos: 29557

O algoritmo IDEA (International Data Encryption Algorithm) foi desenvolvido em 1990, na ETH Zurique - Suíça, por James L. Massey e Xueija Lai. O IDEA é um algoritmo simétrico que utiliza uma chave de 128 bits.

Originalmente, o IDEA foi chamado de PES (Proposed Encryption Standard). Um ano após o seu lançamento, em 1991, Biham e Shamir demonstraram que o algoritmo era susceptível à criptoanálise diferencial e os autores fizeram modificações substanciais. Chamaram o novo algoritmo de IPES (Improved Proposed Encryption Standard). Em 1992, o IPES foi rebatizado transformando-se no IDEA, um dos melhores algoritmos de bloco. O proprietário da patente deste método é a ASCOM. Visando sua disseminação, a ASCOM autorizou o uso não comercial do algoritmo.

O algoritmo IDEA

O algoritmo é usado tanto para a cifragem quanto para a decifração e, como outras cifras de bloco, usa a confusão e a difusão (maiores detalhes na Teoria da Informação) para produzir o texto cifrado. A filosofia que norteou este projeto foi "misturar operações de grupos algébricos diferentes". O IDEA possui três grupos algébricos cujas operações são misturadas. Estas operações, que podem ser facilmente implementadas via hardware e/ou software, são:

XOR
Adição módulo 2¹⁶ (adição ignorando qualquer overflow)
Multiplicação módulo 2¹⁶+1 (multiplicação ignorando qualquer overflow)

Todas estas operações são feitas com blocos de 16 bits, o que faz com que este algoritmo também seja eficiente em processadores de 16 bits.

Descrição do IDEA

Fluxograma do algoritmo IDEA

Na cifragem, o texto claro é dividido em blocos de 64 bits. Cada um destes blocos é dividido em quatro sub-blocos de 16 bits: B1, B2, B3 e B4. Estes quatro sub-blocos são a entrada da primeira volta ou rodada do algoritmo. No total, são oito rodadas. Em cada rodada, os quatro sub-blocos são submetidos à operação lógica XOR, somados e multiplicados entre si e com seis sub-blocos de 16 bits oriundos da chave (K1, K2, K3, K4, K5 e K6). Entre cada rodada, o segundo e o terceiro sub-bloco são trocados.

Em cada rodada, a sequência de eventos é a seguinte (acompanhe no fluxograma acima):

Multiplicação de B1 pelo primeiro sub-bloco da chave K1.
Adição de B2 com o segundo sub-bloco da chave K2.
Adição de B3 com o terceiro sub-bloco da chave K3.
Multiplicação de B4 pelo quarto sub-bloco da chave K4.
XOR entre os resultados obtidos nas etapas (1) e (3).
XOR entre s resultados obtidos nas etapas (2) e (4).
Multiplicação do resultado da etapa (5) pelo quinto sub-bloco da chave K5
Adição dos resultados das etapas (6) e (7).
Multiplicação do resultado da etapa (8) pelo sexto sub-bloco da chave K6.
Adição dos resultados das etapas (7) e (9).
XOR entre os resultados obtidos nas etapas (1) e (9).
XOR entre os resultados obtidos nas etapas (3) e (9).
XOR entre os resultados obtidos nas etapas (2) e (10).
XOR entre os resultados obtidos nas etapas (4) e (10).

A saída da rodada são os quatro sub-blocos resultantes das etapas (11), (13), (12) e (14). Exceto na última rodada, os sub-blocos (13) e (12) trocam de lugar e esta nova sequência de sub-blocos será a entrada para a próxima rodada.

Após a oitava rodada, a saída final é transformada com:

Multiplicação de B1 pelo primeiro sub-bloco da chave K1.
Adição de B2 com o segundo sub-bloco da chave K2.
Adição de B3 com o terceiro sub-bloco da chave K3.
Multiplicação de B4 pelo quarto sub-bloco da chave K4.

No final, os quatro sub-blocos obtidos (G1, G2, G3 e G4) são concatenados para produzir o texto cifrado.

Sub-blocos da chave

A obtenção de sub-blocos da chave é simples. O algoritmo usa 52 destes sub-blocos - seis em cada uma das oito rodadas, mais quatro na última transformação. Inicialmente, a chave de 128 bits é dividida em oito sub-blocos de 16 bits. Estes são os primeiros sub-blocos da chave: seis serão usados na primeira rodada e os outros dois serão K1 e K2 da segunda rodada. Depois disto, os bits da chave são deslocados 25 posições para a esquerda e a nova chave é novamente dividida em oito sub-blocos, dos quais quatro serão usados na segunda rodada e quatro na terceira. Este processo continua enquanto sub-blocos da chave forem necessários para completar o algoritmo.

A decifração do IDEA

O processo da decifração é o mesmo da cifragem, com exceção dos sub-blocos da chave que precisam ser revertidos. Na decifração, os sub-blocos da chave são o inverso aditivo ou o inverso multiplicativo dos sub-blocos da chave usados na cifragem. É preciso salientar que, no caso do IDEA, o inverso multiplicativo de 0 é 0. Estes cálculos são um pouco trabalhosos, mas, em compensação, só precisam ser realizados uma vez para cada um dos sub-blocos. A tabela abaixo mostra os sub-blocos da chave na cifragem e os sub-blocos da chave correspondentes na decifração:

     RODADA     SUB-BLOCOS NA CIFRAGEM
     ------     ---------------------------------
        1       K1⁽¹⁾ K2⁽¹⁾ K3⁽¹⁾ K4⁽¹⁾ K5⁽¹⁾ K6⁽¹⁾
        2       K1⁽²⁾ K2⁽²⁾ K3⁽²⁾ K4⁽²⁾ K5⁽²⁾ K6⁽²⁾
        3       K1⁽³⁾ K2⁽³⁾ K3⁽³⁾ K4⁽³⁾ K5⁽³⁾ K6⁽³⁾
        4       K1⁽⁴⁾ K2⁽⁴⁾ K3⁽⁴⁾ K4⁽⁴⁾ K5⁽⁴⁾ K6⁽⁴⁾
        5       K1⁽⁵⁾ K2⁽⁵⁾ K3⁽⁵⁾ K4⁽⁵⁾ K5⁽⁵⁾ K6⁽⁵⁾
        6       K1⁽⁶⁾ K2⁽⁶⁾ K3⁽⁶⁾ K4⁽⁶⁾ K5⁽⁶⁾ K6⁽⁶⁾
        7       K1⁽⁷⁾ K2⁽⁷⁾ K3⁽⁷⁾ K4⁽⁷⁾ K5⁽⁷⁾ K6⁽⁷⁾
        8       K1⁽⁸⁾ K2⁽⁸⁾ K3⁽⁸⁾ K4⁽⁸⁾ K5⁽⁸⁾ K6⁽⁸⁾
      saída     K1⁽⁹⁾ K2⁽⁹⁾ K3⁽⁹⁾ K4⁽⁹⁾

     RODADA     SUB-BLOCOS NA DECIFRAÇÃO
     ------     --------------------------------------------
        1       K1⁽⁹⁾-1  -K2⁽⁹⁾  -K3⁽⁹⁾  K4⁽⁹⁾-1  K5⁽⁸⁾  K6⁽⁸⁾
        2       K1⁽⁸⁾-1  -K2⁽⁸⁾  -K3⁽⁸⁾  K4⁽⁸⁾-1  K5⁽⁷⁾  K6⁽⁷⁾
        3       K1⁽⁷⁾-1  -K2⁽⁷⁾  -K3⁽⁷⁾  K4⁽⁷⁾-1  K5⁽⁶⁾  K6⁽⁶⁾
        4       K1⁽⁶⁾-1  -K2⁽⁶⁾  -K3⁽⁶⁾  K4⁽⁶⁾-1  K5⁽⁵⁾  K6⁽⁵⁾
        5       K1⁽⁵⁾-1  -K2⁽⁵⁾  -K3⁽⁵⁾  K4⁽⁵⁾-1  K5⁽⁴⁾  K6⁽⁴⁾
        6       K1⁽⁴⁾-1  -K2⁽⁴⁾  -K3⁽⁴⁾  K4⁽⁴⁾-1  K5⁽³⁾  K6⁽³⁾
        7       K1⁽³⁾-1  -K2⁽³⁾  -K3⁽³⁾  K4⁽³⁾-1  K5⁽²⁾  K6⁽²⁾
        8       K1⁽²⁾-1  -K2⁽²⁾  -K3⁽²⁾  K4⁽²⁾-1  K5⁽¹⁾  K6⁽¹⁾
      saída     K1⁽¹⁾-1  -K2⁽¹⁾  -K3⁽¹⁾  K4⁽¹⁾-1

A velocidade do IDEA

A velocidade de cifragem e decifração do IDEA é praticamente a mesma do DES. Devido aos cálculos suplementares nos sub-blocos da chave, a decifração é um pouco mais lenta do que a cifragem.

Criptoanálise

O comprimento da chave do IDEA é de 128 bits. Um ataque de força bruta dos mais eficientes precisaria fazer 2¹²⁸ (ou 10³⁶) cifragens para recuperar a chave. Se dispuséssemos de um bilhão de chips que testassem um bilhão de chaves por segundo cada um, ainda assim seriam necessários 10¹³ anos para se realizar a tarefa! Talvez a força bruta não seja o melhor método para se quebrar o IDEA...

O algoritmo IDEA é imune à criptoanálise diferencial e, de acordo com Eli Biham, seu ataque criptoanalítico de chave relacionada também não funcionou contra o IDEA. Existem alguns textos que "descobriram" uma classe de chaves fracas. Estas chaves fracas são diferentes das chamadas chaves fracas do DES, onde a função de cifragem é auto-inversa. São consideradas fracas porque, se forem utilizadas, um atacante pode identificá-las com facilidade através de um ataque de texto claro escolhido. Por exemplo, a chave

0000 0000 0F00 0000 0000 000F FFFF F000

é uma chave fraca, sendo que os F podem ser substituídos por qualquer dígito hexadecimal. Este não é um problema crucial porque a chance de acidentalmente gerar uma chave deste tipo é extremamente pequena, da ordem de 2^-96.

Programando o IDEA

A seguir, transcrevo o texto HOWTO: INTERNATIONAL DATA ENCRYPTION ALGORITHM - sumário da implementação por Fauzan Mirza ( O endereço de e-mail address está sendo protegido de spambots. Você precisa ativar o JavaScript enabled para vê-lo. )

Observações do autor

Este documento foi escrito para ajudar programadores a entenderem como implementar o criptossistema IDEA.

Obrigado a Colin Plumb ( O endereço de e-mail address está sendo protegido de spambots. Você precisa ativar o JavaScript enabled para vê-lo. ) por ajudar a eliminar os erros que fiz na versão rascunho deste documento. As fontes foram obtidas da implementação do IDEA em assembly 8086 feita por Colin Plumb e a fonte da referência IDEA é de Richard De Moliner ( O endereço de e-mail address está sendo protegido de spambots. Você precisa ativar o JavaScript enabled para vê-lo. ). Por favor, avisem-me se houver erros ou omissões.

O IDEA trabalha com unidades de 16 bits. Se você for processar bytes, estes estão definidos como big-endian de modo que, numa máquina Intel, é preciso trocar os bytes de posição.

O IDEA possui uma chave de usuário de 16 bytes (128 bits) que é expandida numa subchave de 104 bytes (832 bits). Os dados são processados em blocos de 8 bytes (64 bits).

O código fonte em C

A função Idea precisa receber a subchave, não a chave do usuário. O exemplo de código a seguir exige que a multiplicação seja feita em módulo 65537 (como definido nas especificações do IDEA). Uma entrada zero é considerada como sendo 65536.

void Idea(u_int16 *in, u_int16 *out, u_int16 *key) { u_int16 x0, x1, x2, x3, t0, t1, round; x0 = *in++; x1 = *in++; x2 = *in++; x3 = *in; for (round = 0; round < 8; round++) { x0 *= *key++; x1 += *key++; x2 += *key++; x3 *= *key++; t0 = x1; t1 = x2; x2 ^= x0; x1 ^= x3; x2 *= *key++; x1 += x2; x1 *= *key++; x2 += x1; x0 ^= x1; x3 ^= x2; x1 ^= t1; x2 ^= t0; } *out++ = x0 * *key++; *out++ = x2 + *key++; /* NB: Ordem */ *out++ = x1 + *key++; *out = x3 * *key; }

A função a seguir pode ser usada para realizar a multiplicação módulo 65537 usada no IDEA.

u_int16 mul(u_int16 x, u_int16 y) { u_int32 p=x*y; if (p == 0) x = 65537-x-y; else { x = p >> 16; y = p; x = y-x; if (y < x) x += 65537; } return x; }

A função a seguir é usada para expandir a chave do usuário e obter a subchave de cifragem. Os primeiros 16 bytes são a chave do usuário, o restante da subchave é calculado fazendo a rotação dos 16 bytes anteriores deslocando-os 25 bits para a esquerda. O processo é repetido até que a subchave seja completada. O código a seguir pode ser otimizado.

void Expandkey(u_int16 *ukey, u_int16 *key) { int i; for (i=0; i<8; i++) key[i]=ukey[i]; for (i=8; i<52; i++) { if ((i & 7) < 6) key[i]=(key[i-7] & 127) << 9 | key[i-6] >> 7; else if ((i & 7) == 6) key[i]=(key[i-7] & 127) << 9 | key[i-14] >> 7; else key[i]=(key[i-15] & 127) << 9 | key[i-14] >> 7; } }

A função para inverter a subchave de cifragem para obter a subchave de decifragem é necessária para decifrações que usam modos ECB e CBC. Inclui também as funções dos inversos multiplicativo e aditivo.

Regras:

x + addinv(x) == 0
x * mulinv(x) == 1 (modulo 65537)

void Invertkey(u_int16 *in, u_int16 *out) { u_int16 t1, t2, t3, t4, round; u_int16 *p = out + 52; /* We work backwards */ t1 = mulinv(*in++); t2 = addinv(*in++); t3 = addinv(*in++); t4 = mulinv(*in++); *--p = t4; *--p = t3; *--p = t2; *--p = t1; for (round = 1; round < 8; round++) { t1 = *in++; t2 = *in++; *--p = t2; *--p = t1; t1 = mulinv(*in++); t2 = addinv(*in++); t3 = addinv(*in++); t4 = mulinv(*in++); *--p = t4; *--p = t2; /* NB: Order */ *--p = t3; *--p = t1; } t1 = *in++; t2 = *in++; *--p = t2; *--p = t1; t1 = mulinv(*in++); t2 = addinv(*in++); t3 = addinv(*in++); t4 = mulinv(*in++); *--p = t4; *--p = t3; *--p = t2; *--p = t1; } u_int16 addinv(u_int16 x) { return 0-x; }

Esta função calcula o inverso multiplicativo usando o algoritmo do Máximo Divisor Comum de Euclides. Zero e um são inversos deles mesmos.

u_int16 mulinv(u_int16 x) { u_int16 t0, t1, q, y; if (x < 2) return x; t0 = 0; t1 = 65537 / x; y = 65537 % x; while (y != 1) { q = x / y; x = x % y; t0 = t0 + (t1 * q); if (x == 1) return t0; q = y / x; y = y % x; t1 = t1 + (t0 * q); } return 65537-x; } ------------------------ final do texto de Fauzan Mirza -----------------------

Comentários e Sugestões

Caso você queira criticar, complementar ou alterar este texto sobre o algoritmo IDEA, faça contato por email usando a área de texto do menu identificada com PERGUNTA/CONTATO. É a forma mais rápida de se comunicar comigo. Não se esqueça de incluir o seu endereço de email para que eu possa responder. Por favor, confira seu endereço antes de enviar sua mensagem.

Grande abraço

vovo vovó Vicki

Fontes

at-mix
Schneier, Bruce - Applied Cryptography, 1994
HOWTO: INTERNATIONAL DATA ENCRYPTION ALGORITHM

Aldeia Numaboa UM PORTAL DIFERENTE EM PORTUGUÊS DO BRASIL

Navegação da pesquisa

Navegação

Pesquisa