3
$\begingroup$

I am new in Elliptic curve and I got a lot of knowledge through reading :) but I reached to NAF method as a scalar multiplication method, but don't understand how in this example get it:

Let k = 1234567 and its binary representation contains 21- bits:
100101101011010000111. In this 
11 1′s and 10 0′s can be found resulting in 20 doubling operations (D) and 10 point addition operations (A). The width-4 NAF
representation of 1234567 is
9 0 0 0 0 13 0 0 0 0 13 0 0 0 0 0 0 7. In this, an increased number of 0′
s can be
seen. The computational cost = 18D + 4A, assuming that the values 9P, 13P
and 7P are computed before hand and stored.

$\endgroup$

1 Answer 1

4
$\begingroup$

With the double-and-add method of curve multiplication, we set single bits in the exponent. For example, if we're at 1101000G, we can double (to get 11010000G) and then conditionally add $G$ (to set the lsbit, getting 11010001G).

NAF extends this by noting that, with a bit of precomputation, we can insert several bits at once. For example, if we're at 11010000G, and we have 1101G precomputed, we can add those together, getting 11011101G. In this example, we set 3 bits in the exponent with a single add - doing the same with double-and-add with require 3 point additions.

So, with 4-bit NAT, we start with the values $0G, 1G, 2G, ..., 15G$ precomputed. If we are using the same $G$ repeatedly (e.g. $G$ is the curve 'generator point'), we can do those once and put them in a table. Alternatively, we can compute those with 7 additions and 7 doublings.

Then, to compute 100101101011010000111G, we start with the top 4 bits 1001. We have 1001G in our precomputed table, so we start there. Then, we keep on doubling until we reach 100100000G; at this point, we have 4 bits (the 1101 pattern) in the target that is not expressed in our current value - we get the 1101G value in our precomputed table and add it in, given 100101101G. We keep on going (adding in values from our precomputed table when we get 4 bits in the target that is not expressed in our current value) until we hit the end - in that case, there's a remaining 111G, so we add that in, and we're done.

If you note the patterns of doublings and additions (with a doubling without an addition being signified by a 0), that pattern is the 9 0 0 0 0 13 0 0 0 0 13 0 0 0 0 0 0 7 that's found in quote.

With double-and-add, we end up using an expected $n/2$ additions to multiply by an $n$-bit scalar; with 4-bit NAF, we use an expected $n/5$ additions (and the number of doublings are about the same - 4 bit NAT uses 3 fewer) - that is not that bad of a savings.

On the other hand, if the attacker is able to listen into when we are performing the doublings versus the additions, he can gain some information on the scalar we're multiplying by - that can be bad (hence this algorithm may not be appropriate without additional masking in some circumstances).

There are even more aggressive ways of implementing point multiplications with elliptic curves; however that should help with understanding this one.

$\endgroup$
6
  • $\begingroup$ thanks a lot for nice explination, and sure this will added value to my knowledge about EC, but I have question, do you have the function of doubling and adding for this NAF 4bits method, because I want to know why we doubled 5 times after 1001 $\endgroup$ Jan 18, 2023 at 8:51
  • 1
    $\begingroup$ @CiscoSaeed: we doubled 5 times after 1001 to get to 100100000, so that we can add 1101 to get 100101101 $\endgroup$
    – poncho
    Jan 18, 2023 at 13:19
  • $\begingroup$ OK so first I took the 1st 4 bits 1001 then I faced 0 after and to pass it then need to double 5 times to reach the next 4 bits then I reached 1101 then I faced 0 then I doubled five to reach 1101 then I faced 4 Zeros how I get 6 doubles here? :-) onc more thing could you refer to me any example about adding additional masking because of security reason? $\endgroup$ Jan 18, 2023 at 17:13
  • 1
    $\begingroup$ You do 7 (not 6) doubles to move from 10010110101101 to 100101101011010000000, so that a single addition of 111 gets you to 100101101011010000111, the target value $\endgroup$
    – poncho
    Jan 18, 2023 at 17:19
  • 1
    $\begingroup$ As for masking, well, there are a number of alternatives - the most common is "Coron Blinding", which is "to compute $xG$, you pick a random $r$ and compute $(x+rq)G$ (where $q$ is the order of the point). Now, straight-forward Coron blinding doesn't work that well with curves such as P256 (which has a $q$ very close to a power of 2; that means that you need a large $r$ to disguise all the bits) - one way around it is to use a point multiply routine that's based on a radix which is not a power of 2 (e.g. 48); that implies a base conversion routine to base 48; however it can work... $\endgroup$
    – poncho
    Jan 18, 2023 at 17:24

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.