Estimativa de intervalo máximo entre números primos para criptografia RSA

UNIVERSIDADE SÃO JUDAS TADEU Centro de Pesquisa Programa Voluntário de Iniciação Científica

Fernando Ferreira de Oliveira

Estimativa de intervalo máximo entre números primos para criptografia RSA

São Paulo, 2015

UNIVERSIDADE SÃO JUDAS TADEU Centro de Pesquisa Programa Voluntário de Iniciação Científica

Fernando Ferreira de Oliveira

Estimativa de intervalo máximo entre números primos para criptografia RSA

Projeto de pesquisa apresentado ao Programa

Voluntário

de

Iniciação

Científica do Centro de Pesquisa da Universidade São Judas Tadeu, como requisito parcial das Atividades de Pesquisa. Orientador(a): Prof. Rodolfo Riyoei Goya

São Paulo, 2015

Componentes do Projeto de Pesquisa 1. Introdução 1.1. 1.2.

Apresentação do tema e delimitação do problema Justificativa

2. Revisão de Literatura (ou Fundamentação Teórica) 2.1. Objetivos (e/ou Hipóteses) 2.1.1. Objetivo Geral 2.1.2. Objetivos Específicos

3. Método (ou Material e Métodos) 3.1. 3.2. 3.3.

Sujeitos (ou Amostragem) Materiais Procedimentos

4. Plano de Análise dos Dados 5. Cronograma 6. Referências Bibliográficas 7. Anexos 7.1. 7.2.

Anexo A Anexo B

8. Apêndices 8.1. 8.2.

Apêndice A Apêndice B

1. Introdução 1.1.

Apresentação do tema e delimitação do problema A descoberta dos números primos é imprescindível na área da Matemática, na

qual os mesmos intitulam o princípio central do campo de estudo da Teoria dos Números. Um número qualquer é considerado primo se, e somente se, for divisível apenas por 1 e por ele mesmo. De forma mais específica, se p é um número primo, então p=a . b para a⩽b , na qual a=1 e b=p . Os dez primeiros números primos são 2, 3, 5, 7, 11, 13, 17, 19, 23 e 27. De acordo com o Teorema Fundamental da Aritmética, qualquer número inteiro positivo maior que 1 pode ser expressado como um produto de números primos. Por exemplo, o número 105 é unicamente expressado como 3×5×7, enquanto o número 32 é unicamente expressado como 2×2×2×2×2. Este conjunto único de números multiplicados até n, é chamado de fatoração de números primos de n. Os números primos são altamente utilizados em segurança da informação, através de algoritmos de criptografia para transmissão de dados. O objetivo principal da criptografia é que informações trocadas por dois meios não sejam interpretadas por um possível interceptador. As informações podem ser transformadas da sua forma original para outra de forma ilegível, na qual as mesmas possam ser reconhecidas apenas por seu destinatário. O destinatário possui uma chave secreta para que ele possa reconhecer as informações, o que torna difícil o processo de interpretação por alguém que não esteja autorizado. O algoritmo de criptografia RSA é considerado um dos mais eficientes em segurança de dados, na qual se baseia na dificuldade em fatorar um número n em seus componentes primos. Fatorar números pequenos é algo consideravelmente simples,

porém fatorar números muito grandes torna o processo extremamente complicado e demorado. A dificuldade ocorre devido a não possibilidade de resolução em um tempo polinomial determinístico, ou seja, não há uma fórmula ou um padrão a ser seguido. Portanto, a falta de padronização entre números primos é um problema tanto para o processo de criptografia quando para o processo de decriptografia de dados. Um dos problemas do algoritmo de criptografia RSA é a geração de chaves privadas. Como uma parte do processo de geração é feito por tentativa e erro ou por funções de aproximação, um intervalo muito grande entre dois números primos consecutivos pode tornar o processo mais demorado. Porém, através dos resultados recentes sobre intervalo máximo entre números primos pode fazer com que o algoritmo seja mais eficiente futuramente, trazendo uma nova perspectiva e novas possibilidades durante o processo.

1.2.

Justificativa Conforme as descobertas recentes sobre o intervalo máximo entre números

primos consecutivos menores que X, o intervalo de busca por um número primo antecessor pode ser reduzido e consequentemente pode trazer maior eficiência aos sistemas que utilizam criptografia RSA. Como o sistema de criptografia utiliza números muito grandes para geração de chaves públicas e privadas, na ordem de 10100 no mínimo, a redução da área de busca por um número primo resulta em melhora de performance e diminuição de possíveis ciberataques. As descobertas mais recentes são apenas descobertas matemáticas e que não tinha uma aplicação direta. Porém, os resultados seguem características que podem ser

implementadas na otimização do algoritmo de criptografia RSA, principalmente pelo fato de que a descoberta tem como foco números primos muito grandes.

