Questions tagged [blum-blum-shub]
The Blum Blum Shub generator is a deterministic Pseudo-Random Bit Generator with security demonstrably reducible to that of integer factorization.
18
questions
0
votes
0answers
27 views
When will the random bit sequence start to repeat in pseudo random number generator
Let's say we have the Blum-Micali pseudorandom number generator.
from wikipedia:
Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ ...
1
vote
0answers
26 views
CSPRNG unique seeds and proving uniform output [closed]
I have two related questions concerning cryptographically secure pseudo random number generators.
My first question is as follows: are there conditions on the definition of cryptographically secure ...
0
votes
0answers
44 views
using non prime numbers in Blum Blum Shub or Blum Micali
I would like to use Blum Blum Shub, or Blum Micali methods as random number generators only. I am not interested in their encryption capabilities.
I was wondering, if I replaced the prime numbers ...
5
votes
1answer
381 views
Blum Blum Shub Pseudo-Random Generator Requirements
I am trying to understand the Blum Blum Shub pseudo-random generator originally described in A Simple Unpredictable Pseudo-random Number Generator
As best I can tell the requirements are:
For any $...
1
vote
1answer
132 views
Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG
In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ ...
1
vote
1answer
91 views
Stream cipher — Are all random bit generators suitable for stream cipher?
I learned the stream cipher using LFSR in the book. I wonder whether all random bit generators (i.e. BBS, Rabin generator) are suitable for stream cipher. I search using keywords "stream cipher" and "...
6
votes
1answer
460 views
How did SHA-1 'feed' Blum Blum Shub
One of the most (in)famous hardware derived random number generators was Lavarand (patent). It did it with funky lava lamps. An image of the lamps was hashed and fed into Blum Blum Shub (BBS) to ...
4
votes
1answer
244 views
Blum Blum Shub Hash
Will this algorithm make a cryptographically secure hash function? Can it be used to generate passwords? Is it secure enough for use as a MAC?
Divide the message into blocks.
The initial state is $h=...
6
votes
2answers
251 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
2answers
229 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
1answer
384 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
0answers
188 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
414 views
Is BBS used for generation of keys for any modern cryptosystem?
Is there any (current) cryptosystem or digital signature or cryptographic primitive that uses the BBS PRG in order to generate its secret keys?
3
votes
2answers
609 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
194 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 ...
25
votes
2answers
5k 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
2k 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 Q\...
2
votes
2answers
643 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)?
