Blum-Blum-Shub generator

The Blum-Blum-Shub-Generator (BBS-Generator; also "s² mod n - Generator") is a pseudo-random number generator , developed in 1986 by Lenore Blum , Manuel Blum and Michael Shub . The system is used u. a. in cryptology in the design of complex-theoretical secure cryptosystems .

definition

The BBS generator is defined as a sequence through the iteration rule ${\displaystyle (s_{i})}$

${\displaystyle {\begin{aligned}&s_{0}&=s^{2}\;{\bmod {\;}}n\\&s_{i+1}&=s_{i}^{2}\;{\bmod {\;}}n\end{aligned}}}$

(denotes modthe remainder of the division; see modulo ).

The modulus is the product of two different prime numbers and , which are of the form , i.e. H. . A number with these properties is also called a Blum number . The start value is to be prime : . ${\displaystyle n=pq}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle 4k+3}$ ${\displaystyle p\equiv q\equiv 3\;({\bmod {\;}}4)}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle \operatorname {ggT} (s,n)=1}$

The parameter should also meet the following conditions so that it is as difficult to factor as possible and the generator is guaranteed to generate high-quality random numbers (see chapter "Security"): ${\displaystyle n}$ ${\displaystyle n}$

• ${\displaystyle n}$should be big enough; for cryptographic use at least about 200 decimal places.
• ${\displaystyle p}$and should be about the same size, but not too close together, for example . ${\displaystyle q}$ ${\displaystyle 2<p/q<1000}$
• ${\displaystyle p-1}$and as well as and should each have a large prime factor , greater than approx . ${\displaystyle p+1}$ ${\displaystyle q-1}$ ${\displaystyle q+1}$ ${\displaystyle {\sqrt[{4}]{n}}}$

Sometimes it is useful to calculate iteration steps of the generator all at once. This goes with the formula ${\displaystyle k}$

${\displaystyle s_{i+k}=s_{i}^{2^{k}\,{\bmod {\,}}\lambda (n)}\;{\bmod {\;}}n}$, whereby here , see LCM . ${\displaystyle \lambda (n)=\operatorname {kgV} (p-1,q-1)}$

Period length

Let be the set of coprime numbers in . ${\displaystyle Z}$ ${\displaystyle n}$ ${\displaystyle \{1,\dots ,n-1\}}$

The BBS generator works modulo on the set of residual squares . They are trivially in , since they are calculated as the remainder of the square of a number that is too prime. contains exactly a quarter of the numbers in . Each has exactly one root in : . The iteration rule of the generator therefore maps bijectively on . It is thus divided into several subsets , each forming a period of the generator. The period length is always a factor of , where is the Carmichael function . ${\displaystyle Q\subset Z}$ ${\displaystyle n}$ ${\displaystyle s_{i}}$ ${\displaystyle Q}$ ${\displaystyle n}$ ${\displaystyle Q}$ ${\displaystyle Z}$ ${\displaystyle x\in Q}$ ${\displaystyle Q}$ ${\displaystyle W_{x}=\{w\in Z\;|\;w^{2}\;{\bmod {\;}}n=x\}\;;\;|W_{x}\cap Q|=1}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q_{j}}$ ${\displaystyle \left|Q_{j}\right|}$ ${\displaystyle \lambda (\lambda (n))}$ ${\displaystyle \lambda }$

example

Be . Then is and are the remnants of the square . The roots of the square remnants are ${\displaystyle n=3\cdot 7=21}$ ${\displaystyle Z\!\,=\{1,2,4,5,8,10,11,13,16,17,19,20\}}$ ${\displaystyle Q\!\,=\{1,4,16\}}$

${\displaystyle W_{1}=\{1,8,13,20\}}$with , ${\displaystyle 1\in Q}$

${\displaystyle W_{4}=\{2,5,16,19\}}$where and ${\displaystyle 16\in Q}$

${\displaystyle W_{16}=\{4,10,11,17\}}$whereby . ${\displaystyle 4\in Q}$

Because , but and , is divided into the two periods and . ${\displaystyle 1\in W_{1}}$ ${\displaystyle 16\in W_{4}}$ ${\displaystyle 4\in W_{16}}$ ${\displaystyle Q}$ ${\displaystyle Q_{1}\!\,=\{1\}}$ ${\displaystyle Q_{2}\!\,=\{4,16\}}$

Proof of the period length

It is difficult to determine the parameters and such that a sufficient period length is guaranteed. When using the BBS generator in cryptography, this problem is often neglected because the probability of a period that is too short is very small. Absolute security cannot be achieved anyway, since an attacker could factor the module with luck, for example by trying out a few million randomly generated test participants. ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle n}$

If and are chosen such that: ${\displaystyle n}$ ${\displaystyle s}$

${\displaystyle \operatorname {ord} _{\lambda (n)/2}(2)=\lambda (\lambda (n))}$, and

${\displaystyle \operatorname {ord} _{n}(s_{0})=\lambda (n)/2}$,

then the period length is . ${\displaystyle \lambda (\lambda (n))}$

