English

Diffie-Hellman鍵共有法(DH法)
(Diffie-Hellman Key Agreement Method)

このメモの位置づけ

本書は、 インターネットコミュニティに対してインターネットスタンダードトラックのプロトコルを定義するとともに、 それを改良するための議論や提言を求めるものである。 このプロトコルの標準化状態およびステータスについては、 「Internet Official Protocol Standards」(STD 1)の最新版を参照すること。 このメモの配布に制限はない。

著作権表記

Copyright (C) The Internet Society (1999). All Rights Reserved.

要旨

本書は、ANSI X9F1ワーキンググループによって策定されたANSI X9.42ドラフトに基づく1つの特定のDH法の流儀の1つを標準化する。 DH法は、2者によって「共有された秘密(shared secret)」を共有するために使われる鍵共有アルゴリズムである。 「共有された秘密(shared secret)」を任意の数の鍵とする材料に変換するためのアルゴリズムが提供される。 結果としての鍵とする材料は、対称鍵として使われる。 ここに記述したDH法の流儀では、受信者が証明書を持つことを要求するが、 起点者は、(証明書の中におかれる公開鍵とともに)無期(static)鍵ペア、 もしくは、短期(ephemeral)鍵ペアをもつ可能性がある。

目次

1. 1.はじめに
   1. 1.1. 要件についての用語法
2. 2. 手法の概要
   1. 2.1. 鍵共有
      1. 2.1.1. ZZの生成
      2. 2.1.2. 鍵とする材料(Keying Material)の生成
      3. 2.1.3. KEK算定
      4. 2.1.4. 共通鍵アルゴリズムについての鍵長
      5. 2.1.5. 公開鍵検証
      6. 2.1.6. 例1
      7. 2.1.7. 例2
   2. 2.2. 鍵とパラメータの要件
      1. 2.2.1. グループパラメータ生成
         1. 2.2.1.1. p, qの生成
         2. 2.2.1.2. gの生成
      2. 2.2.2. Group Parameter検証
   3. 2.3. Ephemeral-Staticモード
   4. 2.4. Static-Staticモード
3. 謝辞
4. 参考文献
5. セキュリティについての考慮事項
6. 著者のアドレス
7. 著作権表記全文

1. はじめに English

DiffieとHellmanは、[DH76] において、 「共有された秘密(shared secret)」が盗聴者によって入手できないやり方で、 2者が秘密を共有するための方法を記述している。 この秘密は、 他の(共通鍵)アルゴリズムのための暗号技術的な鍵とする材料に変換することができる。 この過程については、マイナーな流儀が数多く存在している。 本書は、そのような流儀のひとつで、 ANSI X9.42仕様に基づいたものについて記述する。

1.1. 要件についての用語法 English

本書中に現れるキーワード"MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT", "MAY"は、[RFC2119] に記述されているように解釈されるべきものである。

2. 手法の概要 English

DH法は、メッセージの送信者と受信者の両方が鍵ペアをもつことを要求する。 ある者の私有鍵と他者の公開鍵を組み合わせることによって、両者は、 同一の「共有された秘密の数字(shared secret number)」を算定することができる。 この数値は、暗号技術的な鍵とする材料に変換することができる。 その鍵とする材料は、典型的には、 メッセージデータを暗号化するために使われるCEK (content-encryption key：コンテンツ暗号化鍵)を暗号化するためのKEK (key-encryption key：鍵暗号化鍵)として使われる。

2.1. 鍵共有 English

鍵共有過程の最初の段階は、 ZZと呼ばれる「共有された秘密の数字(shared secret number)」を算出することである。 同一の起点者と受信者の公開鍵／秘密鍵のペアが使われた場合、 同一のZZ値が結果となる。 ZZ値は、次に、共有される共通暗号鍵に変換される。 起点者が、無期(static)の私有鍵／公開鍵のペアを採用する場合、 公開ランダム値の導入は、結果としての共通鍵は、 各鍵共有と異なることを確保する。

2.1.1. ZZの生成 English

X9.42は、「共有された秘密(shared secret)」ZZが次のように生成されることを規定する。：

ZZ = g ^ (xb * xa) mod p
    

両者が実際に算出を行うことに注意。：

ZZ = (yb ^ xa)  mod p  = (ya ^ xb)  mod p
    

ここで、^は、べき乗(exponentiation)を表現する。

