RFC3766 日本語訳
3766 Determining Strengths For Public Keys Used For ExchangingSymmetric Keys. H. Orman, P. Hoffman. April 2004. (Format: TXT=55939 bytes) (Also BCP0086) (Status: BEST CURRENT PRACTICE)
プログラムでの自動翻訳です。
英語原文
Network Working Group H. Orman
Request for Comments: 3766 Purple Streak Dev.
BCP: 86 P. Hoffman
Category: Best Current Practice VPN Consortium
April 2004
Ormanがコメントのために要求するワーキンググループH.をネットワークでつないでください: 3766はStreakデーウを紫色にします。 BCP: 86P.ホフマンカテゴリ: 最も良い現在の練習VPN共同体2004年4月
Determining Strengths For Public Keys Used
For Exchanging Symmetric Keys
対称鍵を交換するのに使用される公開鍵のために強さを測定します。
Status of this Memo
このMemoの状態
This document specifies an Internet Best Current Practices for the Internet Community, and requests discussion and suggestions for improvements. Distribution of this memo is unlimited.
このドキュメントはインターネット共同体、要求議論、および提案のためのインターネットBest Current Practicesを改良に指定します。 このメモの分配は無制限です。
Copyright Notice
版権情報
Copyright (C) The Internet Society (2004). All Rights Reserved.
Copyright(C)インターネット協会(2004)。 All rights reserved。
Abstract
要約
Implementors of systems that use public key cryptography to exchange symmetric keys need to make the public keys resistant to some predetermined level of attack. That level of attack resistance is the strength of the system, and the symmetric keys that are exchanged must be at least as strong as the system strength requirements. The three quantities, system strength, symmetric key strength, and public key strength, must be consistently matched for any network protocol usage.
対称鍵が公開鍵をいくつかに抵抗力があるようにするように必要とする交換に公開鍵暗号を使用するシステムの作成者は攻撃のレベルを予定しました。 そのレベルの攻撃抵抗がシステムの強さであり、交換される対称鍵はシステム強度要件と少なくとも同じくらい強いに違いありません。 どんなネットワーク・プロトコル用法のためにも、一貫して、3つの量(システムの強さ、対称鍵の強さ、および公開鍵の強さ)を合わせなければなりません。
While it is fairly easy to express the system strength requirements in terms of a symmetric key length and to choose a cipher that has a key length equal to or exceeding that requirement, it is harder to choose a public key that has a cryptographic strength meeting a symmetric key strength requirement. This document explains how to determine the length of an asymmetric key as a function of a symmetric key strength requirement. Some rules of thumb for estimating equivalent resistance to large-scale attacks on various algorithms are given. The document also addresses how changing the sizes of the underlying large integers (moduli, group sizes, exponents, and so on) changes the time to use the algorithms for key exchange.
それがかなり対称鍵の長さに関してシステム強度要件を言い表して、キー長を等しくする暗号を選ぶ簡単であるかその要件を超えている間、対称鍵強度要件を満たす暗号の力を持っている公開鍵をより選びにくいです。 このドキュメントで、対称鍵強度要件の機能として非対称のキーの長さを測定する方法がわかります。 様々なアルゴリズムで大規模な攻撃への同等な抵抗を見積もるためのいくつかの経験則を与えます。 また、ドキュメントは基本的な大きい整数(係数、グループサイズ、解説者など)のサイズを変えると主要な交換にアルゴリズムを使用する時間がどう変化するかを記述します。
Orman & Hoffman Best Current Practice [Page 1] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[1ページ]RFC3766
Table of Contents
目次
1. Model of Protecting Symmetric Keys with Public Keys. . . . . . 2
1.1. The key exchange algorithms . . . . . . . . . . . . . . . 4
2. Determining the Effort to Factor . . . . . . . . . . . . . . . 5
2.1. Choosing parameters for the equation. . . . . . . . . . . 6
2.2. Choosing k from empirical reports . . . . . . . . . . . . 7
2.3. Pollard's rho method. . . . . . . . . . . . . . . . . . . 7
2.4. Limits of large memory and many machines. . . . . . . . . 8
2.5. Special purpose machines. . . . . . . . . . . . . . . . . 9
3. Compute Time for the Algorithms. . . . . . . . . . . . . . . . 10
3.1. Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . 10
3.1.1. Diffie-Hellman with elliptic curve groups. . . . . 11
3.2. RSA encryption and decryption . . . . . . . . . . . . . . 11
3.3. Real-world examples . . . . . . . . . . . . . . . . . . . 12
4. Equivalences of Key Sizes. . . . . . . . . . . . . . . . . . . 13
4.1. Key equivalence against special purpose brute force
hardware. . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2. Key equivalence against conventional CPU brute force
attack. . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3. A One Year Attack: 80 bits of strength. . . . . . . . . . 16
4.4. Key equivalence for other ciphers . . . . . . . . . . . . 16
4.5. Hash functions for deriving symmetric keys from public
key algorithms. . . . . . . . . . . . . . . . . . . . . . 17
4.6. Importance of randomness. . . . . . . . . . . . . . . . . 19
5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1. TWIRL Correction. . . . . . . . . . . . . . . . . . . . . 20
6. Security Considerations. . . . . . . . . . . . . . . . . . . . 20
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.1. Informational References. . . . . . . . . . . . . . . . . 20
8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 22
9. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 23
1. 公開鍵で左右対称のキーを保護するモデル。 . . . . . 2 1.1. 主要な交換アルゴリズム. . . . . . . . . . . . . . . 4 2。 要素. . . . . . . . . . . . . . . 5 2.1への努力を決定します。 方程式のためのパラメタを選びます。 . . . . . . . . . . 6 2.2. 実証的なレポート. . . . . . . . . . . . 7 2.3からのkを選びます。 Pollardρの方法。 . . . . . . . . . . . . . . . . . . 7 2.4. 大きいメモリと多くのマシンの限界。 . . . . . . . . 8 2.5. 専用マシン。 . . . . . . . . . . . . . . . . 9 3. 計算してください。アルゴリズムのための時間… 10 3.1。 ディフィー-ヘルマンの主要なExchange. . . . . . . . . . . . . . . 10 3.1.1。 楕円曲線をもっているディフィー-ヘルマンは分類します。 . . . . 11 3.2. RSA暗号化と復号化. . . . . . . . . . . . . . 11 3.3。 本当の世界例. . . . . . . . . . . . . . . . . . . 12 4。 主要なサイズの等価性。 . . . . . . . . . . . . . . . . . . 13 4.1. 目的の特別な馬鹿力ハードウェアに対する主要な等価性。 . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2. 従来のCPU総当たり攻撃に対する主要な等価性。 . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3. A Oneの年の攻撃: 強さの80ビット。 . . . . . . . . . 16 4.4. 他の暗号. . . . . . . . . . . . 16 4.5のための主要な等価性。 公開鍵アルゴリズムから対称鍵を得るためのハッシュ関数… 17 4.6。 偶発性の重要性。 . . . . . . . . . . . . . . . . 19 5. 結論. . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.1。 修正を振り回してください。 . . . . . . . . . . . . . . . . . . . . 20 6. セキュリティ問題。 . . . . . . . . . . . . . . . . . . . 20 7. 参照. . . . . . . . . . . . . . . . . . . . . . . . . . 20 7.1。 情報の参照。 . . . . . . . . . . . . . . . . 20 8. 作者のアドレス. . . . . . . . . . . . . . . . . . . . . . 22 9。 完全な著作権宣言文. . . . . . . . . . . . . . . . . . . 23
1. Model of Protecting Symmetric Keys with Public Keys
1. 公開鍵で左右対称のキーを保護するモデル
Many books on cryptography and security explain the need to exchange symmetric keys in public as well as the many algorithms that are used for this purpose. However, few of these discussions explain how the strengths of the public keys and the symmetric keys are related.
暗号とセキュリティに関する多くの本で、このために使用される多くのアルゴリズムと同様に公然と対称鍵を交換する必要性がわかります。 しかしながら、これらの議論のわずかで、公開鍵の強さと対称鍵がどう関係づけられるかがわかります。
To understand this, picture a house with a strong lock on the front door. Next to the front door is a small lockbox that contains the key to the front door. A would-be burglar who wants to break into the house through the front door has two options: attack the lock on the front door, or attack the lock on the lockbox in order to retrieve the key. Clearly, the burglar is better off attacking the weaker of the two locks. The homeowner in this situation must make
これを理解するには、正面玄関の上に強い錠がある状態で、家について描写してください。 正面玄関の横に、玄関の鍵を入れてある小さいロックボックスがあります。 正面玄関を通して家に侵入したがっているひとりよがりの強盗は2つのオプションを持っています: 正面玄関の上の錠を攻撃するか、またはキーを検索するためにロックボックスの上で錠を攻撃してください。 明確に、強盗は2個の錠について、より弱いのを攻撃しているほうがよいです。 状況が作らなければならないこれのマイホーム所有者
Orman & Hoffman Best Current Practice [Page 2] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[2ページ]RFC3766
sure that adding the second entry option (the lockbox containing the front door key) is at least as strong as the lock on the front door, in order not to make the burglar's job easier.
強盗の仕事をより簡単にしない命令における正面玄関で2番目のエントリーオプション(正面玄関キーを入れてあるロックボックス)を加えるのが錠と少なくとも同じくらい強いのを確信しています。
An implementor designing a system for exchanging symmetric keys using public key cryptography must make a similar decision. Assume that an attacker wants to learn the contents of a message that is encrypted with a symmetric key, and that the symmetric key was exchanged between the sender and recipient using public key cryptography. The attacker has two options to recover the message: a brute-force attempt to determine the symmetric key by repeated guessing, or mathematical determination of the private key used as the key exchange key. A smart attacker will work on the easier of these two problems.
公開鍵暗号を使用することで対称鍵を交換するシステムを設計する作成者は同様の決定をしなければなりません。 攻撃者が対称鍵でコード化されるメッセージのコンテンツを学びたがっていて、対称鍵が送付者と受取人の間で公開鍵暗号を使用することで交換されたと仮定してください。 攻撃者には、メッセージを回復するために、2つのオプションがあります: 繰り返された推測で対称鍵を決定する馬鹿力試み、または主要な交換キーとして使用される秘密鍵の数学の決断。 賢い攻撃者はこれらの2つの問題について、より簡単に働くでしょう。
A simple-minded answer to the implementor's problem is to be sure that the key exchange system is always significantly stronger than the symmetric key; this can be done by choosing a very long public key. Such a design is usually not a good idea because the key exchanges become much more expensive in terms of processing time as the length of the public keys go up. Thus, the implementor is faced with the task of trying to match the difficulty of an attack on the symmetric key with the difficulty of an attack on the public key encryption. This analysis is not necessary if the key exchange can be performed with extreme security for almost no cost in terms of elapsed time or CPU effort; unfortunately, this is not the case for public key methods today.
作成者の問題の純真な答えはいかにも、主要な交換システムが対称鍵よりかなりいつも強いということです。 非常に長い公開鍵を選ぶことによって、これができます。 公開鍵の長さが上がるのに応じて主要な交換が処理時間に関してはるかに高価になるので、通常、そのようなデザインは名案ではありません。 したがって、作成者は公開鍵暗号化に対する攻撃の困難に対称鍵に対する攻撃の困難を合わせようとするタスクに直面しています。 ほとんどどんな費用でも極端なセキュリティで経過時間かCPUの努力で主要な交換を実行できないなら、この分析は必要ではありません。 残念ながら、今日、これは公開鍵方法のためのそうではありません。
A third consideration is the minimum security requirement of the user. Assume the user is encrypting with CAST-128 and requires a symmetric key with a resistance time against brute-force attack of 20 years. He might start off by choosing a key with 86 random bits, and then use a one-way function such as SHA-1 to "boost" that to a block of 160 bits, and then take 128 of those bits as the key for CAST-128. In such a case, the key exchange algorithm need only match the difficulty of 86 bits, not 128 bits.
3番目の考慮はユーザの最小のセキュリティ要件です。 ユーザがキャスト-128があるコード化であり、20年の全数探索法に対して抵抗時間がある対称鍵を必要とすると仮定してください。 彼は、無作為の86ビットでキーを選ぶことによって始めて、次に、160ビットのブロックにそれを「上げ」て、次に、キーとしてキャスト-128にそれらの128ビット取るのにSHA-1などの一方向関数を使用するかもしれません。 このような場合には、主要な交換アルゴリズムは128ビットではなく、86ビットの困難に合うだけでよいです。
The selection procedure is:
選択手順は以下の通りです。
1. Determine the attack resistance necessary to satisfy the security
requirements of the application. Do this by estimating the
minimum number of computer operations that the attacker will be
forced to do in order to compromise the security of the system and
then take the logarithm base two of that number. Call that
logarithm value "n".
1. アプリケーションのセキュリティ要件を満たすのに必要な攻撃抵抗を決定してください。 攻撃者がシステムのセキュリティで妥協して、次に、その数の対数ベースtwoを取るためにやむを得ずするコンピュータ操作の最小の数を見積もっていることによって、これをしてください。 対数値「n」にそれに電話をしてください。
Orman & Hoffman Best Current Practice [Page 3] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[3ページ]RFC3766
A 1996 report recommended 90 bits as a good all-around choice for
system security. The 90 bit number should be increased by about
2/3 bit/year, or about 96 bits in 2005.
1996年のレポートはシステムセキュリティのための良い統合的な選択として90ビットを推薦しました。 90ビットの数は2005年におよそ2/3ビット/年、またはおよそ96ビットによって増加させられるべきです。
2. Choose a symmetric cipher that has a key with at least n bits and
at least that much cryptanalytic strength.
2. 少なくともnビットと少なくともそれだけがあるキーが強さをcryptanalyticする左右対称の暗号を選んでください。
3. Choose a key exchange algorithm with a resistance to attack of at
least n bits.
3. 少なくともnビットの攻撃への抵抗がある主要な交換アルゴリズムを選んでください。
A fourth consideration might be the public key authentication method used to establish the identity of a user. This might be an RSA digital signature or a DSA digital signature. If the modulus for the authentication method isn't large enough, then the entire basis for trusting the communication might fall apart. The following step is thus added:
4番目の考慮はユーザのアイデンティティを証明するのに使用される公開鍵認証方法であるかもしれません。 これは、RSAデジタル署名かDSAデジタル署名であるかもしれません。 係数が認証方法のために十分大きくないなら、コミュニケーションを信じる全体の基礎はバラバラに壊れるかもしれません。 以下のステップはこのようにして加えられます:
4. Choose an authentication algorithm with a resistance to attack of
at least n bits. This ensures that a similar key exchanged cannot
be forged between the two parties during the secrecy lifetime of
the encrypted material. This may not be strictly necessary if the
authentication keys are changed frequently and they have a well-
understood usage lifetime, but in lieu of this, the n bit guidance
is sound.
4. 少なくともnビットの攻撃への抵抗がある認証アルゴリズムを選んでください。 これは、コード化された材料の秘密主義生涯2回のパーティーの間で交換された同様のキーを鍛造できないのを確実にします。 頻繁に認証キーを変えて、それらによく理解されている用法寿命があるなら、これは厳密に必要でないかもしれませんが、これの代わりに、nビットの指導は健全です。
1.1. The key exchange algorithms
1.1. 主要な交換アルゴリズム
The Diffie-Hellman method uses a group, a generator, and exponents. In today's Internet standards, the group operation is based on modular multiplication. Here, the group is defined by the multiplicative group of an integer, typically a prime p = 2q + 1, where q is a prime, and the arithmetic is done modulo p; the generator (which is often simply 2) is denoted by g.
ディフィー-ヘルマン方法はグループ、ジェネレータ、および解説者を使用します。 今日のインターネット標準では、グループ操作はモジュールの乗法に基づいています。 ここで、整数、通常主要なp=2q+1の乗法群はグループを定義します、そして、法pを演算にします。そこでは、qが主要です。 ジェネレータ(単にしばしば2である)はgで指示されます。
In Diffie-Hellman, Alice and Bob first agree (in public or in private) on the values for g and p. Alice chooses a secret large random integer (a), and Bob chooses a secret random large integer (b). Alice sends Bob A, which is g^a mod p; Bob sends Alice B, which is g^b mod p. Next, Alice computes B^a mod p, and Bob computes A^b mod p. These two numbers are equal, and the participants use a simple function of this number as the symmetric key k.
ディフィー-ヘルマンでは、アリスとボブは最初に、gとpのために値で同意します(公然とか内緒で)。 アリスは秘密の大きい無作為の整数(a)を選びます、そして、ボブは秘密の無作為の大きい整数(b)を選びます。 アリスはボブAを送ります。(ボブは、g^aモッズpです)。 ボブはアリスBを送ります。(彼女はg^bモッズpです)。 次に、アリスはB^aモッズpを計算します、そして、ボブはA^bモッズpを計算します。 これらの2つの番号が等しいです、そして、関係者は対称鍵kとしてこの数の簡単な関数を使用します。
Note that Diffie-Hellman key exchange can be done over different kinds of group representations. For instance, elliptic curves defined over finite fields are a particularly efficient way to compute the key exchange [SCH95].
ディフィー-ヘルマンの主要な交換が異種の集団代表制の上にできることに注意してください。 例えば、有限分野の上で定義された楕円曲線は主要な交換[SCH95]を計算する特に効率的な方法です。
Orman & Hoffman Best Current Practice [Page 4] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[4ページ]RFC3766
For RSA key exchange, assume that Bob has a public key (m) which is equal to p*q, where p and q are two secret prime numbers, and an encryption exponent e, and a decryption exponent d. For the key exchange, Alice sends Bob E = k^e mod m, where k is the secret symmetric key being exchanged. Bob recovers k by computing E^d mod m, and the two parties use k as their symmetric key. While Bob's encryption exponent e can be quite small (e.g., 17 bits), his decryption exponent d will have as many bits in it as m does.
RSAの主要な交換には、ボブにpとqが2つの秘密の素数と、暗号化解説者eと、復号化解説者dであるp*qと等しい公開鍵(m)があると仮定してください。 主要な交換のために、アリスはk^eモッズボブE=mを送ります、kが交換される秘密の対称鍵であるところで。 ボブはE^dモッズmを計算することによって、kを回復します、そして、2回のパーティーが彼らの対称鍵としてkを使用します。 ボブの暗号化解説者eがかなり小さい場合がある間(例えば、17ビット)、彼の復号化解説者dには、それのmと同じくらい多くのビットがあるでしょう。
2. Determining the Effort to Factor
2. 因数分解する努力を決定します。
The RSA public key encryption method is immune to brute force guessing attacks because the modulus (and thus, the secret exponent d) will have at least 512 bits, and that is too many possibilities to guess. The Diffie-Hellman exchange is also secure against guessing because the exponents will have at least twice as many bits as the symmetric keys that will be derived from them. However, both methods are susceptible to mathematical attacks that determine the structure of the public keys.
RSA公開鍵暗号化方法は係数(そして、その結果、秘密の解説者d)には少なくとも512ビットがあるので攻撃を推測する推測するあまりに多くの可能性である獣の力に免疫です。 また、ディフィー-ヘルマンの交換も、解説者には少なくともそれらから得られる対称鍵の2倍のビットがあるので推測しないように安全です。 しかしながら、両方の方法は公開鍵の構造を決定する数学の攻撃に影響されやすいです。
Factoring an RSA modulus will result in complete compromise of the security of the private key. Solving the discrete logarithm problem for a Diffie-Hellman modular exponentiation system will similarly destroy the security of all key exchanges using the particular modulus. This document assumes that the difficulty of solving the discrete logarithm problem is equivalent to the difficulty of factoring numbers that are the same size as the modulus. In fact, it is slightly harder because it requires more operations; based on empirical evidence so far, the ratio of difficulty is at least 20, possibly as high as 64. Solving either problem requires a great deal of memory for the last stage of the algorithm, the matrix reduction step. Whether or not this memory requirement will continue to be the limiting factor in solving larger integer problems remains to be seen. At the current time it is not, and there is active research into parallel matrix algorithms that might mitigate the memory requirements for this problem.
RSA係数を因数分解すると、秘密鍵のセキュリティの完全な妥協はもたらされるでしょう。 ディフィー-ヘルマンのモジュールの羃法システムのための離散対数問題を解決すると、すべての主要な交換のセキュリティは、特定の係数を使用することで同様に煙滅するでしょう。 このドキュメントは、離散対数問題を解決するという困難が係数と同じサイズである数を因数分解するという困難に同等であると仮定します。 事実上、それは、より多くの操作を必要とするので、わずかに困難です。 今までのところの実証的証拠に基づいて、困難の比率は64とことによると同じくらい上に少なくとも20です。 どちらの問題も解決するのはアルゴリズムの最後のステージ、マトリクス減少ステップのための多くのメモリを必要とします。 このメモリ要件が、より大きい整数問題を解決することにおいてずっと限定因子であるかどうかがまだ不明です。 現在の時間に、それはそうではありません、そして、この問題のためのメモリ要件を緩和するかもしれない平行なマトリクスアルゴリズムの活発な研究があります。
The number field sieve (NFS) [GOR93] [LEN93] is the best method today for solving the discrete logarithm problem. The formula for estimating the number of simple arithmetic operations needed to factor an integer, n, using the NFS method is:
ナンバーフィールドふるい(NFS)[GOR93][LEN93]は、離散対数問題を解決するための今日の最も良い方法です。 簡単な四則演算の数が、整数を因数分解する必要だったと見積もるための公式、n、NFS方法を使用するのは、以下の通りです。
L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2))
L(n)はk*e^と等しいです。(1.92+o(1))*cubrt、(ln(n)*(ln(ln(n)))^2))
Many people prefer to discuss the number of MIPS years (MYs) that are needed for large operations such as the number field sieve. For such an estimation, an operation in the L(n) formula is one computer
多くの人々が、ナンバーフィールドふるいなどの大きい操作に必要であるMIPS何年もの(MYs)の数について議論するのを好みます。 そのような見積りのために、L(n)公式における操作は1台のコンピュータです。
Orman & Hoffman Best Current Practice [Page 5] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[5ページ]RFC3766
instruction. Empirical evidence indicates that 4 or 5 instructions might be a closer match, but this is a minor factor and this document sticks with one operation/one instruction for this discussion.
指示。 これはさ細な要素です、そして、実証的証拠は、4か5つの指示が、より近いマッチであるかもしれないことを示しますが、このドキュメントはこの議論のための1つ操作/1の指示に忠実です。
2.1. Choosing parameters for the equation
2.1. 方程式のためのパラメタを選びます。
The expression above has two parameters that can be estimated by empirical means: k and o(1). For the range of numbers we are interested in, there is little distinction between them.
上の表現には、実証的な手段で見積もることができる2つのパラメタがあります: kとo(1)。 私たちが興味を持っている数の範囲には、それらの間には、区別がほとんどありません。
One could assume that k is 1 and o(1) is 0. This is reasonably valid if the expression is only used for estimating relative effort (instead of actual effort) and one assumes that the o(1) term is very small over the range of the numbers that are to be factored.
人はkが1であり、o(1)が0であると仮定できました。 表現が相対的な努力(実際の努力の代わりに)と人が、o(1)用語が因数分解されることになっている数の範囲で非常に小さいと仮定すると見積もるのに使用されるだけであるなら、これはかなり有効です。
Or, one could assume that o(1) is small and roughly constant and thus its value can be folded into k; then estimate k from reported amounts of effort spent factoring large integers in tests.
または、人は、o(1)が小さくて、およそ一定であると仮定できました、そして、その結果、値はkに折り重ねることができます。 そして、報告された量の努力からの見積りkは、テストにおける大きい整数を因数分解しながら、費やされました。
This document uses the second approach in order to get an estimate of the significance of the factor. It appears to be minor, based on the following calculations.
このドキュメントは、要素の意味の見積りを得るのに2番目のアプローチを使用します。 それは以下の計算に基づいて小さい方であるように見えます。
Sample values from recent work with the number field sieve include:
ナンバーフィールドふるいがある近作からの標本値は:
Test name Number of Number of MYs of effort
decimal bits
digits
RSA130 130 430 500
RSA140 140 460 2000
RSA155 155 512 8000
RSA160 160 528 3000
努力小数ビットケタRSA130 130 430 500 RSA140 140 460 2000RSA155 155 512 8000RSA160 160 528 3000のMYsのNumberのテスト名前Number
There are few precise measurements of the amount of time used for these factorizations. In most factorization tests, hundreds or thousands of computers are used over a period of several months, but the number of their cycles were used for the factoring project, the precise distribution of processor types, speeds, and so on are not usually reported. However, in all the above cases, the amount of effort used was far less than the L(n) formula would predict if k was 1 and o(1) was 0.
これらのfactorizationsのために費やされた時間の正確な寸法がわずかしかありません。 彼らのサイクルの数は因数分解プロジェクトに使用されました、そして、ほとんどの縮約テストで、数カ月の期間にわたって数百か何千台ものコンピュータが使用されますが、通常、プロセッサタイプの正確な分配、速度などは報告されません。 しかしながら、すべての上の場合では、L(n)公式がkが1であり、o(1)が0であったかどうかと予測するだろうより使用される努力の量ははるかに少なかったです。
A similar estimate of effort, done in 1995, is in [ODL95].
1995年に行われた努力の同様の見積りが[ODL95]にあります。
Results indicating that for the Number Field Sieve factoring method, the actual number of operations is less than expected, are found in [DL].
方法を因数分解するNumber Field Sieveに関して操作の実数が予想より少ないのを示す結果が[DL]で見つけられます。
Orman & Hoffman Best Current Practice [Page 6] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[6ページ]RFC3766
2.2. Choosing k from empirical reports
2.2. 実証的なレポートからのkを選びます。
By solving for k from the empirical reports, it appears that k is approximately 0.02. This means that the "effective key strength" of the RSA algorithm is about 5 or 6 bits less than is implied by the naive application of equation L(n) (that is, setting k to 1 and o(1) to 0). These estimates of k are fairly stable over the numbers reported in the table. The estimate is limited to a single significant digit of k because it expresses real uncertainties; however, the effect of additional digits would have make only tiny changes to the recommended key sizes.
実証的なレポートからのkのために解決することによって、kがおよそ0.02であるように見えます。 これは、RSAアルゴリズムの「有効な主要な強さ」が方程式L(n)(すなわち、1へのkと0へのo(1)を設定する)のナイーブなアプリケーションで含意されるよりおよそ5か6ビット少ないことを意味します。 kのこれらの見積りはかなりテーブルで報告された数の上安定しています。 本当の不明確なことを言い表すので、見積りはkのただ一つの有効数字に制限されます。 しかしながら、追加ケタの効果で、お勧めの主要なサイズへの小さい変更だけを行うでしょう。
The factorers of RSA130 used about 1700 MYs, but they felt that this was unrealistically high for prediction purposes; by using more memory on their machines, they could have easily reduced the time to 500 MYs. Thus, the value used in preparing the table above was 500. This story does, however, underscore the difficulty in getting an accurate measure of effort. This document takes the reported effort for factoring RSA155 as being the most accurate measure.
RSA130のfactorersはおよそ1700MYsを使用しましたが、彼らは、これが予測目的のために非現実的に高いと感じました。 それらのマシンに関する、より多くのメモリを使用することによって、それらは容易に時間を500MYsまで短縮したかもしれません。 したがって、上で食事の支度する際に使用された値は500でした。 しかしながら、この話は努力の正確な手段を得ることにおける苦労を強調します。 このドキュメントは最も正確な測定であるとしてRSA155を因数分解するための報告された努力を取ります。
As a result of examining the empirical data, it appears that the L(n) formula can be used 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. The equation becomes:
実験によって得られるデータを調べることの結果、100〜200の10進数字の範囲で数を因数分解することに関して話すとき、0に決められたo(1)用語と0.02に設定されたkと共にL(n)公式を使用できるように見えます。 方程式はなります:
L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
L(n)は0.02*e^と等しいです。(1.92*cubrt、(ln(n)*(ln(ln(n)))^2))
To convert L(n) from simple math instructions to MYs, divide by 3*10^13. The equation for the number of MYs needed to factor an integer n then reduces to:
簡単な数学指示からMYsまでL(n)を変換するには、3*10^13で、分割してください。 その時整数nを因数分解するのが必要であるMYsの数のための方程式は以下のことのために減少します。
MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
MYsは6*10^(-16)*e^と等しいです。(1.92*cubrt、(ln(n)*(ln(ln(n)))^2))
With what confidence can this formula be used for predicting the difficulty of factoring slightly larger numbers? The answer is that it should be a close upper bound, but each factorization effort is usually marked by some improvement in the algorithms or their implementations that makes the running time somewhat shorter than the formula would indicate.
わずかに大きい数を因数分解するという困難を予測するのにどんな自信をもってこの公式を使用できますか? 答えはそれが近い上限であるべきであるのにもかかわらずの、通常、それぞれの縮約の努力がアルゴリズムか彼らの実現における実行時間を公式が示すだろうよりいくらか短くする何らかの改良でマークされるということです。
2.3. Pollard's rho method
2.3. Pollardρの方法
In Diffie-Hellman exchanges, there is a second attack, Pollard's rho method [POL78]. The algorithm relies on finding collisions between values computed in a large number space; its success rate is proportional to the square root of the size of the space. Because of Pollard's rho method, the search space in a DH key exchange for the key (the exponent in a g^a term), must be twice as large as the
ディフィー-ヘルマンの交換には、2番目の攻撃、Pollardのρ方法[POL78]があります。 アルゴリズムは多くスペースで計算された値の間の調査結果衝突に依存します。 成功率はスペースのサイズの平方根に比例しています。 方法、Pollardのρによるキー(g^a用語による解説者)へのDHの主要な交換における検索スペースは2倍大きくなければなりません。
Orman & Hoffman Best Current Practice [Page 7] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[7ページ]RFC3766
symmetric key. Therefore, to securely derive a key of K bits, an implementation must use an exponent with at least 2*K bits. See [ODL99] for more detail.
対称鍵。 したがって、しっかりとKビットのキーを引き出すために、実現は少なくとも2*Kビットがある解説者を使用しなければなりません。 その他の詳細に関して[ODL99]を見てください。
When the Diffie-Hellman key exchange is done using an elliptic curve method, the NFS methods are of no avail. However, the collision method is still effective, and the need for an exponent (called a multiplier in EC's) with 2*K bits remains. The modulus used for the computation can also be 2*K bits, and this will be substantially smaller than the modulus needed for modular exponentiation methods as the desired security level increases past 64 bits of brute-force attack resistance.
ディフィー-ヘルマンの主要な交換が楕円曲線法を使用し終わっているとき、NFS方法には、利益が全くありません。 しかしながら、衝突方法はまだ効果的です、そして、2*Kビットがある解説者(ECのもので乗数と呼ばれる)の必要性は残っています。 また、計算に使用される係数が2*Kビットであるかもしれなく、これは必要なセキュリティー・レベルが全数探索法抵抗の64ビットの先で増加するのに従ってモジュールの羃法方法に必要である係数より実質的にさらに小さくなるでしょう。
One might ask, how can you compare the number of computer instructions really needed for a discrete logarithm attack to the number needed to search the keyspace of a cipher? In comparing the efforts, one should consider what a "basic operation" is. For brute force search of the keyspace of a symmetric encryption algorithm like DES, the basic operation is the time to do a key setup and the time to do one encryption. For discrete logs, the basic operation is a modular squaring. The log of the ratio of these two operations can be used as a "normalizing factor" between the two kinds of computations. However, even for very large moduli (16K bits), this factor amounts to only a few bits of extra effort.
人は尋ねるかもしれなくて、あなたはどうしたら本当に離散対数攻撃に必要である計算機命令の数を暗号のkeyspaceを捜すのに必要である数にたとえることができますか? 努力を比較する際に、「基本的な操作」が何であるかを考えるべきです。 基本的な操作は、獣に関しては、DESのような左右対称の暗号化アルゴリズムのkeyspaceの検索を強制してください、そして、主要なセットアップをする時間と1つの暗号化をする時間です。 離散的なログに関しては、基本的な操作はモジュールの二乗です。 2種類の計算の間の「正常にする要素」としてこれらの2つの操作の比率に関するログを使用できます。 しかしながら、非常に大きい係数(16Kのビット)のためにさえ、この要素は余分な努力のほんの数ビットに達します。
2.4. Limits of large memory and many machines
2.4. 大きいメモリと多くのマシンの限界
Robert Silverman has examined the question of when it will be practical to factor RSA moduli larger than 512 bits. His analysis is based not only on the theoretical number of operations, but it also includes expectations about the availability of actual machines for performing the work (this document is based only on theoretical number of operations). He examines the question of whether or not we can expect there be enough machines, memory, and communication to factor a very large number.
Robert Silvermanはそれが512ビットより大きい要素RSA係数に実用的になる時に関する質問を調べました。 彼の分析は操作の理論上でない数だけに基づいていますが、また、それは仕事をするための実際のマシンの有用性に関して期待を含んでいます(このドキュメントは理論上の手術件数だけに基づいています)。 彼は私たちが、非常に大きい数を因数分解するためにそこで十分なマシンと、メモリと、コミュニケーションであるように予想できるかどうかに関する質問を調べます。
The best factoring methods need a lot of random access memory for collecting data relations (sieving) and a critical final step that does a row reduction on a large matrix. The memory requirements are related to the size of the number being factored (or subjected to discrete logarithm solution). Silverman [SILIEEE99] [SIL00] has argued that there is a practical limit to the number of machines and the amount of RAM that can be brought to bear on a single problem in the foreseeable future. He sees two problems in attacking a 1024-bit RSA modulus: the machines doing the sieving will need 64-bit address spaces and the matrix row reduction machine will need several terabytes of memory. Silverman notes that very few 64-bit machines
最も良い因数分解方法は資料収集関係(ふるい分け)のための多くのランダムアクセスメモリーと大きいマトリクスで列の減少をする批判的な最終的なステップを必要とします。 メモリ要件は因数分解される(または、離散対数解決策にかけられます)数のサイズに関連します。 シルバーマン[SILIEEE99][SIL00]は、ただ一つの問題ですぐに生かすことができるマシンの数とRAMの量への実用的な限界があると主張しました。 彼は1024年のビットのRSA係数を攻撃する際に2つの問題を認めます: ふるい分けをするマシンは64ビットのアドレス空間を必要とするでしょう、そして、マトリクス列のリダクションマシンはメモリのいくつかのテラバイトを必要とするでしょう。 シルバーマンは64数ビットのまさしくそのマシンに注意します。
Orman & Hoffman Best Current Practice [Page 8] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[8ページ]RFC3766
that have the 170 gigabytes of memory needed for sieving have been sold. Nearly a billion such machines are necessary for the sieving in a reasonable amount of time (a year or two).
それには、ふるい分けを販売したので必要であるメモリの170のギガバイトがあります。 そのようなおよそ10億台のマシンが妥当な時間(1年か2年)でふるい分けに必要です。
Silverman's conclusion, based on the history of factoring efforts and Moore's Law, is that 1024-bit RSA moduli will not be factored until about 2037. This implies a much longer lifetime to RSA keys than the theoretical analysis indicates. He argues that predictions about how many machines and memory modules will be available can be with great confidence, based on Moore's Law extrapolations and the recent history of factoring efforts.
努力とムーアの法則を因数分解する歴史に基づくシルバーマンの結論は1024年のビットのRSA係数が2037年頃まで因数分解されないということです。 これは理論解析が示すよりRSAキーへのはるかに長い生涯を含意します。 彼は、いくつのマシンと記憶モジュールが利用可能になるかに関する予測が自信たっぷりにそうであることができると主張します、ムーアの法則推定と努力を因数分解する最近の歴史に基づいて。
One should give the practical considerations a great deal of weight, but in a risk analysis, the physical world is less predictable than trend graphs would indicate. In considering how much trust to put into the inability of the computer industry to satisfy the voracious needs of factorers, one must have some insight into economic considerations that are more complicated than the mathematics of factoring. The demand for computer memory is hard to predict because it is based on applications: a "killer app" might come along any day and send the memory industry into a frenzy of sales. The number of processors available on desktops may be limited by the number of desks, but very capable embedded systems account for more processor sales than desktops. As embedded systems absorb networking functions, it is not unimaginable that millions of 64-bit processors with at least gigabytes of memory will pervade our environment.
多くの重さを実用的な問題に与えるべきですが、危険分析では、物理的な世界は傾向グラフが示すだろうというほど予測できません。 コンピュータ産業がfactorersの貧欲な需要を満たすことができないことにどのくらいの信用を置くかを考える際に、因数分解の数学より複雑な経済上の考慮に何らかの洞察力を持たなければなりません。 コンピュータメモリの要求はアプリケーションに基づいているので、予測しにくいです: 「キラー・アプリケーション」は、販売の狂乱にいつでも、やって来て、メモリ産業を送るかもしれません。 デスクトップで利用可能なプロセッサの数は机の数によって制限されるかもしれませんが、非常にできる組込み型システムはデスクトップより多くのプロセッサ販売を説明します。 組込み型システムがネットワーク機能を吸収するので、少なくともメモリのギガバイトがある何百万台もの64ビットのプロセッサが私たちの環境を瀰漫させるのは、想像を絶していません。
The bottom line on this is that the key length recommendations predicted by theory may be overly conservative, but they are what we have used for this document. This question of machine availability is one that should be reconsidered in light of current technology on a regular basis.
これの結論は理論によって予測されたキー長推薦がひどく保守的であるかもしれないのにもかかわらずの、それらが私たちがこのドキュメントに使用したことであるということです。 マシンの有用性のこの質問は現在の技術の観点から定期的に再考されるべきであるものです。
2.5. Special purpose machines
2.5. 専用マシン
In August of 2003, a design for a special-purpose "sieving machine" (TWIRL) surfaced [Shamir2003], and it substantially changed the cost estimates for factoring numbers up to 1024 bits in size. By applying many high-speed VLSI components in parallel, such a machine might be able to carry out the sieving of 512-bit numbers in 10 minutes at a cost of $10K for the hardware. A larger version could sieve a 1024- bit number in one year for a cost of $10M. The work cites some advances in approaches to the row reduction step in concluding that the security of 1024-bit RSA moduli is doubtful.
2003年8月に、専用「ふるい分けマシン」(TWIRL)のためのデザインは[Shamir2003]の表面を仕上げました、そして、それは実質的に数を因数分解するための費用見積りをサイズにおける1024ビットまで変えました。 平行な多くの高速VLSIコンポーネントを適用することによって、そのようなマシンはハードウェアのために10分で10ドルのKの費用で512ビットの数のふるい分けを行うことができるかもしれません。 より大きいバージョンはある年間でaの数がかかる1024年の10ドルのMのふるいのaビットをそうすることができました。 1024年のビットのRSA係数のセキュリティが疑わしいと結論を下す際に仕事は列の減少ステップへのアプローチにおけるいくつかの進歩を引用します。
The estimates for the time and cost for factoring 512-bit and 1024- bit numbers correspond to a speed-up factor of about 2 million over what can be achieved with commodity processors of a few years ago.
時間の見積りと512ビットと1024の噛み付いている番号を因数分解するための費用は数年前の商品プロセッサで達成できることの上でおよそ200万の加速要素に対応しています。
Orman & Hoffman Best Current Practice [Page 9] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[9ページ]RFC3766
3. Compute Time for the Algorithms
3. アルゴリズムのための時間を計算してください。
This section describes how long it takes to use the algorithms to perform key exchanges. Again, it is important to consider the increased time it takes to exchange symmetric keys when increasing the length of public keys. It is important to avoid choosing unfeasibly long public keys.
このセクションは、主要な交換を実行するのにアルゴリズムを使用するにはどれくらいかかるかを説明します。 一方、わざわざ公開鍵の長さを増加させるときそれが対称鍵を交換する増加する考えるのは重要です。 「非-実行できるように」に長い公開鍵を選ぶのを避けるのは重要です。
3.1. Diffie-Hellman Key Exchange
3.1. ディフィー-ヘルマンの主要なExchange
A Diffie-Hellman key exchange is done with a finite cyclic group G with a generator g and an exponent x. As noted in the Pollard's rho method section, the exponent has twice as many bits as are needed for the final key. Let the size of the group G be p, let the number of bits in the base 2 representation of p be j, and let the number of bits in the exponent be K.
主要な交換が有限循環群Gと共にジェネレータgと解説者xで行われるディフィー-ヘルマン。 Pollardρの方法部で注意されるように、解説者には最終的なキーに必要とされるより2倍のビットがあります。 グループGのサイズがpであることをさせてください、そして、pのベース2表現における、ビットの数がjであることをさせてください、そして、解説者のビットの数がKであることをさせてください。
In doing the operations that result in a shared key, a generator is raised to a power. The most efficient way to do this involves squaring a number K times and multiplying it several times along the way. Each of the numbers has j/w computer words in it, where w is the number of bits in a computer word (today that will be 32 or 64 bits). A naive assumption is that you will need to do j squarings and j/2 multiplies; fortunately, an efficient implementation will need fewer (NB: for the remainder of this section, n represents j/w).
共有されたキーでその結果を操作にする際に、ジェネレータはパワーに上げられます。 これをする最も効率的な方法は、数のK回数を二乗して、道に沿って何度かそれを掛けることを伴います。 それぞれの数には、それのj/wコンピュータ単語があります。そこでは、コンピュータ単語でwがビットの数(それは、今日、32ビットか64ビットになる)です。 単純な想定はあなたが、j squaringsをする必要があるということです、そして、j/2は増えます。 幸い、効率的な実現は必要としないでしょう。(ネブラスカ: このセクションの残りのために、nはj/wを表します)。
A squaring operation does not need to use quite as many operations as a multiplication; a reasonable estimate is that squaring takes .6 the number of machine instructions of a multiply. If one prepares a table ahead of time with several values of small integer powers of the generator g, then only about one fifth as many multiplies are needed as the naive formula suggests. Therefore, one needs to do the work of approximately .8*K multiplies of n-by-n word numbers. Further, each multiply and squaring must be followed by a modular reduction, and a good assumption is that it is as hard to do a modular reduction as it is to do an n-by-n word multiply. Thus, it takes K reductions for the squarings and .2*K reductions for the multiplies. Summing this, the total effort for a Diffie-Hellman key exchange with K bit exponents and a modulus of n words is approximately 2*K n-by-n-word multiplies.
二乗操作は乗法と全く同じくらい多くの操作を使用する必要はありません。 合理的な見積りは二乗がaの機械番号指示が掛ける.6を取るということです。 1つが早めにジェネレータgの小さい整数強国のいくつかの値でテーブルを準備するなら、多くが増えるようにナイーブな公式が示すようにおよそ1/5だけが必要です。 したがって、人は、*Kがn×n単語番号について掛けるおよそ.8の仕事をする必要があります。 さらに、それぞれが増えます、そして、モジュールの減少は二乗のあとに続かなければなりません、そして、良い仮定はそれがn nの単語が掛けるすることになっているのと同じくらいしにくいモジュールの減少であるということです。 その結果、squaringsと.2*KのためのK減少に減少を取る、増えます。 これをまとめて、総努力は、Kとのディフィー-ヘルマンの主要な交換が解説者に噛み付いて、n単語の係数がおよそ2*Kであるのでn単語nに増えます。
For 32-bit processors, integers that use less than about 30 computer words in their representation require at least n^2 instructions for an n-by-n-word multiply. Larger numbers will use less time, using Karatsuba multiplications, and they will scale as about n^(1.58) for larger n, but that is ignored for the current discussion. Note that 64-bit processors push the "Karatsuba cross-over" number out to even more bits.
32ビットのプロセッサに関しては、彼らの表現におよそ30未満のコンピュータ単語を使用する整数が少なくともn単語によるnのための2つの指示が掛けるn^を必要とします。 Karatsuba掛け算を使用して、より大きい数は、より少ない時間を費やすでしょう、そして、より大きいnのためのn^(1.58)のように比例するでしょうが、それは現在の議論のために無視されます。 64ビットのプロセッサが「Karatsubaクロスオーバー」番号をさらに多くのビットまで押し出すことに注意してください。
Orman & Hoffman Best Current Practice [Page 10] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[10ページ]RFC3766
The basic result is: if you double the size of the Diffie-Hellman modular exponentiation group, you quadruple the number of operations needed for the computation.
基本的な結果は以下の通りです。 ディフィー-ヘルマンのモジュールの羃法グループのサイズを倍にするなら、あなたは計算に必要である手術件数を4倍にします。
3.1.1. Diffie-Hellman with elliptic curve groups
3.1.1. 楕円曲線グループをもっているディフィー-ヘルマン
Note that the ratios for computation effort as a function of modulus size hold even if you are using an elliptic curve (EC) group for Diffie-Hellman. However, for equivalent security, one can use smaller numbers in the case of elliptic curves. Assume that someone has chosen an modular exponentiation group with an 2048 bit modulus as being an appropriate security measure for a Diffie-Hellman application and wants to determine what advantage there would be to using an EC group instead. The calculation is relatively straightforward, if you assume that on the average, it is about 20 times more effort to do a squaring or multiplication in an EC group than in a modular exponentiation group. A rough estimate is that an EC group with equivalent security has about 200 bits in its representation. Then, assuming that the time is dominated by n-by-n- word operations, the relative time is computed as:
ディフィー-ヘルマンに楕円曲線(EC)グループを使用していても係数サイズの関数としての計算の努力のための比率が成立することに注意してください。 しかしながら、同等なセキュリティのために、1つは楕円曲線の場合により少ない数を使用できます。 だれかが、ディフィー-ヘルマンアプリケーションのための適切な安全対策であるとして2048年のビットの係数があるモジュールの羃法グループを選んで、代わりにECグループを使用するのにどんな利点があるかを決定したがっていると仮定してください。 計算は比較的簡単です、あなたが、平均して、それがECグループの二乗か乗法をするためのモジュールの羃法グループよりおよそ20倍多くの努力であると仮定するなら。 概算は同等なセキュリティがあるECグループが表現でおよそ200ビットを持っているということです。 そして、時間が近くn n-単語の操作で支配されると仮定して、相対的な時間は以下として計算されます。
((2048/200)^2)/20 ~= 5
((2048/200)^2)/20 ~= 5
showing that an elliptic curve implementation should be five times as fast as a modular exponentiation implementation.
楕円曲線実現がモジュールの羃法実現の5倍速いはずであるのを示します。
3.2. RSA encryption and decryption
3.2. RSA暗号化と復号化
Assume that an RSA public key uses a modulus with j bits; its factors are two numbers of about j/2 bits each. The expected computation time for encryption and decryption are different. As before, we denote the number of words in the machine representation of the modulus by the symbol n.
RSA公開鍵がjビットがある係数を使用すると仮定してください。 要素はそれぞれj/2ビットの2つの番号です。 暗号化と復号化のための予想された計算時間はいろいろです。 従来と同様、私たちはシンボルnで係数のマシン表現におけるワード数を指示します。
Most implementations of RSA use a small exponent for encryption. An encryption may involve as few as 16 squarings and one multiplication, using n-by-n-word operations. Each operation must be followed by a modular reduction, and therefore the time complexity is about 16*(.6 + 1) + 1 + 1 ~= 28 n-by-n-word multiplies.
RSAのほとんどの実現が暗号化に小さい解説者を使用します。 n単語によるn操作を使用して、暗号化は最小16squaringsと1つの乗法にかかわるかもしれません。 モジュールの減少は各操作のあとに続かなければなりません、そして、したがって、時間的コストはn単語による*1~=28(.6+1)+1+nが掛けるおよそ16です。
RSA decryption must use an exponent that has as many bits as the modulus, j. However, the Chinese Remainder Theorem applies, and all the computations can be done with a modulus of only n/2 words and an exponent of only j/2 bits. The computation must be done twice, once for each factor. The effort is equivalent to 2*(j/2) (n/2 by n/2)- word multiplies. Because multiplying numbers with n/2 words is only 1/4 as difficult as multiplying numbers with n words, the equivalent effort for RSA decryption is j/4 n-by-n-word multiplies.
RSA復号化は係数、jと同じくらい多くのビットを持っている解説者を使用しなければなりません。 すべての計算が、しかしながら、中国のRemainder Theoremは適用して、n/2つの単語だけの係数でしていてj/2ビットだけの解説者であるかもしれません。 各要素のために二度一度計算しなければなりません。 努力は2*(j/2)(n/n2×/2)に同等です--言葉は増えます。 増えるのがn/2で単語に付番するので、1/4だけがRSA復号化がn単語によるnが掛けるj/4であるのでn単語、同等な努力で数を掛けるのと同じくらい難しいですか?
Orman & Hoffman Best Current Practice [Page 11] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[11ページ]RFC3766
If you double the size of the modulus for RSA, the n-by-n multiplies will take four times as long. Further, the decryption time doubles because the exponent is larger. The overall scaling cost is a factor of 4 for encryption, a factor of 8 for decryption.
あなたが倍増すると、nがRSA、nに増えるので、係数のサイズは長いとして4倍みなすでしょう。 さらに、解説者が、より大きいので、復号化時間は倍増します。 総合的なスケーリング費用は暗号化のための4の要素、復号化のための8の要素です。
3.3. Real-world examples
3.3. 本当の世界の例
To make these numbers more real, here are a few examples of software implementations run on hardware that was current as of a few years before the publication of this document. The examples are included to show rough estimates of reasonable implementations; they are not benchmarks. As with all software, the performance will depend on the exact details of specialization of the code to the problem and the specific hardware.
これらの数をより現実的にするように、数年の時点でよく見られたハードウェアの上を走ったソフトウェア実行に関するいくつかの例がこのドキュメントの公表の前にここにあります。 例は合理的な実現の概算を示しているために含まれています。 それらはベンチマークではありません。 すべてのソフトウェアの場合、性能は問題へのコードと特定のハードウェアの専門化の正確な詳細に依存するでしょう。
The best time informally reported for a 1024-bit modular exponentiation (the decryption side of 2048-bit RSA), is 0.9 ms (about 450,000 CPU cycles) on a 500 MHz Itanium processor. This shows that newer processors are not losing ground on big number operations; the number of instructions is less than a 32-bit processor uses for a 256-bit modular exponentiation.
1024年のビットのモジュールの羃法(2048年のビットのRSAの復号化側面)のために非公式に報告される中で最も良い時間は500MHzのアイテニアムプロセッサの上の0.9ms(およそ45万CPUサイクル)です。 これは、より新しいプロセッサが大きい数の操作のときに悪化しないのを示します。 指示の数は256ビットのモジュールの羃法への1つ未満の32ビットのプロセッサ用途です。
For less advanced processors timing, the following two tables (computed by Tero Monenen at SSH Communications) for modular exponentiation, such as would be done in a Diffie-Hellman key exchange.
それほど高度でないプロセッサタイミング、ディフィー-ヘルマンの主要な交換でするようなモジュールの羃法のための以下の2個のテーブル(SSH CommunicationsでTero Monenenによって計算される)のために。
Celeron 400 MHz; compiled with GNU C compiler, optimized, some platform specific coding optimizations:
セレロン400MHz。 GNU Cコンパイラで、いくつかのプラットホームの特定のコード化最適化を最適化されて、コンパイルします:
group modulus exponent time
type size size
mod 768 ~150 18 msec
mod 1024 ~160 32 msec
mod 1536 ~180 82 msec
ecn 155 ~150 35 msec
ecn 185 ~200 56 msec
グループ係数解説者時間タイプサイズサイズモッズ風の768~150の1536~180 82msec ecn155~150 35msec18msecモッズ風の1024~160 32msecモッズecn185~200 56msec
The group type is from [RFC2409] and is either modular exponentiation
("mod") or elliptic curve ("ecn"). All sizes here and in subsequent
tables are in bits.
グループタイプは、[RFC2409]から来ていて、モジュールの羃法(「モッズ」)か楕円曲線("ecn")のどちらかです。 こことその後のテーブルのすべてのサイズがビットにあります。
Orman & Hoffman Best Current Practice [Page 12] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[12ページ]RFC3766
Alpha 500 MHz compiled with Digital's C compiler, optimized, no platform specific code:
アルファー500MHzはDigital Cのコンパイラでどんなプラットホームの特定のコードも最適化されて、コンパイルしませんでした:
group modulus exponent time
type size size
mod 768 ~150 12 msec
mod 1024 ~160 24 msec
mod 1536 ~180 59 msec
ecn 155 ~150 20 msec
ecn 185 ~200 27 msec
グループ係数解説者時間タイプサイズサイズモッズ風の768~150の1536~180 59msec ecn155~150 20msec12msecモッズ風の1024~160 24msecモッズecn185~200 27msec
The following two tables (computed by Eric Young) were originally for RSA signing operations, using the Chinese Remainder representation. For ease of understanding, the parameters are presented here to show the interior calculations, i.e., the size of the modulus and exponent used by the software.
以下の2個のテーブル(エリック・ヤングによって計算される)が元々中国のRemainder表現を使用して、操作にサインするRSAのためのものでした。 理解の容易さにおいて、パラメタは、内部の計算、すなわち、ソフトウェアによって使用される係数と解説者のサイズを示しているためにここに提示されます。
Dual Pentium II-350:
二元的なPentium II-350:
equiv equiv equiv
modulus exponent time
size size
256 256 1.5 ms
512 512 8.6 ms
1024 1024 55.4 ms
2048 2048 387 ms
equiv equiv equiv係数解説者時間サイズサイズ256 256 1.5ms512 512 8.6ms1024 1024 55.4ms2048 2048 387ms
Alpha 264 600mhz:
アルファー264 600mhz:
equiv equiv equiv
modulus exponent time
size size
512 512 1.4 ms
equiv equiv equiv係数解説者時間サイズサイズ512 512 1.4ms
Recent chips that accelerate exponentiation can perform 1024-bit exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 milliseconds or less.
羃法を加速する最近のチップはおよそ3ミリセカンド以下で1024年のビットの羃法(1024は係数に噛み付きました、1024年のビットの解説者)を実行できます。
4. Equivalences of Key Sizes
4. 主要なサイズの等価性
In order to determine how strong a public key is needed to protect a particular symmetric key, you first need to determine how much effort is needed to break the symmetric key. Many Internet security protocols require the use of TripleDES for strong symmetric encryption, and it is expected that the Advanced Encryption Standard (AES) will be adopted on the Internet in the coming years. Therefore, these two algorithms are discussed here. In this section, for illustrative purposes, we will implicitly assume that the system
どれくらい強い公開鍵が特定の対称鍵を保護するのに必要であるかを決定するために、あなたは、最初に、どのくらいの努力が対称鍵を壊すのに必要であるかを決定する必要があります。 多くのインターネットセキュリティプロトコルがTripleDESの強い左右対称の暗号化の使用を必要とします、そして、エー・イー・エス(AES)が来たる年の間インターネットに採用されると予想されます。 したがって、ここでこれらの2つのアルゴリズムについて議論します。 このセクションでは、説明に役立った目的のために、私たちは、それがシステムであるとそれとなく思うつもりです。
Orman & Hoffman Best Current Practice [Page 13] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[13ページ]RFC3766
security requirement is 112 bits; this doesn't mean that 112 bits is recommended. In fact, 112 bits is arguably too strong for any practical purpose. It is used for illustration simply because that is the upper bound on the strength of TripleDES.
セキュリティ要件は112ビットです。 これは、112ビットがお勧めであることを意味しません。 事実上、112ビットはどんな実用的な目的のためにも論証上強過ぎます。 単にそれがTripleDESの強さの上限であるので、それはイラストに使用されます。
If one could simply determine the number of MYs it takes to break TripleDES, the task of computing the public key size of equivalent strength would be easy. Unfortunately, that isn't the case here because there are many examples of DES-specific hardware that encrypt faster than DES in software on a standard CPU. Instead, one must determine the equivalent cost for a system to break TripleDES and a system to break the public key protecting a TripleDES key.
人が単にTripleDESを壊すのに要するMYsの数を測定できるなら、同等な強さの公開鍵サイズを計算するタスクは簡単でしょうに。 残念ながら、それが標準のCPUの上にソフトウェアでDESより速くコード化するDES特有のハードウェアに関する多くの例があるので、それはここのそうではありません。 代わりに、システムがTripleDESキーを保護する公開鍵を壊すためにTripleDESとシステムを壊すように、同等な費用を決定しなければなりません。
In 1998, the Electronic Frontier Foundation (EFF) built a DES- cracking machine [GIL98] for US$130,000 that could test about 1e11 DES keys per second (additional money was spent on the machine's design). The machine's builders fully admit that the machine is not well optimized, and it is estimated that ten times the amount of money could probably create a machine about 50 times as fast. Assuming more optimization by guessing that a system to test TripleDES keys runs about as fast as a system to test DES keys, so approximately US$1 million might test 5e12 TripleDES keys per second.
1998年に、電子フロンティア財団(EFF)は、1秒あたりの1e11 DESキーに関してテストされることができた13万USドルでマシン[GIL98]を割りながら、DESを造りました(別途のお金はマシンのデザインに費やされました)。 マシンの建築業者は、マシンがよく最適化されないで、金額の10倍がたぶんおよそ50倍速くマシンを作成するかもしれないと見積もられていることを完全に認めます。 したがって、それを推測するのによる、より多くの最適化がDESキーを検査するためにシステムとほぼ同じくらい速く検査するシステムであると仮定する場合、およそ100万USドルは1秒あたりの5e12 TripleDESキーを検査するかもしれません。
In case your adversaries are much richer than EFF, you may want to assume that they have US$1 trillion, enough to test 5e18 keys per second. An exhaustive search of the effective TripleDES space of 2^112 keys with this quite expensive system would take about 1e15 seconds or about 33 million years. (Note that such a system would also need 2^60 bytes of RAM [MH81], which is considered free in this calculation). This seems a needlessly conservative value. However, if computer logic speeds continue to increase in accordance with Moore's Law (doubling in speed every 1.5 years), then one might expect that in about 50 years, the computation could be completed in only one year. For the purposes of illustration, this 50 year resistance against a trillionaire is assumed to be the minimum security requirement for a set of applications.
あなたの敵がEFFよりはるかに金持ちであるといけないので、あなたは、彼らには1秒あたりの5e18キーを検査できるくらいの1兆USドルがあると仮定したがっているかもしれません。 このかなり高価なシステムによる2個の^112キーの有効なTripleDESスペースの徹底的な検索は1e15秒かおよそ3300万年に関して取るでしょう。 (また、そのようなシステムがRAM[MH81]の2^60バイトを必要とすることに注意します。)RAMはこの計算で自由であると考えられます。 これは不必要に保守的な値に見えます。 しかしながら、コンピュータ論理速度が、ムーアの法則によると、増加し続けているなら(1.5年毎に速度で倍増して)、人は、計算がほんの1年間で終了できたとおよそ50年間で、予想するかもしれません。 イラストの目的のために、trillionaireに対する50年間のこの抵抗は1セットのアプリケーションのための最小のセキュリティ要件であると思われます。
If 112 bits of attack resistance is the system security requirement, then the key exchange system for TripleDES should have equivalent difficulty; that is to say, if the attacker has US$1 trillion, you want him to spend all his money to buy hardware today and to know that he will "crack" the key exchange in not less than 33 million years. (Obviously, a rational attacker would wait for about 45 years before actually spending the money, because he could then get much better hardware, but all attackers benefit from this sort of wait equally.)
攻撃抵抗の112ビットがシステムセキュリティ要件であるなら、TripleDESの主要な交換システムは同等な苦労をするはずです。 すなわち、攻撃者に1兆USドルがあるなら、あなたは、彼に今日、ハードウェアを買って、彼が少なくとも3300万年後に主要な交換を「割ること」を知るのにすべてのお金を使って欲しいです。 (明らかに、理性的な攻撃者はこの種類の待ちから次に、彼がはるかに良いハードウェアを手に入れることができたので実際にお金を使うおよそ45年前にもかかわらず、すべての攻撃者利益を等しく待つでしょう。)
Orman & Hoffman Best Current Practice [Page 14] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[14ページ]RFC3766
It is estimated that a typical PC CPU of just a few years ago can generate over 500 MIPs and could be purchased for about US$100 in quantity; thus you get more than 5 MIPs/US$. Again, this number doubles about every 18 months. For one trillion US dollars, an attacker can get 5e12 MIP years of computer instructions on that recent-vintage hardware. This figure is used in the following estimates of equivalent costs for breaking key exchange systems.
わずか数年前の典型的なPC CPUは500MIPsを発生させることができて、量におけるおよそ100USドルで購入できたと見積もられています。 したがって、あなたは5MIPs/USドル以上を得ます。一方、この数は18カ月毎に関して倍増します。 兆米ドル、攻撃者はその最近のヴィンテージハードウェアで5e12 MIP数年の計算機命令を手に入れることができます。 この図は壊れている主要な交換システムに同等なコストの以下の見積りに使用されます。
4.1. Key equivalence against special purpose brute force hardware
4.1. 目的の特別な馬鹿力ハードウェアに対する主要な等価性
If the trillionaire attacker is to use conventional CPU's to "crack" a key exchange for a 112 bit key in the same time that the special purpose machine is spending on brute force search for the symmetric key, the key exchange system must use an appropriately large modulus. Assume that the trillionaire performs 5e12 MIPs of instructions per year. Use the following equation to estimate the modulus size to use with RSA encryption or DH key exchange:
trillionaire攻撃者が専用マシンが対称鍵の獣の力の検索に費やされる同時間で主要な112ビットへの主要な交換を「割ること」に従来のCPUのものを使用するつもりであるなら、主要な交換システムは適切に大きい係数を使用しなければなりません。 trillionaireが1年あたりの指示の5e12 MIPsを実行すると仮定してください。 以下の方程式を使用して、係数がRSA暗号化かDHの主要な交換と共に使用するサイズであると見積もってください:
5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
5 *10^33は*e^と等しいです(6*10^-16)。(1.92*cubrt、(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
nのために周囲でこれを解決するのはもたらされます:
n = 10^(625) = 2^(2077)
n=10^(625)は2^と等しいです。(2077)
Thus, assuming similar logic speeds and the current efficiency of the number field sieve, moduli with about 2100 bits will have about the same resistance against attack as an 112-bit TripleDES key. This indicates that RSA public key encryption should use a modulus with around 2100 bits; for a Diffie-Hellman key exchange, one could use a slightly smaller modulus, but it is not a significant difference.
したがって、同様の論理が速度とナンバーフィールドふるいの電流効率であると仮定すると、およそ2100ビットがある係数は112ビットのTripleDESキーとしてほぼ同じくらいの抵抗を攻撃に抱くでしょう。 これは、RSA公開鍵暗号化がおよそ2100ビットがある係数を使用するべきであるのを示します。 ディフィー-ヘルマンの主要な交換のために、1つはわずかに小さい係数を使用するかもしれませんが、それは著しい違いではありません。
4.2 Key equivalence against conventional CPU brute force attack
4.2 従来のCPU総当たり攻撃に対する主要な等価性
An alternative way of estimating this assumes that the attacker has a less challenging requirement: he must only "crack" the key exchange in less time than a brute force key search against the symmetric key would take with general purpose computers. This is an "apples-to- apples" comparison, because it assumes that the attacker needs only to have computation donated to his effort, not built from a personal or national fortune. The public key modulus will be larger than the one in 4.1, because the symmetric key is going to be viable for a longer period of time.
これを見積もる代替の方法は、攻撃者にはそれほどやりがいがない要件があると仮定します: 彼は対称鍵に対する獣の力のキー検索が汎用計算機で取るだろうより少ない時間、主要な交換を「割るだけでよいです」。 これは「りんごからりんご」比較です、攻撃者が、個人的であるか国家の財産から建てられるのではなく、彼の努力に計算を単に寄贈させる必要であると仮定するので。 公開鍵係数はものより4.1でさらに大きくなるでしょう、対称鍵がさらに長い期間の間、実行可能になるので。
Assume that the number of CPU instructions to encrypt a block of material using TripleDES is 300. The estimated number of computer instructions to break 112 bit TripleDES key:
TripleDESを使用することで1ブロックの材料をコード化するCPU指示の数が300であると仮定してください。 112ビットのTripleDESキーを壊す計算機命令の概算数:
Orman & Hoffman Best Current Practice [Page 15] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[15ページ]RFC3766
300 * 2^112
= 1.6 * 10^(36)
= .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
300 *2^112 = 1.6*10^(36)は.02*e^と等しいです。(1.92*cubrt、(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
nのために周囲でこれを解決するのはもたらされます:
n = 10^(734) = 2^(2439)
n=10^(734)は2^と等しいです。(2439)
Thus, for general purpose CPU attacks, you can assume that moduli with about 2400 bits will have about the same strength against attack as an 112-bit TripleDES key. This indicates that RSA public key encryption should use a modulus with around 2400 bits; for a Diffie- Hellman key exchange, one could use a slightly smaller modulus, but it not a significant difference.
したがって、汎用のCPU攻撃のために、あなたは、ビットが112ビットのTripleDESキーとしてほぼ同じくらいの強さを攻撃に抱くとおよそ2400があるその係数に仮定できます。 これは、RSA公開鍵暗号化がおよそ2400ビットがある係数を使用するべきであるのを示します。 ディフィーのヘルマンのキー交換のために、1つは著しい違いではなく、わずかに小さい係数、しかし、それを使用するかもしれません。
Note that some authors assume that the algorithms underlying the number field sieve will continue to get better over time. These authors recommend an even larger modulus, over 4000 bits, for protecting a 112-bit symmetric key for 50 years. This points out the difficulty of long-term cryptographic security: it is all but impossible to predict progress in mathematics and physics over such a long period of time.
何人かの作者が、ナンバーフィールドふるいの基礎となるアルゴリズムが、時間がたつにつれて回復し続けると仮定することに注意してください。 これらの作者は、50年間112ビットの対称鍵を保護するためにさらに大きい係数を4000ビットの上推薦します。 これは長期の暗号のセキュリティの困難を指摘します: そのような長日月の間、数学と物理学における進歩を予測するのはほとんど不可能です。
4.3. A One Year Attack: 80 bits of strength
4.3. A Oneの年の攻撃: 強さの80ビット
Assuming a trillionaire spends his money today to buy hardware, what size key exchange numbers could he "crack" in one year? He can perform 5*e12 MYs of instructions, or
trillionaireが今日ハードウェアを買うために私費を投じると仮定する場合、彼は1年間でどんなサイズの主要な局番を「割るかもしれませんか?」 または彼が指示の5*e12 MYsを実行できる。
3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
3*10^13*5*10^12は.02*e^と等しいです。(1.92*cubrt、(ln(n)*(ln(ln(n)))^2))
Solving for an approximation of n yields
nの近似のために、利回りを解決します。
n = 10^(360) = 2^(1195)
n=10^(360)は2^と等しいです。(1195)
This is about as many operations as it would take to crack an 80-bit symmetric key by brute force.
これは暴力で80ビットの対称鍵を割るのに要するだろうというのとほぼ同じくらい多くの操作です。
Thus, for protecting data that has a secrecy requirement of one year against an incredibly rich attacker, a key exchange modulus with about 1200 bits protecting an 80-bit symmetric key is safe even against a nation's resources.
したがって、1年の秘密主義要件を信じられないほど金持ちの攻撃者に抱くデータを保護するのにおいて、およそ1200ビットが80ビットの対称鍵を保護している主要な交換係数は国のリソースに対してさえ安全です。
4.4. Key equivalence for other ciphers
4.4. 他の暗号のための主要な等価性
Extending this logic to the AES is straightforward. For purposes of estimation for key searching, one can think of the 128-bit AES as being at least 16 bits stronger than TripleDES but about three times
この論理についてAESに敷衍するのは簡単です。 主要な探す見積りの目的のために、人はTripleDESにもかかわらず、およそ3回より少なくとも16ビット強いとして128ビットのAESを考えることができます。
Orman & Hoffman Best Current Practice [Page 16] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[16ページ]RFC3766
as fast. The time and cost for a brute force attack is approximately 2^(16) more than for TripleDES, and thus, under the assumption that 128 bits of strength is the desired security goal, the recommended key exchange modulus size is about 700 bits longer.
速いとして。 総当たり攻撃のための時間と費用は(16) TripleDESよりさらにおよそ2^です、そして、その結果、強さの128ビットが必要なセキュリティ目標であるという仮定で、お勧めの主要な交換係数サイズはおよそ700ビットより長いです。
If it is possible to design hardware for AES cracking that is considerably more efficient than hardware for DES cracking, then (again under the assumption that the key exchange strength must match the brute force effort) the moduli for protecting the key exchange can be made smaller. However, the existence of such designs is only a matter of speculation at this early moment in the AES lifetime.
そして(主要な交換の強さが獣の力の努力に合わなければならないという再び仮定で)、DES分解のためのハードウェアよりかなり効率的なAES分解のためのハードウェアを設計するのが可能であるなら、主要な交換を保護するための係数をより小さくすることができます。 しかしながら、そのようなデザインの存在はAES生涯のこの瞬間前半の思惑の問題にすぎません。
The AES ciphers have key sizes of 128 bits up to 256 bits. Should a prudent minimum security requirement, and thus the key exchange moduli, have similar strengths? The answer to this depends on whether or not one expect Moore's Law to continue unabated. If it continues, one would expect 128 bit keys to be safe for about 60 years, and 256 bit keys would be safe for another 400 years beyond that, far beyond any imaginable security requirement. But such progress is difficult to predict, as it exceeds the physical capabilities of today's devices and would imply the existence of logic technologies that are unknown or infeasible today. Quantum computing is a candidate, but too little is known today to make confident predictions about its applicability to cryptography (which itself might change over the next 100 years!).
AES暗号には、256ビットまでの128ビットの主要なサイズがあります。 慎重な最小のセキュリティ要件、およびその結果、主要な交換係数には、同様の強さがあるべきですか? この答えは人が、ムーアの法則が変わらない状態で続くと予想するかどうかによります。 続くなら、人は、128ビットのキーがおよそ60年間安全であると予想するでしょう、そして、256ビットのキーはもう400年間それを超えて安全でしょう、遠くにどんな想像可能なセキュリティ要件を超えて。 しかし、そのような進歩は予測するのが難しいです、今日の装置の肉体的能力を超えて、未知であることの、または、今日実行不可能な論理技術の存在を含意するだろうというとき。 量子コンピューティングは候補ですが、今日、暗号への適用性に関する自信がある予測をするのが少ししか知られ過ぎるというわけではありません(次の100年間それ自体で変化するかもしれない!)。
If Moore's Law does not continue to hold, if no new computational paradigms emerge, then keys of over 100 bits in length might well be safe "forever". Note, however that others have come up with estimates based on assumptions of new computational paradigms emerging. For example, Lenstra and Verheul's web-based paper "Selecting Cryptographic Key Sizes" chooses a more conservative analysis than the one in this document.
どんな新しいコンピュータのパラダイムも現れないならムーアの法則がずっと成立しないなら、長さ100ビット以上のキーは「いつまでも、」たぶん安全でしょう。 しかしながら、新しいコンピュータのパラダイムの仮定に基づいた見積りが現れていて他のものが来たことに注意してください。 例えば、Lenstraとフェルヘールのウェブベースの紙の「選択の暗号の主要なサイズ」は本書ではものより保守的な分析を選びます。
4.5. Hash functions for deriving symmetric keys from public key
algorithms
4.5. 公開鍵アルゴリズムから対称鍵を得るためのハッシュ関数
The Diffie-Hellman algorithm results in a key that is hundreds or thousands of bits long, but ciphers need far fewer bits than that. How can one distill a long key down to a short one without losing strength?
ディフィー-ヘルマンアルゴリズムは数百の、または、長さ何千ビットであるもキーをもたらしますが、暗号はそれよりはるかに少ないビットを必要とします。 力を失わないで、1つはどうしたら長いキーを短いものまで蒸留できますか?
Cryptographic one-way hash functions are the building blocks for this, and so long as they use all of the Diffie-Hellman key to derive each block of the symmetric key, they produce keys with sufficient strength.
暗号の片道ハッシュ関数はこれのためのブロックです、そして、対称鍵の各ブロックを引き出すために主要なディフィー-ヘルマンのすべてを使用する限り、それらは十分な力でキーを生産します。
Orman & Hoffman Best Current Practice [Page 17] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[17ページ]RFC3766
The usual recommendation is to use a good one-way hash function applied to he base material (the result of the key exchange) and to use a subset of the hash function output for the key. However, if the desired key length is greater than the output of the hash function, one might wonder how to reconcile the two.
普通の推薦は適用された良い片道ハッシュ関数を使用するために、彼が材料(主要な交換の結果)を基礎づけるということです、そして、キーのために出力されて、細切れ肉料理の部分集合を使用するのは機能します。 しかしながら、必要なキー長がハッシュ関数の出力より大きいなら、人は2を和解させる方法を思うかもしれません。
The step of deriving extra key bits must satisfy these requirements:
余分なキービットを引き出すステップはこれらの要件を満たさなければなりません:
- The bits must not reveal any information about the key exchange
secret
- ビットは、主要な交換のどんな情報も秘密であることを明らかにしてはいけません。
- The bits must not be correlated with each other
- 互いと共にビットを関連させてはいけません。
- The bits must depend on all the bits of the key exchange secret
- ビットは主要な交換秘密のすべてのビットに依存しなければなりません。
Any good cryptographic hash function satisfies these three requirements. Note that the number of bits of output of the hash function is not specified. That is because even a hash function with a very short output can be iterated to produce more uncorrelated bits with just a little bit of care.
どんな良い暗号のハッシュ関数もこれらの3つの要件を満たします。 ハッシュ関数の出力のビットの数が指定されないことに注意してください。 それはまさしく少しの注意がある、より多くの非相関ビットを作り出すために非常に短い出力があるハッシュ関数さえ繰り返すことができるからです。
For example, SHA-1 has 160 bits of output. For deriving a key of attack resistance of 160 bits or less, SHA(DHkey) produces a good symmetric key.
例えば、SHA-1には、出力の160ビットがあります。 160ビット以下の攻撃抵抗のキーを引き出すために、SHA(DHkey)は良い対称鍵を生産します。
Suppose one wants a key with attack resistance of 160 bits, but it is to be used with a cipher that uses 192 bit keys. One can iterate SHA-1 as follows:
人が160ビットの攻撃抵抗があるキーが欲しいのですが、それが192ビットのキーを使用する暗号と共に使用されるつもりであるなら。 1つは以下のSHA-1を繰り返すことができます:
Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00)
(that is, concatenate a single octet of value 0x00 to
the right side of the DHkey, and then hash)
Bits 161-192 of the symmetric key = K2 =
select_32_bits(SHA(K1 | 0x01))
対称鍵=ケーツー=のSHA(DHkey| 0×00)(すなわち、DHkeyの右側への価値0x00のただ一つの八重奏を連結して、次に、細切れ肉料理を連結する)対称鍵のビット1-160=K1=ビット161-192は_32_ビットを選択します。(SHA(K1| 0×01))
But what if one wants 192 bits of strength for the cipher? Then the appropriate calculation is
しかし、人が暗号のために強さの192ビットが欲しい場合、どうなるでしょうか? そして、適切な計算はそうです。
Bits 1-160 of the symmetric key = SHA(0x00 | DHkey)
Bits 161-192 of the symmetric key =
select_32_bits(SHA(0x01 | DHkey))
対称鍵=のSHA(0×00| DHkey)対称鍵のビット1-160=ビット161-192は_32_ビットを選択します。(SHA(0×01| DHkey))
(Note that in the description above, instead of concatenating a full octet, concatenating a single bit would also be sufficient.)
(また、完全な八重奏を連結することの代わりに上の記述に、1ビットを連結するのも十分であることに注意してください。)
Orman & Hoffman Best Current Practice [Page 18] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[18ページ]RFC3766
The important distinction is that in the second case, the DH key is used for each part of the symmetric key. This assures that entropy of the DH key is not lost by iteration of the hash function over the same bits.
大切な区別は2番目の場合に、DHキーが対称鍵の各部分に使用されるということです。 これは、DHキーのエントロピーがハッシュ関数の繰り返しで同じビットの上失われていないことを保証します。
From an efficiency point of view, if the symmetric key must have a great deal of entropy, it is probably best to use a cryptographic hash function with a large output block (192 bits or more), rather than iterating a smaller one.
効率観点から、対称鍵に多くのエントロピーがなければならないなら、より小さいものを繰り返すよりむしろ大きい出力ブロック(192ビット以上)がある暗号のハッシュ関数を使用するのはたぶん最も良いです。
Newer hash algorithms with longer output (such as SHA-256, SHA-384, and SHA-512) can be used with the same level of security as the stretching algorithm described above.
ストレッチングアルゴリズムが上で説明したようにセキュリティの同じレベルと共に、より長い出力(SHA-256や、SHA-384や、SHA-512などの)がある、より新しい細切れ肉料理アルゴリズムを使用できます。
4.6. Importance of randomness
4.6. 偶発性の重要性
Some of the calculations described in this document require random inputs; for example, the secret Diffie-Hellman exponents must be chosen based on n truly random bits (where n is the system security requirement). The number of truly random bits is extremely important to determining the strength of the output of the calculations. Using truly random numbers is often overlooked, and many security applications have been significantly weakened by using insufficient random inputs. A much more complete description of the importance of random numbers can be found in [ECS].
本書では説明された計算のいくつかが無作為の入力を必要とします。 例えば、本当に無作為のnビット(nがシステムセキュリティ要件であるところ)に基づいて秘密のディフィー-ヘルマン解説者を選ばなければなりません。 本当に無作為のビットの数は計算の出力の強さを測定するのに非常に重要です。 本当に、乱数を使用するのはしばしば見落とされます、そして、多くのセキュリティアプリケーションが、不十分な無作為の入力を使用することによって、かなり弱められました。 [ECS]で乱数の重要性のはるかに完全な記述を見つけることができます。
5. Conclusion
5. 結論
In this table it is assumed that attackers use general purpose computers, that the hardware is purchased in the year 2000, and that mathematical knowledge relevant to the problem remains the same as today. This is an pure "apples-to-apples" comparison demonstrating how the time for a key exchange scales with respect to the strength requirement. The subgroup size for DSA is included, if that is being used for supporting authentication as part of the protocol; the DSA modulus must be as long as the DH modulus, but the size of the "q" subgroup is also relevant.
このテーブルでは、攻撃者が汎用計算機を使用して、2000年の間ハードウェアを購入して、問題に関連している数学の知識が今日として同じままでいると思われます。 これは主要な交換のための時間が強度要件に関してどう比例するかを示す純粋な「りんごからりんご」比較です。 それがプロトコルの一部として認証を支持するのに使用されているなら、DSAのためのサブグループサイズは含まれています。 DSA係数はDH係数と同じくらい長いに違いありませんが、また、「q」サブグループのサイズも関連しています。
Orman & Hoffman Best Current Practice [Page 19] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[19ページ]RFC3766
+-------------+-----------+--------------+--------------+ | System | | | | | requirement | Symmetric | RSA or DH | DSA subgroup | | for attack | key size | modulus size | size | | resistance | (bits) | (bits) | (bits) | | (bits) | | | | +-------------+-----------+--------------+--------------+ | 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 | +-------------+-----------+--------------+--------------+
+-------------+-----------+--------------+--------------+ | システム| | | | | 要件| 左右対称| RSAかDH| DSAサブグループ| | 攻撃のために| 主要なサイズ| 係数サイズ| サイズ| | 抵抗| (ビット) | (ビット) | (ビット) | | (ビット) | | | | +-------------+-----------+--------------+--------------+ | 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 | +-------------+-----------+--------------+--------------+
5.1. TWIRL Correction
5.1. 回転修正
If the TWIRL machine becomes a reality, and if there are advances in parallelism for row reduction in factoring, then conservative estimates would subtract about 11 bits from the system security column of the table. Thus, in order to get 89 bits of security, one would need an RSA modulus of about 1900 bits.
TWIRLマシンが現実のものになって、進歩が因数分解の列の減少のための平行関係にあれば、内輪な見積りはテーブルに関するシステムセキュリティコラムからおよそ11ビットを引き算するでしょう。 したがって、セキュリティの89ビットを手に入れるために、人はおよそ1900ビットのRSA係数を必要とするでしょう。
6. Security Considerations
6. セキュリティ問題
The equations and values given in this document are meant to be as accurate as possible, based on the state of the art in general purpose computers at the time that this document is being written. No predictions can be completely accurate, and the formulas given here are not meant to be definitive statements of fact about cryptographic strengths. For example, some of the empirical results used in calibrating the formulas in this document are probably not completely accurate, and this inaccuracy affects the estimates. It is the authors' hope that the numbers presented here vary from real world experience as little as possible.
本書では与えられた方程式と値は、できるだけ正確であることが意味されて、このドキュメントが書かれている時に目的コンピュータを一般に、到達技術水準に基礎づけました。 どんな予測も完全に正確であるというわけではない場合があります、そして、ここに与えられた定石は暗号の強さに関する事実の決定的な声明であることが意味されません。 例えば、定石を較正する際に使用される実証的な結果のいくつかがたぶん本書では完全に正確であるというわけではありません、そして、この不正確は見積りに影響します。 ここに提示された数が本当の世界経験とできるだけ少ししか異ならないのは、作者の望みです。
7. References
7. 参照
7.1. Informational References
7.1. 情報の参照
[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.
[DL] ダドソン、B.、およびA.K.Lenstra、4が大きいNFSは以下を用意します。 爆発的実験、Proceedings Crypto95、ComputのLecture Notes。 Sci。 963, (1995) 372-385.
[ECS] Eastlake, D., Crocker, S. and J. Schiller, "Randomness
Recommendations for Security", RFC 1750, December 1994.
[ECS] イーストレークとD.とクロッカーとS.とJ.シラー、「セキュリティのための偶発性推薦」、RFC1750、1994年12月。
Orman & Hoffman Best Current Practice [Page 20] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[20ページ]RFC3766
[GIL98] Cracking DES: Secrets of Encryption Research, Wiretap
Politics & Chip Design , Electronic Frontier Foundation,
John Gilmore (Ed.), 272 pages, May 1998, O'Reilly &
Associates; ISBN: 1565925203
[GIL98]分解DES: Encryption Research、Wiretap PoliticsとChip Design、電子フロンティア財団、272ページのジョン・ギルモア(エド)、1998年5月オライリーと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.
[GOR93] ゴードン、D.、「ナンバーフィールドふるいを使用するGF(p)の離散対数」、Discrete Mathematics、6のシャムJournal(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.
[LEN93]LenstraとA.K.とH.W.Lenstra、Jr.(eds)、数の開発はMath、1554年、Springer Verlag、ベルリン1993年にふるい、Lecture Notesをさばきます。
[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.
[MH81] Merkle、R.C.とヘルマン、「複数の暗号化のセキュリティ」のACM、vのM.Communications。 24 n。 7 1981、ページ 465-467.
[ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The
Future of Integer Factorization, A. M. Odlyzko
[ODL95]RSA研究室Cryptobytes、ボリューム1、No.2--1995年夏。 整数縮約、A.M.Odlyzkoの未来
[ODL99] A. M. Odlyzko, Discrete logarithms: The past and the
future, Designs, Codes, and Cryptography (1999).
[ODL99] A.M.Odlyzko、Discrete対数: 過去、未来、Designs、Codes、およびCryptography(1999)。
[POL78] J. Pollard, "Monte Carlo methods for index computation
mod p", Mathematics of Computation, 32 (1978), 918-924.
[POL78]J.Pollard、「インデックス計算モッズpのためのモンテカルロ方法」、Computation、32のMathematics(1978)、918-924。
[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange
(IKE)", RFC 2409, November 1998.
[RFC2409]ハーキンとD.とD.個人閲覧室、「インターネット・キー・エクスチェンジ(IKE)」、RFC2409 1998年11月。
[SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic
Curve Systems, In Don Coppersmith, editor, Advances in
Cryptology -- CRYPTO 31 August 1995. Springer-Verlag
[SCH95] R.Schroeppel、他、Fast Key Exchange With Elliptic Curve Systems、InドンCoppersmith、エディタ、CryptologyのAdvances--CRYPTO1995年8月31日。 追出石-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.
[SHAMIR03]シャミル(「回転装置で大きい数を因数分解する」アディとEran Tromer)は、暗号理論で進みます--よりバネであることの暗号2003はコンピュータサイエンス2729での注意について講義します。
[SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 -
April 2000, A Cost-Based Security Analysis of Symmetric
and Asymmetric Key Lengths
[SIL00]R.D.シルバーマン、RSA研究所報告、No.13--2000年4月、左右対称の、そして、非対称のキー長の費用ベースの証券分析
[SILIEEE99] R. D. Silverman, "The Mythical MIPS Year", IEEE Computer,
August 1999.
1999年8月の[SILIEEE99]R.D.シルバーマン、「神話のMIPS年」IEEEコンピュータ。
Orman & Hoffman Best Current Practice [Page 21] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[21ページ]RFC3766
8. Authors' Addresses
8. 作者のアドレス
Hilarie Orman Purple Streak Development 500 S. Maple Dr. Salem, UT 84653
Hilarie Ormanは一続きの開発500秒間ユタ カエデ礼拝堂博士、84653を紫色にします。
EMail: hilarie@purplestreak.com and ho@alum.mit.edu
メール: おーい、 hilarie@purplestreak.com と@alum.mit.edu
Paul Hoffman VPN Consortium 127 Segre Place Santa Cruz, CA 95060 USA
ポールホフマンVPN共同体127セグレ・Placeカリフォルニア95060サンタクルス(米国)
EMail: paul.hoffman@vpnc.org
メール: paul.hoffman@vpnc.org
Orman & Hoffman Best Current Practice [Page 22] RFC 3766 Determining Strengths for Public Keys April 2004
2004年4月に公開鍵のために強さを測定するOrmanとホフマン最も良い現在の習慣[22ページ]RFC3766
9. Full Copyright Statement
9. 完全な著作権宣言文
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.
Copyright(C)インターネット協会(2004)。 このドキュメントはBCP78に含まれた権利、ライセンス、および制限を受けることがあります、そして、そこに詳しく説明されるのを除いて、作者は彼らのすべての権利を保有します。
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.
このドキュメントと「そのままで」という基礎と貢献者、その人が代表する組織で提供するか、または後援されて、インターネット協会とインターネット・エンジニアリング・タスク・フォースはすべての保証を放棄します、と急行ORが含意したということであり、他を含んでいて、ここに含まれて、情報の使用がここに侵害しないどんな保証も少しもまっすぐになるという情報か市場性か特定目的への適合性のどんな黙示的な保証。
Intellectual Property
知的所有権
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.
IETFはどんなIntellectual Property Rightsの正当性か範囲、実現に関係すると主張されるかもしれない他の権利、本書では説明された技術の使用またはそのような権利の下におけるどんなライセンスも利用可能であるかもしれない、または利用可能でないかもしれない範囲に関しても立場を全く取りません。 または、それはそれを表しません。どんなそのような権利も特定するためのどんな独立している努力もしました。 BCP78とBCP79でRFCドキュメントの権利に関する手順に関する情報を見つけることができます。
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.
IPR公開のコピーが利用可能に作られるべきライセンスの保証、または一般的な免許を取得するのが作られた試みの結果をIETF事務局といずれにもしたか、または http://www.ietf.org/ipr のIETFのオンラインIPR倉庫からこの仕様のimplementersかユーザによるそのような所有権の使用のために許可を得ることができます。
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.
IETFはこの規格を実行するのに必要であるかもしれない技術をカバーするかもしれないどんな著作権もその注目していただくどんな利害関係者、特許、特許出願、または他の所有権も招待します。 ietf-ipr@ietf.org のIETFに情報を記述してください。
Acknowledgement
承認
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC Editor機能のための基金は現在、インターネット協会によって提供されます。
Orman & Hoffman Best Current Practice [Page 23]
OrmanとホフマンBest現在の習慣[23ページ]
一覧
スポンサーリンク
