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