Criptografia

Disponível somente no TrabalhosFeitos
  • Páginas : 60 (14784 palavras )
  • Download(s) : 0
  • Publicado : 24 de outubro de 2012
Ler documento completo
Amostra do texto
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 andcriptography, 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 elaine@mat.ufmg.br

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 dealguns 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 completaemente inseguro (decifragem polinomial). • Internet e criptografia: seguran¸a, assinatura. c • Chave p´blica: saber codificar n˜o implica saber decodificar! u a

2.2

Criptografia RSA

• RSA: Rivest, Shamir, Adleman (M.I.T.) 1978. • Codifica¸ao: basta conhecer o produto de dois primos (n = pq). n ´ c˜ e chamado chave p´blica. u • Decodifica¸ao: precisamos conhecer p e q (chave de decodifica¸ao). c˜ c˜ •Decifrar RSA = fatora¸ao de n. Se n possui 150 algarismos ou mais, c˜ fator´-lo levaria milhares de anos. a ´ ıcil • Obs: E dif´ determinar os fatores primos de um n´mero composto, mas ´ u e poss´ verificar se um n´mero ´ primo ou composto sem tentar fator´-lo. ıvel u e a • Teoria de n´meros: parte da matem´tica que estuda n´meros inteiros. u a u

2

2.3

Computa¸˜o alg´brica ca e

•Chave p´blica do RSA: multiplica-se dois primos muito grandes. u • Pascal, C: n˜o permitem lidar com n´meros dessa magnitude. a u • Computa¸ao alg´brica: trata do c´lculo exato com inteiros, fra¸oes, etc. c˜ e a c˜ Exemplo: Mathematica, Maple. • Inteiro de tamanho indeterminado: de tamanho flex´ ıvel, grandes o suficiente. Restri¸oes: tamanho da mem´ria, estruturas de dados (vetores de c˜ o tamanhospr´-fixados). e • Inteiros = listas! Algarismos = elemento da lista; opera¸oes de soma e c˜ multiplica¸ao: usuais, como com l´pis e papel. Divis˜o ´ mais complic˜ a a e cado...

3
3.1

Algoritmo da divis˜o de Euclides a
Algoritmos

• Algoritmo = processo de c´lculo baseado em regras formais. a • Especifica¸ao de um algoritmo: entrada + instru¸oes + sa´ c˜ c˜ ıda. • Perguntas: – ao executarmos umconjunto de instru¸oes, sempre chegaremos a um c˜ resultado? (ponto fixo) – o resultado obtido ´ sempre o desejado? (semˆntica) e a

3.2

Algoritmo da divis˜o a

• Objetivo: encontrar o quociente q e o resto r (sa´ ıda) da divis˜o entre dois a inteiros positivos a e b (entrada): a = bq + r • Algoritmo da divis˜o: a Etapa 1: q = 0; r = a Etapa 2: Se r < b, pare. Nesse caso, o quociente ´...
tracking img