Criptografia e Criptografia e Segurança de RedesSegurança de Redes

Capítulo 8Capítulo 8

Quarta EdiçãoQuarta Edição

por William Stallingspor William Stallings

Tradução: Cesar e Luis AugustoTradução: Cesar e Luis Augusto

Capítulo 8 – Capítulo 8 – Introdução à Teoria Introdução à Teoria dos Númerosdos Números

O diabo disse a Daniel Webster: “De-me uma tarefa que eu não possa realizar, e eu vou lhe dar qualquer coisa no mundo que você pedir." Daniel Webster: "É justo. Prove que para n maior que 2, a equação a^n + b^n = c^n não possui solução trivial no conjunto dos inteiros." Eles concordaram com um período de três dias para o trabalho, e o diabo desapareceu. Ao final de três dias, o diabo apresentou-se, fatigado, mordendo o lábio. Daniel Webster lhe disse: "Bem, como você se saiu na minha tarefa? Conseguiu provar o teorema? "Eh? Não... Não,eu não consegui provar." "Então eu posso ter o que eu quiser? Dinheiro? A Presidência? "O quê? Ah, é claro. Mas escute! Se pudéssemos simplesmente provar os dois lemas a seguir...“

The mathematical Magpie, Clifton Fadiman

Números PrimosNúmeros Primos

Números primos são divisíveis por 1 e ele mesmoNúmeros primos são divisíveis por 1 e ele mesmoEles não podem ser escritos como produto de outros Eles não podem ser escritos como produto de outros

númerosnúmerosObserve: 1 é primo, mas geralmente não é de interesseObserve: 1 é primo, mas geralmente não é de interesse

Ex.: 2,3,5,7 são primos, 4,6,8,9,10 não sãoEx.: 2,3,5,7 são primos, 4,6,8,9,10 não são Números primos são o centro da teoria dos númerosNúmeros primos são o centro da teoria dos números A lista das primos menores que 200 é:A lista das primos menores que 200 é:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149

151 157 163 167 173 179 181 191 193 197 199151 157 163 167 173 179 181 191 193 197 199

Fatoração em PrimoFatoração em Primo

Fatorar um número Fatorar um número nn é escrevê-lo como é escrevê-lo como produto de outros números: produto de outros números: n=a x b x cn=a x b x c

Observe que fatorar é relativamente difícil Observe que fatorar é relativamente difícil comparado com multiplicar os fatores juntos comparado com multiplicar os fatores juntos para gerar o númeropara gerar o número

A fatoração de um primo A fatoração de um primo nn é quando ele é um é quando ele é um produto de primosproduto de primosEx.: Ex.: 91=7x13 ; 3600=291=7x13 ; 3600=244x3x322x5x522

Relatividade de Números Primos Relatividade de Números Primos & MDC& MDC

Dois números Dois números a, ba, b são relativamente primos se não são relativamente primos se não tem nenhum divisor comum a não ser o 1 tem nenhum divisor comum a não ser o 1 Ex.: 8 & 15 são relativamente primos desde que os fatores Ex.: 8 & 15 são relativamente primos desde que os fatores

de 8 sejam 1,2,4,8 e do 15 sejam 1,3,5,15 e 1 é o único fator de 8 sejam 1,2,4,8 e do 15 sejam 1,3,5,15 e 1 é o único fator comum comum

Inversa pode determinar o máximo divisor comum Inversa pode determinar o máximo divisor comum comparando suas fatorações de primos e usando a comparando suas fatorações de primos e usando a menor potênciamenor potênciaEx.: Ex.: 300=2300=211x3x311x5x522 18=2 18=211x3x322 por issopor isso MDC(18,300)=2MDC(18,300)=211x3x311x5x500=6=6

Teorema de FermatTeorema de Fermat

aap-1p-1 = 1 (mod p) = 1 (mod p)onde onde pp é primo e é primo e mdc(a,p)=1mdc(a,p)=1

Também conhecido como Pequeno Também conhecido como Pequeno Teorema de FermatTeorema de Fermat

também também aapp = a (mod p) = a (mod p)Aplicável em chaves públicas e testes de Aplicável em chaves públicas e testes de

primalidadeprimalidade

Função Totiente de Euler Função Totiente de Euler ø(n)ø(n)

Quando usamos aritmética módulo nQuando usamos aritmética módulo n Conjunto completo de resíduos é: Conjunto completo de resíduos é: 0..n-10..n-1 Conjunto reduzido de resíduos são aqueles Conjunto reduzido de resíduos são aqueles

números (resíduos) que são relativamente primos números (resíduos) que são relativamente primos de nde nEx.: para n=10, Ex.: para n=10, Conjunto completo de resíduos é: {0,1,2,3,4,5,6,7,8,9} Conjunto completo de resíduos é: {0,1,2,3,4,5,6,7,8,9} Conjunto reduzido é: {1,3,7,9} Conjunto reduzido é: {1,3,7,9}

O número de elementos no conjunto reduzido de O número de elementos no conjunto reduzido de resíduos é chamado resíduos é chamado Função Totiente de Euler ø(n)Função Totiente de Euler ø(n)

