Criptografia

Teoria de n´ meros e criptografia RSA u
Elaine Gouvˆa Pimentel e 1o Semestre - 2006 ´ (Ultima Modifica¸˜o: 4 de Maio de 2006) ca

1

Bibliografia e referˆncias e

Livro texto: S.C. Coutinho N´meros inteiros e criptografia RSA IMPA/SBM, u 2000. Outras referˆncias: e • Rosen, K. H., Elementary number theory and its applications, AddisonWesley,1984. • Koblitz, N. A course in number theory and criptography, Graduate Texts in Mathematics 97, Springer-Verlag, 1987. Ao longo do curso, ser˜o indicadas leituras complementares. a Qualquer d´vida ou coment´rio, escrever para: u a [e-mail]

2

Introdu¸˜o ca

O objetivo desse curso ´ estudar o m´todo de criptografia de chaves p´blicas e e u conhecido como RSA. Para entender como este m´todo funciona, ´ necess´rio e e a o estudo de alguns conceitos de uma ´rea da matem´tica chamada Teoria de a a n´meros. E, ´ claro, espera-se desenvolver, ao longo do curso, o racioc´ u e ınio l´gico matem´tico dos alunos, introduzindo m´todos de prova de teoremas como o a e indu¸ao matem´tica e demonstra¸ao por absurdo. c˜ a c˜ Deve ficar bem claro que este ´ um curso de matem´tica para cientistas da e a computa¸ao. Isto ´, o rigor nunca ser´ deixado de lado mas a aten¸ao estar´ c˜ e a c˜ a sempre voltada para a aplica¸ao principal proposta: criptografia RSA. c˜

1

2.1

Criptografia

• Criptografia: estuda os m´todos para codificar uma mensagem de modo e que s´ seu destinat´rio leg´ o a ıtimo consiga interpret´-la. a • Prim´rdios: Cesar (transla¸ao do alfabeto). o c˜ • Criptoan´lise: arte de decifrar c´digos secretos. a o • Decodificar x Decifrar (quebrar). • Substituir letras por s´ ımbolos - contagem de frequˆncia: e – vogais s˜o mais frequentes; a – letra mais frequente: A; – monoss´ ılabo de uma letra = vogal; – consoantes mais frequentes: S e M M´todo de contagem de frequˆncia de caracteres pode ser usado para e e decifrar inscri¸oes antigas. c˜ • O surgimento dos computadores torna esse m´todo de cifragem completae