Blum Blum Shub

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. Application, the system finds, inter alia, in cryptology in design computationally secure cryptosystems.

• 3.1 generating random
• 3.2 Symmetric Cryptosystem
• 3.3 Asymmetric Cryptosystem

Definition

The BBS generator is defined as a sequence by the iteration

( here referred to mod the remainder; see modulo).

The module is the product of two distinct prime numbers and that are of the form, i.e.. A number with these properties is called Blum number. The starting value is to be coprime.

The parameters should also satisfy the following conditions, making it as difficult as possible to factorize and the generator ensures high quality random numbers generated (see chapter "Safety"):

• Should be sufficiently large; for cryptographic application at least about 200 decimal places.
• And should be approximately equal sized, but not too close together, about.
• And, as well, and should always have a large prime factor greater than about.

Sometimes it is convenient to calculate iteration of the generator at one time. This goes with the formula

Period length

Be the quantity of prime numbers in.

The BBS generator operates on the set of residues modulo square. They are trivially in, since they are calculated as the remainder of the square of a prime number too. contains exactly one quarter of the numbers in. Each has exactly one root in. The iteration of the generator thus forms bijective onto. Thus divided into a plurality of subsets, each of which forms one period of the generator. The period length is always a divisor of, the Carmichael function.

Example

Be. Then the square and radicals. The roots of the quadratic residues are

Because, however, and is divided into the two periods and.

Proof of period length

It is difficult to determine the parameters and so that a sufficient period length is guaranteed. When using the BBS generator in cryptography, this problem is often neglected, because the probability of too short period is very small. Absolute safety can not be achieved anyway, because an attacker could factor the modulus with happiness, as by trying several million sample divider randomly generated.

When and are chosen such that:

Then is the period length.

Denotes the order of the element of prime residue class group:

For efficient computation can be exploited that the element order, according to the set of Lagrangian must be a divisor of the group order:

For the factorization of the group order must be known ( see Euler's φ - function).

You have to construct so therefore, that the factorizations are from and known or can be calculated with reasonable effort, as well as the factorization of the reduced order prime factors of and. Thus, the required sizes and the factors of group orders can be determined efficiently. With the binary exponentiation can then calculate each for all divisors of efficiently.

Application

Generating random

One or more random bits are extracted from each. In the simplest case, one takes the least significant bit, in other words

Or to calculate the parity bit to:

The function returns the number of bits with the value 1 in the binary representation of.

A further possibility is to determine the positional bits, which depends on the position of the interval:

It is best, however, if the parity bit is determined by some fixed chosen bits. This, you select in advance a constant z as a mask, which is about the size of n and has an irregular, " random " binary representation, and calculated

It denotes the bitwise AND operation.

For one, you can get several random bits. The inventors Blum, Blum and Shub have suggested early on to use the least significant bit position bit and the same time:

One can show that the BBS generator cryptographically even then it is still safe when extracting up to bits from each. Most significant bits are simply taken:

Or something more elaborate, with " disjoint " masks:

Symmetric Cryptosystem

First, the BBS generator is used to implement a stream cipher. When secret keys between the transmitter and the receiver are used n and the initial value s of the generator.

For example, the transmitter generates n = 711 = 77 and s = 64 according to the procedure indicated above the sequence of si. The corresponding pseudo-random number bi results, for example from the last bit of the value of si, that is, bi = si mod 2 To determine the ciphertext, the plaintext is (in this example 0011) XORed with the pseudo- random number sequence.

Generated sequence 15 71 36 64 ...   Pseudo-random number sequence 1 1 0 0 ...   Plaintext 0 0 1 1   Key text 1 1 1 1 The receiver determines its part n of the secret values ​​s and the consequences of si and bi. With the help of over ended ciphertext is again calculated by XOR the plaintext.

Generated sequence 15 71 36 64 ...   Pseudo-random number sequence 1 1 0 0 ...   Key text 1 1 1 1   Plaintext 0 0 1 1 Asymmetric Cryptosystem

To implement an asymmetric crypto system, the BBS generator is also suitable. This method was proposed by Manuel Blum and Shafi Goldwasser 1984 and is also referred to as the Blum - Goldwasser cryptosystem. The secret key at the receiver are the prime factors p and q.

On the transmitter side, the calculations run analogously to the above symmetric case. In addition to the key text is still sent si 1. Since the receiver does not know the initial value, it forms using the secret prime numbers p and q, the result of the pseudo-random numbers on the basis of Si 1 sent to the start value s back. For example, this means the recipient will be p = 11, q = 7, and s4 = 15

The approach makes use of the Chinese Remainder algorithm, a special case of the Chinese remainder theorem. The two unknowns u and v are the prime factors p and q dependent and are determined at the beginning by means of the extended Euclidean algorithm. Where up vq = 1, that is 2.11 -3 · 7 = 1 in the example. This results in the following execution.

Receiver side, the result of the pseudo-random numbers will be similar to the symmetric case of the newly calculated backwards BBS generator sequence determines and ultimately generated by XORing the ciphertext of the plaintext.

However, a so constructed asymmetric cryptosystem is not secure against active attackers, such as by an attack with freely selectable ciphertext (English: chosen - ciphertext attack).

Security

The security of the BBS generator based on the factoring assumption (FA). Anyone who can break BBS can also factorize, but what is considered to be virtually impossible. Consequently, BBS is safe.

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

At present, no reliable statement can be made, how hard is factorization. In other words, the question of an algorithm which performs in an acceptable time for any input n is the prime factorization in p and q, remains unanswered. Thus, the problem can only be estimated using an assumption.

For concrete practical applications, it then requests that for a given length of the prime factors only a certain part can be factorized in a given time with maximum available computing capacity and the best known factorization, eg, with a length of 1024 bits 2-50 % of all n factored in a year.

Who can factorize, can also break BBS. Factoring allows the breaking of the quadratic -residue assumption, which allows to predict the pseudo-random sequence.

Quadratic -residue assumption ( QRA ) (English: quadratic residuosity assumption ): It is difficult (in the sense of consuming ), to be decided by a given number, if it is a square residue in a residue class ring, ie whether there is a number such that. The QRA is like the FA not proven.

Two points complicate this test. First, there is a residue class ring several roots to a given number. Thus, for example, in the figures 1 and 3, the same squares. Second, we are interested only for such squares are squares themselves. This fact can explain by means of the definition of the BBS generator sequence.

In summary, therefore: the security of the BBS generator is equivalent to factoring.