Função Totiente de Euler Função Totiente de Euler ø(n)ø(n)

Para computar ø(n) é preciso contar o número Para computar ø(n) é preciso contar o número de resíduos à ser excluídode resíduos à ser excluído

Geralmente faz-se a fatoração do primo, masGeralmente faz-se a fatoração do primo, masPara p (p primo) Para p (p primo) ø(p) = p-1ø(p) = p-1 para p.q (p,q primo) para p.q (p,q primo) ø(pq) =(p-1)x(q-1)ø(pq) =(p-1)x(q-1)

Ex.:Ex.:ø(37) = 36ø(37) = 36ø(21) = (3–1)x(7–1) = 2x6 = 12ø(21) = (3–1)x(7–1) = 2x6 = 12

Teorema de EulerTeorema de Euler

Uma generalização do Teorema de FermatUma generalização do Teorema de Fermat aaø(n)ø(n) = 1 (mod n) = 1 (mod n)

para cada para cada a,na,n onde onde mdc(a,n)=1mdc(a,n)=1 Ex.:Ex.:aa=3;=3;nn=10; ø(10)=4; =10; ø(10)=4; por isso 3por isso 34 4 = 81 = 1 mod 10= 81 = 1 mod 10

aa=2;=2;nn=11; ø(11)=10;=11; ø(11)=10;por isso 2por isso 210 10 = 1024 = 1 mod 11= 1024 = 1 mod 11

Teste de primalidadeTeste de primalidade

Freqüentemente precisa-se encontrar o maior número Freqüentemente precisa-se encontrar o maior número primoprimo

Tradicionalmente Tradicionalmente selecionaseleciona utilizando divisão básica utilizando divisão básicaEx.: divide por todos números (primos) menores do que a Ex.: divide por todos números (primos) menores do que a

raiz quadrada do número raiz quadrada do número Só funciona para números pequenosSó funciona para números pequenos

Uma alternativa é usar o teste de primalidade Uma alternativa é usar o teste de primalidade estatística baseado na propriedade dos primosestatística baseado na propriedade dos primosPara que todos os números primos satisfaçam a Para que todos os números primos satisfaçam a

propriedadepropriedadeMas alguns números compostos, chamados pseudo-primos, Mas alguns números compostos, chamados pseudo-primos,

também satisfazem a propriedadetambém satisfazem a propriedadePode usar um teste de primalidade determinística mais Pode usar um teste de primalidade determinística mais

devagardevagar

Algoritmo de Miller RabinAlgoritmo de Miller Rabin

Um teste baseado no teorema de FermatUm teste baseado no teorema de Fermat O algoritmo é:O algoritmo é:TEST (TEST (nn) é:) é:1. Encontre inteiros 1. Encontre inteiros kk, , qq, com , com k k > 0, > 0, q q impar, de modo que impar, de modo que (n (n – 1 = 2– 1 = 2kkq);q);2. Selecione um inteiro aleatório 2. Selecione um inteiro aleatório aa, 1 < , 1 < a a < < n n – 1;– 1;3.Se 3.Se aaqq mod mod n n = 1= 1 então então return (“talvez primo”);return (“talvez primo”);4. 4. Para Para j j = 0 = 0 até até k k – 1 – 1 façafaça

5. 5. sese ( (aa22jjqq mod mod n n = = n n - 1- 1))

então então return(" talvez primo ");return(" talvez primo ");6. return (“composto");6. return (“composto");

Considerações ProbabilísticasConsiderações Probabilísticas

Se Miller-Rabin retornar “composto” o número é Se Miller-Rabin retornar “composto” o número é definitivamente não-primodefinitivamente não-primo

De outro modo, é primo ou pseudo-primoDe outro modo, é primo ou pseudo-primoAs chances de detectar um pseudo-primo é de As chances de detectar um pseudo-primo é de

menos de menos de ¼¼

Por isso se repetir o teste com diferentes Por isso se repetir o teste com diferentes aleatoriedades a chance de n primos depois de aleatoriedades a chance de n primos depois de t testes são:t testes são:Pr(n primos depois de t testes) = 1-4Pr(n primos depois de t testes) = 1-4 -t-t

Ex.: para t=10 esta probabilidade é > 0.99999Ex.: para t=10 esta probabilidade é > 0.99999

Distribuição dos PrimosDistribuição dos Primos

Teoria dos números primos afirma que primos Teoria dos números primos afirma que primos ocorrem aproximadamente a toda (ocorrem aproximadamente a toda (ln nln n))

Mas pode ignorar os eventos imediatamenteMas pode ignorar os eventos imediatamenteEntão, na prática precisa testar somente Então, na prática precisa testar somente 0.5 0.5 ln(n)ln(n) números de tamanho números de tamanho nn para encontrar para encontrar um primoum primoObserve, isto é somente a “média”Observe, isto é somente a “média”Algumas vezes os primos estão próximosAlgumas vezes os primos estão próximosOutras estão muito distantesOutras estão muito distantes

Teorema Resto ChinêsTeorema Resto Chinês

