Encontrar factores primos para grandes números utilizando CPUs especialmente diseñadas

Question

Tengo entendido que muchos algoritmos criptográficos de clave pública en estos días dependen de grandes números primos para componer las claves, y es la dificultad de factorizar el producto de dos primos lo que hace que el cifrado sea difícil de romper. También entiendo que una de las razones por las que factorizar números tan grandes es tan difícil, es que el gran tamaño de los números utilizados significa que ninguna CPU puede operar de manera eficiente en los números, ya que nuestras minúsculas CPU de 32 y 64 bits no son comparables Para 1024, 2048 o incluso 4096 números de bits. Se deben usar bibliotecas matemáticas especializadas de Big Integer para procesar esos números, y esas bibliotecas son intrínsecamente lentas, ya que una CPU solo puede contener (y procesar) trozos pequeños (como 32 o 64 bits) al mismo tiempo.

Entonces ...

¿Por qué no puede crear un chip personalizado altamente especializado con registros de 2048 bits y circuitos aritméticos gigantes, de la misma manera que escalamos de 8 a 16 a 32 a 64 bits de CPU, simplemente compile uno mucho más grande? ? Este chip no necesitaría la mayoría de los circuitos en las CPU convencionales, después de todo, no necesitaría manejar cosas como memoria virtual, multihilo o E / S. Ni siquiera tendría que ser un procesador de propósito general que admita instrucciones almacenadas. Solo lo mínimo para realizar los cálculos aritméticos necesarios en números gigantescos.

No sé mucho sobre el diseño de circuitos integrados, pero recuerdo haber aprendido cómo funcionan las puertas lógicas, cómo crear un medio sumador, un sumador completo, y luego unir un grupo de sumadores para hacer aritmética de múltiples bits. Sólo escala Mucho.

Ahora, estoy bastante seguro de que hay una muy buena razón (o 17) para que lo anterior no funcione (ya que, de lo contrario, una de las personas más inteligentes que yo ya lo habría hecho) pero estoy interesado al saber por qué no funcionará.

(Nota: es posible que esta pregunta necesite un poco de reparación, ya que aún no estoy seguro de si la pregunta tiene sentido)

Answer 1

Lo que dijo @cube, y el hecho de que una unidad de lógica aritmética gigante tomaría más tiempo para que las señales lógicas se estabilicen e incluiría otras complicaciones en el diseño digital. El diseño de la lógica digital incluye algo que se da por sentado en el software, a saber, que las señales a través de la lógica combinatoria toman un tiempo pequeño pero distinto de cero para propagarse y establecerse. Un multiplicador de 32x32 necesita ser diseñado cuidadosamente. Un multiplicador de 1024x1024 no solo tomaría una gran cantidad de recursos físicos en un chip, sino que también sería más lento que un multiplicador de 32x32 (aunque quizás más rápido que un multiplicador de 32x32 que computa todos los productos parciales necesarios para realizar una multiplicación de 1024x1024). Además, no solo el multiplicador es el cuello de botella: tienes vías de memoria. Tendría que pasar un montón de tiempo reuniendo los 1024 bits de un circuito de memoria de solo 32 bits de ancho, y almacenando los 2048 bits resultantes en el circuito de la memoria.

Es casi seguro que es mejor obtener un montón de " convencional " Sistemas de 32 bits o 64 bits que trabajan en paralelo: se obtiene la aceleración sin la complejidad del diseño del hardware.

editar: si alguien tiene acceso a ACM (yo no), quizás eche un vistazo a este documento para ver lo que dice.

Answer 2

Esto se debe a que esta aceleración sería solo en O (n), pero la complejidad de factorizar el número es algo así como O (2 ^ n) (con respecto al número de bits). Entonces, si hiciste este überprocessor y factorizaste los números 1000 veces más rápido, solo tendría que hacer que los números fueran 10 bits más grandes y volveríamos a empezar de nuevo.

Answer 3

Como se indicó anteriormente, el problema principal es simplemente la cantidad de posibilidades que tiene que recorrer para factorizar un número. Dicho esto, existen computadoras especializadas para hacer este tipo de cosas.

El progreso real para este tipo de criptografía son las mejoras en los algoritmos de factorización numérica. Actualmente, el algoritmo general más rápido conocido es el tamiz de campo de número general .

Históricamente, parece que somos capaces de factorizar números dos veces más grandes en cada década. Parte de eso es un hardware más rápido, y parte de él es simplemente una mejor comprensión de las matemáticas y cómo realizar la factorización.

Answer 4

No puedo comentar sobre la viabilidad de un enfoque exactamente como el que usted describió, pero la gente hace similares muy frecuentemente utilizando FPGA:

• Crack DES keys
• Conversaciones GSM de crack
• Tarjeta gráfica de código abierto

Answer 5

Shamir & amp; Tromer sugiere un enfoque similar, utilizando un tipo de grid computing :

  

Este artículo analiza un nuevo diseño para un hardware personalizado   implementación del paso de tamizado, que   reduce [el costo del tamizado, en relación con TWINKLE,] a aproximadamente $ 10M. El nuevo dispositivo,   llamado TWIRL, puede ser visto como una extensión de la   Dispositivo TWINKLE. Sin embargo, a diferencia de TWINKLE   No tiene componentes optoelectrónicos, y puede   De esta forma se fabricará utilizando la tecnología VLSI estándar.   en obleas de silicio. La idea subyacente es usar   una sola copia de la entrada para resolver muchos subproblemas   en paralelo. Dado que el almacenamiento de entrada domina el costo, si el   la sobrecarga de paralelización se mantiene baja entonces la resultante   Speedup se obtiene esencialmente de forma gratuita. De hecho, el   El principal desafío radica en lograr este paralelismo de manera eficiente y al mismo tiempo permitir un almacenamiento compacto de la entrada.   Abordar esto implica innumerables consideraciones, que van desde   De la teoría de los números a la tecnología VLSI.

Answer 6

¿Por qué no intentas construir una computadora uber-quantum y ejecutas algoritmo de Shor en ello?

  

" ... Si se construyera una computadora cuántica con un número suficiente de qubits, el algoritmo de Shor podría usarse para romper esquemas de criptografía de clave pública, como el esquema RSA ampliamente utilizado. RSA se basa en el supuesto de que factorizar grandes números es computacionalmente inviable. Hasta donde se sabe, esta suposición es válida para computadoras clásicas (no cuánticas); No se conoce ningún algoritmo clásico que pueda tener en cuenta el tiempo polinomial. Sin embargo, el algoritmo de Shor muestra que la factorización es eficiente en una computadora cuántica, por lo que una computadora cuántica suficientemente grande puede romper el RSA. ... " -Wikipedia