How do I generate a challenge for elliptic curve signing using NIST standards?

Basically, NIST FIPS 186-4 describes a standard for generating some message that will be signed by an elliptic curve private key. However, I'm having difficulty interpreting how this message should look.

To give more context, with RSA, I've been attempting to follow PKCS #1 v1.5, so I'm basically doing pad(sha1(crypto.randomBytes(256)), which I believe creates a sufficiently random challenge of appropriate length in the case of RSA. (If I'm wrong here, please let me know that as well).

What are the discrete steps in the case of ECC? (I'm trying to follow B.5.1 Per-Message Secret Number Generation Using Extra Random Bits and B.5.2 Per-Message Secret Number Generation by Testing Candidates of the publication above).

In this method, a random number is obtained and tested to determine that it will produce a value of k in the correct range. If k is out-of-range, another random number is obtained (i.e., the process is iterated until an acceptable value of k is obtained.

So in plain English looking at the publication, it appears I do the following to create a challenge, k:

1. Find the bit length N of the public key
2. Generate a string of N random bits
3. Convert the string of random bits to a non-negative integer c (using the method for bit-to-string conversion in the same publication)
4. If c is greater than n-2, start over...
5. k = c + 1

Make sure k and the inverse of k are within the limits [1, n–1].

However, there doesn't seem to be any hashing going on. In the context of RSA, I've been reading you should always hash this random bit string before signing it (and of course, we must pad it appropriately so the message is the correct size). Am I missing something in the case of ECC? (Of course, I could theoretically just send any random message to be signed, but I want to follow some standard for the challenge, and it looks like NIST is the way to go...)

• Actually, the reason we pad in RSA is not to make sure that the message is the correct size; instead, it's to avoid certain forgery attacks that can occur if we aren't careful to do it correctly. – poncho Aug 1 '16 at 21:32
• @poncho thanks for correcting me. However, I'm curious to know, the PKCS1 v1.5 for padding looks deterministic... Is this just in the case of that specific standard? We don't need to go on too much of a tangent here since it's irrelevant to the actual question :) – Josh Beam Aug 1 '16 at 21:44
• Actually, PKCS1 v1.5 specifies two different padding methods, one determanistic (RSASSA-PKCS1-v1_5), and one which is probabilistic (RSASSA-PSS). – poncho Aug 1 '16 at 22:35

I believe you're misunderstanding how ECDSA works.

When you sign a message with RSA, you pad out the message somehow; some padding methods are determanistic, and some are randomized. However, once you get this padded message, you present it to the underlying RSA private operation, which is entirely determanistic.

However, ECDSA isn't like that. Instead, the ECDSA private operation selects a value k; this value k is not the message being signed, instead it's a random value (and there are known attacks that can occur if it's biased; that's why FIPS 186 goes into such detail about exactly how you do it - if you ignore their advice without knowing what you're doing, well, there be dragons here).

Now, once you have the value k, you can take the message (actually, the hash of the message), and then present that to the ECDSA signature operation to generate the signature.

So, with ECDSA, there is a hash involved; however it's the message that is hashed, not k.

• Thank you very much for the response! Give me a minute to read this over a few times to make sure I understand it correctly... – Josh Beam Aug 1 '16 at 21:42
• I guess I'm a bit confused. Not sure how familiar you are with Node.js (that's what I'm using here), but what message do I generate and send to some method privateKey.sign(message)? Just some random bytes? (Using, say, crypto.randomBytes(256)). Or should I hash the message myself first? I understand this is the cryptography forum so maybe code examples are out of context here. – Josh Beam Aug 1 '16 at 23:14
• @JoshBeam: I'm unfamiliar with Node.js, but if you're using a crypto library, presumably it'll take care of j; all you need to do is give it the message (or the hash - look at the crypto library documentation to find out which) – poncho Aug 2 '16 at 0:42