yaは、主体aの公開鍵； ya = g ^ xa mod p
ybは、主体bの公開鍵； yb = g ^ xb mod p
xaは、主体aの私有鍵
xbは、主体bの私有鍵
pは、大きな素数
qは、大きな素数
g = h^{(p-1)/q} mod p
ここで、hは、h{(p-1)/q} mod p > 1を満たす、1 < h < p-1内の任意の整数。
(gは、位数 q mod pをもつ。すなわち、g^q mod p = 1 if g != 1)
j は、p=qj + 1 となるような大きな数値(鍵とパラメータについてのクライテリアについては、2.2 節を参照。)
    

[CMS] において、受信者の鍵は、 CMS RecipientIdentifierによって識別される。 これは、受信者の証明書を指示する。 送信者の公開鍵は、送信者の証明書を参照することによるか、 公開鍵を中に含めることによって、 OriginatorIdentifierOrKeyフィールドを使って識別される。

2.1.2. 鍵とする材料(Keying Material)の生成 English

X9.42は、 an essentially任意の数の鍵とする材料をZZから生成するためのアルゴリズムを提供する。 我々のアルゴリズムは、いくつかのオプションとしてのフィールドを強制し、 他を省略することによって、そのアルゴリズムから派生している。

KM = H ( ZZ || OtherInfo)
    

Hは、暗号技術的ハッシュ関数SHA-1である [FIPS-180]。 ZZは、 2.1.1節において算出される「共有された秘密の数字(shared secret value)」である。 先のゼロは、 ZZがpと同じオクテットを占めるように確保されなければならない(MUST)。 例えば、pが1024bitである場合、ZZの長さは、128byteである必要がある。 OtherInfoは、次の構造のDER encodingとなる。：

OtherInfo ::= SEQUENCE {
    keyInfo KeySpecificInfo,
    partyAInfo [0] OCTET STRING OPTIONAL,
    suppPubInfo [2] OCTET STRING

}

KeySpecificInfo ::= SEQUENCE {
    algorithm OBJECT IDENTIFIER,
    counter OCTET STRING SIZE (4..4) }
    

このようなASN.1規定は、 EXPLICITタグ付けを使うことに注意。 (ASN.1において、EXPLICITタグ付けは、 IMPLICITが明確に仕様とされていない限り、 暗黙の承認(implicit)である。)

algorithmは、 このKEKとともに使われるCEKラッピングアルゴリズムのASN.1アルゴリズムOIDである。 これは、AlgorithmIdentifierではなく、 単にOBJECT IDENTIFIERであることに注意。 パラメータは、使われない。

counterは、32bitの数字であり、ネットワークバイト順に表現される。 その初期値は、いかなるZZについても1である。 すなわち、バイト列は、00 00 00 01 (hex)であり、 与えられたKEKについて上記の鍵生成関数が走る度に1インクリメントされる。

partyAInfoは、送信者によって提供されたランダムなストリングである。 CMSにおいて、 これが(OCTET STRINGとしてエンコードされた)UserKeyingMaterialフィールドの中のパラメータとして提供された場合、 partyAInfoは、512bitを含まなければならない(MUST)。

suppPubInfoは、生成されたKEKのbit単位の長さであり、 32bitの数字としてネットワークバイト順に表現される。 例：3DESについては、これは、次のバイト列になる。00 00 00 C0

KEKを生成するためには、 1つ以上のKMブロックを(適切にcounterをインクリメントして)十分な材料が生成されるまで生成する。 KM ロックは、左から右に連結される。 すなわち、KM(counter=1) || KM(counter=2)...

この算出における秘密のエントロピーについての唯一の源泉は、 ZZであることに注意。 ZZよりも長いストリングが生成された場合においても、 KEKの有効な鍵空間は、 pとqのパラメータによって提起されるあらゆるセキュリティレベルの考慮事項に加えて、 ZZの大きさによって制限される。 しかし、partyAInfoが各メッセージについて異なる場合、 異なるKEKが各メッセージについて生成される。 partyAInfoは、 Static-Staticモードにおいて使われなければならない(MUST)が、 Ephemeral-Staticモードにおいて現れる可能性がある(MAY)ことに注意。

2.1.3. KEK算定 English

