Re: Rabin vs. RSA/ElGamal

Ertugrul Soeylemez wrote:
daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) (06-03-05 20:23:36):
Encryption in Rabin's scheme is a bit faster than RSA (on the order of
50%), but not a lot faster. RSA encryption is already so fast that
for most applications, the speed difference between RSA encryption and
Rabin encryption probably is irrelevant.

For RSA or ElGamal you need exponentiation.

I am assuming that if you care about speed, you will use e=3 with RSA.
Why would you use a larger exponent? It conveys no known security
advantages and just needlessly slows down encryption.

For RSA with e=3, you use one squaring and one multiply. For Rabin, you
use one squaring. I would expect something on the order of a 2x difference.
But encryption is so fast with either scheme that I doubt it will be the
bottleneck for most applications.

This is a bit more difficult. You need to apply the Chinese Remainder
Theorem to find the four square roots of a number modulo a blum integer,
which in turn involves using the Extended Euklidean Algorithm to
calculate modular inverses.

Oh, come on. That's not a difficult optimization. If you call that
difficult, then you shouldn't be doing optimization of public-key
cryptography. People who really care about optimized implementations
of public-key crypto use far more obscure optimizations than that.

It's a lot slower than Rabin encryption,

The same is true of RSA, but that's not a fair statement, because
Rabin and RSA encryption are so fast that anything would be slower
than them. Eating a ham sandwich is a lot slower than Rabin encryption.

I urge you to put some real numbers on it. Go measure. How many
microseconds does it take to do a 1024-bit RSA encryption? Rabin
encryption? RSA decryption? Rabin decryption? How many times per
second does your application perform one of these operations? Until
you measure, quantitatively and concretely, you will be guessing,
and you risk making statements that make you look uninformed.

Theoretically RSA encryption is roughly only twice as fast as
ElGamal encryption

This is not accurate. Go measure it. I told you how to do it.

ElGamal decryption and RSA decryption are equally fast.

This is not true, either. Go measure.

What is a lot worse about ElGamal is that the ciphertext is twice the
size of the plaintext.

I presume you are familiar with the notion of hybrid cryptosystems?
For long messages, this is not accurate. The public-key cryptosystem
adds an additive overhead to message length, not multiplicative

Elliptic curves are faster still.

Possibly. I don't have enough background knowledge in this sector.

I'm telling you, elliptic curves are faster still. You can choose to
believe me, or to disbelieve me. If you aren't prepared to hear an
answer to your question, I can't see why you asked it.

Or, you can go measure for yourself, and not have to take anyone else's
work on it.

Well, as Tom already mentioned, Rabin is not fully deterministic. The
plaintext must be of a special form to avoid inconsistencies.

One can use Rabin in a way that eliminates these problems.
So long as you use Rabin in that way -- and why wouldn't you? --
there are no problems. So what's the problem?