How to calculate point addition using Jacobian coordinate-system over elliptic curves

Question

I'm writing a small project of elliptic curve cryptography, and the program works well when I use affine coordinate system, which means each point is represented by 2 coordinates (x',y').

Now I'm trying to replace affine coordinate system by jacobian coordinate system in which each point is represented by 3 coordinates (x,y,z), x' = x/z² and y' = y/z³.

I'd like to know how to transform affine coordinates to jacobian coordinates**. In some tutorials, people uses the formula: (x,y) = (x,y,1) which means the z-coordinate is always set to one. But I'm not sure if it's correct.

Then for points additions over elliptic curve, to calculate P(x1,y1,z1) + Q(x2,y2,z2) = R(x3,y3,z3). I've used the following formulas in my program:

u1 = x1.z2²
u2 = x2.z1²
s1 = y1.z2³
s2 = y2.z1³
h = u2 - u1
r = s2 - s1
x3 = r² - h³ - 2.u1.h²
Y3 = r. (U1.h² - x3) - s1.h³
z3 = z1.z2.h

But when I test my program, I get some negative coordinates e.g. (-2854978200,-5344897546224,578). And when I try to convert the result back to affine coordinate system with the formular (x'=x/z²,y'=y/z³), I get (-8545, -27679), actually the x coordinate is -8545.689.... The jacobian x coordinate isn't divisible by z².

What should I do if the coordinates are not integers? And if they're negative? I've tried to MOD with the field size of my curve, but the result isn't correct either.

So the point using jacobian coordinates (x,y,1) is correct, but not unique. All points satisfying (a^2.x,a^3.y,a) are equivalent. And in my program the curve is defined in a prime field, so when I calculate u1, u2, s1, s2 ... I should apply MOD p to each variable?

And for transforming the final result back to affine coordinates, e.g. The x coordinate, in fact it is not a division, it's a modular inverse? For example, my curve is defined in a finite prime field p=11, and I have a point using jacobian coordinates (15,3,2), to transform jacobian x coordinate to affine x coordinate, I have to calculate 2^2 = 4 => x = 4^-1 mod p => x = 3, and 15.3 mod p = 1, so the affine x coordinate is 1, is that right?

The objective of jacobian coordinates is to avoid the division during addition. But as Thomas Pornin said, when we calculate P1 + P2 = P3, there are some special cases to handle.

1. P1 and P2 are both infinite: P3=infinite.
2. P1 is infinite: P3=P2.
3. P2 is infinite: P3=P1.
4. P1 and P2 have the same x coordinate, but different y coordinates or both y coordinates equal 0: P3=infinite.
5. P1 and P2 have different x coordinate: Addition formula.
6. P1 and P2 have same coordinates: Doubling formula.

And here's prototypes of my C functions:

jac_addition(jacobian *, point *, jacobian *);
jac_doubling(jacobian *, jacobian *);

point is a structure representing a point defined in affine coordinate system, and jacobian for jacobian system.

The problem is when I handle those special cases, especially the 4th one, I still have convert both points back to affine coordinates, or I can't compare their coordinates, which means I still have to calculate the division.

Answer 1

The Jacobian form of the projective coordinates (as any other form) is not unique - for every value of Z (other than 0) you get other X and Y without the actual point changing.

Thus, if you have a point in affine coordinates (X', Y'), the pair (X', Y', 1) is a projective representative of this point, as well as (4·X', 8·Y', 2), (9·X', 27·Y', 3), etc. The one with 1 is the easiest to create, so usually you would use this one.

While one can define (and study) elliptic curves over any field, and many mathematicians study curves defined over the complex numbers, for cryptographic uses, the coordinates are elements of some finite field. In the simplest case, we have a prime field (i.e. integers modulo a prime number), and you'll have to do addition, subtraction, multiplication and division (and probably exponentiation) in this field.

As long as Z is not zero, you should be able to divide by Z² - this is equivalent to multiplying by the inverse of Z², and such an element exists, and can be calculated efficiently using the extended euclidean algorithm.

This is easiest if your programming language comes with some big number library which has the necessary operations predefined, like Java's BigInteger class (with its mod, modPow and modInverse methods).

The field in question (i.e. the modulus) is part of the definition of the elliptic curve, and operations over one field give totally different results than operations in another one. So make sure you are using the right field.