Por que são primos importante em criptografia?
https://stackoverflow.com/questions/439870
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Uma coisa que sempre me parece um não-criptógrafo: Por que é tão importante o uso de números primos? O que os torna tão especial em criptografia?
Alguém tem um simples breve explicação? (Estou ciente de que há muitos iniciadores e que Applied Cryptography é a Bíblia, mas como disse: Eu não estou olhando para implementar o meu próprio algoritmo de criptografia, e as coisas que eu achei só fez o meu cérebro explodir - há 10 páginas de fórmulas matemáticas por favor:))
Agradecimentos para todas as respostas. Eu aceitei o que fez o próprio conceito mais claro para mim.
Solução
A maioria explicação básica e geral: criptografia é tudo 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ê lidar com números primos muito na teoria dos números.
Mais especificamente, alguns algoritmos criptográficos importantes, como RSA dependem criticamente o fato de que nobre fatoração de números grandes leva muito tempo. Basicamente você tem uma "chave pública", que consiste de um produto de dois números primos grandes usados ??para criptografar uma mensagem, e uma "chave secreta" composta pelos dois primos usados ??para descriptografar a mensagem. Você pode fazer o público chave pública, e todos podem usá-lo para criptografar mensagens para você, mas só você sabe os fatores primos e pode decifrar as mensagens. Todo mundo teria que fator o número, o que leva muito tempo para ser prático, dado o estado atual da arte da teoria dos números.
Outras dicas
Simples? Yup.
Se você multiplicar dois números primos grandes, você recebe um grande número non-prime com apenas dois (grande) fatores primos.
Factoring esse número é uma operação não-trivial, e esse fato é a fonte de uma série de algoritmos criptográficos. Consulte one-way funções para mais informações.
Adenda: Apenas um pouco mais de 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. Qualquer operação feita com dados que só pode ser desfeita por conhecer um dos dois fatores será não-trivial para desencriptar.
Aqui está um exemplo muito simples e comum.
O RSA criptografia algoritmo que é comumente usado em sites de comércio seguro, é baseado no fato de que é fácil de tomar dois (muito grandes) números primos e multiplicá-los, ao mesmo tempo que é extremamente difícil de fazer o oposto - o que significa: ter um número muito grande, uma vez que ele tem apenas dois fatores primos, e encontrar -los.
É não tanto os próprios números primos, que são importantes, mas os algoritmos que trabalham 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 em que eles têm exatamente dois fatores:. 1 e si
O factoring razão é tão importante é matemáticos e cientistas da computação não sei como fator de um número sem simplesmente a tentar todas as combinações possíveis. Isto é, primeiro tente dividir por 2, em seguida, por 3, então por 4, e assim por diante. Se você tentar fator de um número primo - especialmente um muito grande - você tem que tentar (essencialmente) a cada número possível entre 2 e que grande número primo. Mesmo nos computadores mais rápidos, vai demorar anos (até mesmo séculos) para fator os tipos de números primos usados ??na criptografia.
É o fato de que nós não sabemos como fator de forma eficiente um grande número que dá algoritmos criptográficos sua força. Se, um dia, alguém descobrir como fazê-lo, todos os algoritmos criptográficos atualmente uso se tornará obsoleto. Esta continua a ser 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 de verificar se um conjunto de fatores primos se multiplicam a um certo número inteiro.
Há alguns bons recursos para incrementando em criptografia. Aqui está um:
A partir dessa página:
No-chave pública mais comumente usado sistema de criptografia, inventado por Ron Rivest, Adi Shamir e Len Adleman em 1977, tanto o público eo privado as teclas são derivadas a partir de um par de grande números primos de acordo com um relativamente simples matemática Fórmula. Em teoria, pode ser possível derivar a chave privada a partir da chave pública, trabalhando a para trás fórmula. Mas apenas o produto dos números primos grandes é públicas e factoring números de que tamanho em números primos é tão difícil que até mesmo a maioria dos supercomputadores poderosos o mundo não pode quebrar um ordinário chave pública.
O livro de Bruce Schneier Applied Cryptography é outra. Eu recomendo esse livro; É uma leitura divertida.
Para ser um pouco mais concreta sobre como RSA usa as propriedades dos números primos, o algoritmo RSA depende criticamente Euler Teorema do, que afirma que para números relativamente primos "a" e "N", a ^ e é congruente a 1 modulo N, onde e é o de Euler função totient de N.
Onde primos entram em que? Para calcular a função totient de Euler de N de forma eficiente exige saber a fatoração nobre 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, cálculo de e é muito difícil
Mais abstratamente, muitos protocolos crypotgraphic usar vários alçapão funções , funções que são fáceis de calcular, mas difícil de inverter. teoria dos números é uma fonte rica de tais funções alçapão (como multiplicação de grandes números primos), e os números primos são absolutamente central para a teoria dos números.
Gostaria de sugerir o livro A Mathematical Journey Código Em . O livro tem um bom para baixo a sensação terra, o que é surpreendente, uma vez que é sobre criptografia. O livro resume a jornada de Sarah Flannery de aprender puzzles como um filho para criar o algoritmo de Cayley-Purser (CP) com a idade de 16. Ele dá uma explicação incrivelmente detalhada das funções de uma maneira, teoria dos números, e números primos e como eles se relacionam com criptografia.
O que torna este livro ainda mais específico para sua pergunta é Sarah tentou implementar um novo algoritmo de chave pública usando da matriz. Foi muito mais rápido, em seguida, usando números primos, mas uma lacuna se que poderia explorá-la. Acontece que seu algoritmo foi melhor usado como um mecanismo de criptografia privada. O livro é um grande testemunho de usar números primos para criptografia, uma vez que tem resistido ao teste do tempo e os desafios de indivíduos muito inteligentes.
Mais um recurso para você. Segurança Now! episódio 30 (~ 30 minutos podcast, link é para a transcrição) fala sobre questões de criptografia, e explica por que primos são importantes.
Eu não sou um matemático ou cryptician, então aqui está uma observação no exterior em termos leigos (sem equações fantasia, sorry).
Todo este segmento está cheio de explicações sobre Como números primos são usados ??em criptografia, é difícil encontrar alguém nesta discussão explicando de uma forma fácil Por números primos são usados. .. provavelmente porque todo mundo tem esse conhecimento para concedido.
Apenas olhando para o problema do lado de fora pode gerar uma reação semelhante; mas se eles usam as somas de dois primos, porque não criar uma lista de todas as somas possíveis quaisquer dois primos pode gerar?
Neste site há uma lista de 455042511 números primos, onde o maiores números primos é 9987500000 ( 10 dígitos).
O maior conhecido prime (a partir de fevereiro 2015) é 2 ao poder do 257885161 - 1 que é 17425170 dígitos
Isto significa que não há nenhum ponto. manter uma lista de todos os números primos conhecidos e muito menos todos os seus possíveis somas. É mais fácil pegar um número e verificar se ele é um primo.
Cálculo grandes números primos em si é uma tarefa monumental, tão cálculo reverter dois primos que tem sido multiplicados uns com os outros dois criptógrafos e matemáticos diria é com força suficiente .. . hoje.
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, calculando seus fatores é "difícil" (ou seja demorado). Se esses dois números são números primos, então não há apenas uma resposta, o que torna ainda mais difícil, e também garante que quando você encontrar a resposta, é o caminho certo, não alguma outra resposta que só acontece para dar o mesmo resultado.
Eu acho que são importantes em criptografia não são primos em si, mas é o dificuldade de problema fatoração nobre
Suponha que você tenha muito, muito grande inteiro, que é conhecido por ser produto de dois números 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 publicada papel no algoritmo que pode "resolver "este problema fatoração privilegiada em tempo aceitável usando o computador quântico. Então, algoritmos mais recentes em criptografia não pode invocar esta "dificuldade" de primeiro-factorização mais quando computador quântico chega à cidade:)
Porque algoritmos de fatoração acelerar consideravelmente com cada fator encontrados. Fazendo ambos chaves privadas garante principais o primeiro fator encontrados também será a última. Idealmente, as duas chaves privadas também serão quase iguais em valor uma vez que apenas a força das questões fundamentais mais fracos.
Os números primos são usados ??principalmente em criptografia, uma vez que 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 torna-se inútil para eles
