Teoria de n´umeros e criptografia rsa

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 and criptography, 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: [e-mail] 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 alguns conceitos 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 lado mas 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 (decifragem