Bloom-Blum-Fur coat algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 4-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A Blum-Blum-Shub algoritmus ( angol. Algorithm Blum-Blum-Shub , BBS) egy pszeudo-véletlen számgenerátor , amelyet 1986-ban Lenore Blum , Manuel Blum és Michael Shub javasolt .

A BBS így néz ki:

x_{n+1}=x_n^2\;\bmod\;M,

ahol két nagy prímszám és a szorzata . Az algoritmus minden lépésében a kimenet vagy a paritásbitből vagy egy vagy több legkisebb jelentőségű bitből származik . $M=pq$ $p$ $q$ $x_{n}$ $x_{n}$

A és a két prímnek egybe kell esnie 3 modulo 4 értékkel (ez garantálja, hogy minden másodfokú maradéknak van egy négyzetgyöke , ami egyben másodfokú maradék is ), és a legnagyobb közös osztónak , a gcd - nek kicsinek kell lennie (ez növeli a ciklus hosszát). $p$ $q$ ${\megjelenítési stílus (p-1, q-1)}$

Ennek az algoritmusnak egy érdekessége, hogy a megszerzéséhez nem szükséges az összes előző számot kiszámítani, ha a generátor kezdeti állapota és a és számok ismertek . -adik érték "közvetlenül" kiszámítható a következő képlet segítségével: $x_{n}$ $n-1$ $x_{0}$ $p$ $q$ $n$

x_{n}=x_{0}^{2^{n}{\bmod {\lambda }}(M)}\;{\bmod {\;}}M

ahol a Carmichael függvény : ebben az esetben a számok legkisebb közös többszöröse és . $\lambda$ $\lambda (M)=\lambda (pq)=lcm(p-1,q-1)$ $p-1$ $q-1$

Megbízhatóság

Ez a generátor alkalmas titkosításra , de nem szimulációra, mert nem elég gyors. Ugyanakkor szokatlanul nagy a tartóssága, amit a generátor minősége biztosít a számtényezős probléma számítási összetettsége alapján . Ha a prímszámokat gondosan választják ki, és mindegyik bitje a kimenet, akkor a határérték gyorsan növekszik, és a kimeneti bitek kiszámítása ugyanolyan nehéz lesz, mint a faktorizálás . $O(\log\logM)$ $x_{n}$ $M$ $M$

Ha az egész számok faktorizálása olyan nehéz (ahogy annak lennie kell), akkor egy nagy BBS kimenete mentes minden nem véletlenszerű mintától, amely elegendő számítással kimutatható. A faktorizálás gyors algoritmusa azonban lehetséges, ezért a BBS nem garantált megbízhatósága. $M$

Jegyzetek

Irodalom

Lenore Blum, Manuel Blum és Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing , 15. kötet, 364-383. oldal, 1986. május.
Lenore Blum, Manuel Blum és Michael Shub. "Két pszeudo-véletlenszám-generátor összehasonlítása", Advances in Cryptology: Proceedings of Crypto '82 . Elérhető PDF formátumban .
Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", 1999. augusztus. 21 oldalas PDF-fájl
Martin Geisler, Mikkel Krøigård és Andreas Danielsen. "About Random Bits", 2004. december. Elérhető PDF és Gzipped Postscript formátumban .
Véletlenszerűségi ajánlások a biztonsághoz - RFC 1750 .