楕円曲線暗号
RFC 6090 楕円曲線暗号アルゴリズムの基礎 Fundamental Elliptic Curve Cryptography Algorithms RFC 5480 Elliptic Curve Cryptography Subject Public Key Information
RFC 8813 Clarifications for Elliptic Curve Cryptography Subject Public Key Information
RFC 9380 楕円曲線へのハッシュ Hashing to Elliptic Curves
SEC 1: 楕円曲線暗号 Elliptic Curve Cryptography SEC 2: 推奨される楕円曲線ドメインパラメータ Recommended Elliptic Curve Domain Parameters 鍵交換・署名用アルゴリズムとして利用される。暗号化には利用できない(鍵交換を利用する)
RFC 4754 IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)
有限体くらいまでわかれば実装できる
ECDSA
secp ($ \mathbb{F}_pGF(p) )
$ y^2 = x^3+ax + b
K
$ y^2=x^3 + b
$ y^2 = x^3 + ax
sect ($ \mathbb{F}_{2^m}GF(2^m) )
$ y^2+xy=x^3+ax^2+b
EdDSA RFC 7748 8032 EdWards25519 EdWards448 (ツイスト)エドワーズ曲線
Ed448 $ x^2 + y^2 = 1 + dx^2y^2
Ed25519 $ -x^2 + y^2 = 1 +dx^2y^2
ECDH RFC 7748 Curve25519 Curve448 モンゴメリ曲線
$ v^2 = u^3 + Au^2 + u
ECDSAはxからy, EdDSAではyからx，Curve25519, Curve448 では u からvが計算できるのでほぼ半分に圧縮できる
符号は2つあるので符号も別に保存する
table:楕円
用途 署名/鍵交換 署名 鍵交換
曲線 ツイストエドワーズ エドワーズ モンゴメリ
RFC 6090 ? 8032, 7748 7748
RFC PKI 5480,5915
RFC CMS 5753 8419 8418
有限体 GF(p) GF(2^m) GF(p) GF(p) GF(p) GF(p)
ECDH ○ ○ △ △ ○ ○
Curve25519/448 - - △ △ ○ ○
EdWards25519/448 - - ○ ○ △ △
主要パラメータ p, a, b p, a, b p, d p, d p, A p, A
軸座標 x y y u u
生成元 G G B または P B または P P P
部分群 order n L? order
cofactor h? 2^c
鍵(基本的に乱数) 6090 5.3.1
ECDSAは素数GF(p)の生成元とバイナリ系GF(2^m)のがあるよ(他の曲線だと3^mなども原理的には可能)
標準的に使われるP-256,P-384,P-521とビットコイン系のsecp256kが主流?
B系はあまり使わない
EdDSAには2種類の曲線のみ(生成元が違うものもある)
EdWards曲線とECDHのモンゴメリ曲線Curveとは変換可能な関係ではあるかもしれない(変換しない)
ツイストエドワーズ曲線とエドワーズ曲線でアルゴリズムが異なるので2系統
モンゴメリ曲線は共通アルゴリズム?
ECDHはどちらの曲線用もあり
TLSでは鍵に関係なくECDHE?
鍵の構造
RFC 5915 楕円曲線秘密鍵の構造
RFC 5480 公開鍵
RFC 6090 5.3.1 生成
秘密鍵 z
q = order of the generator = n
1 <= z < q
1 <= z < order
公開鍵 Y
alpha 生成元 G
Y = alpha^z
Y = zG
RFC 6090 5.3. KT-IV 署名
5.3.2. 生成
m メッセージ
q order
1. 乱数: 1 <= k < q
2. R = (r_x, r_y) = kG
3. s1 = r_x mod q
4. h(m) + z * s1 = 0 mod q の検証
0 k を再生成, (s1 が 0でないかも検証できる)
5. s2 = k/(h(m) + z*s1) mod q
署名 (s1, s2)
5.3.3 検証
1. 0 < s1 < q かつ 0 < s2 < q の確認
2.
u1 = h(m) * s2 mod q
u2 = s1 * s2 mod q
3. R' = u1G * u2Y
4. R' mod q の x座標とs1が等しいことを検証
RFC 6090 5.4. KT-I 署名
5.4.2. 生成
m メッセージ
q order
1. 乱数 1 <= k < q
2. R = (r_x, r_y) = kG
3. s1 = r_x mod q
4. s2 = (h(m) + z*s1)/k mod q
s1 = 0 または s2 = 0 のときはk を再生成する必要がある(SHOULD)
5. 署名 (s1, s2)
5.4.3. 検証
1. 0 < s1 < q かつ 0 < s2 < q の確認
2. s2_inv = 1/s2 mod q (逆数)を計算
3.
u1 = h(m) * s2_inv mod q
u2 = s1 * s2_inv mod q
4. R' = u1G * u2Y
5. R' mod q の x座標とs1が等しいことを確認
s2 の逆数を計算することで KT-IV署名とKT-I署名は比較可能
KT-I署名が標準っぽい
ハッシュ全体を取るか、楕円鍵のビット長を取るかは複数仕様で異なる?
RFC 7748 セキュリティのための楕円曲線 Elliptic Curves for Security RFC 8032
素数 r
素数を使う場合と2^nっぽいの(ガロア拡大体?)を使う場合があるが、素数側
モジュロ加算 modular addition
モジュロ減算 modular subtraction
モジュロ乗算 modular multiplication
モジュロ逆演算(逆数) modular inverse
2.2 群演算ぐるーぷ(群) Operations ぐるーぷとか群とかいうxとyを持つ計算
元(element)2つ
a と b は乗法表記で * で表す a * b
2 + 3 は a^2 * a^3 のようになり
加法表記もある a + b
e は 最小っぽいもの有限体の逆数かけて元になる値か
元点 (x,y)
加減算、整数倍が可能
2.3 有限体
RFC 6090 適当訳
楕円曲線暗号アルゴリズムの基礎
概要
本稿では、1994年以前のいくつかの重要な文献で定義された楕円曲線暗号（ECC）アルゴリズムの基礎について説明します。これらの説明は、その後数年間に開発された特殊な手法を用いることなく、アルゴリズムの基礎を実装する際に役立つ可能性があります。本稿では、標数が3を超える体上で定義された楕円曲線のみを扱います。これらの曲線は、Suite Bで使用されているものです。 この文書のステータス
この文書は、インターネット標準化過程の仕様ではなく、情報提供を目的として公開されています。
この文書は、インターネット技術タスクフォース（IETF）の成果物です。IETFコミュニティの合意を反映したものであり、インターネット技術運営グループ（IESG）による公開レビューを受け、公開が承認されています。IESGによって承認されたすべての文書が、インターネット標準の候補となるわけではありません。RFC 5741のセクション2を参照してください。 1. はじめに
本稿では、標数が3より大きい有限体上のECCの基本アルゴリズムについて、原典文献を直接参照して解説します。その目的は、インターネットコミュニティに対し、特殊化または最適化されたアルゴリズムよりも古い基本アルゴリズムの概要を提供することです。この概要は、規範的な参考文献として使用できるほど詳細です。原典の記述と表記法に可能な限り忠実に従いました。
ECCアルゴリズムを規定または組み込んでいる標準規格には、インターネット鍵交換（IKE）、ANSI X9.62、IEEE P1363などがあります。このノートで示すアルゴリズムは、適切なパラメータとオプションを選択することにより、これらの標準規格の一部のアルゴリズムと相互運用可能です。詳細は第7章に列挙されています。 このノートの残りの部分は以下のように構成されています。第2.1章、第2.2章、および第2.3章では、それぞれ合同算術(モジュロ算術)、群論、および有限体理論における必要な用語と表記法を示します。第3章では、標数が3より大きい有限体上の楕円曲線に基づく群を定義します。第4章では、基本的な楕円曲線Diffie-Hellman (ECDH)アルゴリズムを示します。第5章では、ElGamal署名方式の楕円曲線版を示します。整数をオクテット文字列として表現する方法は、第6章で規定されています。第2章から第6章までには、規範的なテキスト（この仕様に準拠する実装の規範を定義するテキスト）がすべて含まれており、それ以下のセクションはすべて参考情報として提供されています。相互運用性についてはセクション7で説明します。検証テストについてはセクション8で説明します。セクション9では知的財産権に関する問題について考察します。セクション10ではセキュリティに関する考慮事項をまとめます。付録Bでは乱数生成について説明し、その他の付録ではより詳細な情報を提供します。 1.1. この文書で使用される表記規則
この文書における「しなければならない（MUST）」、「してはならない（MUST NOT）」、「必須（REQUIRED）」、「するものとする（SHALL）」、「するべきではない（SHALL NOT）」、「すべきである（SHOULD）」、「すべきでない（SHOULD NOT）」、「推奨される（RECOMMENDED）」、「してもよい（MAY）」、「任意（OPTIONAL）」というキーワードは、付録Aに記載されているとおりに解釈されます。
2. 数学的背景
このセクションでは、数学的な予備知識を概説し、以下で使用する用語と表記法を定義します。
2.1. モジュロ演算 モジュロ演算 モジュラー演算 Modular Arithmetic 2.2. 群演算 Group Operations 3. 楕円曲線群 Elliptic Curve Groups
この注釈では、標数が3より大きい体上の楕円曲線についてのみ扱います。これらはSuite B Suite B で使用される曲線です。他の体の場合、楕円曲線群の定義は異なります。 体Fp上の楕円曲線は、曲線方程式によって定義されます。
$ y^2 = x^3 + a*x + b
ただし、x、y、a、bは体Fp M1985の元であり、判別式は非零です（3.3.1節で説明されているとおり）。楕円曲線上の点とは、曲線方程式を満たすFp上の値のペア（x,y）のこと、または単位元を表す特別な点(@,@)（「無限遠点(point at infinity)」と呼ばれる）のことを指します。楕円曲線群の位数は、異なる点の数です。 楕円曲線上の二つの点 (x1,y1) と (x2,y2) は、x1=x2 かつ y1=y2 であるか、あるいは両点が無限遠点(infinity)である場合には等しい。点 (x1,y1) の逆(inverse)は点 (x1,-y1) である。無限遠点(point of infinity)は自身の逆(inverse)である。
楕円曲線群に関連する群演算は以下の通りである BC1989。任意の点 P と Q の組を、それぞれ座標 (x1,y1) と (x2,y2) で指定し、この群演算によって、座標 (x3,y3) を持つ第三の点 P*Q を割り当てる。 これらの座標は以下のように計算される。
P が Q と等しくなく、かつ x1 が x2 と等しい場合、
(x3,y3) = (@,@) 。
P が Q と等しくなく、x1 が x2 と等しくない場合、
$ x3 = (\frac{y2-y1}{x2-x1})^2 - x1 - x2 かつ
$ y3 = \frac{(x1-x3)*(y2-y1)}{x2-x1} - y1 。
P が Q と等しく、y1 が 0 と等しい場合、
(x3,y3) = (@,@) 。
P が Q と等しく、y1 が 0 と等しくない場合、
$ x3 = (\frac{3*{x1^2} + a}{2*y1})^2 - 2*x1 かつ
$ y3 = \frac{(x1-x3)*(3*x1^2 + a)}{2*y1} - y1 。
上記の式において、a、x1、x2、x3、y1、y2、および y3 は体 Fp の元である。したがって、実際には x3 と y3 の計算は、右辺を p を法として簡約する必要があります。群演算の擬似コードは付録 F.1 に示されています。
楕円曲線上の点を Zp 内の整数のペアとして表現することをアフィン座標表現といいます。この表現は、群の要素を伝達または格納するための外部データ表現として適していますが、無限遠点は特別なケースとして扱う必要があります。
整数のペアの中には、楕円曲線上の点として有効ではないものがあります。有効なペアは曲線方程式を満たしますが、無効なペアは満たしません。
3.1. 同次座標 Homogeneous Coordinattes
群演算を実装する別の方法として、同次座標系(homogeneous coordinates) K1987 を用いる方法があります（KMOV1991 も参照）。この方法は、モジュロ逆元演算(modular inversion operation)を必要としないため、一般的により効率的です。 楕円曲線上の点 (x,y)（無限遠点 (@,@) を除く）は、x=X/Z mod p かつ y=Y/Z mod p のとき、同次座標系の点 (X,Y,Z) と等しくなります。
P1=(X1,Y1,Z1) および P2=(X2,Y2,Z2) を楕円曲線上の点とし、点 P1 と P2 が (@,@) と等しくなく、P1 が P2 と等しくなく、かつ P1 が $ P2^{-1} と等しくないとします。このとき、積 P3=(X3,Y3,Z3) = P1 * P2 は次式で与えられます。
$ X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) \mod p
$ Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 \mod p
$ Z3 = v^3 * Z1 * Z2 \mod p
ただし、u = Y2 * Z1 - Y1 * Z2 mod p、v = X2 * Z1 - X1 * Z2 mod p です。
点 P1 と P2 が等しいとき、(X1/Z1, Y1/Z1) は (X2/Z2, Y2/Z2) に等しくなります。それと、u と v が両方とも 0 である場合にのみ成り立ちます。
積 P3=(X3,Y3,Z3) = P1 * P1 は次のように与えられます。
$ X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) \mod p
$ Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 \mod p
$ Z3 = 8 * (Y1 * Z1)^3 \mod p
ただし、$ w = 3 * X1^2 + a * Z1^2 \mod p です。上記の式において、a、u、v、w、X1、X2、X3、Y1、Y2、Y3、Z1、Z2、Z3 は集合 Fp に含まれる整数です。同次座標における群演算の擬似コードは付録 F.2 に示されています。
アフィン座標から同次座標に変換する場合は、Z を 1 に設定すると便利です。同次座標からアフィン座標に変換する場合は、モジュラー逆演算を実行して 1/Z mod p を見つける必要があります。
3.2. その他の座標系 Other Coordinates
他にもいくつかの座標系が記述されており、ヤコビ座標系を含むいくつかはCC1986に記載されています。 3.3. ECCパラメータ
暗号学の文脈において、楕円曲線パラメータセットは、楕円曲線の巡回部分群と、その部分群の優先生成元から構成されます。標数が3より大きい素数位数有限体を扱う場合、楕円曲線群は以下のパラメータによって完全に指定されます。
体Fpの位数を示す素数p。
曲線方程式で使用される値a。
曲線方程式で使用される値b。
部分群(subgroup)の生成元(generator) g。
gによって生成される部分群の位数n。
ECCパラメータセットの例は付録Dに記載されています。
パラメータ生成については、本稿では扱いません。
各楕円曲線点は、特定のパラメータセットに関連付けられています。楕円曲線群の演算は、同じ群内の2点間でのみ定義されます。異なるグループに属する2つの要素にグループ演算を適用したり、有効な点ではない座標のペアにグループ演算を適用したりするとエラーになります。（Fp内の座標のペア（x,y）は、曲線方程式を満たす場合にのみ有効な点となります。）詳細については、セクション10.3を参照してください。
3.3.1. 判別式
各楕円曲線群について、判別式 -16*(4*a^3 + 27*b^2) は p を法として非ゼロでなければならない S1986。これは、 $ 4*a^3 + 27*b^2 \neq 0 \mod p
であることを必要とする。
3.3.2. セキュリティ
セキュリティはこれらのパラメータの選択に大きく依存します。本節では、許容される選択に関する規範的なガイダンスを示します。参考となるガイダンスについては、第10節も参照してください。
g によって生成される群の位数は、離散対数問題 K1987 の容易な解を排除するため、大きな素数で割り切れる必要があります。 パラメータの選択によっては、離散対数問題の解法が大幅に容易になります。これには、b = 0 かつ p = 3 (mod 4) のパラメータセットや、a = 0 かつ p = 2 (mod 3) のパラメータセットが含まれます MOV1993。これらのパラメータ選択は暗号用途には適さないため、使用すべきではありません。 4. 楕円曲線Diffie-Hellman (ECDH)
Diffie-Hellman鍵交換 (DH)プロトコル DH1976 は、安全でない通信路を介して通信する2者が秘密鍵に合意することを可能にします。DH は元々、大きな素数標数を持つ体の乗法群における演算を用いて定義されました。Massey M1983 は、DH が任意の巡回群を用いて定義されるように容易に一般化できることを指摘しました。Miller M1985 と Koblitz K1987 は、楕円曲線群上の DH プロトコルを解析しました。ここでは、前述の文献に従って DH について説明します。 G を群(group)とし、g をその群の生成元(generator)とし、t を G の位数(order)とします。DH プロトコルは以下のように実行されます。 Aは1とt-1（両端を含む）の間の指数jを一様ランダムに選択し、$ g^jを計算し、その要素をBに送ります。Bは1とt-1（両端を含む）の間の指数kを一様ランダムに選択し、$ g^kを計算し、その要素をAに送ります。各当事者は$ g^{(j*k)}を計算でき、Aは$ (g^k)^jを計算し、Bは$ (g^j)^kを計算します。
乱数生成については付録Bを参照してください。
4.1. データ型
ECDHプロトコルの各実行は、特定のパラメータセット（セクション3.3で定義）に関連付けられており、公開鍵$ g^jと$ g^k、および共有秘密鍵$ g^{(j*k)}は、パラメータセットに関連付けられた巡回部分群の要素です。
ECDH秘密鍵zはZtの整数であり、tは部分群の位数です。
4.2. コンパクト表現
M1985の最終段落で述べられているように、指数関数を一方向性関数として使用する場合、共有秘密値$ g^{(j*k)}のx座標は、点全体の適切な表現となります。ECDH鍵交換プロトコルでは、要素$ g^{(j*k)}を計算した後、その値のx座標を共有秘密として使用できます。これをコンパクト出力と呼びます。 M1985に再び従うと、ECDHでコンパクト出力を使用する場合、典型的なアフィン座標表現のように両方の座標を送信するのではなく、楕円曲線点のx座標のみを送信すれば済みます。これをコンパクト表現と呼びます。その数学的な背景については付録Cで説明します。 ECDHは、コンパクト出力の有無にかかわらず使用できます。ECDHプロトコルの特定の実行においては、両当事者は同じ手法を使用する必要があります。ECDHは、コンパクト表現の有無にかかわらず使用できます。 ECDH プロトコルの特定の実行でコンパクト表現が使用される場合は、コンパクト出力も使用する必要があります。
(別ページに分割)
6. 整数とオクテット文字列の変換
このセクションでは、公開鍵暗号 R1993 の確立された規約に従い、整数とオクテット文字列間の変換方法を規定します。この方法により、整数を伝送または保存に適したオクテット文字列として表現することができます。この方法は、本ノートで定義されている楕円曲線の点または楕円曲線座標を表現する際に使用する必要があります。 6.1. オクテット文字列から整数への変換
オクテット文字列 S は、以下のように整数 x に変換される。
S1, ..., Sk を S の先頭から末尾までのオクテットとする。整数 x は、次の式を満たす。
$ x = \sum_{i=1}^k 2^{8(k-i)}Si
言い換えれば、S の最初のオクテットは整数の中で最も重要度が高く、最後のオクテットは最も重要度が低い。
注：整数 x は $ 0 <= x < 2^{(8*k)} を満たす。
6.2. 整数からオクテット文字列への変換
整数 x は、以下のように長さ k のオクテット文字列 S に変換される。文字列 S は、以下の式を満たすものとする。
$ y = \sum_{i=1}^k 2^{8(k-i)} Si
ここで、S1, ..., Sk は、S の先頭から末尾までのオクテットである。
言い換えれば、S の最初のオクテットは整数の中で最も重要度が高く、最後のオクテットは最も重要度が低い。
7. 相互運用性
このノートに記載されているアルゴリズムは、他のECC仕様との相互運用に使用できます。このセクションでは、各アルゴリズムの詳細について説明します。
7.1. ECDH
セクション4は、インターネット鍵交換（IKE）バージョン1 RFC2409 またはバージョン2 RFC5996 で使用できます。これらのアルゴリズムは、RFC5903、RFC5114、RFC2409、およびRFC2412 で定義されているECPグループと互換性があります。このプロトコルのグループ定義では、公開鍵のアフィン座標表現を使用します。RFC5903 はセクション4.2 のコンパクト出力を使用しますが、RFC4753（RFC 5903 によって廃止されました）は使用しません。どちらのRFCもコンパクト表現を使用していません。一部のグループでは、曲線パラメータ「a」が負であると示されていることに注意してください。これらの値は、体の位数を法として解釈されます。例えば、パラメータ a = -3 は p - 3 に等しくなります。ここで、p は体の位数です。 RFC5903 のセクション8のテストケースは実装のテストに使用できます。これらのケースでは、この注記と同様に乗法表記が用いられます。KEiペイロードとKErペイロードはそれぞれg^jとg^kに等しく、64ビットの符号化データが先頭に付加されます。 セクション4のアルゴリズムは、特性値が3より大きいフィールドに基づくECDHのIEEE P1363およびANSI X9.62標準規格との相互運用性を確保するために使用できます。 IEEE P1363 ECDH は、この仕様書に記載されている以下のオプションとパラメータを選択することで、本ノートと相互運用可能な方法で使用できます。 係数が 1 の素曲線、
ECSVDP-DH（楕円曲線秘密値導出プリミティブ、Diffie-Hellman 版）、
鍵導出関数 (KDF) は「同一性」関数である必要があります（つまり、KDF ステップを省略し、共有秘密値を直接出力する必要があります）。 7.2. KT-IとECDSA
デジタル署名アルゴリズム（DSA）は、大きな素数位数を持つ有限体の乗法部分群上の離散対数問題に基づいています DSA1991 FIPS186。楕円曲線デジタル署名アルゴリズム（ECDSA）P1363 X9.62 は、DSAの楕円曲線版です。 KT-Iは数学的にも機能的にもECDSAと等価であり、3より大きい標数体に基づく楕円曲線DSA（ECDSA）のIEEE P1363 およびANSI X9.62 標準と相互運用可能です。KT-I署名はECDSA検証アルゴリズムを用いて検証でき、ECDSA署名はKT-I検証アルゴリズムを用いて検証できます。 8. 実装の検証
暗号アルゴリズムの実装を検証することは不可欠です。このセクションでは、このノートで定義されるアルゴリズムに対して実行すべきテストの概要を示します。
既知解テスト（KAT）は、固定された入力セットを用いてアルゴリズムをテストします。アルゴリズムの出力は、同じく固定値である期待出力と比較されます。ECDHおよびKT-IのKATについては、以下のサブセクションで説明します。
整合性テストは、テスト対象のアルゴリズムに対し、同じくテスト対象の2つ目のアルゴリズムを用いて入力を生成し、最初のアルゴリズムの出力を検証します。署名作成アルゴリズムは、署名検証アルゴリズムと比較して整合性をテストできます。KT-Iの実装は、この方法でテストする必要があります。KT-Iの署名生成プロセスは非決定論的であるため、KATを使用してテストすることはできません。一方、署名検証アルゴリズムは決定論的であるため、KATを使用してテストする必要があります。このテストの組み合わせにより、鍵ペア生成を含むすべての操作を網羅できます。一貫性テストは ECDH にも適用する必要があります。
8.1. ECDH
ECDH実装は、RFC 5903またはRFC 5114の既知の解答テストケースを用いて検証できます。RFC 5903の表記とこのノートの表記の対応関係は、以下の表にまとめられています。（3.3節および4節を参照。生成元gはアフィン座標表現で(gx, gy)と表されます。） table:ECDH RFC 5903
ECDH RFC 5903
体 Fp の位数 p p
曲線係数 a -3
曲線係数 b b
生成子 g g=(gx, gy)
秘密鍵 j と k i と r
公開鍵 g^j, g^k g^i = (gix, giy) かつ g^r = (grx, gry)
RFC 5114 の表記法とこのノートの表記法の対応関係は、次の表にまとめられています。
table:ECDH RFC 5114
ECDH RFC 5114
体 Fp の位数 p p
曲線係数 a a
曲線係数 b b
生成子 g g=(gx, gy)
群位数 n n
秘密鍵 j と k dA と dB
公開鍵 g^j, g^k g^(dA) = (x_qA, y_qA) と
g^(dB) = (x_qB, y_qB)
共有秘密鍵 g^(j*k) g^(dA*dB) = (x_Z, y_Z)
8.2. KT-I
KT-I実装は、RFC4754の既知解テストケースを用いて検証できます。このRFCにおける表記と本ノートにおける表記の対応関係は、以下の表にまとめられています。 table:KT-I RFC 4754
KT-I RFC 4754
体 Fp の位数 p p
曲線係数 a -3
曲線係数 b b
生成元 alpha g
群位数 q q
秘密鍵 z w
公開鍵 Y g^w = (gwx,gwy)
ランダム k ephem priv k
s1 r
s2 s
s2_inv sinv
u1 u = h*sinv mod q
u2 v = r*sinv mod q
9. 知的財産
近年、多くの最適化や特殊なアルゴリズムが特許取得されているため、知的財産に関する懸念からECCの採用が遅れています。
ECDH（セクション4で定義）に関するすべての規範的参照は1989年またはそれ以前に発行されており、KT-Iに関するすべての規範的参照は1994年5月またはそれ以前に発行されています。これらのアルゴリズムに関する規範的テキストはすべて、それぞれの参照のみに基づいています。
9.1. 免責事項
本文書は法的助言を目的としたものではありません。読者は、ご自身の権利に関する法的解釈をご希望の場合は、ご自身の法律顧問にご相談ください。
10. セキュリティに関する考慮事項
楕円曲線暗号のセキュリティレベルは、攻撃者が実装するのに最も費用がかからない暗号解読アルゴリズムによって決定されます。考慮すべきアルゴリズムはいくつかあります。
Pohlig-Hellman法は分割統治法ですPH1978。 群の位数nが次のように因数分解できる場合
n = q1 * q2 * ... * qz
群上の離散対数問題は、位数q1、q2、...、qzの群における離散対数問題を独立に解き、その結果を中国剰余定理を用いて結合することで解くことができます。全体的な計算コストは、最大の位数を持つ部分群における離散対数問題の計算コストによって支配されます。
Shanksアルゴリズム K1981v3 は、n次の群における離散対数を、O(sqrt(n)) の演算量と O(sqrt(n)) の記憶容量で計算します。Pollard rhoアルゴリズム P1978 は、n次の群における離散対数を、O(sqrt(n)) の演算量と無視できる記憶容量で計算し、効率的に並列化できます VW1994。 Pollard lambdaアルゴリズム P1978 は、指数が幅wの区間内にあることが分かっている場合、O(sqrt(w)) の演算量と O(log(w)) の記憶容量で離散対数問題を解くことができます。 上記のアルゴリズムは、任意の群で動作します。楕円曲線群に特化した特殊なアルゴリズムも存在します。一般的な楕円曲線群に対する部分指数アルゴリズムは知られていないが、特定の特殊な楕円曲線群を対象とする手法は存在する。MOV1993およびFR1994を参照。 10.1. 部分群
空でない元集合 S とそれに関連する群演算 * からなる群は、元集合 G を持つ群の部分群である。この場合、後者の群が同じ群演算を用い、S が G の部分集合である。各楕円曲線方程式に対して、群位数が楕円曲線の位数に等しい楕円曲線群が存在する。つまり、曲線上のすべての点を含む群が存在する。
楕円曲線の位数 m は、生成元に関連付けられた群の位数 n で割り切れる。つまり、各楕円曲線群について、ある数 c に対して m = n * c が成立する。数 c は「余因子」と呼ばれる P1363。3.3 節で示した各 ECC パラメータセットは、特定の余因子に関連付けられる。 余因子を 1 とすることも可能であり、望ましい。
10.2. Diffie-Hellman
第4節で定義される鍵交換プロトコルは、能動的な攻撃から保護するものではないことに注意してください。当事者Aは、(g^k)が攻撃者ではなく意図された通信相手Bによって発信されたことを確認するための何らかの方法を用いる必要があり、当事者Bは(g^j)についても同様の方法を用いる必要があります。
共有秘密g^(j*k)を認証するだけでは不十分です。なぜなら、これではプロトコルが公開鍵を操作する攻撃に対して無防備になってしまうからです。代わりに、交換される公開鍵g^xとg^yの値を直接認証する必要があります。これは、Diffie-Hellmanを基盤とし、エンドエンティティ認証を用いて能動的な攻撃から保護するプロトコル（OAKLEY RFC2412やインターネット鍵交換 RFC2409 RFC4306 RFC5996など）で用いられる戦略です。 10.3. 群の表現とセキュリティ
楕円曲線群演算は、曲線方程式のパラメータ b を明示的に組み込んでいません。そのため、悪意のある攻撃者が偽の公開鍵 BMM2000 を提示することで、ECDH 秘密鍵に関する情報を入手される可能性があります。攻撃者は、ECDH プロトコルで使用されている群 G と同一のパラメータを持ち、b が異なる楕円曲線群 G' を作成できます。攻撃者は、群 G を使用している ECDH プロトコルの実行に G' 上の点を提示し、攻撃対象デバイスの秘密鍵を用いた群演算が、実際には G ではなく G' で行われているという事実から情報を得ることができます。 この攻撃は、静的な公開鍵、つまりプロトコルの複数の実行で使用される公開鍵に関連付けられた ECDH 秘密鍵に関する有用な情報を入手することができます。しかし、一時鍵に対しては有用な情報は得られません。
この種の攻撃は、ECDH実装においてZpの各座標ペアが適切な楕円曲線上の点であると仮定していない場合、阻止されます。
これらの考慮事項は、ECDHをコンパクト表現で使用する場合にも適用されます（付録Cを参照）。
10.4. 署名
楕円曲線パラメータは、信頼できる情報源から取得された場合のみ使用すべきである。そうでない場合、攻撃の可能性がある AV1996 V1996。 ElGamal署名システムにおいてハッシュ関数が使用されていない場合、システムは存在偽造に対して脆弱となる。存在偽造とは、秘密鍵を知らない攻撃者が、対応する公開鍵に対して有効な署名を生成することはできるが、攻撃者が選択したメッセージに対しては署名を生成することができない状態を指す。(例えば E1985 を参照。) 衝突耐性ハッシュ関数を使用することで、この脆弱性は解消される。 原則として、衝突耐性ハッシュ関数であれば、KT署名に使用できる。相互運用性を高めるため、以下のハッシュを、セクション5.2で定義される関数Hとして使用できるものと認識している。
SHA-256（出力ビット数256ビット）。
SHA-384（出力ビット数384ビット）。
SHA-512（出力ビット数512ビット）。
KT署名で使用されるハッシュの出力ビット数は、グループ順序を表すために必要なビット数と等しいか、それに近い値である必要があります。
11. 謝辞
著者は、本論文の執筆を可能にした楕円曲線暗号の創始者たち、そして貴重で建設的なフィードバックを提供してくれたすべての査読者に感謝の意を表します。特に、Howard Pinder、Andrey Jivsov、Alfred Hoenes（付録Fのアルゴリズムを提供した）、Dan Harkins、Tina Tsouに感謝の意を表します。
12. 参考文献
12.1. 規範的参考文献
AMV1990 Agnew, G.、Mullin, R.、S. Vanstone、「離散べき乗法に基づく改良型デジタル署名方式」、Electronics Letters Vol. 26, No. 14、1990年7月。 BC1989 Bender, A. および G. Castagnoli, "楕円曲線暗号システムの実装について"、Advances in Cryptology - CRYPTO '89 Proceedings、Springer Lecture Notes in Computer Science (LNCS)、第435巻、1989年。 CC1986 Chudnovsky, D. および G. Chudnovsky, "形式群における加算によって生成される数列と新しい素数性および因数分解テスト"、Advances in Applied Mathematics、第7巻、第4号、1986年12月。 D1966 Deskins, W., "抽象代数"、MacMillan Company New York、1966年。 DH1976 Diffie, W. および M. Hellman, "暗号技術における新しい方向性"、IEEE Transactions in Information Theory IT-22、 pp. 644-654, 1976. FR1994 Frey, G. および H. Ruck, 「曲線の因子類群におけるm-割り切れることと離散対数に関する一考察」『計算数学』第1巻 62, No. 206, pp. 865-874, 1994.
HMP1994 Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal署名方式", ケムニッツ-ツヴィッカウ工科大学 コンピュータサイエンス学科 技術報告書 TR-94-5, 1994年5月. K1981v2 Knuth, D., "The Art of Computer Programming, Vol. 2: Seminumerical Algorithms", Addison Wesley , 1981.
K1987 Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics of Computation, Vol. 48, 1987, pp. 203-209, 1987. KT1994 小山 憲一, 鶴岡 勇, 「楕円曲線に基づくデジタル署名システムとその署名装置及び検証装置」, 特開平6-43809, 1994年2月18日. M1983 Massey, J., 「有限巡回群における対数 - 暗号問題」, 第4回情報理論シンポジウム論文集, 1983. M1985 Miller, V., 「暗号における楕円曲線の利用」, Advances in Cryptology - CRYPTO '85 論文集, Springer Lecture Notes in Computer Science (LNCS), 第218巻, 1985. MOV1993 Menezes, A., Vanstone, S., and T. Okamoto, "Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field, IEEE Transactions on Information Theory, Vol. 39, No. 5, pp. 1639-1646, September, 1993.
R1993 RSA Laboratories, "PKCS#1: RSA Encryption Standard", Technical Note version 1.5, 1993. S1986 Silverman, J., "The Arithmetic of Elliptic Curves", Springer-Verlag, New York, 1986. 12.2. 参考文献
A1992 Anderson, J., "Response to the proposal DSS", Communications of the ACM, v. 35, n. 7, p. 50-52、1992年7月。 AV1996 Anderson, R. および S. Vaudenay、「PとQに注意」、Advances in Cryptology - ASIACRYPT '96 Proceedings、Springer Lecture Notes in Computer Science (LNCS)、第1163巻、1996年。 BMM2000 Biehl, I.、Meyer, B.、および V. Muller、「楕円曲線暗号システムにおける差分フォールト解析」、Advances in Cryptology - CRYPTO 2000 Proceedings、Springer Lecture Notes in Computer Science (LNCS)、第1880巻、2000年。 BS1992 Branstad, D. および M. Smid、「NISTデジタル署名標準案に関するコメントへの回答」、Advances in Cryptology - CRYPTO '92 Proceedings、Springer Lecture Notes in Computer Science (LNCS)、第740巻、1992年8月。 DSA1991 米国国立標準技術研究所、「デジタル署名標準」、連邦官報、第56巻、1991年8月。 E1984a ElGamal, T.、「有限体上の暗号化と対数」、スタンフォード大学、UMI注文番号DA 8420519、1984年。 E1984b ElGamal, T.、「有限体上の暗号化と対数」、Advances in Cryptology - CRYPTO '84 Proceedings、Springer Lecture Notes in Computer Science (LNCS)、第196巻、1984年。
E1985 ElGamal, T.、「離散対数に基づく公開鍵暗号システムと署名方式」、IEEE Transactions on Information Theory、Vol. 30、No.4、469-472ページ、 1985年。
「SECURE HASH STANDARD」、連邦情報処理
規格 (FIPS) 180-2、2002 年 8 月。
「デジタル署名標準」、連邦情報
処理規格 FIPS-186、1994 年 5 月。
HP1994 Horster、P.、H. Petersen、「Verallgemeinerte ElGamal-」 Signaturen」、Proceedings der Fachtagung SIS '94、Verlag
デア・ファッハフェライン、チューリッヒ、1994年。
K1981v3 Knuth, D.、「The Art of Computer Programming」Vol. 3: ソートと検索」、Addison Wesley、1981年。
KMOV1991 Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, 「環Zn上の楕円曲線に基づく新しい公開鍵方式」、Advances in Cryptology - CRYPTO '91
Proceedings、Springer Lecture Notes in Computer Science
(LNCS)、第576巻、1991年。
L1969 Lehmer, D., 「数理論へのコンピュータ技術の応用」、M.A.A. Studies in Mathematics, 180-2, 1969. LL1997 Lim, C. および P. Lee, 「素数位数部分群を用いた離散対数ベース方式に対する鍵回復攻撃」, Advances in Cryptology - CRYPTO '97 Proceedings, Springer Lecture Notes in Computer Science
(LNCS), 第1294巻, 1997.
NR1994 Nyberg, K. および R. Rueppel, 「離散対数問題に基づく署名方式のメッセージ回復」, Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer Lecture Notes in Computer Science
(LNCS), 第950巻, 1994年5月.
P1363 「公開鍵暗号の標準仕様」, Institute of Electric and Electronic Engineers (IEEE), P1363, 2000年
P1978 Pollard, J., 「指数計算のためのモンテカルロ法」、Mathematics of Computation、第32巻、1978年。 PH1978 Pohlig, S. および M. Hellman, 「GF(p) 上の対数計算のための改良アルゴリズムとその暗号学的意義」, IEEE Transactions on Information Theory, Vol. 24, pp. 106-110, 1978. R1988 Rose, H., 「数論講座」, Oxford University Press, 1988. R1992 Rivest, R., 「提案された DSS への対応」, Communications of the ACM, v. 35, n. 7, p. 41-47、1992年7月。 RFC2119 Bradner, S.、「RFCで要件レベルを示すキーワード」、BCP 14、RFC 2119、1997年3月。 RFC2409 Harkins, D. および D. Carrel、「インターネット鍵交換 (IKE)」、RFC 2409、1998年11月。 RFC2412 Orman, H.、「OAKLEY鍵決定プロトコル」、RFC 2412、1998年11月。 RFC3979 Bradner, S.、「IETF技術における知的財産権」、BCP 79、RFC 3979、2005年3月。 RFC4086 Eastlake, D.、Schiller, J.、およびS. Crocker、 「セキュリティのためのランダム性要件」、BCP 106、RFC 4086、2005年6月。 RFC4306 Kaufman, C.、「インターネット鍵交換（IKEv2）プロトコル」、RFC 4306、2005年12月。 RFC4753 Fu, D.、J. Solinas、「IKEおよびIKEv2のECPグループ」、RFC 4753、2007年1月。 RFC4754 Fu, D.、J. Solinas、「楕円曲線デジタル署名アルゴリズム（ECDSA）を使用したIKEおよびIKEv2認証」、RFC 4754、2007年1月。 RFC4879 Narten, T.、「RFC 3979における第三者開示手順の明確化」、BCP 79、RFC 4879、2007年4月。 2007年 RFC5114 Lepinski, M. および S. Kent, 「IETF標準で使用するための追加のDiffie-Hellmanグループ」、RFC 5114、2008年1月 RFC5903 Fu, D. および J. Solinas, 「IKEおよびIKEv2における素数を法とする楕円曲線グループ（ECPグループ）」、RFC 5903、2010年6月 RFC5996 Kaufman, C.、Hoffman, P.、Nir, Y.、およびP. Eronen、「インターネット鍵交換プロトコル バージョン2 (IKEv2)」、RFC 5996、2010年9月。 suiteb_cryptography/index.shtml>。
V1996 Vaudenay, S., 「DSS における隠れた衝突」, Advances in Cryptology - CRYPTO '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), 第 1109 巻, 1996 年. VW1994 van Oorschot, P. および M. Wiener, 「並列衝突探索とハッシュ関数および離散対数への応用」, Proceedings of the 2nd ACM Conference on Computer and communications security, pp. 210-218, 1994 年. VW1996 van Oorschot, P. および M. Wiener, 「短い指数を持つ Diffie-Hellman 鍵の一致について」, Advances in Cryptology - EUROCRYPT '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), 第 1109 巻1070, 1996. X9.62 「金融サービス業界向け公開鍵暗号：楕円曲線デジタル署名アルゴリズム（ECDSA）」、米国規格協会（ANSI） X9.62.
付録A. キーワード
これらのキーワードの定義はRFC2119から引用されており、インターネット標準で一般的に使用されています。1994年以降の規範的な参照を避けるため、この注記に再録します。 1. MUST - この単語、または「REQUIRED（必須）」もしくは「SHALL（すべきである）」という用語は、その定義が仕様の絶対的な要件であることを意味します。
2. MUST NOT - このフレーズ、または「SHALL NOT（すべきではない）」というフレーズは、その定義が仕様の絶対的な禁止であることを意味します。
3. SHOULD - この単語、または形容詞「RECOMMENDED（推奨される）」は、特定の状況において特定の項目を無視する正当な理由が存在する可能性があることを意味しますが、異なる方針を選択する前に、その意味を完全に理解し、慎重に検討する必要があります。
4. SHOULD NOT すべきではない - このフレーズ、または「NOT RECOMMENDED 推奨されない」というフレーズは、特定の状況において、特定の動作が許容される、あるいは有用である正当な理由が存在する可能性があることを意味します。ただし、このラベルが付いた動作を実装する前に、その意味を完全に理解し、ケースを慎重に検討する必要があります。
5. MAY してもよい - この単語、または形容詞「OPTIONAL オプション」は、項目が真にオプションであることを意味します。あるベンダーは、特定の市場で必要とされている、または製品の機能強化に役立つと判断したために、その項目を含めることを選択する場合があります。一方、別のベンダーは同じ項目を省略する場合があります。特定のオプションを含まない実装は、機能が制限される可能性はありますが、そのオプションを含む別の実装と相互運用できるように準備する必要があります。同様に、特定のオプションを含む実装は、そのオプションを含まない別の実装と相互運用できるように準備する必要があります（もちろん、そのオプションが提供する機能は除きます）。
付録 B. ランダム整数生成
ある正の整数 t に対して、0 から (2^t)-1 まで（両端を含む）の一様ランダムな整数を生成することは簡単です。まず t ビットのランダムビット列を生成し、そのビット列を整数の 2 進展開における係数として扱うことで、非負整数に変換します。整数 r を一様ランダムに生成し、例えば r が特定の性質 P を満たすように、例えば特定の区間内に存在するようにする必要がある場合もあります。これを行う簡単な方法は、棄却法です。
1. 性質 P を満たすすべての数値（および他のいくつかの数値、できればあまり多くない数値）を含む集合から、候補となる数値 c を一様ランダムに生成します。
2. c が性質 P を満たす場合、c を返します。それ以外の場合は、手順1に戻ります。
例えば、1からn-1まで（両端を含む）の数値を生成するには、0から(2^t)-1まで（両端を含む）の整数を繰り返し生成し、その区間に含まれる最初の整数で停止します。
ランダムビット文字列の生成方法に関する推奨事項は、RFC4086に記載されています。 付録 C. コンパクト表現が機能する理由
アフィン表現では、任意の非負指数 i と任意の点 P に対して、点 P^i の x 座標は点 P の y 座標に依存しません。この事実は次のように示されます。点 P の x 座標のみが与えられた場合、y 座標を正確に決定することはできませんが、y 値は曲線方程式の解となります。
$ y^2 = x^3 + a*x + b (\mod p)
最大で y = w と y = -w mod p の 2 つの異なる解が存在し、点 P は Q=(x,w) または Q^-1=(x,-w) のいずれかでなければなりません。したがって、P^n は Q^n または (Q^-1)^n = (Q^n)^-1 のいずれかに等しくなります。これらの値は同じ x 座標を持ちます。したがって、点 P^i の x 座標は、点 P の x 座標から、P の y 座標の可能な値の 1 つを計算し、次に P の i 乗を計算し、その結果の y 座標を無視することによって計算できます。
一般に、Shanks 法 K1981v2 を用いて p を法とする平方根を計算することができます。p の値によっては、簡単な方法が存在します。p = 3 (mod 4) の場合、z mod p の平方根は w と -w mod p です。 ここで、
$ w = z ^ {(p+1)/4} (\mod p)
この観察は Lehmer L1969 によるものです。p がこの性質を満たす場合、y は曲線方程式から計算でき、y = w または y = -w mod p のいずれかとなります。ここで、 $ w = (x^3 + a*x + b)^{(p+1)/4} (\mod p)
pを法とする平方根は、pを法とする平方剰余に対してのみ存在します（R1988）。もしzが平方剰余でなければ、w^2 = z (mod p)となるような数wは存在しません。wを計算した後にzが平方剰余であることを確認する簡単な方法は、w * w = z (mod p)であることを確認することです。この関係が上記の式で成立しない場合、値xは有効な楕円曲線点の有効なx座標ではありません。これは、ECDHをコンパクト出力で使用する際に重要な考慮事項です。10.3節を参照してください。 RFC5903で説明されているP-256、P-384、およびP-521曲線で使用される素数はすべて、p = 3 (mod 4)という性質を持ちます。 付録D. ECCパラメータセットの例
具体的には、SolinasとFuがRFC5903で定義し、128ビットのセキュリティレベルを提供すると考えられているP-256と呼ばれる楕円曲線を想起します。3.3節の表記法を使用し、生成子をアフィン座標表現g=(gx,gy)で表します。ここで、値gxとgyはFpに含まれます。 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a: - 3
b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
pは次のようにも表せることに注意してください。
$ p = 2^{256}-2^{224}+2^{192}+2^{96}-1.
付録E. 加法表記と乗法表記
楕円曲線暗号に関する初期の出版物では乗法表記が使用されていましたが、最近の出版物のほとんどは加法表記を使用しています。このセクションでは、これら2つの表記法の対応表を示します。このセクションでは、aとbは楕円曲線群の元であり、Nは整数です。
table:乗法表記と加法表記
乗法表記 加法表記
乗算 加算
a * b a + b
2乗 2倍
a * a = a^2 a + a = 2a
べき乗 スカラー乗算
a^N = a * a * ... * a Na = a + a + ... + a
逆数 逆数
a^-1 -a
付録F. アルゴリズム
このセクションでは、楕円曲線群演算の擬似コード記述を示します。記号「//」に続くテキストは、命令ではなくコメントとして解釈されます。
F.1. アフィン座標
楕円曲線上の任意の点PとQの組（アフィン座標P=(x1,y1)とQ=(x2,y2)で指定）に対し、群演算によって、座標(x3,y3)を持つ3番目の点R = P*Qが割り当てられます。これらの座標は次のように計算されます。
code:Affine
if P is (@,@),
R = Q
else if Q is (@,@),
R = P
else if PはQと等しくなく、x1はx2と等しい,
R = (@,@)
else if PはQと等しくなく、x1はx2と等しくない,
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
else if PはQに等しく、y1は0に等しい,
R = (@,@)
else // PはQと等しく、y1は0と等しくない
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.
1つ目と2つ目のケースから、無限遠点はこの演算の中立元であり、無限遠点自身の逆元であることがわかります。
曲線方程式から、与えられた曲線点P = (x,y) に対して、無限遠点とは異なる点 (x,-y) も曲線点であることがわかり、3つ目と5つ目のケースから、これがPの逆元、P^-1であることがわかります。
注：5つ目と6つ目のケースは「点の2乗」として知られています。
F.2. 同次座標
楕円曲線上の点 (x, y) (無限遠点 (@, @) を除く) は、x=X/Z かつ y=Y/Z のとき、同次座標 (X, Y, Z) の点と等価です。(X、Y、Z は Fp に含まれますが、3 つすべてが同時に 0 になることはありません)。「同次座標」とは、Fp に X'=s*X、Y'=s*Y、Z'=s*Z となる非零の s が存在する場合、2 つの 3 項 (X, Y, Z) と (X', Y', Z') が「等しい」(つまり、同じ点を表す) とみなされることを意味します。無限遠点 (@, @) は、同次座標 (0, 1, 0) と等価とみなされます。つまり、Fp に Y が 0 でない任意の 3 項 (0, Y, 0) で表すことができます。
P1=(X1,Y1,Z1) および P2=(X2,Y2,Z2) を楕円曲線上の点とし、u = Y2 * Z1 - Y1 * Z2、v = X2 * Z1 - X1 * Z2 とします。
点 P1 と P2 が等しいのは、u と v が両方とも 0 の場合のみです。そうでない場合、P1 または P2 のいずれかが無限遠点に等しい場合、v は 0 で u は 0 以外になります（ただし、逆の含意は成り立ちません）。
すると、積 P3=(X3,Y3,Z3) = P1 * P2 は次のように与えられます。
code:Homogeneous
if P1は無限遠点である,
P3 = P2
else if P2は無限遠点である,
P3 = P1
else if uは0ではないが、vは0である,
P3 = (0,1,0)
else if uとvはどちらも0ではない,
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
Z3 = v^3 * Z1 * Z2
else // P2 equals P1, P3 = P1 * P1
w = 3 * X1^2 + a * Z1^2
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
Z3 = 8 * (Y1 * Z1)^3
したがって、無限遠点は単位元であることがわかります。
そして、P1=(X,Y,Z)がこの無限遠点と等しくない場合、P2=(X,-Y,Z)はP1^-1を表します。
著者の住所
David A. McGrew
シスコシステムズ
510 McCarthy Blvd.
Milpitas, CA 95035
アメリカ合衆国
電話: (408) 525 8651
Eメール: mcgrew@cisco.com
Kevin M. Igoe
国家安全保障局
Commercial Solutions Center
アメリカ合衆国
Eメール: kmigoe@nsa.gov
Margaret Salter
国家安全保障局
9800 Savage Rd.
Fort Meade, MD 20755-6709
アメリカ合衆国
Eメール: msalter@restarea.ncsc.mil