Estudio de dos de los más comunes de los sistemas criptográficos en sistemas de comunicación: sistemas de ElGamal y rabin, obtenidos de la del criptosistema RSA

Criptografias ElGamal, Rabin e algumas técnicas de cifra- mento

Adriele Giareta Biase

Universidade Federal de Uberlândia - Faculdade de Matemática Graduanda em Matemática - PROMAT

adrielegbiase@ yahoo. com. br

Edson Agustini

Universidade Federal de Uberlândia - Faculdade de Matemática Professor Associado I

agustini@ ufu. br

Resumo: Nesse trabalho apresentamos um estudo de dois dos sistemas criptográficos mais comuns em sistemas de comunicações: os sistemas ElGamal e Rabin, derivados do sistema criptográfico RSA. Também apresentamos algumas técnicas de ciframento, como Criframento de Vigenère, Substituição de Hill, Sistema Merkle-Hellman (MH), Sistema de Rotores e Data Encryption Standard (DES). Para o desenvolvimento desses sistemas crip- tográficos, introduzimos alguns preliminares de Teoria dos Números, mais precisamente, algoritmos envolvendo números primos e congruências. Procuramos trabalhar com vários exemplos ilustrativos de cada técnica apre- sentada, com o objetivo de tornar o texto mais compreensivo. Por fim, algumas conclusões são apresentadas.

1 Introdução

Este trabalho é uma extensão do texto “Criptografia, Assinaturas Digitais e Senhas Segmentadas”, (1), no qual foi destacada a necessidade moderna de se proteger informações, por meio de criptografia, de modo que alguém indesejável não tenha acesso ao seu conteúdo.

O método mais conhecido de criptografia é o chamado RSA (Rivest, Shamir, Adleman) (7) e seus derivados, como o ElGamal e o Rabin (6), aos quais daremos ênfase nesse trabalho. Além desses, há o método D.E.S. - Data Encryption Standard, (10) e (5), também abordado nesse trabalho.

O texto está dividido em três partes do seguinte modo:

- Preliminares: são alguns resultados de Teoria dos Números, em complemento aos resultados apre- sentados em (1), que são interessantes para o desenvolvimento das seções subseqüentes.

- Técnicas de Ciframento: onde apresentamos algumas das principais técnicas de ciframento, como a Substituição de Hill, Ciframento de Vigenère, Sistema de Rotores e o Método MH.

- Criptografias: (duas seções) onde apresentamos a Criptografia ElGamal, Criptografia Rabin e a Criptografia D.E.S.

2 Preliminares

Os teoremas e as proposições apresentados nessa seção são básicos e suas demonstrações podem ser encontradas em livros introdutórios de Teoria dos Números como, por exemplo, (2) e (4).



36 FAMAT em Revista 2.1 O Pequeno Teorema de Fermat

Um resultado bastante útil durante os procedimentos de criptografia e deciframento de mensagens é o teorema enuciado abaixo.

Pequeno Teorema de Fermat. Se p > 1 é primo e a é um inteiro positivo não divisível por p, então:

ap−1 ≡ 1(mod p).

Demonstração.

Seja a seqüência de números