[要約] RFC 3766は、対称鍵を交換するために使用される公開鍵の強度を決定する方法に関するガイドラインを提供します。この文書の目的は、セキュリティレベルを確保するために必要な公開鍵の最小サイズを推奨することです。
Network Working Group H. Orman
Request for Comments: 3766 Purple Streak Dev.
BCP: 86 P. Hoffman
Category: Best Current Practice VPN Consortium
April 2004
Determining Strengths For Public Keys Used For Exchanging Symmetric Keys
対称鍵の交換に使用される公開鍵の強度を決定する
Status of this 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.
このドキュメントは、インターネットコミュニティのためのインターネットの最良の現在の慣行を指定し、改善のための議論と提案を要求します。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (2004). All Rights Reserved.
著作権（C）インターネットソサエティ（2004）。全著作権所有。
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.
システム強度要件を対称鍵長の観点から表現し、その要件以上の鍵長を持つ暗号を選択することはかなり容易ですが、対称鍵強度要件を満たす暗号強度を持つ公開鍵を選択することはより困難です。この文書では、対称鍵強度要件の関数として非対称鍵の長さを決定する方法について説明します。様々なアルゴリズムに対する大規模攻撃への等価な耐性を推定するためのいくつかの経験則が示されています。この文書では、基礎となる大きな整数（モジュラス、群のサイズ、指数など）のサイズを変更することが、鍵交換アルゴリズムの使用時間にどのように影響するかについても扱います。
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
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 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つの選択肢があります。正面玄関の錠を攻撃するか、鍵を取り出すためにロックボックスの錠を攻撃するかです。明らかに、泥棒は2つの錠のうち弱い方を攻撃するほうが有利です。この状況で家の所有者は、泥棒の仕事を楽にしないために、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つ目の考慮事項は、ユーザーの最小限のセキュリティ要件です。ユーザーがCAST-128で暗号化を行っており、総当たり攻撃に対して20年間の耐用期間を持つ対称鍵を必要としていると仮定します。彼はまず86ビットのランダムなビットを持つ鍵を選択し、SHA-1などの一方向関数を使用してそれを160ビットのブロックに「ブースト」し、そのうちの128ビットをCAST-128の鍵として使用するかもしれません。そのような場合、鍵交換アルゴリズムは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. アプリケーションのセキュリティ要件を満たすために必要な攻撃耐性を決定します。これを行うには、システムのセキュリティを侵害するために攻撃者が強いられるコンピュータ操作の最小回数を推定し、その数の2を底とする対数を取ります。その対数値を "n" と呼びます。
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ビットという数値は、1年あたり約2/3ビットずつ増やす必要があり、2005年には約96ビットになります。
2. Choose a symmetric cipher that has a key with at least n bits and at least that much cryptanalytic strength.
2. 少なくともnビットの鍵を持ち、少なくともそれと同等の暗号解読強度を持つ対称暗号を選択してください。
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ビットの攻撃耐性を持つ認証アルゴリズムを選択してください。これにより、暗号化されたデータの機密保持期間中に、二者間で同様の鍵交換を偽造できないことが保証されます。認証鍵が頻繁に変更され、その使用寿命が十分に理解されている場合、これは厳密には必要ないかもしれませんが、そうでない場合、nビットの指針は妥当です。
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.
Diffie-Hellman法は、群、生成元、および指数を使用します。今日のインターネット標準では、群演算はモジュラー乗算に基づいています。ここで、群は整数の乗法群、典型的には素数 p = 2q + 1（qは素数）によって定義され、演算はモジュロpで行われます。生成元（多くの場合、単に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.
Diffie-Hellmanでは、AliceとBobは最初に（公に、または秘密裏に）gとpの値について合意します。Aliceは秘密の大きなランダム整数（a）を選択し、Bobは秘密の大きなランダム整数（b）を選択します。AliceはBobにA（g^a mod p）を送信し、BobはAliceにB（g^b mod p）を送信します。次に、AliceはB^a mod pを計算し、BobはA^b mod 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].
Diffie-Hellman鍵交換は、異なる種類の群表現上で行うことができます。例えば、有限体上で定義された楕円曲線は、鍵交換を計算するための特に効率的な方法です[SCH95]。
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鍵交換の場合、Bobがp*qに等しい公開鍵（m）、暗号化指数e、および復号化指数dを持っていると仮定します。ここで、pとqは2つの秘密の素数です。鍵交換のために、AliceはBobにE = k^e mod mを送信します。ここで、kは交換される秘密の対称鍵です。BobはE^d mod mを計算することでkを復元し、両者はkを対称鍵として使用します。Bobの暗号化指数eは非常に小さい（例えば17ビット）場合がありますが、復号化指数dはmと同じくらいのビット数を持ちます。
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ビットあり、推測すべき可能性が多すぎるため、総当たり推測攻撃に対して安全です。Diffie-Hellman交換も、指数がそこから導出される対称鍵の少なくとも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モジュラスを素因数分解すると、秘密鍵のセキュリティが完全に侵害されます。Diffie-Hellmanモジュラー指数システムに対する離散対数問題を解くと、特定のモジュラスを使用したすべての鍵交換のセキュリティが同様に破壊されます。この文書では、離散対数問題を解く難易度は、モジュラスと同じサイズの数値を素因数分解する難易度と同等であると仮定しています。実際には、より多くの演算が必要なため、少し困難です。これまでの経験的証拠に基づくと、難易度の比率は少なくとも20、おそらく64にもなります。どちらの問題を解決する場合でも、アルゴリズムの最終段階である行列簡約ステップで大量のメモリが必要になります。このメモリ要件が、より大きな整数の問題を解決する際の制限要因であり続けるかどうかは、まだ分かりません。現時点ではそうではなく、この問題のメモリ要件を軽減する可能性のある並列行列アルゴリズムに関する活発な研究が行われています。
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]は、今日、離散対数問題を解くための最良の方法です。NFS法を使用して整数nを素因数分解するために必要な単純な算術演算の数を推定する式は次のとおりです。
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 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.
多くの人々は、数体篩法などの大規模な演算に必要なMIPS年（MYs）の数について議論することを好みます。このような推定のために、L(n)式の1演算は1コンピュータ命令とします。経験的証拠は、4または5命令がより近い一致かもしれないことを示していますが、これは些細な要素であり、この文書ではこの議論のために1演算/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
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.
これらの素因数分解に使用された時間の正確な測定値はほとんどありません。ほとんどの素因数分解テストでは、数百または数千台のコンピュータが数ヶ月間にわたって使用されますが、素因数分解プロジェクトに費やされたサイクル数、プロセッサの種類や速度の正確な分布などは通常報告されません。しかし、上記のすべての場合において、費やされた労力は、kが1でo(1)が0の場合にL(n)式が予測するものよりもはるかに少ないものでした。
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].
数体篩法による素因数分解において、実際の演算数が予想よりも少ないことを示す結果が[DL]にあります。
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)の単純な適用（つまり、kを1、o(1)を0に設定）によって示唆されるものよりも約5または6ビット低いことを意味します。これらのkの推定値は、表で報告されている数値全体でかなり安定しています。この推定値は、実際の不確実性を表すため、kの有効数字1桁に制限されています。ただし、桁数を増やしても、推奨される鍵サイズにはごくわずかな変更しか生じません。
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の素因数分解を行った人々は約1700 MYsを使用しましたが、予測目的としてはこれが非現実的に高いと感じていました。マシンでより多くのメモリを使用すれば、時間を500 MYsに容易に短縮できたはずだからです。したがって、上記の表の作成に使用された値は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進数の素因数分解について議論する場合、L(n)式はo(1)項を0に設定し、kを0.02に設定して使用できるようです。式は次のようになります。
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:
L(n)を単純な数学命令からMYsに変換するには、3*10^13で割ります。整数nを素因数分解するために必要なMYsの数の式は、次のようになります。
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.
わずかに大きな数の素因数分解の難易度を予測するために、この式はどの程度の信頼性で使用できるでしょうか？答えは、それは近い上限になるはずですが、各素因数分解の取り組みは通常、アルゴリズムまたはその実装の何らかの改善によって特徴付けられ、実行時間は式が示すよりもいくらか短くなるということです。
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 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.
Diffie-Hellman交換には、2番目の攻撃であるポラードのρ法[POL78]があります。このアルゴリズムは、大きな数空間で計算された値間の衝突を見つけることに依存しており、その成功率は空間のサイズの平方根に比例します。ポラードのρ法があるため、DH鍵交換における鍵（g^a項の指数）の探索空間は、対称鍵の2倍の大きさでなければなりません。したがって、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.
楕円曲線法を使用してDiffie-Hellman鍵交換を行う場合、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.
離散対数攻撃に実際に必要なコンピュータ命令数と、暗号の鍵空間を探索するのに必要な数をどのように比較できるのか、と疑問に思うかもしれません。労力を比較する際には、「基本演算」が何であるかを考慮する必要があります。DESのような対称暗号アルゴリズムの鍵空間の総当たり探索の場合、基本演算は鍵設定と1回の暗号化を行う時間です。離散対数の場合、基本演算はモジュラー二乗演算です。これら2つの演算の比率の対数は、2種類の計算間の「正規化係数」として使用できます。しかし、非常に大きなモジュラス（16Kビット）であっても、この係数はわずか数ビットの追加労力にしかなりません。
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 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).
最良の素因数分解方法は、データ関係の収集（篩い分け）のために多くのランダムアクセスメモリと、大きな行列の行簡約を行う重要な最終ステップを必要とします。メモリ要件は、素因数分解される（または離散対数解法の対象となる）数のサイズに関連しています。Silverman [SILIEEE99] [SIL00]は、予見可能な将来において、単一の問題に投入できるマシンの数とRAMの量には実用的な限界があると主張しています。彼は1024ビットRSAモジュラスへの攻撃において2つの問題を見ています。篩い分けを行うマシンは64ビットのアドレス空間を必要とし、行列行簡約マシンは数テラバイトのメモリを必要とすることです。Silvermanは、篩い分けに必要な170ギガバイトのメモリを搭載した64ビットマシンはほとんど販売されていないと指摘しています。妥当な時間（1、2年）で篩い分けを行うには、そのようなマシンが約10億台必要です。
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.
素因数分解の取り組みの歴史とムーアの法則に基づくSilvermanの結論は、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.
実用的な考慮事項を大いに重視すべきですが、リスク分析において、物理的な世界はトレンドグラフが示すよりも予測不可能です。コンピュータ業界が素因数分解を行う人々の貪欲なニーズを満たすことができないという点にどれだけの信頼を置くかを検討する際には、素因数分解の数学よりも複雑な経済的考慮事項についてある程度の洞察が必要です。コンピュータメモリの需要はアプリケーションに基づいているため、予測が困難です。「キラーアプリ」がいつ登場し、メモリ業界を販売の熱狂に巻き込むか分かりません。デスクトップで利用可能なプロセッサの数は机の数によって制限されるかもしれませんが、非常に高性能な組み込みシステムはデスクトップよりも多くのプロセッサ販売を占めています。組み込みシステムがネットワーク機能を吸収するにつれて、少なくともギガバイト単位のメモリを持つ数百万個の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.
これに関する結論は、理論によって予測された鍵長の推奨事項は過度に保守的である可能性がありますが、この文書ではそれらを使用しているということです。マシンの可用性というこの問題は、現在の技術に照らして定期的に再検討されるべきです。
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コンポーネントを並列に適用することで、このようなマシンは、ハードウェアコスト1万ドルで512ビット数の篩い分けを10分で実行できる可能性があります。より大きなバージョンでは、1000万ドルのコストで1024ビット数を1年で篩いにかけることができるでしょう。この研究は、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万倍のスピードアップに相当します。
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.
このセクションでは、アルゴリズムを使用して鍵交換を実行するのにかかる時間について説明します。繰り返しますが、公開鍵の長さを増やす場合、対称鍵の交換にかかる時間の増加を考慮することが重要です。実用的でないほど長い公開鍵を選択しないようにすることが重要です。
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.
Diffie-Hellman鍵交換は、生成元gと指数xを持つ有限巡回群Gを用いて行われます。ポラードのρ法のセクションで述べたように、指数は最終的な鍵に必要なビット数の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回の二乗と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.
二乗演算は、乗算ほど多くの演算を使用する必要はありません。妥当な見積もりは、二乗は乗算の機械命令数の0.6倍かかるというものです。生成元gの小さな整数乗の値をいくつか含むテーブルを事前に用意しておけば、単純な式が示唆するよりも約5分の1の乗算で済みます。したがって、nワード×nワードの数の約0.8*K回の乗算に相当する作業を行う必要があります。さらに、各乗算と二乗の後にはモジュラー簡約を行う必要があり、モジュラー簡約を行うのはnワード×nワードの乗算を行うのと同じくらい難しいと仮定するのが妥当です。したがって、二乗のためにK回の簡約、乗算のために0.2*K回の簡約が必要です。これを合計すると、Kビットの指数とnワードのモジュラスを持つDiffie-Hellman鍵交換の総労力は、約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ワード乗算に対して少なくともn^2命令を必要とします。より大きな数はKaratsuba乗算を使用することで時間を短縮し、より大きなnに対して約n^(1.58)としてスケールしますが、現在の議論では無視します。64ビットプロセッサでは、「Karatsuba法の分岐点」となる数値がさらに多くのビット数になることに注意してください。
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.
基本的な結果は次のとおりです。Diffie-Hellmanモジュラー指数群のサイズを2倍にすると、計算に必要な演算数は4倍になります。
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:
モジュラスサイズの関数としての計算労力の比率は、Diffie-Hellmanに楕円曲線（EC）群を使用している場合でも成り立つことに注意してください。ただし、同等のセキュリティであれば、楕円曲線の場合はより小さな数値を使用できます。誰かがDiffie-Hellmanアプリケーションの適切なセキュリティ対策として2048ビットのモジュラスを持つモジュラー指数群を選択し、代わりにEC群を使用することにどのような利点があるかを判断したいと仮定します。平均して、EC群での二乗または乗算はモジュラー指数群よりも約20倍の労力を要すると仮定すれば、計算は比較的簡単です。大まかな見積もりでは、同等のセキュリティを持つEC群は、その表現において約200ビットです。そして、時間がnワード×nワード演算によって支配されると仮定すると、相対時間は次のように計算されます。
((2048/200)^2)/20 ~= 5
showing that an elliptic curve implementation should be five times as fast as a modular exponentiation implementation.
楕円曲線の実装は、モジュラー指数の実装の5倍高速であることを示しています。
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ワード演算を使用して、わずか16回の二乗と1回の乗算しか含まれない場合があります。各演算の後にはモジュラー簡約を行う必要があるため、時間計算量は約 16*(0.6 + 1) + 1 + 1 ≒ 28回のnワード×nワード乗算となります。
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ビットを持つ指数を使用する必要があります。しかし、中国の剰余定理が適用されるため、すべての計算はわずかn/2ワードのモジュラスとj/2ビットの指数で行うことができます。計算は各因数に対して1回ずつ、計2回行う必要があります。労力は 2*(j/2)回の(n/2 × n/2)ワード乗算に相当します。n/2ワードの数の乗算はnワードの数の乗算の4分の1の難しさで済むため、RSA復号化の等価労力は j/4回のnワード×nワード乗算となります。
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.
RSAのモジュラスのサイズを2倍にすると、n×n乗算には4倍の時間がかかります。さらに、指数が大きくなるため、復号化時間は2倍になります。全体的なスケーリングコストは、暗号化では4倍、復号化では8倍になります。
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の復号化側）について非公式に報告された最良の時間は、500 MHz Itaniumプロセッサで0.9ミリ秒（約45万CPUサイクル）です。これは、新しいプロセッサが大きな数の演算において遅れをとっていないことを示しています。命令数は、32ビットプロセッサが256ビットのモジュラー指数に使用するものよりも少ないです。
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.
それほど高度でないプロセッサのタイミングについては、Diffie-Hellman鍵交換で行われるようなモジュラー指数に関する次の2つの表（SSH CommunicationsのTero Monenenによる計算）を参照してください。
Celeron 400 MHz; compiled with GNU C compiler, optimized, some platform specific coding optimizations:
Celeron 400 MHz。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
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]からのもので、モジュラー指数（「MOD」）または楕円曲線（「ECN」）のいずれかです。こちらと後続のテーブルのすべてのサイズはビットです。
Alpha 500 MHz compiled with Digital's C compiler, optimized, no platform specific code:
Alpha 500 MHzはデジタルの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
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つの表（Eric Youngによって計算された）は、もともと中国剰余表現を使用した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
Alpha 264 600mhz:
Alpha 264 600MHz：
equiv equiv equiv
modulus exponent time
size size
512 512 1.4 ms
Recent chips that accelerate exponentiation can perform 1024-bit exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 milliseconds or less.
べき乗演算を加速する最近のチップは、1024ビットのべき乗演算（1024ビットのモジュラス、1024ビットの指数）を約3ミリ秒以下で実行できます。
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 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.
特定の対称鍵を保護するためにどれほど強力な公開鍵が必要かを判断するには、まず対称鍵を破るためにどれだけの労力が必要かを判断する必要があります。多くのインターネットセキュリティプロトコルでは、強力な対称暗号化のためにTripleDESの使用が要求されており、今後数年間でAdvanced Encryption Standard（AES）がインターネット上で採用されると予想されます。したがって、ここではこれら2つのアルゴリズムについて説明します。このセクションでは、説明のために、システムセキュリティ要件が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鍵をテストできるDES解読機[GIL98]を13万米ドルで構築しました（マシンの設計には追加の資金が費やされました）。マシンの製作者は、マシンが十分に最適化されていないことを完全に認めており、10倍の資金があれば、おそらく約50倍高速なマシンを作成できると推定されています。TripleDES鍵をテストするシステムがDES鍵をテストするシステムと同じくらい高速に動作すると推測してさらなる最適化を仮定すると、約100万米ドルで毎秒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個の鍵をテストできると仮定したいかもしれません。この非常に高価なシステムを使用して2^112個の鍵を持つ有効なTripleDES空間を徹底的に探索するには、約1e15秒、つまり約3300万年かかります。（このようなシステムには2^60バイトのRAM [MH81]も必要ですが、この計算では無料とみなされることに注意してください）。これは不必要に保守的な値のように思えます。しかし、コンピュータのロジック速度がムーアの法則（1.5年ごとに速度が2倍になる）に従って増加し続けると、約50年後には、計算がわずか1年で完了すると予想されるかもしれません。説明のために、この大富豪に対する50年間の耐性が、ある一連のアプリケーションの最小セキュリティ要件であると仮定します。
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.) 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.
112ビットの攻撃耐性がシステムセキュリティ要件である場合、TripleDESのための鍵交換システムは同等の難易度を持つべきです。つまり、攻撃者が1兆ドルを持っている場合、彼が今日ハードウェアを買うためにすべてのお金を使い、3300万年以上かけないと鍵交換を「解読」できないようにしたいのです。（明らかに、合理的な攻撃者は、実際にお金を費やす前に約45年間待つでしょう。そうすればはるかに優れたハードウェアを入手できるからです。しかし、すべての攻撃者はこの種の待ち時間から等しく恩恵を受けます。）数年前の典型的なPC CPUは500 MIPS以上を生成でき、大量購入すれば約100米ドルで購入できると推定されています。したがって、1ドルあたり5 MIPS以上が得られます。繰り返しますが、この数は約18ヶ月ごとに倍増します。1兆米ドルあれば、攻撃者はその最近のハードウェア上で5e12 MIPS年のコンピュータ命令を得ることができます。この数値は、鍵交換システムを破るための等価コストの以下の推定で使用されます。
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:
大富豪の攻撃者が、専用マシンが対称鍵の総当たり探索に費やすのと同じ時間で、従来のCPUを使用して112ビット鍵の鍵交換を「解読」しようとする場合、鍵交換システムは適切に大きなモジュラスを使用しなければなりません。大富豪は年間5e12 MIPSの命令を実行すると仮定します。RSA暗号化またはDH鍵交換で使用するモジュラスサイズを推定するには、次の式を使用してください。
5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
nについて近似的に解くと：
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ビットのモジュラスを使用すべきであることを示しています。Diffie-Hellman鍵交換の場合、わずかに小さいモジュラスを使用できますが、大きな違いはありません。
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を使用してデータのブロックを暗号化するためのCPU命令数は300であると仮定します。112ビットのTripleDES鍵を破るための推定コンピュータ命令数は次のとおりです。
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)
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攻撃の場合、約2400ビットのモジュラスは、112ビットのTripleDES鍵と攻撃に対してほぼ同じ強度を持つと想定できます。これは、RSA公開鍵暗号化が約2400ビットのモジュラスを使用すべきであることを示しています。Diffie-Hellman鍵交換の場合、わずかに小さいモジュラスを使用できますが、大きな違いはありません。
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.
数体篩法の基礎となるアルゴリズムが時間の経過とともに改善され続けると仮定する著者もいることに注意してください。これらの著者は、112ビットの対称鍵を50年間保護するために、4000ビットを超えるさらに大きなモジュラスを推奨しています。これは、長期的な暗号セキュリティの難しさを指摘しています。これほど長期間にわたる数学と物理学の進歩を予測することはほぼ不可能です。
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
大富豪が今日ハードウェアを購入するためにお金を使うと仮定して、1年間でどのようなサイズの鍵交換数を「解読」できるでしょうか？彼は5*e12 MYsの命令を実行できます。つまり、
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)
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年間の機密保持要件を持つデータを保護する場合、80ビットの対称鍵を保護する約1200ビットの鍵交換モジュラスは、国家の資源に対しても安全です。
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 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.
この論理をAESに拡張することは簡単です。鍵探索の推定の目的のために、128ビットAESはTripleDESよりも少なくとも16ビット強力ですが、約3倍高速であると考えることができます。総当たり攻撃の時間とコストはTripleDESよりも約2^(16)倍多くなります。したがって、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暗号は、128ビットから最大256ビットの鍵サイズを持っています。慎重な最小セキュリティ要件、したがって鍵交換モジュラスも同様の強度を持つべきでしょうか？これに対する答えは、ムーアの法則が衰えることなく続くかどうかに依存します。もし続くなら、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とVerheulのWebベースの論文「Selecting Cryptographic Key Sizes」は、この文書よりも保守的な分析を選択しています。
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?
Diffie-Hellmanアルゴリズムは、数百または数千のビットの長さのキーをもたらしますが、暗号はそれよりはるかに少ないビットを必要とします。強度を失うことなく、短いキーを短い方に蒸留するにはどうすればよいですか。
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.
暗号学的ハッシュ関数はこれのための構成要素であり、対称鍵の各ブロックを導出するためにDiffie-Hellman鍵のすべてを使用する限り、十分な強度を持つ鍵を生成します。
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ビットキーを使用する暗号で使用されます。次のように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))
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))
(Note that in the description above, instead of concatenating a full octet, concatenating a single bit would also be sufficient.) 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など）を備えた新しいハッシュアルゴリズムは、上記のストレッチアルゴリズムと同じレベルのセキュリティで使用できます。
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].
この文書で説明されている計算のいくつかはランダムな入力を必要とします。たとえば、秘密のDiffie-Hellman指数は、n個の真にランダムなビットに基づいて選択する必要があります（ここで、nはシステムセキュリティ要件です）。真にランダムなビットの数は、計算出力の強度を決定する上で非常に重要です。真の乱数を使用することはしばしば見落とされ、不十分なランダム入力を使用することによって多くのセキュリティアプリケーションが大幅に弱体化されてきました。乱数の重要性に関するより完全な説明は[ECS]にあります。
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」サブグループのサイズも重要です。
+-------------+-----------+--------------+--------------+
| 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 |
+-------------+-----------+--------------+--------------+
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モジュラスが必要になります。
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.
この文書に記載されている式および値は、この文書が執筆された時点での汎用コンピュータにおける最新技術に基づいて、可能な限り正確であることを意図しています。どのような予測も完全に正確ではあり得ず、ここに示された式は、暗号強度に関する事実の決定的な声明であることを意図したものではありません。たとえば、この文書の式を校正するために使用された経験的結果の一部はおそらく完全に正確ではなく、この不正確さが推定値に影響を与えます。著者は、ここに提示された数値が現実世界の経験とできるだけ乖離しないことを望んでいます。
[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] Dodson、B.およびA. K.Lenstra、4つの大きな素数を用いたNFS：爆発的実験、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, December 1994.
[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, May 1998, O'Reilly & Associates; ISBN: 1565925203
[GIL98] Cracking DES：暗号化研究の秘密、盗聴政治＆チップ設計、電子フロンティア財団、John Gilmore (Ed.)、272ページ、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.
[GOR93] Gordon, D., "数体篩法を使用したGF(p)の離散対数", 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.
[LEN93] Lenstra, A. K. and H. W. Lenstra, Jr. (eds), 数体篩法の開発, 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.
[MH81] Merkle, R.C., and Hellman, M., "多重暗号化のセキュリティについて", 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
[ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; 整数素因数分解の将来, A. M. Odlyzko
[ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, Designs, Codes, and Cryptography (1999).
[ODL99] A. M. Odlyzko, 離散対数：過去と未来, Designs, Codes, and Cryptography (1999)。
[POL78] J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of Computation, 32 (1978), 918-924.
[POL78] J. Pollard, "指数計算mod pのためのモンテカルロ法", Mathematics of Computation, 32 (1978), 918-924。
[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)", RFC 2409, November 1998.
[RFC2409] Harkins, D. and D. Carrel, "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 August 1995. Springer-Verlag
[SCH95] R. Schroeppel, et al., 楕円曲線システムを用いた高速鍵交換, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 31 August 1995. 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.
[SHAMIR03] Shamir, Adi and Eran Tromer, "TWIRLデバイスを用いた大きな数の素因数分解", Advances in Cryptology - CRYPTO 2003, Springer, Lecture Notes in Computer Science 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. Silverman, RSA Laboratories Bulletin, Number 13 - April 2000, 対称および非対称鍵長のコストベースのセキュリティ分析
[SILIEEE99] R. D. Silverman, "The Mythical MIPS Year", IEEE Computer, August 1999.
[SILIEEE99] R. D. Silverman, "神話上のMIPS年", IEEE Computer, 1999年8月。
Hilarie Orman Purple Streak Development 500 S. Maple Dr. Salem, UT 84653
Hilarie Orman Purple Streak開発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
Paul Hoffman VPNコンソーシアム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.
Copyright (C) The Internet Society (2004). 本文書は、BCP 78に含まれる権利、ライセンス、および制限の対象となり、そこに規定されている場合を除き、著者はすべての権利を保持します。
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.
この文書およびここに含まれる情報は「現状のまま」提供され、寄稿者、その代理人またはスポンサー（もしあれば）、インターネットソサエティ、およびIETF（Internet Engineering Task Force）は、明示または黙示を問わず、ここに含まれる情報の使用がいかなる権利も侵害しないという保証や、商品性または特定目的への適合性の黙示の保証を含むがこれらに限定されない、すべての保証を放棄します。
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は、この文書に記載された技術の実装または使用に関連すると主張される可能性のある知的財産権もしくはその他の権利の有効性または範囲、あるいはそのような権利に基づくライセンスが利用可能であるか否かに関していかなる立場もとらず、また、そのような権利を特定するために独自の調査を行ったことを表明するものでもありません。RFC文書の権利に関する手続きの情報は、BCP 78および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.
IETF事務局に行われたIPR開示のコピー、および利用可能になるライセンスの保証、またはこの仕様の実装者や利用者がそのような所有権を使用するための一般的なライセンスまたは許可を取得しようとした試みの結果は、IETFオンラインIPRリポジトリ（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.
IETFは、この規格の実装に必要となる可能性のある技術をカバーする可能性のある著作権、特許、特許出願、またはその他の所有権について、関心のある当事者が注意を喚起することを求めます。情報は ietf-ipr@ietf.org 宛てにIETFに送付してください。
Acknowledgement
謝辞
Funding for the RFC Editor function is currently provided by the Internet Society.
RFCエディタ機能のための資金は、現在インターネットソサエティによって提供されています。