如何使用椭圆曲线上的雅可比坐标系计算点加法
我正在编写一个椭圆曲线密码学的小项目，当我使用仿射坐标系时，该程序运行良好，这意味着每个点都由 2 个坐标 (x',y') 表示。
现在我尝试用雅可比坐标系替换仿射坐标系，其中每个点由 3 个坐标 (x,y,z) 表示，x' = x/z2 和 y' = y/z3。
我想知道如何将仿射坐标转换为雅可比坐标**。在一些教程中，人们使用公式：(x,y) = (x,y,1) 这意味着 z 坐标始终设置为 1。但我不确定这是否正确。
然后在椭圆曲线上进行点加法，计算 P(x1,y1,z1) + Q(x2,y2,z2) = R(x3,y3,z3)。我在程序中使用了以下公式：
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
但是当我测试程序时，我得到一些负坐标，例如（-2854978200，-5344897546224,578）。当我尝试使用公式 (x'=x/z²,y'=y/z³) 将结果转换回仿射坐标系时，我得到 (-8545, -27679)，实际上 x 坐标是 -8545.689。 ... 雅可比 x 坐标不能被 z² 整除。
如果坐标不是整数怎么办？如果结果是否定的呢？我尝试用曲线的场大小进行 MOD，但结果也不正确。
所以使用雅可比坐标 (x,y,1) 的点是正确的，但不是唯一的。所有满足 (a^2.x,a^3.y,a) 的点都是等价的。在我的程序中，曲线是在素数域中定义的，因此当我计算 u1, u2, s1, s2 ... 时，我应该对每个变量应用 MOD p 吗？
而为了将最终结果转换回仿射坐标，例如x坐标，实际上它不是除法，它是模逆？例如，我的曲线是在有限素数域中定义的p=11，我有一个观点，使用雅可比坐标 (15,3,2)，将雅可比 x 坐标转换为仿射 x 坐标，我必须计算 2 ^2 = 4=> x = 4^-1 mod p => x = 3，以及 15.3 mod p = 1，所以仿射 x 坐标为 1，对吗？
雅可比坐标的目的是避免加法过程中的除法。但正如 Thomas Pornin 所说，当我们计算 P1 + P2 = P3 时，有一些特殊情况需要处理。
- P1 和 P2 都是无限的：
P3=infinite。 - P1 是无限的：
P3=P2。 - P2 是无限的：
P3=P1。 - P1 和 P2 具有相同的 x 坐标，但不同的 y 坐标或两个 y 坐标都等于 0：
P3=infinite。 - P1和P2有不同的x坐标：
加法公式。 - P1 和 P2 具有相同的坐标：
加倍公式。
这是我的 C 函数的原型：
jac_addition(jacobian *, point *, jacobian *);
jac_doubling(jacobian *, jacobian *);
point 是表示仿射坐标系中定义的点的结构，jacobian 表示雅可比系统。
问题是当我处理这些特殊情况时，尤其是第四个情况，我仍然需要将两个点转换回仿射坐标，或者我无法比较它们的坐标，这意味着我仍然需要计算除法。
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.
- 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 equal 0:
P3=infinite. - P1 and P2 have different x coordinate:
Addition formula. - 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
射影坐标的雅可比形式（与任何其他形式一样）不是唯一的 - 对于
Z的每个值（0 除外），您都会得到其他X和Y没有实际的点改变。因此，如果仿射坐标中有一个点
(X', Y')，则(X', Y', 1)对是该点的投影表示，以及(4·X', 8·Y', 2)、(9·X', 27·Y', 3)等。 1 是最容易创建的，所以通常你会用这个。虽然人们可以在任何域上定义（和研究）椭圆曲线，并且许多数学家研究在复数上定义的曲线，但对于密码学用途，坐标是某个有限域的元素。在最简单的情况下，我们有一个素数域（即以素数为模的整数），您必须在该域中进行加法、减法、乘法和除法（可能还有求幂）。
只要
Z不为零，您就应该能够除以Z²- 这相当于乘以 Z² 的倒数，并且这样的元素存在，并且可以使用扩展欧几里德算法可以有效地计算。如果您的编程语言附带了一些预定义了必要操作的大数库，例如 Java 的 BigInteger 类（及其 modPow ），那么这是最简单的> 和
modInverse方法）。所讨论的字段（即模数）是椭圆曲线定义的一部分，并且在一个字段上进行操作会给出与在另一字段上进行操作完全不同的结果。因此，请确保您使用正确的字段。
The Jacobian form of the projective coordinates (as any other form) is not unique - for every value of
Z(other than 0) you get otherXandYwithout 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
Zis not zero, you should be able to divide byZ²- 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
BigIntegerclass (with itsmod,modPowandmodInversemethods).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.
处理椭圆曲线时，坐标位于字段中。对于密码学来说，这是一个有限域；在你的情况下，“整数模素数p”。 所有运算都在该字段中进行，即您应该执行每一次加法、乘法或取模p的求逆。
在进行点加法时，有一些特殊情况必须特别处理：
有一个特殊的“无穷远点”，它没有坐标x和y。它是曲线加法的“零”。在通用点加法例程中，您必须有一种方法来编码“无穷远点”并专门检查它。
将(x,y)添加到(x',y')时，可能会发生x = x'。在这种情况下，要么y = y'，然后它是一个点加倍，有其特定的公式（如果您应用通用公式，您最终会除以零，这不起作用）；或者，y = -y'，在这种情况下，总和是“无穷远点”。
因此，只有在处理完特殊情况后才能应用通用公式。一般来说，在曲线 y2 = x3+a·x+b 中，(x1,y1) 和 (x2,y2)是(x3,y3) 使得 x3 = f2-x1-x2 和 y3 = f·(x1 sub>-x3)-y1，其中f = (y2-y1)/(x2-x1)。这意味着计算一次除法和两次乘法，以及一些减法（所有运算都是对整数模 p 进行的，如上所述）。
除法和求反模 p 相对昂贵（模除法的成本通常与大约 80 次乘法相同），因此在某些情况下，我们使用射影或雅可比坐标系。雅可比坐标是将一个点表示为三个值(X,Y,Z)（所有这些值都在有限域中，即以p为模的整数），使得 x = X/Z2 和 y = Y/Z3。
每个点(x,y)都有许多可能的表示形式(X,Y,Z)。通过设置X = x、Y = y和Z = 1可以轻松转换到雅可比坐标： >(x,y,1) 是 (x,y) 点的完全有效的雅可比表示。从雅克比坐标转换在计算上比较困难：您必须进行模求逆和一些乘法（计算U = 1/Z，然后x = X ·U2 和y = Y·U3）。
对于雅可比坐标，两点的加法是通过十几次域乘法完成的，根本不需要除法。您只能得到结果的雅可比行列式表示，因此您仍然必须在某个时刻进行模求逆或除法； 但是（这就是为什么你费心使用雅可比坐标），这种除法是可以相互化的。如果您必须进行一百个左右的连续点加法（就像在加密环境中典型的那样，当将点与整数“相乘”时），那么您可以在整个过程中使用雅可比表示，并执行一次转换回笛卡尔坐标< em>(x,y) 最后。因此，您不需要执行 200 次乘法和 100 次除法，而是执行 1000 次乘法和 1 次求逆；由于一次反转的成本与 80 次乘法相同，因此增益是可观的。
尝试利用这本书；任何好的大学图书馆都应该有一个。它非常清楚地解释了这一切。
When dealing with elliptic curves, the coordinates are in a field. For cryptography, this is a finite field; in your case, the "integers modulo a prime p". All operations are meant in that field, i.e. you should do every single addition, multiplication or inversion modulo p.
When doing addition of points, there are a few special cases which you must handle specially:
There is a special "point at infinity" which does not have coordinates x and y. It is the "zero" of the curve addition. In a generic point addition routine, you must have a way to encode a "point at infinity" and check it specially.
When adding (x,y) to (x',y'), it may happen that x = x'. In that case, either y =y', and then it is a point doubling which has its specific formula (if you apply the generic formula, you end up dividing by zero, which will not work); or, y = -y', in which case the sum is the "point at infinity".
So the generic formula is to be applied only once you have handled the special case. In all generality, in a curve y2 = x3+a·x+b, the sum of (x1,y1) and (x2,y2) is (x3,y3) such that x3 = f2-x1-x2 and y3 = f·(x1-x3)-y1, where f = (y2-y1)/(x2-x1). This implies computing one division and two multiplications, and a few subtractions (all operations being done on integers modulo p, as explained above).
Division and inversion modulo p are relatively expensive (a modular division has typically the same cost as about 80 multiplications) so in some situations, we use projective or Jacobian coordinate systems. Jacobian coordinates are about representing a point as three values (X,Y,Z) (all of them in the finite field, i.e. integers modulo p) such that x = X/Z2 and y = Y/Z3.
Each point (x,y) has many possible representations as (X,Y,Z). Conversion to Jacobian coordinates is easy by setting X = x, Y = y and Z = 1: (x,y,1) is a perfectly valid Jacobian representation of the (x,y) point. Conversion from Jacobian coordinates is computationally harder: you have to do a modular inversion, and a few multiplications (you compute U = 1/Z, then x = X·U2 and y = Y·U3).
With Jacobian coordinates, the addition of two points is done in a dozen field multiplications, and no division at all. You get only a Jacobian representation of the result, so you still have to do a modular inversion or division at some point; however (and that's why you bother using Jacobian coordinates), that division can be mutualized. If you have to do a hundred or so successive point additions (as is typical in a cryptographic context, when "multiplying" a point with an integer), then you can use Jacobian representations throughout, and do a single conversion back to cartesian coordinates (x,y) at the end. So instead of doing 200 multiplications and 100 divisions, you do 1000 multiplications and 1 inversion; since an inversion costs the same as 80 multiplications, the gain is appreciable.
Try to avail yourself to this book; any good college library should have one. It explains all of that very clearly.
这是 python 中的一个示例：
因此您可以求和：
Here is a sample in python:
So you can sum with: