Porque é que os primos são importantes na criptografia?
Obrigado por todas as respostas. Aceitei aquele que deixou o conceito mais claro para mim.
14 answers
Explicação mais básica e geral: a criptografia é toda sobre teoria dos números, e todos os números inteiros (exceto 0 e 1) são compostos de números primos, então 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 factorização primo de números grandes leva muito tempo. Basicamente você tem uma "chave pública" consistindo de um produto de dois primos grandes usados para criptografar uma mensagem, e uma" chave secreta " consistindo desses dois primos usados para descriptografar a mensagem. Você pode tornar a chave pública pública pública pública, e todos podem usá-la para criptografar mensagens para você, mas só você conhece os fatores primos e pode decifrar as mensagens. Todos os outros teriam de ter em conta o número, que demora demasiado tempo a ser prático, dado o estado actual da técnica da teoria dos números.
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.
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.
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.
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.
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?
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:)
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