${\displaystyle \operatorname {ord} _{b}(a)}$denotes the order of the element of the prime residue class group : ${\displaystyle a}$ ${\displaystyle (\mathbb {Z} /b\mathbb {Z} )^{\times }}$

${\displaystyle \operatorname {ord} _{b}(a)=\min\{m\in \mathbb {N} ^{+}\;|\;a^{m}\equiv 1\;({\bmod {\;}}b)\}}$.

For efficient calculation it can be used that the element order according to Lagrange's theorem has to be a factor of the group order:

${\displaystyle \operatorname {ord} _{b}(a)\;|\;\phi (b)}$.

For this, the factorization of the group order must be known (see Euler's φ function ). ${\displaystyle \phi (b)}$

One must therefore construct so that the factorization of , and may be calculated are known or at a reasonable cost, as well as the factorization of the order reduced prime factors of and . This enables the required sizes and the factors of the group orders to be determined efficiently. With the binary exponentiation one can then calculate efficiently for all factors of . ${\displaystyle n}$ ${\displaystyle p-1}$ ${\displaystyle q-1}$ ${\displaystyle 1}$ ${\displaystyle p-1}$ ${\displaystyle q-1}$ ${\displaystyle a^{m}\;({\bmod {\;}}b)}$ ${\displaystyle m}$ ${\displaystyle \phi (b)}$

application

Generation of random bits

One or more random bits are extracted from each . In the simplest case one takes the least significant bit, that is ${\displaystyle s_{i}}$

${\displaystyle b_{i}=s_{i}\;{\bmod {\;}}2}$,

or the parity bit is calculated as : ${\displaystyle s_{i}}$

${\displaystyle b_{i}=\operatorname {bitnum} (s_{i})\;{\bmod {\;}}2}$.

The function returns the number of bits with the value 1 in the binary representation of . ${\displaystyle \operatorname {bitnum} (x)}$ ${\displaystyle x}$

Another possibility is to determine the position bit, which depends on the position of in the interval : ${\displaystyle s_{i}}$ ${\displaystyle [1,n-1]}$

${\displaystyle b_{i}={\begin{cases}1,&{\text{wenn }}s_{i}>\lfloor n/2\rfloor \\0,&{\text{wenn }}s_{i}\leq \lfloor n/2\rfloor \end{cases}}}$.

It is best, however, if the parity bit is determined from a few fixed bits . To do this, a constant z is selected in advance as a mask, which is about the same size as n and has an irregular, “random” binary representation, and it is calculated ${\displaystyle s_{i}}$

${\displaystyle b_{i}=\operatorname {bitnum} (s_{i}\wedge z)\;{\bmod {\;}}2}$.

Here referred to the bitwise AND operation . ${\displaystyle \wedge }$

Several random bits can be obtained from one . The inventors Blum, Blum and Shub suggested using the least significant bit and the position bit at the same time: ${\displaystyle s_{i}}$

${\displaystyle b_{2i}=s_{i}\;{\bmod {\;}}2,\quad b_{2i+1}={\begin{cases}1,&{\text{wenn }}s_{i}>\lfloor n/2\rfloor \\0,&{\text{wenn }}s_{i}\leq \lfloor n/2\rfloor \end{cases}}}$.

It can be shown that the BBS generator is cryptographically secure even if up to 8,000 bits are extracted from each . Usually the least significant bits are simply taken: ${\displaystyle a=\lfloor \log _{2}\log _{2}n\rfloor }$ ${\displaystyle s_{i}}$ ${\displaystyle a}$

${\displaystyle b_{ai+j}=\lfloor s_{i}\,/\,2^{j}\rfloor \;{\bmod {\;}}2\quad {\text{mit}}\;j=0,1,\ldots ,a-1}$,

or a little more elaborate, with "disjoint" masks : ${\displaystyle z_{j}}$

${\displaystyle b_{ai+j}=\operatorname {bitnum} (s_{i}\wedge z_{j})\;{\bmod {\;}}2\quad {\text{mit}}\;j=0,1,\ldots ,a-1\;;\quad j\neq k\Rightarrow z_{j}\wedge z_{k}=0}$.

Symmetrical cryptosystem

First, the BBS generator is used to convert a stream cipher . The secret key between sender and receiver is n and the generator's starting value s .

For example, the transmitter generates the sequence of s _i from n = 7 * 11 = 77 and s = 64 according to the rule given above . The associated pseudo-random number b _i results, for example, from the last bit of the respective value of s _i , i.e. H. b _i = s _i mod 2. To determine the ciphertext, the plain text (in the example: 0011) is XORed with the pseudo-random number sequence.

 Generierte Folge         15 71 36 64 …
 Pseudozufallszahlenfolge  1  1  0  0 …
 Klartext                  0  0  1  1
 Schlüsseltext             1  1  1  1

The receiver in turn determines the sequences s _i and b _i from the secret values n and s . With the help of the sent cipher text, the plain text is in turn calculated using XOR.

 Generierte Folge         15 71 36 64 …
 Pseudozufallszahlenfolge  1  1  0  0 …
 Schlüsseltext             1  1  1  1
 Klartext                  0  0  1  1

Asymmetric cryptosystem

The BBS generator is also suitable for implementing an asymmetric cryptosystem . This method was proposed by Manuel Blum and Shafi Goldwasser in 1984 and is also known as the Blum-Goldwasser cryptosystem . The secret key on the recipient's side are the prime factors p and q .

On the transmitter side, the calculations are carried out analogously to the symmetrical case above. In addition to the ciphertext , s _{i +1 is also} sent. Since the recipient does not know the start value, he uses the secret prime numbers p and q to recreate the sequence of pseudo-random numbers starting from the sent s _{i +1} up to the start value s . For the example this means that the recipient receives p = 11, q = 7, and s ₄ = 15. ${\displaystyle x_{0}\oplus b_{0},\ldots ,x_{i}\oplus b_{i}}$

${\displaystyle s_{i-1}=\left(up\cdot s_{i}^{\left(q+1\right)/4}{\bmod {q}}+vq\cdot s_{i}^{\left(p+1\right)/4}{\bmod {p}}\right){\bmod {n}}}$ With ${\displaystyle n=pq}$

The approach uses the Chinese remainder algorithm, a special case of the Chinese remainder theorem . The two unknowns u and v are dependent on the prime factors p and q and are initially determined using the extended Euclidean algorithm . Up + vq = 1 applies, i.e. 2 11-3 7 = 1 in the example. This results in the following processing.

s ₃ = (22 15 ² mod 7 - 21 15 ³ mod 11) mod 77

s ₃ = (22 * 1 - 21 * 9) mod 77 = 64

s ₂ = (22 64 ² mod 7 - 21 64 ³ mod 11) mod 77

s ₂ = (22 * 1 - 21 * 3) mod 77 = 36

s ₁ = (22 36 ² mod 7 - 21 36 ³ mod 11) mod 77

s ₁ = (22 * 1 - 21 * 5) mod 77 = 71

s ₀ = (22 71 ² mod 7 - 21 71 ³ mod 11) mod 77

s ₀ = (22 * 1 - 21 * 4) mod 77 = 15

s = (22 15 ² mod 7 - 21 15 ³ mod 11) mod 77

s = (22 * 1 - 21 * 5) mod 77 = 64

On the receiver side, analogously to the symmetrical case, the sequence of pseudo-random numbers is determined from the BBS generator sequence that has just been calculated backwards, and the plain text is ultimately generated by XORing the ciphertext.

However, an asymmetrical cryptosystem constructed in this way is not secure against active attackers, e.g. B. by an attack with freely selectable ciphertext (English: chosen-ciphertext attack ).

safety

The security of the BBS generator is based on the factorization assumption (FA). Anyone who can break BBS can factorize too, but this is considered practically impossible. Hence, BBS is safe.

Factoring Assumption (FA) : The probability that a fast factorization procedure successfully factors an integer n = pq decreases rapidly with increasing length of the factors p and q .

At the moment, no reliable statement can be made about how difficult factorization is. In other words, the question of an algorithm that performs the prime factorization into p and q in a reasonable time when any n is entered remains unanswered. Thus, the problem can only be assessed with the help of an assumption.

For concrete practical applications it is then required that, given the length of the prime factors, only a certain part can be factored in a certain time with the maximum available computer capacity and the best known factoring methods, e.g. For example, with a length of 1024 bits, ^2-50  % of all n are factored in a year.

Those who can factorize can also break BBS. Factoring allows the residual square assumption to be broken, which allows the pseudorandom sequence to be predicted.

Quadratic residues assumption (QRA) (English: quadratic residuosity assumption ): It is difficult (in terms of time-consuming), of a given number to determine whether it is a quadratic residue in a residue class ring is d. H. whether there is a number such that is. Like the FA, the QRA has not been proven. ${\displaystyle a}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle b}$ ${\displaystyle a\equiv b^{2}{\pmod {n}}}$

Two points make this test difficult. First, in a residue class ring there are multiple roots to a given number. So have z. As in the figures 1 and 3, the same squares: . Second, one is only interested in squares that are themselves squares. This fact can be illustrated by the definition of the BBS generator sequence. ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$ ${\displaystyle 1^{2}\equiv 3^{2}\equiv 1{\pmod {4}}}$

In summary, the following applies: The security of the BBS generator is equivalent to the factorization assumption.

Individual evidence

1. ^ Andrey Sidorenko and Berry Schoenmakers: Concrete Security of the Blum-Blum-Shub Pseudorandom Generator . In: Cryptography and Coding 2005 . 2005, p. 355-375 ( tue.nl [PDF]).

literature

• Lenore Blum, Manuel Blum, and Michael Shub: A Simple Unpredictable Pseudo-Random Number Generator , SIAM Journal on Computing, Volume 15, No. 2, Pages 364-383, May 1986.
• Lenore Blum, Manuel Blum, and Michael Shub: Comparison of two pseudo-random number generators , Advances in Cryptology: Proceedings of Crypto '82.
• Martin Geisler, Mikkel Krøigård, and Andreas Danielsen: About Random Bits , December 2004. As PDF and Gzipped Postscript .