Por que a maioria da criptografia depende de pares grandes de números primos, em oposição a outros problemas?

9

A maioria dos métodos atuais de criptografia depende da dificuldade de fatorar números que são o produto de dois grandes números primos. Pelo que entendi, isso é difícil apenas enquanto o método usado para gerar os números primos grandes não puder ser usado como um atalho para fatorar o número composto resultante (e que fatorar grandes números em si é difícil).

Parece que os matemáticos encontram atalhos melhores de tempos em tempos e, como resultado, os sistemas de criptografia precisam ser atualizados periodicamente. (Também há a possibilidade de que a computação quântica acabe tornando a fatoração um problema muito mais fácil, mas isso não surpreenderá ninguém se a tecnologia alcançar a teoria.)

Alguns outros problemas são comprovadamente difíceis. Dois exemplos que vêm à mente são variações no problema da mochila e no problema do vendedor ambulante.

Eu sei que Merkle-Hellman foi quebrado, que Nasako-Murakami permanece seguro e que os problemas da mochila podem ser resistentes à computação quântica. (Obrigado, Wikipedia.) Não encontrei nada sobre como usar o problema do vendedor ambulante para criptografia.

Então, por que pares de números primos grandes parecem governar a criptografia?

  • É simplesmente porque atualmente é fácil gerar pares de números primos grandes que são fáceis de multiplicar, mas difíceis de fatorar?
  • Será que o fato de pares de primos grandes de fatoração serem comprovadamente difíceis em um grau previsível que seja bom o suficiente?
  • Os pares de números primos grandes são úteis de outra maneira que não a dificuldade, como a propriedade de trabalhar para criptografia e assinatura criptográfica?
  • O problema de gerar conjuntos de problemas para cada um dos outros tipos de problemas difíceis o suficiente para o próprio objetivo criptográfico é muito difícil de ser prático?
  • As propriedades de outros tipos de problemas são insuficientemente estudadas para serem confiáveis?
  • De outros.
Steve
fonte
8
Primeiro, tenho certeza de que a criptografia de curva elíptica é usada na prática, embora não me lembre em qual situação. No entanto, você está certo de que o RSA é usado muito mais do que outros sistemas de criptografia. Eu acho que o motivo é principalmente porque a criptografia RSA é algum tipo de padrão há anos, com muitos softwares (de bugs, é claro!) Implementando e com pessoas acostumadas. Outros sistemas de criptografia (baseados, por exemplo, em curvas ou treliças elípticas) são às vezes utilizáveis, mas é preciso que as pessoas as adquiram, e isso leva tempo! Mudança de hábitos ...
de Bruno
3
O @Bruno Bitcoin, por exemplo, usa curvas elípticas para assinar transações.
Martin Berger

Respostas:

9

Boaz Barak abordou isso em um post do blog

Minha opinião sobre seu post (grosso modo) é que só sabemos como projetar primitivas criptográficas usando problemas computacionais que possuem alguma estrutura, que exploramos. Sem estrutura, não sabemos o que fazer. Com muita estrutura, o problema se torna eficientemente computável (portanto inútil para fins criptográficos). Parece que a quantidade de estrutura precisa estar correta.

Tyson Williams
fonte
Ao ler esse artigo, pensei em outro motivo possível de que fatorar pares de números primos grandes continua sendo o método de escolha para criptografia de chave pública: é realmente difícil encontrar um substituto. O número de matemáticos que entendem qualquer alternativa é pequeno, o que (1) limita o número de pessoas que podem propor alternativas e (2) limita o número de pessoas que podem analisar com credibilidade as propostas para determinar se são viáveis. Primes podem não funcionar para sempre, mas funcionam por enquanto, por isso a inércia os mantém em uso.
9788 Steve #
6

Tudo o que eu vou dizer é bem conhecido (todos os links são para a Wikipedia), mas aqui vai:

  1. (Z/pqZ)×

  2. Existem outras abordagens para a criptografia, principalmente a criptografia baseada em treliça, que depende de certos problemas difíceis nas treliças (encontrar pontos com norma pequena na treliça, por exemplo) para implementar a criptografia de chave pública. Curiosamente, alguns desses sistemas são comprovadamente difíceis , ou seja, podem ser quebrados se e somente se o problema difícil correspondente na teoria da rede puder ser resolvido. Isso contrasta com, digamos, a RSA, que não oferece a mesma garantia . Observe que a abordagem baseada em rede é conjecturada como não sendo NP-difícil (mas parece mais difícil do que o fatoramento inteiro por enquanto).

  3. Há uma preocupação separada com o compartilhamento de chaves, ou seja, a revelação secreta , que possui propriedades muito interessantes da teoria da complexidade. Não conheço os detalhes, mas a teoria dos protocolos de conhecimento zero permite que Alice revele a Bob seu conhecimento de um segredo que NP é difícil de calcular (gráfico hamiltoniano) sem revelar o próprio segredo (o caminho nesse caso).

Por fim, convém verificar a página de criptografia pós-quantum para ver algumas abordagens alternativas para sistemas de criptografia de chave pública que dependem de problemas difíceis.

cody
fonte