如何用椭圆曲线上的雅可比坐标系计算点加法

Question

我正在编写一个椭圆曲线加密的小项目,当我使用仿射坐标系时,该程序运行良好,这意味着每个点由2个坐标(x',y')表示.

现在我试图用雅可比坐标系代替仿射坐标系,其中每个点由3个坐标(x,y,z),x'= x /z²和y'= y /z³表示.

我想知道如何将仿射坐标转换为雅可比坐标**.在一些教程中,人们使用公式:(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. ... jacobian x坐标不能被z²整除.

如果坐标不是整数,我该怎么办？如果他们是负面的？我已经尝试用我的曲线的字段大小MOD,但结果也不正确.

所以使用雅可比坐标的点(x,y,1)是正确的,但不是唯一的.所有满意(a^2.x,a^3.y,a)的点都是等价的.在我的程序中,曲线是在素数场中定义的,所以当我计算时u1, u2, s1, s2 ...我应该将MO​​D 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,有一些特殊情况要处理.

1. P1和P2都是无限的:P3=infinite.
2. P1是无限的:P3=P2.
3. P2是无限的:P3=P1.
4. P1和P2具有相同的x坐标,但不同的y坐标或两个y坐标等于0: P3=infinite.
5. P1和P2有不同的x坐标:Addition formula.
6. P1和P2具有相同的坐标:Doubling formula.

这是我的C函数的原型:

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

point是表示在仿射坐标系中定义的点的结构,以及jacobian雅可比系统.

问题是当我处理那些特殊情况时,特别是第四个,我仍然将两个点转换回仿射坐标,或者我无法比较它们的坐标,这意味着我仍然需要计算除法.

Answer 1

投影坐标的雅可比形式(与任何其他形式一样)并不是唯一的 - 对于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,这是最简单的.modPowmodInverse

所讨论的场(即模数)是椭圆曲线定义的一部分,并且在一个场上的操作给出与在另一场中的操作完全不同的结果.因此,请确保使用正确的字段.

Answer 2

处理椭圆曲线时，坐标位于 字段中。对于密码学来说，这是一个有限域；在你的情况下，“整数模质数p ”。所有操作都在该字段中进行，即您应该执行每一次加法、乘法或模p 的求逆。

\n\n

在进行积分加法时，有几种特殊情况必须特殊处理：

\n\n

\n

• 有一个特殊的“无穷远点”，它没有坐标x和y。它是曲线加法的“零”。在通用点加法例程中，您必须有一种方法来编码“无穷远点”并专门检查它。

\n

• 将(x,y)添加到(x\',y\')时，可能会出现x = x\'。在这种情况下，要么y =y\'，然后它是一个有其特定公式的倍数（如果您应用通用公式，您最终会除以零，这是行不通的）；或者，y = -y\'，在这种情况下，总和是“无穷远点”。

\n

\n\n

因此，只有在处理完特殊情况后才能应用通用公式。一般来说，在曲线y ² = x ³ +a\xc2\xb7x+b中， (x ₁ ,y ₁ )和(x ₂ ,y ₂ )之和为(x ₃ ,y ₃ )使得x ₃ = f ² -x ₁ -x ₂和y ₃ = f\xc2\xb7(x ₁ -x ₃ )-y ₁，其中f = (y ₂ -y ₁ )/(x ₂ -x ₁ )。这意味着计算一次除法和两次乘法，以及一些减法（所有运算都对整数模p进行，如上所述）。

\n\n

除法和求模p的逆运算相对昂贵（模除法的成本通常与大约 80 次乘法相同），因此在某些情况下，我们使用射影或雅可比坐标系。雅可比坐标是将一个点表示为三个值(X,Y,Z)（所有这些值都在有限域中，即以p为模的整数），使得x = X/Z ²和y = Y/Z ³。

\n\n

每个点(x,y)有许多可能的表示形式为(X,Y,Z)。通过设置X = x、Y = y和Z = 1可以轻松转换为雅可比坐标：(x,y,1)是(x,y)点的完全有效的雅可比表示。从雅可比坐标转换在计算上比较困难：您必须进行模求逆和一些乘法（计算U = 1/Z，然后x = X\xc2\xb7U ²和y = Y\xc2\xb7U ³）。

\n\n

对于雅可比坐标，两点的加法是通过十几次域乘法完成的，根本不需要除法。您只能得到结果的雅可比行列式表示，因此您仍然必须在某个时刻进行模求逆或除法；然而（这就是为什么你费心使用雅可比坐标），这种除法是可以相互化的。如果您必须进行一百个左右的连续点加法（就像在加密环境中典型的那样，当将点与整数“相乘”时），那么您可以在整个过程中使用雅可比表示，并执行一次转换回笛卡尔坐标（ x,y)最后。因此，您不需要进行 200 次乘法和 100 次除法，而是进行 1000 次乘法和 1 次求逆；由于一次反转的成本与 80 次乘法相同，因此增益是可观的。

\n\n

尝试利用这本书；任何好的大学图书馆都应该有一个。它非常清楚地解释了这一切。

\n