0
$\begingroup$

I'm implementing point addition, doubling and scalar multiplication using projective coordinates. I took reference from this link.

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_mul t(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$ I have problems with ec_doubling. It gives wrong result. E.g. for point (5,1) it gives result (11,4) it should be (6,3). Are you sure there is no mistake in formula? $\endgroup$
    – guffi
    Commented Nov 4, 2021 at 10:27

1 Answer 1

2
$\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$
8
  • $\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
    Commented Feb 16, 2016 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
    Commented Feb 16, 2016 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
    Commented Feb 16, 2016 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
    Commented Feb 16, 2016 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
    Commented Feb 16, 2016 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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