メインコンテンツまでスキップ

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-2) が4で割り切れる小さな整数になるようにAを選択します。

特定のセキュリティレベルの各曲線について:

  1. フロベニウストレースは{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}のいずれかです。補因子を考慮するアルゴリズムがツイスト上の点をチェックする心配をしなくて済むように, 後者の補因子を持つ曲線を選択します。これは, ツイストの補因子が2つのうち小さい方になるためです。

モンゴメリ曲線を生成するには, A > 2 かつ (A-2) が4で割り切れ, 補因子が望ましいものである最小の正のA値を見つけます。以下の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 > 2 かつ (A-2) が4で割り切れる最小の正のAを持つ曲線を選択します。以下の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

基点を生成

に最終更新