Criptografia RSA
Marcos Antônio da Câmara – Tutor do PET
Universidade Federal de Uberlândia – Faculdade de Matemática
38408-100, Campus Santa Mônica, Uberlândia, MG
E-mail: [email protected]
Rafael Alves Figueiredo
Universidade Federal de Uberlândia – Faculdade de Matemática
38408-100, Campus Santa Mônica, Uberlândia, MG
E-mail: [email protected]
RESUMO
O sistema de criptografia, com chave pública,
é utilizado nas comunicações eletrônicas como
compras pela internet, uso de cartões de
crédito e outras comunicações em que é
necessário usar assinatura eletrônica. O mais
conhecido dos métodos de criptografia de
chave pública é o RSA.
Para implementar o RSA precisamos de dois
números primos grandes p e q, cujo produto é
igual a um número inteiro n, e de um inteiro
positivo e tal que mdc(e,(p − 1)(q − 1)) = 1 .
Chamaremos o par (n, e) de chave de
codificação do sistema RSA. Para codificar
uma
mensagem
no
RSA,
primeiro
convertemos as letras da mensagem em
números usando um alfabeto digital e em
seguida quebramos em blocos o número
produzido de tal forma que estes blocos sejam
números menores do que n. Se b é um desses
blocos a codificação do bloco b, denotada por
C(b) será dada por C(b) ≡ be (mod n) .
Codificando cada bloco separadamente, a
mensagem codificada será a seqüência de
blocos codificados.
Para decodificar a mensagem, precisaremos de
n e de um número inteiro d tal que
ed ≡ 1(mod(p − 1)(q − 1)) . Chamaremos o par
(n, d) de chave de decodificação. Se a é um
bloco
da
mensagem
codificada,
a
decodificação do bloco a, denotada por D(a) ,
será dado por D(a) ≡ ad (mod n ) .
Sabemos que para decodificar a mensagem
precisamos de (n, d) . Como n é conhecido,
basta encontrar d que é o inverso de
e(mod(p − 1)(q − 1)) .
Para
encontar
d
precisamos conhecer p e q. Logo, a segurança
do método depende da dificuldade de se
fatorar n.
Em relação à segurança do método RSA,
estudamos alguns algoritmos de fatoração e
alguns testes de primalidade bem conhecidos.
Vamos citar o algoritmo de Fermat e o Teste
de Lucas. Algoritmo de Fermat: Dado um
número inteiro ímpar z, a idéia desse
algoritmo é achar números inteiros x e y tais
que z = x 2 − y 2 . Etapa 1: Comece com
x =  z  ; se z = x 2 então x é fator de z e
podemos parar. Etapa 2: Caso contrário
incremente x de uma unidade e calcule
y = x 2 − z . Etapa 3: Repita a etapa 2 até
encontrar um valor inteiro para y, ou até que x
seja igual a (z + 1) / 2 . No primeiro caso z tem
fatores x + y e x − y . No segundo, z é primo.
Teste de Lucas: Dado um número n inteiro
positivo ímpar e b um inteiro tal que
2 ≤ b ≤ n −1.
Se
bn −1 ≡ 1(mod n)
e
b (n −1) / p ≡/ 1(mod n) , para cada fator primo p de
n − 1 , então n é primo. Nesses casos
estudados, o método se mostrou seguro.
Referências
[1] S. C. Coutinho, “Números Inteiros e
Criptografia RSA”, IMPA/SBM, Rio de
Janeiro, 1997.
[2] N. Koblitz, “A couse in number theory
and cryptography”, Springer-Verlag,
Berlim, 1988.