53
$\begingroup$

I'm signing very small messages using RSA, and the signature and public key are added to every message, which requires a lot of space compared to the actual content.

I'm considering switching to ECDSA, would this require less space with the same level of encryption? And is the verification performance in the same range as RSA?

Improve this question
$\endgroup$
2
  • $\begingroup$ ECDSA signatures are around 64 bytes $\endgroup$
    – CodesInChaos
    Commented Jul 12, 2012 at 19:46
  • 1
    $\begingroup$ @CodeInChaos That's shorter than RSA, but if the Public Key is larger, it doesn't save space ;) $\endgroup$
    – Maestro
    Commented Jul 12, 2012 at 19:54

2 Answers 2

Reset to default
49
$\begingroup$

I'm considering switching to ECDSA, would this require less space with the same level of encryption?

The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels. If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security level; the 192-bit ECDSA curve is probably a bit stronger); then the RSA signature and public key can be expressed in 128 bytes each (assuming that you'll willing to use a space-saving format for the public key, rather than using the standard PKCS format); the ECDSA signature would be 48 bytes, and the public key would be 25 bytes.

As you increase the required security level, the advantage tilts even more radically towards ECDSA; that's because you have to increase the RSA modulus size far faster than the ECDSA curve size to increase the security level.

And is the verification performance in the same range as RSA?

Well, no, ECDSA signature verification is slower than RSA (for reasonable security levels). That is the one place that RSA shines; you can verify RSA signatures rather faster than you can verify an ECDSA signature. According to this web page, on their test environment, 2k RSA signature verification took 0.16msec, while 256-bit ECDSA signature verification took 8.53msec (see the page for the details on the platform they were testing it). Now to be fair, this isn't quite an apples-to-apples comparison (256-bit ECDSA is probably a bit stronger than 2k RSA), but even if the difference isn't quite 50x, RSA is still faster.

I do have one question, though. You mention that you are including the RSA public key along with the signed message. Does that mean that the verifier uses that public key to verify the message? If so, how do you know that someone who wants to forge a message won't just provide his own public key along with the signature (signed using his private key)? That is, how does the receiver know that the public key he sees in the message is the one that was sent?

Improve this answer
$\endgroup$
8
  • $\begingroup$ "Does that mean that the verifier uses that public key to verify the message?" It is used to identify the senders, so you can add them to a white-list. If someone else signs the same (or a new) message, you can see that it wasn't from the same person you whitelisted. $\endgroup$
    – Maestro
    Commented Jul 12, 2012 at 20:35
  • 4
    $\begingroup$ @Joshua: Well, if you were concerned with message overhead, couldn't you replace the public key with some short identifier, and have the verifier map the identifier to the public key? If you could do this, you would cut the overhead for RSA about in half, without the hassle of using a different public key algorithm. $\endgroup$
    – poncho
    Commented Jul 12, 2012 at 20:43
  • 1
    $\begingroup$ Sounds like a slow ECC implementation. eBacs results seem to be a bit better. bench.cr.yp.to/results-sign.html $\endgroup$
    – CodesInChaos
    Commented Jul 12, 2012 at 21:45
  • $\begingroup$ @poncho Unfortunately not, because it's a decentral system (like email), so having a central authority where users would need to sign up to have their identifiers mapped to keys, will undermine the whole concept. $\endgroup$
    – Maestro
    Commented Jul 12, 2012 at 21:51
  • 1
    $\begingroup$ @Joshua: The hash would allow you to know when a key was the correct one, so you wouldn't have to trust anyone to provide it to you. If you didn't already have a needed key, you could obtain it by any method. (Retrieve it from a URL. Retrieve it from DNS. Retrieve it from a keyserver. Any method would do, no trust needed.) $\endgroup$
    – David Schwartz
    Commented Jul 13, 2012 at 15:35
2
$\begingroup$

For a 128 bit security level, you need 256 bit ECC. Compressed public keys need about 32 bytes, and signatures use 64 bytes.

The verification time depends a lot on the choice of curve, representation and implementation. Ed25519 Is supposed to be one of the fastest versions, especially if you use batch verification. But I'm not sure if it's possible to create a windows build of the optimized version.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It seems that ECC requires less space, but this paper (nicj.net/files/…) states "Thus, for applications requiring message verification more often than signature generation, RSA may be the better choice." And verification performance is critical in my case, so I will have to research how big the difference is. $\endgroup$
    – Maestro
    Commented Jul 12, 2012 at 20:17
  • $\begingroup$ Signing, verification, and key generation are all very fast in the Ed25519 implementation. $\endgroup$
    – joeforker
    Commented Jul 13, 2012 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.