aula11_2010

Prévia do material em texto

A´lgebra A - Aula 11
RSA
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Criptografia RSA- pre´-codificac¸a˜o
I Converter a mensagem em uma sequ¨eˆncia de nu´meros
pre´-codificac¸a˜o.
I Letras A a Z (maiu´sculas) + espac¸os em branco entre
palavras (99).
I A = 10, B = 11, etc, Z = 35.
I Nu´meros com exatamente dois algarismos.
Pre´-codificac¸a˜o
Chave pu´blica: n = p.q, p e q primos. Devemos quebrar a
mensagem em blocos: nu´meros menores que n. Orientac¸o˜es:
I Na˜o comec¸ar com o nu´mero 0 (problemas na decodificac¸a˜o).
I Os blocos na˜o devem corresponder a nenhuma unidade
lingu´ıstica (palavra, letra, etc): decodificac¸a˜o por contagem
de frequ¨eˆncia fica imposs´ıvel.
Codificando
Para codificar: n = p.q e inteiro positivo e que seja invers´ıvel
mo´dulo φ(n). Em outras palavras,
mdc(e, φ(n)) = mdc(e, (p − 1).(q − 1)) = 1
Chamaremos o par (n, e) a chave de codificac¸a˜o do sistema
RSA.
Codificando cada bloco b:
C (b) ≡ be (mod n)
Onde 0 ≤ C (b) < n.
Importante: Na˜o reunir os blocos apo´s a codificac¸a˜o.
Exemplo
Paraty e´ linda:
2510271029349914992118231310
Tome n = 11.13 = 143. Quebrando a mensagem em blocos:
25− 102− 7− 102− 93− 49− 91− 49− 92− 118− 23− 13− 10
Como φ(143) = 10.12 = 120, tomamos e = 7. Logo,
C (25) ≡ 257 ≡ 2522 .252.25 (mod 143)
≡ 2522 .53.25 (mod 143)
≡ 532.53.25 (mod 143)
≡ 92.53.25 (mod 143)
≡ 14.25 (mod 143)
≡ 64 (mod 143)
Obtemos assim a seguinte mensagem cifrada:
64− 119− 6− 119− 102− 36− 130− 36− 27− 79− 23− 117− 10
Decodificando
(n, d) = chave de decodificac¸a˜o onde d e´ o inverso de e mo´dulo
φ(n). D(c) e´ dado por:
D(c) ≡ cd (mod n)
onde 0 ≤ D(c) < n.
Observe que e´ muito fa´cil calcular d , desde que φ(n) e e sejam
conhecidos: basta aplicar o algoritmo euclideano estendido.
Entretanto, se na˜o conhecemos p e q e´ praticamente imposs´ıvel
calcular d .
Exemplo
Voltando ao nosso exemplo, temos que n = 143 e e = 7. Para
calcular d , usamos o algoritmo euclideano estendido:
120 = 7.17 + 1 =⇒ 1 = 120 + (−17).7
Logo o inverso de 7 mo´dulo 120 e´ −17. Como d deve ser usado
como um expoente, precisamos que d seja positivo. Logo tomamos
d = 120− 17 = 103.
Funciona?
Pergunta o´bvia que surge:
D(C (b)) = b?
Ou seja, decodificando um bloco de mensagem codificada,
encontramos um bloco da mensagem original?
Consideremos enta˜o n = p.q. Vamos provar que
DC (b) ≡ b (mod n)
E por que na˜o a igualdade? Observe que DC (b) e b sa˜o menores
que n − 1. Por isso escolhemos b menor que n e mantivemos os
blocos separados depois da codificac¸a˜o!
Funciona!
Por definic¸a˜o:
DC (b) ≡ (be)d ≡ be.d (mod n)
Mas d e´ o inverso de e mo´dulo φ(n). Logo existe inteiro k tal que
ed = 1 + kφ(n). Logo,
bed ≡ b1+kφ(n) ≡ (bφ(n))k .b (mod n)
Se mdc(b, n) = 1, enta˜o podemos usar o teorema de Euler:
bed ≡ (bφ(n))k .b ≡ b (mod n)
Funciona!
Se b e n na˜o sa˜o primos entre si, observe que n = p.q, p e q
primos distintos. Logo,
bed ≡ b1+kφ(n) ≡ (b(p−1))k.(q−1).b (mod p)
Se mdc(b, p) = 1, enta˜o podemos usar o teorema de Fermat
(bp−1 ≡ 1 (mod p)). Se na˜o, temos que p|b e portanto
bed ≡ b ≡ 0 (mod p)
Funciona!
Logo,
bed ≡ b (mod p)
qualquer que seja b.
Fazemos o mesmo para o primo q, obtendo:
bed ≡ b (mod q)
Portanto,
bed ≡ b (mod p.q)
como quer´ıamos.
Porque o RSA e´ seguro
O RSA so´ e´ seguro se for dif´ıcil calcular d quando apenas o par
(n, e) e´ conhecido. Mas d somente se φ(n): fatorac¸a˜o de n.
Por que na˜o outro processo para calcular d e φ(n)? Resposta:
φ(n) = (p − 1).(q − 1) = pq − (p + q) + 1 = n − (p + q) + 1
Logo, (p + q) = n − φ(n) + 1 e
(p + q)2 − 4n = (p2 + q2 + 2pq)− 4pq = (p − q)2
Logo,
p − q =
√
(p + q)2 − 4n
Porque o RSA e´ seguro
Outro jeito de quebrar o RSA seria achar um algoritmo que calcule
d diretamente a partir de n e e. Como ed ≡ 1 (mod φ(n)), isto
implica que conhecemos um mu´ltiplo de φ(n). Isso tambe´m e´
suficiente para fatorar n (prova complicada).
A u´ltima alternativa seria achar b a partir da forma reduzida de be
mo´dulo n sem achar d . Bom, ningue´m conseguiu fazer isso ate´
agora... Acredita-se que quebrar o RSA e fatorar n sejam
problemas equivalentes, apesar disso na˜o ter sido demonstrado.
Escolhendo primos
RSA de chave pu´blica (n, e), n com aproximadamente r algarismos.
Escolha um primo p entre 4r10 e
45r
100 algarismos e q pro´ximo de
10r
p .
Tamanho da chave recomendado atualmente: 768 bits. n tera´ 231
algarismos. p e q: 104 e 127 algarismos respectivamente.
Importante: p − 1, q − 1, p + 1, p − 1 na˜o tenham fatores primos
pequenos, pois sena˜o seria fa´cil fatorar n.
Escolhendo primos
Para encontrar p e q, seguiremos a seguinte estrate´gia:
1. Tome um nu´mero s ı´mpar.
2. Verifique se s e´ divis´ıvel por um primo menor que 5.000.
3. Aplique o teste de Miller a s usando como base os 10
primeiros primos.
Se x e´ um nu´mero da ordem de 10127, no intervalo entre x e
x + 104 existem aproximadamente 34 primos dentre 560 nu´meros
que passam a etapa (1) da estrate´gia acima...
Assinaturas
I Apenas codificar mensagens na˜o basta: sistema e´ de chave
pu´blica.
I Um hacker poderia facilmente mandar instruc¸o˜es ao banco
para que o seu saldo banca´rio fosse transferido para uma
outra conta.
I Por isso, o banco precisa de uma garantia de que a mensagem
teve origem em um usua´rio autorizado.
I Ou seja, a mensagem tem que ser assinada .
Assinaturas
Cm e Dm: codificac¸a˜o e decodificac¸a˜o do Ma´rio e de Ca e Da as
func¸o˜es do Allan.b: de Ma´rio para Allan.
Mensagem assinada:
Ca(Dm(b))
Para ler a mensagem: Allan aplica Da e depois Cm.
Observe que Cm e´ pu´blico. Se a mensagem fizer sentido, e´ certo
que a origem foi mesmo o Ma´rio!
Mas cuidado ! Esse sistema pode ser usado para quebrar o RSA,
como em 1995 por um consultor em assuntos de seguranc¸a de
computadores...
Exerc´ıcios propostos - Cap´ıtulo 11
1,2,3,4,6