implementação e análise de desempenho do des e triplo-des

IMPLEMENTAÇÃO E ANÁLISE DE DESEMPENHO
DO DES E TRIPLO-DES
Renan Rodrigues de Oliveira e José Luiz de Freitas Júnior
Universidade Católica de Goiás
Departamento de Computação
Av. Universitária, 1440, Setor Universitário. Goiânia/GO
BRAZIL
E-mails: [email protected] e [email protected]
Resumo: Este poster apresenta um comparativo, com relação ao
desempenho, entre implementações dos algoritmos criptográficos DES e
Triplo-DES desenvolvidas nesta pesquisa e as apresentadas por London[3].
Utilizou-se como ferramentas a linguagem de programação C-ANSI e
sistema operacional Linux-Conectiva 8. Apresentam-se os principais
procedimentos em C responsáveis pelo ganho em desempenho dos
algoritmos DES e Triplo-DES.
1 Introdução
Atualmente, devido ao avanço contínuo dos meios de comunicação e transmissão de
dados, surgem diversas situações que necessitam de um certo nível de segurança,
tornando-se aparente o problema da exposição destes dados ao acesso e uso por pessoas
ou entidades não autorizadas. Neste contexto, surge a necessidade de se utilizar a
criptografia.
Um dos algoritmos criptográficos mais utilizado e difundido é o DES (Data Encryption
Standard); proposto pela IBM em 1974 e adotado como padrão pelo governo Americano
em 1977 [6]. Em suas operações, utiliza basicamente permutações, transformações,
substituições e operações de ou-exclusivo (xor) bit a bit. O DES foi utilizado como padrão
até 2001, “cedendo lugar” ao AES (Advanced Encryption Standart), mas ainda é bastante
utilizado na versão conhecida como Triplo-DES que ainda é considerado seguro para o
padrões atuais.
Implementou-se o DES e Triplo-DES e apresenta-se, neste poster, uma
avaliação/análise de desempenho destas implementações com as feitas por London [3], ou
seja, tratam-se de importantes implementações, pois as mesmas apresentaram melhoras
consideráveis com relação ao desempenho com as publicadas por Loudon em 2000 [3];
2 Implementação do DES e Triplo-DES
Considerando que o DES opera sobre blocos de 64 bits, não deve ser surpresa o fato de
que seja freqüentemente implementado em hardware. Mas também há lugar para
implementações em software, onde é útil ter várias operações básicas para auxiliar no
transporte das numerosas permutações, transformações e substituições necessárias no
processo de cifragem e decifragem. Para isso, freqüentemente é necessária a execução de
operações em nível de um bit de uma determinada estrutura.
Para se acessar um bit qualquer, é necessário buscar-se a estrutura que contem o bit
desejado, construir uma máscara apropriada de acordo com a posição do bit que se deseja
acessar e selecioná-lo com operações lógicas adequadas. Estas são operações simples e
rápidas, mas devido a quantidade de operações que são realizadas para se acessar um bit e
trabalhando-se com um grande volume de dados, podem não trazer um tempo de
execução satisfatório na implementação do DES.
Nas implementações em software, surge a possibilidade de se trabalhar apenas com
bytes. O byte é o menor dado endereçável, isto é, o menor item que pode ser acessado
individualmente. É um tipo de dado “mais visível” que o bit, reduzindo o tempo de acesso
às informações requeridas pelo DES e conseqüentemente o tempo de execução da
aplicação. Para esse tipo de implementação são utilizadas cadeias de strings onde, no
trecho de código apresentado na figura 4, cada byte da string representa o estado de um bit
(‘0’ para 0 ou ‘1’ para 1) que são normalmente tratados nas operações realizadas pelo
DES através de procedimentos específicos.
Como exemplo, é apresentado a seguir (figura 1) o procedimento de permutação do
DES, numa implementação baseada em bits, juntamente com outros procedimentos de que
necessita (figura 2 e 3).
void permuta1(unsigned char *bits,const int *mapeamento, int tam)
{unsigned char temp[8]; int i;
for(i=0;i<tam;i++)
bit_set(temp,i,bit_get(bits,mapeamento[i]-1));
memcpy(bits,temp,8); }
Figura 1 - Procedimento de permutação do DES baseado em bits [3]
int bit_get(unsigned char *bits, int pos)
{ unsigned char mask; int i; mask = 0x80;
for(i=0;i<(pos%8);i++)
mask = mask>>1;
return(((mask & bits[(int)(pos/8)]) == mask) ? 1 : 0); }
Figura 2 - Verifica o estado de um determinado bit [3]
void bit_set(unsigned char *bits, int pos, int state)
{unsigned char mask; int i; mask = 0x80;
for(i=0;i<(pos%8);i++)
mask=mask>>1;
if(state)
bits[pos/8]=bits[pos/8] | mask;
else bits[pos/8]=bits[pos/8] & (~mask);}
Figura 3 - Muda o estado de um determinado bit [3]
O procedimento de permutação trabalhando-se apenas com bytes, pode ser reduzido ao
código apresentado na figura 4.
void permuta2(char *bits,const int *mapeamento,int tam)
{int i;
char per[tam];
for (i=0;i<tam;i++)
per[i]=bits[mapeamento[i]-1];
strcpy(bits,per); }
Figura 4 - Procedimento de permutação do DES baseado em bytes.
Apesar de ser uma implementação “menos elegante”, há uma diminuição da sobrecarga
para se realizar as permutações, pois cada permutação é feita de maneira direta
considerando o fácil acesso a um determinado byte que representa o estado de um bit.
Como no DES existem muitas tabelas de permutações de bits, com esse tipo de acesso
consegue-se reduzir de maneira considerável o tempo de execução total do algoritmo.
Ainda considerando a implementação em nível de bit, o procedimento responsável pela
operação de xor também contribui na sobrecarga da execução total do DES.
Este procedimento, quando implementado, realizando a operação de xor diretamente
em grupos de bits apresenta um tempo de execução mais satisfatório, do que realizando a
operação de xor bit por bit.
Como o objetivo é a comparação de implementações diferentes, qualquer modificação
pode trazer grande discrepância no resultado final.
Os resultados obtidos mostram que quanto menos se trabalha com bits individualmente,
mais fácil é o acesso aos dados e mais se ganha no tempo de execução.
3 Análise dos Resultados Obtidos
As tabelas 1 e 2 mostram os resultados obtidos nas implementações mencionadas,
executadas em um Pentium II - 400 Mhz no sistema Linux - Conectiva 8.
Tabela 1 - Tempo de execução do algoritmo DES
Qu an t i dade
d e b l o co s d e
6 4 bi t s
1 0 .0 0 0
5 0 .0 0 0
1 0 0 .0 0 0
T e m p o T o t a l d a I m p l e m e n t a çã o
B as eada
B as eada
B as eada
em by t es
em bi t s 1 1
em bi t s 2 2
0 m0 2 . 9 3 8 s 0 m1 0 . 2 6 7 s 0 m1 7 . 9 7 4 s
0 m1 4 . 4 4 7 s 0 m5 1 . 2 9 4 s 1 m2 9 . 6 8 9 s
0 m2 8 . 7 3 2 s 1 m4 2 . 2 5 6 s 2 m5 9 . 4 8 3 s
Analisando a tabela 1, a implementação do DES baseada em bytes apresenta ser em
média 83,65%, [1 - (0m02.938s / 0m17.974s) x 100], mais rápida do que a
implementação baseada em bits2 e 71,38%, [1 - (0m02.938s / 0m10.267s) x 100], mais
rápida que a implementação baseada em bits1.
1
2
Utiliza procedimento responsável pela operação xor em grupos de bits.
Utiliza procedimento responsável pela operação xor bit por bit.
Tabela 2 -Tempo de execução do Triplo-DES
Qu an t i dade
d e b l o co s d e
6 4 bi t s
1 0 .0 0 0
5 0 .0 0 0
1 0 0 .0 0 0
T e m p o T o t a l d a I m p l e m e n t a çã o
B as eada
B as eada
B as eada
em by t es
em bi t s 1 1 em bi t s 2 2
0 m0 8 . 8 9 9 s 0 m3 0 . 7 8 1 s 0 m5 3 . 8 7 6 s
0 m4 4 . 3 2 1 s 2 m3 3 . 5 2 3 s 4 m2 9 . 0 4 7 s
1 m2 8 . 4 8 5 s 5 m0 6 . 7 9 9 s 8 m5 8 . 0 0 6 s
Era esperado que a implementação do Triplo-DES fosse três vezes mais lenta em
relação a implementação do DES normal, devido aos processos utilizados pelo TriploDES na cifragem. Na prática, analisando as tabelas 1 e 2, percebe-se que o Triplo-DES
possui em média menos de 1/3 da velocidade do DES normal, pois a implementação
baseada em bytes do DES (0m02.938s) e do Triplo-DES (0m08.899s), resulta-se em
3,029 (0m08.899s / 0m02.938s). Isto ocorre devido ao processo de geração dos dois
conjuntos de subchaves e artifícios de implementação.
A implementação do Triplo-DES baseada em bytes apresenta, proporcionalmente o
mesmo desempenho da implementação do DES normal.
4 Conclusão
Neste trabalho foram apresentadas diferentes implementações do algoritmo DES, e
apontados os principais procedimentos em linguagem C, responsáveis pela diferença no
tempo de execução total do algoritmo.
Comparando tais implementações, destacou-se a implementação baseada em bytes, que
devido às características das operações do DES, analisadas de outro ponto de vista em
uma implementação em software, proporcionou resultados mais significativos, tornando o
algoritmo DES mais de 4 vezes mais rápido.
Implementações do algoritmo DES em ASSEMBLY encontra-se em fase final, assim
como implementações do algoritmo IDEA e AES e serão publicadas futuramente.
5 Referências
1. Denning, Dorothy E., (Dorothy Elizabeth), Cryptography and Data Security. Addison-Wesley,
1982
2. Júnior, José Luiz de Freitas, Teixeira, Edilberto Pereira, Souza, João Nunes: Cryptographic
System For Storage Of Data Using Linear Codes, IJCR – International Journal of Computer
Research, Volume 12, Number 1, pp. 73-80. Nova Science Publishers, 2003.
3. London, Kyle, Dominando Algoritmos com C. Rio de Janeiro, Editora Ciência Moderna Ltda.,
2000.
4. Salomaa, Arto, Public-Key Cryptography (EATCS monographs on theoretical computer science;
v.23), 2nd enlarged ed. 1996
5. Schneier, Bruce., Aplied Cryptography: Protocols, algorithms and source code in C. New York:
John Wiley, 1996.
6. Stinson, D. R., Cryptography: Theory And Practice. CRC Press LLC, 1995.