Re: Rabin vs. RSA/ElGamal

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:

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

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.

Relevant Pages