Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Números Primos e Criptografia RSA
Jean Carlo Baena Vicente
Matemática - UFPR
Orientador:
Carlos Henrique dos Santos
6 de outubro de 2013
Referências
Criptografia RSA
Por que o RSA funciona?
Fatoração
Sumário
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Primalidade
Referências
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Motivação
O método de criptografia RSA foi desenvolvido por Ron Rivest,
Adi Shamir e Leonard Adleman, é fundamentado pela área da
matemática denominada Teoria de Números, hoje é o algoritmo de
chave pública mais utilizado ao redor do mundo.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Pré-codificação
Neste primeiro momento é necessário transcrever a mensagem a
ser criptografada, por meio de uma conversão de letras em
números, por exemplo:
A=10
B=11
C=12
D=13
E=14
F=15
G=16
H=17 . . .
I =18
J =19
Alguns cuidados devem ser tomados!
Referências
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Pré-codificação
Em seguida, deve-se conhecer o número n = pq, onde p e q são
números primos distintos, n é chamado de chave pública, e agora a
mensagem transcrita deve ser quebrada em blocos, e cada um
destes deve ser menor que n, por exemplo:
Se a mensagem, já transcrita, for:
2510271029349914992118231310
Uma das formas de se formar blocos é:
25 − 102 − 7 − 102 − 93 − 49 − 91 − 49 − 92 − 118 − 23 − 13 − 10
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Codificando
Para codificar a mensagem serão necessários os números n e um
número e inversı́vel módulo φ(n), ou seja, mdc(e, φ(n)) = 1.
Como p e q são primos, φ(n) é facilmente calculado.
φ(n) = (p − 1)(q − 1)
Cada um dos blocos da mensagem será codificado da seguinte
forma:
C (b) = b e (mod n)
Onde b é o bloco a ser codificado.
Referências
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Codificando
Usando o exemplo anterior, onde os blocos da mensagem eram:
25 − 102 − 7 − 102 − 93 − 49 − 91 − 49 − 92 − 118 − 23 − 13 − 10
Tomando os primos p = 11 e q = 13, obtemos que n = pq = 143.
Tomando agora e = 7, pode-se fazer a codificação da mensagem
acima:
64 − 119 − 6 − 119 − 102 − 36 − 130 − 36 − 27 − 79 − 23 − 117 − 10
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Decodificando
Observando o processo de codificação dos blocos da mensagem, é
natural imaginar o que deverá ser feito para decodifica-los.
Basta tomar d o inverso de e módulo φ(n), então faz-se:
D(C (b)) = C (b)d (mod n)
A existência de d é garantida pelo teorema de Bézout, no exemplo,
como e = 7, temos d = 103, realizando os cálculos acima na
mensagem codificada:
25 − 102 − 7 − 102 − 93 − 49 − 91 − 49 − 92 − 118 − 23 − 13 − 10
Obtemos:
64 − 119 − 6 − 119 − 102 − 36 − 130 − 36 − 27 − 79 − 23 − 117 − 10
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Por que funciona?
Para garantir que, independente dos valores de p, q, e e d
utilizados, a mensagem decodificada será fiel à original deve-se
mostrar que D(C (b)) = b, ou seja:
b de ≡ b(mod n)
Isto não é tão óbvio pois não é certo que mdc(b, n) = 1, logo não
pode-se aplicar diretamente o teorema de Euler, mas é fácil ver
que, como de = 1 + kφ(n) = 1 + k(p − 1)(q − 1), temos:
b de ≡ b(mod p)
Caso mdc(p, b) = 1, e também quando p | b. As mesmas relações
valem para q.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Por que funciona?
Basta agora usar o seguinte lema:
Lema
Sejam a e b, dois inteiros coprimos, se a | c e b | c, então o
produto ab | c.
Como vimos, p | b de − b e q | b de − b, como p e q são primos
concluı́mos, pelo lema acima, que
b de ≡ b(mod pq)
Referências
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Segurança
A segurança depende do quão difı́cil será decompor n, então os
primos p e q devem ser tomados com cautela, afim de que não
sejam facilmente descobertos.
Dependendo da escolha dos primos pode-se garantir que o sistema
será seguro durante anos, mas o que deve ser levado em
consideração para decidir quais primos serão utilizados?
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Fatoração usual
Algoritmo (Usual de Fatoração)
Etapa1: Comece fazendo F = 2
Etapa2: Se n/F é inteiro então F é fator de n; caso contrário vá
para a etapa 3.
Etapa3: Incremente F de uma unidade e vá para a etapa 4.
√
Etapa4: Se F n então n é primo; caso contrário volte à etapa 2.
O algoritmo usual de fatoração é menos eficiente quanto maiores
forem os fatores do número a ser decomposto.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Fatoração por Fermat
Algoritmo (Fermat)
√
Etapa1: Comece com x = n, se n = x 2 então x é fator de n;
caso contrário vá para a etapa 2.
√
Etapa2: Incremente x de uma unidade e calcule y = x 2 − n.
Etapa3: Repita a etapa 2 até encontrar um valor inteiro para y , ou
até que x seja igual a (n + 1)/2; no primeiro caso n tem fatores
x + y e x − y , no segundo n é primo.
O algoritmo de Fermat encontrará facilmente fatores que são
relativamente próximos um ao outro.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Primos Populares
Então deve-se impor certas condições aos primos utilizados no
RSA, afim de que a codificação atinja um certo nı́vel de segurança,
para encontrar estes números, se faz necessário o uso de algumas
ferramentas.
Computacionalmente falando, o método mais facil de se encontrar
estes números é fazer uso de funções que possam gerar primos,
algumas destas funções são bastante conhecidas.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Números de Mersenne
Os números de Mersenne são os números da seguinte forma:
Mn = 2n − 1
É sabido que se o número Mn é primo, então n também será um
número primo. Infelizmente a reciproca desta afirmação não é
válida.
Referências
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Números de Fermat
Os números de Fermat seguem a seguinte regra:
Fn = 2n + 1
Pode-se mostrar que, quando Fn é primo, n será uma potência de
dois. A recı́proca também falha nesta afirmação.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Famı́lias de Primos
Obviamente os números de Mersenne e Femat não serão úteis para
os fins do RSA, mas existe uma infinidade de famı́lias de primos
que podem ser utilizadas.
Teorema (Dirichlet)
Sejam a, b ∈ N, tais que mdc(a, b) = 1 então a progressão
aritmética:
an = a + nb
Contém infinitos números primos.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Pseudoprimos
Pelo teorema de Fermat podemos compreender o que são números
pseudoprimos.
Teorema
Se n > 0 e 1 < b < n são números inteiros e b n−1 6≡ 1(mod n),
então n é um número composto.
O número b é uma de testemunha de que n é composto.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Teste de Lucas
Teorema
Seja n > 0 um inteiro tal que
n − 1 = p1e1 . . . prer
onde p1 < · · · < pr são primos. Se, para cada i = 1, . . . , r
existirem inteiros positivos bi (2 ≤ bi ≤ n − 1) que satisfaçam
bin−1 ≡ 1(mod n)
(n−1/pi )
bi
6≡ 1(mod n),
então n é primo.
Este algoritmo é bastante eficiente para determinar primalidade de
números como os de Fermat.
Criptografia RSA
Por que o RSA funciona?
Fatoração
Primalidade
Referências
Referências
S. C. Coutinho: Números Inteiros e Criptografia RSA. Instituto
Nacional de Matemática Pura e Aplicada - IMPA. 2009.
S. C. Coutinho: Criptografia. Programa de Iniciação Cientı́fica
OBMEP. 2009.
RSA Algorithm. xtrmntr.org/priikone/docs/rsa.pdf. Acessado
em 06/05/2013.