it-swarm-eu.dev

Einen linearen Kongruenzgenerator knacken

Ich habe mir kürzlich den Security Now Podcast angehört und sie haben nebenbei erwähnt, dass der lineare Kongrunentialgenerator (LCG) trivial zu knacken ist. Ich benutze die LCG in einem Statistikkurs für das erste Jahr und dachte, dass das Knacken ein schönes "zusätzliches" Problem darstellen würde.

Gibt es nette Möglichkeiten, die LCG zu knacken, die keine rohe Gewalt beinhalten?


Ich bin mir nicht sicher, ob diese Frage OT ist, aber ich war mir nicht sicher, wo ich die Frage sonst posten sollte. Außerdem sind meine Tags nicht sehr hilfreich, da ich nicht genügend Mitarbeiter habe, um neue Tags zu erstellen.

34
csgillespie

Ja. Es gibt äußerst effiziente Möglichkeiten, einen linearen Kongruenzgenerator zu brechen.

Ein linearer Kongruenzgenerator ist definiert durch sn + 1 = a sn + b mod m, wobei m der Modul ist. In seiner einfachsten Form gibt der Generator nur s ausn als die npseudozufallszahl. Wenn dem Angreifer m bekannt ist und a, b nicht bekannt sind, hat Thomas beschrieben, wie man es bricht.

Wenn keiner von a, b, m bekannt ist, kann man einen linearen Kongruenzgenerator immer noch brechen, indem man zuerst wiederherstellt m. Es ist eine interessante Übung, abzuleiten, wie dies effizient funktioniert. es kann getan werden. Ich werde unten zeigen, wie; Lesen Sie nicht weiter, wenn Sie es lieber selbst herausfinden möchten.

Um m wiederherzustellen, definieren Sie tn = sn + 1 - sn und un = |tn + 2 tn - t2n + 1|; dann haben Sie mit hoher Wahrscheinlichkeit m = gcd (u1u2, ..., u10). 10 hier ist willkürlich; Wenn Sie es schaffen k, ist die Wahrscheinlichkeit, dass dies fehlschlägt, in k exponentiell gering. Ich kann einen Hinweis darauf geben, warum dies funktioniert, wenn jemand interessiert ist.

Die wichtige Lehre ist, dass der lineare Kongruenzgenerator unwiderruflich unsicher und für die kryptografische Verwendung völlig ungeeignet ist.


Hinzugefügt: @AviD wird mich noch mehr hassen :), aber hier ist die Mathematik, warum dies funktioniert, für diejenigen, die es angefordert haben.

Die Schlüsselidee: tn + 1 = sn + 1 - sn = (a sn - b) - (a sn-1 - b) = a sn - wien-1 = a tn mod m und tn + 2 = a2 tn mod m und tn + 3 = a3 tn mod m. Deshalb tn + 2 tn - tn + 12 = 0 mod m, D. H. |tn + 2 tn - tn + 12| ist ein zufälliges Vielfaches von m. Tatsache der Nifty-Number-Theorie: Der gcd von zwei zufälligen Vielfachen von m wird m mit einer Wahrscheinlichkeit von 6/π sein2 = 0,61; und wenn Sie den gcd von k von ihnen nehmen, kommt diese Wahrscheinlichkeit sehr nahe an 1 (exponentiell schnell in k). Ist das cool oder was?

36
D.W.

Ein linearer Kongruenzgenerator ist linear, was alles sagen sollte.

Sie haben nämlich einen Zustand s, der aktualisiert wird mit: s ← als + b mod w, für zwei Konstanten a und b und ein geeigneter Modul w (typischerweise 232: s, a und b sind 32-Bit-Wörter); Die Ausgabe besteht aus den aufeinanderfolgenden Werten von s. Wenn Sie drei aufeinanderfolgende Ausgänge haben (s, s1 und s2), dann erhalten Sie zwei lineare Gleichungen in zwei Unbekannten (a und b), die mit elementarer Arithmetik leicht gelöst werden können.

Dies kann auf Varianten erweitert werden, bei denen Sie nur Teile der Werte s erhalten, möglicherweise nicht aufeinanderfolgend. Wenn a und b zwei 32-Bit-Konstanten sind, benötigen Sie nur eine Ausgabe im Wert von etwa 96 Bit, um die Konstanten neu zu berechnen.

18
Thomas Pornin

Eine andere Methode zum Lösen nach m ergibt sich aus diesem Papier .

Im Wesentlichen nutzt diese Methode die Tatsache, dass der lineare Kongruenzgenerator den Ebenentest dramatisch nicht besteht. Die Determinante einer 3x3-Matrix mit 4 Ausgängen ist ein Vielfaches von m .

Die gcd von zwei Vielfachen ( n_1 und n_2 von m ist m wenn x_1 = n_1 / m und x_2 = n_2 / m sind Co-Prime.

Die Wahrscheinlichkeit, dass k ganze Zahlen Co-Primzahlen sind, ist gegeben durch 1/ζ (k), also die Wahrscheinlichkeit, dass x_1 und x_2 sind Co-Prime ist 1/ζ (2) oder 6/π ^ 2, ungefähr 61%.

Wie @Thomas sagte, sobald m gefunden ist, ist der Rest des Problems einfach.

3
Jon Takagi