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

Question

Mi entendimiento es que muchos algoritmos criptográficos de clave pública actualmente dependen de números primos grandes para componer las claves, y es la dificultad al factorizar el producto de dos primos lo que hace la encriptación es difícil de romper. También tengo entendido que una de las razones por las que factorizar números tan grandes es tan difícil es que el tamaño total de los números utilizados significa que ninguna CPU puede operar eficientemente los números, ya que nuestras minúsculas CPU de 32 y 64 bits no son compatibles. para números de 1024, 2048 o incluso 4096 bits. Se deben utilizar las bibliotecas matemáticas especializadas Big Integer para procesar esos números, y esas bibliotecas son inherentemente lentas, ya que una CPU solo puede contener (y procesar) fragmentos pequeños (como 32 o 64 bits) a la vez.

Entonces ...

¿Por qué no se puede construir un chip a medida altamente especializado, con registros de 2048 bits, y los circuitos aritméticos gigantes, gran parte de la misma manera que escalamos de 8 a 16 a 32 a 64- bit CPUs, ¿solo construye 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 necesitaría ser un procesador de uso general que admita instrucciones almacenadas. El mínimo indispensable para realizar los cálculos aritméticos necesarios en números descomunales.

No sé mucho sobre el diseño de circuitos integrados, pero recuerdo haber aprendido cómo funcionan las compuertas lógicas, cómo crear un medio sumador, un sumador completo, luego unir un conjunto de sumadores para hacer aritmética de múltiples bits . Solo escalar. 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 muchas personas más inteligentes que yo ya lo habría hecho) pero estoy interesado en saber por qué no va a funcionar.

(Nota: Esta pregunta puede necesitar algo de re-trabajo, ya que no estoy siquiera seguro todavía si la pregunta tiene sentido)

Answer 1

Lo que dijo @cube, y el hecho de que una unidad lógica aritmética gigante tomaría más tiempo para estabilizar las señales lógicas e incluye otras complicaciones en el diseño digital. El diseño de lógica digital incluye algo que se da por sentado en el software, es decir, que las señales a través de la lógica combinacional tardan un tiempo pequeño pero distinto de cero en 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 tal vez más rápido que un multiplicador de 32x32 que computa todos los productos parciales necesarios para multiplicar 1024x1024). Además, no es solo el multiplicador 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 memoria.

Casi con certeza, es mejor tener un conjunto de sistemas "convencionales" de 32 bits o de 64 bits trabajando en paralelo: obtienes la aceleración sin la complejidad del diseño del hardware.

editar: si alguien tiene acceso ACM (yo no), tal vez eche un vistazo a this paper para ver lo que dice.

Answer 2

Su porque este aumento de velocidad sería sólo 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 hicieras este überprocessor y factorizases los números 1000 veces más rápido, solo tendría que hacer los números 10 bits más grandes y estaríamos de nuevo en el comienzo.

Answer 3

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

El verdadero progreso para este tipo de criptografía es la mejora en los algoritmos de factorización de números. Actualmente, el algoritmo general más rápido conocido es el general number field sieve.

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

Answer 4

que no puedo comentar sobre la viabilidad de un enfoque exactamente como el que usted describe, pero la gente similares cosas con mucha frecuencia utilizando FPGAs:

• Crack DES keys
• Crack GSM conversations
• Open source graphics card

Answer 5

Why don ' ¿Intentas construir una computadora súper cuántica y ejecutar Shor's algorithm en ella?

" ... Si un ordenador cuántico con un número suficiente de qubits iban a ser construidas, el algoritmo de Shor podría ser utilizado para romper los esquemas de criptografía de clave pública, tales como el esquema RSA ampliamente utilizado. RSA se basa en la suposición de que factorizar grandes números es computacionalmente inviable. Hasta donde se conoce, esta suposición es válida para computadoras clásicas (no cuánticas), no se conoce ningún algoritmo clásico que pueda factorizar 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 RSA ... "-Wikipedia

Answer 6

Shamir & Tromer sugieren un enfoque similar, utilizando un tipo de grid computing:

Este artículo discute un nuevo diseño para una implementación hardware personalizado de la etapa de tamizado, que reduce [el costo de tamizado, relativa a TWINKLE,] a alrededor de $ 10M. El nuevo dispositivo, llamado TWIRL, puede verse como una extensión del dispositivo TWINKLE . Sin embargo, a diferencia de TWINKLE, no tiene componentes optoelectrónicos, y puede fabricarse utilizando la tecnología estándar VLSI 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 la sobrecarga de paralelización se mantiene baja, la aceleración resultante se obtiene esencialmente de forma gratuita. De hecho, el desafío principal de radica en lograr este paralelismo de manera eficiente a la vez que permite un almacenamiento compacto de la entrada. Abordar esto implica una miríada de consideraciones, que van desde desde la teoría de los números hasta la tecnología VLSI.