如何利用椭圆曲线上的雅可比坐标系计算点加法
我正在写一个椭圆曲线密码学的小项目，当我使用仿射坐标系时，程序工作得很好，这意味着每个点用两个坐标(x'，y')表示。
现在我试图用jacobian坐标系代替仿射坐标系，其中每个点用3坐标(x，y，z)表示，x‘=x/z 2和y’=y/z。
我想知道如何将仿射坐标转换成jacobian坐标**。在一些教程中，人们使用的公式是：(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 2，y’=y/z)将结果转换回仿射坐标系时，得到(-8545，-27679)，实际上x坐标是-8545.689.jacobian x坐标不能被z 2整除。
如果坐标不是整数，我该怎么办？如果是阴性的话？我试着用我的曲线的字段大小来进行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所说，当我们计算P1 + P2 = P3时，有一些特殊情况需要处理。
- P1和P2都是无限的：
P3=infinite。 - P1是无限的：
P3=P2。 - P2是无限的：
P3=P1。 - P1和P2的x坐标相同，但y坐标不同，或者y坐标等于0：
P3=infinite。 - P1和P2有不同的x坐标：
Addition formula。 - P1和P2的坐标相同：
Doubling formula。
下面是我的C函数的原型：
jac_addition(jacobian *, point *, jacobian *);
jac_doubling(jacobian *, jacobian *);point是一个表示仿射坐标系中定义的点的结构，jacobian表示jacobian系统。
问题是，当我处理这些特殊情况，特别是第四种情况时，我仍然将两个点转换回仿射坐标，或者我无法比较它们的坐标，这意味着我仍然需要计算除法。
回答 2
Stack Overflow用户
发布于 2011-12-05 21:27:33
射影坐标的Jacobian形式(与任何其他形式一样)并不是唯一的--对于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类(以及它的mod、modPow和modInverse方法)。
所讨论的域(即模)是椭圆曲线定义的一部分，一个域上的运算与另一个域上的运算结果完全不同。因此，请确保您正在使用正确的字段。
Stack Overflow用户
发布于 2018-08-27 03:37:13
下面是python中的一个示例：
def to_jacobian((Xp, Yp)):
"""
Convert point to Jacobian coordinates
:param (Xp,Yp,Zp): First Point you want to add
:return: Point in Jacobian coordinates
"""
return (Xp, Yp, 1)
def from_jacobian((Xp, Yp, Zp), P):
"""
Convert point back from Jacobian coordinates
:param (Xp,Yp,Zp): First Point you want to add
:param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p)
:return: Point in default coordinates
"""
z = inv(Zp, P)
return ((Xp * z**2) % P, (Yp * z**3) % P)
def jacobian_add((Xp, Yp, Zp), (Xq, Yq, Zq), A, P):
"""
Add two points in elliptic curves
:param (Xp,Yp,Zp): First Point you want to add
:param (Xq,Yq,Zq): Second Point you want to add
:param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p)
:param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p)
:return: Point that represents the sum of First and Second Point
"""
if not Yp:
return (Xq, Yq, Zq)
if not Yq:
return (Xp, Yp, Zp)
U1 = (Xp * Zq ** 2) % P
U2 = (Xq * Zp ** 2) % P
S1 = (Yp * Zq ** 3) % P
S2 = (Yq * Zp ** 3) % P
if U1 == U2:
if S1 != S2:
return (0, 0, 1)
return jacobian_double((Xp, Yp, Zp), A, P)
H = U2 - U1
R = S2 - S1
H2 = (H * H) % P
H3 = (H * H2) % P
U1H2 = (U1 * H2) % P
nx = (R ** 2 - H3 - 2 * U1H2) % P
ny = (R * (U1H2 - nx) - S1 * H3) % P
nz = (H * Zp * Zq) % P
return (nx, ny, nz)所以你可以和：
def fast_add(a, b, A, P):
return from_jacobian(jacobian_add(to_jacobian(a), to_jacobian(b), A, P), P)https://stackoverflow.com/questions/8389324
复制相似问题
腾讯云开发者
