# Re: Rabin vs. RSA/ElGamal

*From*: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)*Date*: Tue, 7 Mar 2006 05:28:01 +0000 (UTC)

Ertugrul Soeylemez wrote:

There is an attack against small exponents.

No, there isn't. You are confused.

If you're talking about raw (unpadded) RSA, then sure, there are

attacks if you use e=3. There are also attacks against raw (unpadded)

RSA if you use any other choice of e. So this does not demonstrate

a problem with e=3.

If you're talking about padded RSA (e.g., RSA-OAEP), then there

are no known attacks against small exponents.

This confusion is, sadly, widespread, no doubt partly due to the

confusion on the part of many textbooks between a trapdoor permutation

primitive (like raw, unpadded RSA) and an IND-CPA encryption scheme

(like RSA-OAEP, or other forms of padded RSA).

This is why most RSA implementations use larger values like 65537.

My impression is that most RSA implementations that use e=65537 do

so more out of ignorance than out of reasoned analysis. Maybe not all,

but a common pattern I hear, when I ask why they use e=65537, is the

confusion that the implementor thought there were known attacks against

e=3 (which, as I said above, is just a confusion).

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.

No, that's not true either. Sheesh.

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.

I agree.

Against RSA there is at least another attack: discrete

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

Actually, no, you are confused. RSA has nothing to do with the

discrete logarithm problem. (Incidentally, the discrete logarithm

problem in (Z/nZ)^* is provably at least as hard as factorization.)

I think what you meant is that there may be some other attack on

RSA that involves breaking the RSA Assumption without factoring --

e.g., that involves some way to take cube roots modulo n without

ever factoring n.

because most implementations use small public exponents like 65537.

No decent implementation that cares about speed would use RSA with e=65537.

If you care about speed, you use e=3. It's that simple.

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.

It's not true either in theory or in practice.

I don't know what you think "in theory" means, but it is not some

kind of excuse to make false statements. It is not true that "1+1=3

in theory".

You are confused if you think that the exponentiation RSA uses takes

the same amount of time as the exponentiation that El Gamal uses.

You are confused if you think that the time to perform an additional

multiplication makes any noticeable difference, compared to El Gamal's

exponentiation.

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.

And if pigs had wings, horses could fly. What kind of nonsense is this?

No one who cares about speed would do something so silly as to encrypt the

whole message with El Gamal.

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.

Whatever, dude. I answered your question, and I also provided you with

some extra bonus additional information, just in case it was helpful.

I'm sorry to hear that you found the extra information unhelpful or hard

to believe.

.

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

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

**Re: 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: 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):