Graham Toal says:
How secure do you guys think Probabilistic encryption using a BBS generator is? It looks like its every bit as good for key exchanges as RSA and somewhat better because of its speed.
The technique you mention is not one I've heard of. What is a BBS generator? Could you please explain?
BBS is Blum-Blum-Shub, a cryptographically strong RNG I believe.
Ah, the Blum-Blum-Shub generator is familiar to me. However, how can you possibly use this for key exchange?
How he plans using this in some way to get the effect of an RSA public key system I have no idea. I hope we're not about to get the usual kiddy PRNG exor encryption lecture.
Ditto.
Well it is based on a PRNG exor, but the hardness of the encryption is based on the hardness of factoring the modulus used in the BBS RNG so I don't think you need to give me a "kiddy" lecture. (And I'm not using it for authentication, something which I belive is necessarily weak in any cypher being encrypted and decrypted via exor) I first saw a useful version of this in Schneier although I had previously seen versions that generated ciphers twice as large as the plaintext (which are uninteresting to me since I'm working ona VERY bandwidth conscious application). Here is how it works: First, choose two large prime numbers that are one less than a multiple of four. Since the security of this algorithm is based on the difficulty of factoring, I guess hard primes would be nice but I don't know if it really matters. Next choose a random number. Since you only need one random number, you probably don't need it to be very secure, but just in case its a good idea. In each iteration of a BBS you modify the seed by the following operation: seed(new) = (seed(old))^2 mod n [n is the product of your primes]. Throw your seed in there, if you question its security iterate it once before using any numbers. If your seed has 2^n bits, the lowest n bits will be randomly generated bits that are sufficiently secure for any cryptographics application you can think off. Exor the the stream of random bits with the stream of plaintext and append the final seed and you get your cyphertext. NOW, in order to remove the cypher, you need to figure out what the initial seed was. For a BBS generator, the only way you can do that is by factoring the modulus. The private key then, is the two factors. The public key is the modulus n. Clearly you can't authenticate by this, but there are much better algorithms for that anyway. What this provides is a public key system based on the hardness of factoring that is faster than RSA and apparently not covered by the RSA patent. (although I've asked for opinions on this last point in another post) I really believe that this is secure, but I wanted opinions before I implemented it as the algorithm users can use when they want to say "screw you RSADSI". Cheers, Jason W. Solinsky