Re: Rabin vs. RSA/ElGamal

tomstdenis@xxxxxxxxx (06-03-06 05:12:56):

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. In today's
implementations this is done by repeated squaring and addition. You
have to square as many times as the amount of bits in the exponent.
So the speed of the RSA encryption is O(e) = log_2(e), not counting
the modulo operations involved (which are even slower than the
multiplications). For Rabin you need a single square operation and
a single modulo operation, and possibly an additional hash function
step.

First off, learn the math. It's "square and multiply" and even then
people don't just do a binary approach.

I know the math. But even the best mathematicians make mistakes
sometimes. So do we all. I would really appreciate, if you could be a
bit more serious. What you are doing here in sci.crypt is just being an
annoying know-it-all. If you don't feel like talking to idiots like me,
then please just ignore me.


Second, RSA encryption is by far the least of your worries. It takes
so little time to accomplish that barely anyone includes it in
benchmark specs. What DOES takes the time is decryption.

By convention, yes, but not by definition. And you could as well choose
a (relatively small) private key and derive the public key from it,
making encryption far slower, but decryption a lot faster.

This also doesn't change the fact that Rabin encryption is still a lot
faster than both RSA encryption and decryption - no matter what your
keys are. You couldn't just take a small public exponent to make it
faster, because this reduces the security of RSA.


So comparing RSA decryption to Rabin encryption is nonsense specially
since Rabin decrypt is THE SAME SPEED AS RSA.

I'm talking about Rabin _encryption_. It _is_ faster than both RSA
operations.


Both RSA and Rabin encryption are much, much faster than El Gamal
encryption.

Practically yes, because mostly a very small public exponent is used
for RSA. Theoretically RSA encryption is roughly only twice as fast
as ElGamal encryption (a final multiplication is needed in ElGamal,
but that's not really worth mentioning, because this doesn't change
the asymptotic runtime). ElGamal decryption and RSA decryption are
equally fast. Again unlike RSA, ElGamal requires a final
multiplication.

This is nonsense. RSA encryption is orders of magnitude faster than
ElGamal encryption. ...

You are always confusing theory with practice. I'm talking about theory
here.


Elliptic curves are faster still.

Possibly. I don't have enough background knowledge in this sector.

Stick to the Integer schemes for now :-)

Yes, Mr. Smart. Probably I would be too dumb for ECC anyway.


Regards.
.

Relevant Pages

  • Re: Name this key exchange
    ... RSA is faster than DH at encryption and slower at decryption. ... Bob generates a secret by choosing a random number r and setting ...
    (sci.crypt)
  • Re: Sharing Encrypted Data
    ... > where D stands for decryption and E stands for encryption. ... You can use RSA directly or any ... You could then give your public key ... decryption functions are identical, differing only by the key they use. ...
    (sci.crypt.research)
  • Re: Symmetric encryption algorithm with group like properties
    ... >> Solutions that exist today are not as secure as they can be. ... I wouldn't expect more than PGP / GPG type encryption, ... > versions - with the key, protected by RSA encryption under a RSA public key ... > Alice needs a secure decryption mechanism to read her emails, ...
    (sci.crypt)
  • RE: rsa encrtyption
    ... It seems to work for her now and all we did was apply some Sql Server updates. ... My only guess was that the MS dll she used to apply the RSA encryption was ... According to the RSA encryption reference, I've performed some local tests, ... Export the machine-level RSA key container: ...
    (microsoft.public.dotnet.framework.aspnet.security)
  • RE: rsa encrtyption
    ... According to the RSA encryption reference, I've performed some local tests, ... Grant Read Access to the RSA Encryption Key: ... Export the machine-level RSA key container: ... Import the the machine-level RSA key container on the 2nd server: ...
    (microsoft.public.dotnet.framework.aspnet.security)