cryptography - Tablas de arcoiris como una solución para factorizar grandes y primos

public-key-encryption rainbowtable (3)

En las explicaciones que he leído sobre la criptografía de clave pública, se dice que se obtiene un gran número multiplicando 2 primos extremadamente grandes. Como factorizar el producto de primos grandes es casi imposible de usar, usted tiene seguridad.

Esto parece un problema que podría resolverse trivialmente con tablas rainbow. Si conoce el tamaño aproximado de los primos utilizados y sabe que hay 2 de ellos, puede construir rápidamente una tabla de arco iris. Sería una gran mesa poderosa, pero podría hacerse y la tarea podría paralelizarse en todo el hardware.

¿Por qué las tablas del arco iris no son una forma efectiva de vencer la clave pública de criptografía basada en la multiplicación de números primos grandes?

Descargo de responsabilidad: obviamente, decenas de miles de personas preocupadas por la seguridad, locos e inteligentes, no olvidaron durante décadas lo que pensé en una tarde. Supongo que estoy malinterpretando esto porque estaba leyendo explicaciones simplificadas para el público (por ejemplo: si se usan más de 2 números) pero aún no sé lo suficiente para saber dónde está mi brecha de conocimiento.

Editar: Sé que "tabla de arco iris" se refiere al uso de hashes precalculados en una tabla de búsqueda, pero lo anterior suena como un ataque de tabla arcoiris, así que estoy usando el término aquí.

Edición 2: Como se indica en las respuestas, no hay forma de almacenar solo todos los números primos, mucho menos todos sus productos.

Este sitio dice que existen muchos primos de 512 bits: ((2 ^ 511) * 1) / (512 log (2)) = 4.35 × 10 ¹⁵¹
La masa del sol es de 2 × 10 ³⁰ kg o 2 × 10 ³³ g
Eso es 2.17 × 10 ¹²⁴ primos por gramo de sol.
Qty. de números de 512 bits que pueden caber en un kilobyte: 1 kb = 1024 bytes = 8192 bits / 512 = 16
Eso puede caber en un terabyte: 16 * 1024 * 1024 * 1024 = 1.72 × 10 ¹⁰
Petabyte: 16 * 1024 * 1024 * 1024 * 1024 = 1,72 × 10 ¹³
Exabyte: 16 * 1024 * 1024 * 1024 * 1024 * 1024 = 1.72 × 10 ¹⁶

Incluso si 1 exabyte pesó 1 gramo, no estamos cerca de alcanzar los 2.17 × 10 ¹²⁴ necesarios para poder colocar todos estos números en un disco duro con la masa del sol

Creo que el principal problema es que las tablas rainbow pregeneradas para ciertos algoritmos usan un rango bastante "pequeño" (generalmente algo en el rango de 128 bits). Esto generalmente no cubre todo el rango, pero acelera el proceso de fuerza bruta. Usualmente consumen algo de TB de espacio.

En la factorización prima, los primos son mucho más grandes (para RSA seguro, se recomiendan 2048 bits). Por lo tanto, las tablas del arcoíris no serían "poderosas", pero serían imposibles de almacenar en cualquier lugar (usando hasta millones de TB de espacio).

Además, las tablas de arcoiris utilizan cadenas de hash aceleran aún más el proceso ( Wikipedia tiene una buena explicación) que no se puede utilizar para primos.

De uno de mis libros favoritos, Applied Cryptography de Bruce Schneier

"Si alguien creó una base de datos de todos los números primos, ¿no podrá usar esa base de datos para romper los algoritmos de clave pública? Sí, pero no puede hacerlo. Si pudiera almacenar un gigabyte de información en una unidad que pesa un gramo, entonces una lista de solo los números primos de 512 bits pesaría tanto que excedería el límite de Chandrasekhar y colapsaría en un agujero negro ... por lo que no podrías recuperar los datos de todos modos "

En otras palabras, es imposible o inviable, o ambos.

Los números primos utilizados en RSA y Diffie-Hellman son típicamente del orden de 2 ⁵¹² . En comparación, solo hay alrededor de 2 ²⁵⁶ átomos en el universo conocido. Eso significa que 2 ⁵¹² es lo suficientemente grande como para asignar 2 ²⁵⁶ números únicos a cada átomo en el universo.

Simplemente no hay forma de almacenar / calcular esa cantidad de datos.

Como un aparte, supongo que te refieres a "una gran tabla de primos": las tablas del arco iris están diseñadas específicamente para hashes, y no tienen ningún significado real aquí.