# Tag Info

22

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

8

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

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

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

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

3

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

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

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