Criptografia

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 a demonstracao 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 e privada, 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, existe por´ 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 se resume 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 escolha