4
$\begingroup$

I want to implement a point multiplication ($k \cdot P$) operation on FPGA. I have a BN curve $y^2=x^3+2$, and a scalar value $k$. The $x$ and $y$ coordinates of point $P$ are of 256 bits. In the double and add formulas, there are three main operations: addition, multiplication, and division. Each of these are mod operations (e.g, $a+b \mod m$). What should be the value of this $m$? Could it be the reduction polynomial (remember that I am working in a prime field) or some constant integer value?

|improve this question
$\endgroup$
  • $\begingroup$ When working in prime fields, you don't need to think in polynomials. You can use simple modular arithmetic. $\endgroup$ – CodesInChaos Jan 22 '13 at 12:56
  • $\begingroup$ @CodesInChaos I thought we always think for polynomial interpretations in finite fields (?) $\endgroup$ – curious Dec 5 '13 at 9:20
5
$\begingroup$

It's the prime of the prime field.

(Note that, if you're also using the curve for pairings, you'll need arithmetic over both $\mathbb{F}_p$ and $\mathbb{F}_{p^{12}}$. The first can be viewed as arithmetic modulo $p$, but the second is slightly more complex, and can be viewed as arithmetic of polynomials over $\mathbb{F}_p$, modulo a reduction polynomial.)

|improve this answer
$\endgroup$
  • $\begingroup$ it is very good and to the point answer.if i am doing arithmetic over Fp^2 (quadratic numbers). what should be the reduction polynomial? and how to compute a reduction polynomial for Fp^4 and so on.. $\endgroup$ – Khalid Jan 22 '13 at 15:53
  • $\begingroup$ You can use any irreducible polynomial. Usually it's $x^2 + 1$, which is irreducible if $-1$ does not have a square root modulo $p$. The same for other degrees: use a $n$-degree irreducible polynomial. Note that for efficiency a "tower of extensions" is often used (e.g. quartic extension can be built as an quadratic over another quadratic). Ask another question if you need details. I also suggest reading this: everything2.com/user/Swap/writeups/finite+field $\endgroup$ – Conrado Jan 22 '13 at 17:48
  • $\begingroup$ how to handle Fp arithmetic, like i add/sub two numbers in Fp e.g A+b/A-b mod p. do i need to represent these numbers as signed numbers because for A-B if number A is less than B then the result would be negative. There are two possibilities one to represent A and B in two's complement format or take the two's complement of result, which is suitable and faster in Fp arithmetic. $\endgroup$ – Khalid Jan 25 '13 at 16:20
  • 1
    $\begingroup$ I strongly suggest you to refer to a stardard reference like Hankerson et. al's "Guide to Elliptic Curve Cryptography" or Menezes et. al's "Handbook of Applied Cryptography". Anyway, if the result of the subtraction is negative, simply add $p$ to the result (since you're working modulo $p$, this will not "change" the value). $\endgroup$ – Conrado Jan 25 '13 at 19:48
2
$\begingroup$

An elliptic curve is defined over a finite field $GF(p)$

The $m$ in $(a+b\mod m)$ is equal to $p$ in $GF(p)$.

You can also read this Elliptic Curve Cryptography - An implmentation guide. It is easy-to-read and it covers most topic you will encounter during implementation.

|improve this answer
$\endgroup$

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.