The Blum Blum Shub generator is a deterministic Pseudo-Random Bit Generator with security demonstrably reducible to that of integer factorization.

learn more… | top users | synonyms

17
votes
2answers
1k views

Blum Blum Shub vs. AES-CTR or other CSPRNGs

Following on from D.W.'s comments on a previous question, what properties does Blum Blum Shub have that make it better / worse than other PRNGs? Are there significant implementation difficulties or ...
5
votes
2answers
719 views

How many bits can be safely extracted from the BBS generator at each step?

The Blum-Blum-Shub generator is a deterministic Pseudo-Random Bit Generator with security reducible to that of integer factorization. Setup: Secretly chose random primes $P$, $Q$, with $P\equiv ...
3
votes
2answers
154 views

Advantages to knowing $p$ and $q$ in Blum Blum Shub?

Do you gain any advantage by knowing the factorization of $M$ (over just knowing $M$ itself) in the Blum Blum Shub generator? The only advantage I see is being able to calculate the $i$-th number ...
3
votes
1answer
128 views

Why is $-1$ an illegal message in the Goldwasser-Micali Encryption Scheme

I'm not sure why in the Goldwasser-Micali encryption scheme with a Blum integer $N$, the message $-1$ is always a illegal message. Can you give me some direction for starting? What is illegal ...
2
votes
2answers
312 views

Is the Blum Blum Shub PRNG suitable to create initialization vectors?

Is it a good idea to use a Blum Blum Shub Generator to create my initialization Vector (IV) in AES-OFB (Output Feedback Mode)?
2
votes
1answer
69 views

Are factorization algorithms parallelizable?

I was reading about the Blum-Blum-Shub random number generator, and its security depends on the hardness of factoring very large numbers (like many things in crypto do). I'm just wondering, if I have ...
1
vote
1answer
87 views

Why is knowing M not enough to break Blum Blum Shub?

In Blum Blum Shub, the generator is $x_{n+1}={x_n}^2 \mod M$ where $M=p \cdot q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, knowing $p$ and $q$ is enough to break the system. But if I know ...
1
vote
2answers
65 views

If Blum Blum Shub is modified to use a prime modulus, is it still secure?

The definition of the Blum Blum Shub cryptographically secure pseudorandom number generator is $x=x^2 \mod N$ where $N=p \times q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, the security ...
1
vote
0answers
71 views

Exploration of Blum Micali Security By Seed Size

I'm new to cryptography and am most intrigued by mathematically based pseudo random number generators. With reference to the Blum Micali algorithm: $X_{i+1} = G^{X_i} \bmod P$ can security be ...
0
votes
2answers
76 views

Is BBS used for generation of keys for any modem cryptosystem?

Is there any (current) cryptosystem or digital signature or cryptographic primitive that uses the BBS PRG in order to generate its secret keys?
0
votes
0answers
241 views

Blum-Blum-Shub Cryptosystem

I am given $N$, which is Bob's encryption key. I was able to successfully factor $N$ into $N=p*q$. Alice encrypts a messages for bob and sends $a = [1,1,1,0,0,0,1,0,1,1,0,...]$ $b = 1545164156...$ ...