Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite
1

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?

share|improve this question
When working in prime fields, you don't need to think in polynomials. You can use simple modular arithmetic. – CodesInChaos Jan 22 at 12:56

2 Answers

up vote 4 down vote

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

share|improve this answer
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.. – user4602 Jan 22 at 15:53
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 – Conrado PLG Jan 22 at 17:48
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. – user4602 Jan 25 at 16:20
1  
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). – Conrado PLG Jan 25 at 19:48
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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