How to calculate the addition of a point using the Jacobian coordinate system over elliptic curves

Question

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

Now I am trying to replace the affine coordinate system with a Jacobian coordinate system in which each point is represented by three coordinates (x, y, z), x '= x / z² and y' = y / z³.

I would like to know how to convert affine coordinates to Jacobian coordinates **. In some textbooks, people use the formula: (x, y) = (x, y, 1) which means that the z-coordinate is always equal to one. But I'm not sure if this is correct.

Then, to add points along the elliptic curve, calculate P (x1, y1, z1) + Q (x2, y2, z2) = R (x3, y3, z3). I 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, for example. (-2854978200, -5344897546224.578). And when I try to convert the result back to an affine coordinate system with the formula (x '= x / z², y' = y / z³), I get (-8545, -27679), in fact the x coordinate is -8545.689 .... Coordinate jacobian x is not divisible by z².

What if the coordinates are not integers? And if they are negative? I tried MOD with the field size of my curve, but the result is also not correct.

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

And to convert the final result back to affine coordinates, for example. The x coordinate is actually not a division, is it a modular inverse? For example, my curve is defined in a finite simple field p=11 , and I have a point using jacobian coordinates (15,3,2) to convert the jacobian x coordinate to an 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 coordinate x is 1, is this correct?

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

• P1 and P2 are both infinite: P3=infinite .
• P1 is infinite: P3=P2 .
• P2 is infinite: P3=P1 .
• P1 and P2 have the same x coordinate, but different y coordinates or both y coordinates are 0: P3=infinite .
• P1 and P2 have a different x coordinate: Addition formula .
• P1 and P2 have the same coordinates: Doubling formula .

And here are the prototypes of my C functions:

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

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

The problem is that when I handle these special cases, especially the fourth, I still translate both points back to affine coordinates or I can’t compare their coordinates, which means that I still need to calculate the division.

Answer 1

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

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

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

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

This is easiest if your programming language contains some large number library that predetermines the necessary operations, such as the Java BigInteger class (with mod , modPow and modInverse ).

The field in question (i.e., the module) is part of the definition of an elliptic curve, and operations on one field give completely different results than operations in another. So make sure you use the correct field.

Answer 2

When working with elliptical curves, the coordinates are in the field . For cryptography, this is the final field ; in your case, "integers modulo a prime number p". All operations mean in this field, i.e. you must do every addition, multiplication or inversion modulo p.

When adding points, there are several special cases that you must handle specifically:

• There is a special “point at infinity” that does not have x and y coordinates. This is the “zero” curve addition. In the normal procedure for adding points, you should have a way to encode a "point at infinity" and test it specifically.

• When adding (x, y) to (x ', y') it may happen that x = x '. In this case, either y = y ', and then this is a doubling of the point, which has its own specific formula (if you apply the general formula, you will ultimately divide by zero, which will not work); or, y = -y ', in which case the sum is a "point at infinity".

Therefore, the general formula should only be applied after you have processed the special case. In general, in the curve y ² = x ³ + a · x + b the sum of (x ₁ , y ₁ ) and (x ₂ , y ₂ ) is (x ₃ , y ₃ ) such that x ₃ = f ² -x ₁ -x ₂ and y ₃ = f · (x ₁ -x ₃ ) - y ₁ , where f = (y ₂ -y <sub> 1sub>) / (x <sub> 2sub> -x <sub> 1sub> ) This implies the calculation of one division and two multiplications and several subtractions (all operations are performed by integers modulo p, as explained above).

Subdivision and inversion modulo p relative to the road (modular division usually has the same cost as about 80 multiplications), so in some situations we use projective or Jacobian coordinate systems. The Jacobian coordinates represent one point as three values ​​(X, Y, Z) (all of them in a finite field, i.e. Integers modulo p) such that x = X / Z ² and y = Y / Z ³ .

Each point (x, y) has many possible representations as (X, Y, Z). The transformation into Jacobi coordinates is easily established by setting X = x, Y = y and Z = 1: (x, y, 1) is a perfectly valid Jacobi representation of the point (x, y). The transformation from the Jacobi coordinates is more complicated with the calculation: you need to do a modular inversion and several multiplications (you calculate U = 1 / Z, then x = X · U ² and y = Y · U ³ ).

With Jacobi coordinates, the addition of two points is performed in dozens of field multiplications and no division at all. You get only the Jacobian representation of the result, so you still have to perform modular inversion or division at some point; however (and why you are worried using the coordinates of Jacobian), this separation can be mutually agreed. If you need to make a hundred consecutive additions of points (as is typical in a cryptographic context, when you “multiply” a point by an integer), then you can use Jacobian's representations everywhere and do one transformation back to the Cartesian coordinates (x, y) at the end. Therefore, instead of 200 multiplications and 100 divisions, you do 1000 multiplications and 1 inversion; since inversion costs the same as 80 multiplications, the gain is noticeable.

Try using this book ; any good college library should have one. This explains all this very clearly.