SEC 1
楕円曲線の元の仕様
適当に
効率的な暗号化の標準
SEC 1: 楕円曲線暗号
Certicom Research
連絡先: Daniel R. L. Brown (dbrown@certicom.com)
2009年5月21日
Version 2.0
1 はじめに
このセクションでは、この規格の概要、その使用、目的、および開発について説明します。
1.1 概要
この文書は、楕円曲線暗号（ECC）に基づく公開鍵暗号方式を規定する。具体的には、以下の内容を規定する。
署名方式
暗号化および鍵転送方式
鍵共有方式
また、これらの方式を構築するために用いられる暗号プリミティブと、これらの方式を識別するためのASN.1構文についても説明する。
これらの方式は、コンピュータシステムおよび通信システムにおける一般的な応用を目的としている。
1.2 目的
この文書の目的は以下の3つです。
第一に、ECCに基づく効率的で確立され、広く理解されている公開鍵暗号方式を完全に規定することにより、ECCの導入を促進すること。
第二に、ANS X9.62 X9.62a、WAP WTLS WTLS、ANS X9.63 X9.63、IEEE 1363 1363、およびNIST SP 800-56 800-56A勧告などの標準をプロファイリングすることにより、ECCの相互運用可能な実装の導入を促進すること。ただし、これらの標準で認められているオプションを制限することで、相互運用性の可能性を高め、可能な限り多くの標準への適合を確保すること。 第三に、ベースライン技術を明確かつ完全に公開的に規定することにより、暗号学者によるECCの継続的な詳細分析を支援すること。
2 数学的基礎
本節では、楕円曲線暗号に必要な数学的基礎の概要を示します。
本文書で説明する各公開鍵暗号方式の使用には、有限体上の楕円曲線上の算術演算が含まれます。本節では、これらの算術演算を理解し実装するために必要な数学的概念を紹介します。
2.1節では有限体について、2.2節では有限体上の楕円曲線について、2.3節では関連するデータ型とデータ型間の変換に使用される規則について説明します。
実装に関する議論、セキュリティに関する議論、参考文献など、本節の内容に関する解説については、付録Bを参照してください。
抽象的に、有限体は、体元(field elements)と呼ばれるオブジェクトの有限集合(finite set)と、体元のペアに対して実行できる2つの演算（加算と乗算）の記述から構成されます。これらの演算は、特定の性質を持たなければなりません。
q 個の体元を含む有限体が存在する場合と、q が素数のべき乗である場合とで、さらに、そのような q に対してちょうど1つの有限体が存在することがわかります。q 個の体元を含む有限体は $ \mathbb{F}_q と表記されます。
ここでは、2種類の有限体 $ \mathbb{F}_q のみを使用します。1つは、奇数の素数である q = p の有限体 $ \mathbb{F}_p で、素有限体(prime finite fields)と呼ばれます。もう1つは、任意の m ≥ 1 に対して $ q = 2^m の有限体 $ \mathbb{F}_{2^m} で、標数 2 の有限体(characteristic 2 finite fields)と呼ばれます。
ECC に基づく暗号方式を正確に規定するためには、これらの体を具体的に記述する必要があります。セクション 2.1.1 では素有限体について説明し、セクション 2.1.2 では標数 2 の有限体について説明します。
2.1.1 有限体 $ \mathbb{F}_p
有限体 $ \mathbb{F}_p は p 個の元を含む素有限体です。奇数の素数 p に対しては素有限体 $ \mathbb{F}_p は 1 つしか存在しませんが、$ \mathbb{F}_p の元を表す方法は数多くあります。
ここで、$ \mathbb{F}_p の元は整数の集合で表されます。
$ \{0, 1, ... , p - 1\}
加算と乗算は以下のように定義されます。
加算：a, b ∈ $ \mathbb{F}_p ならば、$ \mathbb{F}_p において a + b = r が成り立ちます。ここで、$ r ∈ [0, p − 1] は整数 a + b を p で割ったときの余りです。これは p を法とする加算と呼ばれ、a + b ≡ r (mod p) と書きます。
乗算：a, b ∈ $ \mathbb{F}_p ならば、$ \mathbb{F}_p において ab = s が成り立ちます。ここで、$ s \in [ 0, p − 1] は整数 ab を p で割ったときの余りです。これは p を法とする乗算と呼ばれ、ab ≡ s (mod p) と書きます。
$ \mathbb{F}_pにおける加算と乗算は、通常の整数演算の標準アルゴリズムを用いて効率的に計算できます。 $ \mathbb{F}_pのこの表現において、加法単位元または零元は整数 0 であり、乗法単位元は整数 1 です。
整数の減算と除算を定義するのと同様に、体元の減算と除算を定義するのも簡単です。そのためには、体元の加法逆元（または負の逆元）と乗法逆元を記述する必要があります。
• 加法逆元：$ a \in \mathbb{F}_p の場合、$ \mathbb{F}_p における a の加法逆元 (-a) は、方程式 a + x ≡ 0 (mod p) の唯一の解です。
• 乗法逆元：$ a \in \mathbb{F}_p の場合、a 6 = 0 の場合、$ \mathbb{F}_p における a の乗法逆元 a-1 は、方程式 ax ≡ 1 (mod p) の唯一の解です。
$ \mathbb{F}_p における加法逆元と乗法逆元は効率的に計算できます。乗法逆元は拡張ユークリッド互除法を用いて計算できます。除算と減算は、加法逆数と乗法逆数によって定義されます。a−b mod p は a+(−b) mod p であり、a/b mod p は a(b−1) mod p です。
ここで、使用される素数有限体 $ \mathbb{F}_p は、次の式を満たす必要があります。
$ \lceil \log_2p \rceil \in \{192, 224, 256, 384, 521\}
この制約は相互運用性を促進するために設計されており、実装者は、p がワードサイズに整合しているため計算と通信の点で効率的であり、一般的に要求されるすべてのセキュリティレベルを提供できる実装を展開できます。$ \lceil \log_2 p\rceil = 512 ではなく $ \lceil \log_2 p\rceil = 521 を含めることは、この文書を他の標準化活動、特に米国政府が推奨する楕円曲線ドメインパラメータ 186-2 と整合させるために選択された例外的な方法です。 2.1.2 有限体 $ \mathbb{F}_{2^m}
有限体 $ \mathbb{F}_{2^m}は、$ 2^m 個の元を含む標数 2 の有限体である。m ≥ 1 の 2 のべき乗 $ 2^m に対しては、標数 2 の有限体 $ \mathbb{F}_{2^m} は 1 つしか存在しないが、$ \mathbb{F}_{2^m} の元を表す方法は多数存在する。
ここで、$ \mathbb{F}_{2^m} の元は、次数 m − 1 以下の 2 元多項式の集合で表される。
$ \{a_{m−1}x^{m−1} + a_{m−2}x^{m−2} + · · · + a_1x + a_0 : a_i \in \{0, 1\}\}
加法と乗法は、次式のように、既約な m 次 2 元多項式 $ f (x) （この多項式は縮約多項式と呼ばれる）によって定義される。
加算: $ a = a_{m−1}x^{m−1} + · · · + a_0, b = b_{m−1}x^{m−1} + · · · + b_0 \in \mathbb{F}_{2^m} とすれば、 $ \mathbb{F}_{2^m} において a + b = r が成立する。ただし、 $ r = r_{m−1}x^{m−1} + · · · + r_0 であり、$ r_i ≡ a_i + b_i (\mod 2) とする。
乗算: $ a = a_{m−1}x^{m−1} + · · · + a_0, b = b_{m−1}x^{m−1} + · · · + b_0 \in \mathbb{F}_{2^m} とすれば、 $ \mathbb{F}_{2^m}において ab = s が成立する。ただし、 $ s = s_{m−1}x^{m−1} + · · · + s_0 は、すべての係数演算を 2 を法として実行し、多項式 ab を$ f (x) で割ったときの剰余である。
$ \mathbb{F}_{2^m}における加算と乗算は、通常の整数演算および多項式演算の標準アルゴリズムを使用して効率的に計算できる。 $ \mathbb{F}_{2^m} のこの表現において、加法単位元または零元は多項式 0 であり、乗法単位元は多項式 1 です。
ここでも、体元の減算と除算を定義することが便利です。そのためには、体元の加法逆元（または負の逆元）と乗法逆元を記述する必要があります。
加法逆元： $ a \in \mathbb{F}_{2^m} の場合、 $ \mathbb{F}_{2^m} における a の加法逆元 (-a) は、 $ \mathbb{F}_{2^m} における方程式 a + x = 0 の唯一の解です。すべての $ a \in \mathbb{F}_{2^m} について、-a = a であることに注意してください。
乗法逆元： $ a \in \mathbb{F}_{2^m}の場合、 $ a \ne 0 の場合、 $ \mathbb{F}_{2^m} における a の乗法逆元 $ a^{-1} は、 $ \mathbb{F}_{2^m} における方程式 ax = 1 の唯一の解です。
$ \mathbb{F}_{2^m} の加法逆元と乗法逆元は効率的に計算できます。乗法逆数は、拡張ユークリッド互除法の多項式版を用いて計算できます。
除算と減算は、加法逆数と乗法逆数によって定義されます。$ \mathbb{F}_{2^m} の a − b は $ \mathbb{F}_{2^m} の a + (−b) であり、$ \mathbb{F}_{2^m} の a/b は $ \mathbb{F}_{2^m} の $ a(b^{−1}) です。
ここで、使用される特性2の有限体 $ \mathbb{F}_{2^m} は、以下の式を満たす必要があります。
$ m \in \{163,233,239,283,409,571\}
$ \mathbb{F}_{2^m}での加算と乗算は、表1のm次の既約2進多項式のいずれかを使用して実行する必要があります。これまでと同様に、この制限は相互運用性を促進し、実装者が共通のセキュリティ要件を満たす効率的な実装を展開できるように設計されています。
table:表1: F_2^mの表現
Field Reduction Polynomial(s)
体 縮小多項式
F_2^163 f(x) = x^163 + x^7 + x^6 + x^3 + 1
F_2^233 f(x) = x^233 + x^74 + 1
F_2^239 f(x) = x^239 + x^36 + 1 または x^239 + x^158 + 1
F_2^283 f(x) = x^283 + x^12 + x^7 + x^5 + 1
F_2^409 f(x) = x^409 + x^87 + 1
F_2^571 f(x) = x^571 + x^10 + x^5 + x^2 + 1
許容可能な m を選択する際に用いられた規則は、集合
{160, 224, 256, 384, 512, 1024}
内の各整数区間において、そのような m が存在する場合、その区間において、$ \mathbb{F}_{2^m} 上の素数の 2 倍または 4 倍の位数を持つコブリッツ曲線が存在するという性質を持つ最小の素数 m を選択する、そうでなければ、単にその区間において最小の素数 m を選択するというものである。(コブリッツ曲線とは、a, b ∈ {0, 1} を満たす $ \mathbb{F}_{2^m} 上の楕円曲線である。第 2.2 節を参照。) m = 239 は、既に実務で広く使用されているため、例外的に採用されたものである。m = 277 ではなく m = 283 を採用したのは、この文書を他の標準化活動、特に米国政府が推奨する楕円曲線の領域パラメータ 186-2 と整合させるために、例外的に採用されたものである。合成 m の使用を避けたのは、本仕様を他の標準化活動と整合させ、また m が合成である $ \mathbb{F}_{2^m} 上に定義された楕円曲線のセキュリティについて一部の専門家が表明した懸念に対処するためです (例えば、GS99、JMS01、GHS02、Hes05、MT06 を参照)。 許容可能な約分多項式を選択する際に使用される規則は次のとおりです。
$ f (x) = x^m + x^k + 1 with $ m > k ≥ 1
という m 次二項式が存在する場合は、k が可能な限り小さいこの三項式を使用します。そうでない場合は、
f (x) = xm + xk3 + xk2 + xk1 + 1 (m > k3 > k2 > k1 ≥ 1) という m 次二項式を使用します。
$ f (x) = x^m + x^{k_3} + x^{k_2} + x^{k_1} + 1 with $ m > k_3 > k_2 > k_1 ≥ 1
という条件で、(1) $ k_3 は可能な限り小さい、(2) $ k_3 が与えられた場合の $ k_2 は可能な限り小さい、(3) $ k_3 と $ k_2 が与えられた場合の $ k_1 は可能な限り小さい。これらの多項式は、体演算の効率的な計算を可能にします。m = 239 の2番目の縮約多項式は、広く使用されているため、例外的に選択されました。
2.2 楕円曲線
$ \mathbb{F}_q 上の楕円曲線は、$ \mathbb{F}_q の方程式の解によって定義されます。$ \mathbb{F}_q 上の楕円曲線を定義する方程式の形は、体（$ \mathbb{F}_q が素数有限体か、または標数 2 の有限体か）によって異なります。
2.2.1 節では素数有限体上の楕円曲線について、2.2.2 節では標数 2 の有限体上の楕円曲線について説明します。
2.2.1 $ \mathbb{F}_p 上の楕円曲線
$ \mathbb{F}_p を素有限体とし、$ p を奇素数とする。また、$ a, b \in \mathbb{F}_p は $ 4a^3 +27b^2 \not\equiv 0 (mod p) を満たすものとする。このとき、パラメータ $ a, b \in \mathbb{F}_p によって定義される $ \mathbb{F}_p 上の楕円曲線 $ E(\mathbb{F}_p)は、方程式 $ P = (x, y) の $ x, y \in \mathbb{F}p に対する解の集合、すなわち点 $ P = (x, y) の集合から構成される。
$ y^2 ≡ x^3 + ax + b (\mod p)
そして、無限遠点と呼ばれる追加の点 $ O を伴う。方程式 $ y^2 \equiv x^3 + ax+b (\mod p) は、$ E(\mathbb{F}_p) の定義方程式と呼ばれる。与えられた点 $ P = (x_P , y_P ) に対して、$ x_P は P の x 座標、$ y_P は P の y 座標と呼ばれる。
$ E(\mathbb{F}_p) 上の点の数は $ \#E(\mathbb{F}_p)で表される。ハッセの定理は次のように規定する:
$ p + 1 − 2\sqrt{p} \le \#E(\mathbb{F}_p) \le p + 1 + 2\sqrt{p}
E 上の点を加算する加法則を定義することが可能である。加法則は以下のように規定される:
1. 無限遠点をそれ自身に加える規則:
$ \mathcal{O} + \mathcal{O} = \mathcal{O}
2. 無限遠点を他の任意の点に加える規則:
$ (x,y) + \mathcal{O} = \mathcal{O} + (x, y) = (x, y) for all $ (x,y) \in E(\mathbb{F}_p)
3. 同じx座標を持つ2点を、異なる点、またはy座標が0の点と加算する規則：
$ (x,y) + (x, -y) = \mathcal{O} for all $ (x, y) \in E(\mathbb{F}_p)
-- つまり、点(x, y)の負の数は、-(x, y) = (x, -y)です。
4. 異なるx座標を持つ2点を加算する例: $ (x1, y1) \in E(\mathbb{F}_p)と $ (x2, y2) \in E(\mathbb{F}_p) を、$ x1 \ne x2 となる2点とします。すると、$ (x1, y1) + (x2, y2) = (x3, y3) となります。ここで、
$ x_3 \equiv \lambda^2-x_1-x_2(\mod p), y_3 \equiv \lambda(x_1 - x_3)-y_1 (\mod p), および $ \lambda\equiv \frac{y_2-y_1}{x_2-x_1} (\mod p)
5. 点をそれ自身に加える（点を2倍にする）規則：$ (x_1, y_1) \in E(\mathbb{F}_p) を $ y_1 \ne 0 となる点とします。
すると、$ (x_1, y_1) + (x_1, y_1) = (x_3, y_3) となります。ここで、
$ x_3 \equiv \lambda^2-2x_1(\mod p), y_3 \equiv \lambda(x_1-x_3)-y_1(\mod p), および $ \lambda \equiv \frac{3x_1^2+a}{2y_1}(\mod p)
$ E(\mathbb{F}_p) 上の点の集合は、この加法規則のもとで群を形成します。さらに、この群はアーベル群です。つまり、すべての点 $ P_1, P_2 \in E(\mathbb{F}_p) について、$ P_1 + P_2 = P_2 + P_1 が成り立ちます。加法規則は常に、単純な体算術を用いて効率的に計算できることに注目してください。
ECC に基づく暗号方式は、楕円曲線点のスカラー乗算に依存しています。整数 $ k と点 $ P \in E(\mathbb{F}_p) が与えられたとき、スカラー乗算は $ P をそれ自身に $ k 回加算する処理です。このスカラー乗算の結果は $ kP と表されます。楕円曲線点のスカラー乗算は、加法規則と double-and-add アルゴリズムまたはその派生アルゴリズムのいずれかを用いることで効率的に計算できます。
2.2.2 $ \mathbb{F}_{2^m}上の楕円曲線
$ \mathbb{F}_{2^m}を標数2の有限体とし、$ a, b \in \mathbb{F}_{2^m}が$ \mathbb{F}_{2^m}において$ b \ne 0 を満たすものとする。すると、パラメータ$ a, b \in \mathbb{F}_{2^m} によって定義される$ \mathbb{F}_{2^m}上の（非特異）楕円曲線$ E(\mathbb{F}_{2^m}) は、方程式$ x, y \in \mathbb{F}_{2^m}に対する解または点$ P = (x, y) の集合から構成される:
$ y^2 + xy = x^3 + ax^2 + b in $ \mathbb{F}_{2^m}
と、無限遠点と呼ばれる追加の点$ \mathcal{O}から構成される。(ここで注目する$ \mathbb{F}_{2^m}上の楕円曲線は、非特異楕円曲線のみである。)
$ E(\mathbb{F}_{2^m}) 上の点の数は $ \#E(\mathbb{F}_{2^m}) と表される。ハッセの定理は次式で表される:
$ 2^m + 1 − 2\sqrt{2^m} \le \#E(\mathbb{F}_{2^m}) \le 2^m + 1 + 2\sqrt{2^m}.
2.2.1 節と同様に，$ E上の点を加算する加法規則を定義することも可能である。加法規則は以下のように規定される:
1. 無限遠点をそれ自身に加算する規則:
$ \mathcal{O} + \mathcal{O} = \mathcal{O}.
2. 無限遠点を他の任意の点に加算する規則:
すべての$ (x, y) \in E(\mathbb{F}_p) に対して$ (x, y) + \mathcal{O} = \mathcal{O} + (x, y) = (x, y)
3. 2点のx座標が異なっているか、x座標が0である場合、同じx座標を持つ2点を加算する規則：
$ (x, y) + (x, x + y) = \mathcal{O}（すべての $ (x, y) \in E(\mathbb{F}p)に対して）
— つまり、点$ (x, y)の負数は$ -(x, y) = (x, x + y)です。
4. 2点のx座標が異なる場合の規則：$ (x_1, y_1) \in E(\mathbb{F}_{2^m} )と$ (x_2, y_2) \in E(\mathbb{F}_{2^m} )を、$ x_1 \not= x_2となる2点とします。すると、$ (x_1, y_1) + (x_2, y_2) = (x_3, y_3) となる。
$ x_3 = λ^2 + λ + x_1 + x_2 + a ($ \mathbb{F}_{2^m}において)、$ y_3 = λ(x_1 + x_3) + x_3 + y_1 ($ \mathbb{F}_{2^m}において)、 および $ λ = \frac{y_1 + y_2}{x_1+x_2} ($ \mathbb{F}_{2^m}において)
5. 点をそれ自身に加える（点を2倍にする）規則：$ (x_1, y_1) \in E(\mathbb{F}_{2^m} ) を$ x_1 \not= 0となる点とする。
すると、$ (x_1, y_1) + (x_1, y_1) = (x_3, y_3) となる。
$ x_3 = λ^2 + λ + a ($ \mathbb{F}_{2^m}において)、$ y_3 = x_1^2+ (λ + 1)x_3 ($ \mathbb{F}_{2^m}において)、$ λ = x_1 + \frac{y_1}{x_1}($ \mathbb{F}_{2^m}において)。
$ E(\mathbb{F}_{2^m} )上の点の集合は、この加法則の下でアーベル群を形成する。加法則は常に単純な体算術を用いて効率的に計算できることに注意されたい。
ECC に基づく暗号方式は、楕円曲線上の点のスカラー乗算に依存している。前述のように、整数$ k と点$ P \in E(\mathbb{F}_{2^m})が与えられたとき、スカラー乗算は$ Pをそれ自身に$ k回加算する処理である。このスカラー乗算の結果は$ kP と表記される。
2.3 データ型と変換
このドキュメントで規定されているスキームには、複数の異なるデータ型を用いた演算が含まれます。このセクションでは、様々なデータ型を列挙し、あるデータ型を別のデータ型に変換する方法について説明します。
このドキュメントでは、5つのデータ型が用いられています。楕円曲線演算に関連する3つの型（整数(integers)、体元(field elements)、楕円曲線点(elliptic curve points)）に加え、情報の通信と保存に使用されるオクテット列、および一部のプリミティブで使用されるビット列です。
多くの場合、あるデータ型を別のデータ型に変換する必要が生じます。例えば、楕円曲線上の点をオクテット列として表現する場合などです。このセクションの残りの部分では、必要な変換をどのように行うべきかについて説明します。
図1は、必要な変換とその記述箇所を示しています。
図1: データ型間の変換 (略)
2.3.1 ビット列からオクテット列への変換
ビット列は、このセクションで説明するようにオクテット列に変換する必要があります。非公式な考え方としては、ビット列の左側に0を詰めて長さを8の倍数にし、その結果をオクテットに分割します。正式な変換ルーチンは以下のように規定されます。
入力: blenビットのビット列 B
出力: 長さ$ mlen = \lceil blen/8\rceilオクテットのオクテット列 M
処理: ビット列 $ B = B_0B_1...B_{blen-1} からオクテット列$ M = M_0M_1...M_{mlen-1} に変換します
1. For 0 < i <= mlen - 1,
$ M_i = B_{blen - 8 - 8(mlen-1-i)}B_{blen-7-8(mlen-1-i)}...B_{blen-1-8(mlen-1-i)}
2. $ M_0の左端の$ 8(mlen) − blenビットを0にし、右端の$ 8 − (8(mlen) − blen)ビットを$ B_0B_1 . . . B_{8−8(mlen)+blen−1}に設定する。
3. 出力 $ M
2.3.2 オクテット列からビット列への変換
オクテット列は、このセクションで説明するようにビット列に変換する必要があります。非公式には、オクテット列をビット列として扱うという単純な考え方です。公式には、変換ルーチンは以下のように規定されます。
入力: 長さ mlen オクテットのオクテット列 M。
出力: 長さ blen = 8(mlen) ビットのビット列 B。
処理: オクテット列 $ M = M_0M_1 . . . M_{mlen−1} を、以下のようにビット文字列 $ B = B_0B_1 . . . B_{blen−1} に変換します。
1. 0 ≤ i ≤ mlen − 1 に対して、次のように設定します。
$ B_{8i}B_{8i+1} ... B_{8i+7} = M_i
2. 出力 $ B
2.3.3 楕円曲線点からオクテット列への変換
楕円曲線上の点は、この節で説明するようにオクテット列に変換する必要があります。非公式には、点圧縮が使用されている場合、圧縮されたy座標がオクテット文字列の左端オクテットに配置され、点圧縮がオンであることを示す情報も含まれ、x座標がオクテット列の残りの部分に配置されます。点圧縮がオフの場合、左端オクテットは点圧縮がオフであることを示し、オクテット列の残りの部分にはx座標とy座標が含まれます。正式な変換ルーチンは次のように規定されます。
設定: 点を点圧縮を使用して表現するかどうかを決定します。
入力: 体元 a, b によって定義される $ \mathbb{F}_q 上の楕円曲線上の点 $ P。
出力: 長さ mlen オクテットのオクテット列 M。ただし、$ P = \mathcal{O} の場合は mlen = 1、$ P \ne \mathcal{O} かつ点圧縮が使用されている場合は $ mlen = \lceil (\log_2 q)/8\rceil+1、$ P \ne \mathcal{O} かつ点圧縮が使用されていない場合は $ mlen = 2\lceil(\log_2 q)/8\rceil + 1 です。
処理: 次のように、P をオクテット文字列 $ M = M_0M_1...M_{mlen−1} に変換します。
1. $ P = \mathcal{O} の場合は、$ M = 00_{16} を出力します。
2. $ P = (x_P , y_P ) \ne \mathcal{O} かつ点圧縮が使用されている場合は、次のように処理します。
2.1. セクション 2.3.5 で指定された変換ルーチンを使用して、体元 $ x_P を長さ $ \lceil (\log_2 q)/8\rceil オクテットのオクテット列 $ X に変換します。
2.2. $ y_P から 1 ビット $ \tilde{y}P を次のように導出します（これにより、y 座標を 1 ビットで簡潔に表現できます）。
2.2.1. $ q = p が奇数の素数の場合、$ \tilde{y}P = yP (\mod 2) とします。
2.2.2. $ q = 2^m の場合、$ x_P = 0 であれば $ \tilde{y}_P = 0 とします。それ以外の場合は、$ z = z_{m−1}x^{m−1} + ... + z_1x + z_0 を計算します。$ z = y_P x_P^{−1} となり、$ \tilde{y}_P = z_0 とします。
2.3. $ \tilde{y}_P = 0の場合は単一オクテット$ Yに値$ 02_{16}を割り当て、$ \tilde{y}_P = 1の場合は値$ 03_{16}を割り当てます。
2.4. 出力 $ M = Y || X
3. $ P = (x_P , y_P ) \ne \mathcal{O}かつポイント圧縮が使用されていない場合は、次の手順に従います。
3.1. セクション 2.3.5 で指定された変換ルーチンを使用して、体元 $ x_P を長さ $ \lceil (\log_2 q)/8\rceil オクテットのオクテット列 $ X に変換します。
3.2. セクション 2.3.5 で指定された変換ルーチンを使用して、体元 $ y_P を長さ $ \lceil (\log_2 q)/8\rceil オクテットのオクテット列 $ Y に変換します。
3.3. 出力 $ M = 04_{16} || X || Y
2.3.4 オクテット列から楕円曲線点への変換
オクテット列は、このセクションで説明するように楕円曲線の点に変換する必要があります。非公式な考え方としては、オクテット列が圧縮された点を表す場合、圧縮されたy座標を左端のオクテットから復元し、x座標をオクテット列の残りの部分から復元し、その後、点の圧縮プロセスを逆に実行します。そうでない場合は、オクテット列の左端のオクテットを削除し、残りのオクテット列の左半分からx座標を復元し、残りのオクテット列の右半分からy座標を復元します。形式的には、変換ルーチンは以下のように規定される。
入力: 体元 a, b と、単一のオクテット $ 00_{16}、長さ $ mlen = \lceil (\log_2 q)/8\rceil+1 のオクテット文字列、または長さ $ mlen = 2\lceil (\log_2 q)/8\rceil+1のオクテット列のいずれかであるオクテット列 $ M で定義される$ \mathbb{F}_q 上の楕円曲線。
出力: 楕円曲線点 $ P 、または「無効」("invalid")。
処理: 以下のように $ M を楕円曲線点 $ P に変換する。
1. $ M = 00_{16} のとき出力 $ P = \mathcal{O}
2. $ Mの長さが $ \lceil (\log_2 q)/8\rceil+1オクテットの場合、次のように処理します。
2.1. $ M = Y || X を、1 オクテット $ Y とそれに続く $ \lceil (\log_2 q)/8\rceil オクテット $ X として解析します。
2.2. セクション 2.3.6 で指定された変換ルーチンを使用して、$ X を $ \mathbb{F}_q の体元 $ x_P に変換します。ルーチンが "invalid" を出力した場合は、"invalid" を出力して停止します。
2.3. $ Y = 02_{16} の場合は $ \tilde{y}P = 0に設定し、$ Y = 03_{16} の場合は $ \tilde{y}P = 1に設定します。それ以外の場合は "invalid" を出力して停止します。
2.4. $ x_P と $ \tilde{y}_P から楕円曲線点 $ P = (x_P , y_P) を導出します。ここで、
2.4.1. q = p が奇数の素数である場合、体元 $ \alpha \equiv x_P^3+ax_P+b(\mod p) を計算し、p を法とする $ \alpha の平方根 $ \beta を計算する。$ p を法とする $ \alpha の平方根がない場合は「invalid」を出力して終了する。それ以外の場合は、 $ \beta \equiv \tilde{y}_P (\mod 2) の場合は $ y_P = \beta とし、$ \beta \not\equiv \tilde{y}P (\mod 2) の場合は $ y_P = p − \beta とする。
2.4.2. $ q = 2^m かつ $ x_P = 0 の場合、$ \mathbb{F}_{2^m} において $ \tilde{y}_P = b^{2^{m-1}} を出力する。
2.4.3. $ q = 2^m かつ$ x_P \ne 0 の場合、$ \mathbb{F}_{2^m} の体元$ \beta = x_P + a + bx_P^{-2} を計算し、$ \mathbb{F}_{2^m} で$ z^2 + z = \beta となるような元 $ z = z_{m−1}x^{m−1} + · · · + z_1x + z_0 を求めます。そのようなzが存在しない場合は「invalid」を出力して停止し、そうでない場合は $ z_0 = \tilde{y}_P の場合は$ \mathbb{F}_{2^m} で$ y_P = x_P z に設定し、$ z_0 \ne \tilde{y}_P の場合は$ \mathbb{F}_{2^m} で $ y_P = x_P (z + 1) に設定します。
2.5. 出力 $ P = (x_P, y_P)
3. $ M の長さが $ 2\lceil (\log_2 q)/8\rceil+1 オクテットの場合、次の手順に従います。
3.1. $ M = W || X || Y を、1つのオクテット $ W とそれに続く $ \lceil (\log_2 q)/8\rceil オクテット $ X 、それに続く $ \lceil (\log_2 q)/8\rceil オクテット $ Y として解析します。
3.2. $ W = 04_{16} であることを確認します。$ W \ne 04_{16} の場合、「invalid」を出力して停止します。
3.3. 2.3.6節で指定された変換ルーチンを用いて、$ X を$ \mathbb{F}_q の体元$ x_P に変換する。ルーチンが「invalid」を出力した場合は「invalid」を出力し、停止する。
3.4. 2.3.6節で指定された変換ルーチンを用いて、$ Y を$ \mathbb{F}_q の体元$ y_P に変換する。ルーチンが「invalid」を出力した場合は「invalid」を出力し、停止する。
3.5. $ P = (x_P , y_P ) が楕円曲線の定義式を満たしていることを確認します。
3.6. 出力 $ P = (x_P, y_P)
2.3.5 フィールド要素からオクテット列への変換
体元は，この節で説明するようにオクテット文字列に変換する必要がある．非公式な考え方としては，体が $ \mathbb{F}_p の場合は整数をオクテット文字列に変換し，体が $ \mathbb{F}_{2^m} の場合は多項式の係数を最高次項を左に持つビット文字列とみなし，そのビット文字列をオクテット文字列に変換する．公式的な変換ルーチンは以下のように規定される：
入力: 体 $ \mathbb{F}_q の元 a．
出力: 長さ $ mlen = \lceil (\log_2 q)/8\rceil オクテットのオクテット文字列 M．
処理: a を以下のようにオクテット文字列 $ M = M_0M_1 . . . M_{mlen−1} に変換する：
1. q = p が奇数の素数である場合、a は区間 $ [0, p − 1] 内の整数である。2.3.7 節で指定された変換ルーチンを用いて a を M に変換する（a と mlen を入力とする）。出力は M となる。
2. $ q = 2^m の場合、$ a = a_{m−1}x^{m−1} + · · · + a_1x + a_0 は2項多項式である。a を$ M に変換するには、次のようにする。
2.1. 0 < i ≤ mlen − 1 の場合、次のようにする。
$ M_i = a_{7+8(mlen−1−i)}a_{6+8(mlen−1−i)} . . . a_{8(mlen−1−i)}
2.2.$ M_0 の左端 8(mlen) − m ビットを 0 に設定し、右端 8 − (8(mlen) − m) ビットを$ a_{m−1}a_{m−2} . . . a_{8(mlen)−8} に設定する。
2.3. 出力$ M
2.3.6 オクテット列からフィールド要素への変換
オクテット文字列は、この節で説明するように体元に変換する必要があります。非公式な考え方としては、体が $ \mathbb{F}_pの場合はオクテット文字列を整数に変換し、体が $ \mathbb{F}_{2^m}の場合は、オクテット文字列のビットを、右端のビットを定数項とする2項多項式の係数として使用します。正式な変換ルーチンは次のように規定されます。
入力: 使用する体 $ \mathbb{F}_q の指定と、長さ $ mlen = \lceil (\log_2 q)/8\rceil オクテットのオクテット文字列 M。
出力: $ \mathbb{F}_q の元 a、または「invalid」(無効)。
処理: $ M_i = M^0_i M^1_i . . . M^7_i である $ M = M_0M_1 . . . M_{mlen−1} を、次のように体元 a に変換します。
1. q = p が奇数の素数である場合、a は区間 $ [0, p − 1] 内の整数でなければならない。 2.3.8 節で指定された変換ルーチンを使用して、$ M を整数 a に変換する。a が区間 $ [0, p − 1] 内にない場合は「invalid」(無効)を出力して停止し、そうでない場合は a を出力する。
2. $ q = 2^m の場合、a は次数 m − 1 以下の2元多項式でなければならない。体元 a を $ a = a_{m−1}x^{m−1} + · · · + a_1x + a_0 と設定し、次の関係を満たすものとする。
$ a_i = M^{7−i+8( \lfloor i/8\rfloor)}_{mlen−1−\lfloor i/8 \rfloor}
$ M_0 の左端 $ 8(mlen) − m ビットがすべて 0 でない場合は「invalid」(無効)を出力して停止し、そうでない場合は a を出力する。
2.3.7 整数からオクテット列への変換
整数は、このセクションで説明するようにオクテット文字列に変換する必要があります。非公式には、整数を2進数で表現し、結果のビット文字列をオクテット文字列に変換します。公式には、変換ルーチンは以下のように規定されます。
入力: 非負整数 x と、オクテット文字列の希望する長さ mlen。次の式を満たす必要があります。
$ 2^{8(mlen)} > x
出力: 長さ mlen オクテットのオクテット文字列 $ M
処理: 基数 $ 2^8 = 256 で表される $ x = x_{mlen−1}2^{8(mlen−1)} + x_{mlen−2}2^{8(mlen−2)} + · · · + x_12^8 + x_0 を、以下のようにオクテット文字列 $ M = M_0M_1 . . . M_{mlen−1} に変換します。
1. $ 0 ≤ i ≤ mlen − 1 の場合、次のように設定します。
$ M_i = x_{mlen−1−i}
2. $ M を出力します。
2.3.8 オクテット列から整数への変換
オクテット文字列は、このセクションで説明するように整数に変換する必要があります。非公式には、オクテット文字列を整数の256進表現と見なすという単純な考え方です。公式には、変換ルーチンは以下のように規定されます。
入力: 長さ mlen オクテットのオクテット文字列 $ M 。
出力: 整数 $ x 。
処理: $ M = M_0M_1 . . . M_{mlen−1} を以下のように整数 $ x に変換します。
1. $ M_i を範囲 $ [0, 255] の整数と見なし、以下のように設定します。
$ x = \sum_{i=0}^{mlen-1}2^{8(mlen-1-i)}M_i
2. $ x を出力します。
2.3.9 フィールド要素から整数への変換
体の元は、この節で説明するように整数に変換する必要があります。非公式には、体が $ \mathbb{F}_pの場合は変換は不要であり、体が $ \mathbb{F}_{2^m}の場合はまず2元多項式をビット列に変換し、次にビット列を整数に変換するという考え方です。正式には、変換ルーチンは次のように指定されます。
入力: 体 $ \mathbb{F}_q の元 a。
出力: 整数 x。
アクション: 体の元 a を次のように整数 x に変換します。
1. $ q = p が奇数の素数の場合、a は区間 $ [0, p − 1] 内の整数でなければなりません。出力 $ x = a 。
2. $ q = 2^m の場合、a は最大で m−1 次までの2元多項式でなければなりません。つまり、$ a = a_{m−1}x^{m−1} + a_{m−2}x^{m−2} + · · · + a_1x + a_0 です。設定:
$ x = \sum_{i=0}^{m-1}2^ia_i
$ x を出力します。
3 暗号コンポーネント Cryptographic Components
このセクションでは、署名スキーム、暗号化スキーム、および鍵共有スキームの構築に使用される様々な暗号コンポーネントについて説明します。
実装に関する説明、セキュリティに関する説明、参考文献など、このセクションの内容に関する解説については、付録Bを参照してください。
3.1 楕円曲線領域(ドメイン)パラメータ Elliptic Curve Domain Parameters
この文書で説明する各公開鍵暗号方式の演算には、いくつかの楕円曲線領域パラメータによって決定される有限体上の楕円曲線上の算術演算が含まれます。
このセクションでは、楕円曲線領域パラメータの提供について説明します。楕円曲線領域(ドメイン)パラメータとは何か、どのように生成し、どのように検証すべきかについて説明します。
使用できる楕円曲線領域パラメータには、$ \mathbb{F}_p 上の楕円曲線領域パラメータと$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータの 2 種類があります。セクション 3.1.1 では $ \mathbb{F}_p 上の楕円曲線領域パラメータについて説明し、セクション 3.1.2 では $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータについて説明します。
楕円曲線領域パラメータは検証可能ランダムである可能性があります。つまり、パラメータの一部は、あるシード値 S に適用された安全なハッシュ関数の出力として取得されます。検証可能ランダムな楕円領域パラメータが推奨されますが、優れたパフォーマンスなど、さまざまな理由から他のパラメータが使用される場合もあります。
3.1.1 $ \mathbb{F}_p 上の楕円曲線領域パラメータ
$ \mathbb{F}_p上の楕円曲線領域パラメータは、以下の6つの組から成ります。
$ T = (p, a, b, G, n, h)
有限体$ \mathbb{F}_pを表す整数 p、次式で定義される楕円曲線 $ E(\mathbb{F}_p)を表す2つの元 $ a, b \in \mathbb{F}_p から成ります。
$ E : y^2 \equiv x^3 + ax + b (\mod p)
$ E(\mathbb{F}_p) 上の基点 $ G = (x_G, y_G) 、$ G の位数である素数 $ n 、そして余因子 $ h = \#E(\mathbb{F}p)/n である整数 $ h です。
$ \mathbb{F}_p上の楕円曲線領域パラメータは、楕円曲線と基点を正確に指定します。これは、ECC に基づく公開鍵暗号方式を正確に定義するために必要です。
楕円曲線領域パラメータ$ T がセクション3.1.3で規定されているように検証可能なランダムである場合、それらは導出されるシード値$ Sを伴うべきである。
セクション3.1.1.1では$ \mathbb{F}_p上の楕円曲線領域パラメータを生成する方法について説明し、セクション3.1.1.2では$ \mathbb{F}_p上の楕円曲線領域パラメータを検証する方法について説明している。
3.1.1.1 $ \mathbb{F}_p 上の楕円曲線領域パラメータ生成の基本
$ \mathbb{F}_p 上の楕円曲線領域パラメータは、以下のように生成する。
入力: 楕円曲線領域パラメータに必要なセキュリティレベル（ビット単位）の概算値
— これは整数 $ t \in \{80, 112, 128, 192, 256\} でなければならない。シード値 S は任意である。
出力: $ \mathbb{F}_p 上の楕円曲線領域パラメータ:
$ T = (p, a, b, G, n, h)
対応する楕円曲線上の対数演算には約 2t 回の演算が必要となる。
アクション: $ \mathbb{F}_p 上の楕円曲線領域パラメータを以下のように生成する。
1. 有限体$ \mathbb{F}_pを決定するために、$ 80 < t < 256 の場合には $ \lceil \log_2 p\rceil = 2t、t = 256 の場合には $ \lceil \log_2 p\rceil = 521、t = 80 の場合には $ \lceil \log_2 p\rceil = 192 となるような素数 p を選択する。
2. 次式で定義される楕円曲線 $ E(\mathbb{F}_p) を決定するために、元 $ a, b \in \mathbb{F}_p を選択する。
$ E : y^2 \equiv x^3 + ax + b (\mod p)
$ E(\mathbb{F}_p) 上の基点 $ G = (x_G, y_G)、$ G の位数である素数 $ n、および余因子 $ h = \#E(\mathbb{F}_p)/n である整数 h を、以下の制約に従って決定する。
$ 4a^3 + 27b^2 \not\equiv 0 (\mod p).
$ \#E(\mathbb{F}_p)\ne p.
$ 1 \le B < 100のすべてに対して$ p^B \not\equiv 1(\mod p)
$ h \le 2^{i/8}.
$ n − 1 と $ n + 1 はそれぞれ大きな素因数 $ r を持つ必要があります。これは $ \log_n(r) > \tfrac{19}{20} という意味で大きいです。
シード$ Sが指定されている場合は、係数ペア$ (a,b)、点$ G、またはその両方を$ Sから導出する必要があります。セクション3.1.3を参照してください。
3. $ T = (p, a, b, G, n, h)を出力
このプリミティブは、既知の曲線選択手法（例えば、複素乗算に基づく手法や、一般的な点数計算アルゴリズムに基づく手法など）のいずれかを使用できます。ただし、相互運用性を高めるため、実装者はSEC 2 SEC 2 で規定されている $ \mathbb{F}_p 上の楕円曲線定義域パラメータのいずれかを使用することを強く推奨します。詳細については付録Bを参照してください。 3.1.1.2 $ \mathbb{F}_p 上の楕円曲線領域パラメータの検証
多くの場合、$ \mathbb{F}_p 上の楕円曲線領域パラメータを使用するエンティティは、安全でないパラメータの悪意のある挿入を防ぐため、または不注意によるコーディングエラーや伝送エラーを検出するために、パラメータが有効であること、つまり楕円曲線領域パラメータの算術要件を満たしていることの保証を受けることが必要または望ましい。
エンティティ$ Uが$ \mathbb{F}_p上の楕円曲線定義域パラメータの有効性を保証するために許容される方法は4つあります。少なくとも1つの方法を提供する必要がありますが、多くの場合、複数の方法を実行することでより高いセキュリティが得られます。
許容される4つの方法は次のとおりです。
1. エンティティ$ Uは、セクション3.1.1.2.1で説明されている検証プリミティブを使用して、$ \mathbb{F}_p自体の楕円曲線ドメインパラメータの検証を実行します。
2. エンティティ$ Uは、信頼できるシステムを使用して$ \mathbb{F}_p自体に楕円曲線ドメインパラメータを生成し、信頼できるシステムはセクション3.1.1.1で指定されたプリミティブを使用します。
3. エンティティ$ Uは、エンティティ$ Uの$ \mathbb{F}_p上の楕円曲線ドメインパラメータの使用に関して信頼された当事者が、セクション3.1.1.2.1で説明されている検証プリミティブを使用してパラメータの検証を実行したという保証を確実な方法で受け取ります。
4. エンティティ$ Uは、エンティティ$ Uによる$ \mathbb{F}_p上の楕円曲線ドメインパラメータの使用に関して信頼された当事者が、セクション3.1.1.1で指定されたプリミティブを使用する信頼できるシステムを使用してパラメータを生成したことを確実に保証されます。
通常、エンティティ $ U が楕円曲線ドメインパラメータが有効であるという別の当事者の保証を受け入れる場合、その別の当事者は CA です。
3.1.1.2.1 $ \mathbb{F}_p 上の楕円曲線領域パラメータ検証の基本
$ \mathbb{F}_p 上の楕円曲線領域パラメータ検証プリミティブは、$ \mathbb{F}_p上の楕円曲線領域パラメータが以下のように有効であることを検証するために用いる。
入力:$ \mathbb{F}_p上の楕円曲線領域パラメータ：
$ T = (p, a, b, G, n, h)
および、楕円曲線領域パラメータに要求されるセキュリティレベル（ビット単位）のおおよその整数 $ t \in \{80, 112, 128, 192, 256\}。オプションでシード値 $ S。
出力: 楕円曲線領域パラメータが有効かどうかを示す値（「有効(valid)」または「無効(invalid)」）
アクション: $ \mathbb{F}_p上の楕円曲線定義域パラメータを次のように検証します。
1. p が奇数の素数であり、80 < t < 256 の場合は $ \lceil \log_2 p\rceil = 2tとなるか、t = 256 の場合は $ \lceil \log_2 p\rceil = 521となるか、t = 80 の場合は $ \lceil \log_2 p\rceil = 192となるかを確認します。
2. $ a, b, x_G, y_G が区間 $ [0, p − 1] 内の整数であることを確認します。
3. $ 4a^3 + 27b^2 \not\equiv 0 (\mod p) であることを確認します。
4. $ y^2_G \equiv x^3_G + ax_G + b (\mod p) であることを確認します。
5. $ n が素数であることを確認します。
6. $ h \le 2^{t/8}] かつ $ h = \lfloor (\sqrt p+1)^2/n\rfloorであることを確認します。
7. $ nG = \mathcal{O} であることを確認します。
8. $ 1 \le B < 100 のすべてについて $ p^B \not\equiv 1 (\mod n) であり、$ n \not= p であることを確認します。
9. いずれかのチェックが失敗した場合は「無効(invalid)」を出力し、それ以外の場合は「有効(valid)」を出力します。
上記のステップ8では、Menezes-Okamoto-Vanstone攻撃、Frey-R¨uck攻撃、またはSemaev-Smart-Satoh-Araki攻撃のいずれかに対して脆弱な既知の曲線の弱クラスを除外します。詳細については付録Bを参照してください。
楕円曲線の領域パラメータがセクション3.1.3で説明したように検証可能なランダム生成されている場合、aとbがシード$ Sから正しく導出されていること、または$ Gがシード$ Sから正しく導出されていること、あるいはすべてがシード$ Sから正しく導出されていることを確認することもできます。
3.1.2 $ \mathbb{F}_{2^m} 上の楕円曲線の領域パラメータ
$ \mathbb{F}_{2^m} 上の楕円曲線の領域(ドメイン)パラメータは、以下の7つの組から成ります。
$ T = (m, f(x), a, b, G, n, h)
これは、有限体 $ \mathbb{F}_{2^m}を表す整数 $ m、$ \mathbb{F}_{2^m}の表現を表す $ m 次既約二項式 $ f (x)、次式で定義される楕円曲線 $ E(\mathbb{F}_{2^m})
を表す2つの元 $ a,b\in\mathbb{F}_{2^m},
$ \mathbb{F}_{2^m} における$ y^2 + xy = x^3 + ax^2 + b
および、$ E(\mathbb{F}_{2^m})上の基点 $ G = (x_G, y_G)、$ G の位数である素数 $ n、そして余因子 $ h = \#E(\mathbb{F}_{2^m})/nである整数 h で構成されます。
$ \mathbb{F}_{2^m}上の楕円曲線の領域パラメータは、楕円曲線と基点を正確に指定します。これは、ECCに基づく公開鍵暗号方式を正確に定義するために必要です。
楕円曲線領域パラメータTが3.1.3節で規定されているように検証可能なランダムである場合、それらは導出されるシード値Sを伴う必要があります。
3.1.2.1節では、$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータを生成する方法について説明し、3.1.2.2節では、$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータを検証する方法について説明します。
3.1.2.1 $ \mathbb{F}_{2^m} 上の楕円曲線領域パラメータ生成の基本
$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータは、以下のように生成する。
入力: 楕円曲線領域パラメータに必要なセキュリティレベル（ビット単位）の概算値
— これは整数 $ t \in \{80, 112, 128, 192, 256\} でなければならない。シード値 S は任意である。
出力: $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータ:
$ T = (m, f (x), a, b, G, n, h)
ただし、対応する楕円曲線上の対数演算には約 $ 2^t 回の演算が必要となる。
アクション: $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータを以下のように生成する。
1. $ t′ を、集合 $ \{112, 128, 192, 256, 512\} における $ t より大きい最小の整数とする。有限体 $ \mathbb{F}_{2^m}を決定するために、$ 2t < m < 2t′ となるような $ m \in \{163, 233, 239, 283, 409, 571\} を選択する。
2. 2.1.2 節の表 1 から m次二項既約多項式 $ f (x) を選択し、 $ \mathbb{F}_{2^m}の表現を決定する。
3. 元 $ a,b \in \mathbb{F}_{2^m}を選択し、次式で定義される楕円曲線$ E(\mathbb{F}_{2^m}) を決定する。
: $ \mathbb{F}_{2^m} において $ E:y^2 + xy = x^3 + ax^2 + b、
$ E(\mathbb{F}_{2^m})上の基点 $ G = (x_G, y_G)、$ G の位数である素数$ n、および余因子 $ h = \#E(\mathbb{F}_{2^m} )/n である整数 $ h とする。ただし、以下の制約条件を満たす。
$ \mathbb{F}_{2^m}において $ b \not= 0。
$ \#E(\mathbb{F}_{2^m})\not=2^m。
$ 1 \le B <100m のすべてにおいて、 $ 2^B \not\equiv1 (\mod n) である。
$ h \le 2^{t/8}。
$ n − 1と$ n + 1はそれぞれ大きな素因数$ r を持つべきであり、これは $ \log_n(r) > \tfrac{19}{20} の意味で大きい。
シード値 $ S が与えられた場合、係数ペア $ (a, b)、点 $ G、またはその両方をそこから導出すべきである。セクション 3.1.3 を参照。
4. 出力 $ T = (m, f (x), a, b, G, n, h)。
このプリミティブでは、複素乗算に基づく方法や一般的な点数計算アルゴリズムに基づく方法など、既知の曲線選択手法のいずれかを使用することもできる。ただし、相互運用性を高めるために、実装者は SEC 2 SEC 2 で規定されている $ \mathbb{F}_{2^m} 上の推奨楕円曲線定義域パラメータのいずれかを使用することを強く推奨する。 詳細については付録Bを参照してください。
3.1.2.2 $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータの検証
$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータを使用するエンティティは、多くの場合、パラメータが有効であること、すなわち楕円曲線領域パラメータの算術要件を満たしていることの保証を受けることが必要または望ましい。これは、安全でないパラメータの悪意のある挿入を防ぐため、または不注意による符号化エラーや伝送エラーを検出するためである。
エンティティ$ Uが$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータが有効であることの保証を受けるには、4つの許容される方法がある。少なくとも1つの方法を提供する必要があるが、多くの場合、複数の方法を実行することでより高いセキュリティが得られる可能性がある。
許容される4つの方法は以下のとおりである。
1. エンティティ$ Uは、セクション3.1.2.2.1で説明されている検証プリミティブを使用して、$ \mathbb{F}_{2^m}自体の楕円曲線ドメインパラメータの検証を実行します。
2. エンティティ$ Uは、信頼できるシステムを使用して$ \mathbb{F}_{2^m}自体に楕円曲線ドメインパラメータを生成します。信頼できるシステムは、セクション3.1.2.1で指定されたプリミティブを使用します。
3. エンティティ$ Uは、エンティティ$ Uの$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータの使用に関して信頼された当事者が、セクション3.1.2.2.1で説明されている検証プリミティブを使用してパラメータの検証を実行したという保証を確実な方法で受け取ります。
4. エンティティ$ Uは、エンティティ$ Uによる$ \mathbb{F}_{2^m}上の楕円曲線ドメインパラメータの使用に関して信頼された当事者が、セクション3.1.2.1で指定されたプリミティブを使用する信頼できるシステムを使用してパラメータを生成したことの保証を確実な方法で受け取ります。
通常、エンティティ $ U が楕円曲線ドメインパラメータが有効であるという別の当事者の保証を受け入れる場合、その別の当事者は CA です。
3.1.2.2.1 $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータ検証プリミティブ
$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータ検証プリミティブは、$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータが以下のように有効であることを確認するために用いられる。
入力: $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータ:
$ T= (m,f(x),a,b,G,n,h)
および整数 $ t \in \{80, 112, 128, 192, 256\}。これは、楕円曲線領域パラメータに必要なセキュリティレベル（ビット単位）のおおよその値です。
出力: 楕円曲線領域パラメータが有効かどうかを示す値 (「valid(有効)」または「invalid(無効)」)。
アクション: $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータを以下のように検証します。
1. $ t′ を $ \{112, 128, 192, 256, 512\} の集合の中で t より大きい最小の整数とする。$ m が $ \{163, 233, 239, 283, 409, 571\} の集合の中で $ 2t < m < 2t′ を満たす整数であることを確認しなさい。
2. $ f (x) が 2.1.2 節の表 1 に記載されている $ m 次二項既約多項式であることを確認しなさい。
3. $ a, b, x_G, y_G が $ m − 1 次以下の二項多項式であることを確認しなさい。
4. $ \mathbb{F}_{2^m}において $ b \not= 0 であることを確認しなさい。
5. $ \mathbb{F}_{2^m}において $ y^2_G + x_Gy_G = x^3_G + ax^2_G + b であることを確認しなさい。
6. $ n が素数であることを確認しなさい。
7. $ h \le 2^{t/8} かつ $ h = \lfloor(\sqrt{2^m}+1)^2/n\rfloor であることを確認する。
8. $ nG = \mathcal{O} であることを確認する。
9. $ 1 \le B < 100m のすべてについて $ 2^B\not\equiv1(\mod n)であること、および $ nh \not= 2^m であることを確認する。
10. いずれかのチェックが失敗した場合は「invalid(無効)」を出力し、それ以外の場合は「valid(有効)」を出力する。
上記のステップ 9 では、Menezes-Okamoto-Vanstone 攻撃、Frey-R¨uck 攻撃、または Semaev-Smart-Satoh-Araki 攻撃のいずれかに対して脆弱な既知の曲線クラスを除外している。詳細については付録 B を参照のこと。
セクション3.1.3で説明したように、楕円曲線ドメインパラメータが検証可能にランダムに生成された場合、$ aと$ bがシードから正しく導出されたことも確認でき、$ Gが$ Sから正しく導出されたことも確認できる。
3.1.3 検証可能ランダムな曲線と基点生成器
本節では、シード$ Sから楕円曲線係数$ aと$ b、そして基点生成器$ Gを導出する方法を規定する。これらの方法はANS X9.62 X9.62bに準拠している。 ここで示す2つのルーチンは、 (a) 検証可能ランダムな楕円曲線または基点の生成、および (b) 楕円曲線または基点が検証可能ランダムであることを検証することの両方に使用できる。最初の適用では、ユーザーはシードを選択し、選択ルーチンを実行する。2番目のルーチンでは、ユーザーは楕円曲線または基点を生成した別のユーザーからシードを受け取る。その後、ユーザーはルーチンを再実行して、楕円曲線または基点を復元するか、結果が使用を意図した既存の楕円曲線または基点と一致するかどうかを確認する。
3.1.3.1 曲線選択
入力: 長さ $ g/8 オクテットの「seed(シード)」オクテット列 $ S、フィールドサイズ $ q、出力長 $ hashlen オクテットのハッシュ関数 Hash、フィールド要素 $ a \in \mathbb{F}_q。
出力: フィールド要素 $ b \in \mathbb{F}_q または「failure(失敗)」。
アクション: 要素 $ b を以下のように生成します。
1. $ m = \lceil \log_2q\rceil とする。
2. $ t = 8hashlen とする。
3. $ s = \lfloor(m − 1)/t \rfloor とする。
4. $ q が偶数なら $ k = m − st とし、$ q が奇数なら$ k = m − st − 1 とする。
5. $ S を整数 $ s_0 に変換する。
6. $ j が 0 から $ s までであるとき、以下を実行する。
6.1. $ s_j = s_0 + j \mod 2^g とする。
6.2. $ S_j を、長さ $ g/8 オクテットのオクテット文字列に変換された整数 $ s_j とする。
6.3. $ H_j = Hash(S_j ) とする。
6.4. $ H_j を整数 $ e_j に変換する。
7. $ e = e_02^{ts} + e_12^{t(s−1)} + · · · + e_s \mod 2^{k+st} とします。
8. $ e を次のように体元に変換します。
8.1. $ e を長さ $ mlen = \lceil(\log_2q)/8\rceilオクテットのオクテット列 E に変換します。
8.2. $ E を体元 $ r \in \mathbb{F}_q に変換します。
9. $ qが偶数の場合、次のようにします。
9.1. $ r = 0 の場合、「failure(失敗)」を出力して終了します。
9.2. $ r \not= 0の場合、 $ b = r \in \mathbb{F}_qを出力して終了します。
10. $ q が奇数の場合、次のようにします。
10.1. $ a = 0 の場合、「failure(失敗)」を出力して終了します。
10.2. $ \mathbb{F}_qにおいて $ 4r + 27 = 0 の場合、「failure(失敗)」を出力して停止します。
10.3. $ \mathbb{F}_qにおいて$ a^3/r が平方根を持たない場合、「failure(失敗)」を出力して停止します。
10.4. それ以外の場合、 $ b = \sqrt{a^3/r}\in\mathbb{F}_qを出力して停止します。
3.1.3.2 点の選択
入力: 長さ $ g/8 オクテットの「seed(シード)」オクテット列 $ S、フィールドサイズ $ q、出力長 $ hashlen のハッシュ関数 Hash、楕円曲線パラメータ a と b、楕円曲線コファクタ h。
出力: 楕円曲線点 G または「失敗」。
アクション: 以下のように楕円曲線点 G を生成する。
1. $ A = 4261736520706F696E74_{16} とし、これはテキスト文字列「Base point」のASCII表現に関連付けられたオクテット文字列です。
2. $ B = 01_{16} とし、長さ1のオクテット列とします。
3. $ c = 1 とします。
4. 整数 $ c を長さ $ 1 + \lfloor \log_{256}(c)\rfloor のオクテット列 C に変換します。
5. $ H = Hash(A‖B‖C‖S) とします。
6. $ H を整数 $ e に変換します。
7. $ t = e \mod 2q とします。
8. $ u = t \mod q、$ z = \lfloor t/q \rfloor とします。
9. 整数 $ u を体元 $ x \in \mathbb{F}_q に変換します。
10. 圧縮された点情報 $ (x, z) から、楕円曲線に応じて適切な $ y座標を復元します。
11. 有効な $ yが存在しない場合は、$ c をインクリメントして手順 4 に戻ります。
12. $ R = (x, y) とします。
13. $ G = hR を計算します。
14. $ G を出力します。
3.2 楕円曲線鍵ペア
本文書で説明するすべての公開鍵暗号方式は、楕円曲線鍵ペアと呼ばれる鍵ペアを使用します。
楕円曲線の領域パラメータ$ T = (p, a, b, G, n, h) または $ (m, f (x), a, b, G, n, h) が与えられた場合、$ T に関連付けられた楕円曲線鍵ペア $ (d, Q) は、区間$ [1, n − 1] 内の整数である楕円曲線秘密鍵 $ d と、点 $ Q = dG である楕円曲線公開鍵 $ Q = (x_Q, y_Q) で構成されます。
3.2.1節では楕円曲線鍵ペアの生成方法、3.2.2節では楕円曲線公開鍵の検証方法、3.2.3節では楕円曲線公開鍵の部分検証方法について説明します。
3.2.1 楕円曲線鍵ペア生成プリミティブ
楕円曲線鍵ペアは以下のように生成する。
入力: 有効な楕円曲線ドメインパラメータ $ T = (p, a, b, G, n, h) または $ (m, f (x), a, b, G, n, h)。
出力: $ T に関連付けられた楕円曲線鍵ペア $ (d, Q)。
アクション: 以下のように楕円曲線鍵ペアを生成する。
1. 区間$ [1, n − 1] 内の整数 $ d をランダムまたは擬似ランダムに選択する。
2. $ Q = dG を計算する。
3. $ (d, Q) を出力する。
3.2.2 楕円曲線公開鍵の検証
楕円曲線公開鍵を使用する主体は、多くの場合、その公開鍵が有効であること、すなわち楕円曲線公開鍵の算術的要件を満たしていることの保証を得ることが必要または望ましい。これは、小集団攻撃などの攻撃を可能にするために不正な公開鍵が悪意を持って挿入されるのを防ぐため、あるいは不注意による符号化エラーや伝送エラーを検出するためである。
主体Uが楕円曲線公開鍵が有効であることの保証を得るには、4つの方法が許容される。少なくとも1つの方法を提供する必要があるが、多くの場合、複数の方法を実行することでより高いセキュリティが得られる可能性がある。
許容される4つの方法は以下のとおりである。
1. エンティティ$ Uは、セクション3.2.2.1に規定されている公開鍵検証プリミティブを用いて、楕円曲線公開鍵自体の検証を行う。
2. エンティティ$ Uは、セクション3.2.1に規定されているプリミティブを使用する信頼できるシステムを用いて、楕円曲線公開鍵自体を生成する。
3. エンティティ$ Uは、$ Uによる楕円曲線公開鍵の使用に関して信頼されている当事者が、セクション3.2.2.1に規定されている公開鍵検証プリミティブを用いて公開鍵の検証を行ったという保証を、真正な方法で受け取る。
4. エンティティ$ Uは、$ Uによる楕円曲線公開鍵の使用に関して信頼されている当事者が、セクション3.2.1に規定されているプリミティブを使用する信頼できるシステムを用いて公開鍵を生成したという保証を、真正な方法で受け取る。
通常、$ Uが楕円曲線公開鍵の有効性に関する他者の保証を受け入れる場合、その他者とは、認証プロセスにおいて公開鍵を検証したCAである。場合によっては、$ UはCA以外の第三者から保証を受けることもあります。例えば、公開鍵が署名付きメッセージ（例えば$ Vによって署名されたメッセージ）で受信された場合、$ Uは$ Vから公開鍵の有効性に関する保証を受け入れることが許容される場合があります。
3.2.2.1 楕円曲線公開鍵検証プリミティブ
楕円曲線公開鍵検証プリミティブは、楕円曲線公開鍵の有効性を以下のように検証する。
入力: 有効な楕円曲線ドメインパラメータ $ T = (p, a, b, G, n, h) または $ (m, f (x), a, b, G, n, h)、および $ T に関連付けられた楕円曲線公開鍵 $ Q = (x_Q, y_Q)。
出力: 楕円曲線公開鍵が有効かどうかを示す値（「valid(有効)」または「invalid(無効)」）。
アクション: 楕円曲線公開鍵を以下のように検証する。
1. $ Q \not= \mathcal{O} であることを確認する。
2. $ T が $ \mathbb{F}_p 上の楕円曲線の領域パラメータを表す場合、$ x_Q と$ y_Q が区間$ [0, p − 1] 内の整数であること、および次式が成り立つことを確認する。
$ y^2_Q \equiv x^3_Q+ax_Q+ b (\mod p)
3. $ T が $ \mathbb{F}_{2^m} 上の楕円曲線の領域パラメータを表す場合、$ x_Q と$ y_Q が次数 $ m − 1 以下の2項多項式であること、および次式が成り立つことを確認する。
$ y^2_Q + x_Qy_Q = x^3_Q + ax^2_Q + b 。
4. $ nQ = \mathcal{O} であることを確認する。
5. いずれかのチェックに失敗した場合は「invalid(無効)」を出力し、それ以外の場合は「valid(有効)」を出力する。
上記のルーチンでは、ステップ 1、2、3 で $ Q が $ E 上の無限遠点以外の点であることを確認し、ステップ 4 で$ Q が$ G のスカラー倍であることを確認します。
ステップ 4 では、点 $ nQ を計算する必要がない場合があります。たとえば、$ h = 1 の場合、ステップ 2 と 3 の確認によって $ nQ = \mathcal{O} が暗黙的に示されます。これは、この特性がすべての点 $ Q \in E に対して成り立つためです。$ h = 2 で、$ T が $ \mathbb{F}_{2^m} 上の楕円曲線の領域パラメータを表す場合、$ x_Q のトレースが 1 であることを確認するだけで十分です。$ h が小さい他の状況でも、同様の確認を行うことができます。
3.2.3 楕円曲線公開鍵の部分検証
楕円曲線公開鍵を使用する主体にとって、公開鍵が「完全に」有効であるのではなく、部分的に有効であるという保証を得るだけで十分な場合があります。この場合、楕円曲線公開鍵$ Qは、$ Qが対応する楕円曲線上の点であるとき、部分的に有効であるとされますが、ある$ dに対して$ Q = dGが必ずしも成立するとは限りません。
MQV鍵共有方式と、cofactor Diffie-Hellmanプリミティブを用いたDiffie-Hellman方式は、どちらも、主体が関連する公開鍵が部分的に有効であることを確認するだけでセキュリティを確保できるように設計された方式の例です。 （この機能が望ましいのは、これらの方式が、状況によっては、「標準」Diffie-Hellmanプリミティブを用いたDiffie-Hellman方式のような「完全に」有効な公開鍵を必要とする方式よりも計算上の優位性を持つことを意味するためです。計算上の優位性は、公開鍵の部分的な検証が公開鍵の「完全な」検証よりも効率的であるという事実に起因します。）
エンティティ$ Uが楕円曲線公開鍵が部分的に有効であるという保証を得るための許容可能な方法は4つあります。少なくとも1つの方法を提供する必要がありますが、多くの場合、複数の方法を実行することでより高いセキュリティが得られます。
許容される4つの方法は次のとおりです。
1. エンティティ$ Uは、セクション3.2.3.1で説明されている公開鍵部分検証プリミティブを使用して、楕円曲線公開鍵自体の部分検証を実行します。
2. エンティティ$ Uは、セクション3.2.1で指定されたプリミティブを使用する信頼できるシステムを使用して、楕円曲線公開鍵自体を生成します。
3. エンティティ$ Uは、$ Uによる楕円曲線公開鍵の使用に関して信頼される当事者が、セクション3.2.3.1に規定される公開鍵部分検証プリミティブを用いて公開鍵の部分検証を実行したことについて、真正な方法で保証を受ける。
4. エンティティ$ Uは、$ Uによる楕円曲線公開鍵の使用に関して信頼される当事者が、セクション3.2.1に規定されるプリミティブを使用する信頼できるシステムを用いて公開鍵を生成したことについて、真正な方法で保証を受ける。
3.2.3.1 楕円曲線公開鍵部分検証プリミティブ
楕円曲線公開鍵部分検証プリミティブは、楕円曲線公開鍵が部分的に有効であることを以下のように検証するために用いる。
入力: 有効な楕円曲線ドメインパラメータ $ T = (p, a, b, G, n, h) または$ (m, f (x), a, b, G, n, h)、および$ T に関連付けられた楕円曲線公開鍵 $ Q = (x_Q, y_Q)。
出力: 楕円曲線公開鍵が部分的に有効かどうかを示す値（「valid(有効)」または「invalid(無効)」）。
アクション: 楕円曲線公開鍵を以下のように部分的に検証する。
1. $ Q \not= \mathcal{O} であることを確認する。
2. $ T が$ \mathbb{F}_p 上の楕円曲線の領域パラメータを表す場合、 $ x_Q と $ y_Q が区間$ [0, p − 1] 内の整数であること、および次式が成り立つことを確認する。
$ y^2_Q ≡ x^3_Q + ax_Q + b (\mod p)
3. $ T が $ \mathbb{F}_{2^m} 上の楕円曲線の領域パラメータを表す場合、$ x_Q と$ y_Q が次数$ m − 1 以下の2項多項式であること、および次式が成り立つことを確認する。
$ y^2_Q + x_Qy_Q = x^3_Q + ax^2_Q + b in $ \mathbb{F}_{2^m}
4. いずれかのチェックが失敗した場合は「invalid(無効)」を出力し、それ以外の場合は「valid(有効)」を出力する。
上記のルーチンでは、ステップ 1、2、および 3 で、$ Q が無限遠点以外の E 上の点であることを確認します。
3.2.4 検証可能鍵ペア生成および検証支援
状況によっては、権限機関がエンティティUの鍵ペア生成に協力したい場合があります。例えば、エンティティUがなりすましや未知の鍵共有攻撃などの悪意のある目的で鍵ペアを盗用または偽造していないことを確認するために、権限機関は鍵ペアに何らかの入力を行う場合があります。また、エンティティUが秘密鍵に十分なエントロピーを提供できない場合、権限機関は安全な環境下でエントロピーを補充したい場合があります。
自己署名署名とは、署名されたメッセージに署名が含まれる署名です。自己署名ECDSA署名を生成することが可能です。これは、まず署名を選択し、次にメッセージの残りの部分を選択し、最後に鍵ペアを選択することによって行われます。詳細はセクション4.1.7に記載されています。
ECDSAの場合、自己署名署名は、署名されたメッセージごとに一意の鍵ペアを保証します。自己署名署名から鍵ペアを生成する機能は本質的に一方向であるため、目的の鍵ペアを生成する自己署名署名を作成することは困難です。
認証局が署名されたメッセージに固有の情報を提供する場合、認証局は鍵ペアが一意であることを保証します。一意の鍵ペアは、その鍵ペアが他のエンティティの鍵ペアではなく、攻撃の一環として作成されたものでないことを保証します。
認証局は、署名するメッセージに含めるエントロピーを提供することで、鍵ペア生成にエントロピーを提供することもできます。自己署名署名にこの情報を含めることで、認証局は提供されたエントロピーが鍵ペア生成に使用されたことを保証できます。これを行う理由は、鍵ペア生成器のエントロピー生成の信頼性が低い場合です。その場合、認証局は鍵ペア生成器を支援できます。ただし、このような状況では、鍵ペアのセキュリティを保護するために、認証局は信頼でき、自己署名メッセージの機密性が保たれなければなりません。
3.3 楕円曲線Diffie-Hellmanプリミティブ
本節では、5.1節の楕円曲線統合暗号化方式および6.1節の楕円曲線Diffie-Hellman方式の動作の基礎となる楕円曲線Diffie-Hellmanプリミティブについて規定する。
ここで規定するプリミティブは、楕円曲線Diffie-Hellmanプリミティブと楕円曲線コファクタDiffie-Hellmanプリミティブの2つである。これらのプリミティブの基本的な考え方は同じである。つまり、一方のエンティティ$ Uが所有する秘密鍵と、もう一方のエンティティ$ Vが所有する公開鍵から共有秘密値を生成することである。これにより、両方のエンティティが対応する鍵を入力として同時にプリミティブを実行すると、同じ共有秘密値が復元される。
しかし、これら2つのプリミティブは微妙に異なります。楕円曲線Diffie-Hellmanプリミティブは、よく知られているDiffie-Hellman鍵共有方式の直接的な類似物ですが、楕円曲線コファクタDiffie-Hellmanプリミティブは、共有秘密値の計算にコファクタを組み込むことで、小サブグループ攻撃などの攻撃に対する効果的な耐性を提供します。
楕円曲線Diffie-Hellmanプリミティブはセクション3.3.1で規定され、楕円曲線コファクタDiffie-Hellmanプリミティブはセクション3.3.2で規定されています。
3.3.1 楕円曲線Diffie-Hellmanプリミティブ
エンティティ$ Uは、楕円曲線Diffie-Hellmanプリミティブを用いて$ Vと共有秘密値を計算するため、以下の手順に従うべきである。
入力: 楕円曲線Diffie-Hellmanプリミティブは、以下のものを入力として受け取る。
1. 有効な楕円曲線ドメインパラメータ$ T = (p, a, b, G, n, h) または$ (m, f (x), a, b, G, n, h)。
2. $ Uが所有するTに関連付けられた楕円曲線秘密鍵 dU。
3. Vが所有するとされるTに関連付けられた有効な楕円曲線公開鍵 QV。
出力: 共有秘密フィールド要素$ z、または「invalid(無効)」。
アクション: 以下の手順で共有秘密値を計算します。
1. 楕円曲線点$ P = (x_P , y_P ) = d_U Q_V を計算する。
2. $ P \not= \mathcal{O} であることを確認する。$ P = \mathcal{O} の場合、「invalid(無効)」を出力して終了する。
3. 共有秘密フィールドの要素として$ z = x_P を出力する。
3.4 楕円曲線MQVプリミティブ
本節では、6.2節で規定された楕円曲線MQV方式の動作の基礎となる楕円曲線MQVプリミティブについて規定する。
このプリミティブの基本的な考え方は、一方のエンティティUが所有する2つの楕円曲線鍵ペアと、もう一方のエンティティVが所有する2つの楕円曲線公開鍵から共有秘密値を生成することである。これにより、両方のエンティティが対応する鍵を入力として同時にプリミティブを実行すると、同じ共有秘密値が復元される。
エンティティUは、楕円曲線MQVプリミティブを用いてエンティティVと共有秘密値を計算するために、以下の手順を採用する必要がある。
入力: 楕円曲線MQVプリミティブは、以下の値を入力として受け取る。
1. 有効な楕円曲線ドメインパラメータ$ T = (p, a, b, G, n, h) または$ (m, f (x), a, b, G, n, h)。
2. $ T に関連付けられ、$ U が所有する2つの楕円曲線鍵ペア$ (d_{1,U}, Q_{1,U} ) と$ (d_{2,U}, Q_{2,U} )。
3. $ T に関連付けられ、$ V が所有しているとされる2つの部分的に有効な楕円曲線公開鍵 $ Q_{1,V} と$ Q_{2,V}。
出力: 共有秘密フィールド要素$ z、または「invalid(無効)」。
アクション: 共有秘密値を次のように計算する。
1. $ T = (p, a, b, G, n, h) の場合は$ q = p とし、$ T = (m, f (x), a, b, G, n, h) の場合は$ q = 2^m とする。
2. $ Q_{2,U} = (x_Q, y_Q) を用いて、次のように整数 $ \overline{Q_{2,U}} を計算する。
2.1. セクション 2.3.9 で指定された変換ルーチンを用いて、$ x_Q を整数$ x に変換する。
2.2. 次を計算する。
$ \overline{x} = x \mod 2^{\lceil(\log_2 n)/2\rceil}
2.3. 次を計算する。
$ \overline{Q_{2,U}} = \overline{x} + 2^{\lceil(\log_2 n)/2\rceil}
3. 次を計算する。
$ s = d_{2,U} + \overline{Q_{2,U}}d_{1,U} \mod n
4. $ Q_{2,V} = (x′_Q, y′_Q) を用いて、次のように整数$ \overline{Q_{2,V}} を計算する。
4.1.セクション2.3.9で指定された変換ルーチンを使用して、$ x′_Qを整数$ x′に変換する。
4.2. 計算：
$ \overline{x′} = x′ \mod 2^{\lceil (\log_2 n)/2\rceil}
4.3. 計算：
$ \overline{Q_{2,V}} = \overline{x′} + 2^{\lceil(\log_2 n)/2\rceil}
5. 楕円曲線点を計算する：
$ P = (x_P , y_P ) = hs(Q_{2,V} + \overline{Q_{2,V}} Q_{1,V} )
6. $ P \not= \mathcal{O}であることを確認する。$ P = \mathcal{O}の場合、「invalid(無効)」を出力して終了する。
7. 共有秘密フィールドの要素として$ z = x_Pを出力する。
3.5 ハッシュ関数 Hash Functions
2005年に、約269回のハッシュ演算でSHA-1の衝突を検出する攻撃WYY05bが発表されました。その後、263回のハッシュ演算を用いた攻撃WYY05aが発表されました。 これらの攻撃は、衝突耐性に対するSHA-1の安全性を低下させます。この標準では、衝突耐性はECDSAにおいて特に重要です。なぜなら、ECDSAに対するアクティブ選択メッセージ攻撃による存在偽造に対抗する必要があるからです。
SHA-1を使用したECDSAのみが使用可能で、アクティブ選択メッセージ攻撃による存在偽造に対して80ビットの安全性が必要な場合、以下の対策のうち1つ以上を実施する必要があります。
検証時には、署名がSHA-1への攻撃が発見される前に生成されたことを独立して保証する。
署名時には、メッセージの内容または一部が、アクティブ選択メッセージ攻撃が実行不可能になるほど予測不可能であることを確認する。これを実現する方法の1つは、800-106で規定されています。 署名または検証を行う際には、メッセージの形式が既存の衝突攻撃に対して脆弱ではないことを確認してください。
このセクションでは、このドキュメントでサポートされる暗号ハッシュ関数を規定します。
ハッシュ関数は、セクション3.1.3で規定されている検証可能ランダム曲線および基点生成器、セクション3.6で規定されている一部の鍵導出関数、セクション3.7で規定されているHMACメッセージ認証コード、およびセクション4.1で規定されているECDSAデジタル署名アルゴリズムによって使用されます。
ハッシュ関数は、オクテット列に関連付けられたハッシュ値を計算するために使用されます。
現時点でサポートされているハッシュ関数のリストは次のとおりです。
SHA-1
SHA-224
SHA-256
SHA-384
SHA-512
これらのハッシュ関数は、FIPS 180-2 180-2 で規定されています。これらの関数は、一定数オクテット未満の長さのオクテット列を、固定長のオクテット列であるハッシュ値にマッピングします。 NIST は SHA-3 ハッシュ関数のコンペを開催しており、2012 年の完了が予定されています。
SHA-3 ハッシュ関数は SHA-2 と同じ出力長を提供しますが、SHA-1 に対する攻撃の拡張に対して SHA-2 よりも脆弱になる可能性が低くなるように設計されています。
この標準 SEC 1 の将来のバージョンでは、SHA-3 が許可される可能性があり、必要に応じて楕円曲線ハッシュ関数などの他のハッシュも許可される可能性があります。
ハッシュ関数に関連付けられたセキュリティレベルは、その用途によって異なります。衝突耐性が必要な場合、セキュリティレベルはハッシュ関数の出力長（ビット単位）の最大半分になります。衝突耐性が不要な場合、セキュリティレベルはハッシュ関数の長さ（ビット単位）以下になります。衝突耐性は、ECDSAにおけるメッセージダイジェストの計算に一般的に必要ですが、それ以外の場合（鍵導出、メッセージ認証、乱数生成、曲線生成など）には厳密には必要ではありません。最近の研究結果によると、SHA-1は80ビット未満の衝突耐性しか提供しないことが示唆されています。したがって、SHA-1はECDSAでメッセージダイジェストを計算する際に、後方互換性のためにのみ使用してください。他のハッシュ関数の場合、衝突耐性のセキュリティレベルは、追って通知があるまで、出力長の半分とみなすことができます。したがって、例えばSHA-256は、128ビットのセキュリティレベルでECDSAのメッセージダイジェストを計算するために使用できます。相互運用性を促進するため、メッセージダイジェスト、メッセージ認証（ECIESの一部としてのHMAC）、鍵導出、および曲線生成に使用するハッシュ関数は、必要なセキュリティレベルの2倍にする必要があります。主に効率性または後方相互運用性の理由から、例外が認められる場合があります。
このセクションの残りの部分では、わかりやすくするために、ハッシュ関数の一般的な操作について説明し、後でハッシュ関数の使用方法を正確に指定できるようにします。
ハッシュ関数 SHA-1、SHA-224、SHA-256、SHA-384、SHA-512 における $ hashlen の値は、それぞれ 20、28、32、48、64 です。ハッシュ関数 SHA-1、SHA-224、SHA-256 における $ hashmaxlen の値は$ 2^{61} − 1 であり、ハッシュ関数 SHA-384 および SHA-512 における $ hashmaxlen の値は$ 2^{125} − 1 です。
ハッシュ値は以下のように計算します。
準備: 承認済みのハッシュ関数を 1 つ選択します。$ Hash は選択したハッシュ関数、$ hashlen は$ Hash を使用して計算されるハッシュ値の長さ（オクテット単位）、$ hashmaxlen は$ Hash を使用してハッシュできるメッセージの最大長（オクテット単位）を表します。
入力: ハッシュ関数への入力はオクテット文字列$ M です。
出力: ハッシュ値$ H = Hash(M) は、長さ$ hashlen オクテットのオクテット列、または「invalid(無効)」です。
アクション: ハッシュ値$ H を次のように計算します。
1. $ M が$ hashmaxlenオクテット長未満であることを確認します。つまり、次の条件を満たしていることを確認します。
$ |M | < hashmaxlen
$ |M | ≥ hashmaxlen の場合、「invalid(無効)」を出力して停止します。
2. セクション 2.3.2 で指定された変換ルーチンを使用して、$ M をビット列$ \overline{M} に変換します。
3. 選択したハッシュ関数を使用して、$ \overline{M} に対応するハッシュ値$ \overline{H} を計算します。
$ \overline{H} = \overline{Hash}(\overline{M} )
ここで、$ \overline{Hash} はビット列の入出力で定義されたハッシュ関数アルゴリズムです。
4. セクション 2.3.1 で指定された変換ルーチンを使用して、$ \overline{H} をオクテット列$ H に変換します。
5. $ Hを出力します。
3.6 鍵導出関数 Key Derivation Functions
このセクションでは、本文書でサポートされる鍵導出関数を規定します。
鍵導出関数は、セクション5で規定される暗号化および鍵転送スキーム、ならびにセクション6で規定される鍵共有スキームで使用されます。
鍵導出関数は、共有秘密オクテット文字列から鍵データを導出するために使用されます。
現在サポートされている鍵導出関数のリストは次のとおりです。
ANSI-X9.63-KDF
IKEv2-KDF
TLS-KDF
NIST-800-56-Concatenation-KDF
鍵導出関数 ANSI-X9.63-KDF は、ANSI X9.63 X9.63 に記述されている単純なハッシュ関数構造である。この鍵導出関数については、セクション 3.6.1 で説明されている。 鍵導出関数 IKEv2-KDF および TLS-KDF は、それぞれ IKEv2 プロトコルおよび TLS プロトコルで使用する楕円曲線 Diffie-Hellman 方式でのみ使用されるものとする。関数 IKEv2-KDF は 2409 および 4306 で規定されている。関数 TLS-KDF は 2246 および 4492 で規定されている。 関数 NIST-800-56-Concatenation-KDF は 800-56A で規定されている。 NIST-800-56-Catenation-KDF を使用する必要があります。ただし、既に他の3つの鍵導出関数のいずれかを使用している実装との後方互換性を保つ場合は除きます。
3.6.1 ANS X9.63 鍵導出関数
鍵データは、ANSI-X9.63-KDF を使用して以下のように計算する必要があります。
セットアップ: セクション3.5に記載されている承認済みハッシュ関数のいずれかを選択します。Hash は選択したハッシュ関数、hashlen は Hash を使用して計算されるハッシュ値の長さ（オクテット単位）、hashmaxlen は Hash を使用してハッシュできるメッセージの最大長（オクテット単位）を表します。
入力: 鍵導出関数への入力は次のとおりです。
1. 共有秘密値であるオクテット列$ Z。
2. 生成する鍵データのオクテット単位の長さである整数 $ keydatalen。
3. (オプション) 共有秘密値$ Z を共有するエンティティ間で共有されるデータで構成されるオクテット文字列$ SharedInfo。
出力: 鍵データ$ K。長さ keydatalen オクテットのオクテット文字列、または「invalid(無効)」。
アクション: 鍵データ$ K を次のように計算します。
1. $ |Z| + |SharedInfo| + 4 < hashmaxlen であることを確認します。$ |Z| + |SharedInfo| + 4 ≥ hashmaxlen の場合は、「invalid(無効)」を出力して終了します。
2. $ keydatalen < hashlen × (2^{32} − 1) であることを確認します。$ keydatalen ≥ hashlen × (2^{32} − 1) の場合は、「invalid(無効)」を出力して終了します。
3. 4オクテット、ビッグエンディアンオクテット列カウンタを$ 00000001_{16}として初期化する。
4. $ i = 1から$ \lceil keydatalen/hashlen\rceilまで、以下を実行する。
4.1. セクション3.5の承認済みハッシュ関数リストから選択したハッシュ関数を使用して、以下の式を計算する。
$ K_i = Hash(Z ‖ Counter ‖ [SharedInfo])
4.2. カウンタをインクリメントする。
4.3. $ iをインクリメントする。
5. $ Kを以下のキーデータ長の左端のオクテットに設定する：
$ K_1 ‖ K_2 ‖ . . . ‖ K_{\lceil keydatalen/hashlene\rceil}
6. $ Kを出力する。
3.7 MACスキーム MAC schemes
このセクションでは、このドキュメントでサポートされるMACスキームを指定する。
MACスキームは、セクション5.1で規定されているECIESによって使用される。
MACスキームは、$ Uがメッセージ$ Mを$ Vに正当な方法で送信し、$ Vが$ Mの正当性を検証したい場合に、送信者Uと受信者Vの2つのエンティティによって使用されるように設計されている。
ここでは、MACスキームをタグ付け操作、タグチェック操作、および関連するセットアップ手順と鍵展開手順の観点から説明する。エンティティ$ Uと$ Vは、通信時に次のようにスキームを使用する必要がある。まず、$ Uと$ Vはセットアップ手順と鍵展開手順を使用して、スキームを使用するオプションを決定し、タグ付け操作とタグチェック操作を制御するための共有秘密鍵Kを作成する必要がある。そして、$ U がメッセージ$ M を$ V に送信するたびに、エンティティ$ U は共有秘密鍵$ K を用いて$ M にタグ付け操作を適用し、$ M 上のタグ$ D を計算し、$ M と$ D を$ V に伝える必要があります。最後に、$ V が$ M と$ D を受信すると、エンティティ$ V は$ K を用いて$ M と$ D にタグチェック操作を適用し、$ M の真正性を検証する必要があります。タグチェック操作で「valid(有効)」が出力された場合、$ V は$ M が真正であると結論付けます。
簡単に言えば、 MAC スキームは、攻撃者が有効なメッセージとタグのペアを偽造することが困難になるように設計されています。言い換えれば、 MAC スキームはデータ発信元の認証とデータの整合性を提供します。
現在サポートされている MAC スキームのリストは次のとおりです。
HMAC–SHA-1–160 with 20 octet or 160 bit keys
HMAC–SHA-1–80 with 20 octet or 160 bit keys
HMAC–SHA-224–112 with 28 octet or 224 bit keys
HMAC–SHA-224–224 with 28 octet or 224 bit keys
HMAC–SHA-256–128 with 32 octet or 256 bit keys
HMAC–SHA-256–256 with 32 octet or 256 bit keys
HMAC–SHA-384–192 with 48 octet or 384 bit keys
HMAC–SHA-384–284 with 48 octet or 384 bit keys
HMAC–SHA-512–256 with 64 octet or 512 bit keys
HMAC–SHA-512–512 with 64 octet or 512 bit keys
CMAC–AES–128
CMAC–AES–192
CMAC–AES–256
これらのMAC方式の最初の2つは、180-1で規定されたハッシュ関数SHA-1に基づいて2104とX9.71で規定されている。残りのHMAC方式は198で導入され、CMAC方式は800-38Bで導入されている。2104で提案されている表記法に従い、ここでHMAC-$ Hash-$ xはハッシュ関数$ Hashと組み合わせて使用されるHMAC関数を示し、長さ$ x/8オクテットまたは$ xビットのメッセージタグを生成する。CMACの場合、表記CMAC-AES-$ xは使用されるブロック暗号がAES-xであることを示す。ここで$ xはビット単位の鍵サイズである。CMAC-AES-$ xのタグ長は常に128ビットである。サポートされているすべてのMAC方式は、選択メッセージ攻撃を実行できる敵対者の存在下では存在的に偽造不可能となるように設計されている。 （この文書は、システム内の他の場所で他のMACスキームを使用すべきではないと示唆するものではなく、ECIESの構築には上記のMACスキームのみを使用すべきであると述べているに過ぎないことに留意してください。） このセクションの残りの部分では、$ Uと$ VによるMACスキームの一般的な操作について説明し、後でこれらのスキームの使用方法を正確に指定できるようにします。セットアップ手順はセクション3.7.1で説明し、鍵展開手順はセクション3.7.2で規定し、タグ付け操作はセクション3.7.3で規定し、タグチェック操作はセクション3.7.4で規定します。
3.7.1 スキームの設定
エンティティ$ Uおよび$ Vは、MACスキームを使用するために、以下の設定手順を実行する必要があります。
1. エンティティ$ Uおよび$ Vは、サポートされているMACスキームのうち、どのスキームを使用するかを決定します（必要に応じて、MACスキームで必要な初期値を選択します）。$ MACは選択されたMACスキーム、$ mackeylenはスキームで使用される鍵のオクテット長、$ maclenはスキームによって生成されるタグのオクテット長を表します。
3.7.2 鍵の展開
エンティティ$ U と$ V は、MAC スキームを使用するために、以下の鍵展開手順を実行する必要があります。
1. エンティティ$ U と$ V は、長さ$ mackeylen オクテットの共有秘密鍵$ K を確立する必要があります。$ K はランダムまたは擬似ランダムに選択する必要があります。
3.7.3 タグ付け操作
エンティティ$ U は、セットアップ手順および鍵展開手順で確立された鍵とパラメータを使用して、$ V に送信するメッセージに以下のタグを付ける必要があります。
入力: タグ付けするデータであるオクテット文字列$ M。
出力: 長さ$ maclen オクテットのオクテット文字列$ D で、$ M のタグ、または「invalid(無効)」です。
アクション: $ M のタグ$ D を以下の手順で計算します。
1. セクション 2.3.2 で指定された変換ルーチンを使用して、$ M をビット列$ \overline{M}に、$ K をビット列$ \overline{K} に変換します。
2. 選択されたMACスキームを用いて、共有秘密鍵$ \overline{K}を用いて$ \overline{M}上のタグ$ \overline{D}を計算する。
$ \overline{D} = MAC_{\overline{K}} (\overline{M} )
MACスキームが「invalid(無効)」を出力した場合、「invalid(無効)」を出力して終了する。
3. セクション2.3.1で指定された変換ルーチンを用いて、$ \overline{D}をオクテット列$ Dに変換する。
4. 長さ$ maclenオクテットのオクテット列$ Dを出力する。
3.7.4 タグ確認操作
エンティティ$ Vは、セットアップ手順および鍵展開手順で確立された鍵とパラメータを用いて、$ Uからのタグ付きメッセージの真正性を以下のように確認する。
入力: タグ確認操作への入力は以下のとおりである。
1. メッセージであるオクテット文字列$ M。
2. $ M上のタグとされるオクテット文字列$ D。
出力: タグ付きメッセージが有効かどうかを示す値（「valid(有効)」または「invalid(無効)」）。
アクション: $ M 上のタグ$ D を以下のようにチェックする:
1. セクション 2.3.2 で指定された変換ルーチンを使用して、$ Mをビット列$ \overline{M} に、$ D をビット列$ \overline{D} に、$ K をビット列$ \overline{K} に変換する。
2. 共有秘密鍵$ \overline{K} を用いて、選択された MAC 方式を使用して$ \overline{M} 上のタグ$ \overline{D′} を計算する:
$ \overline{D′} = MAC_{\overline{K}} (\overline{M} )
MAC 方式が「invalid(無効)」を出力した場合は、「invalid(無効)」を出力して停止する。
3. $ \overline{D′} と$ \overline{D}を比較する。$ \overline{D′} = \overline{D} の場合は「valid(有効)」を出力し、$ \overline{D′} \not= \overline{D} の場合は「invalid(無効)」を出力する。
3.8 対称暗号化方式
このセクションでは、このドキュメントでサポートされる対称暗号化方式を指定します。
対称暗号化方式は、セクション5.1で規定されている楕円曲線統合暗号化方式（ECIES）で使用されます。特に明記されていない限り、ここでの対称暗号化方式の説明はECIESでの使用に適用されるものであり、より一般的なアプリケーションでの使用には必ずしも適用されないことを強調しておきます。特に、ECIESは、メッセージがECIESを使用して暗号化されるたびに新しい対称暗号化鍵が生成されるため、単一の対称暗号化鍵が2つの異なるメッセージを暗号化するために使用されることはありません。
対称暗号化方式は、$ Uがメッセージ$ Mを$ Vに機密扱いで送信し、$ Vが$ Mを復元したい場合に、送信者$ Uと受信者$ Vの2つのエンティティによって使用されるように設計されています。
ここでは、対称暗号化方式を、暗号化操作、復号化操作、および関連するセットアップ手順と鍵展開手順の観点から説明します。エンティティ$ U と $ V は、通信を行う際に、次のように方式を使用する必要があります。まず、$ Uと$ V はセットアップ手順と鍵展開手順を使用して、方式を使用するオプションを決定し、暗号化および復号化操作を制御するための共有秘密鍵 $ K を作成します。次に、$ Uがメッセージ M を$ Vに送信するたびに、$ Uは共有秘密鍵$ Kに基づいて$ Mに暗号化操作を適用し、$ Mの暗号化または暗号文$ Cを計算し、$ Cを$ Vに送信します。最後に、$ Vが$ Cを受信すると、$ Vは$ Kに基づいて$ Cに復号化操作を適用し、メッセージ$ Mを復元します。
簡単に言えば、対称暗号化方式は、攻撃者が暗号文からメッセージを復元することが困難になるように設計されています。言い換えれば、対称暗号化方式はデータの機密性を提供します。
現在サポートされている対称暗号化方式のリストは次のとおりです。
3鍵TDES in CBCモード
XOR暗号化方式
AES–128 in CBCモード
AES–192 in CBCモード
AES–256 in CBCモード
AES–128 in CTRモード
AES–192 in CTRモード
AES–256 in CTRモード
CBCモードのブロック暗号3鍵TDESは、ANS X9.52 X9.52 で規定されている。ここでは、長さ24オクテット（192ビット）の共有秘密鍵を用いることが想定されている。これらの鍵は、左端の8オクテット（64ビット）を$ K_1、中央の8オクテット（64ビット）を$ K_2、右端の8オクテット（64ビット）を$ K_3と解釈し、$ K_1、$ K_2、$ K_3の適切なビットをパリティビットに置き換えることで、3つのサブ鍵$ K_1、$ K_2、$ K_3に分割される。 ブロック暗号AESは197で規定されている。AESのCBCモードとCTRモードは800-38Aで規定されている。 さらに、ここで CBC モードの TDES の 8 オクテットまたは 64 ビットの$ IV は、常に値 $ 00000000_{16} を取る必要があります。さらに、ここで CBC モードの AES の 16 オクテットまたは 128 ビットの$ IV は、常に値 $ 0000000000000000_{16} を取る必要があります。同様に、CTR モードの AES の ICB は、値 $ 0000000000000000_{16} を取る必要があります。ECIES で使用される IV も ICB も、暗号文の一部として送信しないでください。
XOR 暗号化方式は、暗号化がキーとメッセージの XOR で構成され、復号化がキーと暗号文の XOR で構成され、メッセージが復元される単純な暗号化方式です。XOR 方式は、「ワンタイム パッド」として知られる真にランダムなキーで使用されるか、ストリーム暗号の構築コンポーネントとして疑似ランダム キーで使用されることが一般的です。 XOR 暗号化方式では、暗号化するメッセージまたは復号化する暗号文と同じ長さのキーを使用します。
CBCモードの3鍵TDESおよびAESブロック暗号は、選択メッセージ攻撃および選択暗号文攻撃を仕掛ける敵対者の存在下で、意味的セキュリティを提供するように設計されています。XOR暗号化方式は、受動的な攻撃しか仕掛けられない敵対者の存在下で、単一のメッセージを暗号化する際に意味的セキュリティを提供するように設計されています。（これはXOR暗号化方式の一般的な使用を制限しますが、ECIESを構築する目的には十分です。）
上記の要件はECIESに適用されます。システムの他の場所では、他の対称暗号化方式が使用される場合があります。CBCモードの一般的な使用では、IVは予測不可能な値として選択する必要があります。同様に、CTRモードの一般的な使用では、ICBは安全に選択する必要があります。
本規格の残りの部分では、$ Uおよび$ Vによる対称暗号化方式の一般的な動作について説明し、後でこれらの方式の使用を正確に指定できるようにします。セットアップ手順はセクション3.8.1で説明され、鍵展開手順はセクション3.8.2で規定され、暗号化操作はセクション3.8.3で規定され、復号操作はセクション3.8.4で規定されます。
3.8.1 スキームのセットアップ
エンティティ$ Uと$ Vは、対称暗号化スキームを使用するために、以下のセットアップ手順を実行する必要があります。
1. エンティティ$ Uと$ Vは、サポートされている対称暗号化スキームのうち、使用するスキームを決定する必要があります（必要に応じて、暗号化スキームで必要な初期値も選択します）。$ ENCは選択された暗号化スキームを表し、$ enckeylenはスキームで使用される鍵のオクテット単位の長さを表します。
3.8.2 鍵展開
エンティティ$ Uと$ Vは、対称暗号化方式を使用するために、以下の鍵展開手順を実行する必要があります。
1. エンティティ$ Uと$ Vは、長さ$ enckeylenオクテットの共有秘密鍵$ Kを確立する必要があります。
3.8.3 暗号化操作
エンティティ$ Uは、セットアップ手順と鍵展開手順で確立された鍵とパラメータを使用して、エンティティ$ Vに送信するメッセージを以下の通りに暗号化する必要があります。
入力: 暗号化するデータであるオクテット文字列$ M。
出力: $ Mに対応する暗号文であるオクテット文字列$ C、または「invalid(無効)」。
アクション: 暗号文$ Cを以下の通りに計算します。
1. セクション2.3.2で指定された変換ルーチンを使用して、$ Mをビット列$ \overline{M}に変換し、$ Kをビット列$ \overline{K}に変換します。
2. 選択された対称暗号化方式の暗号化操作を使用して、共有秘密鍵$ \overline{K}を用いて$ \overline{M}の暗号化$ \overline{C}を計算します。暗号化操作で「invalid(無効)」が出力された場合は、「invalid(無効)」を出力して操作を終了します。
3. セクション2.3.1で指定された変換ルーチンを使用して、$ \overline{C}をオクテット文字列$ Cに変換します。
4. オクテット文字列$ Cを出力します。
3.8.4 復号操作
エンティティ$ Vは、セットアップ手順および鍵展開手順で確立された鍵とパラメータを使用して、エンティティ$ Uからの暗号文を以下のように復号する。
入力: 暗号文であるオクテット文字列$ Cと対称暗号鍵$ K。
出力: $ Cの復号結果であるオクテット文字列$ M、または「invalid(無効)」。
アクション: $ Cを以下のように復号する。
1. セクション2.3.2で指定された変換ルーチンを使用して、$ Cをビット列$ \overline{C}に、$ Kをビット列$ \overline{K}に変換する。
2. 共有秘密鍵$ \overline{K}を用いて、選択された対称暗号方式の復号操作を使用して、$ \overline{C}の復号結果$ \overline{M}を計算する。復号操作で「invalid(無効)」が出力された場合は、「invalid(無効)」を出力して操作を中止する。
3. セクション2.3.1で指定された変換ルーチンを使用して、$ \overline{M}をオクテット文字列$ Mに変換する。
4. オクテット文字列$ Mを出力する。
3.9 鍵ラップ方式
このサブセクションでは、NIST AES鍵ラップアルゴリズムまたはCMS TDES鍵ラップアルゴリズムのいずれかを、
ラップ鍵転送方式における鍵ラップ方式として使用しなければならないこと、および
既存の対称鍵を別の対称鍵でラップする際に、より一般的に使用すべきことを規定します。
AES鍵ラップアルゴリズムは、Nat01で最初に規定されました。3394でも再規定されています。2007年10月現在、ASC X9もX9.102で追加入力のための若干の拡張を加えて再規定しており、そのアルゴリズムのパブリックレビューを要請していますASC04。 AES鍵ラップアルゴリズムは、AESブロック暗号またはTDESブロック暗号と併用できます。AESブロック暗号を使用して鍵をラップする場合は、AES鍵ラップアルゴリズムを使用する必要があります。ただし、TDESブロック暗号を使用する場合、後方互換性のために、別の鍵ラップアルゴリズムであるCMS TDES鍵ラップアルゴリズムを使用することができます。このアルゴリズムは2630で最初に規定され、X9.102でも再規定されています。 本規格の残りの部分では、$ Uおよび$ Vによる鍵ラップ方式の一般的な操作について説明し、後でこれらの方式の使用を正確に規定できるようにします。セットアップ手順はセクション3.9.1で、鍵配備手順はセクション3.9.2で、ラップ操作はセクション3.9.3で、アンラップ操作はセクション3.9.4で規定されています。
3.9.1 鍵ラップスキームの設定
エンティティ$ Uおよび$ Vは、鍵ラップスキームを使用するために、以下の設定手順を実行する必要があります。
1. エンティティ$ Uおよび$ Vは、サポートされている鍵ラップスキームのうち、どのスキームを使用するかを決定します（必要に応じて、鍵ラップスキームで必要な初期値を選択します）。$ WRAPは選択された暗号化スキームを表し、$ wrapkeylenはスキームで使用される鍵のオクテット単位の長さを表します。
3.9.2 鍵ラップ方式 鍵生成
エンティティ$ Uおよび$ Vは、鍵ラップ方式を使用するために、以下の鍵展開手順を実行する必要があります。
1. エンティティ$ Uおよび$ Vは、長さ$ wrapkeylen オクテットの鍵暗号化鍵$ Kを確立する必要があります。
3.9.3 鍵ラップ方式 ラップ操作
エンティティ$ Uは、セットアップ手順および鍵展開手順中に確立された鍵暗号化鍵および鍵ラップパラメータを使用して、エンティティ$ Vに送信する鍵を以下のとおりラップする必要があります。
入力: 鍵暗号化鍵$ Kおよびラップする鍵であるオクテット文字列$ C。
出力: $ Cに対応するラップされた鍵であるオクテット文字列$ W、または「invalid(無効)」。
アクション: ラップされた鍵$ Wを以下のとおり計算します。
1. セクション2.3.2で指定された変換ルーチンを使用して、$ Cをビット列$ \overline{C}に変換し、$ Kをビット列$ \overline{K}に変換します。
2. 選択された鍵ラップ方式の鍵ラップ演算を用いて、鍵暗号化鍵 $ \overline{K} のもとで、$ \overline{C} のラップ鍵$ \overline{W} を計算する。鍵ラップ演算で「invalid(無効)」が出力された場合は、「invalid(無効)」を出力して終了する。
3. セクション 2.3.1 で指定された変換ルーチンを用いて、$ \overline{W} をオクテット列$ W に変換する。
4. オクテット文字列$ W を出力する。
3.9.4 鍵ラップスキームのアンラップ操作
エンティティ$ V は、セットアップ手順および鍵展開手順中に確立された鍵暗号化鍵および鍵ラップパラメータを使用して、エンティティ$ U からラップされた鍵を以下のようにアンラップする必要があります。
入力: 鍵暗号化鍵$ K と、ラップされた鍵であるオクテット文字列$ W。
出力: $ W のアンラップであるオクテット文字列$ C、または「invalid(無効)」。
アクション: $ Wを以下のようにアンラップします。
1. セクション2.3.2で指定された変換ルーチンを使用して、$ Wをビット列$ \overline{W}に変換し、$ Kをビット列$ \overline{K}に変換する。
2. 選択された鍵ラップ方式のアンラップ操作を用いて、共有鍵暗号化鍵$ \overline{K}の下で$ \overline{W}のアンラップ$ \overline{C}を計算する。アンラップ操作の結果が「invalid(無効)」と出力された場合は、「invalid(無効)」を出力して終了する。
3. セクション2.3.1で指定された変換ルーチンを使用して、$ \overline{C}をオクテット文字列$ Cに変換する。
4. オクテット文字列$ Cを出力する。
3.10 乱数生成
暗号鍵は、攻撃者が秘密鍵を推測できない方法で生成されなければなりません。鍵は乱数生成器を用いて生成されるべきです。
乱数生成器は、ANS X9.82 X9.82 または対応するNIST出版物 800-90 に準拠する必要があります。 完全性を保つため、ここでは1つの乱数生成器（RNG）を指定します。
相互運用性のために、通常、乱数生成器（RNG）仕様への準拠は必須ではありません。しかしながら、鍵の機密性は通常、乱数生成器（RNG）のセキュリティに依存するため、安全な乱数生成器（RNG）仕様への準拠は不可欠です。準拠しない場合、安全でない鍵生成が行われるリスクがあり、実装のセキュリティが損なわれる可能性があります。
3.10.1 エントロピー
乱数生成器（random number generator RNG）は状態を維持します。乱数生成器の出力は状態の関数です。RNGのセキュリティは、その状態がいずれかの値を取る最大確率に依存します。セキュリティレベルが$ tビットの場合、任意の状態値の最大確率は最大でも$ 2^{−t}でなければなりません。一般に、暗号システムのセキュリティレベルは、暗号鍵の導出元となるRNGのセキュリティレベル以下です。
ある確率分布における最大確率が$ 2^{−t}の場合、その分布は最小エントロピーが$ tビットであると言われます。最小エントロピーはシャノンエントロピーを超えることはありません。シャノンエントロピーは、確率分布の異常性のため、一般に暗号における十分なセキュリティを保証するのに十分ではありません。例えば、長さ256ビットのビット列を生成するRNGは、シャノンエントロピーが128ビットである可能性がありますが、最小エントロピーは1ビットしかありません。
2つの異なるRNGが同じ状態と衝突するリスクに対する予防措置として、RNGは重複する可能性が低い値でパーソナライズされるべきです。パーソナライズ値は秘密である必要はありません。800-90, §8.7.1を参照してください。 3.10.2 疑似乱数ビット列の決定論的生成
RNGの出力は、出力から状態を効率的に導出できないように、状態の一方向性変換でなければなりません。いくつかの一方向性関数が利用可能です。
状態は一方向性関数で更新されるべきであり、これにより、過去の状態は将来の侵害された状態から学習できなくなります。この属性は、前方秘匿性またはバックトラッキング耐性と呼ばれることもあります。MQVなど、標準規格の一部の方式は前方秘匿性を提供します。これらの方式のセキュリティ目標が前方秘匿性である場合、使用されるRNGも前方秘匿性を提供する必要があります。
状況によっては、RNGが現在の状態の侵害から回復できることが必須です。このような回復は、新しいエントロピーを注入することによってのみ実現できます。このセキュリティ属性は、回復可能セキュリティまたは予測耐性と呼ばれることもあります。予測耐性は、非常に高いセキュリティレベルのアプリケーションではオプションの属性です。
3.10.2.1 Dual EC RNG
このセクションは、NIST Special Publication 800-90「決定論的ビット生成器を用いた乱数生成に関する勧告」および米国国家規格草案 X9.82 パート3「決定論的乱数ビット生成器のメカニズム」で規定されている「Dual EC DRBG」の再規定を目的としています。NIST SP 800-90 または ANS X9.82 のいずれかに準拠する「Dual EC DRBG」の実装は、この規格にも準拠します。完全性と利便性のため、生成される乱数の主要な側面は、等価な形式で言い換えられ、ここで再規定されます。
Dual EC RNGは、楕円曲線の領域パラメータの集合$ Tと、楕円曲線上の点である追加パラメータ$ Qを使用します。もう1つのパラメータは、点あたりのビット数である$ outlenです。
Dual EC RNGには、以下に示す様々な演算が含まれます。
Dual EC RNGは、整数$ sという秘密状態を保持します。この状態は十分なエントロピーで初期化する必要があり、また、定期的に追加のエントロピーで再シードする必要があります。初期化と再シードについては、現時点ではここでは規定されていません。これらの操作については、「Dual EC DRBG」の他の仕様、例えばNIST SP 800-90やANS X9.82-2を参照してください。
Dual EC RNGにおける2値体上の楕円点は、セクション2.1.2で規定されているように、標準多項式基底表現を用いて表されます。
3.10.2.1.1 出力ブロック これは Dual EC RNG の内部操作です。$ (x_1, y_1) = sP および $ (x_2, y_2) = sQ を計算します。$ x_1 を整数 $ s′ に変換し、これが新しい状態になります。
$ x_2 をビット文字列$ b に変換します。$ b の右端の$ outlen ビットを取り、より短いビット文字列$ r を取得します (左端のビットをいくつか削除します)。楕円曲線が有限体$ \mathbb{F}_{2^m} 上で$ m = 409 として定義されている場合は、$ r の右端のビットを削除します。ビット文字列 $ r が出力ブロックです。
3.10.2.1.2 出力ビット文字列 これは Dual EC RNG の主な外部操作です。$ k ビットのビット文字列を生成するには、合計長さが $ k を超えるまで連続する出力ブロック$ r_0、...、r_j を取得します。ブロックを連結し、左端の$ k ビットを出力します。
3.10.3 ランダムビット列から乱数への変換
楕円曲線秘密鍵は、ある範囲の整数です。完全なセキュリティを確保するには、これらの整数の確率分布は可能な限り均一である必要があります。（そうでなければ、様々な攻撃が可能になる可能性があります。）
前節の決定論的アルゴリズムは、ランダムビット列を生成します。ビット列は整数に変換できますが、その範囲は楕円曲線秘密鍵に必要な範囲と完全に一致しません。
ランダムビット列をランダム整数に変換するには、以下のいずれかの方法を使用できます。この場合、ビット列が均一であれば整数も均一になります。
決定論的乱数生成に関するNIST Special Publication 800-90に記載されている方法 800-90, §B.5.1 のいずれかを使用できます。 以下の代替方法も使用できます。区間$ [1, n − 1] 内の乱数$ k を生成するには、固定長$ m ≥ \lceil \log_2(n − 1)\rceil の乱数ビット列$ B を選択する。$ B を区間$ [0, 2^m − 1] 内の整数$ b に変換する。$ q = \lfloor 2^m/(n − 1)\rfloor とする。$ b < q(n − 1) の場合、$ k = 1 + (b \mod n − 1) とする。$ b ≥ q(n − 1) の場合、別の$ B を選択する。
3.11 セキュリティレベルと保護期間
現在暗号化技術で保護されているデータは、将来も保護が必要になる可能性があります。暗号解読技術の進歩は、少なくとも概算で予測可能です。
現在の概算に基づき、この文書では、2010年以降も保護が必要なデータは、112ビット以上のセキュリティで保護する必要があると規定しています。2030年以降も保護が必要なデータは、128ビット以上のセキュリティで保護する必要があります。
2040年以降も保護が必要なデータは、192ビット以上のセキュリティで保護する必要があります。2080年以降も保護が必要なデータは、256ビット以上のセキュリティで保護する必要があります。
4 署名方式 Signature Schemes
このセクションでは、本文書でサポートされるECCベースの署名方式について規定する。
署名方式は、署名者$ Uと検証者$ Vの2つのエンティティが、$ Uがメッセージ$ Mを真正な方法で送信し、$ Vが$ Mの真正性を検証したい場合に用いるよう設計されている。実際、メッセージが署名されると、$ Uの公開鍵のコピーを持つ任意のエンティティ$ Vが署名を検証できる。特に、検証者は$ Uが元々メッセージを送信したエンティティではない可能性がある。
このような第三者による検証は、否認防止にとって重要である。
ここでは、署名スキームを、署名操作、検証操作、および関連するセットアップ手順と鍵配布手順の観点から説明する。エンティティ$ Uと$ Vは、通信を行う際に、以下のようにスキームを用いるべきである。まず $ U と $ V はセットアップ手順を使用して、どのオプションでスキームを使用するかを確立する必要があります。次に、$ Uは鍵展開手順を使用して鍵ペアを選択し、$ V は $ Uの公開鍵を取得する必要があります。$ Uは鍵ペアを使用して署名操作を制御し、$ V は公開鍵を使用して検証操作を制御します。その後、 $ Uがメッセージ$ M を送信するたびに、エンティティ $ U は鍵ペアを使用して$ Mに署名操作を適用し、$ M の署名 S を取得し、$ Mと$ S から署名されたメッセージを形成し、署名されたメッセージを$ Vに伝えます。最後に、 $ Vが署名されたメッセージを受信すると、エンティティ$ Vは $ U の公開鍵を使用して署名されたメッセージに検証操作を適用し、その信頼性を検証する必要があります。検証操作で「有効」が出力された場合、エンティティ$ Vは署名されたメッセージが確かに本物であると結論付けます。
署名方式には、$ U が$ Vに伝える署名メッセージの形式によって 2 種類あります。1 つは付録付き署名方式で、$ U は$ Mと$ Sの両方を$ Vに伝える必要があります。もう 1 つはメッセージ復元付き署名方式で、$ Mは $ Sから復元できるため、$ U は$ Sのみを $ Vに伝えれば済みます。
簡単に言えば、署名方式は、$ U の秘密鍵を知らない攻撃者が有効な署名メッセージを偽造することが困難になるように設計されています。これにより、署名方式は、データ発信元の認証、データの整合性、および否認防止を提供します。
現時点でサポートされている署名方式は、楕円曲線デジタル署名アルゴリズム (ECDSA) のみです。ECDSA はセクション 4.1 で指定されています。
実装に関する議論、セキュリティに関する議論、および参考文献を含む、このセクションの内容に関する解説については、付録 B を参照してください。
4.1 楕円曲線デジタル署名アルゴリズム Elliptic Curve Digital Signature Algorithm
楕円曲線デジタル署名アルゴリズム（ECDSA）は、ECCに基づく付加的な署名方式です。選択メッセージ攻撃を実行できる攻撃者が存在する場合でも、存在的に偽造不可能となるように設計されています。
ECDSAのセットアップ手順はセクション4.1.1で規定され、鍵配布手順はセクション4.1.2で規定され、署名操作はセクション4.1.3で規定され、検証操作はセクション4.1.4で規定されています。
4.1.1 スキームの設定
エンティティ$ Uおよび$ Vは、ECDSAを使用する準備として、以下の設定手順を実行する必要があります。
1. エンティティ$ Uは、署名生成時にセクション3.5でサポートされているハッシュ関数のうち、どのハッシュ関数を使用するかを設定する必要があります。$ Hashは選択されたハッシュ関数を表し、$ hashlenは$ Hashを用いて生成されたハッシュ値のオクテット単位の長さを表します。
2. エンティティ$ Uは、必要なセキュリティレベルで楕円曲線ドメインパラメータ$ T = (p, a, b, G, n, h)または$ T = (m, f (x), a, b, G, n, h)を設定する必要があります。楕円曲線ドメインパラメータ$ Tは、セクション3.1.1.1で指定されたプリミティブまたはセクション3.1.2.1で指定されたプリミティブを使用して生成する必要があります。エンティティ$ Uは、セクション3.1.1.2またはセクション3.1.2.2で指定された方法のいずれかを使用して、楕円曲線ドメインパラメータ$ Tが有効であることの保証を受け取る必要があります。
3. エンティティ$ V は、ハッシュ関数$ Hash と$ U が確立した楕円曲線ドメインパラメータ$ T を正当な方法で取得する必要があります。
エンティティ$ V は、セクション 3.1.1.2 またはセクション 3.1.2.2 に規定されている方法のいずれかを用いて、楕円曲線ドメインパラメータ$ T が有効であることの保証を受けなければなりません。
4.1.2 鍵の配備
エンティティ$ U と$ V は、ECDSA を使用する準備として、以下の鍵配備手順を実行する必要があります。
1. エンティティ$ U は、署名スキームで使用するために、$ T に関連付けられた楕円曲線鍵ペア$ (d_U , Q_U ) を確立する必要があります。鍵ペアは、セクション 3.2.1 に規定されているプリミティブを使用して生成する必要があります。
2. エンティティ$ V は、$ U が選択した楕円曲線公開鍵$ Q_U を正当な方法で取得する必要があります。
エンティティ$ V は、セクション 3.2.2 に規定されている方法のいずれかを用いて、楕円曲線公開鍵$ Q_U が有効であることの保証を受けなければなりません。
4.1.3 署名操作
エンティティ$ Uは、セットアップ手順および鍵配布手順中に確立された鍵とパラメータを用いて、ECDSAを用いてメッセージに署名しなければならない。手順は以下のとおりである。
入力: 署名操作は、署名対象となるメッセージであるオクテット文字列$ Mを入力とする。
出力: 整数$ rと$ sのペアからなる$ M上の署名$ S = (r, s)、または「invalid(無効)」。
アクション: $ M上に署名$ Sを以下のように生成する。
1. セクション3.2.1で規定された鍵ペア生成プリミティブを用いて、セットアップ手順中に確立された楕円曲線領域パラメータTに関連付けられた、$ R = (x_R, y_R)となる一時楕円曲線鍵ペア$ (k, R)を選択する。
2. セクション2.3.9で規定された変換ルーチンを用いて、体元$ x_Rを整数$ \overline{x_R}に変換する。
3. $ r = \overline{x_R} \mod nとする。$ r = 0、またはオプションで$ r が他の公開検証可能な基準（下記参照）を満たさない場合、ステップ 1 に戻る。
4. セットアップ手順で選択したハッシュ関数を使用して、ハッシュ値を計算する。
$ H = Hash(M)
長さはセクション 3.5 で指定されている$ hashlen オクテット。ハッシュ関数が「invalid(無効)」を出力した場合は、「invalid(無効)」を出力して終了する。
5. 次のように$ H から整数$ eを導出する。
5.1. セクション 2.3.2 で指定された変換ルーチンを使用して、オクテット列$ H をビット列$ \overline{H}に変換する。
5.2. $ \lceil\log_2 n\rceil\ge8(hashlen)の場合は$ \overline{E} = \overline{H}に設定し、$ \lceil\log_2 n\rceil < 8(hashlen) の場合は$ \overline{E} を$ \overline{H} の左端の$ \lceil\log_2 n\rceil ビットに設定する。
5.3. セクション 2.3.1 で指定された変換ルーチンを使用して、ビット列$ \overline{E}をオクテット列$ E に変換する。
5.4. セクション 2.3.8 で指定された変換ルーチンを使用して、オクテット列$ E を整数$ e に変換する。
6. 次を計算する。
$ s = k^{−1}(e + rd_U ) \mod n
$ s = 0 の場合、ステップ 1 に戻る。
7. $ S = (r, s)を出力する。オプションで、$ r から$ R を効率的に復元するために必要な追加情報を出力する（下記参照）。
署名者は、$ (r, s) を$ (r, −s \bmod n) に置き換えることができる。これは等価署名であるためである。
$ r が条件を満たす公開検証可能な基準には、整数$ \overline{x_R} = r + jn (j \in \{0, 1, 2 . . . , h\}) は$ G の倍数の有効な x 座標を表します。h = 1 および h = 2 の推奨曲線 SEC 2 の場合、有効な候補 x 座標の数は通常は 1 つなので、これは意味のないチェックです。 $ R を計算するために必要な追加情報は、圧縮形式または非圧縮形式の点 $ R 自体で構成できます。ただし、$ r は $ x_R に関するかなりの情報を提供するため、$ x_R を決定するために追加情報を提供しなくても十分な場合がよくあります。最悪の場合、$ r から$ x_R を見つけるのに $ \log_2(h + 1) ビットが必要です。いずれの場合も、$ y_R を復元するために必要な情報は、コンパクトさと速度のどちらを優先するかに応じて、1 ビットの形、または$ y_R の完全な値の形を取ることができます。
4.1.4 検証操作
エンティティ$ V は、セットアップ手順および鍵配布手順で確立された鍵とパラメータを用いて、エンティティ$ U からの署名付きメッセージを ECDSA を用いて以下のように検証しなければならない。
入力: 検証操作は、以下のものを入力とする。
1. メッセージであるオクテット文字列 M。
2. エンティティ U の M 上の署名 S = (r, s)。
3. オプション: r から R を効率的に復元するための追加情報 (下記参照)。
出力: $ M 上の署名が有効かどうかを示す値 (「valid(有効)」または「invalid(無効)」)。
アクション: $ M 上の署名$ S を以下のように検証する。
1. $ r と$ s が両方とも区間 $ [1, n − 1] 内の整数でない場合、「invalid(無効)」を出力して停止する。
2. セットアップ手順で確立したハッシュ関数を用いて、ハッシュ値を計算する。
$ H = Hash(M)
長さはセクション3.5で指定される$ hashlenオクテット。ハッシュ関数が「invalid(無効)」を出力した場合は、「invalid(無効)」を出力して終了する。
3. 次のように$ Hから整数$ eを導出する。
3.1. セクション2.3.2で指定された変換ルーチンを用いて、オクテット文字列$ Hをビット文字列$ \overline{H}に変換する。
3.2. $ \lceil\log_2 n\rceil\ge8(hashlen)の場合は$ \overline{E} = \overline{H}とし、$ \lceil\log_2 n\rceil<8(hashlen)の場合は$ \overline{E}を$ \overline{H}の左端の$ \lceil\log_2 n\rceilビットに設定する。
3.3. セクション2.3.1で指定された変換ルーチンを用いて、ビット列$ \overline{E}をオクテット列$ Eに変換する。
3.4. セクション2.3.8で指定された変換ルーチンを用いて、オクテット列$ Eを整数$ eに変換する。
4. 次式を計算する。
$ u_1 = es^{−1} \bmod n かつ $ u_2 = rs^{−1} \bmod n。
5. 次式を計算する。
$ R = (x_R, y_R) = u_1G + u_2Q_U
$ R = \mathcal{O} の場合、「invalid(無効)」を出力して終了する。
6. 2.3.9節で規定された変換ルーチンを用いて、体元$ x_R を整数$ \overline{x_R} に変換する。
7. $ v = \overline{x_R} \bmod n と設定する。
8. $ vと$ rを比較する。$ v = r の場合は「valid(有効)」を出力し、$ v \not= rの場合は「invalid(無効)」を出力する。
$ r から$ Rを効率的に復元するために使用される追加情報のオプション入力は、上記のアクションでは使用されない。しかし、より効率的な検証を実現するために、同等のアクションシーケンスで使用できる。例えば、$ rから$ R を復元する場合、$ sR = eG + rQ_U を検証できる。より一般的には、ある整数$ tを選択し、$ tsR = teG + trQ_Uを検証できる。$ t は、整数$ (ts \bmod n) と$ (tr \bmod n) の両方のサイズが約$ \sqrt{n}になるように選択することができ、これにより検証操作を高速化できる。
4.1.5 代替検証操作
署名者$ U は、$ U自身の秘密鍵を使用する次の操作によって、$ U自身の署名をより効率的に検証できる。
これが役立つ状況としては、CA が自身の証明書を検証する場合が挙げられます。
検証手順はすべて同じですが、ステップ 5 では検証者が代わりに
$ R = (x_R, y_R) = (u_1 + u_2d)G
を計算します。
この方法の利点は、検証者がスカラー乗算を 1 回だけ実行するだけで済むことと、$ Gの倍数を事前に計算しておくことで計算を高速化できることです。
4.1.6 公開鍵復元操作
ECDSA署名 $ (r, s) とECドメインパラメータが与えられれば、一般に、少なくとも少数の選択肢の範囲内で公開鍵$ Q を決定することが可能です。
これは、自己署名署名の生成に有用です。
これは、帯域幅が制限され、公開鍵の送信が不可能な環境でも有用です。エンティティ$ U はエンティティ$ V に署名を送信し、エンティティ$ V は$ Q_U を復元します。エンティティ$ V は、証明書またはディレクトリで公開鍵を検索し、一致する場合、署名を受け入れることができます。あるいは、エンティティ$ U は、証明書から公開鍵を省略する以外は、署名と証明書を一緒に送信することもできます。例えば、ECDSAで署名された長い証明書チェーンでは、公開鍵を省略することで帯域幅を節約できます。
署名から複数の候補となる公開鍵を復元できる可能性があります。署名者はわずかなコストで、候補となる公開鍵のうち1つだけが有効なECDSA署名を生成することができ、検証者はどの公開鍵が正しいかを判断するための追加コストを非常に小さく抑えることができます。
入力: 公開鍵回復操作は、以下の情報を入力として受け取ります。
1. 必要なセキュリティレベルにおける楕円曲線ドメインパラメータ $ T = (p, a, b, G, n, h)または $ T = (m, f (x), a, b, G, n, h)。
2. メッセージ$ M。
3. メッセージ$ M上で有効な ECDSA 署名値$ (r, s)。これは、決定すべき公開鍵に対して有効です。
出力: メッセージ$ M 上で有効な署名$ (r, s) となる楕円曲線公開鍵$ Q 。
アクション: 公開鍵$ Q を以下のように求めます。
1. 0 から$ h までの$ j について、以下を実行します。
1.1. $ x = r + jn とします。
1.2. 整数$ x を、セクション 2.3.7 で指定された変換ルーチンを使用して、長さ$ mlenのオクテット列$ X に変換します。ここで、$ mlen = \lceil(\log_2 p)/8\rceilまたは$ mlen = \lceil m/8\rceil です。
1.3. セクション 2.3.4 で指定された変換ルーチンを使用して、オクテット文字列$ 02_{16}‖X を楕円曲線点$ R に変換します。この変換ルーチンが「invalid(無効)」を出力する場合、手順1をもう一度繰り返します。
1.4. $ nR \not= \mathcal{O}の場合、手順1をもう一度繰り返します。
1.5. ECDSA署名検証の手順2と3を使用して、$ Mから$ eを計算します。
1.6. $ kが1から2までの場合、以下を実行します。
1.6.1. 候補公開鍵を次のように計算します。
$ Q = r^{−1}(sR − eG).
1.6.2. $ Qが正当な公開鍵であることを検証します。(例えば、証明書から$ Qが省略されたために切り捨てられた証明書内の認証局の署名を検証します。) $ Qが認証された場合、処理を中止し、$ Qを出力します。
1.6.3. $ Rを$ -Rに変更します。
2. 「invalid(無効)」を出力します。
4.1.7 自己署名操作
自己署名ECDSA署名は、セクション3.2.4で説明されているように、検証可能な鍵生成に役立ちます。
自己署名ECDSA署名を生成するには、以下の操作を使用できます。
入力: 自己署名操作は、以下の情報を入力として受け取ります。
1. 必要なセキュリティレベルにおける楕円曲線ドメインパラメータ$ T = (p, a, b, G, n, h) または$ T = (m, f (x), a, b, G, n, h)。
2. 自己署名署名に組み込む情報$ I。情報$ I には、署名者のIDを含める必要があります。
出力: 自己署名操作生成により、以下の情報が出力されます。
1. ドメインパラメータ$ T に関連付けられた楕円曲線鍵ペア$ (d, Q)。
2. メッセージ$ M 。これには、情報$ Iのコピーと、公開鍵$ Qによるメッセージ$ M の有効な ECDSA 署名$ (r, s) のコピーが含まれます。$ (r, s) は自身とその他の情報への署名であるため、自己署名署名です。
アクション: 自己署名署名メッセージ$ M と楕円曲線鍵ペアを次のように生成します。
1. 選択した楕円曲線ドメインパラメータに関連付けられた一時鍵ペア$ (k, R) を選択します。
2. ECDSA 署名生成の手順 1、2、3 と同様に、$ Rから$ rを計算します。
3. 区間 $ [1, n − 1] 内のランダムな整数$ sを選択します。
4. $ I と$ (r, s) の両方を含むメッセージ$ Mを作成します。
5. セクション4.1.6の公開鍵復元操作を用いて、入力$ T 、$ M 、および$ (r, s) を用いて公開鍵$ Q を復元する。
6. 秘密鍵$ dを以下のように計算する。
$ d = r^{−1}(sk − e) \bmod n.
別のエンティティ$ Vは、$ Mが与えられた場合、 $ Mから署名$ (r, s)を抽出できる。その後、$ Vは通常の ECDSA 検証操作を用いて署名を検証できる。
署名者が、要求されるセキュリティレベルに必要なエントロピーよりも低いエントロピーを持つ一時的な秘密鍵$ kしか生成できない場合、信頼できる機関は$ I内に追加のエントロピーを提供することができる。信頼できる機関は、情報$ Iが実際に鍵ペアの生成に使用されたことを検証できる。この場合、自己署名された$ Mは、信頼できないエンティティから秘密にしておく必要がある。
5 暗号化および鍵転送方式 Encryption and Key Transport Schemes
このセクションでは、本文書でサポートされるECCに基づく公開鍵暗号化および鍵転送方式について規定します。
公開鍵暗号化方式は、送信者$ Uと受信者$ Vの2つのエンティティが、$ Uがメッセージ$ Mを$ Vに秘密裏に送信し、$ Vが$ Mを復元したい場合に使用するように設計されています。
鍵転送方式は、メッセージ$ Mが暗号鍵（通常は対称鍵）に制限される、公開鍵暗号化方式の特別なクラスです。この制限を除けば、以下で公開鍵暗号化方式について述べるほとんどの内容は、鍵転送方式にも当てはまります。
ここでは、公開鍵暗号化方式を、暗号化操作、復号操作、および関連するセットアップ手順と鍵展開手順の観点から説明します。エンティティ$ Uと$ Vは、通信を行う際に、以下のようにこの方式を使用する必要があります。まず$ U と$ V はセットアップ手順を使用して、どのオプションで方式を使用するかを確立する必要があります。次に、$ Vは鍵展開手順を使用して鍵ペアを選択し、$ Uは$ Vの公開鍵を取得する必要があります。$ Uは$ Vの公開鍵を使用して暗号化手順を制御し、$ Vは鍵ペアを使用して復号化操作を制御します。次に、$ Uがメッセージ$ Mを$ Vに送信するたびに、$ Uは$ Vの公開鍵を使用して$ Mに暗号化操作を適用し、$ Mの暗号化または暗号文$ Cを計算し、 $ Cを$ Vに伝えます。最後に、$ V が$ Cを受信すると、エンティティ$ Vは鍵ペアを使用して$ Cに復号化操作を適用し、メッセージ$ Mを復元する必要があります。
大まかに言えば、公開鍵暗号化方式は、$ Vの秘密鍵を持たない敵対者が暗号文からメッセージを復元することが困難になるように設計されています。そのため、公開鍵暗号化方式はデータの機密性を提供します。
このセクションで指定されている公開鍵暗号化方式は、あらゆる種類のメッセージを暗号化するために使用できます。これらは、鍵データを$ U から$ V に転送するために、または情報データを直接暗号化するために使用できます。この柔軟性により、これらの方式は幅広い暗号システムに適用できます。ただし、大多数のアプリケーションでは、これらの方式を鍵転送に適用し、転送された鍵を対称バルク暗号化方式と組み合わせて情報データを暗号化することが想定されています。これは、公開鍵暗号化方式の従来の使用法です。
サポートされている公開鍵暗号化方式は、楕円曲線統合暗号化方式 (ECIES: Elliptic Curve Integrated Encryption Scheme) と、鍵共有方式と鍵ラップメカニズムを組み合わせた一般的な構成です。最初の ECIES については、セクション 5.1 で規定されています。2 番目の一般的な構成については、セクション 5.2 で規定されています。
実装に関する説明、セキュリティに関する説明、および参考文献を含む、このセクションの内容に関する解説については、付録 B を参照してください。
5.1 楕円曲線統合暗号化方式 Elliptic Curve Integrated Encryption Scheme
楕円曲線統合暗号化方式（ECIES）は、ECCに基づく公開鍵暗号化方式です。選択平文攻撃および選択暗号文攻撃を実行できる攻撃者の存在下でも、意味的に安全であるように設計されています。
ECIESの設定手順はセクション5.1.1で規定され、鍵配備手順はセクション5.1.2で規定され、暗号化操作はセクション5.1.3で規定され、復号操作はセクション5.1.4で規定されています。