# Tag Info

30

Blum-Blum-Shub is a stream cipher: given a short key, it produces an effectively unlimited-length stream of pseudorandom bits. Other well-known examples of stream ciphers include AES-CTR and RC4. Blum-Blum-Shub gets mentioned a lot by non-expert cryptographers. I suspect this is because it comes with a "proof" of security, which sounds like a wonderful ...

9

BBS has a so-called "security proof" which shows it to be secure as long as the quadratic residuosity problem is hard; the latter is believed to be as hard as integer factorization, which is itself believed to be a hard to solve problem. Gee, the description of the quadratic residuosity problem on Wikipedia really lacks clarity. In simpler words, the ...

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

The choice or PRNG doesn't really matter much, as long as it's a decent one. I wouldn't use BBS because it's slow, and the security proof isn't too useful. The interesting question is rather, how to seed the PRNG with sufficient entropy. You need a sufficient amount of data that an attacker can't predict. I strongly recommend not doing this yourself, but to ...

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 ...

4

The direct answer to your question is in Koblitz and Menezes (Indocrypt 2006). They pointed out that, for practical parameters, one can produce only $1$ bit per iteration if one wants provable security. See Section 6 of the paper for the detail. Additional note: if you can change the assumption from the hardness of integer factoring, then you can produce ...

4

No, it is not a good idea to use the Blum Blum Shub Generator to generate an Initialization Vector for a block cipher operated in OFB mode. In this usage, one needs that the IV has negligible chance to match an earlier IV used with the same key. The exact requirement is that the IV has negligible chance to match an input to the block cipher used in ...

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

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 ...

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 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 ...

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.

1

See my answer to Blum Blum Shub vs. AES-CTR or other CSPRNGs, which cites references that provide detailed analysis of this question and answers this question for some specific examples. I see no point on repeating it here. The short summary: How many bits should you extract from BBS? None. In practice, you shouldn't be using BBS; you should be using ...

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