Teoria de n´umeros e criptografia rsa

Disponível somente no TrabalhosFeitos
  • Páginas : 57 (14150 palavras )
  • Download(s) : 0
  • Publicado : 4 de dezembro de 2012
Ler documento completo
Amostra do texto
Teoria de n´umeros e criptografia RSA
Elaine Gouvˆea Pimentel
1o Semestre - 2006
(´Ultima Modifica¸c˜ao: 4 de Maio de 2006)
1 Bibliografia e referˆencias
Livro texto: S.C. Coutinho N´umeros inteiros e criptografia RSA IMPA/SBM,
2000.
Outras referˆencias:
• Rosen, K. H., Elementary number theory and its applications, Addison-
Wesley,1984.
• Koblitz, N. A course in number theory andcriptography, Graduate Texts
in Mathematics 97, Springer-Verlag, 1987.
Ao longo do curso, ser˜ao indicadas leituras complementares.
Qualquer d´uvida ou coment´ario, escrever para:
elaine@mat.ufmg.br
2 Introdu¸c˜ao
O objetivo desse curso ´e estudar o m´etodo de criptografia de chaves p´ublicas
conhecido como RSA. Para entender como este m´etodo funciona, ´e necess´ario
o estudo de algunsconceitos de uma ´area da matem´atica chamada Teoria de
n´umeros. E, ´e claro, espera-se desenvolver, ao longo do curso, o racioc´ınio
l´ogico matem´atico dos alunos, introduzindo m´etodos de prova de teoremas como
indu¸c˜ao matem´atica e demonstra¸c˜ao por absurdo.
Deve ficar bem claro que este ´e um curso de matem´atica para cientistas da
computa¸c˜ao. Isto ´e, o rigor nunca ser´a deixado de ladomas a aten¸c˜ao estar´a
sempre voltada para a aplica¸c˜ao principal proposta: criptografia RSA.
1
2.1 Criptografia
• Criptografia: estuda os m´etodos para codificar uma mensagem de modo
que s´o seu destinat´ario leg´ıtimo consiga interpret´a-la.
• Prim´ordios: Cesar (transla¸c˜ao do alfabeto).
• Criptoan´alise: arte de decifrar c´odigos secretos.
• Decodificar x Decifrar (quebrar).
•Substituir letras por s´ımbolos - contagem de frequˆencia:
– vogais s˜ao mais frequentes;
– letra mais frequente: A;
– monoss´ılabo de uma letra = vogal;
– consoantes mais frequentes: S e M
M´etodo de contagem de frequˆencia de caracteres pode ser usado para
decifrar inscri¸c˜oes antigas.
• O surgimento dos computadores torna esse m´etodo de cifragem completamente
inseguro (decifragempolinomial).
• Internet e criptografia: seguran¸ca, assinatura.
• Chave p´ublica: saber codificar n˜ao implica saber decodificar!
2.2 Criptografia RSA
• RSA: Rivest, Shamir, Adleman (M.I.T.) 1978.
• Codifica¸c˜ao: basta conhecer o produto de dois primos (n = pq). n ´e
chamado chave p´ublica.
• Decodifica¸c˜ao: precisamos conhecer p e q (chave de decodifica¸c˜ao).
• Decifrar RSA = fatora¸c˜ao de n.Se n possui 150 algarismos ou mais,
fator´a-lo levaria milhares de anos.
• Obs: ´E dif´ıcil determinar os fatores primos de um n´umero composto, mas ´e
poss´ıvel verificar se um n´umero ´e primo ou composto sem tentar fator´a-lo.
• Teoria de n´umeros: parte da matem´atica que estuda n´umeros inteiros.
2
2.3 Computa¸c˜ao alg´ebrica
• Chave p´ublica do RSA: multiplica-se dois primos muitograndes.
• Pascal, C: n˜ao permitem lidar com n´umeros dessa magnitude.
• Computa¸c˜ao alg´ebrica: trata do c´alculo exato com inteiros, fra¸c˜oes, etc.
Exemplo: Mathematica, Maple.
• Inteiro de tamanho indeterminado: de tamanho flex´ıvel, grandes o suficiente.
Restri¸c˜oes: tamanho da mem´oria, estruturas de dados (vetores de
tamanhos pr´e-fixados).
• Inteiros = listas! Algarismos = elementoda lista; opera¸c˜oes de soma e
multiplica¸c˜ao: usuais, como com l´apis e papel. Divis˜ao ´e mais complicado...
3 Algoritmo da divis˜ao de Euclides
3.1 Algoritmos
• Algoritmo = processo de c´alculo baseado em regras formais.
• Especifica¸c˜ao de um algoritmo: entrada + instru¸c˜oes + sa´ıda.
• Perguntas:
– ao executarmos um conjunto de instru¸c˜oes, sempre chegaremos a um
resultado?(ponto fixo)
– o resultado obtido ´e sempre o desejado? (semˆantica)
3.2 Algoritmo da divis˜ao
• Objetivo: encontrar o quociente q e o resto r (sa´ıda) da divis˜ao entre dois
inteiros positivos a e b (entrada):
a = bq + r 0 ≤ r < b.
• Algoritmo da divis˜ao:
Etapa 1: q = 0; r = a
Etapa 2: Se r < b, pare. Nesse caso, o quociente ´e q e o resto r.
Etapa 3: Se r ≥ b, fa¸ca r := r − b, q := q +...
tracking img