7 votes
Accepted

How did SHA-1 'feed' Blum Blum Shub

I thought that the seed for BBS was computed via prime multiplication. This is not how BBS works. To help better understand the seed, it's necessary to explain BBS. Blum Blum Shub is realized in the ...
forest's user avatar
  • 15.2k
6 votes
Accepted

Blum Blum Shub Pseudo-Random Generator Requirements

Your understanding of the requirements are correct. To elaborate, the first requirement you specify can be explained as taking the parity of $x_i$. Also, the two primes are called Blum primes and the ...
forest's user avatar
  • 15.2k
4 votes
Accepted

How big does M need to be in Blum Blum Shub?

The usual definition for the Blum-Blum-Shub (BBS) generator goes as follows: Let $N$ be a Blum-Integer of unknown factorization. Let $j$ be the "extraction rate". Let $x_0$ be a uniformly ...
SEJPM's user avatar
  • 45.9k
4 votes
Accepted

Blum Blum Shub Hash

The authors of the original algorithm (1) shows that the security of the $x^2 \bmod N$generator as a pseudorandom number generator (PRG) can be reduced to the quadratic residuosity problem. The ...
Chris's user avatar
  • 809
3 votes
Accepted

Stream cipher -- Are all random bit generators suitable for stream cipher?

The requirements for cryptographically secure pseudo random number generator and those for a stream cipher are essentially the same. Obvious not all PRNG are secure, LFSR and mersenne-twister to name ...
Meir Maor's user avatar
  • 11.8k
3 votes
Accepted

Period of Blum-Blum-Shub

Define1 Blum-Blum-Shub generator's output as $b_i=x_i\bmod 2$ with $x_{i+1}={x_i}^2\bmod n$ for $i\ge0$, $n=p\,q$ with $p$ and $q$ distinct odd primes. Unless otherwise stated we do not assume $p\...
fgrieu's user avatar
  • 140k
2 votes

Significance of having remainder $3$ when divided by $4$ for both $p$ and $q$ in BBS

This is in order to maximise the state space of the generator after multiple steps. After $s$ steps, the BBS generator will have state $i^{2^s}\mod N$ where $i$ is the initial seed and $N$ is the ...
Daniel S's user avatar
  • 23k
2 votes

How big does M need to be in Blum Blum Shub?

I only found this: n sollte hinreichend groß sein; für kryptografische Anwendung mindestens etwa 200 Dezimalstellen. (German Wikipedia) which translated means as much as n should be sufficiently ...
secf00tprint's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible