Blum Blum Shub: Porovnání verzí
Smazaný obsah Přidaný obsah
m Bot: Odstranění 14 odkazů interwiki, které jsou nyní dostupné na Wikidatech (d:q886155) |
fundamentální doplnění |
||
| Řádek 1: | Řádek 1: | ||
'''Blum Blum Shub''' ('''BBS''') je jednoduchý [[generátor pseudonáhodných čísel]]. Název je odvozen od autorů, kteří popsali v roce 1986 jeho vlastnosti. Těmi jsou [[Lenore Blum]], [[Manuel Blum]] a [[Michael Shub]]. |
'''Blum Blum Shub''' ('''BBS''') je jednoduchý [[generátor pseudonáhodných čísel]] z třídy [[Generátor kryptograficky bezpečných pseudonáhodných čísel|generátorů kryptograficky bezpečných pseudonáhodných čísel]] (CSPRNG). Název je odvozen od autorů, kteří popsali v roce 1986 (resp. 1982) jeho vlastnosti. Těmi jsou [[Lenore Blum]], [[Manuel Blum]] a [[Michael Shub]]. |
||
BBS používá rekurzivní formuli |
BBS používá rekurzivní formuli |
||
:''x |
:''x<sub>i</sub>'' = (''x''<sub>''i''-1</sub>)<sup>2</sup> [[modulo|mod]] ''M'' |
||
kde |
|||
* ''M'' je součin dvou velkých (tajných) prvočísel ''p'' a ''q'', pro ta by mělo platit, že jsou |
|||
** kongruentní 3 modulo 4 |
|||
** stejné délky<ref name="blum1986" /> |
|||
* ''x''<sub>0</sub> je inicializační hodnota (''seed''), splňující |
|||
** 0 < ''x''<sub>0</sub> < ''M'' |
|||
** [[Největší společný dělitel|gcd]](''x''<sub>0</sub>, ''M'') = 1 |
|||
* výstupem generátoru je bit získaný jako bitová parita čísla ''x<sub>i</sub>''<ref name="blum1983" /> |
|||
Výhodou generátoru je možnost přímo vypočítat ''x<sub>i</sub>'': |
|||
: ''x<sub>i</sub>'' = ''x''{{su|b=0|p=2<sup>''i''</sup> mod λ(''M'')|s=0}} mod ''M'' |
|||
kde λ je [[Carmichaelova funkce]]. |
|||
Blum Blum Shub je zajímavý spíše z teoretického hlediska a v praxi se příliš nepoužívá, kvůli malé rychlosti a nutnosti utajení ''p'' a ''q''. |
|||
== Odkazy == |
|||
=== Reference === |
|||
<references> |
|||
<ref name="blum1983">{{Citace elektronického periodika |
|||
| příjmení1 = Blum |
|||
| jméno1 = Lenore |
|||
| příjmení2 = Blum |
|||
| jméno2 = Manuel |
|||
| příjmení3 = Shub |
|||
| jméno3 = Michael |
|||
| titul = Comparison of Two Pseudo-Random Number Generators |
|||
| periodikum = Advances in Cryptology |
|||
| datum_vydání = 1983 |
|||
| strany = 61–78 |
|||
| datum_přístupu = 2021-06-30 |
|||
| jazyk = en |
|||
| doi = 10.1007/978-1-4757-0602-4_6 |
|||
| url = https://iacr.org/cryptodb/data/paper.php?pubkey=1751 |
|||
}}</ref> |
|||
<ref name="blum1986">{{Citace elektronického periodika |
|||
| příjmení1 = Blum |
|||
| jméno1 = L. |
|||
| příjmení2 = Blum |
|||
| jméno2 = M. |
|||
| příjmení3 = Shub |
|||
| jméno3 = M. |
|||
| titul = A Simple Unpredictable Pseudo-Random Number Generator |
|||
| periodikum = SIAM Journal on Computing |
|||
| ročník = 15 |
|||
| číslo = 2 |
|||
| datum_vydání = 1986-05 |
|||
| strany = 364–383 |
|||
| url = https://epubs.siam.org/doi/10.1137/0215025 |
|||
| datum_přístupu = 2021-06-30 |
|||
| jazyk = en |
|||
| doi = 10.1137/0215025 |
|||
}}</ref> |
|||
</references> |
|||
{{Pahýl}} |
{{Pahýl}} |
||
Verze z 30. 6. 2021, 09:46
Blum Blum Shub (BBS) je jednoduchý generátor pseudonáhodných čísel z třídy generátorů kryptograficky bezpečných pseudonáhodných čísel (CSPRNG). Název je odvozen od autorů, kteří popsali v roce 1986 (resp. 1982) jeho vlastnosti. Těmi jsou Lenore Blum, Manuel Blum a Michael Shub.
BBS používá rekurzivní formuli
- xi = (xi-1)2 mod M
kde
- M je součin dvou velkých (tajných) prvočísel p a q, pro ta by mělo platit, že jsou
- kongruentní 3 modulo 4
- stejné délky[1]
- x0 je inicializační hodnota (seed), splňující
- 0 < x0 < M
- gcd(x0, M) = 1
- výstupem generátoru je bit získaný jako bitová parita čísla xi[2]
Výhodou generátoru je možnost přímo vypočítat xi:
- xi = x2i mod λ(M)
0 mod M
kde λ je Carmichaelova funkce.
Blum Blum Shub je zajímavý spíše z teoretického hlediska a v praxi se příliš nepoužívá, kvůli malé rychlosti a nutnosti utajení p a q.
Odkazy
Reference
- ↑ BLUM, L.; BLUM, M.; SHUB, M. A Simple Unpredictable Pseudo-Random Number Generator. S. 364–383. SIAM Journal on Computing [online]. 1986-05 [cit. 2021-06-30]. Roč. 15, čís. 2, s. 364–383. Dostupné online. DOI 10.1137/0215025. (anglicky)
- ↑ BLUM, Lenore; BLUM, Manuel; SHUB, Michael. Comparison of Two Pseudo-Random Number Generators. S. 61–78. Advances in Cryptology [online]. 1983 [cit. 2021-06-30]. S. 61–78. Dostupné online. DOI 10.1007/978-1-4757-0602-4_6. (anglicky)
