Porque é que os primos são importantes na criptografia?

Simples? Sim.

Se multiplicarmos dois grandes números primos, obtemos um enorme número não primo com apenas dois (grandes) factores primos.

Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. Ver funções unidireccionais para mais informações.

Adenda: Só mais uma explicação. O produto dos dois números primos pode ser usado como uma chave pública, enquanto os próprios primos como uma chave privada. As operação feita a dados que só pode ser desfeita conhecendo um dos dois fatores será não-trivial para unencrypt.

Aqui está um exemplo muito simples e comum.

A algoritmo de criptografia RSA que é comumente usado em sites de comércio seguro, é baseado no fato de que é fácil tomar duas (muito grande) números primos e multiplicá-los, enquanto é extremamente difícil fazer o oposto - o que significa: tirar um número muito grande, dado que ele tem apenas dois factores primos, e encontrá-los.

Porque ninguém conhece um algoritmo rápido para factorizar um inteiro nos seus factores primos. No entanto, é muito fácil verificar se um conjunto de fatores primos se multiplicam para um certo número inteiro.

Há bons recursos para melhorar a criptografia. Aqui está um.

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

A partir dessa página:

Na chave pública mais utilizada sistema de criptografia, inventado por Ron Rivest, Adi Shamir, e Len Adleman in Em 1977, tanto o público como o privado as chaves são derivadas de um par de grandes números primos de acordo com a matemática relativamente simples formula. Em teoria, pode ser possível derivar a chave privada a partir da chave pública, trabalhando a fórmula para trás. Mas só a produto dos grandes números primos é público, e factoring números de que o tamanho em números primos é tão difícil que até os supercomputadores mais poderosos em o mundo não pode quebrar um comum chave.

O livro de Bruce Schneier A criptografia aplicada é outro. Eu recomendo muito esse livro; é divertido ler.

Não são tanto os números primos em si 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 sabe, qualquer número tem pelo menos dois factores. Números primos têm a propriedade única em que eles têm exatamente dois fatores: 1 e eles mesmos. A razão pela qual factoring é tão importante é que matemáticos e cientistas da computação não sabem como fatorar um número sem simplesmente tentar tudo o que é possível. combinacao. Isto é, primeiro tente dividir por 2, depois por 3, depois por 4, e assim por diante. Se você tentar Fator um número primo -- especialmente um muito grande--você terá que tentar (essencialmente) cada número possível entre 2 e esse grande número primo. Mesmo nos computadores mais rápidos, levará anos (mesmo séculos) para faturar os tipos de números primos usados na criptografia. É o fato de que não sabemos como eficientemente fatorar um grande número que dá algoritmos criptográficos forca. Se, um dia, alguém descobrir como fazê-lo, todos os algoritmos criptográficos que usamos atualmente tornar-se-ão obsoletos. Esta continua a ser uma área aberta de investigação.

Para ser um pouco mais concretas sobre como o RSA utiliza as propriedades dos números primos, o algoritmo RSA depende essencialmente Teorema de Euler, que afirma que, para relativamente primos os números "a" e "N", a^e é congruente a 1 módulo N, onde e é o Euler totient função de N.

Onde é que os primos entram nisso? Para calcular a função totiente de Euler de N de forma eficiente, é necessário conhecer a fatoração primária de N. No caso do algoritmo RSA., onde n = pq para alguns primos " p " e "q", então e = (p - 1) (q - 1) = N - p - q + 1. Mas sem saber p E q, A computação de e é muito difícil.

De forma mais abstracta, muitos protocolos crypotgraphic usam várias funções trapdoor , funções que são 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 números primos são absolutamente centrais para a teoria dos números.

Eu sugeriria o livro uma jornada Matemática no Código . O livro tem uma sensação agradável até a terra, o que é surpreendente, uma vez que é sobre criptografia. O livro resume a jornada de Sarah Flannery de aprender quebra-cabeças quando criança para criar o algoritmo Cayley-Purser (CP) aos 16 anos. Ele dá uma explicação incrivelmente detalhada de funções de um caminho, teoria dos números, e números primos e como eles se relacionam com a criptografia. O que torna este livro ainda mais específico para a sua pergunta é Sarah tentou implementar um novo algoritmo de chave pública usando matrix. foi muito mais rápido, então usando números primos, mas um buraco de loop foi encontrado que poderia explorá-lo. Acontece que o algoritmo dela era melhor usado como um mecanismo de encriptação privado. O livro é um grande Testamento para usar números primos para a criptografia como ele resistiu o teste do tempo e os desafios de indivíduos muito inteligentes.

Mais um recurso para ti. Segurança Agora! Episódio 30 (~30 minutos podcast, link é para a transcrição) fala sobre problemas de criptografia, e explica por que os primos são importantes.

Não sou um matemático ou enigmático, então aqui está uma observação externa em termos leigos (sem equações extravagantes, desculpe).

Todo este tópico está cheio de explicações sobre comoprimos são usados na criptografia, é difícil encontrar alguém neste tópico explicando de uma forma fácil Porque primos são usados ... provavelmente porque todos tomam esse conhecimento como garantido.

Só olhar para o problema a partir do exterior pode gerar uma reacção como; mas se eles usam as somas de dois primos, por que não criar uma lista de todas as somas possíveis quaisquer dois primos podem gerar?

Neste local há uma lista de 455,042,511 primes, onde estão os primes mais altos9,987,500,000 (10 dígitos).

O maior primo conhecido (a partir de fevereiro de 2015) é 2 para a potência de 257.885.161-1 {[5] } que é 17,425,170 dígitos.

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

Calcular grandes números primos em si é uma tarefa monumental, por isso calcular inversamente dois números primos que foram multiplicados entre si tanto criptógrafos como matemáticos diriam que é suficientemente difícil ... agora.

Algoritmos criptográficos geralmente dependem para a sua segurança em ter um "problema difícil". A maioria dos algoritmos modernos parecem usar o factoring de números muito grandes como seu problema difícil - se você multiplicar dois números grandes juntos, computando seus fatores é "difícil" (ou seja, demorado). Se esses dois números são números primos, então há apenas uma resposta, o que torna ainda mais difícil, e também garante que quando você encontrar a resposta, é a certa, não alguns outra resposta que dá o mesmo resultado.

Eu acho que o que é importante na criptografia não são números primos em si, mas é a dificuldade do problema da factorização Primária

Suponha que você tem um inteiro muito grande que é conhecido por ser produto de dois primos m E n, não é fácil encontrar o que são M E N. algoritmo como RSA depende deste fato.

A propósito, há um artigo publicado sobre algoritmo que pode "resolver" este problema de factorização primária em tempo aceitável usando computador quântico. Então algoritmos mais recentes em criptografia podem não confiar mais nesta "dificuldade" de fatoração primária quando o computador quântico chega à cidade:)

Porque os algoritmos de factorização aceleram consideravelmente com cada factor encontrado. Fazer ambas as chaves privadas primo garante que o primeiro fator encontrado também será o último. Idealmente, ambas as chaves privadas também serão quase iguais em valor, uma vez que apenas a força das matérias-chave mais fracas.

Os números primos são usados principalmente na criptografia, uma vez que consome bastante tempo para determinar se um dado número é ou não número primo. Para o hacker, se algum algoritmo levar muito tempo para quebrar o código, torna-se inútil para eles