Relatório do IC

Relatório do IC

(Parte 1 de 3)

Numeros Inteiros e Criptografia RSA

Guilherme de Loreno1 , Daniela Maria Grande Vicente1

1Colegiado do Curso de Matematica - Centro de Ciencias Exatas e Tecnologicas da

Universidade Estadual do Oeste do Parana

Caixa Postal 711 - 85819-110 - Cascavel - PR - Brasil guilherme.loreno@unioeste.br daniela.grande@unioeste.br

Resumo. Nesse projeto de iniciacao cientıfica estudamos um dos metodos mais utilizados de criptografia de chave publica, o RSA, bem como a matematica requerida para a compreensao do mesmo. Descrevemos aqui, sucintamente, o funcionamento do metodo da Criptografia RSA, que nada mais e que um metodo para codificar mensagens, nas quais apenas o destinatario legıtimo conseguira decodificar. Neste artigo apresentamos uma breve explicacao de como funciona o metodo de codificacao, assim como o de decodificacao e uma discussao, em linhas gerais, do porque que tal metodo sempre funciona. O objetivo principal deste projeto de iniciacao cientıfica foi de estudar a matematica envolvida em um dos principais metodos de criptografia comercialmente utilizado.

Palavras Chaves. Criptografia RSA; Codificacao: Decodificacao; Congruencia; Numeros Primos;

1. Introducao

Atualmente, as pessoas cada vez mais vem usando a internet para realizar transacoes bancarias ou comerciais. Para que essas transacoes sejam seguras e preciso bons metodos de criptografia, pois e relativamente facil interceptar mensagens enviadas por linha telefonica, tornando-se necessario codificar essas mensagens de forma que so o seu destinatario possa decodifica-la. Um dos metodos de criptografia de chave publica mais utilizados comercialmente e o RSA, e foi inventado em 1978 por R. L. Rivest, A. Shamir e L. Andleman. O metodo consiste basicamente em dois processos, o primeiro de codificar a mensagem e posteriormente decodificar. Mais especificamente, o metodo RSA consiste na escolha de dois numeros primos grandes (de 150 algarismos ou mais). Para decodificar uma mensagem precisamos conhecer esses dois numeros primos, que chamaremos de p e q. A chave de codificacao do RSA e a multiplicacao deles n = p.q e esse numero e conhecido como a ?chave publica?, pois n pode ser tornado publico. Ja a chave de decodificacao e constituıda pelos numeros p e q que sao mantidos em seguedo pelo usuario. Entao, para decifrar o RSA basta fatorar o numero n e encontrar p e q. Porem isso se torna muito trabalhoso e ate mesmo praticamente impossıvel, pois no metodo RSA os numeros que devem ser fatorados sao muito grandes, com mais de 150 algarismos. Podemos dizer entao que e disso que a seguranca do RSA depende, da ineficiencia dos metodos de fatoracao atualmente conhecidos.

1.1. Teoria dos Numeros

Dentre os problemas que vamos analisar para descrever o metodo RSA esta relacionado a chamada Teoria dos Numeros, que e o ramo da matematica que estuda as propriedades dos numeros em geral, principalmente do conjunto dos inteiros. Para compreender o metodo, devemos saber calcular o resto da divisao de uma potencia por um numero dado, encontrar um numero que deixa restos especıficos quando divididos por outros numeros e tambem estabelecer criterios de divisibilidade por numeros primos, calcular o maximo divisor comum e o mınimo multiplo comum entre dois numeros dados.

O estudo das propriedades dos numeros inteiros se remete ja as antigas civilizacoes, contudo foi na Grecia Antiga que identificamos a teoria como a entendemos hoje em dia, muitos desses problemas sao discutidos no livro Elementos do matematico grego Euclides. Mas, foi durante o Renascimento europeu que muitas obras gregas foram publicadas na Europa e despertaram o interesse de muitos no continente, dentre eles o suıco Leonard Euler, o frances Pierre de Fermat e o alemao Carl Friedrich Gauss, no perıodo que vai do seculo XVII ao XIX. A maioria das ideias que estudaremos foram herdadas da Grecia Antiga, ou desses tres matematicos.

Nessa secao apresentamos algumas das propriedades basicas dos numeros inteiros que serao necessarias para melhor compreensao do RSA mais adiante.

