Por que os primos são importantes na criptografia?

Uma coisa que sempre me parece não criptografadora: por que é tão importante usar números primos? O que os torna tão especiais em criptografia?

Alguém tem uma explicação curta e simples ? (Estou ciente de que existem muitos iniciadores e que a Criptografia Aplicada é a Bíblia, mas como foi dito: não pretendo implementar meu próprio algoritmo criptográfico, e as coisas que encontrei acabaram de fazer meu cérebro explodir - não há 10 páginas de fórmulas matemáticas por favor :))

Obrigado por todas as respostas. Aceitei o que tornou o conceito atual mais claro para mim.

Explicação mais básica e geral: a criptografia tem tudo a ver com teoria dos números e todos os números inteiros (exceto 0 e 1) são compostos de números primos; portanto, você lida muito com números primos na teoria dos números.

Mais especificamente, alguns algoritmos criptográficos importantes, como RSA, dependem criticamente do fato de que a fatoração primária de grandes números leva muito tempo. Basicamente, você tem uma "chave pública" que consiste em um produto de dois primos grandes usados ​​para criptografar uma mensagem e uma "chave secreta" que consiste nesses dois primos usados ​​para descriptografar a mensagem. Você pode tornar a chave pública pública e todos podem usá-la para criptografar mensagens para você, mas somente você conhece os principais fatores e pode descriptografar as mensagens. Todos os outros teriam que fatorar o número, o que leva muito tempo para ser prático, dado o estado atual da arte da teoria dos números.

Simples? Sim.

Se você multiplicar dois números primos grandes, obtém um número não primo enorme com apenas dois fatores primos (grandes).

Fatorar esse número é uma operação não trivial e esse fato é a fonte de muitos algoritmos criptográficos. Consulte as funções de mão única para obter mais informações.

Adendo: Apenas um pouco mais de explicação. O produto dos dois números primos pode ser usado como uma chave pública, enquanto os primos são uma chave privada. Qualquer operação feita com dados que só pode ser desfeita por se conhecer um dos dois fatores não será trivial para descriptografar.

Aqui está um exemplo muito simples e comum.

O algoritmo de criptografia RSA, comumente usado em sites de comércio seguro, baseia-se no fato de que é fácil pegar dois números primos (muito grandes) e multiplicá-los, enquanto é extremamente difícil fazer o oposto - o que significa: número muito grande, dado que possui apenas dois fatores principais, e encontre-os.

Não são tanto os números primos que são importantes, mas os algoritmos que funcionam com números primos. Em particular, encontrar os fatores de um número (qualquer número).

Como você sabe, qualquer número tem pelo menos dois fatores. Os números primos têm a propriedade única, pois possuem exatamente dois fatores: 1 e eles mesmos.

A razão pela qual a fatoração é tão importante é que matemáticos e cientistas da computação não sabem como fatorar um número sem simplesmente tentar todas as combinações possíveis. Ou seja, primeiro tente dividir por 2, depois por 3, depois por 4 e assim por diante. Se você tentar fatorar um número primo - especialmente um número muito grande - precisará tentar (essencialmente) todos os números possíveis entre 2 e esse número primo grande. Mesmo nos computadores mais rápidos, levará anos (até séculos) para fatorar os tipos de números primos usados ​​na criptografia.

É o fato de que não sabemos como fatorar eficientemente um grande número que dá força aos algoritmos criptográficos. Se, um dia, alguém descobrir como fazê-lo, todos os algoritmos criptográficos que usamos atualmente se tornarão obsoletos. Isso continua sendo uma área aberta de pesquisa.

Porque ninguém conhece um algoritmo rápido para fatorar um número inteiro em seus fatores primos. No entanto, é muito fácil verificar se um conjunto de fatores primos se multiplica em um determinado número inteiro.

Existem alguns bons recursos para aumentar a criptografia. Aqui está um:

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

A partir dessa página:

No sistema de criptografia de chave pública mais usado, inventado por Ron Rivest, Adi Shamir e Len Adleman em 1977, as chaves pública e privada são derivadas de um par de grandes números primos, de acordo com uma fórmula matemática relativamente simples. Em teoria, pode ser possível derivar a chave privada da chave pública, trabalhando a fórmula para trás. Mas apenas o produto dos grandes números primos é público, e fatorar números desse tamanho em números primos é tão difícil que mesmo os supercomputadores mais poderosos do mundo não conseguem quebrar uma chave pública comum.

O livro de Bruce Schneier, Applied Cryptography, é outro. Eu recomendo esse livro; é uma leitura divertida.

Para ser um pouco mais concreto sobre como o RSA usa propriedades de números primos, o algoritmo RSA depende criticamente do Teorema de Euler , que afirma que para números relativamente primos "a" e "N", a ^ e é congruente a 1 módulo N, onde e é a função totiente de Euler de N.

