Criptografia RSA e Teoria dos Números - Teorema de Fermat e Euler

1 O criptossistema RSA Rivest Shamir e Adleman 2 Foto antiga de Adi Shamir Ron Rivest e Leonard Adleman 3 Anel de Chaves Pública de Alice João Pedro Bob José Cifrar Texto Plano Texto Plano Algoritmo de Criptografia ex RSA Algoritmo de Decriptografia Texto Cifrado Chave Privada de Bob 4 Teorema de Fermat Seja p um número primo a 7 p 19 72 49 º 11 mod 19 74 º 121 º 7 mod 19 78 º 49 º 11 mod 19 716 º 121 º 7 mod 19 ap1 718 716 72 º 7 11 º 1 mod 19 p 5 a 3 35 243 º 3 mod 5 p 5 a 10 105 100000 mod 5 º 0 mod 5 i a Î Z ap º a mod p ii Se p a então ap1 º 1 mod p 5 Demonstração ii Supondo que p a Temse que os inteiros 1a 2a p1a formam o conjunto dos resíduos módulo p Isto pode ser mostrado da maneira a seguir Pegando dois resíduos ia e ja os mesmos têm que estar na mesma classe de resíduos isto é ia º ja mod p Þ pi ja Como p a Þ pij Como ip e jp Þ ij Logo os inteiros 1 2 3 p1 é um rearranjo recomposição de a 2a 3a p1a módulo p Þ ap1p1 º p1 mod p Þ pp1 ap11 Como p p 1 Þ pap11 com requerido ap1 º 1 mod p i Multiplicando ambos os lados da congruência ap1 º 1 mod p por a Þ a ap1 º a1 mod p Þ ap º a mod p quando pa Se pa a congruência ap º a mod p é trivial pois ambos os lados são º 0 mod p a é múltiplo de p 6 Função phi de Euler fn é Número de Inteiros positivos menores que n e relativamente primos a n Se p e q são primos então fp p1 e fq q1 fpq fpfq p1q1 f21 12 f3f7 2 x 6 3171 onde os 12 inteiros são 1245810111316171920 1 1 Õ i i e i m i ie p p f m 7 Teorema de Euler afn º 1 mod n a 3 n 10 f10 4 34 81 º 1 mod 10 a 2 n 11 f11 10 210 1024 º 1 mod 11 Com a e n relativamente primos 8 Aspectos Computacionais Exponenciação d 1 para i k passo 1 até 0 faça d d x d mod n se bi 1 então d d x a mod n fim se fim para retorna d d am mod n a mod n x b mod n mod n a x b mod n Seja m bkbk1b0 Õ Õ Õ å ¹ ¹ ¹ å ¹ ú û ù ê ë é ¹ 0 2 0 2 0 2 2 0 mod mod mod 2 0 i i i i i i ib i i b b m b m b i n a n a n a a a a m 9 Criptografia de chave pública Alguns algoritmos de chave pública RSA Utiliza teoria dos números Segurança dificuldade de fatorar números inteiros grandes McEliece Utiliza teoria algébrica dos códigos lineares Segurança Dificuldade de decodificar códigos de blocos lineares ElGamal Utiliza corpos finitos Segurança Dificuldade do problema do logaritmo discreto para corpos finitos Elliptic Curve Utiliza Curvas elípticas 10 Simétrica x Assimétrica Rápida Gerência e distribuição das chaves é complexa Não oferece assinatura digital Lenta Gerência e distribuição das chaves é simples Oferece assinatura digital 11 Sistema Híbrido exemplo Emissor cria uma chave simétrica Emissor criptografa a mensagem com a chave simétrica criada Emissor criptografa a chave simétrica com a chave pública do receptor Emissor envia a mensagem e a chave criptografada Receptor descriptografa a chave utilizado a sua chave secreta Receptor descriptografa a mensagem utilizando a chave simétrica que descriptografou anteriormente 12 Protocolos que empregam Sistemas Híbridos IPSEC Padrão desenvolvido para o IPv6 SSL e TLS Utilizado nos protocolos NTTP HTTP SMTP e Telnet PGP Criptografia de email pessoal SMINE Criptografia de email corporativo SET Transações financeiras X509 Relacionamento entre as autoridades de certificação 13 Criptografia de chave pública É assimétrica porque utiliza um par de chave Uma para encriptar e a outra para decriptar a mensagem Desenvolvida para resolver duas questões Distribuição de chaves Assinaturas digitais Invenção pública por Whitfield Diffie Martin Hellman na Universidade de Stanford em 1976 14 Criptografia de chave pública É o avanço mais significativo em 3000 anos de criptografia Utilizase duas chaves que devem ter as características Computacionalmente intratável determinar a chave de decifragem conhecendo apenas o algoritmo e a chave utilizada na cifragem Computacionalmente fácil cifrardecifrar mensagens quando a chave correta é conhecida Alguns algoritmos permitem que as duas chaves possam ser utilizadas para cifrar ou decifrar 15 Criptografia de chave pública Funções unidirecionais Dado x é de fácil complexidade calcular fx mas é intratável calcular x através de fx ou seja fácil de se calcular fx e difícil de se calcular f1x Os algoritmos de chave pública utilizam funções unidirecionais com segredo 16 Anel de Chaves Pública de Alice João Pedro Bob José Cifrar Texto Plano Texto Plano Algoritmo de Criptografia ex RSA Algoritmo de Decriptografia Texto Cifrado Chave Privada de Bob 17 Anel de Chaves Pública de Bob João Pedro Alice José Autenticação Texto Plano Texto Plano Algoritmo de Criptografia ex RSA Algoritmo de Decriptografia Texto Cifrado Chave Privada de Alice 18 Criptografia de chave pública O RSA Desenvolvido por Ron Rivest Adi Shamir e Len Adleman em 1977 Algoritmo de chave pública mais conhecido e utilizado Baseado em exponenciações de inteiros utilizando aritmética modular Exponenciação leva Olog n3 operações fácil cifrardecifrar Utiliza inteiros muito grandes por exemplo 2048 bits Segurança Dificuldade de fatorar nos inteiros grandes Fatoração leva Oe log n log n log noperações difícil obter a chave privada a partir da chave pública 19 Selecione pq p e q primos Calcular n p x q Calcular fn p1q1 Selecionar e inteiro gcdfne 1 1 e fn Calcular d d e1 mod fn Chave Pública KUen Chave Privada KRdn Geração da Chave Texto Plano M n Texto Cifrado C Me mod n Cifrar Texto Cifrado C Texto Claro M Cd mod n Decifrar Algoritmo RSA 20 Exemplo RSA Selecionar dois números primos p 7 e q 17 Calcular n pq 7 x 17 119 Calcular fn p1q1 96 Selecionar e tal que e é relativamente primo a fn e menor que fn e 5 Determinar d tal que de 1 mod 96 e d 96 d 77 pois 77 x 5 385 4 x 96 1 Kp 5119 e Ks 77119 21 Continuação do Exemplo 195 2476099 119 20807 66 KU 5119 Texto Plano 19 6677 127x10140 119 106x10138 19 KR 77119 Texto Plano 19 Texto Cifrado 66 Cifrar Decifrar 22 Exercício 6677 127x10140 119 106x10138 19 KR 77119 Texto Plano 19 Decriptar Usar o algoritmo para calcular d ab mod n d 6677 mod 119 23 Porque é que o RSA funciona Teorema de Euler afn º 1 mod n No RSA temos npq e fnp1q1 e d são inversos mod fn ed º 1 mod fn portanto ed 1kfn Cd Med M1kfn M1Mfnk M11k M1 M 24 Criptografia de chave pública RSA Considerações A dificuldade de se quebrar o RSA baseiase na intratabilidade de fatorar n na ordem de 618 dígitos decimais ou de determinar jn ou d que são problemas computacionalmente equivalentes Os números p e q devem diferir em alguns bits de comprimento caso contrário p e q ficarão muito próximos da RAIZn Os números p1 e q1 devem conter fatores primos grandes O mdcp1q1 deve ser pequeno Obs 4096 bits 1234 dígitos decimais 1024 bits 310 dígitos decimais 25 Geração da chave do RSA Os utilizadores do RSA têm que determinar dois números primos ao acaso p e q selecionar e ou d e calcular o outro Os primos p e q não podem ser determinados facilmente a partir de n npq têm que ser suficientemente grandes não há métodos diretos para determinar primos muito grandes tipicamente usam números aleatórios e testes de primalidade Esses testes não garantem que o número seja primo 26 Geração da chave do RSA Algoritmo de MillerRabin Escolhe n ímpar e fazse n1 2km com m impar Escolhe um inteiro a aleatório 1 a n1 Calcula b am mod n se bº1 mod n então escreva n é primo e sair para i0 até k1 faça se b º 1 mod n então escreva n é primo e sair else b b2 mod n escreva n é composto 27 Geração da chave do RSA Considerações a probabilidade de um número ímpar aleatório p ser primo é Pp ser primo Exemplo para o RSA com módulo n 1024bit os primos p e q devem ter 512 comprimento de cerca de 512 bits ou seja p q 2 Logo Pp ser primo Exercício Calcular Pp para o RSA com módulo n 2048 bits 28 Geração da chave do RSA Considerações O número de execuções no teste de primalidade do algoritmo de Miller Rabin para uma probabilidade de erro inferior a 201 é Comprimento em bits de p Número de execuções ssegurança 250 11 300 9 400 6 500 5 600 3 29 Geração da chave do RSA Algoritmo de MillerRabin Exemplo Testar se o número 91 é primo Realizar 4 testes Primeiro teste a 12 Segundo teste a 17 Terceiro teste a 38 Quarto teste a 39 Mostre o resultado de cada teste