Public-key Based Streamed Encryption?

Scott_F asks this thought provoking question: "Doing research on my thesis, I have come across many different encryption algorithms. The one thing I have not found is a public-key based stream encryption algorithm. Does one exist? If so, is it publicly available? If one does not exist, without going too far into the theory for the general readers' sake, is it viable? It should be from what I've found, but there may be circumstances that I've overlooked. Since it is stream encryption, there is no "look-ahead" so encryption can only be done a bit at a time. The algorithm could depend on the values of previous bits, but that would possibly leave those previous values with a weaker encryption. What would be desired would be a consistent security throughout the entire bit string. "

Comments

Use a hybrid system...

[Ageless]

Public key encryption is very slow (for all operations) so it is never used for bulk encryption. Instead, what you need to do is use a very fast secret key stream encryption algorithm (such as RC4) to do your actual data transfer and use the public key system to transfer the keys. It works like this with client A and server B:
A: generate a random, unguessable secret session key.
A: obtain B's public key
A: encrypt your secret key with B's public key
A: send the encrypted key to B
A: initialize the stream cipher with the session key
B: decrypt the encrypted key with my private key
B: initialize the cipher with the decrypted session key
A and B: begin data transfer.

Now, as far as feasability of using a public key system for stream transfer.. it's certainly possible but only in output feedback mode with a rather large block size. Also, it will be slow as to be useless. Your only other option is to invent a very fast public key cryptosystem... I wish you luck :)
By the way, the protocol I described above is very similar to what SSL and PGP use. The technical documents on those protocols would be good reading along with "Applied Cryptography" by Bruce Schnier

I am not a professional cryptographer...

[rjh]

... in fact, I don't even play one on TV.

The problem with streaming asymmetric encryption comes from the way asymmetric encryption works. Namely, you've got all these different numbers that all coalesce and interact to give the cipher security. The two numbers that cause the most problems with streaming are referred to as p and k. p is a prime number that's very, very large, and k is a number which is relatively prime to (p-1).

The value of p is a constant for all the bytes you want to encrypt. The value of k will change for each byte -- or at least it should change, if you're as rabidly paranoid about security as you should be.

If p is a few hundred digits long, then it is a nontrivial task to find k relatively prime to p-1. Right there is a huge bottleneck. You also have to do a lot of multiplication on extremely large numbers; this, too, causes a bottleneck. And since you'd have to do these tasks for each and every byte, it would become a huge tax on the processor in no time flat.

Then there's the problems of decrypting. At some point in the decryption process, the extended Euclidean algorithm (or one of its derivatives) must be used. This is another nontrivial algorithm, and it must be executed for every byte received.

So in short -- yes, it is possible to do streamed asymmetric algorithms. But it's such an enormous performance hit that it's almost universally a bad idea. Far better to use an asymmetric method to negotiate a random session key (Diffie-Hellmann key exchange is specifically designed just for this), and then use a very fast symmetric algorithm to encrypt the stream.

If I recall correctly, algorithms like Blowfish are something like three orders of magnitude faster than asymmetric algorithms like RSA or Diffie-Hellmann. It's significant.

I may be off somewhat on some of my statements; I don't have my usual crypto references handy. So take this with a grain of salt. :)

the first question to ask is why

[mwalker]

WHY do want public key based stream encryption? If, during the initiation of your stream, you use public key encryption to exchange a shared secret (let's call this a "stream key") which is generated from random noise, then you can use shared secret stream encryption from that point forward. All the trust advantages of public key encryption, with all the speed advantages of shared secret encryption.

So, for example, during a TCP handshake you use RSA to exchange a 2048 byte key. Then use your favorite symmetric cypher (3DES, IDEA, whatever) with this shared key to encrypt the stream!

I write stream encryption software for www.v-one.com. The method I've just described is roughly what we do, and what all of our competitors do. While public key stream encryption is certainly feasible, if you understood the preceding paragraph you'll understand why it hasn't been written.

More details available upon request,
-mwalker.