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?

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

2 Answers 2

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.)

$\endgroup$
4
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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.

$\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.