Usado par acelerar a computação de móduloUsado par acelerar a computação de móduloSe rodando o módulo de um produto de Se rodando o módulo de um produto de

númerosnúmerosEx.:. Ex.:. mod M = mmod M = m11mm22..m..mkk

Teorema Resto Chinês nos deixa trabalhar em Teorema Resto Chinês nos deixa trabalhar em cada módulo mcada módulo mi i separadamente separadamente

Desde o custo computacional é proporcional ao Desde o custo computacional é proporcional ao tamanho, ele é mais rápido do que trabalhar no tamanho, ele é mais rápido do que trabalhar no tamanho total Mtamanho total M

Teorema Resto ChinêsTeorema Resto Chinês

Pode-se implementar o CRT de várias formasPode-se implementar o CRT de várias formas Para calcular Para calcular A(mod M)A(mod M)

Primeiro calcule todos Primeiro calcule todos aaii = A mod m = A mod mii separadamente separadamenteDetermine constantes Determine constantes ccii abaixo, onde abaixo, onde MMii = M/m = M/mii

Então combine os resultados para obter a resposta usando:Então combine os resultados para obter a resposta usando:

Raiz PrimitivaRaiz Primitiva

Do Teorema de Euler temos Do Teorema de Euler temos aaø(n)ø(n)mod n=1 mod n=1 considere considere aamm=1 (mod n), MDC(a,n)=1=1 (mod n), MDC(a,n)=1

Deve existir para Deve existir para m = ø(n)m = ø(n) mas deve ser menor mas deve ser menorQuando potência atingir m, repete o cicloQuando potência atingir m, repete o ciclo

Se o menor for Se o menor for m = ø(n)m = ø(n) então então aa é chamado um é chamado um raiz primitivaraiz primitiva

Se Se pp é primo, potências sucessivas de é primo, potências sucessivas de aa “geram" o “geram" o grupo grupo mod pmod p

São úteis, mas difícil de se encontrarSão úteis, mas difícil de se encontrar

Logaritimos DiscretosLogaritimos Discretos

O problema inverso à exponenciação é encontar o O problema inverso à exponenciação é encontar o logaritmo discretologaritmo discreto de um número módulo p de um número módulo p

Isto é encontrar Isto é encontrar xx desde que desde que y = gy = gxx (mod p) (mod p) É escrito como É escrito como x = logx = loggg y (mod p) y (mod p) Se g for um raiz primitiva então isto sempre existe, Se g for um raiz primitiva então isto sempre existe,

senão pode não existirsenão pode não existir Ex.:Ex.:x = logx = log33 4 mod 13 não tem resposta 4 mod 13 não tem resposta

x = logx = log22 3 mod 13 = 4 mas tentando sucessivas potências 3 mod 13 = 4 mas tentando sucessivas potências Enquanto exponenciação é relativamente fácil, Enquanto exponenciação é relativamente fácil,

encontrar logaritmo discreto é um grande problemaencontrar logaritmo discreto é um grande problema

SumárioSumário

Considerações:Considerações:Números primosNúmeros primosTeorema de Fermat e Euler & ø(n) Teorema de Fermat e Euler & ø(n) Teste de primalidadeTeste de primalidadeTeorema do Resto ChinêsTeorema do Resto ChinêsLogaritmos DiscretosLogaritmos Discretos

É um teste rápido, mas siga as etapas com atenção. É um teste rápido, mas siga as etapas com atenção. Não pule etapas. Não pule etapas. Responda as perguntas e leia atentamente até o final. Responda as perguntas e leia atentamente até o final. 1 - Olhe no relógio e marque as horas!!! 1 - Olhe no relógio e marque as horas!!! 2 - Pense em um número inteiro de 1 a 9 2 - Pense em um número inteiro de 1 a 9 3 - Multipique seu valor por 9 3 - Multipique seu valor por 9 4 - some os dois algarismos deste produto! (Ex.: 21, 2+1 3) 4 - some os dois algarismos deste produto! (Ex.: 21, 2+1 3) 5 - Nao pule as etapas!!!! 5 - Nao pule as etapas!!!! 6 - some 7 ao resultado 6 - some 7 ao resultado 7 - divida o resultado por 4 7 - divida o resultado por 4 8 - Faca a conversao do número por uma letra do alfabeto (Ex.: 1 a 2 8 - Faca a conversao do número por uma letra do alfabeto (Ex.: 1 a 2

b 3 c b 3 c 9 - Pense em um pais com a letra correspondente 9 - Pense em um pais com a letra correspondente 10 - Nao pule as etapas!!!! 10 - Nao pule as etapas!!!! 11 - Ache a 5ª Letra deste pais 11 - Ache a 5ª Letra deste pais 12 - Pense em um animal com esta letra. 12 - Pense em um animal com esta letra. 13 - Depois de Tudo isso, veja as horas.13 - Depois de Tudo isso, veja as horas.

14 - Veja quanto tempo da sua vida você perdeu!!!! 14 - Veja quanto tempo da sua vida você perdeu!!!! E além do mais, na Dinamarca não se pode criar macaco!E além do mais, na Dinamarca não se pode criar macaco!