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?
4
$\begingroup$
$\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$
$\endgroup$
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.)
-
$\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$
$\endgroup$
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.
