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.

I need to use ECDSA as the signing algorithm and SHA256 for hashing the message. I'm running into troubles verifying the signature calculated on two different platform (one is BouncyCastle, another one a C library for a microprocessor).

I figured out that BouncyCastle, in its ECDSASigner class, reduces the input message (which is supposed to be already the hash), in both, generateSignature() and verifySignature() using a helper function called calculateE(). In essence, this functions truncates the input message/hash to the bitlength of the curve's order $N$.

protected BigInteger calculateE(BigInteger n, byte[] message)
{
    int log2n = n.bitLength();
    int messageBitLength = message.length * 8;

    BigInteger e = new BigInteger(1, message);
    if (log2n < messageBitLength)
    {
        e = e.shiftRight(messageBitLength - log2n);
    }
    return e;
}

This reduction results from the fact that a SHA256 hash has 32 Bytes, whereas the size of $N$ is (for secp192r1) 192/8 = 24 Bytes.

What I don't understand:

  1. Do I have to use a curve with greater size of bitlength(N) for SHA256 hashes to be signed (e.g., secp256r1 or secp521r1)?
  2. Is the implementation in BouncyCastle wrong/imcomplete, or only applies to SHA-1 (160 b = 20 B <= 24 B)?
  3. Where is it documented/specified, how to “reduce” a hash of greater bitlength than that of the curve domain?
share|improve this question

2 Answers 2

up vote 2 down vote accepted

NIST FIPS 186-4 at the end of section 6.4 states that:

When the length of the output of the hash function is greater than the bit length of $n$, then the leftmost $n$ bits of the hash function output block shall be used in any calculation using the hash function output during the generation or verification of a digital signature.

In section 6.1 they define $n$ as the order of the generator, which makes the wording

leftmost $n$ bits

wrong. Although it's clear they meant the bit size of $n$.

Which means:

  1. You don't need a bigger curve
  2. BouncyCastle implementation looks correct
share|improve this answer
    
I don't need a bigger curve, but from pure security perspective I should use a "bigger" one, right? Because by truncating my hash I lose security (in terms of bits), as far as I understand? –  Christian Aug 5 at 13:56
    
@Christian The security level is limited to half the curve size. So with a 192 bit curve you get 96 bits of security. This is still infeasible to break, but you should consider upgrading to a 224 or 256 bit curve. –  CodesInChaos Aug 5 at 14:26
1  
@Christian The security level will be the minimum value between half of the digest size of your hash function and half of the size of the order of the curve. So for P-192 and SHA-256 you get 96 bits of security. If you want 128 bit of security you need (at least) P-256 and SHA-256 –  Ruggero Aug 5 at 15:03

Your options are:

  1. Use secp192r1 and truncate the hash. Then you have 96-bit security.
  2. Use secp256r1 and full SHA-256. Then you have 128-bit security.

Both elliptic curves and hashes usually* need to be twice the "effective security" bitlength. Even 96-bit security is most likely enough at the moment, but some estimates put it within reach in e.g. a few decades. In comparison, it is widely believed that 128-bit security is enough, period, unless/until quantum computers break ECC.

* "Usually", because if only preimage resistance is important, a hash function can be shorter.

share|improve this answer

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.