Blum Blum Shub (B.B.S). ist ein Pseudozufallszahlengenerator vorgeschlagen 1986 von Lenore Blum, Manuel Blum und Michael Shub (Blum u. a. 1986).

Blum Blum Shub nimmt die Form an:

wo M=pq das Produkt von zwei großer Blüte p und q ist. An jedem Schritt des Algorithmus wird eine Produktion aus x abgeleitet; die Produktion ist allgemein entweder die Bitparität von x oder ein oder mehr von den am wenigsten bedeutenden Bit von x

Der Samen x sollte eine ganze Zahl sein es ist co-prime zur M (d. h. p, und q sind nicht Faktoren von x), und nicht 1 oder 0.

Die zwei Blüte, p und q, sollte beide zu 3 (mod 4) kongruent sein (das versichert, dass jeder quadratische Rückstand eine Quadratwurzel hat, die auch ein quadratischer Rückstand ist) und gcd (φ (p-1), φ (q-1)) klein sein sollte (das macht die Zyklus-Länge groß).

Eine interessante Eigenschaft des Generators von Blum Blum Shub ist die Möglichkeit, jeden X-Wert direkt (über den Lehrsatz von Euler) zu berechnen:

wo die Funktion von Carmichael ist. (Hier haben wir).

Sicherheit

Der Generator ist für den Gebrauch in Simulationen nur für die Geheimschrift nicht passend, weil es sehr langsam ist. Jedoch gibt es einen Beweis, der seine Sicherheit auf die rechenbetonte Schwierigkeit des Quadratischen residuosity Problems reduziert. Da die einzige bekannte Weise, dieses Problem zu beheben, Factoring das Modul verlangt, wird die Schwierigkeit der Ganzen Zahl factorization allgemein als Versorgung der Sicherheit betrachtet. Wenn die Blüte passend gewählt wird, und O (Klotz M loggen), sind Bit der niedrigeren Ordnung jedes x Produktion dann in der Grenze, weil M groß wächst, sollte das Unterscheiden der Produktionsbit vom zufälligen mindestens so schwierig sein wie Factoring M.

Wenn ganze Zahl factorization schwierig ist (wie verdächtigt wird) dann, sollte B.B.S. mit der großen M eine Produktion haben, die von irgendwelchen nichtzufälligen Mustern frei ist, die mit jedem angemessenen Betrag der Berechnung entdeckt werden können. So scheint es, so sicher zu sein, wie andere Verschlüsselungstechnologien zum factorization Problem wie RSA-Verschlüsselung punktgleich gewesen sind.

Beispiel

Lassen Sie und (wo der Samen ist.) Wir können annehmen, eine große Zyklus-Länge für jene kleinen Zahlen, weil zu bekommen.

Der Generator fängt an, durch das Verwenden zu bewerten, und schafft die Folge, = 9, 81, 82, 36, 42, 92. Der folgende Tisch zeigt, dass die Produktion (in Bit) für die verschiedenen Bit-Auswahl-Methoden gepflegt hat, die Produktion zu bestimmen.

• Lenore Blum, Manuel Blum und Michael Shub. "Ein Einfacher Unvorhersehbarer Pseudozufälliger Zahlengenerator", SIAM Zeitschrift auf der Computerwissenschaft, dem Band 15, den Seiten 364-383, Mai 1986.
• Lenore Blum, Manuel Blum und Michael Shub. "Vergleich von zwei pseudozufälligen Zahlengeneratoren", Fortschritte in Cryptology: Verhandlungen von Geheim-'82. Verfügbar als [ftp://ftp.hacktic.nl/pub/mirrors/Advances%20in%20Cryptology/HTML/PDF/C82/61.PDF PDF].
• Martin Geisler, Mikkel Krøigård und Andreas Danielsen. "Über Zufällige Bit", Dezember 2004. Verfügbar als PDF und Gzipped Nachschrift.

Links

• GMPBBS (archiviert am 2009-05-24 an der Wayback Maschine), ein GPL'ed hat Durchführung von Blum Blum Shub durch Mark Rossmiller GMP-basiert. Wiederbekommen am 2011-09-05.
• Eine Durchführung in Java
• Zufälligkeit prüft