[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/blum-blum-bour-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/blum-blum-bour-wikipedia\/","headline":"Blum Blum Bour – Wikipedia wiki","name":"Blum Blum Bour – Wikipedia wiki","description":"before-content-x4 Aus Wikipedia, der freien Enzyklop\u00e4die after-content-x4 Blum Blum Bour ( B.B.S. ) ist ein Pseudorandom-Zahlengenerator, das 1986 von Lenore","datePublished":"2016-01-05","dateModified":"2016-01-05","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/1973ef6f265492040ea5a1ac9cd2e1be73e2b04b","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/1973ef6f265492040ea5a1ac9cd2e1be73e2b04b","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/blum-blum-bour-wikipedia\/","wordCount":4877,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Aus Wikipedia, der freien Enzyklop\u00e4die        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Blum 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.         (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Blum Blum Shub nimmt die Form an xn+1= xn2modM{DisplayStyle x_ {n+1} = x_ {n}^{2} {b auf eine Weise {m}}} Anwesend Wo M = pq ist das Produkt von zwei gro\u00dfen Primzahlen P Und Q . Bei jedem Schritt des Algorithmus wird ein gewisser Ausgang abgeleitet X N +1 ; Der Ausgang ist normalerweise entweder die Bitparit\u00e4t 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.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Die beiden Primzahlen, P Und Q sollte beide mit 3 (MOD 4) \u00fcbereinstimmen (dies garantiert, dass jeder quadratische R\u00fcckstand eine quadratische Wurzel hat, die ebenfalls ein quadratischer R\u00fcckstand ist) und sichere Primzahlen mit einem kleinen GCD sein sollte ((((((( P-3 ) \/2 , ( Q-3 ) \/2 ) (Dies macht die Zyklusl\u00e4nge gro\u00df). Ein interessantes Merkmal des Blum Blum Shub -Generators ist die M\u00f6glichkeit, alle zu berechnen X ich Wert direkt (\u00fcber Euler’s Theorem): xi= (x02imod\u03bb(M))modM{DisplayStyle x_ {i} = links (x_ {0} {{2 {i} {b in einem lambda}} (m)} rechts) {b in gewisser Weise {m}}} Anwesend Wo l {displayStyle lambda} ist die Carmichael -Funktion. (Hier haben wir l ( M ) = l ( P \u22c5 Q ) = LCM \u2061 ( P – – Erste Anwesend Q – – Erste ) {displayStyle lambda (m) = lambda (pcdot q) = operatorname {lcm} (p-1, q-1)} ). Table of ContentsSicherheit [ bearbeiten ] Beispiel [ bearbeiten ] Verweise [ bearbeiten ] Zitate [ bearbeiten ] Quellen [ bearbeiten ] Externe Links [ bearbeiten ] Sicherheit [ bearbeiten ] Es gibt einen Beweis, der seine Sicherheit auf die rechnerische Schwierigkeit der Faktorierung verringert. Wenn die Primzahlen angemessen ausgew\u00e4hlt werden, und \u00d6 (Protokollprotokoll M ) Bit von jeweils niedrigerer Ordnung X N sind ausgegeben, dann in der Grenze als M Wachstum w\u00e4chst, die Unterscheidung der Ausgangsbits von zuf\u00e4llig sollte mindestens so schwierig sein wie das L\u00f6sen des quadratischen Resistuosit\u00e4tsproblemmodulo 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\u00f6nnen erwarten, eine gro\u00dfe Zyklusl\u00e4nge f\u00fcr 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 \u22121= 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\u00fcr 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 \u00fcberpr\u00fcft. ( Defun  Get-number-of-1-Bits  ( Bits )  \"Gibt die Anzahl der 1-Wert-Bits in den ganzzahligen Bits zur\u00fcck.\"  ( erkl\u00e4ren  ( Typ  ( ganze Zahl  0  * )  Bits ))  ( Die  ( ganze Zahl  0  * )  ( Logcount  Bits )))  ( Defun  Get-Even-Parity-Bit  ( Bits )  \"Gibt das gleichm\u00e4\u00dfige Parit\u00e4tsbit der integer kodierten Bits zur\u00fcck.\"  ( erkl\u00e4ren  ( 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\u00fcck der integer kodierten Bits zur\u00fcck.\"  ( erkl\u00e4ren  ( 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\u00fcck, die ein einfaches darstellen  Blum-Blum-Shub-Pseudorandom-Zahlengenerator, die f\u00fcr die Verwendung der Verwendung konfiguriert sind  Generatorparameter P, Q und S (Saatgut) sowie die R\u00fcckgabe von drei Werten:  (1) die Zahl x [n+1],  (2) das gleichm\u00e4\u00dfige Parit\u00e4tsbit der Zahl,  (3) das am wenigsten signifikante Bit der Zahl.  ---  Bitte beachten Sie, dass die Parameter P, Q und S nicht eingecheckt werden  \u00dcbereinstimmung mit den im Artikel beschriebenen Bedingungen. \"  ( erkl\u00e4ren  ( Typ  ( ganze Zahl  0  * )  P  Q  S ))  ( lassen  (( M  ( *  P  Q ))  ;; M = p * q  ( x [n]  S ))  ;; x0 = Samen  ( erkl\u00e4ren  ( 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\u00e4ren  ( Typ  ( ganze Zahl  0  * )  x [n+1] ))  ;; Berechnen Sie die zuf\u00e4lligen 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\u00e4ren  ( Typ  Bit  Even-Parity-Bit ))  ( erkl\u00e4ren  ( 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\u00e4nge.  ( lassen  (( BBS  ( Make-Blum-Blum-Shub  :P  11  :Q  23  :S  3 )))  ( erkl\u00e4ren  ( Typ  ( Funktion  ()  ( Werte  ( ganze Zahl  0  * )  Bit  Bit ))  BBS ))  ( Format  T  \"~ & Keys: E = sogar Parit\u00e4t, 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\u00e4ren  ( Typ  ( ganze Zahl  0  * )  x [n+1] ))  ( erkl\u00e4ren  ( Typ  Bit  Even-Parity-Bit ))  ( erkl\u00e4ren  ( Typ  Bit  niedrigstwertige Bit ))  ( Format  T  \"~ & ~ 6d | ~ d | ~ D\"  x [n+1]  Even-Parity-Bit  niedrigstwertige Bit ))))  Verweise [ bearbeiten ] Zitate [ bearbeiten ] Quellen [ bearbeiten ] Blum, Lenore; Blum, Manuel; Shub, Michael (1983). “Vergleich von zwei Pseudo-Random-Zahlengeneratoren” . Fortschritte in der Kryptologie . Boston, MA: Springer uns. S. 61\u201378. doi: 10.1007\/978-1-14757-0602-4_6 . ISBN 978-1-1-4757-0604-8 . Blum, l .; Blum, M.; Shub, M. (1986). “Ein einfacher unvorhersehbarer Pseudo-Random-Zahlengenerator”  (PDF) . Siam Journal \u00fcber Computing . Gesellschaft f\u00fcr industrielle und angewandte Mathematik (Siam). 15 (2): 364\u2013383. doi: 10.1137\/0215025 . ISSN 0097-5397 . Archiviert  (PDF) vom Original am 2021-08-14. Geisler, Martin; Kr\u00f8ig\u00e5rd, Mikkel; Danielsen, Andreas (Dezember 2004), \u00dcber zuf\u00e4llige Bits  (PDF) , Citeseerx 10.1.1.90.3779 Anwesend archiviert  (PDF) vom Original am 2016-03-31 Externe Links [ bearbeiten ]        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en2de\/wiki7\/blum-blum-bour-wikipedia\/#breadcrumbitem","name":"Blum Blum Bour – Wikipedia wiki"}}]}]