Concepto de tabla arco iris para números primos

Es poco probable. Los números primos involucrados son enormes , por lo que el espacio de teclas es masivo. El tamaño de la clave depende en gran medida, pero vamos a elegir números primos de 512 bits para un ejemplo de límite inferior.

La función de conteo primo nos da una estimación de cuántos números primos están por debajo de un número dado. Es difícil calcular con precisión, pero una estimación cercana se define como π(x) = x / ln(x) , donde ln es el logaritmo natural. Como tal, podemos calcular una estimación del número esperado de primos por debajo del valor más alto en un número de n -bit calculando π(2^n) . Si queremos excluir todos los números que no son exactamente n -bit, calculamos π(2^n) - π(2^(n-1)) . Esto no es técnicamente requerido , pero nos da un límite inferior agradable de cuántos primos grandes hay para ese tamaño de clave.

Para n = 512 , el número de primos necesarios para una lista exhaustiva es 1.885 × 10 ¹⁵¹ . Si podemos almacenar todos los primos en una entrada de 512 bits, eso es 1.207 × 10 ¹⁵³ bytes , que es 132 órdenes de magnitud más de lo que tenemos en el mundo con capacidad de almacenamiento en disco.

Así que no, no es realmente factible.

Tabla de arco iris: cada "color" toma una entrada aleatoria (el hash de salida de la última iteración o el hash original) y devuelve una salida que se asigna al patrón que quieras (por ejemplo, todas las letras). Luego se procesa y se devuelve a la entrada.

Como también podemos especificar una función de reducción que toma cualquier cadena aleatoria y la asigna de manera determinista al patrón de salida que queramos, esto funciona para las contraseñas. Sin embargo, no hay una función definible para tomar un valor de entrada y generar un número que se sepa que es primo como resultado.

Cada número que no se sabe que es primo porque ya lo has probado, tendrá que ser examinado para determinar si es primo. Por lo tanto, a menos que un número se almacene como un valor primordial conocido, no hay una relación de intercambio de tiempo / memoria.

Lo que estás hablando aquí no es factible. Crypto no se limita a calcular números primos grandes, debe factorizar el producto de dos números primos.

Lo que deberías hacer es calcular millones de números primos y colocarlos en una matriz increíblemente grande. Entonces necesitarías duplicar esa matriz para tener una matriz bidimensional. Entonces necesitaría multiplicar cada entrada en la primera dimensión contra cada entrada en la segunda dimensión, y almacenar los dos números primos y el resultado en una segunda matriz. Esta segunda matriz sería gigantesca, y por gigantesco quiero decir completamente incapaz de ser almacenada en cualquier capacidad, pero contendría sus respuestas.

Ciertamente no es fácil, pero ... "donde hay voluntad, hay una manera" SI quería todos los números primos del número 2 - > 512 bits en una tabla y luego todos los productos posibles, entonces sí, esto sería increíblemente grande. Pero volvamos atrás y especulemos por qué alguien podría quererlo. Supongamos que alguien tiene un escenario en el que estaban usando un par de números primos de longitud de bits similares para hacer un número grande que sería difícil para otros factorizar a un par de números primos (¿le suena familiar ...?) No todas las combinaciones posibles de se necesitarían números primos ya que solo se usarían longitudes de bit similares. Este dramáticamente reduce el tamaño de la tabla. De todos modos, para ser pedante, esta sería una tabla Cubo no del Arco iris, ya que requiere varias dimensiones. La capacidad de determinar las características de estos primos grandes es ciertamente difícil, ya que el tamaño de los cubos que residen en la memoria (cuando se mantienen en RAM para un análisis eficiente) es demasiado grande para una PC barata, sin embargo, hay algunas organizaciones grandes que tienen estructuras multidimensionales gigantes de este tipo de proporciones (como Google para sus búsquedas). Parece muy desagradable que no haya organizaciones con muchos recursos que ya hayan calculado y usado tales cubos principales. La dificultad de factorizar el par de números primos es la dificultad de "titular" para, por ejemplo, RSA, pero no subestime la dificultad adicional producida por el paso para generar la clave privada porque tiene un cálculo modular.

Como ya se mencionó anteriormente, no hay ningún lugar cerca del espacio de almacenamiento requerido en todo el mundo. Apuesto a que antes de que lleguemos a esa cantidad de almacenamiento, una computadora cuántica que ejecute el algoritmo de Shor (o un algoritmo similar) habrá anulado la necesidad.