2. Revisão de Literatura (ou Fundamentação Teórica) 2.1.

Objetivos (e/ou Hipóteses)

2.1.1. Objetivo Geral O principal objetivo desta pesquisa é apresentar os estudos e avanços relacionados ao intervalo máximo entre números primos consecutivos e apresentar possíveis soluções ou alternativas para maior eficiência na geração de chaves privadas em algoritmos de criptografia RSA. Em relação ao intervalo entre números primos, o objetivo é apresentar a evolução no desenvolvimento do mesmo com o passar do tempo e abordar questionamentos sobre o assunto que ainda não foram totalmente respondidas na área da Matemática. Em relação a criptografia RSA, o objetivo é introduzir o conceito da criptografia e a geração de chaves públicas e privadas. Além disso, será abordado as formas possíveis de geração de chaves privadas e como o intervalo entre números primos pode ser utilizado para otimização do algoritmo.

2.1.2. Objetivos Específicos 1. Levantamento de artigos científicos e informações sobre intervalo entre números primos. 2. Levantamento de artigos científicos e informações sobre criptografia RSA e processos de desenvolvimento do algoritmo.

3. Desenvolvimento do algoritmo para determinar o intervalo máximo entre números primos consecutivos. 4. Realização de testes do algoritmo. 5. Integrar o algoritmo em uma parte do processo de geração de chave privada na criptografia RSA. 6. Realização de testes do algoritmo integrado à criptografia RSA.

3. Método (ou Material e Métodos) 3.1.

Sujeito (ou Amostragem) Todo o levantamento de informações sobre o intervalo máximo entre números

primos consecutivos e criptografia RSA será feito através de análise em artigos científicos conceituados e revisados, na qual será apresentado as propostas mais relevantes dos mesmos. O desenvolvimento do algoritmo e sua integração ao sistema de criptografia RSA serão realizados em uma linguagem de programação, visando maior simplicidade para tratamento das informações e testes de desempenho, facilitando o processo de análise.

3.2.

Materiais Durante a pesquisa será implementado e testado o algoritmo RSA na

linguagem de programação C++. Livros, artigos e periódicos serão utilizados para melhor compreensão do algoritmo. O software Gantt Project será utilizado para criação do diagrama de Gantt para melhor acompanhamento do projeto.

3.3.

Procedimentos Primeiramente será feito o levantamento de informações, principalmente as

contidas em artigos científicos. Esse levantamento será feito tanto para os números primos quanto para a criptografia RSA. Com todas as informações necessárias, será iniciado o processo de desenvolvimento do algoritmo a partir da pesquisas por números primos. Após esses procedimentos, serão realizados os testes. Assim que o algoritmo já esteja desenvolvido e devidamente testado, será iniciado o processo de integração do mesmo com o método de geração de chave privada da criptografia RSA. Após esses procedimentos, serão realizados os testes.

4. Plano de Análise de Dados Todos os testes, tanto do algoritmo para números primos quanto a integração com a geração de chaves privadas, serão realizados com números considerados médios (na ordem de 1010 −1020 aproximadamente), devido as limitações de hardware. Não serão considerados testes para números pequenos, visto que o foco principal na criptografia é trabalhar com números muito grandes. Serão realizados testes e análises em relação a geração de chaves privadas antes da uilização do novo algoritmo e depois do uso do novo algoritmo. Será avaliado a quantidade de intervalos que é utilizado em ambos os casos.

5. Referências Bibliográficas [1] Stallings, William, Cryptography and Network Security. Pearson, vol. 5, pp. 266299, USA, 2011. [2] Maynard, James; Tao, Terence; Ford, Kevin; Green, Ben; Konyagin, Sergei, Long gaps between primes, Cornell University Library, 2014. Disponível em http://arxiv.org/abs/1412.5029. Acesso em 07 de setembro de 2015. [3] Maynard, James, Large gaps between primes, Cornell University Library, 2014. Disponível em http://arxiv.org/abs/1408.5110. Acesso em 07 de setembro de 2015. [4] Tao, Terence; Ford, Kevin; Green, Ben; Konyagin, Sergei, Large gaps between consecutive prime numbers, Cornell University Library, 2014. Disponível em http://arxiv.org/abs/1408.4505. Acesso em 07 de setembro de 2015. [5] Klarreich, Erica, Mathematicians make major discovery about prime numbers. Disponível

em:

http://www.wired.com/2014/12/mathematicians-make-major-

discovery-prime-numbers. Acesso em 15 de setembro de 2015.

6. Anexos 6.1.

Anexo A Para explicar o intervalo máximo entre primos consecutivos menores que X, o

