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 am trying to learn about the Elliptic Curve Digital Signature Algorithm (ECDSA) by verifying the results in some example calculations. I found a PDF of example ECDSA calculations from NIST here: http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ECDSA_Prime.pdf

In the section "Example of ECDSA with P-256", NIST gives two large hex numbers K and Kinv, which I presume are multiplicative inverses of eachother in the prime field of the P-256 curve. I tried to verify that K * Kinv is equal to 1 (in modulo arithmetic) but I was unable to; I got a really large number instead of 1.

Could someone check my relatively simple work and tell me what I am doing wrong? Or could someone verify it in their own way and tell me how they verified it?

Here is the excerpt from ECDSA_Prime.pdf I am looking at:

============================================================== 
Signature Generation 
msg is "Example of ECDSA with P-256" 
Hash length = 256 
...
K is 
7A1A7E52 797FC8CA 
AA435D2A 4DACE391 58504BF2 04FBE19F 14DBB427 FAEE50AE 
...
Kinv is 
62159E5B A9E712FB 
098CCE8F E20F1BED 8346554E 98EF3C7C 1FC3332B A67D87EF

I found the prime value $p$ that defines the field for curve P-256 in NISTReCur.pdf. I multiplied K and Kinv together in Ruby, taking advantage of that language's automatic handling of very large integers. Here is my Ruby code:

# From http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
# in the section entitled "P-256"
nist_p = 11579208921035624876269744694940757353008614_3415290314195533631308867097853951

# From http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ECDSA_Prime.pdf
# in the section entitled "Example of ECDSA with P-256"
nist_k = 0x7A1A7E52_797FC8CA_AA435D2A_4DACE391_58504BF2_04FBE19F_14DBB427_FAEE50AE 
nist_kinv = 0x62159E5B_A9E712FB_098CCE8F_E20F1BED_8346554E_98EF3C7C_1FC3332B_A67D87EF

puts (nist_k * nist_kinv) % nist_p    # expect to get 1, but did not

Note that the underscores are just spacers between the digits to make these long numbers more readable; they can be removed without affecting the program.

This code outputs the following number, even though I would expect it to output 1:

44876559229634927483363577082941808653359045812660811236387870057706848524951

I tried reversing the order of bytes in the NIST hex numbers and I also tried reversing the order of the 32-bit chunks, but neither yielded the correct result.

What am I doing wrong here? Am I using the wrong value of $p$ for the P-256 curve? Is my understanding of Kinv incorrect? Did NIST miscalculate Kinv?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

You are using the wrong value as the modulus; you ought to be using the value $r$ (which is also listed in the document).

$p$ is the characteristic of the field that the elliptic curve you're using is defined on. In this case, we're not interested in that; instead what we're interested in is the order of the curve, that is, that value $r$ such that $rP = 0$ for all points $P$ on the curve (note: strictly speaking, we're interested in the order of the generator point, however in this case, that's the same). That value $r$ is as listed.

$K$ and $K_{inv}$ are not inverses modulo $p$; instead, $K \times K_{inv} = 1 \ (\bmod \ r)$

share|improve this answer
    
Ah, you are right. I forgot that k is not really a member of the field, it is just a number that represents a point $p*G$ on the curve. My calculations work if I use $r$ instead of $p$. Thanks! –  David Grayson Mar 15 at 22:49

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.