Encontrar fatores principais para grandes números usando CPUs especialmente trabalhada

Question

O meu entendimento é que muitos algoritmos de criptografia de chave pública nos dias de hoje dependem de números primos grandes para compensar as chaves, e é a dificuldade de fatorar o produto de dois números primos que faz a criptografia difícil de quebrar. Ele também é o meu entendimento de que uma das razões que factoring tão grande número é tão difícil, é que o tamanho dos números meios utilizados que nenhum CPU pode operar eficientemente sobre os números, desde a nossa minúscula 32 e 64 CPUs bits não são páreo para 1024, 2048 ou mesmo 4096 bit números. bibliotecas matemáticas especializada inteiro grande deve ser utilizado para processar esses números, e essas bibliotecas são inerentemente lento desde a CPU só pode ter (e processo) pequenos pedaços (como 32 ou 64 bits) de uma vez.

Então ...

Por que você não pode construir um chip personalizado altamente especializados, com 2.048 registros de bits e circuitos aritméticos gigantes, muito da mesma maneira que nós escalado de 8 a 16 a 32 anos para CPUs de 64 bits, apenas construir uma muito maior ? Este chip não precisaria mais dos circuitos de CPUs convencionais, afinal ele não precisaria coisas punho como memória virtual, multithreading ou I / O. Ele nem sequer precisa ser um processador de propósito geral de apoio instruções armazenadas. Apenas o mínimo necessário para realizar os cálculos aritméticos necessários em números ginormous.

Eu não sei muita coisa sobre o projeto IC, mas eu me lembro de aprender sobre como portas lógicas de trabalho, como construir um somador parcial, somador completo, em seguida, unir um bando de víboras para fazer aritmética multi-bit. Apenas escalar. Um monte.

Agora, estou bastante certo de que há uma razão muito boa (ou 17) que o acima não vai funcionar (já que de outra forma uma das muitas pessoas mais inteligentes do que eu estou já teria feito isso), mas eu estou interessado em saber por não vai funcionar.

(Nota: Esta pergunta pode precisar de algum re-trabalho, como eu nem tenho certeza ainda se a pergunta faz sentido)

Answer 1

O que @cube disse, e o fato de que uma unidade lógica aritmética gigante levaria mais tempo para os sinais lógicos a se estabilizar, e incluem outras complicações em design digital. design de lógica digital inclui algo que você tomar para concedido em software, ou seja, que os sinais através de combinações lógica tomar um pequeno, mas diferente de zero tempo para se propagar e se estabelecer. A 32x32 multiplicador precisa ser projetado com cuidado. Um 1024x1024 multiplicador seria não só ter uma enorme quantidade de recursos físicos em um chip, mas também seria mais lento do que um multiplicador de 32x32 (embora talvez mais rápido do que um 32x32 multiplicador de computação todos os produtos parciais necessários para executar uma 1024x1024 multiplicar). Além disso, é não só o multiplicador que é o gargalo: você tem percursos de memória. Você teria que gastar um monte de tempo reunindo os 1024 bits a partir de um circuito de memória que é apenas 32 bits de largura, e armazenar os 2048 bits resultantes de volta para o circuito de memória.

Quase certamente é melhor ter um monte de sistemas "convencionais" de 32 bits ou de 64 bits trabalhando em paralelo:. Você começa a aceleração w / o da complexidade do projeto hardware

Editar: se alguém tem acesso ACM (eu não), talvez dar uma olhada em neste artigo para ver o que diz.

Answer 2

É porque essa aceleração seria apenas em O (n), mas a complexidade de factoring o número é algo como O (2 ^ n) (em relação ao número de bits). Então, se você fez esta überprocessor e fatorado os números 1000 vezes mais rápido, eu só teria que fazer os números 10 bits maiores e que estaria de volta no início novamente.

Answer 3

Como indicado acima, o principal problema é simplesmente quantas possibilidades você tem que percorrer para fator de um número. Dito isto, computadores especializados que existem para fazer esse tipo de coisa.

O verdadeiro progresso para esse tipo de criptografia é melhorias nos algoritmos número de factoring. Atualmente, o algoritmo geral mais rápido conhecido é o número geral campo peneira .

Historicamente, parece que estamos a ser capazes de números fator duas vezes maior a cada década. Parte do que é hardware mais rápido, e parte dela é simplesmente uma melhor compreensão da matemática e como realizar factoring.

Answer 4

Eu não posso comentar sobre o viabilidade de uma abordagem exatamente como o que você descreveu, mas as pessoas fazem semelhante coisas muito frequentemente utilizando FPGAs:

• chaves quebrar o DES
• conversas rachadura GSM
• Abrir cartão fonte gráficos

Answer 5

Shamir & Tromer sugerem uma abordagem semelhante, usando uma espécie de grade de computação :

Este artigo discute um novo design para um hardware personalizado implementação do passo de crivagem, que reduz [o custo de peneiramento, em relação a cintilação,] para cerca de US $ 10M. O novo dispositivo, chamado TWIRL, pode ser visto como uma extensão da CINTILAÇÃO dispositivo. No entanto, ao contrário TWINKLE-lo não tem componentes optoeletrônicos, e pode assim, ser fabricado usando a tecnologia padrão VLSI em bolachas de silício. A ideia subjacente é a de uso uma única cópia da entrada para resolver muitos subproblemas em paralelo. Dado que o custo domina armazenamento de entrada, se o paralelização sobrecarga é mantida baixa, em seguida, o resultante aceleração é obtida, essencialmente, para livre. Na verdade, a principais mentiras desafio para atingir esse paralelismo de forma eficiente, permitindo armazenamento compacto da entrada. Dirigindo-se isso envolve uma infinidade de considerações, variando da teoria dos números à tecnologia VLSI.

Answer 6

Por que você não tentar construir um computador uber-quantum e executar de Shor algoritmo sobre ele?

" ... Se um computador quântico com um número suficiente de qubits seriam construídas, algoritmo de Shor poderia ser usado para quebrar esquemas de criptografia de chave pública, tais como o esquema RSA amplamente utilizado. RSA . baseia-se no pressuposto de que fatorar números grandes é computacionalmente inviável tanto quanto se sabe, esta hipótese é válida para (não-quântica) computadores clássicos;. nenhum algoritmo clássico é sabido que fator pode em tempo polinomial no entanto, mostra o algoritmo de Shor que factoring é eficiente em um computador quântico, portanto, um suficientemente grande computador quântico pode quebrar RSA. ..." -Wikipedia