1.1.1. Divisores e multiplos

Os resultados apresentados abaixo podem ser encontrados mais detalhadamente em [HEFEZ, 2015].

Divisores

Definicao 1. Dado um b ∈ Z, dizemos que b divide outro inteiro a, representado por b | a, se existe c ∈ Z tal que a = bc, ou tambem que b e um divisor de a ou fator de, ou ainda que a e multiplo de b. Na pratica, determinamos se b divide a, efetuando a divisao e verificando se o resto e zero.

Propriedades 1. Sejam a,b,c,d ∈ Z entao vale as seguintes propriedades:

Propriedades 2. Sejam a,m,x,y ∈ Z. Entao valem as seguintes propriedades:

i) 0 e multiplo de a; i) Se m e um multiplo de a, entao −m e multiplo de a; i) Um multiplo de um multiplo de a e um multiplo de a; iv) Se x e y sao multiplos de a entao, x + y e x − y sao multiplos de a.

1.1.2. Mınimo Multiplo Comum e Maximo Divisor Comum

Definicao 3. Seja a,b ∈ Z nao nulos, mesmo que nao sejam ambos positivos, entao define-se o mınimo multiplo comum de a e b , detonado por mmc(a,b) como sendo o menor multiplo comum positivo, ou seja, o menor elemento positivo do conjunto

Definicao 4. Dados a,b ∈ Z nao simultaneamente nulos, o maior divisor comum de a e b sera o maximo divisor comum de a e b, denotado por, mdc(a,b).

Temos que,

1.1.3. Numeros Primos e Compostos

Numeros primos desempenham um papel muito importante na teoria dos numeros e tambem no RSA. Portanto, vamos comecar o definindo.

O nome numero primo e uma heranca dos gregos, eles classificavam os numeros em primeiros ou indecomponıveis e secundarios ou compostos. Os compostos sao chamados assim por serem formados a partir dos primos. Os romanos apenas traduziram literalmente a palavra para primeiro, que em latim e primus. Contudo, determinar se um inteiro e primo ou composto pode ser uma tarefa muito difıcil, que pode ser ligeiramente auxiliada com os criterios de divisibilidade.

1.2. Alguns Criterios de Divisibilidade

Divisibilidade por 2

Um inteiro e divisıvel por 2 se, e somente se, seu algarismo das unidades for par.

Divisibilidade por 3

Um inteiro e divisıvel por 3 se, e somente se, a soma dos seus algarismos e divisıvel por 3.

Divisibilidade por 5

Um inteiro e divisıvel por 5 se, e somente se, seu algarismo das unidades e 0 ou 5.

Divisibilidade por 7 Um inteiro,

a = an·10n+an−1·10n−1+a1·10+a0 = (an·10n−1+an−1·10n−2 ...+a1)·10+a0

1.3. Fatorando inteiros

Nessa secao apresentamos um meio de como fatorar um inteiro, isto e, como encontrar todos os seus fatores primos. Os resultados a seguir, podem ser encontrados com mais detalhes em [COUTINHO, 2015].

1.3.1. Algoritmo achar fator

Dado um inteiro no qual deseja-se fatorar, primeiro tente dividir n por 2, se for divisıvel pare, pois descobrimos que 2 e fator de n, se nao for tente dividir por 3. Se for divisıvel pare, pois descobrimos que 3 e fator de n, se nao for tente dividir por 5. Continue dessa maneira ate encontrar um numero que divida n ou ate que o candidato a divisor seja

Podemos resumir isso tudo em uma unica proposicao.

Proposicao 1. O fator de um numero inteiro n > 1 encontrado pelo algoritmo achar fator acima e sempre um numero primo menor ou igual que a raiz quadrada de n.

Demonstracao. Suponha que o inteiro positivo n, que desejamos fatorar, e composto. Supondo que aplicando o algoritmo em n encontramos o menor fator p de n, ou seja,

Contudo c tambem e divisor de n. Levando em conta que p e o menor desses divisores, podemos escrever que c ≥ p (2)

Mostrando de fato o que querıamos provar.

