Rompiendo un generador lineal congruente

Sí. Hay formas extremadamente eficientes de romper un generador lineal congruente.

s _{n + 1} = as _n + b mod m define un generador lineal congruente. donde m es el módulo. En su forma más simple, el generador simplemente genera s_n como el n th número pseudoaleatorio. Si el atacante conoce m y a , b no se conoce, Thomas describió cómo romperlo.

Si no se conoce ninguno de a , b , m , aún se puede romper un generador lineal congruente, recuperando primero m . Es un ejercicio interesante derivar cómo hacerlo de manera eficiente; se puede hacer. Voy a mostrar cómo a continuación; no siga leyendo si prefiere intentar resolverlo por sí mismo.

  

Para recuperar m , defina t _n = s _{n + 1} - s _n y u_n = | t _{n + 2} t _n - t ² _{n + 1} |; luego con alta probabilidad tendrá m = gcd ( u ₁ , u ₂ , ..., u ₁₀ ). 10 aquí es arbitrario; si lo hace k , entonces la probabilidad de que esto falle es exponencialmente pequeña en k . Puedo compartir un indicador de por qué esto funciona, si alguien está interesado.

La lección importante es que el generador lineal congruente es irremisiblemente inseguro y completamente inadecuado para uso criptográfico .

Añadido: @AviD me odiará aún más :), pero aquí están los cálculos de por qué esto funciona, para aquellos que lo solicitaron.

  

La idea clave: t _{n + 1} = s _{n + 1} - s _n = (como _n - b) - (como _n-1 - b) = como _n - como _n-1 = en _n mod m , y t _{n + 2} = a ² t _n mod m , y t _{n + 3} = a ³ t _n mod m . Por lo tanto, t _{n + 2} t _n - t _{n + 1} ² = 0 mod m , es decir, | t _{n + 2} t _n - t _{n + 1} ² | es un múltiplo aleatorio de m. Hecho de la teoría numérica ingeniosa: el gcd de dos múltiplos aleatorios de m será m con probabilidad 6 / π ² = 0.61; y si tomas el gcd de k de ellos, esta probabilidad se acerca mucho a 1 (exponencialmente rápido en k). ¿Eso es genial, o qué?

Un generador lineal congruente es lineal , que debería decirlo todo.

Es decir, tiene un estado s , que se actualiza con: s ← as + b mod w , para dos constantes a y b , y un módulo conveniente w (generalmente 2³² : s , a y b son palabras de 32 bits); la salida consiste en los valores sucesivos de s . Si tiene tres salidas sucesivas ( s ₀ , s₁ y s ₂ ), luego obtienes dos ecuaciones lineales en dos incógnitas ( a y b ), que se resuelven fácilmente con aritmética elemental.

Esto se puede extender a las variantes en las que solo obtiene partes de los valores s , posiblemente no consecutivos. Si a y b son dos constantes de 32 bits, solo necesitas una salida de aproximadamente 96 bits para volver a calcular las constantes.

Otro

Otro método para resolver m proviene de este documento .

Esencialmente, este método explota el hecho de que el generador lineal congruente falla dramáticamente la prueba de planos. El determinante de una matriz de 3x3 con 4 salidas es un múltiplo de m .

El gcd de dos múltiplos ( n_1 y n_2 de m es m si x_1 = n_1 / m y x_2 = n_2 / m son co -prime.

La probabilidad de que k enteros sean co-prime viene dada por 1 / ζ (k), por lo que la probabilidad de que x_1 y x_2 sean co-prime es 1 / ζ (2) o 6 / π ^ 2, aproximadamente el 61%.

Como dijo @Thomas, una vez que se encuentra m , el resto del problema es fácil.