asymmetric HMAC

Question

validation of HMAC generated hash requires the key to be known to the validator. So its symmetric. What is the similer asymmetric solution other than SSL ? as I want the signature be smaller like an md5 hash. and the generation and validation procedure to be light. I was going through Rabin's Signature algorithm but couldn't find any Implementation or pseudo code ro follow.

Answer 1

The smallest asymmetric signatures come from elliptic curve cryptosystems like ECDSA. ECDSA signature schemes require signatures approximately four times the length of a symmetric cipher key of equivalent security. So a scheme comparable in security to 128-bit AES would have 512-bit signatures. That's the state of the art right now -- schemes with smaller signatures but equal or greater security are not known.

If you don't need security quite that high, you could use a 192-bit curve which would result in 384-bit signatures. You can go down to 320-bit signatures (160-bit curves) and still have security comparable to 80-bit symmetric ciphers. If you really don't particularly care about security, 112-bit curves can be used, providing 224-bit signatures that are about as difficult to break as DES.

The following curves are what I would recommend for each security level:

SecP112R1: 224-bit signatures, 56-bit security level
SecP128R1: 256-bit signatures, 64-bit security level
SecP160K1: 320-bit signatures, 80-bit security level
SecP192K1: 386-bit signatures, 96-bit security level
SecP224K1: 448-bit signatures, 112-bit security level
SecP256K1: 512-bit signatures, 128-bit security level

For each curve, the private key is the same size as the curve. Public keys (in compressed form) are one bit larger than the curve size. Signatures are twice the curve size. So with SecP256K1, private keys are 256-bits, public keys are 257-bits, and signatures are 512-bits. These are the minimum sizes for the raw binary values.

Caution: I would consider 160-bit curves the minimum for any purpose where security is a factor. Smaller curves might be suitable if keys are generated, used, and then thrown away in a small time frame. For long-term security, 256-bit curves should be used. The system as a whole should be evaluated by competent experts before it is relied upon.