0
$\begingroup$

I'm implementing point addition, doubling and scalar multiplication using projective coordinates. I took reference from this link https://www.nsa.gov/ia/_files/nist-routines.pdf

I have implemented

Routine 2.2.6(ec_double)

Routine 2.2.7(ec_add)

Routine 2.2.8(ec_full_add)

Routine 2.2.9(ecc_full_sub)

They all are working and I have verified the results with the example results given at the last for P-256 curve.

I implemented Routine 2.2.10 ec_mult(Scalar multiplication) But I couldnt get the correct output. In line 15 and 16 of this routine they take the binary representation of d(random number) and 3d. And the loop skips both MSB and LSB and performs the operations.

I got doubts like that 3d is modular multiplication or simple multiplication?. The loops runs for d or 3d if its not modular multiplication?

Is there anything else I'm missing out?. If somebody has followed this algorithm and implemented it please help me out here.

$\endgroup$
1
$\begingroup$

3d multiplication is a simple multiplication not a mod multiplication.

I suggest you to check IEEE Std 1363-2000 document and "A.10.3 Elliptic scalar multiplication" part of that document if you can. It has somewhat more explanation than Nist's document.

$\endgroup$
  • $\begingroup$ If it is not modulo mul, 3d will have an extra byte than d. Then how does the loop work? Line 17 says the loop runs from l-1 to 1. This is meant for d or 3d?. And I don't have access to the reference document which u suggested $\endgroup$ – abejoe Feb 16 '16 at 9:33
  • $\begingroup$ I managed to get a look into the document u suggested. The one i'm using is in A.10.9 . In that algorithm k(random number) and 3k are used. 3K will have one byte extra than k and the loop runs for i form l-1 to 1. How exactly will it satisfy for both h[i] and k[i] because h will contain one byte extra than k. $\endgroup$ – abejoe Feb 16 '16 at 10:49
  • $\begingroup$ @abejoe yeah A.10.3 gives a more generalized function whereas A.10.9 provides scalar multiplication algorithm for projective coordinates. In the algorithms l is the most significant bit index of 3d(note that index number start from 0). In each case, because the loop starts from l-1, you dont have to worry about one extra bit. Both h[] and k[] arrays have elements with index "l-1" (i mean h[l-1] and k[l-1] are valid). I dont know the mathematical detail behind it, but that algorithm should work without taking into account the MSB of 3d. $\endgroup$ – Makif Feb 16 '16 at 11:17
  • $\begingroup$ Since its for P-256 the random number 'k' will have only 256 bits and 3k will contain 260 bits. This difference causes all the doubts. The loop's i starts from l-1 of 3k or k, because in this case both are different. l-1 will start from 259th bit of 3k(assuming 260th bit is set) but then d has only 256 bits. $\endgroup$ – abejoe Feb 16 '16 at 12:14
  • $\begingroup$ @abejoe Considering that 4d is a two bit shift of d, 3d would have at most 2 more bits than d. Also, note that d is less than base point order $\endgroup$ – Makif Feb 16 '16 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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