Bases: sage.crypto.cryptosystem.SymmetricKeyCryptosystem
Linear feedback shift register cryptosystem class
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.crypto.cryptosystem.SymmetricKeyCryptosystem
Shrinking generator cryptosystem class
x.__init__(...) initializes x; see help(type(x)) for signature
The Blum-Blum-Shub (BBS) pseudorandom bit generator.
See the original paper by Blum, Blum and Shub [BlumBlumShub1986]. The BBS algorithm is also discussed in section 5.5.2 of [MenezesEtAl1996].
INPUT:
OUTPUT:
Here is a common use case for this function. If you want this function to use pre-computed values for \(p\) and \(q\), you should pass those pre-computed values to this function. In that case, you only need to specify values for length, p and q, and you do not need to worry about doing anything with the parameters lbound and ubound. The pre-computed values \(p\) and \(q\) must be Blum primes. It is your responsibility to check that both \(p\) and \(q\) are Blum primes.
Here is another common use case. If you want the function to generate its own values for \(p\) and \(q\), you must specify the lower and upper bounds within which these two primes must lie. In that case, you must specify values for length, lbound and ubound, and you do not need to worry about values for the parameters p and q. The parameter ntries is only relevant when you want this function to generate p and q.
Note
Beware that there might not be any primes between the lower and upper bounds. So make sure that these two bounds are “sufficiently” far apart from each other for there to be primes congruent to 3 modulo 4. In particular, there should be at least two distinct primes within these bounds, each prime being congruent to 3 modulo 4. This function uses the function random_blum_prime() to generate random primes that are congruent to 3 modulo 4.
ALGORITHM:
The BBS algorithm as described below is adapted from the presentation in Algorithm 5.40, page 186 of [MenezesEtAl1996].
EXAMPLES:
A BBS pseudorandom bit sequence with a specified seed:
sage: from sage.crypto.stream import blum_blum_shub
sage: blum_blum_shub(length=6, seed=3, p=11, q=19)
110000
You could specify the length of the bit string, with given values for p and q:
sage: blum_blum_shub(length=6, p=11, q=19) # random
001011
Or you could specify the length of the bit string, with given values for the lower and upper bounds:
sage: blum_blum_shub(length=6, lbound=10**4, ubound=10**5) # random
110111
Under some reasonable hypotheses, Blum-Blum-Shub [BlumBlumShub1982] sketch a proof that the period of the BBS stream cipher is equal to \(\lambda(\lambda(n))\), where \(\lambda(n)\) is the Carmichael function of \(n\). This is verified below in a few examples by using the function lfsr_connection_polynomial() (written by Tim Brock) which computes the connection polynomial of a linear feedback shift register sequence. The degree of that polynomial is the period.
sage: from sage.crypto.stream import blum_blum_shub
sage: from sage.crypto.util import carmichael_lambda
sage: carmichael_lambda(carmichael_lambda(7*11))
4
sage: s = [GF(2)(int(str(x))) for x in blum_blum_shub(60, p=7, q=11, seed=13)]
sage: lfsr_connection_polynomial(s)
x^3 + x^2 + x + 1
sage: carmichael_lambda(carmichael_lambda(11*23))
20
sage: s = [GF(2)(int(str(x))) for x in blum_blum_shub(60, p=11, q=23, seed=13)]
sage: lfsr_connection_polynomial(s)
x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
TESTS:
Make sure that there is at least one Blum prime between the lower and upper bounds. In the following example, we have lbound=24 and ubound=30 with 29 being the only prime within those bounds. But 29 is not a Blum prime.
sage: from sage.crypto.stream import blum_blum_shub
sage: blum_blum_shub(6, lbound=24, ubound=30, ntries=10)
Traceback (most recent call last):
...
ValueError: No Blum primes within the specified closed interval.
Both the lower and upper bounds must be greater than 2:
sage: blum_blum_shub(6, lbound=2, ubound=3)
Traceback (most recent call last):
...
ValueError: Both the lower and upper bounds must be > 2.
sage: blum_blum_shub(6, lbound=3, ubound=2)
Traceback (most recent call last):
...
ValueError: Both the lower and upper bounds must be > 2.
sage: blum_blum_shub(6, lbound=2, ubound=2)
Traceback (most recent call last):
...
ValueError: Both the lower and upper bounds must be > 2.
The lower and upper bounds must be distinct from each other:
sage: blum_blum_shub(6, lbound=3, ubound=3)
Traceback (most recent call last):
...
ValueError: The lower and upper bounds must be distinct.
The lower bound must be less than the upper bound:
sage: blum_blum_shub(6, lbound=4, ubound=3)
Traceback (most recent call last):
...
ValueError: The lower bound must be less than the upper bound.
REFERENCES:
[BlumBlumShub1982] | L. Blum, M. Blum, and M. Shub. Comparison of Two Pseudo-Random Number Generators. Advances in Cryptology: Proceedings of Crypto ‘82, pp.61–78, 1982. |
[BlumBlumShub1986] | L. Blum, M. Blum, and M. Shub. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing, 15(2):364–383, 1986. |