-
-
Notifications
You must be signed in to change notification settings - Fork 0
RFC6090
RFC 6090 適当訳
この文書では、1994年以前のいくつかの重要な文献で定義された楕円曲線暗号（ECC）アルゴリズムの基礎について説明します。これらの説明は、その後数年間に開発された特殊な手法を用いることなく、アルゴリズムの基礎を実装する際に役立つ可能性があります。本文書では、標数が3を超える体上で定義された楕円曲線のみを扱います。これらの曲線は、Suite Bで使用されているものです。
この文書は、インターネット標準化過程の仕様ではなく、情報提供を目的として公開されています。
この文書は、インターネット技術タスクフォース（IETF）の成果物です。IETFコミュニティの合意を反映したものであり、インターネット技術運営グループ（IESG）による公開レビューを受け、公開が承認されています。IESGによって承認されたすべての文書が、インターネット標準の候補となるわけではありません。RFC5741のセクション2を参照してください。
このドキュメントの現在のステータス、エラータ、およびフィードバックの提供方法については、http://www.rfc-editor.org/info/rfc6090 で入手できます。
著作権表示
Copyright (c) 2011 IETF Trustおよび本書の著者として特定されている人物。All rights reserved.
本文書は、BCP 78およびIETF TrustのIETF文書に関する法的規定（http://trustee.ietf.org/license-info）の対象となります。これらの規定には、本文書に関するお客様の権利と制限が記載されているため、注意深くお読みください。本文書から抽出されたコードコンポーネントには、Trustの法的規定のセクション4.eに記載されているSimplified BSD Licenseのテキストが含まれている必要があり、Simplified BSD Licenseに記載されているように、保証なしで提供されます。
ECCは、より高いセキュリティレベルで性能上の利点を提供する公開鍵技術です。ECCには、Diffie-Hellman鍵交換プロトコルDH1976の楕円曲線バージョンと、ElGamal署名アルゴリズムE1985の楕円曲線バージョンが含まれます。ECCの採用は予想よりも遅れており、これはおそらく、自由に利用できる規範文書の不足と知的財産権に関する不確実性によるものと考えられます。
本稿では、標数が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では乱数生成について説明し、その他の付録ではより詳細な情報を提供します。
この文書における「しなければならない（MUST）」、「してはならない（MUST NOT）」、「必須（REQUIRED）」、「するものとする（SHALL）」、「するべきではない（SHALL NOT）」、「すべきである（SHOULD）」、「すべきでない（SHOULD NOT）」、「推奨される（RECOMMENDED）」、「してもよい（MAY）」、「任意（OPTIONAL）」というキーワードは、付録Aに記載されているとおりに解釈されます。
このセクションでは、数学的な予備知識を概説し、以下で使用する用語と表記法を定義します。
2.1 余剰演算 モジュロ演算 モジュラー演算 Modular Arithmetic
この節では、モジュラー算術について概説する。2 つの整数 x と y は、x - y が n の整数倍である場合、n を法として合同であると言われます。
2 つの整数 x と y は、それらの最大公約数が 1 のときに互いに素です。この場合、z が x を割り切り、かつ z が y を割り切るような、z > 1 となる3つ目の数は存在しない。
集合 Zq = { 0, 1, 2, ..., q-1 } は、モジュラー加算、モジュラー減算、モジュラー乗算、およびモジュラー逆演算に対して閉じています。これらの操作は次のとおりです。
Zq 内の整数 a と b の各ペアについて、a + b mod q は、a + b < q の場合には a + b に等しく、それ以外の場合には a + b - q に等しい。
Zq 内の整数 a と b の各ペアについて、a - b mod q は、a - b >= 0 の場合には a - b に等しく、それ以外の場合には a - b + q に等しい。
Zq 内の整数 a と b の各ペアについて、a * b mod q は、a * b を q で割った余りに等しい。
Zq 内の q と互いに素な整数 x の各ペアについて、q を法とする x の逆数は 1/x mod q と表され、拡張ユークリッド互除法を用いて計算できる（例えば、K1981v2 の 4.5.2 節を参照）。
これらの演算のアルゴリズムはよく知られている。例えば、K1981v2 の第 4 章を参照。
この節では、数学的群に関する用語と表記法をいくつか定義します。これらは後で必要になります。背景となる参考文献は多数あります。例えば、[D1966] を参照してください。
群(Group)とは、G の元(element)と、G の任意の2つの元を結合(combine)して G の3つ目の元を返す演算を組み合わせたものです。演算は * と表記され、その適用は G の任意の2つの元 a と b に対して a * b と表記されます。演算は結合的です。つまり、G の任意の a、b、c に対して、a * (b * c) は (a * b) * c と等しくなります。群演算を元 a に N-1 回繰り返し適用することは、G の任意の元 a と任意の正の整数 N に対して a^N と表記されます。つまり、a^2 = a * a、a^3 = a * a * a、などとなります。群演算の結合性により、a^n の計算は一義的になります。項をどのような形でグループ化しても同じ結果になります。
上記の群演算の定義では、乗法表記が用いられています。場合によっては、加法表記と呼ばれる別の表記法が用いられ、a * b は a + b と、a^N は N * a と表記されます。乗法表記では、a^N はべき乗と呼ばれ、加法表記では同等の演算はスカラー乗算と呼ばれます。この文書では、一貫性を保つために、一貫して乗法表記を使用しています。付録 E では、これら 2 つの表記法の対応関係について説明しています。
すべての群には、単位元と呼ばれる特別な元があり、これを e と表記します。G の各元 a について、e * a = a * e = a となります。慣例により、a^0 は G の任意の a について単位元と等しくなります。
すべての群元 a には、a * b = b * a = e となる一意の逆元(inverse element) b があります。a の逆元は、乗法表記では [$ a^{-1}] と表記されます。 （加法表記では、a の逆数は -a と表記されます。）
任意の正整数 X に対して、[$ a^{-X}] は [$ (a^{-1})^X] と定義されます。 この規則を用いると、べき乗は期待通り、つまり任意の整数 X と Y に対して次のように振舞います。
[$ a^{X+Y} = (a^X)*(a^Y)]
[$ (a^X)^Y = a^{(XY)} = (a^Y)^X]。
暗号アプリケーションでは、通常、有限群(finite groups)（有限個の元を持つ群）を扱います。このような群では、群の元の数は群の位数(order of the group)とも呼ばれます。ある正整数 X に対して [$ a^X = e] が成り立ち、かつ a の位数がそのような X の中で最小のものであるとき、群の元 a は有限位数を持つといいます。そのような X が存在しない場合、a は無限位数を持つ(have infinite order)といいます。有限群のすべての元は有限位数(finite order)を持ち、元の位数は常に群の位数の約数です。
群元 a が位数 R を持つ場合、任意の整数 X および Y に対して、
[$ a^X = a^{X \mod R}]、
[$ a^X = a^Y] は、X が Y mod R と合同である場合に限り、
集合 H = { [$ a, a^2, a^3, ... , a^R=e] } は G の部分群を形成し、これは a によって生成される巡回部分群(cyclic subgroup)と呼ばれ、a は H の生成元であると言われる。
一般的には、H を生成する群元は複数存在する。M が R と互いに素であるような [$ a^M] の形をとる群元は、H を生成する。任意の非負整数 M に対して、[$ a^M] は [$ g^{M modulo R}] に等しいことに注意されたい。
位数 R の元 a と、1 から R-1 まで（両端を含む）の整数 i が与えられた場合、元 [$ a^i] は [M1983] の 2.1 節で概説されている「平方乗法」（Knuth, Vol. 2, セクション4.6.3）、またはその他の方法によって計算できる。
この節では、素標数を持つ有限体に関する用語と表記法を確立する。
p が素数であるとき、加法(addition)、減法(subtraction)、乗法(multiplication)、除法(division)の演算が可能な集合 Zp は、標数 p を持つ[有限体]である。Zp の非零元 x はそれぞれ逆元 1/x を持つ。零から p-1 まで（両端を含む）の整数と、この体の元との間には一対一対応関係がある。体 Zp は、Fp または GF(p) と表記されることもある。 体の元を含む方程式は、明示的に「mod p」演算を示すことはないが、暗黙的に表されていると理解される。例えば、x、y、z が Fp に含まれ、
z = x + y
という命題は、x、y、z が集合 {0, 1, ..., p-1 } に含まれ、
z = x + y mod p
という命題と等価である。
この注釈では、標数が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）のこと、または単位元を表す特別な点(@,@)（「無限遠点」と呼ばれる）のことを指します。楕円曲線群の位数は、異なる点の数です。
楕円曲線上の二つの点 (x1,y1) と (x2,y2) は、x1=x2 かつ y1=y2 であるか、あるいは両点が無限遠点である場合には等しい。点 (x1,y1) の逆は点 (x1,-y1) である。無限遠点は自身の逆である。
楕円曲線群に関連する群演算は以下の通りである [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}{2y1})^2 - 2x1] かつ [$ y3 = \frac{(x1-x3)(3x1^2 + a)}{2*y1} - y1] 。
上記の式において、a、x1、x2、x3、y1、y2、および y3 は体 Fp の元である。したがって、実際には x3 と y3 の計算は、右辺を p を法として簡約する必要があります。群演算の擬似コードは付録 F.1 に示されています。
楕円曲線上の点を Zp 内の整数のペアとして表現することをアフィン座標表現といいます。この表現は、群の要素を伝達または格納するための外部データ表現として適していますが、無限遠点は特別なケースとして扱う必要があります。
整数のペアの中には、楕円曲線上の点として有効ではないものがあります。有効なペアは曲線方程式を満たしますが、無効なペアは満たしません。
群演算を実装する別の方法として、同次座標系 [K1987] を用いる方法があります（[KMOV1991] も参照）。この方法は、モジュラー逆元演算を必要としないため、一般的により効率的です。
楕円曲線上の点 (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]
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]
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]
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]
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]
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p
[$ Z3 = 8 * (Y1 * Z1)^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 を見つける必要があります。
他にもいくつかの座標系が記述されており、ヤコビ座標系を含むいくつかは[CC1986]に記載されています。
暗号学の文脈において、楕円曲線パラメータセットは、楕円曲線の巡回部分群と、その部分群の優先生成元から構成されます。標数が3より大きい素数位数有限体を扱う場合、楕円曲線群は以下のパラメータによって完全に指定されます。
体Fpの位数を示す素数p。 曲線方程式で使用される値a。 曲線方程式で使用される値b。 部分群の生成元g。 gによって生成される部分群の位数n。
ECCパラメータセットの例は付録Dに記載されています。
パラメータ生成については、本稿では扱いません。
各楕円曲線点は、特定のパラメータセットに関連付けられています。楕円曲線群の演算は、同じ群内の2点間でのみ定義されます。異なるグループに属する2つの要素にグループ演算を適用したり、有効な点ではない座標のペアにグループ演算を適用したりするとエラーになります。（Fp内の座標のペア（x,y）は、曲線方程式を満たす場合にのみ有効な点となります。）詳細については、セクション10.3を参照してください。
各楕円曲線群について、判別式 -16*(4a^3 + 27b^2) は p を法として非ゼロでなければならない [S1986]。これは、
[$ 4a^3 + 27b^2 \neq 0 \mod p]
であることを必要とする。
セキュリティはこれらのパラメータの選択に大きく依存します。本節では、許容される選択に関する規範的なガイダンスを示します。参考となるガイダンスについては、第10節も参照してください。
g によって生成される群の位数は、[離散対数問題] [K1987] の容易な解を排除するため、大きな素数で割り切れる必要があります。
パラメータの選択によっては、離散対数問題の解法が大幅に容易になります。これには、b = 0 かつ p = 3 (mod 4) のパラメータセットや、a = 0 かつ p = 2 (mod 3) のパラメータセットが含まれます [MOV1993]。これらのパラメータ選択は暗号用途には適さないため、使用すべきではありません。
Diffie-Hellman (DH) 鍵交換プロトコル [DH1976] は、安全でない通信路を介して通信する2者が秘密鍵に合意することを可能にします。DH は元々、大きな素数標数を持つ体の乗法群における演算を用いて定義されました。Massey [M1983] は、DH が任意の巡回群を用いて定義されるように容易に一般化できることを指摘しました。Miller [M1985] と Koblitz [K1987] は、楕円曲線群上の DH プロトコルを解析しました。ここでは、前述の文献に従って DH について説明します。
G を群とし、g をその群の生成元とし、t を G の位数とします。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を参照してください。
ECDHプロトコルの各実行は、特定のパラメータセット（セクション3.3で定義）に関連付けられており、公開鍵[$ g^j]と[$ g^k]、および共有秘密鍵[$ g^{(j*k)}]は、パラメータセットに関連付けられた巡回部分群の要素です。
ECDH秘密鍵zはZtの整数であり、tは部分群の位数です。
[M1985]の最終段落で述べられているように、指数関数を一方向性関数として使用する場合、共有秘密値[$ g^{(jk)}]のx座標は、点全体の適切な表現となります。ECDH鍵交換プロトコルでは、要素[$ g^{(jk)}]を計算した後、その値のx座標を共有秘密として使用できます。これをコンパクト出力と呼びます。
[M1985]に再び従うと、ECDHでコンパクト出力を使用する場合、典型的なアフィン座標表現のように両方の座標を送信するのではなく、楕円曲線点のx座標のみを送信すれば済みます。これをコンパクト表現と呼びます。その数学的な背景については付録Cで説明します。
ECDHは、コンパクト出力の有無にかかわらず使用できます。ECDHプロトコルの特定の実行においては、両当事者は同じ手法を使用する必要があります。ECDHは、コンパクト表現の有無にかかわらず使用できます。 ECDH プロトコルの特定の実行でコンパクト表現が使用される場合は、コンパクト出力も使用する必要があります。
[ElGamal署名]アルゴリズムは1984年に導入されました[E1984a] [E1984b] [E1985]。これは離散対数問題に基づいており、元々は大きな素数を法とする整数の乗法群に対して定義されました。有限体[$ GF(2^w)]の乗法群[AMV1990]や楕円曲線群[A1992]など、他の有限群を用いるように拡張することは容易です。
ElGamal署名は2つの要素から構成されます。ElGamal署名法の一般化は数多く存在し、第2要素の式を様々な形で変形することで得られます。[HMP1994]、[HP1994]、[NR1994]、[A1992]、[AMV1990]を参照してください。これらの一般化は、使用される数学群とは独立しており、素数を法とする乗法群、[$ GF(2^w)]の乗法群、および楕円曲線群について記述されている[HMP1994] [NR1994] [AMV1990] [A1992]。
デジタル署名アルゴリズム（[DSA]）[FIPS186]は、[ElGamal署名]の重要な変種である。
[ElGamal署名]は、任意の長さのメッセージに署名でき、存在偽造攻撃を回避できるように、衝突耐性ハッシュ関数を使用する必要があります。10.4節を参照してください。（これはすべてのElGamalバリアント[HMP1994]に当てはまります。）ハッシュ関数をh()と表記します。入力は任意長のビット文字列であり、出力は非負整数です。
H()は、出力が固定長ビット文字列であるハッシュ関数を表します。ElGamal署名方式でHを使用するには、その出力と非負整数との間のマッピングを定義します。これにより、前述の関数h()が実現されます。ビット文字列mが与えられた場合、関数h(m)は次のように計算されます。
-
H(m)が評価され、結果は固定長ビット文字列です。
-
結果のビット文字列の左端 (最初) のビットを i の最上位ビットとして扱い、右端 (最後) のビットを i の最下位ビットとして扱って、結果のビット文字列を整数 i に変換します。
小山と鶴岡は、楕円曲線エルガマルに基づく署名方式を報告した。この方式では、署名の第一要素は楕円曲線上の点のx座標をqを法として縮約したものである[KT1994]。本節では、この方式をKT-IVと呼ぶ。
このアルゴリズムは、3.3節で述べたように、素体位数pと曲線方程式パラメータaおよびbを持つ楕円曲線群を用いる。生成元をalpha、生成元位数をqとする。例外ケースのチェックは[FIPS186]に従う。
秘密鍵 z は 1 から q-1 までの整数であり、一様ランダムに生成されます。(ランダムな整数については付録 B を参照してください。) 公開鍵は群元 [$ Y = alpha^z] です。各公開鍵は、セクション 3.3 に従って特定のパラメータセットに関連付けられます。
秘密鍵 z を用いてメッセージ m の KT-IV 署名を計算するには、以下の手順を実行する。
-
1 から q-1 までのすべての整数の集合から、一様ランダムに整数 k を選択する。(ランダムな整数については付録 B を参照。)
-
[$ R = (r_x, r_y) = alpha^k] を計算する。
-
[$ s1 = r_x \mod q] を計算する。
-
h(m) + z * s1 = 0 mod q であるかどうかを確認する。もしそうであれば、k の新しい値を生成し、署名を再計算する必要がある。オプションとして、s1 = 0 であるかどうかを確認することもできる。もしそうであれば、k の新しい値を生成し、署名を再計算する必要がある。 （署名が適切に生成された場合、s1 = 0 または h(m) + z * s1 = 0 mod q となる可能性は極めて低い。）
-
[$ s2 = k/(h(m) + z*s1) \mod q] を計算する。
署名は順序付きペア (s1, s2) である。署名の両要素は非負の整数である。
メッセージ m、生成子 g、群の位数 q、公開鍵 Y、署名 (s1, s2) が与えられた場合、検証は以下のとおりです。
-
0 < s1 < q かつ 0 < s2 < q であることを確認します。いずれかの条件に違反する場合、署名は拒否されます。
-
非負整数 u1 および u2 を計算します。ここで、
u1 = h(m) * s2 mod q、および
u2 = s1 * s2 mod q です。
-
楕円曲線上の点 R' = alpha^u1 * Y^u2 を計算します。
-
R' mod q の x 座標が s1 と等しい場合、署名とメッセージは検証に合格します。そうでない場合、検証は不合格となります。
Horster、Michels、およびPetersenは、多くの異なる[ElGamal署名]方式を分類し、それらの等価性を実証し、あるタイプの署名を別のタイプの署名に変換する方法を示しました[HMP1994]。彼らの用語では、5.3節および[KT1994]の署名方式はタイプIV方式であるため、KT-IVと表記されます。
タイプIのKT署名方式には、デジタル署名アルゴリズムと同じ方法で計算される第2の要素があります。本節では、KT-Iと呼ばれるこの方式について説明します。
鍵ペアと鍵ペア生成は、セクション5.3.1と全く同じです。
秘密鍵zを用いてメッセージmのKT-I署名を計算するには、以下の手順に従います。
-
1からq-1までのすべての整数の集合から、一様ランダムに整数kを選択します。(ランダムな整数については、付録Bを参照してください。)
-
[$ R = (r_x, r_y) = alpha^k]を計算します。
-
[$ s1 = r_x \mod q]を計算します。
-
[$ s2 = (h(m) + z*s1)/k \mod q]を計算します。
-
オプションとして、s1 = 0 または s2 = 0 かどうかをチェックしてもよい（MAY）。s1 = 0 または s2 = 0 のいずれかの場合、k の新しい値を生成し、署名を再計算する必要がある（SHOULD）。（署名が適切に生成された場合、s1 = 0 または s2 = 0 となる可能性は極めて低い。）
署名は順序付きペア（s1, s2）である。署名のどちらの要素も非負の整数である。
メッセージ m、公開鍵 Y、署名 (s1, s2) が与えられた場合、検証は以下の手順で行われます。
-
0 < s1 < q かつ 0 < s2 < q であることを確認します。いずれかの条件に違反する場合、署名は拒否されます。
-
s2_inv = 1/s2 mod q を計算します。
-
非負整数 u1 と u2 を計算します。ただし、
u1 = h(m) * s2_inv mod q かつ
u2 = s1 * s2_inv mod q です。
-
楕円曲線上の点 [$ R' = alpha^{u1} * Y^{u2}] を計算します。
-
R' mod q の x 座標が s1 と等しい場合、署名とメッセージは検証に合格します。そうでない場合、検証は不合格となります。
メッセージmと公開鍵Yに対するKT-IV署名は、同じメッセージと公開鍵Yに対するKT-I署名に簡単に変換できます。(s1, s2)がメッセージmに対するKT-IV署名である場合、(s1, 1/s2 mod q)は同じメッセージに対するKT-I署名です（HMP1994）。
この変換操作は公開情報のみを使用し、変換前のKT-IV署名の作成者、変換後のKT-I署名の検証者、またはその他の任意のエンティティによって実行できます。
実装は、KT-I署名を計算するためにこの方法を使用してもよい（MAY）。
この節は本仕様の規範的なものではなく、背景情報としてのみ提供されています。
[HMP1994] は、ElGamal署名の多くの一般化を提示しています。
同文献の式 (5) は、一般的な署名式を示しています。
A = x_A * B + k * C (mod q)
ここで、x_A は秘密鍵、k は秘密値であり、A、B、C は [HMP1994] の表 1 に示されているように、式の型によって決定されます。[DSA] [FIPS186] は、KT-I と同様に EG-I.1 署名方式であり、A = m、B = -r、C = s です。 （ここでは、[HMP1994]の表記法を用い、第一署名要素をr、第二署名要素をsとする。KT-IおよびKT-IVでは、これらの要素はそれぞれs1およびs2と表記される。秘密鍵x_Aは秘密鍵zに対応する。）署名方程式は
m = -r * z + s * k (mod q)である。
[KT1994]および5.3節の署名法は、EG-IV.1法であり、A = m * s、B = -r * s、C = 1である。署名方程式は
m * s = -r * s * z + k (mod q)である。
[HMP1994]の表1に記載されている関数fおよびgは、単に乗算であり、「第五の一般化」の見出しで説明されている。
上記の式では、メッセージmをビット列から整数へ暗黙的に変換することを利用して計算している。これらの式にはハッシュ関数は示されていないが、10.4節で述べたように、存在偽造攻撃を防ぐために、署名前にメッセージにハッシュ関数を適用する必要がある。
NybergとRueppel [NR1994]は、様々な[ElGamal署名]方式を研究し、「強い等価性」を以下のように定義した。
2つの署名方式は、秘密鍵を知らなくても、最初の方式の署名を2番目の方式の署名に効率的に変換でき、またその逆も可能である場合、強い等価性を持つと呼ばれる。
KT-I署名とKT-IV署名は明らかに強い等価性を持つ。
s2=0の有効な署名は、z = -h(m) / s1 mod qとなるため、秘密鍵を漏洩する。この例外的なケースとs1=0の場合のチェックについては、[FIPS186]に従う。s2=0のチェックはRivest [R1992]によって提案され、[BS1992]で議論されている。
[KT1994]では、楕円曲線点R = (r_x, r_y)のx座標r_xから署名要素s1を計算する際に、「qを超えない正の整数q'」が用いられています。q'の値は、署名検証において、算出された楕円曲線点のx座標とs1の値を比較する際にも用いられます。本稿では、簡略化のためq' = qと表記します。
このセクションでは、公開鍵暗号 [R1993] の確立された規約に従い、整数とオクテット文字列間の変換方法を規定します。この方法により、整数を伝送または保存に適したオクテット文字列として表現することができます。この方法は、本ノートで定義されている楕円曲線の点または楕円曲線座標を表現する際に使用する必要があります。
オクテット文字列 S は、以下のように整数 x に変換される。 S1, ..., Sk を S の先頭から末尾までのオクテットとする。整数 x は、次の式を満たす。
[$ x = \sum_{i=1}^k 2^{8(k-i)}Si] k x = SUM 2^(8(k-i)) Si i = 1
言い換えれば、S の最初のオクテットは整数の中で最も重要度が高く、最後のオクテットは最も重要度が低い。
注：整数 x は [$ 0 <= x < 2^{(8*k)}] を満たす。
整数 x は、以下のように長さ k のオクテット文字列 S に変換される。文字列 S は、以下の式を満たすものとする。
[$ y = \sum_{i=1}^k 2^{8(k-i)} Si] k y = SUM 2^(8(k-i)) Si . i = 1
ここで、S1, ..., Sk は、S の先頭から末尾までのオクテットである。
言い換えれば、S の最初のオクテットは整数の中で最も重要度が高く、最後のオクテットは最も重要度が低い。
このノートに記載されているアルゴリズムは、他のECC仕様との相互運用に使用できます。このセクションでは、各アルゴリズムの詳細について説明します。
セクション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 ステップを省略し、共有秘密値を直接出力する必要があります）。
デジタル署名アルゴリズム（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検証アルゴリズムを用いて検証できます。