cryptography - una - Algoritmos RSA y generador primario
que puedo conectar a un generador de 800w (5)
De acuerdo, mi comprensión del funcionamiento matemático de RSA puede no ser tan profunda como debería, así que no dudes en abofetearme si esto es estúpido:
Para generar una clave privada, necesitamos dos primos grandes aleatorios. No existe un algoritmo que pueda hacer eso de manera precisa y eficiente, pero existen algoritmos que pueden generar números grandes que tienen un 99.99999 ... (un bazillion de 9s) ... 999% de probabilidad de ser primos.
Mi pregunta es: ¿qué sucede si, por un golpe fenomenal de mala suerte, cuando generabas tu clave, el algoritmo de generación principal generaba un no primo? ¿Cómo afecta eso al software que usa esa clave desafortunada?
EDITAR: Sé que otros factores son fuentes mucho más probables de malos resultados en este asunto; esto es pura curiosidad nerdy matemática.
Hay un algoritmo simple para factorizar un gran compuesto - (como siempre se ha sospechado). Esto es conocido por EE. UU. Y sus aliados desde 1989. También identifica primos fácilmente.
También RSA está al tanto.
He aprendido que puedes usar rsa como esto:
p = prime q = prime n = p * q phi(n) = phi(p) * phi(q) = p-1 * q-1
Pero he oído que si haces phi de un no primo no es primo -1 por lo que se bloqueará en el paso anterior (pero no puedo decir por qué)
Lo notará de inmediato: la clave secreta será incorrecta.
Si p o q es compuesto, usted elige la clave pública (típicamente 65537) calcula su clave secreta usando el algoritmo euclidiano extendido: 65537 * x mod n = 1. (donde n = (p-1) * (q-1))
Pero usando la clave secreta x descifrar (encriptar (m))! = M En fórmula: (m ^ 65537) ^ x mod n! = M
Si tienes primos verdaderos, entonces no hay atajos sino fuerza bruta. Si no estás 100% seguro, el atacante tampoco lo hará. Además, puede tener suficiente confianza con los algoritmos de prueba de número primo, que el riesgo de tener un nunber no principal es menor que 1 en todo el espacio clave. Básicamente usted puede, estadísticamente, estar seguro de que su número es primordial. En otras palabras, las probabilidades de adivinar que no es un primo deberían ser mayores que adivinar la clave correcta. Simplemente requiere algo de paciencia en el momento clave de generación.
1. En pruebas probabilísticas de primalidad
Una computadora es un sistema confiable y determinista: para la misma entrada, ejecutará el mismo algoritmo para la misma salida. ¿Siempre hará eso? Casi . Existe algo así como partículas de alta energía vagando por el universo, generalmente conocidas como rayos cósmicos . Cuando una partícula de este tipo golpea un transistor escondido en lo profundo de una CPU, puede causarle hipo: básicamente alterar su voltaje de salida, de manera muy transitoria, de modo que para un ciclo de reloj, el bit que representa la salida del transistor se invierte.
Ahora considere alguna computadora que ejecute un algoritmo de generador principal, que crea números aleatorios y los prueba para la primalidad. La prueba de primalidad es una función que devuelve un valor booleano. En algún punto, el resultado (el booleano que es true para "primo", false para no primo) es un valor constante copiado en un registro. Entonces, hay una ventana de unos pocos ciclos de reloj durante los cuales ese resultado es un bit único, contenido en una estructura flip-flop (que consiste en 6 transistores).
¿Cuál es entonces la probabilidad de que un rayo cósmico voltee ese bit crítico justo en el ciclo de reloj "correcto", haciendo que el programa considere que un no primo es realmente primo? Esa probabilidad es muy baja. Como dije, las computadoras son sistemas confiables. Sin embargo, esa probabilidad puede ser aproximadamente estimada. Generalmente se considera que una CPU determinada experimenta un cambio de bit de rayos cósmicos una vez cada tres meses. Un procesador Core2 Duo contiene aproximadamente 291 millones de transistores y funciona a (por ejemplo) 2.4 GHz. Si hay un solo transistor "crítico", y ese transistor es crítico para un solo ciclo de reloj, entonces la probabilidad de que el rayo cósmico cambie a un no primo en un primo aparente es aproximadamente 1.8 * 10 -24 . Este es un límite inferior muy optimista; en la práctica, muchos transitores podrían voltearse e implicar la falla de la prueba de primalidad, y la temporización objetivo abarca varios ciclos, y un generador principal examinará varias docenas de no primos para cada generación principal. Pero consideremos que tenemos suerte.
La probabilidad de 1.8 * 10 -24 afecta a cada prueba de primalidad, independientemente de si es determinista o no.
Un generador principal habitual ejecutará una prueba de Miller-Rabin con una "certeza" de 2 -100 (la prueba se ejecuta 50 veces y tiene una probabilidad de no más de 0,25 de perder un no primo cada vez). El "100" es arbitrario pero común. Esa probabilidad es un poco menor a 10 -30 . Así que ahí lo tiene: la probabilidad de que una prueba de Miller-Rabin declare el primo como no primo es menos de una millonésima parte de la probabilidad de que un rayo cósmico golpee un transistor y haga que la aplicación asuma que un número es primo mientras que el Miller- La prueba de Rabin dijo que no fue así.
En palabras más cortas, si obtiene un generador no principal de un generador de números primos, esto se debe a un problema de hardware como un rayo cósmico, no a la naturaleza probabilística de la prueba de primalidad.
Tener una mala prima debido a un rayo cósmico es en realidad un golpe de muy buena suerte. La probabilidad de que un asteroide que se precipita a través del espacio finalmente caiga sobre tu casa y te incinere durante el primer segundo después del cual generó tu llave es mucho más alta. No sé ustedes, pero personalmente prefiero tener una mala clave RSA que ser aplastado por una roca que cae.
2. Una mala clave
Si usa un no primo en una clave RSA, entonces obtiene una mala clave. Una clave incorrecta generará malas firmas: el generador de firmas producirá una secuencia de bytes de la longitud correcta, pero el verificador de firma declarará la firma inválida. Nota: en realidad, la firma puede ser válida, con una pequeña probabilidad. Usar los "primos" pyq en RSA es similar a una prueba de primalidad probabilística, al igual que una prueba de Miller-Rabin. Es probable, sin embargo, que pronto se descubra que la llave se comporte mal. Se observará un comportamiento similar para el cifrado asimétrico.
Se notará que producir una mala firma, o no descifrar un mensaje encriptado RSA, también puede ocurrir debido a otro rayo cósmico, o incluso a la ocurrencia mucho más mundana de mala memoria RAM.
En pocas palabras, si te preocupa tener una clave RSA mala pero no sobre el evento mucho más probable de una falla de hardware (que es inevitable debido a los rayos cósmicos, pero afortunadamente no es muy común), entonces estás equivocando tus prioridades.