各鍵暗号化アルゴリズムは、特定の鍵長(n)を要求する。 KEKは、KMの左端のn byteを鍵にマップすることによって生成される。 3DESについては、192bitの鍵とする材料を要求するが、 このアルゴリズムは、2回走らなければならない。 (K1', K2', と K3'の最初の32bitを生成するために)counter値を1として1回、 (K3の最後の32bitを生成するために) counter値を2として1回走らせる。 K1', K2', K3'は、次に、3DES鍵K1, K2, K3を生成するために、 パリティ調整される。 RC2-128については、128bitの鍵とする材料を要求するが、 このアルゴリズムは、counter値を1として1回走り、 左から128bitは、直接、RC2鍵に変換される。 同様に、RC2-40については、40bitの鍵とする材料を要求するが、 このアルゴリズムは、counter値を1として1回走り、 左から40bitが鍵として使われる。

2.1.4. 共通鍵アルゴリズムについての鍵長 English

共通鍵暗号アルゴリズムには、次の鍵長のKEKをもったものがある。

3-key 3DES 192bit
RC2-128 128bit
RC2-40 40bit

RC2の実効鍵長は、RC2の実(real)鍵長に等しい。

2.1.5. 公開鍵検証 English

次のアルゴリズムは、 受け取った公開鍵yを検証するために使うことができる(MAY)。

1. yが [2,p-1] の間にあることを検証する。間にない場合、その鍵は、invalidである。
2. y^q mod pを算定する。result == 1である場合、その鍵は、validである。そうでない場合、その鍵は、invalidである。

公開鍵検証の主な目的は、 送信者の鍵ペアについての「小さな部分群攻撃(small subgroup攻撃)[LAW98]」を防ぐことである。 Ephemeral-Staticモードが使われている場合、このチェックは、 必要不可欠ではない。 公開鍵検証の詳細情報について、[P1363]も参照。

この手順は、継続中の特許の対象である可能性があることに注意。

2.1.6. 例1 English

ZZは、20bytes 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13

鍵ラップアルゴリズムは、3DES-EDEラップである。

partyAInfo は、使われない。

したがって、SHA-1の最初の呼び出しに対する入力は、次のとおり。：

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ

30 1d

そして、出力は、20 byte。：

a0 96 61 39 23 76 f7 04 4d 90 52 a3 97 88 32 46 b6 7f 5f 1e

SHA-1 の 2番目の呼び出しへの入力。：

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ
30 1d

そして、出力は、20 byte。：

f6 3e b5 fb 5f 56 d9 b6 a8 34 03 91 c2 d3 45 34 93 2e 11 30

したがって、
K1'=a0 96 61 39 23 76 f7 04
K2'=4d 90 52 a3 97 88 32 46
K3'=b6 7f 5f 1e f6 3e b5 fb

注意： これらの鍵は、パリティ調整されていない。

2.1.7. 例2 English

ZZは、次の20byte。 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13

鍵ラップアルゴリズムは、RC2-128鍵ラップであるので、我々は、 128bit (16bytes)の鍵とする材料を必要とする。

使われたpartyAInfoは、64byteである。

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

したがって、SHA-1への入力は、次のとおり。：

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ
30 61

出力は、20byte。：

48 95 0c 46 e0 53 00 75 40 3c ce 72 88 96 04 e0 3e 7b 5d e9

それゆえ、K=48 95 0c 46 e0 53 00 75 40 3c ce 72 88 96 04 e0となる。

2.2. 鍵とパラメータの要件 English

X9.42は、グループパラメータが、p=jq + 1の形態であることを要求する。 このqは、長さは、mの大きな素数であり、j>=2である。 この形態の素数を生成するためのアルゴリズムは、補遺Aにある。 (FIPS PUB 186-1[FIPS-186] と [X942] にあるアルゴリズムから派生。)

X9.42は、私有鍵xが、[2, (q - 2)] の間にあることを要求する。 xは、この間に、ランダムに生成される必要がある。 yは、g^x mod pを計算することによって算定される。 このメモに準拠するためには、 mの長さは、>=160bitでなければならない(MUST)。 (したがって、qの長さは、 少なくとも160bitでなければならない(MUST)。) DESよりも強い共通鍵暗号が使われた場合、 より大きなmが得策である可能性がある。 pの長さは、最低限、512bitなければならない。

2.2.1. グループパラメータ生成 English

エージェントは、[FIPS-186] と [X942] から派生した次のアルゴリズムを使ってドメインパラメータ(g,p,q)を生成する必要がある(SHOULD)。 このアルゴリズムが使われる場合、生成手順の正しさは、 2.2.2節のアルゴリズムによって、第三者が検証できる。

2.2.1.1. p, qの生成 English

このアルゴリズムは、p, qペアを生成する。 このqの長さは、mであり、pの長さは、Lである。

1. m' = m/160 を代入。'/'は、割り算して切り上げることを表現する。
   すなわち、200/160 = 2。
2. L' = L/160 を代入。
3. N' = L/1024 を代入。
4. SEEDの長さ>= mとなるような任意のbitのストリングSEEDを選択。
5. U = 0 を代入。
6. For i = 0 to m' - 1
   　　U = U + (SHA1[SEED + i] XOR SHA1[(SEED + m' + i)) * 2^(160 * i)
   m=160 について、 これは、[FIPS-186] のアルゴリズムから派生することに注意。
   　　U = SHA1[SEED] XOR SHA1[(SEED+1) mod 2^160 ]
7. U mod (2^m) を計算し、 最上位bit (2^(m-1) bit)と最下位bitを1にすることより、 qを形成する。 論理演算で書けば、 q = U OR 2^(m-1) OR 1となる。
   2^(m-1) < q < 2^mとすることに注意。
8. qが素数であることをテストするために、堅牢な素数判定アルゴリズムを使う。
9. qが素数でない場合、4へ。
10. counter = 0 にする。
11. R = seed + 2*m' + (L' * counter) を代入。
12. V = 0 を代入。
13. For i = 0 to L'-1 do
    　　V = V + SHA1(R + i) * 2^(160 * i)
14. W = V mod 2^L を代入。
15. X = W OR 2^(L-1) を代入。
    0 <= W < 2^(L-1)であり、よってX >= 2^(L-1)であることに注意。
16. p = X - (X mod (2*q)) + 1を代入。
17. p > 2^(L-1) である場合、 pが素数であるかをテストするために「堅牢な素数判定」を使う。
    　　そうでない場合、18 へ。
18. pが素数である場合、p, q, seed, counterを出力し、ストップ。
19. counter = counter + 1を代入。
20. counter < (4096 * N) の場合、8へ。
21. "failure" を出力。

注意：「堅牢な素数判定」とは、テストを通過する非素数の可能性が、 最大でも2^-80となるものである。 [FIPS-186] は、 [X942] のように、適当なアルゴリズムを提供する。

2.2.1.2. gの生成 English

この節は、([FIPS-186] から派生した)gを生成するためのアルゴリズムを提供する。

1. j = (p - 1)/q とする。
2. h = いかなる数値を代入。ここで、1 < h < p - 1であり、かつ、hは、以前に試した、いかなる値とも異なる。
3. g = h^j mod pを代入。
4. g = 1の場合、step 2へ。

2.2.2. グループパラメータ検証 English

[PKIX] におけるDH鍵についてのASN.1は、 要素jと、 グループパラメータが正しく生成されたことを検証するために鍵の受信者によって使われる可能性がある(MAY)validation-Parmsを含む。 2つのチェックが可能である。：

1. p = qj + 1であることを検証する。このことは、パラメータがX9.42パラメータ クライテリアに適合することを実証する。
2. 種(seed)である'seed'について、 [FIPS-186] Appendix 2のp,q生成手順に従っている場合、 'counter' = pgenCounterであるときpが見つかることを検証する。
   これは、「パラメータが、ランダムに選択され、 特別な形態をもたないこと」を実証する。

「エージェントが検証情報を、その証明書において提供するか否か」は、 そのエージェントと、それらのCAとの間におけるローカルなことである。

2.3. Ephemeral-Staticモード English

Ephemeral-Staticモードにおいて、受信者は、 無期(static)(かつcertified)鍵ペアをもつが、送信者は、 各メッセージについて新しい鍵ペアを生成し、 それをoriginatorKey保護を使って送る。 送信者の鍵が各メッセージについて新たに生成される場合、 「共有された秘密(shared secret)」ZZは、同様に、 各メッセージごとに異なり、partyAInfoは、省略できる(MAY)。 それは、めったに同一のペアとなった鍵によって生成された複数のKEKが重複するように働かないからである。 しかし、 同一の短期的(ephemeral)な送信者鍵が複数のメッセージに使われる場合 (例：これは、性能最適化としてキャッシュされる)、 分離したpartyAInfoが各メッセージに使われねばならない(MUST)。 この標準のすべての実装は、 Ephemeral-Staticモードを実装しなければならない(MUST)。

「小さな部分群攻撃(small subgroup 攻撃)」に耐えるために、受信者は、 2.1.5 節に記述されたチェックを行う必要がある(SHOULD)。 相手が、受信者による復号操作の成功／失敗を判定できない場合、 受信者は、このチェックを省略することを選ぶことができる(MAY)。 「小さな部分群攻撃(small subgroup攻撃)」の対象とならない鍵を生成する手法については、 [LL97] も参照。

2.4. Static-Staticモード English

Static-Staticモードにおいて、送信者と受信者の両方は、 無期(static)(かつcertified)な鍵ペアをもつ。 送信者の鍵と受信者の鍵は、それゆえ、 各メッセージについて同一であるので、ZZは、 各メッセージについて同一となる。 それゆえ、partyAInfoは、 異なるメッセージがKEKを使うことを確保するために使われ(かつ、 各メッセージについて異なら)なければならない(MUST)。 実装は、Static-Staticモードを実装することができる(MAY)。

「小さな部分群攻撃(small subgroup 攻撃)」を防ぐために、 起点者と受信者の両方は、 2.1.5 節に記述された検証ステップを行うか、 CAが正しく鍵のvalidityを検証したことを検証する必要がある(SHOULD)。 「小さな部分群攻撃(small subgroup攻撃)」の対象とならない鍵生成の手法については、 [LL97] も参照。

謝辞 English

本書において記述した鍵共有法は、 ANSI X9F1ワーキンググループによって行われた作業に基づいている。 著者は、彼らの支援について感謝したい。

著者は、また、Stephen Henson, Paul Hoffman, Russ Housley, Burt Kaliski, Brian Korver, John Linn, Jim Schaad, Mark Schertler, Peter Yee, Robert Zuccheratoに、 その専門的助言とレヴューについて感謝したい。

参考文献

セキュリティについての考慮事項 English

このシステムにおけるセキュリティのすべては、 私有鍵とする材料の守秘性によって提供される。 送信者もしくは受信者のいずれかの私有鍵が開示された場合、 その鍵を使って送受信されたすべてのメッセージは、 不確かなものとされる。 同様に、私有鍵の喪失は、 その鍵を使って送ったメッセージを読むことができない結果を招く。

Static Diffie-Hellman 鍵は、「小さな部分群攻撃(small subgroup攻撃)」に対して脆弱である。 [LAW98] 実践において、この論点は、 「Static-Staticモードにおける両者」と「Ephemeral-Staticモードにおける受信者」について起きる。 2.3節と2.4節は、 この攻撃に対して保護するための適切な実践を記述する。 あるいは、それらがこの攻撃に対して耐性があるようなやり方で、 鍵を生成することは可能である。 [LL97] 参照。

これらの手法によって提供されるセキュリティレベルは、 いくつかの要因に依存する。

これは、次のものに依存する。

• 対称鍵の長さ(典型的には、長さがl bit のとき、2^lセキュリティレベル)；
• 素数qの大きさ(2^{m/2}セキュリティレベル)；
• 素数pの大きさ(ここで、セキュリティレベルは、準指数関数のbit単位の大きさに従って上がる。)

良い設計原則とは、バランスがとれたシステムをもつことであり、 3つすべてのセキュリティレベルが、およそ同じにする。 与えられたpとqのペアから多くの鍵が派生した場合、 素数については、より高いレベルのものをもつことが賢明であろう。 いずれにせよ、全体のセキュリティは、 3つのレベルの最も低いものによって制限される。

著者のアドレス

Eric Rescorla
RTFM Inc.
30 Newell Road, #16
East Palo Alto, CA 94303

EMail： ekr＠rtfm.com

翻訳者のアドレス

黒川 貴司
情報処理振興事業協会
セキュリティセンター

EMail： t-kuroka＠ipa.go.jp

宮川 寧夫
情報処理振興事業協会
セキュリティセンター

EMail： miyakawa＠ipa.go.jp

著作権表記全文

Copyright (C) The Internet Society (1999). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

謝辞

Funding for the RFC Editor function is currently provided by the Internet Society.