mesmo será denominado como G(X). Considerar pn o n-ésimo número primo. G ( X ) := max p n+1 ≤X ( p n+ 1− p n ) . De acordo com o teorema dos números primos, sabemos que o intervalo médio entre números primos é: G ( X ) ≥( 1 + o ( 1 ) ) log X , Na qual o ( 1 ) significa que a quantidade tende a zero conforme X → ∞. Portanto, o intervalo médio para valores menores ou iguais a X é de aproximadamente log X. Porém, o intervalo médio não pode ser utilizado em criptografia RSA, pois não satisfaz todas as condições (como é uma média, não tem como definir um intervalo mínimo ou máximo). O problema em relação ao intervalo médio é mostrado na figura abaixo.

Figura 2: Intervalo médio entre números primos

Como é possível observar na Figura 2, o intervalo entre números primos possui muitas variações conforme avançamos ao infinito. Isso significa que um intervalo pode ser muito maior ou muito menor que a média. Em 1931, Erik Westzynthius provou que o intervalo entre números primos consecutivos pode ser um múltiplo do intervalo médio, arbitrariamente grande. Ou seja, G ( X ) / log X →∞ assim como X →∞ . Além disso, ele provou que: G ( X )≫

log X log 3 X . log4 X

Em 1935, Paul Erdős aprimorou o limite quantitativo de Westzynthius para: G ( X )≫

log X log 2 X 2

( log3 X )

.

Em 1938, Robert Rankin aprimorou ainda mais o limite de Erdős para: G ( X ) ≫ ( c+o ( 1 ) ) Para

simplificação,

log X log 2 X log 4 X

( log3 X )

log2 X= loglog X ,

2

.

log3 X=logloglog X e

assim

sucessivamente. A constante c foi definida por Rankin utilizando conceitos da conjectura de Erdős, na qual afirma que se A é um conjunto de números inteiros positivos em que a soma de seus recíprocos diverge, então esse conjunto possui uma progressão aritmética de tamanho qualquer. Rankin inicialmente definiu c= 1/3 . Alguns estudiosos na época achavam que tal limite era ridículo e que o mesmo seria melhorado rapidamente. Mas com o passar do tempo, o único ponto em que houve mudanças de fato, foi apenas o valor da constante c. A estrutura principal se manteve a mesma por muitos anos. A constante c posteriormente foi aprimorada para

1 γ e (γ sendo a constante de 2

Euler) por Arnold Schönhage em 1936, depois para c=eγ por Robert Rankin, depois

para c= 1. 31256 e γ por Helmut Maier e Carl Pomerance e depois para c= 2 e γ por János Pintz. Em 2014, James Maynard mostrou que, ao fazer uma análise de limite quantitativo (taxa de crescimento), a fórmula de Rankin possui um limite

f ( X ) na

forma: f ( X )≈

log3 X log4 X

.

Ao formar um produto com a fórmula de Rankin apresenta um limite: G ( X )≫

log X log2 X . log3 X

Ainda em 2014, a equipe de matemáticos formada por James Maynard, Terence Tao, Kevin Ford, Ben Green e Sergei Konyagin melhorou o limite quantitativo na forma: f ( X )≈ log 3 X ,

na qual permitiu um ajuste na fórmula como um todo. Portanto, aplicando o produto entre

f ( X ) e G ( X ) na fórmula de Rankin como feito anteriormente, chegamos

na conclusão de que o intervalo máximo entre primos consecutivos, para X sendo um número suficientemente grande possui a forma: G ( X ) ≫ ( c+o ( 1 ) )

log X log 2 X log 4 X . log 3 X

Porém, ainda não há um consenso sobre o valor da constante c que satisfaça todas as condições de intervalos. Com a mudança da estrutura de G(X), será necessário novos estudos sobre o valor arbitrário da constante c.

6.2.

Anexo B O algoritmo RSA tem como ideia principal a geração de um par de chaves, uma

chave pública que pode ser reconhecida por qualquer indivíduo e uma chave privada que deve ser mantida em sigilo e que apenas o(s) receptor (es) pode(m) reconhecê-la. A mensagem é cifrada utilizando a chave pública e só pode ser decifrada utilizando a respectiva chave privada. A Figura 3 apresenta a ideia básica do algoritmo RSA.

Figura 3: Procedimento do algoritmo RSA

7. Apêndices 7.1.

Apêndice A Foi desenvolvido um pseudocódigo, mostrando os passos utilizados pelo

algoritmo RSA para geração da chave privada. O pseudocódigo foi desenvolvido levando em consideração o uso da estimativa de intervalo máximo entre primos consecutivos, na qual há uma visão geral de como o mesmo poderá ser utilizado para trazer maior eficiência. Existem dois métodos eficientes para a geração de números primos baseados em números aleatórios: o método OpenSSL e o FIPS 186-3. O OpenSSL é uma

