# Re: Rabin vs. RSA/ElGamal

*From*: Ertugrul Soeylemez <never@xxxxxxxxxxxxxx>*Date*: Mon, 6 Mar 2006 06:34:29 +0100

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

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

speed.

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

crypto.)

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.

Regards.

.

**Follow-Ups**:**Re: Rabin vs. RSA/ElGamal***From:*sillybanter

**Re: Rabin vs. RSA/ElGamal***From:*David Wagner

**Re: Rabin vs. RSA/ElGamal***From:*tomstdenis

**Re: Rabin vs. RSA/ElGamal***From:*tomstdenis

**Re: Rabin vs. RSA/ElGamal***From:*David Wagner

**References**:**Rabin vs. RSA/ElGamal***From:*Ertugrul Soeylemez

**Re: Rabin vs. RSA/ElGamal***From:*David Wagner

- Prev by Date:
**Re: Implementing One-way optimized SRP** - Next by Date:
**Re: Rabin vs. RSA/ElGamal** - Previous by thread:
**Re: Rabin vs. RSA/ElGamal** - Next by thread:
**Re: Rabin vs. RSA/ElGamal** - Index(es):