8

我正在编写一个椭圆曲线密码学的小项目，当我使用仿射坐标系时程序运行良好，这意味着每个点由 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 ...我应该将 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，有一些特殊情况需要处理。

  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对于雅可比系统。

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

4

3 回答 3

10

射影坐标的雅可比形式（与任何其他形式一样）不是唯一的 - 对于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方法），这是最简单的。

所讨论的域（即模数）是椭圆曲线定义的一部分，对一个域的操作与在另一个域的操作给出完全不同的结果。因此，请确保您使用的是正确的字段。

于 2011-12-05T21:27:33.123 回答
4

处理椭圆曲线时，坐标位于字段 中。对于密码学，这是一个有限域；在你的情况下，“整数模素数p ”。所有操作都在那个领域，即你应该做每一个加法、乘法或取反模p。

加分时，有几种特殊情况需要特别处理：

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

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

因此，只有在您处理了特殊情况后，才能应用通用公式。一般而言，在曲线y 2 = x 3 +a·x+b中，(x 1 ,y 1 )和(x 2 ,y 2 )之和为(x 3 ,y 3 )使得x 3 = f 2 -x 1 -x 2和y 3 = f·(x 1 -x 3 )-y 1，其中f = (y 2 -y 1)/(x 2 -x 1 )。这意味着计算一次除法和两次乘法，以及一些减法（所有运算都在整数模p上完成，如上所述）。

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

每个点(x,y)都有许多可能的表示形式(X,Y,Z)。通过设置X = x、Y = y和Z = 1可以轻松转换为雅可比坐标：(x,y,1)是(x,y)点的完全有效的雅可比表示。雅可比坐标的转换在计算上更难：您必须进行模反演和一些乘法（您计算U = 1/Z，然后x = X·U 2和y = Y·U 3）。

使用雅可比坐标，两个点的相加是在十几个域乘法中完成的，根本没有除法。你只得到结果的雅可比表示，所以你仍然需要在某个时候进行模反转或除法；但是（这就是为什么你要使用雅可比坐标），这种划分可以相互化。如果你必须做一百个左右的连续点加法（在密码学上下文中很典型，当用一个整数“乘”一个点时），那么你可以在整个过程中使用雅可比表示，并进行一次转换回笛卡尔坐标（ x,y)在最后。因此，不是进行 200 次乘法和 100 次除法，而是进行 1000 次乘法和 1 次求逆；由于求逆的成本与 80 次乘法相同，因此收益是可观的。

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

于 2011-12-06T12:21:01.693 回答
1

这是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)
于 2018-08-27T03:37:13.043 回答