# Re: Rabin vs. RSA/ElGamal

*From*: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)*Date*: Mon, 6 Mar 2006 06:07:14 +0000 (UTC)

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?

.

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

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

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

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

- Prev by Date:
**Re: Rabin vs. RSA/ElGamal** - Next by Date:
**Explaining One-time pads?** - Previous by thread:
**Re: Rabin vs. RSA/ElGamal** - Next by thread:
**Re: Rabin vs. RSA/ElGamal** - Index(es):