Onde os primos entram nisso? Calcular a função totiente de Euler de N exige conhecer a fatoração primária de N. No caso do algoritmo RSA, em que N = pq para alguns primos "p" e "q", então e = (p - 1) (q - 1) = N - p - q + 1. Mas sem conhecer p e q, o cálculo de e é muito difícil.

Mais abstratamente, muitos protocolos criptográficos usam várias funções de alçapão , funções fáceis de calcular, mas difíceis de inverter. A teoria dos números é uma fonte rica de tais funções de alçapão (como a multiplicação de grandes números primos), e os números primos são absolutamente centrais para a teoria dos números.

Eu sugeriria o livro Uma jornada matemática em código . O livro tem uma sensação agradável e realista, o que é surpreendente, pois trata-se de criptografia. O livro resume a jornada de Sarah Flannery, da aprendizagem de quebra-cabeças em criança à criação do algoritmo Cayley-Purser (CP) aos 16 anos de idade. Ele fornece uma explicação incrivelmente detalhada das funções de sentido único, teoria dos números e números primos, e como eles se relacionam com eles. criptografia.

O que torna este livro ainda mais específico à sua pergunta é que Sarah tentou implementar um novo algoritmo de chave pública usando matrizes. Era muito mais rápido do que usar números primos, mas foi encontrado um loop loop que poderia explorá-lo. Acontece que o algoritmo dela foi melhor usado como um mecanismo de criptografia privada. O livro é um grande testemunho do uso de números primos para criptografia, pois resistiu ao teste do tempo e aos desafios de indivíduos muito inteligentes.

Mais um recurso para você. Segurança agora! O episódio 30 (podcast de ~ 30 minutos, link para a transcrição) fala sobre problemas de criptografia e explica por que os números primos são importantes.

Eu não sou um matemático ou criptográfico, então aqui está uma observação externa em termos leigos (sem equações sofisticadas, desculpe).

Todo esse segmento é preenchido com explicações sobre COMO os primos são usados ​​na criptografia, é difícil encontrar alguém nesse segmento explicando de maneira fácil POR QUE os primos são usados ​​... provavelmente porque todos tomam esse conhecimento como garantido.

Apenas olhar para o problema de fora pode gerar uma reação semelhante; mas se eles usam somas de dois números primos, por que não criar uma lista de todas as somas possíveis que dois números primos podem gerar?

Neste site, há uma lista de 455.042.511 primos, onde os primos mais altos são 9.987.500.000 ( 10 dígitos).

O maior número primo conhecido (a partir de fevereiro de 2015) é 2 à potência de 257.885.161 - 1, que é 17.425.170 dígitos.

Isso significa que não faz sentido manter uma lista de todos os primos conhecidos e muito menos todas as suas possíveis somas. É mais fácil pegar um número e verificar se é primo.

O cálculo de números primos grandes por si só é uma tarefa monumental; portanto, o cálculo reverso de dois números primos que foram multiplicados entre si, tanto pelos criptógrafos quanto pelos matemáticos, diria que já é difícil o suficiente ... hoje.

Os algoritmos criptográficos geralmente confiam em sua segurança para ter um "problema difícil". A maioria dos algoritmos modernos parece usar o fatoração de números muito grandes como seu problema difícil - se você multiplicar dois números grandes juntos, calcular os fatores deles é "difícil" (isto é, demorado). Se esses dois números são números primos, existe apenas uma resposta, o que torna ainda mais difícil e também garante que, quando você encontrar a resposta, ela é a correta, e não outra resposta que dê o mesmo resultado.

Eu acho que o que é importante na criptografia não são os primos em si, mas é a dificuldade primo do problema de fatoração principal

Suponha que você tenha um número inteiro muito grande, que é conhecido por ser o produto de dois primos m e n, não é fácil encontrar o que são m e n. Algoritmos como o RSA dependem desse fato.

A propósito, existe um artigo publicado sobre algoritmo que pode "resolver" esse problema de fatoração primária em tempo aceitável usando computador quântico. Portanto, algoritmos mais recentes em criptografia podem não contar mais com essa "dificuldade" de fatoração primária quando o computador quântico chegar à cidade :)

Porque os algoritmos de fatoração aceleram consideravelmente com cada fator encontrado. Tornar as duas chaves privadas ativadas garante que o primeiro fator encontrado também seja o último. Idealmente, as duas chaves privadas também terão quase o mesmo valor, pois apenas a força das chaves mais fracas é importante.

Os números primos são usados ​​principalmente na criptografia, pois consome um tempo considerável para determinar se um determinado número é número primo ou não. Para o hacker, se algum algoritmo leva muito tempo para quebrar o código, ele se torna inútil para ele