1
$\begingroup$

I am working on a project where I need to implement elliptic curve cryptography, I am struggling from a long time in order to understand the working and the process.

Modular finite field arithmetic, I understood the initial concept, now I am looking at this document from NIST

https://www.nsa.gov/ia/_files/nist-routines.pdf

However, I cannot understand, that if I need to check my modular adder or multiplier, what data should I use.

  1. What is A,B and mod(P) in this document for P-256.
  2. I want to implement montgomery reduction however I am not understanding it. I have a 512 bit value that is A*B. How should I move further from here.

IMP--Using the Fast reduction given by NIST ... how do we do it .... just add and subtract them and then find mod or find mod after every add or subtract?

REDUCTION--- While reducing ... suppose I did all those 256 bit additions and subtractions, Should I use 512 bit adder? as carry may be much more than 1 bit.

I have very very less time left to design the whole system. Please help me understand it is that I could implement it as soon as possible.
I am implementing the design on FPGA using VHDL.

Improve this question
$\endgroup$
8
  • $\begingroup$ Usually A,B and P are constants defining the curve. Or it may be that A and B are the inputs to some function. $\endgroup$
    – SEJPM
    Aug 23, 2015 at 15:58
  • $\begingroup$ Thank you for replying .. umm, What should I do in order to check if my result is same as given there. Is there any other document explaining the parameters in better way? 2 points S and T (x,y) are given but when we add Sx + Tx mod P256(given in the document), we dont get the result same as in there. What am I missing. $\endgroup$
    – rdr1234
    Aug 23, 2015 at 16:03
  • $\begingroup$ Did I read your comment right, that you actually tried $x_S+x_T \bmod p_{256}$ to get $x_R$? Sorry, but that's not how ECC works. $\endgroup$
    – SEJPM
    Aug 23, 2015 at 16:08
  • $\begingroup$ Thats what my point is. I am missing some important basic facts regarding those parameters. I am so confused that I cant even move a bit further. Till now I know how to implement an adder and subtractor and I have implemented multiplier that gives 512 bit output. $\endgroup$
    – rdr1234
    Aug 23, 2015 at 16:21
  • $\begingroup$ Would an explanation of how to do the operations in the samples / test vectors help you? $\endgroup$
    – SEJPM
    Aug 23, 2015 at 16:35

1 Answer 1

Reset to default
2
$\begingroup$

In the document the P-256 parameters describe the curve P-256 on which you want to perform the operations. Traditionally a curve is represented in Weierstrass-form as the set of points for which

$$y^2\equiv x^3 + ax+b \pmod p$$

holds. Where $p$ is the prime defining the field for the operation and $a$ and $b$ define the shape of the curve. A point on the curve is a pair $(x,y)$ for which the above equation holds.

Now in order for elliptic curves to be actually useful, we want to perform operations on them. Usually this addition of two points, like $R=S+T$ with $R,S,T$ being curve points and we want to double points and thereby allow for fast exponentiation using the repeated square and multiply algorithm (although in practice you'd be more clever to avoid timing attacks). Doubling is usually denoted as $R=2S$ with $R,S$ being points on the curve.

Now to the basics on how to actually double and add two points. This is indeed described in the linked document. For reasons of efficiency, usually a third component for the points is defined $z$. If you have a point given only as $(x,y)$, define $z=1$. For practical applications I strongly suggest to simply follow the algorithms given in the document.

For verification you can use the below equations and the test vectors from the document. Note that for each section of the samples the parameters of that section need to be used.

To add two points $R=(x_R,y_R,z_R)$ and $S=(x_S,y_S,z_S)$ you can use the following equations to get $T=(x_T,y_T,z_T)$: $$u=y_R\cdot z_S - y_S\cdot z_R\bmod p$$ $$v=x_R\cdot z_S - x_S\cdot z_R\bmod p$$ $$w=u^2\cdot z_R \cdot z_S - v^3 - 2v^2 x_S\cdot z_R\bmod p$$ $$x_T=vc \bmod p$$ $$y_T=u(v^2x_S\cdot z_R-w)-v^3y_S\cdot z_R \bmod p$$ $$z_T=z_S\cdot z_R v^3 \bmod p$$

And finally you calculate the modular inverse of $z_T$ and calculate the affine coordinates of the resulting points as $x_T=x_T\cdot z_T^{-1} \bmod p$ and $y_T=y_T\cdot z_T^{-1} \bmod p$ giving you again the "classical representation".

This is "only" the addition law for two distinct points. Doubling is similarly complicated and should be implemented by strictly following the specified algorithms.
If you really want to learn more about EC crypto you may find more answers in the Handbook of Elliptic and Hyperelliptic Cruve Cryptography. The above algorithm is taken from Introduction to modern Cryptography (Second edition).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Umm, I am sorry, but in the above explanation, I only understood that P256 given in the document is the prime defining the field. Is it the same used for mod p? I am at the finite field level, and need to know about modular arithmetic, what about reduction after multiplication?? $\endgroup$
    – rdr1234
    Aug 23, 2015 at 18:04
  • $\begingroup$ @rdr1234 yes, the $\bmod p$ should be read as $\bmod p_{256}$ if you're using P-256. You can apply the reduction operation at any given intermediate result, meaning $(n\bmod p)\cdot(m\bmod p)\bmod p=nm\bmod p$. The first version is obviously faster. Maybe this helps you: If you're calculating with EC every number should be reduced $\bmod p$, except for the "d" in $Q=d\times P$ if $Q,P$ are points. $\endgroup$
    – SEJPM
    Aug 23, 2015 at 18:21

Your Answer

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

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