Tag Info

7

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 form of $x_{i+1} = x^2_i \bmod N$. The initial seed, $x_0$, merely has to be co-prime to Blum primes $p$ and $q$ (where $N = p\cdot q$, making $N$ a Blum ...

5

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 modulus is called a Blum integer, which means $p,q \in \mathbb P$, $p \equiv q \equiv 3 \pmod 4$, and $N = p \cdot q$. There are a few other requirements, such ...

5

Short answer: knowing $p$ and $q$ allows building a more efficient generator, including one with random access. Further, for an adversary, at least if $p-1$ and $q-1$ can be factored, that allows finding a period, and at least if the generator allows random access past that, building a distinguisher. With secret seed $x_0$, the Blum Blum Shub generator ...

5

Summary: to a considerable degree, more computers speed up factorization of a given integer; but the expected time decreases significantly slower than the inverse of the number of computers used: we are in the area of sub-linear speedup. Some high-performance (but not the best) factorization algorithms, in particular ECM, enjoy near-linear speedup with the ...

4

Unfortunately NO! The factorization is a hard problem on which many cryptosystems or crypto-protocols are built, and is known as the IFP problem, compared to DLP (Discrete Log Problem) in intractability. Even in the case where $M= 10^{10}$ computers are available, you can't accelerate the resolution of the IFP by M, unless you invent a new and clever ...

4

I don't know of any implementations that use BBS. I hope no important system is using BBS. BBS is a poor choice for practical use. The only benefit it has is that it comes with some security proofs -- but it turns out that those proofs are useless for all practical instantiations of BBS (for realistic parameter settings), so they're pretty much irrelevant ...

3

I'm going to use the notation from here. I'm still not sure why one wants to handle $-1$ as a message, but anyways. Simple solution is that you simply define: if message is $-1$ set message to $1$ and the other way round when decrypting. Second point is that you can only encrypt messages from a message space with two elements (independent from how you name ...

3

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 a few aren't suitable for any cryptographic task. In some cases a PRNG will be not practical for use as a cipher. If you look at it in the pure form of a seed ...

3

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 paper then shows that (all modulo the QRA): Theorem 4: The generator is an unpredictable cryptographically secure pseudo-random sequence generator. Theorem 5: ...

3

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 random non-negative integer smaller than $N$. Define $x_{i+1}=x_{i}^2\bmod N$. For a request of $M=jk$ random bits, compute all $x_i$ up until at least $x_k$ and ...

2

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 large; for cryptographic application at least about 200 decimal digits. This was added in 15th September 2008 before that it has been 100 digits. So I would ...

2

I suggest you read the paper about the generator, because that question is answered there: A Simple Unpredictable Pseudo-random Number Generator, Blum, Blum, Shoup, 1986 They don't have any formal expression of what is called "state compromise extension" there, but they already state in the section 6. The $1/p$ generator is predictable on page 6 exactly the ...

2

Knowing $M$ is not enough to break Blum Blum Shub because the internal state of the random number generator, $x_i$, should never be revealed. Therefore, while you are correct that knowing the current state allows you to know the next (and all subsequent) states, a secure implementation of BBS should not reveal the internal state. For provable security, only ...

1

I am not aware of any implementation of this proposal, but it should be secure: Usually, when theoretically designing a cryptosystem, one assumes access to a good (pseudo)randomness source without precisely specifying its nature. It is certainly possible to use a Blum-Blum-Shub generator, but care must be taken that its modulus and initial state are chosen ...

1

Finding square roots modulo $M$ is difficult when $M$ is not prime. However, knowing the factors of $M$ lets one take the short cut of finding the roots modulo $p$ and $q$ (fast because they are prime), then using the Chinese Remainder Theorem to combine those to find roots modulo $M$. I'm not sure how/whether that breaks Blum Blum Shub, though.

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