|
ネットワーク WG Request for Comments： 3766 BCP： 86 分類： ベストカレントプラクティス |
H. Orman Purple Streak Dev. P. Hoffman VPN Consortium 2004年4月 |
(準備中)
この文書は、 インターネットの「現時点における最善の実践(ベストカレントプラクティス)」を示すものであり、 改善するために議論と示唆を求めるものです。 このメモの配布に制限はありません。
Copyright (C) The Internet Society (2004). All Rights Reserved.
公開鍵暗号技術を共通鍵を交換するために使うシステムの実装者は、 その公開鍵が事前に決定された一定のレベルの攻撃に耐えるようにする必要があります。 攻撃耐性のレベルは、システムの強度であり、交換される共通鍵は、 少なくともシステム強度要件と同程度に強くなければなりません。 3つの量(システム強度、 共通鍵暗号の強度および公開鍵暗号の強度)は、 あらゆるネットワークプロトコルの利用法について整合しなければなりません。
共通鍵の長さでシステム強度要件を表現することと、 その要件以上の鍵長をもつ暗号を選択することは、 相当に容易ですが、 共通鍵の強度要件に適合する暗号技術的強度をもつ公開鍵を選択することは、 困難です。 本書は、 「共通鍵の強度要件の機能としての共通鍵の長さをどのように決定するか？」を説明します。 様々なアルゴリズムについての大規模攻撃と等価の耐性を見積もるための大まかなルールが、 提供されます。 また、本書は、「基礎になっている大きな整数(モジュライ、 群の大きさ、指数等)の大きさを変化させることは、 どのように鍵交換のためのアルゴリズムを使う時間を変化させるか？」に対応します。
多くの暗号技術やセキュリティについての書籍は、 共通鍵を公衆の中で交換することの必要性とともに、 この目的に使われる多くのアルゴリズムを説明しています。 しかし、 これらの議論で「どのように公開鍵暗号の強度と共通鍵が関連しているか？」を説明しているものは、 ほとんどありません。
これを理解するために、玄関に強い鍵をもつ家を思い描いてください。 玄関のドアの隣に、玄関の鍵を入れた小さな鍵ボックスがあります。 玄関を通じて家に侵入しようとしている潜在的な泥棒は、 2つの選択肢をもちます。 (玄関の鍵を攻撃するか、あるいは、 その鍵を取得するために鍵ボックス上の鍵を攻撃する。) 明らかに、その泥棒は、 その2つの鍵の弱者を攻撃することが好都合です。 この状況における家主は、「2番目の進入口オプション(玄関の鍵を入れる鍵ボックス)を追加することは、 泥棒の仕事を易しくしないようにするために、少なくとも、 玄関の鍵と同等の強度であること」を確認しなければなりません。
公開鍵暗号技術を使って共通鍵を交換するためにシステムを設計する実装者は、 同様な判断をしなければなりません。 「攻撃者は、 ある共通鍵で暗号化されたメッセージの中身を学習しようとしていること」と、 「その共通鍵は、公開鍵暗号技術を使って、 送信者と受信者の間を交換されたこと」と想定します。 その攻撃者は、そのメッセージを復元するために、 2つのオプションをもちます。： 推測の繰り返しによって共通鍵を判定するためにブルートフォースを試みるか、 鍵交換の鍵として使われているプライベート鍵を数学的に判定するかです。 賢い攻撃者は、これらの2つの問題のうち、 易しい方について作業します。
実装者の問題に対する簡潔な回答は、 「その鍵交換システムが常に、 その共通鍵よりも顕著に強いこと」を確認することです。 これは、非常に長い公開鍵を選択することによって、可能です。 このような設計は、通常、良いアイディアではありません。 なぜなら、その鍵交換は、その公開鍵が長くなるにしたがって、 処理時間の観点から、はるかに高価になるからです。 それゆえ、その実装者は、当該共通鍵についての攻撃の困難性を、 当該公開鍵による暗号化についての攻撃の困難性と一致させることを試みなければならなくなります。 この解析は、その鍵交換が、経過時間もしくはCPUの労力の観点から、 ほとんどコストがかからずに、優れたセキュリティで行える場合、 必要不可欠ではありません。 残念ながら、これは、今日、公開鍵による手法については、 該当しません。
3番目の考慮は、当該ユーザの最低限のセキュリティ要件です。 「そのユーザは、CAST-128で暗号化しており、 ブルートフォース攻撃に対して20年の耐性をもつ共通鍵を要求する」と想定します。 彼は、86bitの乱雑なビット列をもつ鍵を選択することによって開始し、 次に160bitのブロックに、 それを「加速」するためにSHA-1のような一方向性関数を使い、 それからCAST-128の鍵として、 その128bitを取る可能性があります。 このような場合において、その鍵交換アルゴリズムは、 86bitの困難性で十分であり、128bitである必要がありません。
その選択手順は、下記のとおり。：
4番目の考慮は、 ユーザの身元を確立するために使われる公開鍵認証手法です。 これは、RSAデジタル署名、もしくは、 DSAデジタル署名である可能性があります。 当該認証手法についての法が十分に大きくない場合、 その通信を信用することについての全体的な基礎は、 くずれる可能性があります。 それゆえ、下記のステップが、追加されます。：
Diffie-Hellman鍵共有法は、群、生成器および指数を使います。 今日のインターネット標準において、群の処理は、 モジュラーmultiplicationに基づいています。 ここで、その群は、multiplicativeな整数の群によって定義されます。 典型的には、素数p = 2q + 1です。 (ここで、qは、素数であり、そのarithmeticは、 modulo pによって行われます。) その生成器(これは、しばしば、単に2である)は、 gによって表現されます。
Diffie-Hellmanにおいて、アリスとボブは、最初に、(公的、 あるいは、私的に)gとpの値について合意します。 アリスは、秘密の大きな乱数(a)を選択し、ボブは、 秘密の大きな乱数(b)を選択します。 アリスは、ボブ宛にg^a mod pであるAを送ります。 ボブは、アリス宛にg^b mod pであるBを送ります。 次に、アリスは、B^a mod pを計算し、 ボブは、A^b mod pを計算します。 これらの2つの数字は等しく、両者は、共通鍵kとして、 単純なこの数字の関数を使います。
「Diffie-Hellman鍵共有は、 多様な種類の群の表現上で実行可能であること」に注意してください。 例えば、有限な領域上に定義された楕円曲線は、 特に、鍵交換を処理するのに効率的なやり方です。 [SCH95]
RSA鍵交換について、 「ボブは、p*qに等しい公開鍵(m)(ここでpとqは、2つの秘密の素数)、 暗号化指数e、復号指数dをもつ」と想定します。 この鍵交換のために、アリスは、ボブ宛にE = k^e mod mを送ります。 ここでkは、交換される秘密の共通鍵です。 ボブは、kをE^d mod mを計算することによって復元し、 両者は、kを彼らの共通鍵として使います。 ボブの暗号化指数eは、極めて小さい(例：17bit)可能性がありますが、 彼の復号指数dは、mがもつのと同量のbit数をもちます。
RSA公開鍵暗号化法は、ブルートフォース推測攻撃に対して、 影響を受けません。 なぜなら、その法(ひいては、その秘密の指数d)は、 少なくとも512bit 以上であり、推測するには、 過剰な可能性があるからです。 Diffie-Hellman鍵交換は、推測に対してもセキュアです。 なぜならば、その指数は、少なくとも、 それらから得られる共通鍵と同じ長さをもつからです。 しかし、両手法は、 その公開鍵の構造を判定する数学的攻撃の影響を受けます。
RSAの法を素因数分解することは、 そのプライベート鍵のセキュリティの完全な侵害に帰結します。 Diffie-Hellmanモジュラー指数関数システムについての離散対数問題を解決することは、 同様に、特定の法を使うすべての鍵交換のセキュリティを破壊します。 本書は、「離散対数問題を解く困難性は、 その法と同じ大きさの数を素因数分解することの困難性と同等である」と想定します。 実際、これは、より多くの演算を要求するので、 若干、難しくなります。 これまでの経験的な証拠に基づくと、困難性の比率は、 少なくとも20倍であり、おそらく64倍にまでなります。 いずれかの問題を解決することは、 当該アルゴリズムの最終段階(行列reductionステップ)において、 大容量のメモリを要求します。 「このメモリ要件が、より大きな整数の問題を解くことにおいて、 制約因子であり続けるか否か？」については、見守る必要があります。 現在、制約因子ではなく、 この問題についてのメモリ要件を緩和する可能性がある並列行列(parallel matrix)アルゴリズムについて、活発な研究がなされています。
NFS (Number Field Sieve) [GOR93] [LEN93] は、今日、離散対数問題を解決するための最善の手法です。 整数nをNFS手法を使って素因数分解するのに必要とされる単純な算術演算の数を見積もるために式は、 下記のとおり。：
L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2))
多くの人々は、 「NFS (Number Field Sieve)のような大きな演算のために必要とされるMIPS年(MY)の数」を検討することを選好します。 このような見積もりのためのL(n)式中の演算は、 1コンピュータ命令です。 経験的な証拠は、 「4もしくは5の命令がピッタリ合致する可能性があること」を示しますが、 これは、重要度の低い要素であり、本書は、この検討については、 1演算／1命令にとどまります。
上記の表現は、 経験的な手段によって見積もることができる2つのパラメータ(kとo(1))をもちます。 我々が関心をもつ範囲の数については、それらの間に、 あまり相違点はありません。
「kは1であり、o(1)は0である」と想定できます。 これは、その表現が(実際の労力の代わりに)関連の労力を見積もるためにのみ使われ、かつ、 「o(1)の項は、 素因数分解される数の範囲において非常に小さい」と想定する場合、 合理的に妥当です。
あるいは、「o(1) は、小さく、概ね定数であり、それゆえ、 その値は、kとすることができるので、 大きな整数を試しに素因数分解することに費やされた労力についての報告からKを見積もる」と想定することができます。
本書は、素因数の重要性の見積もりを得るために、 2番目のアプローチを使います。 下記の計算に基づけば、これは重要度が低いようです。
NFSについての最近の作業におけるサンプル値は、 下記のものを含みます。：
| テスト名 | Number of decimal digits |
bit数 | 労力 (MY) |
|---|---|---|---|
| RSA130 | 130 | 430 | 500 |
| RSA140 | 140 | 460 | 2000 |
| RSA155 | 155 | 512 | 8000 |
| RSA160 | 160 | 528 | 3000 |
これらの素因数分解に要した時間の詳細な測定は、 ほとんどありません。 大部分の素因数分解テストにおいて、 数百あるいは数千のコンピュータが数ヶ月間以上使われましたが、 素因数分解プロジェクトに使われたそれらのサイクルの数や、 CPU種別、速度等の詳細な分類は、通常、報告されません。 しかし、上記のすべての場合において、使われる労力は、 kが1であり、かつ、o(1)が0である場合、 公式L(n)が予測するよりも、はるかに少ないものでした。
(1995年に行われた)同様な労力の見積もりは、 [ODL95] にあります。
「NFS (Number Field Sieve)素因数分解手法について、 実際の演算の数は、予想よりも少ないこと」を示す結果は、 [DL] にあります。
(準備中)
経験的な報告からkについて解くと、「kは、約0.02である」ようです。
これは、「RSAアルゴリズムの『有効な鍵強度』は、
方程式L(n)の元の応用(すなわち、kに1を設定し、
o(1)に0を設定すること)によって実装されるより約5もしくは6bit少ないこと」を意味します。
これらのkの見積もりは、
over the numbers reported in the 表
相当に安定しています。この見積もりは、
ひとつのsignificant digit of k
に制限されます。
なぜなら、これは、現実の不確実性を表すからです。
しかし、追加的なdigitsの影響は、推奨される鍵長に対して、
わずかな変更を与えるに留まります。
RSA130の素因数分解をした人たちは、
約1700MYを使いましたが、彼らは、
「これは、
was unrealistically high for 予想目的」
と感じています。
より多くのメモリを、彼らのマシン上で使うことによって、
彼らは、容易に、その時間を500MYに低減できました。
それゆえ、上表を準備する際に使われた値は、500でした。
しかし、この話は、
in getting an accurate measure of effort
困難性を甘く見ています。
本書は、最も正確な手段として、RSA155の素因数分解について、
報告された労力を採用します。
経験的なデータを試験した結果として、
「L(n) 式は、
with the o(1) term set to 0 and with k set to 0.02 when talking
about factoring numbers in the range of 100 to 200 decimal
digits
使える」ようです。
当該方程式は、下記のようになります。：
L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
To convert L(n) from 単純な数学的命令s to MYs,
divide by 3*10^13。
The 方程式 for the number of MYs,
needed to factor an 整数 n
は、
then reduces to。：
MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
「どの程度の確信を持って、
can この方程式 be used for predicting the difficulty of
factoring わずかにより大きな数
？」
この答えは、
「それは、
a close upper bound
である必要があるが、各素因数分解の労力は、通常、
is marked by some improvement in the アルゴリズムs or
their 実装s that makes the running
time somewhat shorter than the 公式 would indicate」
です。
(準備中)
Diffie-Hellman鍵共有において、2番目の攻撃として、
Pollardのrho手法 [POL78]
があります。
このアルゴリズムは、
大きな数の空間において計算された値の衝突(collision)の発見に依存します。
その成功率は、空間の大きさ平方根に比例します。
Pollardのrho手法に起因して、
the search space in a DH 鍵交換 for the 鍵
(the 指数 in a g^a term),
は、その共通鍵の大きさの2倍大きくなければなりません。
それゆえ、セキュアにK bitの鍵を得るためには、実装は、
少なくとも、2*K bitをもつ指数を使わなければなりません。
詳細については、[ODL99]
を参照してください。
Diffie-Hellman鍵共有が楕円曲線法を使って行われるとき、
NFS法は、役に立ちません。
しかし、collision手法は、なお有効であり、
2*K bitをもつ指数(楕円曲線におけるmultiplierと呼ばれる)についての必要性は、残ります。
計算のために使われた法は、2*K bitsである可能性もあり、これは、
望まれるセキュリティレベル increases past 64 bits
of ブルートフォース攻撃耐性
にしたがって、
モジュラー指数関数手法について必要とされる法より小さくなります。
「どのようにして、
really needed for a discrete logarithm 攻撃 to the number needed
to search the keyspace of a cipher
コンピュータ命令の数を比較できるのか？」
と尋ねられる可能性があります。
その労力を計算する際に、「基本演算(basic
operation)とは何か？」を考慮する必要があります。
DESのような共通鍵暗号化アルゴリズムの鍵空間のブルートフォース探索について、
その基本演算は、
is the time to do a 鍵 setup and the time to do one 暗号化。
discrete logs
について、その基本演算は、モジュラー squaring
です。
これらの2つの演算の比率の対数は、
その2種類の計算間における「正規化要素(normalizing
factor)」として使うことができます。
しかし、非常に大きなモジュライ(16K
bit)についてさえ、この素因数は、
amounts to only a few bits of extra effort。
Robert Silvermanは、「いつ、 512bitより大きいRSAモジュライを素因数分解することが現実的となるか？」という問題を吟味しました。 彼の分析は、論理的な演算の数に基づくのみならず、 この作業を行うための実際のマシンの入手可能性についての期待も含みます。 (本書は、論理的な演算の数にのみ基づきます。) 彼は、「我々は、 非常に大きな数を素因数分解するために十分なマシン、 メモリおよび通信の存在を期待できるか否か？」という問題を吟味しています。
(準備中)
最善の素因数分解手法は、データの関連(ふるい分け)の収集と、
大きな行列についてrow reductionを行う重要な最終段階のために大量の RAM
(Random Access Memory)を必要とします。
そのメモリ要件は、素因数分解される数
(あるいは、
subjected to 離散対数 solution)
の大きさに関連します。
Silverman [SILIEEE99] [SIL00]
は、
「それは、
can be brought to bear on a 単一の問題 in the foreseeable 将来
マシンの数と RAM の量について、実際的な限度がある」
と主張しました。
彼は、1024bitのRSAの法を攻撃する際に、
2つの問題を認識しています。：
ふるい分け分けを行うマシンは、64bitのアドレス空間を必要とし、
「行列row reductionマシン」は、
数テラバイトのメモリを必要とします。
Silvermanは、「ふるい分けに必要とされる170GBのメモリをもつ64bitのマシンは、
ほとんど売られていない」と記しています。
10億近くもの、このようなマシンが、
合理的な期間(1年か2年)において、
そのふるい分けに必要不可欠です。
Silvermanの結論(素因数分解の努力の歴史と、 「ムーアの法則」に基づくもの)は、 「1024bitのRSAモジュライは、 2037年頃まで素因数分解されない」です。 これは、理論的分析が示すよりも、 はるかに長いRSA鍵の寿命を意味します。 彼は、「『どれだけのマシンやメモリモジュールが利用可能か？』についての予想は、 「ムーアの法則」による推定と、 素因数分解の努力についての最近の歴史に基づいて、 大きな確証をもって可能である」と主張します。
現実的な考察を重視する必要がありますが、リスク分析において、
物理的世界は、トレンドグラフが示すよりも予測困難です。
「どの程度の trust to put into the inability of
the コンピュータ産業 to satisfy the voracious
needs of factorers？」
を考慮する際に、人は、
素因数分解の数学よりも複雑な経済的条件について何らかの考察をしなければなりません。
コンピュータメモリについての要求は、予想困難です。
なぜなら、それは、アプリケーションに基づくからです。：
「キラーアプリケーション(killer app)」は、
come along any day and send the メモリ産業 into a frenzy
of sales
可能性があります。
デスクトップコンピュータ上で利用可能なCPUの数は、
机の数に制約される可能性がありますが、
組込みシステムが
account for more CPU sales than デスクトップコンピュータs
可能性が高いです。
組込みシステムは、ネットワーク機能を吸収するので、
「少なくともギガバイト(GB)のメモリをもった何百万も64bit
CPUが我々の環境にあふれること」は、
想像不能なことではありません。
これについての最低線は、 「理論によって予測された鍵長の推奨事項が、 過渡に保守的である可能性があること」ですが、それらは、 本書について我々が使ってきたものです。 このマシンの入手可能性についての疑問は、 現行技術の観点から定期的に再考する必要がある論点のひとつです。
2003年の8月、 専用の「ふるい分けマシン」：TWIRLについての設計についての論点が浮上し [Shamir2003]、これは、本質的に、 1024bitまでの素因数分解についての費用見積もりを変化させました。 多くの高速VLSIコンポーネントを並行して適用することによって、 このようなマシンは、10分間で、512bitの数のふるい分け分けを、 費用が$10Kのハードウェアで実行できる可能性があります。 より大きなバージョンは、1年で、 1024bitの数を$10Mの費用でふるい分けることができます。 この作業は、 「1024bitのRSAモジュライのセキュリティは疑わしい」と結論づけるrow reductionステップについてのアプローチにおけるいくつかの優位性を挙げています。
(準備中)
512bitと1024bitの数を素因数分解するための時間と費用についての見積もりは、
of 約 2 million over what can be achieved with commodity
CPUs of 数年前
速度向上要素に対応します。
この章は、「鍵交換を行うために、当該アルゴリズムを使うのに、 どれだけの時間がかかるか？」を記述します。 繰り返しになりますが、公開鍵の長さを延ばすとき、 共通鍵を交換するために要する増加した時間を考慮することが重要です。 非現実的に長い公開鍵の選択を避けることが重要です。
(準備中)
Diffie-Hellman 鍵共有は、
with a 有限な cyclic 群 G with a 生成器 g and an 指数 x
行われます。
「Pollardのrho法」の章に記したように、その指数は、
最終的な鍵について必要とされるものとして、
2倍のbits数をもちます。
群Gの大きさをpとし、
the 底 2 representation of p
におけるbit数をjとし、指数におけるbit数をKとします。
共有された鍵をもたらす演算を行う際に、生成器は、
一定の能力まで高められました。
これを行うための最も効率的な方法は、有る数を K 回、2 乗し、
multiplying it 数回 along the way
を含みます。各数は、
has j/w コンピュータワードs in it。
ここで、w は、
bits in a コンピュータワード
の数です。
(今日、それは、32 bit あるいは 64 bit です)。
素朴な想定は、「あなたは、j 回の squarings と j/2 回の multiplies
を行う必要があること」です。
幸い、効率的な実装は、より少ないもの
(NB： for the remainder of this section, n represents j/w)
しか必要としません 。
2乗の計算は、
multiplicationほど多くの演算を行う必要がありません。
合理的な見積もりは、
「2乗の計算は、
.6 the number of マシン命令s of a multiply」
かかります。人が
ahead of time with several values of 小さな整数 powers
of the 生成器 g
表を準備する場合、元の式が示唆するように、
約 1/5 足らずの multiplies しか必要でありません。
それゆえ、人は、
約 .8*K multiplies of n-by-n ワード数s
の作業を行う必要があります。さらに、
各 multiply and squaring は、
must be followed by a モジュラー reduction,
そして、良い想定は、
「to do a モジュラー reduction as it is to do an
n-by-n word multiply
は、困難であること」
です。それゆえ、これは、
K reductions for the squarings and .2*K reductions for
the multiplies
を要します。
要するに、
K bitの指数とn wordsの法をもつDiffie-Hellman鍵交換についての総労力は、
約2*K n-by-nワードmultipliesです。
32 bit の CPU について、
less than 約 30 のコンピュータワードs in their representation
を使う整数は、少なくとも、
for an n-by-n ワード multiply
n^2 の命令を要求します。
より大きな数は、Karatsuba 乗算法を使えば、
より少ない時間しかかからず、それらは、
as about n^(1.58) for larger n,
規模拡張しますが、それは、現在の議論について、
無視されています。「64 bit の CPU は、"Karatsuba cross-over"
数を、より多くの bit 数に押し広げること」に注意してください。
基本的結論は、以下のとおりです。：
あなたがDiffie-Hellmanモジュラー指数関数群の大きさを倍にする場合、
あなたは、
quadruple the number of 演算s needed for the 計算。
「たとえ、 あなたがDiffie-Hellman用の楕円曲線(EC)群を使っている場合でも、 法の大きさに対して、計算労力についての比率は、 一定であること」に注意してください。 しかし、同等のセキュリティのために、楕円曲線の場合、 より小さな数を使うことができます。 「誰かが、2048bitの法をDiffie-Hellmanの応用についての適切なセキュリティ手段としてもつモジュラー指数関数群を選択済みであり、 『代わりにEC群を使うことには、 どのような優位性があるか？』を判定することを望んでいる」と想定します。 その計算は、比較的、直線的であり、 あなたがそれを平均と想定する場合、 楕円曲線群において2乗もしくはmultiplicationを行うことは、 モジュラー指数関数群におけるものの約20倍の労力です。 およその見積もりは、「同等のセキュリティの楕円曲線群は、 約200bitの形態をもつ」ということです。 そして、「その時間は、 n-by-n-word演算によって占められる」と想定すれば、 その関連時間は、下記のように計算されます。：
((2048/200)^2)/20 ~= 5
これは、「楕円曲線の実装は、 モジュラー指数関数の実装の5倍早い必要があること」を示します。
(準備中)
「RSA公開鍵は、j bitの法を使い、その素因数は、
are 2 numbers of about j/2 bits each」
と想定します。
暗号化と復号について期待される計算時間は、異なります。
既述のように、我々は、
denote the number of words in the マシン representation
of the 法 by the 記号 n。
大部分のRSAの実装は、暗号化のために小さな指数を使います。
暗号化は、
as few as 16 squarings and 1 multiplication,
n-by-n-word演算を使うことを含む可能性があります。
各演算は、モジュラーreductionを伴わなければならず、それゆえ、
その時間の複雑性は、
約16*(.6 + 1) + 1 + 1 ~= 28 n-by-n-word multipliesです。
RSA復号は、
that has as many bits as the 法, j
指数を使わなければなりません。
しかし、「中華剰余定理(Chinese Remainder
Theorem)」が適用され、すべての計算は、
with a 法 of only n/2 ワードs and an 指数 of only j/2 bits
行えます。
その計算は、2回、行われなければならず、
各素因数について1回ずつです。その労力は、
2*(j/2) (n/2 by n/2) ワード multiplies と同等です。
multiplying numbers with n/2 ワードs
は、
is only 1/4 as difficult as multiplying numbers with
n ワードs
ので、RSA復号についての同等の労力は、
j/4 n-by-n-wordの乗算です。
あなたが、RSAについての法の大きさを倍にする場合、
そのn-by-nの乗算は、4倍、長くなります。
さらに、当該復号時間は、指数の方が大きいので、倍になります。
scaling の全体費用は、
is a factor of 4 for 暗号化,
a factor of 8 for 復号。
これらの数をより現実的にするために、ここに、 本書の発行の数年前時点におけるハードウェア上で動作するいくつかのソフトウェア実装例を掲げます。 その例は、 合理的な実装のおよその見積もりを示すために含めています。 それらは、ベンチマークではありません。 すべてのソフトウェアについていえるように、その性能は、 その問題に対するコードの特化の詳細と、 その特定のハードウェアに依存します。
1024bitのモジュラー指数関数(2048bit RSAの復号側)について非公式に報告された最速時間は、 Itanium 500MHz CPU上で、0.9ms(約450,000 CPUサイクル)です。 これは、「より新しいCPUは、 大きな数の演算についての土台を失っていないこと」を示します。 命令の数は、32bit CPUが256bitのモジュラー指数関数について使う命令よりも少ない数です。
速くないCPUについては、 Diffie-Hellman鍵共有において行われるようなモジュラー指数関数についての下記の2つの表(SSH Communications社のTero Monenenによって計算されたもの)を掲げます。
Celeron 400MHz； GNU Cコンパイラでコンパイルされ、最適化された。 プラットフォーム固有コードの最適化を含む。：
| 群の種別 | 法の大きさ | 指数の大きさ | 時間 |
|---|---|---|---|
| mod | 768 | ~150 | 18msec |
| mod | 1024 | ~160 | 32msec |
| mod | 1536 | ~180 | 82msec |
| ecn | 155 | ~150 | 35msec |
| ecn | 185 | ~200 | 56msec |
この「群の種別(group type)」は、 [RFC2409] からのものであり、 モジュラー指数関数(mod)か楕円曲線(ecn)のいずれかです。 ここのすべてのsizeと、以降の表中の単位は、bitです。
Alpha 500MHz； DigitalのCコンパイラーでコンパイルされ、 最適化された。 プラットフォーム固有コードの最適化はなされていない。：
| 群の種別 | 法の大きさ | 指数の大きさ | 時間 |
|---|---|---|---|
| mod | 768 | ~150 | 12msec |
| mod | 1024 | ~160 | 24msec |
| mod | 1536 | ~180 | 59msec |
| ecn | 155 | ~150 | 20msec |
| ecn | 185 | ~200 | 27msec |
下記の2つの表(computed by Eric Young)は、当初、 「中華剰余定理」を使ったRSA署名演算のためのものでした。 理解し易くするために、そのパラメータは、内部の計算(すなわち、 そのソフトウェアによって使われる法および指数の大きさ)を示すために、 ここに表現しました。
Dual Pentium II-350：
| equiv法size | equiv指数size | equiv時間 |
|---|---|---|
| 256 | 256 | 1.5ms |
| 512 | 512 | 8.6ms |
| 1024 | 1024 | 55.4ms |
| 2048 | 2048 | 387ms |
Alpha 264 600MHz：
| equiv法size | equiv指数size | equiv時間 |
|---|---|---|
| 512 | 512 | 14ms |
指数関数を加速する最近のCPUは、 1024bitの指数関数(1024bit法, 1024bit指数)を約3ms 以下で行えます。
「特定の共通鍵を防護するために、公開鍵は、 どれくらい強くある必要があるか？」を決定するために、あなたは、 最初に、「どれくらいの労力が、 その共通鍵を破るために必要とされるか？」を判断する必要があります。 多くのインターネットセキュリティプロトコルは、 強い共通鍵暗号化のために、TripleDESの利用を要求し、 「AES (Advanced Encryption Standard)は、 これからの数年以内にインターネット上で採用されること」が期待されます。 それゆえ、これらの2つのアルゴリズムが、ここで検討されます。 この章において、描写するために、我々は、暗黙に、 「そのシステムセキュリティ要件は、112bitである」と想定します。 これは、「112bit が推奨されること」を意味するものではありません。 事実、112bitは、おそらく、 あらゆる実践的な目的にも強すぎます。 これは、単に、TripleDESの強度の上限であるので、 描写のために使われました。
TripleDESを破るのに要するMYの数を単純に判断できる場合、 同等の強度の公開鍵の長さを計算することは、簡単です。 残念ながら、ここでの議論は、その場合にあてはまりません。 なぜなら、標準的なCPU上のソフトウェアにおけるDESより速く暗号化するDES専用ハードウェアの例が多くあるからです。 代わりに、人は、 TripleDESを破るシステムについて相当する費用と、 TripleDES鍵を防護している公開鍵を破るシステムについて相当する費用を判定しなければなりません。
1998年に、EEE( Electronic Frontier Foundation)は、 130,000 USドルで、毎秒、約1e11のDES鍵を試験できるDES crackingマシン [GIL98]を構築しました。 (別途、資金が当該マシンの設計に費やされました。) そのマシンの構築者は、「そのマシンは、 うまく最適化されていなかったこと」を完全に認めており、 「おそらく、10倍の金額があれば、 約50倍速いマシンを作ることができること」が見積もられます。 「TripleDES鍵をテストするシステムは、 DES鍵を試験するためのシステムと同じくらいの速さで動作する」と想定することによって、 より最適化することを想定するので、 約1 million USドルで、 毎秒5e12のTripleDES鍵を試験する可能性があります。
あなたの敵が、EFFよりはるかにお金持ちである場合、あなたは、 「敵は、毎秒5e18の鍵を試すに十分な1兆USドルをもっている」と想定することを望む可能性があります。 この極めて高価なシステムを用いて、 TripleDESの2^112鍵の有効な空間の網羅的な探索は、 約1e15秒(約3300万年)を要します。 (「このようなシステムは、 この計算において無償であると見なされている2^60byteのRAM [MH81] も必要とすること」に注意。) これは、無用に保守的な値に見受けられます。 しかし、コンピュータの処理速度が「マーフィーの法則(毎1.5年で倍速となる法則)」に従って高速化し続ける場合、 「約50年以内に、その計算は、 たった1年間で計算される可能性があること」を予想する可能性があります。 描写する目的で、この大富豪に対する50年の耐性は、 アプリケーションの集合についての最低限のセキュリティ要件であると想定します。
112bitの攻撃耐性がシステムセキュリティ要件である場合、 TripleDES用の鍵交換システムは、 同等の困難性をもつ必要があります。 すなわち、その攻撃者が1兆USドルをもつ場合、あなたは、 彼が持ち金のすべてを今日、ハードウェアを買うために費やし、 「彼は、その鍵交換を3300万年以上先に『クラック』することになること」を知ることを望みます。 (明らかに、合理的な攻撃者は、実際に支出するまで、 約45年間待ちます。 なぜなら、攻撃者は、そのとき、 はるかに良いハードウェアを得ることができますが、 すべての攻撃者が平等に、 このように待つことによる恩恵を受けるからです。)
「典型的な数年前のPCのCPUは、500MIP以上を生成でき、 約100 USドルで豊富に買えること」が見積もられています。 それゆえ、あなたは、5MIP/USドル以上を得ます。 繰り返しになりますが、この数は、 およそ毎18ヶ月で倍になります。 1兆USドルあれば、攻撃者は、 その最近のハードウェア上で5e12MIP年のコンピュータ命令を得ることができます。 この数字は、 鍵交換システムを破るために要する費用についての下記の見積もりにおいて使われます。
大富豪の攻撃者が、 「その専用マシンを共通鍵についてのブルートフォース探索に費やしている」のと同時に、 市販のCPUを112bitの鍵についての鍵交換を破るために使おうとしている場合、 その鍵交換システムは、適切に大きな法を使わなければなりません。 「その大金持ちは、毎年、5e12MIPの命令を行う」と想定します。 RSA暗号化、もしくは、 DH鍵交換に使うための法の大きさを見積もるためには、 下記の方程式を使います。：
5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
これをnについて解いて、丸めます。：
n = 10^(625) = 2^(2077)
それゆえ、同様の処理速度と、 NFS (Number Field Sieve：数体ふるい法)の現在の効率を想定すると、 約2100bitのモジュライは、攻撃に対して、 112bitのTripleDES鍵とほぼ同じ耐性をもちます。 これは、「RSA公開鍵暗号化は、 約2,100bitの法を使う必要があること」を示します。 Diffie-Hellman鍵交換について、人は、 顕著により小さなmodulesを使うことができますが、これは、 顕著な相違ではありません。
これを見積もる代替的方法は、「その攻撃者は、 より少ない試行要件」を想定します。： 攻撃者は、その鍵交換を、 その共通鍵に対する一般目的のコンピュータを用いたブルートフォース鍵探索より少ない時間で「クラック」しなければならないのみです。 これは、「リンゴとリンゴ」の比較です。 なぜなら、これは、「その攻撃者は、 彼の労力を意味する計算を行う必要があるのみであり、 個人もしくは国の能力から成るものではない」と想定するからです。 その公開鍵モジュールは、 4.1節中のものよりも長いものとなります。 なぜなら、その共通鍵は、より長期間にわたって、 実行可能になるからです。
「素材のブロックをTripleDESを使って暗号化するためのCPU命令の数は、 300である」と想定します。 112bitのTripleDES鍵を破る見積もられるコンピュータ命令の数は、 下記のとおり。：
300 * 2^112
= 1.6 * 10^(36)
= .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
これをnについて解いて、丸めます。：
n = 10^(734) = 2^(2439)
それゆえ、汎用CPU攻撃について、あなたは、 「約2400bitのモジュライは、 112bitのTripleDES鍵に対する攻撃に対して、 概ね同じ強度をもつ」と想定することができます。 これは、「RSA公開鍵暗号化は、約2,400bitの法を使う必要があり、 Diffie-Hellman鍵交換について、人は、 顕著な相違点無しに顕著により小さな法を使うことができること」を示します。
著者によっては、「NFS (Number Field Sieve)の基礎となっているアルゴリズムは、 永遠に改善し続ける」と想定することがあることに注意してください。 これらの著者は、112bitの共通鍵を50年間にわたって防護するために、 より大きな法(4,000bit以上) を推奨します。 これは、長期的暗号技術的セキュリティの困難性を指摘します。： そのように長期にわたって、 数学と物理学における進歩を予想することは、不可能です。
大富豪が、自身のお金を、今日、 ハードウェアを購入するのに費やすと想定すると、彼は、 どれくらいの大きさの鍵交換を1年間にチェックできるでしょうか？ 彼は、5*e12 MYの命令を行うことができるか、あるいは、
3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
これをnについて解いて、丸めます。：
n = 10^(360) = 2^(1195)
これは、ほぼ、ブルートフォースによって、 80bitの共通鍵を解読するのに要するのと同数の演算です。
それゆえ、信じられないほど裕福な攻撃者に対して1年の守秘要件をもつデータを防護するためには、 80bitの共通鍵を防護する約1,200bitの鍵交換モジュールは、 国家機関がもつ能力に対してさえも安全です。
このロジックをAESに拡張することは、直線的です。 鍵探索について見積もるために、128bitのAESについて、 「少なくとも16bit分TripleDESよりも強く、 約3倍速い」と見なすことができます。 ブルートフォース攻撃のための時間と費用は、 TripleDESについてのものより約2^(16)多く、それゆえ、 「128bitsの強度が要求されるセキュリティ目標である」という仮定のもとでは、 推奨される鍵交換の法の大きさは、約700bit長くなります。
DES crackingのためのハードウェアより相当に効率的な「AESクラッキング」のためのハードウェアを設計できる場合、 (繰り返しになりますが、「その鍵交換の強度は、 ブルートフォースの労力に適合しなければならない」という仮定のもとで、 )その鍵交換を防護するためのモジュライは、小さくできます。 しかし、そのような設計の存在は、 AESの寿命において初期に相当する現在における推測の問題にすぎません。
AES暗号は、128bitから256bitの鍵長をもちます。 「慎重な最低限のセキュリティ要件(ひいては当該鍵交換モジュライ)は、 同様の強度をもつ必要があるか？」これに対する答えは、 「人が『ムーアの法則』が成立し続けることを期待するか否か？」に依存します。 これが継続する場合、ある人は、 128bit鍵は約60年にわたって安全であると予測し、 256bit鍵は、それより先、 いかなる想像可能なセキュリティ要件をはるかに越えて、 もう400年にわたって安全であると予測します。 しかし、このような進歩は、予想するのが困難です。 なぜなら、これは、今日のデバイスの物理的能力を越えており、 今日、未知もしくは非現実的なロジック技術の存在を意味するからです。 量子計算は、その候補ではありますが、今日では、まだ、 その暗号技術への応用可能性について、 根拠のある予測をするには、 あまりに知られていることが少なすぎます。 (これ自体は、次の100年を変えてしまう可能性があります！)
「ムーアの法則」が成立し続けない場合、 新しい計算的なパラダイムが台頭しない場合、 100bit以上の長さの鍵は、 うまく「永遠に」安全である可能性があります。 しかし、「他にも、 新しい計算的なパラダイムの台頭の仮定に基づいた見積もりについて、 話題にあがっていること」に注意してください。 例えば、LenstraとVerheulのwebベースの論文「暗号技術的鍵の長さを選択する(Selecting Cryptographic Key Sizes)」は、本書における分析よりも、 保守的な分析を選択します。
Diffie-Hellmanアルゴリズムは、 数百あるいは数千bitの長さの鍵に帰結しますが、 暗号アルゴリズムは、 それよりも、 はるかに少ないビット数しか必要としません。 「どのように、強度を失うことなく、 長い鍵を短いものにすることができるのでしょうか？」
暗号技術的一方向ハッシュ関数は、このための構築部材であり、 それらが、その共通鍵の各ブロックを引き出すために、 すべてのDiffie-Hellman鍵を使う限り、それらは、 十分な強度をもった鍵を作り出します。
通常の推奨は、 その基礎素材(鍵交換の結果)に適用された良い一方向ハッシュ関数を使い、 その鍵についてのハッシュ結果のサブセットを使うことです。 しかし、望まれる鍵長がそのハッシュ関数の出力よりも大きい場合、 「どのように、この2つを調和させるか？」疑問に思う可能性があります。
さらなる鍵のビット列を得るためのステップは、 下記の要件を充足しなければなりません。：
あらゆる良い暗号技術的ハッシュ関数は、 これらの3要件を充足します。 「ハッシュ関数の出力ビット列の長さは、 規定されていないこと」に注意してください。 なぜなら、非常に短い出力をするハッシュ関数でさえ、 わずかばかりの注意をはらって、 より相関性の無いビット列を作り出すために繰り返される可能性があるからです。
例えば、SHA-1は、160bitを出力します。 160bit以下の攻撃耐性の鍵を得るためには、 SHA (DHkey)は、良い共通鍵を作り出します。
「160bitの攻撃耐性をもつ鍵を望みますが、これは、 192bitの鍵を使う暗号アルゴリズムと共に使われるべきもの」と想定します。 下記のように、SHA-1を繰り返すことができます。：
(準備中)
共通鍵の1bit - 160bit
= K1 = SHA(DHkey | 0x00)
(すなわち、
concatenate a 1 オクテット of value 0x00 to
the right side of the DHkey,
and then ハッシュ)
共通鍵の161bit - 192 bit = K2 =
select_32_bits(SHA(K1 | 0x01))
しかし、「誰かがその暗号について192bitの強度を望む場合、 どうなるか？」そして、その適切な計算は、下記のとおり。
共通鍵の1bit - 160 bit = SHA(0x00 | DHkey)
共通鍵の161bit - 192 bit = select_32_bits(SHA(0x01 | DHkey))
(「上記の記述において、
オクテット全体を連鎖させる代わりに、
単一ビットを連鎖させうことも十分であること」に注意してください。)
重要な相違点は、「2番目の場合において、DH鍵は、
共通鍵の各部分について使われること」です。
これは、「DH鍵のエントロピーは、
同じビット列上におけるハッシュ関数の繰り返しによって失われないこと」を保証します。
効率性の観点からは、 その共通鍵が巨大な量のエントロピーをもたなければならない場合、 おそらく、 小さな出力ブロックをもつ暗号技術的ハッシュ関数を使うよりも、 大きな出力ブロック(192bit以上)をもつものを使うことが最善です。
(SHA-256, SHA-384, SHA-512のように)より長い出力をもつ、 より新しいハッシュアルゴリズムを、 上記の伸長アルゴリズムと同レベルのセキュリティで使うことができます。
本書中に記述された計算には、乱雑な入力を要求するものがあります。 例えば、秘密のDiffie-Hellman指数は、 nの真に乱雑なビット列 (ここで、nは、 当該システムのセキュリティ要件)に基づいて選択されなければなりません。 真に乱雑なビット列の数は、その計算結果の強度を決定するために、 極めて重要です。 真性乱数の利用は、しばしば、見落とされてきました。 そして、多くのセキュリティアプリケーションが、 不十分に乱雑な入力を使うことによって、著しく弱められてきました。 乱数の重要性についての、はるかに完全な記述は、 [ECS] にあります。
この表において、「攻撃者は、 一般目的のコンピュータを使う」、「そのハードウェアは、 2000年に購入された」、「この問題に関連する数学的な知識は、 今日と同様のままである」と想定されています。 これは、「鍵交換に要する時間は、 強度要件の変化に対してどのように変化するか？」を実証する純粋な「リンゴとリンゴ」の比較です。 DSA用の部分群の大きさは、それが当該プロトコルの一部として、 認証をサポートするために使われている場合、含まれています。 当該DSAモジュールは、DHの法ほどは長くなりませんが、 "q"部分群の大きさも関係します。
| 攻撃耐性についてのシステム要件 (bit) |
共通鍵の長さ (bit) |
RSAもしくはDHの法の大きさ (bit) |
DSAの部分群の大きさ (bit) |
|---|---|---|---|
| 70 | 70 | 947 | 129 |
| 80 | 80 | 1228 | 148 |
| 90 | 90 | 1553 | 167 |
| 100 | 100 | 1926 | 186 |
| 150 | 150 | 4575 | 284 |
| 200 | 200 | 8719 | 383 |
| 250 | 250 | 14596 | 482 |
TWIRLマシンが現実のものとなった場合、そして、 素因数分解におけるrow reductionについて、 類似物との比較において優位性がある場合、保守的な見積もりは、 この表のシステムセキュリティの欄から約11bitを引きます。 それゆえ、89bitのセキュリティを得るためには、人は、 約1,900bitのRSAの法を必要とします。
本書において示した方程式や値は、本書の執筆時点において、 一般目的のコンピュータの現状に基づいて、 可能な限り正確であることが意図されています。 完全に正確な予想は不可能であり、ここに示した公式は、 「暗号技術的強度についての実際」の決定的な言明とすることを意図したものではありません。 例えば、本書中の公式を測定する際に使われた経験的結果には、 おそらく、完全には正確でないものがあり、この不正確さは、 見積もりに影響を与えます。 「ここに示された数は、 現実世界の経験とできるだけ異ならないこと」を著者は希望します。
| [DL] |
Dodson, B. and A. K. Lenstra, NFS with four large primes: an explosive experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, (1995) 372-385. |
| [ECS] |
Eastlake, D., Crocker, S. and J. Schiller, 「セキュリティのための乱雑性についての推奨事項 (Randomness Recommendations for Security)」, RFC 1750, 1994年12月. |
| [GIL98] |
Cracking
DES: Secrets of Encryption Research, Wiretap Politics & Chip Design, Electronic Frontier Foundation, John Gilmore (Ed.), 272 pages, 1998年 5月, O'Reilly & Associates; ISBN: 1565925203. |
| [GOR93] |
Gordon, D., "Discrete logarithms in GF(p) using the number field sieve", SIAM Journal on Discrete Mathematics, 6 (1993年), 124-138. |
| [LEN93] |
Lenstra, A. K. and H. W. Lenstra, Jr. (eds), The development of the number field sieve, Lecture Notes in Math, 1554, Springer Verlag, Berlin, 1993年. |
| [MH81] |
Merkle, R.C., and Hellman, M., "On the Security of Multiple Encryption", Communications of the ACM, v. 24 n. 7, 1981年, pp. 465-467. |
| [ODL95] |
RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The Future of Integer Factorization, A. M. Odlyzko. |
| [ODL99] |
A. M. Odlyzko, Discrete logarithms: The past and the future, Designs, Codes, and Cryptography (1999). |
| [POL78] |
J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of Computation, 32 (1978), 918-924. |
| [RFC2409] |
Harkins, D. and D. Carrel, 「IKE：インターネット鍵交換 (The Internet Key Exchange (IKE))」, RFC 2409, 1998年11月. |
| [SCH95] |
R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve Systems, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 31 1995年8月. Springer-Verlag. |
| [SHAMIR03] |
Shamir, Adi and Eran Tromer, "Factoring Large Numbers with the TWIRL Device", Advances in Cryptology - CRYPTO 2003, Springer, Lecture Notes in Computer Science 2729. |
| [SIL00] |
R. D. Silverman, RSA Laboratories Bulletin,
Number 13 - 2000年4月, A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths. |
| [SILIEEE99] |
R. D. Silverman, "The Mythical MIPS Year", IEEE Computer, 1999年8月. |
Hilarie Orman
Purple Streak Development
500 S. Maple Dr.
Salem, UT 84653
EMail： hilarie＠purplestreak.com and ho＠alum.mit.edu
Paul Hoffman
VPN Consortium
127 Segre Place
Santa Cruz, CA 95060 USA
EMail： paul.hoffman＠vpnc.org
(準備中)
独立行政法人 情報処理推進機構
セキュリティセンター
Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.
The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr＠ietf.org.
Funding for the RFC Editor function is currently provided by the Internet Society.