Bloom-Blum-Fur coat algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4.11.2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Algoritmi Blum - Blum - Shub ( eng. Algorithm Blum - Blum - Shub , BBS) on näennäissatunnainen lukugeneraattori, jonka Lenore Blum , Manuel Blum ja Michael Shub ehdottivat vuonna 1986 .

BBS näyttää tältä:

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

missä on kahden suuren alkuluvun ja . Algoritmin jokaisessa vaiheessa tulos saadaan joko pariteettibitistä tai yhdestä tai useammasta vähiten merkitsevästä bitistä . $M = pq$ $s$ $q$ $x_{n}$ $x_{n}$

Kahden alkuluvun ja , on molempien oltava kongruentteja 3 modulo 4:n kanssa (tämä takaa, että jokaisella neliöjäännöksellä on yksi neliöjuuri , joka on myös neliöjuuri ) ja suurimman yhteisen jakajan gcd on oltava pieni (tämä lisää syklin pituutta). $s$ $q$ ${\näyttötyyli (p-1,q-1)}$

Tämän algoritmin mielenkiintoinen piirre on, että sen saamiseksi ei tarvitse laskea kaikkia aikaisempia lukuja, jos generaattorin alkutila ja luvut ja ovat tiedossa . -arvo voidaan laskea "suoraan" kaavalla: $x_{n}$ $n-1$ $x_{0}$ $s$ $q$ $n$

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

missä on Carmichael-funktio : tässä tapauksessa lukujen pienin yhteinen kerrannainen ja . $\lambda$ $\lambda (M)=\lambda (pq)=lcm(p-1,q-1)$ $p-1$ $q-1$

Luotettavuus

Tämä generaattori sopii kryptografiaan , mutta ei simulointiin, koska se ei ole tarpeeksi nopea. Sillä on kuitenkin epätavallisen korkea kestävyys, jonka tarjoaa generaattorin laatu, joka perustuu lukukerroinongelman laskennalliseen monimutkaisuuteen . Kun alkuluvut valitaan huolellisesti ja kunkin bitit ovat lähtö, niin nopeasti otettu raja kasvaa ja lähtöbittien laskeminen on yhtä vaikeaa kuin tekijöiden laskeminen . $O(\log\logM)$ $x_{n}$ $M$ $M$

Jos kokonaislukujen tekijöihin jako on niin vaikeaa (kuten sen oletetaan olevan), niin suuren BBS :n tulos on vapaa kaikista ei-satunnaisista kuvioista, jotka voidaan havaita riittävällä laskennalla. Nopea faktorointialgoritmi on kuitenkin mahdollinen, joten BBS:n luotettavuutta ei voida taata. $M$

Muistiinpanot

Kirjallisuus

Lenore Blum, Manuel Blum ja Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing , osa 15, sivut 364-383, toukokuu 1986.
Lenore Blum, Manuel Blum ja Michael Shub. "Kahden pseudosatunnaislukugeneraattorin vertailu", Advances in Cryptology: Proceedings of Crypto '82 . Saatavilla PDF-muodossa .
Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", elokuu 1999. 21-sivuinen PDF-tiedosto
Martin Geisler, Mikkel Krøigård ja Andreas Danielsen. "About Random Bits", joulukuu 2004. Saatavilla PDF- ja Gzipped Postscript -muodossa .
Turvallisuussuositukset - RFC 1750 .