Re: Rabin vs. RSA/ElGamal

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

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.