Tag Info

Hot answers tagged

27

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


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


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


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


2

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


1

Unfortunaltly NO! The factorization is a hard problem on which many cryptosystems or crypto-protocols are build, and is know as the IFP problem to opposite ti DLP (Discret Log Problem) and 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 an clever ...


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.



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