Re: Rabin vs. RSA/ElGamal

daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) (06-03-05 20:23:36):

You know RSA and ElGamal and their shortcomings, e.g. their poor

They are pretty fast. What application did you have in mind?

Actually any application, for which secure keys (i.e. at least 1024
bits) are necessary.

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. In today's implementations
this is done by repeated squaring and addition. You have to square as
many times as the amount of bits in the exponent. So the speed of the
RSA encryption is O(e) = log_2(e), not counting the modulo operations
involved (which are even slower than the multiplications). For Rabin
you need a single square operation and a single modulo operation, and
possibly an additional hash function step.

Rabin decryption is no faster than RSA decryption, as far as I know.
(Or am I wrong? I have no experience with implementing fast public-key

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. It's a lot slower than Rabin encryption,
but still faster than RSA/ElGamal decryption, because only modulo
operations are needed, while in RSA/ElGamal additional multiplications
are necessary.

Both RSA and Rabin encryption are much, much faster than El Gamal encryption.

Practically yes, because mostly a very small public exponent is used for
RSA. Theoretically RSA encryption is roughly only twice as fast as
ElGamal encryption (a final multiplication is needed in ElGamal, but
that's not really worth mentioning, because this doesn't change the
asymptotic runtime). ElGamal decryption and RSA decryption are equally
fast. Again unlike RSA, ElGamal requires a final multiplication.

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

Elliptic curves are faster still.

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

My question: How come that everyone still uses ElGamal or RSA?

Historical inertia, probably. Perhaps a bit of superior marketing for
RSA, too. Rabin seems superior to RSA in just about every context
I've ever seen.

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