Re: Probabilistic Encryption
: > 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. (Haven't looked at it personally). 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. Some of the things the guy said suggested maybe he does know what he's talking about, but his writing style isn't inspiring. Clue for the guy: other people haven't the foggiest idea about what has been going round in your head for the last year. Try to give some context and set the scene in more general terms before you dive into conjectures. Otherwise you risk sounding slightly detached from reality, as in the expression "So what color's the sky in _your_ world, then?"... It may well be you've something useful to say, but if you don't say it in the text one or two postings, you're in danger of slipping into my mental kill-file mode where I gloss over your postings without reading them properly. I suspect others read cpunks mail in a similar fashion. G
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. Perry
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
I hope we're not about to get the usual kiddy PRNG exor encryption lecture. A PRNG XOR-ed with a data stream is a perfectly good stream cipher, provided the PRNG is sufficiently strong. It's that sufficiently strong part that usually goes wrong. LFSR doesn't cut it (Linear Feedback Shift Register). Neither does LC (Linear Congruential). I should point out that these are both iterates of x_{i+1} = x_i * A + B (mod C) where the domain is Z_2[x] (polynomials with coefficients mod 2) for LFSR and Z (integers) for LC. Blum-Blum-Shub makes a very good stream cipher, even with just XOR. For those of you may have interpreted GT's comments as to disparage all PNRG-XOR combinations, I hope the above may help. Graham, you can read up on probabilistic encryption on page 406 of Schneier. In fact, it discusses the BBS generator in this context. Eric
participants (4)
-
gtoal＠an-teallach.com -
hughes＠ah.com -
Perry E. Metzger -
solman＠MIT.EDU