Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For a protocol where the server presents its signature to prove authenticity (e.g. IKE/SIGMA/STS with only one party authenticated), it's essential that the signing is extremely cheap, while verification can be almost arbitrarily expensive.

RSA appears to be the worst alternative, but what about DSA vs. ECDSA? Is there some other signing algorithm that could be even better (i.e. consume even less CPU to calculate)?

share|improve this question
    
ECDSA is rather cheap. Personally I'd go with Ed25519 for signatures, which has a easily available high performance implementations. –  CodesInChaos Jul 5 '13 at 7:29
    
But I don't really like using signatures for transport encryption since it weakens deniability. I prefer EC-Diffie-Hellman, even though it's more expensive than signing. –  CodesInChaos Jul 5 '13 at 7:32
    
@CodesInChaos What do you mean? Signing is not used for encrypting data in SIGMA/STS. –  Nuoji Jul 5 '13 at 7:54
    
I mean that I don't like using signatures to authenticate a side in a transport security protocol, like TLS. I prefer using DH for that. DH is a bit slower, but it offers stronger deniability. –  CodesInChaos Jul 5 '13 at 8:02
    
@CodesInChaos what sort of scheme do you propose? –  Nuoji Jul 5 '13 at 8:10
show 4 more comments

2 Answers

The BLS pairing based signature requires only one exponentiation, and verification requires a pairing computation. However, it can only sign group elements, and hashing to them is a bit painful.

share|improve this answer
1  
ECDSA should be faster than BLS, since it can use a special prime for the finite field arithmetic. And if you need short sigatures, Zhang/Safavi-Naini/Susilo should be faster than BLS since it uses a fixed point multiplication. –  Conrado PLG Jul 5 '13 at 12:03
add comment

From these three, ECDSA is faster - it does arithmetic with smaller numbers, and is thus faster. (RSA verification is faster than ECDSA, even though it uses larger numbers, because it computes a exponentiation by a small number.)

Still, elliptic curve Schnorr signature should be around 5-10% faster than ECDSA (or even more in a side-channel resistant implementation) since it does not require an inversion modulo the curve order. And as mentioned, there is also Ed25519, which uses a special, non-standard curve in order to be more efficient.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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