Criptografia

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1601 palavras )
  • Download(s) : 0
  • Publicado : 2 de junho de 2012
Ler documento completo
Amostra do texto
TANNERY P EROTTO Orientador: Ronie Peterson Dario Universidade Federal de Mato Grosso

CRIPTOGRAFIA RSA

1 Introducao ¸˜
Este trabalho tem como objetivo apresentar o algoritmo RSA como uma aplicacao da ¸˜ Teoria Elementar dos N´ meros. Utilizaremos alguns resultados b´ sicos e logo em seguida dareu a mos o passo-a-passo de como codificar e decodificar uma mensagem de texto finalizando com ademonstracao e coment´ rios sobre o grau de seguranca. ¸˜ a ¸ A criptografia RSA e um tipo de criptografia de chave-p´ blica, ou seja, existem duas chaves: ´ u uma que codifica a mensagem e outra que decodifica. A chave que codifica e de conhecimento ´ p´ blico, possibilitando que qualquer usu´ rio da internet dissimule o conte´ do de sua mensagem e u a u garanta o sigilo da mesma. A chave que decodifica eprivada, ou seja, somente o administrador ´ do sistema que recepciona a mensagem e capaz de aplicar uma funcao na mensagem codificada e ´ ¸˜ posteriormente lˆ -la. e O RSA n˜ o garante a n˜ o interceptacao da mensagem, garante t˜ o somente que o usu´ rio a a ¸˜ a a leg´tmo ser´ capaz de decodificar. Essa garantia de sigilo e relativa. Na teoria e poss´vel descobrir a ı a ´ ´ ı chave privada, existepor´ m, um problema de ordem temporal e computacional no algoritmo RSA e que torna muito dif´cil um usu´ rio n˜ o leg´tmo decodificar usando os m´ todos atuais fatoracao. ı a a ı e ¸˜ Vejamos porquˆ : E que para implementar o algoritmo RSA necessitamos de um n´ mero n produto e ´ u de dois n´ meros primos muitos grandes (mais de 250 d´gitos) p e q. E o problema central na u ı ´ decodificacao seresume em fatorar n. E no problema da fatoracao que reside toda seguranca do ¸˜ ¸˜ ¸ RSA. Uma pessoa que tentasse fatorar um n de 309 d´gitos (1024 bits) com o melhor algoritimo de ı fatoracao existente (crivo dos corpos n´ mericos) levaria 23, 7 meses para descobrir p e q. ¸˜ u

3 Traduzindo Numeros em Palavras ´
3.1 Como Codificar uma Mensagem
O primeiro passo para implementar o RSA e a escolhade um par de n´ meros n e w tais que: ´ u (1) n e o produto de dois n´ meros primos p e q. ´ u (2) w e invers´vel m´ dulo φ(n). ´ ı o Podemos comecar a traduzir uma mensagem seguindo os passos enumerados: ¸ 1. Troca-se as letras da mensagem pelo n´ mero correspondente da tabela abaixo. O espaco u ¸ entre palavras e susbstitu´do pelo n´ mero 99. ´ ı u A B C D E F G H I J K L M 10 11 12 13 14 15 1617 18 19 20 21 22 O P Q R S T U W 24 25 26 27 28 29 30 31 V X Y Z 32 33 34 35 N 23

3.3 Demostracao e Seguranca do RSA ¸˜ ¸
Lembre-se que chamamos de Y o bloco j´ codificado na secao anterior, ou seja, Y = B w . Assim e a ¸˜ ´ de se esperar que [Yd ] = [Bw ]d = [B] que corresponde a uma das letras da tabela de convers˜ o. ` a Demonstracao. (Validade do RSA). Como ¸˜ wd ≡ 1(mod φ(n)), temos queexiste um inteiro α tal que ed = 1 + αφ(n) = 1 + α(p − 1)(q − 1). Assim, Bwd ≡ B · (Bp−1 )α(q−1) (modp). Pelo Pequemo Teorema de Fermat, Bp−1 ≡ 1 (modp). Fazendo substituicao na relacao anterior ¸˜ ¸˜ obtemos ed B ≡ B(mod p), ou seja, um bloco [B] codificado e decodificado retorna a alguma letra da tabela.

2. Separa-se a seq¨ encia num´ rica em blocos menores de maneira que cada bloco seja menoruˆ e que o n escolhido e de maneira que nenhum dos blocos comece por zero. ¸ 3. Para codificarmos um bloco [B] qualquer, fazemos [B] ≡ X(mod n).
w

4 Seguranca do RSA ¸
Embora todos tenham acesso ao par de codificacao (n, w), o que torna dif´cl a decodificacao ¸˜ ı ¸˜ a ´ a e o c´ lculo de d. Para este c´ lculo, e necess´ rio utilizar o algoritmo euclidiano estendido a φ(n) e ´ a w. Mas s´ sabemoscalcular φ(n) se soubermos fatorar n. o E se algu´ m calculasse φ(n) por um m´ todo desconhecido, que utilize somente o par (n, w)? Veja e e o que aconteceria: sabemos que φ(n) = (p − 1)(q − 1) = pq − (p + q) + 1 = n − (p + q) + 1. Note que p + q = n − φ(n) + 1 que e um valor conhecido. E al´ m disso, ´ e

´ 2 Resultados da Teoria Elementar dos Numeros
2.1 Os elementos invers´veis de ı
n...
tracking img