# Re: Rabin vs. RSA/ElGamal

*From*: Ertugrul Soeylemez <never@xxxxxxxxxxxxxx>*Date*: Tue, 7 Mar 2006 04:49:59 +0100

daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) (06-03-06 06:07:14):

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.

There is an attack against small exponents. This is why most RSA

implementations use larger values like 65537.

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.

I meant, it's a bit more difficult to tell something about its speed,

because it highly depends on the numbers themselves.

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.

It's not only the speed I'm talking about. Rabin may even be more

secure than RSA, because there is only one possible attack:

factorization. Against RSA there is at least another attack: discrete

logarithm. Those problems may be equivalent, but this is not proven.

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.

My OpenSSL version doesn't even measure ElGamal speed. Still, in theory

this is the case. In practise, RSA encryption is mostly a lot faster,

because most implementations use small public exponents like 65537.

ElGamal decryption and RSA decryption are equally fast.

This is not true, either. Go measure.

Again, I'm talking about theory. RSA and ElGamal both use one

exponentiation, but ElGamal requires an additional multiplication.

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

This is because the asymmetric encryption is only applied to a symmetric

key. If you encrypted the whole message with ElGamal, then you would

end up with a ciphertext twice of the size of the message.

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.

My question was, why people don't use Rabin, not what alternatives are

there. This is not an answer to my question.

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

work on it.

I know that ECC is "a lot better" (tm) than anything else. However, I

haven't learned it yet, so that's not really relevant to me. And it

also has nothing to do with my original question.

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?

Maybe you should read a thread, before posting to it. You are actually

repeating in short, what I have already stated elsewhere.

Regards.

.

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

**Re: Rabin vs. RSA/ElGamal***From:*Bodo Moeller

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

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

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

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

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

- Prev by Date:
**Re: Encrption query............question?** - Next by Date:
**Re: Encrption query............question?** - Previous by thread:
**Re: Rabin vs. RSA/ElGamal** - Next by thread:
**Re: Rabin vs. RSA/ElGamal** - Index(es):