implementação de código aberto relacionada a criptografia, desenvolvida para a linguagem de programação C. O FIPS 186-3 é outro método que utiliza a geração de números primos para assinatura digital. O pseudocódigo desenvolvido foi baseado no método OpenSSL, por ser código aberto. A estimativa de intervalo máximo poderá ser aplicada em ambos os métodos, ou qualquer outro método para geração de números primos. Portanto: 1. Gerar um número aleatório ímpar p com 512 bits de tamanho (154 dígitos). 2. Aplicar os testes de Fermat e Miller-Rabin. 2.1. Se p não for possivelmente primo, então: 2.1.1.

p ← p + 2.

2.1.2.

Retornar ao passo 2.

Senão: 2.1.3.

O número p é válido.

3. Gerar um número aleatório ímpar q com 512 bits de tamanho (154 dígitos). 4. Aplicar os testes de primalidade de Fermat e Miller-Rabin. 4.1. Se q não for possivelmente primo, então: 4.1.1.

q ← q + 2.

4.1.2.

Retornar ao passo 4.

Senão: 4.1.3.

O número q é válido.

5. n ← (p*q) 6. φ(n) ← (p-1)*(q-1) 7. e ← 65537 8. d ← inverso multiplicativo de e(mod φ(n))

9. Se d > 0, então: 9.1. Retorna as chaves pública e privada. Senão: c∗log p∗log 2 p∗log 4 p log 3 p

9.2.

intervalo ← p -

9.3.

Enquanto intervalo < p: 9.3.1.

Se intervalo for um número primo, então:

9.3.1.1

Retornar ao passo 5.

Senão: 9.3.2.

intervalo ← intervalo + 1.

A chave pública é formada por n e pelo expoente de encriptação e. A chave privada é formada por n e pelo expoente de decriptação d (na qual deve permanecer secreto). Os valores de p, q e φ(n) devem ser mantidos em segredo também, visto que os mesmos são utilizados para formar o expoente de descriptografia. Durante a geração de um número aleatório, foi especificado que o mesmo seja ímpar devido ao teste de primalidade. Testes como os de Fermat e Miller-Rabin irão imediatamente descartar números pares, portanto é gerado um número primo para não gerar mais iterações ao longo do algoritmo. Caso o número não passe pelos dois testes de primalidade, retomamos o processo para o próximo número ímpar, até que se encontre um número que possivelmente seja primo. Sendo p e q válidos é calculado n (correspondente ao tamanho das chaves pública e privada), φ(n) (função totiente de Euler que define a quantidade de números menores ou igual a x co-primos a ele), e (expoente de encriptação) e d (expoente de decriptação).

Por padrão na criptografia RSA, é atribuído a e o valor 65537. O número 65537 é um número primo grande o suficiente para evitar ataques, pois fazer sua fatorização é relativamente complexo . Caso d seja um expoente com valor negativo, significa que a criptografia será facilmente quebrada. Portanto, caso isso ocorra, é utilizado o intervalo máximo entre primos consecutivos, permitindo encontrar o número anterior a p e refazendo o processo. Caso d seja positivo, as chaves pública e privada são válidas.

7.2.

Apêndice B O fluxograma apresentado na Figura 4.1 mostra a geração de chaves privadas na

criptografia RSA sem o uso da estimativa de intervalo máximo entre números primos. Um dos grandes problemas da geração de chaves privadas é quando o valor de d (expoente da chave privada) é negativo. Como d é o expoente que será utilizado na geração da chave, caso o mesmo seja negativo, a decriptografia pode ser quebrada mais facilmente por um interceptador. Portanto, geralmente são gerados novos números aleatórios e o processo é refeito, até que d seja positivo. Este processo pode ser demorado caso os números aleatórios tenham intervalos muito grandes em relação aos números primos mais próximos. A Figura 4.2 mostra o fluxograma para uma das possíveis soluções para a geração de chaves privadas na criptografia RSA utilizando o intervalo máximo entre números primos. Considerando o caso em que o par de números primos (p, q) não tenha passado no teste de cálculo do expoente d. Neste caso, em vez de gerar novos números aleatórios, calculamos o número primo anterior e pulamos duas etapas do processo de geração de chaves privadas (geração dos números aleatórios e os números primos).

O que fazia com que o processo de encontrar o número primo anterior não fosse muito interessante, era o fato de que os intervalos entre primos consecutivos poderia ser muito grande a ponto de ser mais eficiente gerar novos números. Porém, com a descoberta do intervalo máximo, esta possibilidade poderá ser viável futuramente. A utilização do intervalo máximo em criptografia RSA torna os resultados ainda mais evidentes, visto que os sistemas reais utilizam números primos de ordem 10100 no mínimo, como já foi detalhado anteriormente.

Figura 4.1: Fluxograma de chave privada na criptografia RSA

Figura 4.2: Fluxograma de chave privada com estimativa na criptografia RSA