跳到主要内容

Appendix A. Deterministic Generation (附录A. 确定性生成)

Appendix A. Deterministic Generation (确定性生成)​

本节规定了用于生成上述曲线的过程, 具体来说, 它定义了如何生成蒙哥马利曲线 y^2 = x^3 + A*x^2 + x 的参数A。该过程旨在尽可能客观, 以便清楚地表明没有不当考虑影响曲线的选择。该过程的输入是p, 即定义底层域的素数。p的大小决定了在椭圆曲线群中计算离散对数所需的工作量, 而选择精确的p取决于许多实现考虑。曲线的性能将由GF(p)中的运算主导, 因此仔细选择允许在预期架构上轻松进行约简的值至关重要。本文档不试图阐明所有这些考虑。

值 (A-2)/4 用于几个椭圆曲线点算术公式中。出于简单性和性能原因, 使这个常数变小是有益的, 即选择A使得 (A-2) 是可被4整除的小整数。

对于特定安全级别的每条曲线:

  1. Frobenius迹必须不在{0, 1}中, 以排除 [smart]、[satoh] 和 [semaev] 中描述的攻击, 如 [brainpool] 和 [safecurves] 中所述。

  2. MOV度 [reducing]: 嵌入度必须大于 (order - 1) / 100, 如 [brainpool] 和 [safecurves] 中所述。

  3. CM判别式: 判别式D必须大于 2^100, 如 [safecurves] 中所述。

A.1. p = 1 mod 4​

对于与 1 mod 4 同余的素数, 曲线及其扭曲的最小余因子为{4, 8}或{8, 4}。我们选择具有后者余因子的曲线, 以便任何考虑余因子的算法不必担心检查扭曲上的点, 因为扭曲余因子将是两者中较小的一个。

要生成蒙哥马利曲线, 我们找到最小的正A值, 使得 A > 2 且 (A-2) 可被4整除, 并且余因子如所需。以下Sage脚本中的find1Mod4函数在给定p的情况下返回此值:

def findCurve(prime, curveCofactor, twistCofactor):
    F = GF(prime)

    for A in xrange(3, int(1e9)):
        if (A-2) % 4 != 0:
          continue

        try:
          E = EllipticCurve(F, [0, A, 0, 1, 0])
        except:
          continue

        groupOrder = E.order()
        twistOrder = 2*(prime+1)-groupOrder

        if (groupOrder % curveCofactor == 0 and
            is_prime(groupOrder // curveCofactor) and
            twistOrder % twistCofactor == 0 and
            is_prime(twistOrder // twistCofactor)):
            return A

def find1Mod4(prime):
    assert((prime % 4) == 1)
    return findCurve(prime, 8, 4)

生成 p = 1 mod 4 的曲线

A.2. p = 3 mod 4​

对于与 3 mod 4 同余的素数, 曲线和扭曲余因子都可以是4, 这是最小的。因此, 我们选择具有这些余因子和最小正A的曲线, 使得 A > 2 且 (A-2) 可被4整除。以下Sage脚本中的find3Mod4函数在给定p的情况下返回此值:

def find3Mod4(prime):
    assert((prime % 4) == 3)
    return findCurve(prime, 4, 4)

生成 p = 3 mod 4 的曲线

A.3. Base Points (基点)​

曲线的基点是在正确子群中具有最小正u值的点。以下Sage脚本中的findBasepoint函数在给定p和A的情况下返回此值:

def findBasepoint(prime, A):
    F = GF(prime)
    E = EllipticCurve(F, [0, A, 0, 1, 0])

    for uInt in range(1, 1e3):
      u = F(uInt)
      v2 = u^3 + A*u^2 + u
      if not v2.is_square():
        continue
      v = v2.sqrt()

      point = E(u, v)
      pointOrder = point.order()
      if pointOrder > 8 and pointOrder.is_prime():
        return point

生成基点

最后于 更新