Algoritmus Bloom-Blum-Fur coat

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. listopadu 2021; kontroly vyžadují 4 úpravy .

Algorithm Blum - Blum - Shub ( angl. Algorithm Blum - Blum - Shub , BBS) je generátor pseudonáhodných čísel navržený v roce 1986 Lenorem Blumem , Manuelem Blumem a Michaelem Shubem .

BBS vypadá takto:

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

kde je součin dvou velkých prvočísel a . V každém kroku algoritmu je výstup získán buď z paritního bitu nebo z jednoho či více bitů s nejnižší hodnotou . $M=pq$ $p$ $q$ $x_{n}$ $x_{n}$

Dvě prvočísla a , musí být obě shodné s 3 modulo 4 (to zaručuje, že každý kvadratický zbytek má jednu druhou odmocninu , což je také kvadratický zbytek ) a největší společný dělitel gcd musí být malý (tím se prodlužuje délka cyklu). $p$ $q$ $(p-1,q-1)$

Zajímavou vlastností tohoto algoritmu je, že pro získání není nutné počítat všechna předchozí čísla, pokud jsou známy počáteční stav generátoru a čísla a . -tou hodnotu lze vypočítat "přímo" pomocí vzorce: $x_{n}$ $n-1$ $x_{0}$ $p$ $q$ $n$

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

kde je Carmichaelova funkce : v tomto případě nejmenší společný násobek čísel a . $\lambda$ $\lambda (M)=\lambda (pq)=lcm(p-1,q-1)$ $p-1$ $q-1$

Spolehlivost

Tento generátor je vhodný pro kryptografii , ale ne pro simulaci, protože není dostatečně rychlý. Má však neobvykle vysokou odolnost, kterou zajišťuje kvalita generátoru založená na výpočetní složitosti problému rozkladu čísel . Když jsou prvočísla pečlivě vybírána a bity každého jsou výstupem, pak limit zabraný tak rychle roste a výpočet výstupních bitů bude stejně obtížný jako faktorizace . $O(\log\logM)$ $x_{n}$ $M$ $M$

Pokud je faktorizace celých čísel tak obtížná (jak se předpokládá), pak velký BBS bude mít výstup bez jakýchkoliv nenáhodných vzorů, které lze detekovat dostatečným výpočtem. Je však možný rychlý algoritmus faktorizace, a proto není zaručena spolehlivost BBS. $M$

Poznámky

Literatura

Lenore Blum, Manuel Blum a Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing , svazek 15, strany 364-383, květen 1986.
Lenore Blum, Manuel Blum a Michael Shub. "Porovnání dvou generátorů pseudonáhodných čísel", Advances in Cryptology: Proceedings of Crypto '82 . K dispozici jako PDF .
Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generator: The Blum-Blum-Shub Generator", srpen 1999. 21stránkový soubor PDF
Martin Geisler, Mikkel Krøigård a Andreas Danielsen. "About Random Bits", prosinec 2004. Dostupné jako PDF a Gzipped Postscript .
Náhodné doporučení pro bezpečnost - RFC 1750 .