Esse e um modelo mais simples de um modo de calcular um fator (ou divisor) de um numero. Todavia nosso objetivo e escrever n como o produto de fatores primos, a fim de encontrar os outros fatores devemos apenas aplicar o algoritmo achar fator sucessivas vezes. Entretanto, na pratica se o numero for grande, como veremos com detalhes adiante, pode-se demorar ate milhares de anos para que se consiga fatorar um numero, mesmo utilizando um poderoso computador, a fim de encontrar os fatores primos, alem disso, acabaria se tornando muito caro fazer tal processo. Assim, o algoritmo achar-fator pode ser facilmente entendido e de utilizar porem, e ineficiente mesmo utilizando um computador.

1.4. Teorema da Fatorocao Unica

Teorema 2 (Teorema Fundamental da Aritmetica). Dado um inteiro positivo n ≥ 2 podemos escreve-lo, de modo unico, na forma

e1pk

Alem disso, os numeros e1,...,ek sao chamados de multiplicidade e observemos que a quantidade total de fatores primos ( distintos ou nao ) e a soma das multiplicidades

e1 ++ ek.

Esse teorema e tao importante que geralmente e chamado de Teorema Fundamental da Aritmetica. Quem primeiro o enuciou foi Carl Friedrich Gauss em sua famosa obra Disquisitiones Arithmeticae de 1801, porem ja vinha sendo usado desde a Grecia Antiga.

O Teorema nos diz duas coisas, primeiro que todo inteiro pode ser escrito como o produto de fatores primos e que so da uma escolha possıvel de primos e expoentes para a fatoracao de um inteiro dado. Tendo esse enunciado, podemos explicar por que e necessario excluir ±1 da definicao de primo, pois, senao fizessemos isso, nao poderıamos falar de unicidade da fatoracao dita no teorema. Isto e, ±1 nao sao primos, todavia tambem nao sao compostos.

1.5. Propriedade Fundamental dos Primos

Teorema 3. Sejam a,b,c ∈ Z+ e suponhamos que a e b sao primos entre si. Entao, i) Se b | ac entao b | c i) Se a | c e b | c entao o produto ab | c.

Donde b | b · n · c e b | a · m · c,e temos por hipotese que b | ac, logo b | c. i) Temos que a | c, logo existe t inteiro, tal que

b | t, ou seja, t = b · k, para algum inteiro k, assim

1.6. Aritmetica Modular

Estudado a definicao de divisibilidade e suas propriedades, agora vamos introduzir um novo conceito que Gauss desenvolveu, que e a Aritmetica dos Restos, que nada mais e que o estudo dos restos de inteiros sucessivos na divisao por um inteiro n. E em vista disso, podemos dizer que os restos das divisoes desses inteiros sucessivos repetem-se com perıodo exatamente igual a n. As propriedades e resultados encontrados sao muito importantes para o entendimento do metodo RSA.As definicao e propriedades de Aritmetica Modular forem extraıdas da referencia [COUTINHO, 2013].

Uma maneira sistematica de se introduzir a aritmetica modular e atraves de relacoes de equivalencia. Seja X um conjunto e X 6= ∅. Dizemos que ha uma relacao em X quando comparamos dois elementos desse conjunto, denotemos essa relacao por v. Essa relacao sera de equivalencia, quando dados x,y,z ∈ X cumprem-se as seguintes propriedades:

i) Reflexiva: x v x i) Simetrica: se x v y ⇒ y v x i) Transitiva: se x v y e y v x ⇒ x v z

Se x ∈ X entao a classe de equivalencia de x e o conjunto dos elementos de X que sao equivalentes a x por v. Simbolicamente,

Com esses conceitos, podemos agora construir uma relacao de equivalencia no conjunto dos inteiros. Diremos que dois inteiros a e b sao congruentes modulo n se n | b − a e escrevemos, a ≡ b mod n.

Agora devemos de fato, mostrar que congruencia e uma relacao de equivalencia.

Para isso devemos mostrar as tres propriedades, a reflexividade, a simetria e a transitividade.

i) Seja a ∈ Z, temos que a ≡ a mod n pois n | a − a = 0. Portanto a congruencia ≡ e reflexiva. i) Seja a,b ∈ Z, tais que a ≡ b mod n, logo

b ≡ a mod n.

i) Sejam a, b,c ∈ Z, tais que a ≡ b modn b ≡ c modn logo temos que,

isso quer dizer que tanto b − a como c − b sao multiplos, e como a soma de multiplos de um inteiro n tambem e um multiplo de n, logo

