Blum Blum Shub: Difference between revisions
m Amended the documentation to reflect the correct order of return values and improved the formatting. |
Waynejayes (talk | contribs) references |
||
Line 4: | Line 4: | ||
}} |
}} |
||
'''Blum Blum Shub''' ('''B.B.S.''') is a [[pseudorandom number generator]] proposed in 1986 by [[Lenore Blum]], [[Manuel Blum]] and [[Michael Shub]] |
'''Blum Blum Shub''' ('''B.B.S.''') is a [[pseudorandom number generator]] proposed in 1986 by [[Lenore Blum]], [[Manuel Blum]] and [[Michael Shub]]{{sfn|Blum|Blum|Shub|1986|pp=364–383}} that is derived from [[Michael O. Rabin]]'s one-way function. |
||
__TOC__ |
|||
{{cite journal |
|||
|last=Blum |
|||
|first=Lenore |
|||
|author2=Blum, Manuel |author3=Shub, Mike |
|||
|title=A Simple Unpredictable Pseudo-Random Number Generator |
|||
|journal=SIAM Journal on Computing |
|||
|date=1 May 1986 |
|||
|volume=15 |
|||
|issue=2 |
|||
|pages=364–383 |
|||
|doi=10.1137/0215025 |
|||
}} |
|||
</ref> that is derived from [[Michael O. Rabin]]'s one-way function. |
|||
Blum Blum Shub takes the form |
Blum Blum Shub takes the form |
||
Line 36: | Line 23: | ||
==Security== |
==Security== |
||
There is a proof reducing its security to the [[Computational complexity theory|computational difficulty]] of factoring. |
There is a proof reducing its security to the [[Computational complexity theory|computational difficulty]] of factoring.{{sfn|Blum|Blum|Shub|1986|pp=364–383}} When the primes are chosen appropriately, and [[big O notation|''O'']]([[logarithm|log]] log ''M'') lower-order bits of each ''x<sub>n</sub>'' are output, then in the limit as ''M'' grows large, distinguishing the output bits from random should be at least as difficult as solving the [[quadratic residuosity problem]] modulo ''M''. |
||
==Example== |
==Example== |
||
Line 116: | Line 103: | ||
==References== |
==References== |
||
===Citations=== |
|||
{{Reflist}} |
{{Reflist}} |
||
===Sources=== |
|||
;General |
|||
{{refbegin}} |
|||
* {{cite |
* {{cite book| last=Blum | first=Lenore | last2=Blum | first2=Manuel | last3=Shub | first3=Michael | title=Advances in Cryptology | chapter=Comparison of Two Pseudo-Random Number Generators | publisher=Springer US | publication-place=Boston, MA | year=1983 | doi=10.1007/978-1-4757-0602-4_6|chapter-url=https://www.iacr.org/cryptodb/data/paper.php?pubkey=1751}} |
||
*{{cite journal | last=Blum | first=L. | last2=Blum | first2=M. | last3=Shub | first3=M. | title=A Simple Unpredictable Pseudo-Random Number Generator | journal=SIAM Journal on Computing | publisher=Society for Industrial & Applied Mathematics (SIAM) | volume=15 | issue=2 | year=1986 | issn=0097-5397 | doi=10.1137/0215025 | pages=364–383|url=https://shub.ccny.cuny.edu/articles/1986-A_simple_unpredictable_pseudo-random_number_generator.pdf}} |
|||
* {{cite journal|last=Geisler|first=Martin|author2=Krøigård, Mikkel |author3=Danielsen, Andreas |title=About Random Bits|date=December 2004|citeseerx=10.1.1.90.3779}} available as [https://web.archive.org/web/20120209143119/http://daimi.au.dk/~mg/mamian/random-bits.pdf PDF] and [https://web.archive.org/web/20110719120806/http://daimi.au.dk/~mg/mamian/random-bits.ps.gz gzipped Postscript] |
* {{cite journal|last=Geisler|first=Martin|author2=Krøigård, Mikkel |author3=Danielsen, Andreas |title=About Random Bits|date=December 2004|citeseerx=10.1.1.90.3779}} available as [https://web.archive.org/web/20120209143119/http://daimi.au.dk/~mg/mamian/random-bits.pdf PDF] and [https://web.archive.org/web/20110719120806/http://daimi.au.dk/~mg/mamian/random-bits.ps.gz gzipped Postscript] |
||
{{refend}} |
|||
* |
|||
==External links== |
==External links== |
Revision as of 11:55, 29 August 2021
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub[1] that is derived from Michael O. Rabin's one-way function.
Blum Blum Shub takes the form
- ,
where M = pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.
The seed x0 should be an integer that is co-prime to M (i.e. p and q are not factors of x0) and not 1 or 0.
The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue), and should be safe primes with a small gcd((p-3)/2, (q-3)/2) (this makes the cycle length large).
An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (via Euler's theorem):
- ,
where is the Carmichael function. (Here we have ).
Security
There is a proof reducing its security to the computational difficulty of factoring.[1] When the primes are chosen appropriately, and O(log log M) lower-order bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random should be at least as difficult as solving the quadratic residuosity problem modulo M.
Example
Let , and (where is the seed). We can expect to get a large cycle length for those small numbers, because . The generator starts to evaluate by using and creates the sequence , , , = 9, 81, 236, 36, 31, 202. The following table shows the output (in bits) for the different bit selection methods used to determine the output.
Parity bit | Least significant bit |
---|---|
0 1 1 0 1 0 | 1 1 0 0 1 0 |
The following Common Lisp implementation provides a simple demonstration of the generator, in particular regarding the three bit selection methods. It is important to note that the requirements imposed upon the parameters p, q and s (seed) are not checked.
(defun get-number-of-1-bits (bits)
"Returns the number of 1-valued bits in the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the (integer 0 *) (logcount bits)))
(defun get-even-parity-bit (bits)
"Returns the even parity bit of the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the bit (mod (get-number-of-1-bits bits) 2)))
(defun get-least-significant-bit (bits)
"Returns the least significant bit of the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the bit (ldb (byte 1 0) bits)))
(defun make-blum-blum-shub (&key (p 11) (q 23) (s 3))
"Returns a function of no arguments which represents a simple
Blum-Blum-Shub pseudorandom number generator, configured to use the
generator parameters P, Q, and S (seed), and returning three values:
(1) the number x[n+1],
(2) the even parity bit of the number,
(3) the least significant bit of the number.
---
Please note that the parameters P, Q, and S are not checked in
accordance to the conditions described in the article."
(declare (type (integer 0 *) p q s))
(let ((M (* p q)) ;; M = p * q
(x[n] s)) ;; x0 = seed
(declare (type (integer 0 *) M x[n]))
#'(lambda ()
;; x[n+1] = x[n]^2 mod M
(let ((x[n+1] (mod (* x[n] x[n]) M)))
(declare (type (integer 0 *) x[n+1]))
;; Compute the random bit(s) based on x[n+1].
(let ((even-parity-bit (get-even-parity-bit x[n+1]))
(least-significant-bit (get-least-significant-bit x[n+1])))
(declare (type bit even-parity-bit))
(declare (type bit least-significant-bit))
;; Update the state such that x[n+1] becomes the new x[n].
(setf x[n] x[n+1])
(values x[n+1]
even-parity-bit
least-significant-bit))))))
;; Print the exemplary outputs.
(let ((bbs (make-blum-blum-shub :p 11 :q 23 :s 3)))
(declare (type (function () (values (integer 0 *) bit bit)) bbs))
(format T "~&Keys: E = even parity, L = least significant")
(format T "~2%")
(format T "~&x[n+1] | E | L")
(format T "~&--------------")
(loop repeat 6 do
(multiple-value-bind (x[n+1] even-parity-bit least-significant-bit)
(funcall bbs)
(declare (type (integer 0 *) x[n+1]))
(declare (type bit even-parity-bit))
(declare (type bit least-significant-bit))
(format T "~&~6d | ~d | ~d"
x[n+1] even-parity-bit least-significant-bit))))
References
Citations
- ^ a b Blum, Blum & Shub 1986, pp. 364–383.
Sources
- Blum, Lenore; Blum, Manuel; Shub, Michael (1983). "Comparison of Two Pseudo-Random Number Generators". Advances in Cryptology. Boston, MA: Springer US. doi:10.1007/978-1-4757-0602-4_6.
- Blum, L.; Blum, M.; Shub, M. (1986). "A Simple Unpredictable Pseudo-Random Number Generator" (PDF). SIAM Journal on Computing. 15 (2). Society for Industrial & Applied Mathematics (SIAM): 364–383. doi:10.1137/0215025. ISSN 0097-5397.
- Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (December 2004). "About Random Bits". CiteSeerX 10.1.1.90.3779.
{{cite journal}}
: Cite journal requires|journal=
(help) available as PDF and gzipped Postscript