Stream Cryptosystems#
- class sage.crypto.stream.LFSRCryptosystem(field=None)#
Bases:
SymmetricKeyCryptosystem
Linear feedback shift register cryptosystem class
- encoding(M)#
- class sage.crypto.stream.ShrinkingGeneratorCryptosystem(field=None)#
Bases:
SymmetricKeyCryptosystem
Shrinking generator cryptosystem class
- encoding(M)#
- sage.crypto.stream.blum_blum_shub(length, seed=None, p=None, q=None, lbound=None, ubound=None, ntries=100)#
The Blum-Blum-Shub (BBS) pseudorandom bit generator.
See the original paper by Blum, Blum and Shub [BBS1986]. The BBS algorithm is also discussed in section 5.5.2 of [MvOV1996].
INPUT:
length
– positive integer; the number of bits in the output pseudorandom bit sequence.seed
– (default:None
) if \(p\) and \(q\) are Blum primes, thenseed
is a quadratic residue in the multiplicative group \((\ZZ/n\ZZ)^{\ast}\) where \(n = pq\). Ifseed=None
, then the function would generate its own random quadratic residue in \((\ZZ/n\ZZ)^{\ast}\). If you provide a value forseed
, then it is your responsibility to ensure that the seed is a quadratic residue in the multiplicative group \((\ZZ/n\ZZ)^{\ast}\).p
– (default:None
) a large positive prime congruent to 3 modulo 4. Bothp
andq
must be distinct. Ifp=None
, then a value forp
will be generated, where0 < lower_bound <= p <= upper_bound
.q
– (default:None
) a large positive prime congruence to 3 modulo 4. Bothp
andq
must be distinct. Ifq=None
, then a value forq
will be generated, where0 < lower_bound <= q <= upper_bound
.lbound
– (positive integer, default:None
) the lower bound on how small each random primes \(p\) and \(q\) can be. So we have0 < lbound <= p, q <= ubound
. The lower bound must be distinct from the upper bound.ubound
– (positive integer, default:None
) the upper bound on how large each random primes \(p\) and \(q\) can be. So we have0 < lbound <= p, q <= ubound
. The lower bound must be distinct from the upper bound.ntries
– (default:100
) the number of attempts to generate a random Blum prime. Ifntries
is a positive integer, then perform that many attempts at generating a random Blum prime. This might or might not result in a Blum prime.
OUTPUT:
A pseudorandom bit sequence whose length is specified by
length
.
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
andq
, and you do not need to worry about doing anything with the parameterslbound
andubound
. 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
andubound
, and you do not need to worry about values for the parametersp
andq
. The parameterntries
is only relevant when you want this function to generatep
andq
.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 [MvOV1996].
Let \(L\) be the desired number of bits in the output bit sequence. That is, \(L\) is the desired length of the bit string.
Let \(p\) and \(q\) be two large distinct primes, each congruent to 3 modulo 4.
Let \(n = pq\) be the product of \(p\) and \(q\).
Select a random seed value \(s \in (\ZZ/n\ZZ)^{\ast}\), where \((\ZZ/n\ZZ)^{\ast}\) is the multiplicative group of \(\ZZ/n\ZZ\).
Let \(x_0 = s^2 \bmod n\).
For \(i\) from 1 to \(L\), do
Let \(x_i = x_{i-1}^2 \bmod n\).
Let \(z_i\) be the least significant bit of \(x_i\).
The output pseudorandom bit sequence is \(z_1, z_2, \dots, z_L\).
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
andq
: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 [BBS1982] 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.arith.misc 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