Um outro modo de definir congruencia modular e seja n ∈ Z e n > 1. Diremos que dois inteiros a e b sao congruentes modulo n se, e somente se, a e b possuırem mesmo resto quando divididos por n. Simbolicamente, a ≡ b mod n.

A seguir, iremos demonstrar um resultado que foi usado anteriormente.

Subtraindo (4) de (3) temos,

Demonstracao. Temos que a ≡ b mod n e x ≡ y mod n, entao

Analogamente prova-se que, se a ≡ b mod n e x ≡ y mod n, entao a−x ≡ b−y modn.

Multiplicando (9) por (10), obtemos

de modo que a diferenca a · x − b · y e um multiplo de n, que e equivalente a dizer que a · x ≡ b · y mod n.

Em particular,

1.7. Criterios de Divisibilidade

Na secao 1.2 apresentamos alguns criterios de divisibilidade, porem sem fazermos a demonstracao. Agora ja com o conceito e varias propriedades de congruencia modular estabelecidos, podemos demonstrar alguns desses criterios usando congruencia modular.

Criterio de divisibilidade por 3

Seja a ∈ Z. Queremos verificar se a e divisıvel por 3. Para isso precisamos conhecer os algarismos de a. Digamos que, onde a0 e o algarismo das unidades, a1 o algarismo das dezenas, e assim sucessivamente. Logo,

a = an10n + an−110n−1 ++ a1101 + a0.

Observemos que,

a ≡ an + an−1 ++ a1 + a0 mod n. (1)

Se o segundo membro de (1) e divisıvel por 3, entao

Donde, podemos concluir que a ≡ 0 mod3

Isto e, a e divisıvel por 3. Portanto, um numero e divisıvel por 3 se, e somente se, a soma dos seus algarismos tambem for.

Criterio de divisibilidade por 1

Suponha que os algarismos de a sejam anan−1...a1a0, assim

a ≡ an(−1)n + an−1(−1)n−1 ++ (−a1) + a0 mod 1 (12)

logo, de (12) obtivemos a soma alternada dos algarimos. Portanto concluımos que um inteiro e divisıvel por 1 se, e somente se, a soma alternada de seus algarismos e divisıvel por 1.

Os criterios de divisibilidade por 2 e 5 sao mais faceis e nao precisamos de congruencia para entender por que sao verdade.

Uma outra aplicacao das congruencias e no calculo do resto de potencias por um numero qualquer, no qual esse metodo e muito importante na implementacao do RSA, pois reduz o problema de calcular o resto da divisao de um numero muito grande, para mais simples, com numeros menores e mais faceis de serem trabalhados. Iremos analisar esse metodo atraves de dois exemplos.

Queremos calcular o resto da divisao de 10135 por 7. Observemos que 106 ≡ 1 (mod 7). Temos entao as seguintes congruencias modulo 7

Logo o resto da divisao de 10135 por 7 e 6.

Agora queremos encontrar o resto da divisao de 2124 512 por 31. A verdade e que o maior problema e encontrar o quociente dessa divisao, pelo motivo do dividendo ser um numero muito grande. Ja que, para o resto podemos utilizar congruencias. Calculemos as potencias de 2 modulo 31,

Dividindo 124 512 por 5 obtemos,

1.8.1. Ordem de um Inteiro Modular

Os calculos com potencias feitos acima so foram feitos com mais facilidade por que foi possıvel encontrar um expoente inteiro positivo no qual uma potencia da base dava 1 quando tomada em modulo.

Definicao 7. Seja 1 ≤ b ≤ n − 1 inteiros, dizemos que a ordem de b modulo n e o menor inteiro positivo k para o qual bk ≡ 1 mod n.

Contudo, sera que sempre existe um inteiro positivo k tal que bk ≡ 1 mod n ?

A resposta e sim, mas desde que dado 1 ≤ b ≤ n − 1, esse possuira ordem modulo n apenas se b e n sao primos entre si.

Agora discutiremos um pouco um tema que vai ter grande importancia quanto ao funcionamento do RSA, que e o conceito de inversos modulares.

Tambem dizemos que a′ e o inverso de a modulo n, e vice-versa. Contudo nem todos os inteiros admitem inverso modulo n. Temos um teorema que nos garante que se dado um inteiro a quando que ele possuıra inverso modulo n.

(Parte 1 de 3)

Comentários