Craccare un generatore congruenziale lineare

Sì. Esistono modi estremamente efficienti per rompere un generatore congruenziale lineare.

Un generatore congruenziale lineare è definito da s _{n + 1} = come _n + b mod m , dove m è il modulo. Nella sua forma più semplice, il generatore emette solo s _n come n th numero pseudocasuale. Se m è noto all'attaccante e a , b non sono noti, Thomas ha descritto come suddividerlo.

Se nessuno di a , b , m è noto, si può ancora rompere un generatore congruenziale lineare, recuperando prima m . È un esercizio interessante dedurre come farlo in modo efficiente; si può fare. Mostrerò come sotto; non continuare a leggere se preferisci provare a capirlo da solo.

To recover m, define t_n = s_n+1 - s_n and u_n = |t_n+2 t_n - t²_n+1|; then with high probability you will have m = gcd(u₁, u₂, ..., u₁₀). 10 here is arbitrary; if you make it k, then the probability that this fails is exponentially small in k. I can share a pointer to why this works, if anyone is interested.

L'importante lezione è che il generatore di congruenza lineare è irrecentemente insicuro e completamente inadatto per l'uso crittografico .

Aggiunto: @AviD mi odierà ancora di più :), ma ecco la matematica del perché questo funziona, per chi lo ha richiesto.

The key idea: t_n+1 = s_n+1 - s_n = (a s_n - b) - (a s_n-1 - b) = a s_n - a s_n-1 = a t_n mod m, and t_n+2 = a² t_n mod m, and t_n+3 = a³ t_n mod m. Therefore t_n+2 t_n - t_n+1² = 0 mod m, i.e., |t_n+2 t_n - t_n+1²| is a random multiple of m. Nifty number theory fact: the gcd of two random multiples of m will be m with probability 6/π² = 0.61; and if you take the gcd of k of them, this probability gets very close to 1 (exponentially fast in k). Is that cool, or what?

Un generatore congruenziale lineare è lineare , che dovrebbe dire tutto.

Vale a dire, hai uno s , che viene aggiornato con: s ← come + b mod w , per due costanti a e b e un modulo w (in genere 2 ³² : s , a e b sono parole a 32 bit); l'output consiste nei valori successivi di s . Se hai tre output successivi ( s ₀ , s ₁ e s ₂ ), quindi ottieni due equazioni lineari in due incognite ( a e b ), che sono facilmente risolte con l'aritmetica elementare.

Questo può essere esteso alle varianti in cui si ottengono solo parti dei valori s , possibilmente non consecutivi. Se a e b sono due costanti a 32 bit, sono necessari solo circa 96 bit di output per ricalcolare le costanti.

Un altro metodo per risolvere m deriva da questo articolo .

Essenzialmente, questo metodo sfrutta il fatto che il generatore lineare congruativo fallisce drammaticamente nel test degli aerei. Il determinante di una matrice 3x3 usando 4 uscite è un multiplo di m .

Il gcd di due multipli ( n_1 e n_2 di m è m se x_1 = n_1 / m e x_2 = n_2 / m sono co -prime.

La probabilità che k interi siano co-prime è data da 1 / ζ (k) quindi la probabilità che x_1 e x_2 siano co-prime è 1 / ζ (2) o 6 / π ^ 2, circa il 61%.

Come ha detto @Thomas, una volta trovato m il resto del problema è facile.