Blum Blum Bour – Wikipedia wiki

Posted on by
before-content-x4

Aus Wikipedia, der freien Enzyklopädie

after-content-x4

Blum Blum Bour ( B.B.S. ) ist ein Pseudorandom-Zahlengenerator, das 1986 von Lenore Blum, Manuel Blum und Michael Shub vorgeschlagen wurde, der von Michael O. Rabins Einweg-Funktion stammt.

Blum Blum Shub nimmt die Form an

Wo M = pq ist das Produkt von zwei großen Primzahlen P Und Q . Bei jedem Schritt des Algorithmus wird ein gewisser Ausgang abgeleitet X N +1 ; Der Ausgang ist normalerweise entweder die Bitparität von X N +1 oder eine oder mehrere der am wenigsten bedeutenden Teile von X N +1 .

Der Samen X 0 sollte eine Ganzzahl sein, die Co-Primes ist M (D.h. P Und Q sind keine Faktoren von X 0 ) und nicht 1 oder 0.

after-content-x4

Die beiden Primzahlen, P Und Q sollte beide mit 3 (MOD 4) übereinstimmen (dies garantiert, dass jeder quadratische Rückstand eine quadratische Wurzel hat, die ebenfalls ein quadratischer Rückstand ist) und sichere Primzahlen mit einem kleinen GCD sein sollte ((((((( P-3 ) /2 , ( Q-3 ) /2 ) (Dies macht die Zykluslänge groß).

Ein interessantes Merkmal des Blum Blum Shub -Generators ist die Möglichkeit, alle zu berechnen X ich Wert direkt (über Euler’s Theorem):

Wo

l {displayStyle lambda}

ist die Carmichael -Funktion. (Hier haben wir

l ( M ) = l ( P ⋅ Q ) = LCM ⁡ ( P – – Erste Anwesend Q – – Erste ) {displayStyle lambda (m) = lambda (pcdot q) = operatorname {lcm} (p-1, q-1)}

).

Sicherheit [ bearbeiten ]

Es gibt einen Beweis, der seine Sicherheit auf die rechnerische Schwierigkeit der Faktorierung verringert. Wenn die Primzahlen angemessen ausgewählt werden, und Ö (Protokollprotokoll M ) Bit von jeweils niedrigerer Ordnung X N sind ausgegeben, dann in der Grenze als M Wachstum wächst, die Unterscheidung der Ausgangsbits von zufällig sollte mindestens so schwierig sein wie das Lösen des quadratischen Resistuositätsproblemmodulo M .

Beispiel [ bearbeiten ]

Lassen

P = 11 {displayStyle p = 11}

Anwesend

Q = 23 {displayStyle q = 23}

Und

S = 3 {displayStyle s = 3}

(Wo

S {displayStyle s}

ist der Samen). Wir können erwarten, eine große Zykluslänge für diese kleinen Zahlen zu erhalten, weil

gcd( ( P – – 3 ) / 2 Anwesend ( Q – – 3 ) / 2 ) = 2 {displayStyle {rm {gcd}} ((p-3)/2, (q-3)/2) = 2}

.
Der Generator beginnt zu bewerten

X 0{displayStyle x_ {0}}

durch die Nutzung

X −1= S {displayStyle x _ {-1} = s}

und erstellt die Sequenz

X 0{displayStyle x_ {0}}

Anwesend

X 1{displayStyle x_ {1}}

Anwesend

X 2{displayStyle x_ {2}}

Anwesend

… {displayStyle ldots}

X 5{displayStyle x_ {5}}

= 9, 81, 236, 36, 31, 202. Die folgende Tabelle zeigt den Ausgang (in Bits) für die verschiedenen Bitauswahlmethoden zur Bestimmung des Ausgangs.

Die folgende gemeinsame LISP -Implementierung liefert eine einfache Demonstration des Generators, insbesondere in Bezug auf die drei Bitauswahlmethoden. Es ist wichtig zu beachten, dass die Anforderungen der Parameter vorliegt P Anwesend Q Und S (Samen) werden nicht überprüft. 

( Defun  Get-number-of-1-Bits  ( Bits )  "Gibt die Anzahl der 1-Wert-Bits in den ganzzahligen Bits zurück."  ( erklären  ( Typ  ( ganze Zahl  0  * )  Bits ))  ( Die  ( ganze Zahl  0  * )  ( Logcount  Bits )))  ( Defun  Get-Even-Parity-Bit  ( Bits )  "Gibt das gleichmäßige Paritätsbit der integer kodierten Bits zurück."  ( erklären  ( Typ  ( ganze Zahl  0  * )  Bits ))  ( Die  Bit  ( gegen  ( Get-number-of-1-Bits  Bits )  2 )))  ( Defun  Get-Last-Signifikant-Bit  ( Bits )  "Gibt das am wenigsten signifikante Stück der integer kodierten Bits zurück."  ( erklären  ( Typ  ( ganze Zahl  0  * )  Bits ))  ( Die  Bit  ( LDB  ( Byte  Erste  0 )  Bits )))  ( Defun  Make-Blum-Blum-Shub  ( &Taste  ( P  11 )  ( Q  23 )  ( S  3 ))  "Gibt eine Funktion von keine Argumente zurück, die ein einfaches darstellen  Blum-Blum-Shub-Pseudorandom-Zahlengenerator, die für die Verwendung der Verwendung konfiguriert sind  Generatorparameter P, Q und S (Saatgut) sowie die Rückgabe von drei Werten:  (1) die Zahl x [n+1],  (2) das gleichmäßige Paritätsbit der Zahl,  (3) das am wenigsten signifikante Bit der Zahl.  ---  Bitte beachten Sie, dass die Parameter P, Q und S nicht eingecheckt werden  Übereinstimmung mit den im Artikel beschriebenen Bedingungen. "  ( erklären  ( Typ  ( ganze Zahl  0  * )  P  Q  S ))  ( lassen  (( M  ( *  P  Q ))  ;; M = p * q  ( x [n]  S ))  ;; x0 = Samen  ( erklären  ( Typ  ( ganze Zahl  0  * )  M  x [n] ))  #' ( Lambda  ()  ;; x [n+1] = x [n]^2 mod m  ( lassen  (( x [n+1]  ( gegen  ( *  x [n]  x [n] )  M )))  ( erklären  ( Typ  ( ganze Zahl  0  * )  x [n+1] ))  ;; Berechnen Sie die zufälligen Bits basierend auf x [n+1].  ( lassen  (( Even-Parity-Bit  ( Get-Even-Parity-Bit  x [n+1] ))  ( niedrigstwertige Bit  ( Get-Last-Signifikant-Bit  x [n+1] )))  ( erklären  ( Typ  Bit  Even-Parity-Bit ))  ( erklären  ( Typ  Bit  niedrigstwertige Bit ))  ;; Aktualisieren Sie den Zustand so, dass x [n+1] zum neuen x [n] wird.  ( setf  x [n]  x [n+1] )  ( Werte  x [n+1]  Even-Parity-Bit  niedrigstwertige Bit ))))))  ;; Drucken Sie die beispielhaften Ausgänge.  ( lassen  (( BBS  ( Make-Blum-Blum-Shub  :P  11  :Q  23  :S  3 )))  ( erklären  ( Typ  ( Funktion  ()  ( Werte  ( ganze Zahl  0  * )  Bit  Bit ))  BBS ))  ( Format  T  "~ & Keys: E = sogar Parität, l = am wenigsten signifikant" )  ( Format  T  "~ 2%" )  ( Format  T  "~ & x [n+1] | e | l" )  ( Format  T  "~ & --------------" )  ( Schleife  wiederholen  6  Tun  ( Mehrwertbindung  ( x [n+1]  Even-Parity-Bit  niedrigstwertige Bit )  ( Funcall  BBS )  ( erklären  ( Typ  ( ganze Zahl  0  * )  x [n+1] ))  ( erklären  ( Typ  Bit  Even-Parity-Bit ))  ( erklären  ( Typ  Bit  niedrigstwertige Bit ))  ( Format  T  "~ & ~ 6d | ~ d | ~ D"  x [n+1]  Even-Parity-Bit  niedrigstwertige Bit ))))

Verweise [ bearbeiten ]

Zitate [ bearbeiten ]

Quellen [ bearbeiten ]

Externe Links [ bearbeiten ]

after-content-x4