[要約] RFC 4086は、セキュリティ目的で使用される乱数の生成に関する要件を定めた文書です。このRFCは、乱数がセキュリティプロトコルや暗号化技術において重要な役割を果たすことを説明し、高品質な乱数生成方法を推奨しています。利用場面には、セキュリティトークン、セッションキーの生成、デジタル署名などがあります。
Network Working Group D. Eastlake, 3rd
Request for Comments: 4086 Motorola Laboratories
BCP: 106 J. Schiller
Obsoletes: 1750 MIT
Category: Best Current Practice S. Crocker
June 2005
Randomness Requirements for Security
セキュリティのためのランダム性要件
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 (2005).
著作権（C）インターネット社会（2005）。
Abstract
概要
Security systems are built on strong cryptographic algorithms that foil pattern analysis attempts. However, the security of these systems is dependent on generating secret quantities for passwords, cryptographic keys, and similar quantities. The use of pseudo-random processes to generate secret quantities can result in pseudo-security. A sophisticated attacker may find it easier to reproduce the environment that produced the secret quantities and to search the resulting small set of possibilities than to locate the quantities in the whole of the potential number space.
セキュリティシステムは、パターン分析の試みへの耐性が強い暗号化アルゴリズム上に構築されています。ただし、これらのシステムのセキュリティは、パスワード、暗号鍵、および同様の量の秘密の数の生成に依存しています。秘密の数を生成するための疑似ランダムプロセスの使用は疑似セキュリティをもたらす可能性があります。洗練された攻撃者は、秘密数量を生み出した環境を再現し、潜在的な数の空間全体の数量を見つけることよりも結果として生じる小さな可能性を検索することがより容易になるかもしれません。
Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult. This document points out many pitfalls in using poor entropy sources or traditional pseudo-random number generation techniques for generating such quantities. It recommends the use of truly random hardware techniques and shows that the existing hardware on many systems can be used for this purpose. It provides suggestions to ameliorate the problem when a hardware solution is not available, and it gives examples of how large such quantities need to be for some applications.
機密性でやる気のある敵対者を箔にするためのランダムな量を選択することは驚くほど困難です。この文書は、エントロピー源やそのような量を生成するための伝統的な疑似乱数生成技術を使用する際の多くの落とし穴を指摘しています。それは真にランダムなハードウェア技術の使用を推奨し、多くのシステム上の既存のハードウェアをこの目的のために使用できることを示しています。ハードウェアソリューションが利用できない場合に問題を改善するための提案を提供し、そのような量の多くのアプリケーションに対してどのような数の量である必要があるかの例を示します。
Table of Contents
目次
1. Introduction and Overview .......................................3
2. General Requirements ............................................4
3. Entropy Sources .................................................7
3.1. Volume Required ............................................7
3.2. Existing Hardware Can Be Used For Randomness ...............8
3.2.1. Using Existing Sound/Video Input ....................8
3.2.2. Using Existing Disk Drives ..........................8
3.3. Ring Oscillator Sources ....................................9
3.4. Problems with Clocks and Serial Numbers ...................10
3.5. Timing and Value of External Events .......................11
3.6. Non-hardware Sources of Randomness ........................12
4. De-skewing .....................................................12
4.1. Using Stream Parity to De-Skew ............................13
4.2. Using Transition Mappings to De-Skew ......................14
4.3. Using FFT to De-Skew ......................................15
4.4. Using Compression to De-Skew ..............................15
5. Mixing .........................................................16
5.1. A Trivial Mixing Function .................................17
5.2. Stronger Mixing Functions .................................18
5.3. Using S-Boxes for Mixing ..................................19
5.4. Diffie-Hellman as a Mixing Function .......................19
5.5. Using a Mixing Function to Stretch Random Bits ............20
5.6. Other Factors in Choosing a Mixing Function ...............20
6. Pseudo-random Number Generators ................................21
6.1. Some Bad Ideas ............................................21
6.1.1. The Fallacy of Complex Manipulation ................21
6.1.2. The Fallacy of Selection from a Large Database .....22
6.1.3. Traditional Pseudo-random Sequences ................23
6.2. Cryptographically Strong Sequences ........................24
6.2.1. OFB and CTR Sequences ..............................25
6.2.2. The Blum Blum Shub Sequence Generator ..............26
6.3. Entropy Pool Techniques ...................................27
7. Randomness Generation Examples and Standards ...................28
7.1. Complete Randomness Generators ............................28
7.1.1. US DoD Recommendations for Password Generation .....28
7.1.2. The /dev/random Device .............................29
7.1.3. Windows CryptGenRandom .............................30
7.2. Generators Assuming a Source of Entropy ...................31
7.2.1. X9.82 Pseudo-Random Number Generation ..............31
7.2.2. X9.17 Key Generation ...............................33
7.2.3. DSS Pseudo-random Number Generation ................34
8. Examples of Randomness Required ................................34
8.1. Password Generation .......................................35
8.2. A Very High Security Cryptographic Key ....................36
9. Conclusion .....................................................38
10. Security Considerations ........................................38
11. Acknowledgments ................................................39
Appendix A: Changes from RFC 1750 ..................................40
Informative References .............................................41
Software cryptography is coming into wider use, although there is a long way to go until it becomes pervasive. Systems such as SSH, IPSEC, TLS, S/MIME, PGP, DNSSEC, and Kerberos are maturing and becoming a part of the network landscape [SSH] [IPSEC] [TLS] [S/MIME] [MAIL_PGP*] [DNSSEC*]. For comparison, when the previous version of this document [RFC1750] was issued in 1994, the only Internet cryptographic security specification in the IETF was the Privacy Enhanced Mail protocol [MAIL_PEM*].
ソフトウェア暗号化はより広い使用になりますが、それが蔓延するまで行くのは長い道のりがあります。SSH、IPSec、TLS、S/MIME、PGP、DNSSEC、およびKerberosなどのシステムは、ネットワークランドスケープ[SSH] [IPsec] [S/MIME] [Mail_PGP*] [DNSSEC*]。比較のために、1994年にこの文書の以前のバージョンが発行された場合、IETFの唯一のインターネット暗号化セキュリティ仕様はプライバシー強化メールプロトコル[Mail_Pem*]でした。
These systems provide substantial protection against snooping and spoofing. However, there is a potential flaw. At the heart of all cryptographic systems is the generation of secret, unguessable (i.e., random) numbers.
これらのシステムは、スヌーピングとなりすましに対する実質的な保護を提供します。しかし、潜在的な欠陥があります。すべての暗号化システムの中心にあるのは、秘密、不正な（すなわち、ランダム）番号の生成です。
The lack of generally available facilities for generating such random numbers (that is, the lack of general availability of truly unpredictable sources) forms an open wound in the design of cryptographic software. For the software developer who wants to build a key or password generation procedure that runs on a wide range of hardware, this is a very real problem.
そのような乱数を生成するための一般的に利用可能な施設の欠如（すなわち、本当に予測不可能な情報源の一般的な利用可能性の欠如）は、暗号化ソフトウェアの設計において開いた傷を形成する。幅広いハードウェア上で実行されるキーまたはパスワード生成手順を構築したいソフトウェア開発者は、これが非常に本当の問題です。
Note that the requirement is for data that an adversary has a very low probability of guessing or determining. This can easily fail if pseudo-random data is used that meets only traditional statistical tests for randomness, or that is based on limited-range sources such as clocks. Sometimes such pseudo-random quantities can be guessed by an adversary searching through an embarrassingly small space of possibilities.
要件は、敵対者が推測または決定の確率が非常に低いデータに対するデータに対するものであることに注意してください。擬似ランダムデータを使用すると、ランダム性のための従来の統計テストのみを満たす、またはクロックなどの限られた範囲のソースに基づく疑似ランダムデータが使用される場合、これは簡単に失敗できます。時々このような疑似ランダムな量は、恥ずかしいほど小さいスペースを介して敵対的な検索によって推測され得る。
This Best Current Practice document describes techniques for producing random quantities that will be resistant to attack. It recommends that future systems include hardware random number generation or provide access to existing hardware that can be used for this purpose. It suggests methods for use if such hardware is not available, and it gives some estimates of the number of random bits required for sample applications.
この最良の現在の練習文書は、攻撃に対して耐性があるだろうランダムな量を生産するための技術を説明しています。将来のシステムには、ハードウェア乱数の世代が含まれているか、この目的のために使用できる既存のハードウェアへのアクセスを提供することをお勧めします。そのようなハードウェアが利用できない場合に使用する方法は、サンプルアプリケーションに必要なランダムビット数のいくつかの推定値を示しています。
Today, a commonly encountered randomness requirement is to pick a user password, usually a simple character string. Obviously, a password that can be guessed does not provide security. For re-usable passwords, it is desirable that users be able to remember the password. This may make it advisable to use pronounceable character strings or phrases composed of ordinary words. But this affects only the format of the password information, not the requirement that the password be very hard to guess.
現在、ランダム性に関する一般的な要件は、ユーザー パスワード (通常は単純な文字列) を選択することです。推測できるパスワードではセキュリティが確保されないのは明らかです。再利用可能なパスワードの場合、ユーザーがパスワードを思い出せることが望まれます。このため、発音可能な文字列や一般的な単語で構成されたフレーズを使用することをお勧めします。ただし、これはパスワード情報の形式にのみ影響し、パスワードを推測しにくいものにするという要件には影響しません。
Many other requirements come from the cryptographic arena. Cryptographic techniques can be used to provide a variety of services, including confidentiality and authentication. Such services are based on quantities, traditionally called "keys", that are unknown to and unguessable by an adversary.
その他の多くの要件は、暗号化の分野から生じます。暗号化技術は、機密性や認証など、さまざまなサービスを提供するために使用できます。このようなサービスは、従来「キー」と呼ばれ、敵対者には知られておらず推測もできない量に基づいています。
There are even TCP/IP protocol uses for randomness in picking initial sequence numbers [RFC1948].
TCP/IP プロトコルでは、初期シーケンス番号の選択にランダム性を利用することもあります [RFC1948]。
Generally speaking, the above examples also illustrate two different types of random quantities that may be wanted. In the case of human-usable passwords, the only important characteristic is that they be unguessable. It is not important that they may be composed of ASCII characters, so the top bit of every byte is zero, for example. On the other hand, for fixed length keys and the like, one normally wants quantities that appear to be truly random, that is, quantities whose bits will pass statistical randomness tests.
一般的に言えば、上記の例は、必要なランダム量の 2 つの異なるタイプも示しています。人間が使用できるパスワードの場合、唯一の重要な特性は推測不可能であることです。パスワードが ASCII 文字で構成され、各バイトの最上位ビットがゼロであるなどということは重要ではありません。一方、固定長キーなどの場合、通常、真にランダムであるように見える量、つまりビットが統計的ランダム性テストに合格する量が求められます。
In some cases, such as the use of symmetric encryption with the one-time pads or an algorithm like the US Advanced Encryption Standard [AES], the parties who wish to communicate confidentially and/or with authentication must all know the same secret key. In other cases, where asymmetric or "public key" cryptographic techniques are used, keys come in pairs. One key of the pair is private and must be kept secret by one party; the other is public and can be published to the world. It is computationally infeasible to determine the private key from the public key, and knowledge of the public key is of no help to an adversary [ASYMMETRIC]. See general references [SCHNEIER, FERGUSON, KAUFMAN].
ワンタイム パッドを使用した対称暗号化や、米国の高度暗号化標準 [AES] のようなアルゴリズムを使用する場合など、機密性を保ちながら通信したり認証を行ったりしたい関係者全員が同じ秘密鍵を知っている必要があります。一方、非対称または「公開鍵」暗号化技術が使用される場合、鍵はペアになります。ペアの鍵の 1 つは秘密鍵であり、一方の関係者のみが秘密にしておく必要があります。もう 1 つは公開鍵であり、世界中に公開できます。公開鍵から秘密鍵を特定することは計算上不可能であり、公開鍵を知っていても敵対者にとって何の役にも立ちません [ASYMMETRIC]。一般的な参考文献 [SCHNEIER、FERGUSON、KAUFMAN] を参照してください。
The frequency and volume of the requirement for random quantities differs greatly for different cryptographic systems. With pure RSA, random quantities are required only when a new key pair is generated; thereafter, any number of messages can be signed without a further need for randomness. The public key Digital Signature Algorithm devised by the US National Institute of Standards and Technology (NIST) requires good random numbers for each signature [DSS]. And encrypting with a one-time pad (in principle the strongest possible encryption technique) requires randomness of equal volume to all the messages to be processed. See general references [SCHNEIER, FERGUSON, KAUFMAN].
乱数が必要となる頻度と量は、暗号システムによって大きく異なります。純粋な RSA では、乱数が必要となるのは新しい鍵ペアが生成される場合のみです。その後は、乱数を必要とすることなく、任意の数のメッセージに署名できます。米国国立標準技術研究所 (NIST) が考案した公開鍵デジタル署名アルゴリズムでは、署名ごとに適切な乱数が必要です [DSS]。また、ワンタイム パッド (原則として最も強力な暗号化技術) による暗号化では、処理するすべてのメッセージに等しい量の乱数が必要です。一般的な参考文献 [SCHNEIER、FERGUSON、KAUFMAN] を参照してください。
In most of these cases, an adversary can try to determine the "secret" key by trial and error. This is possible as long as the key is enough smaller than the message that the correct key can be uniquely identified. The probability of an adversary succeeding at this must be made acceptably low, depending on the particular application. The size of the space the adversary must search is related to the amount of key "information" present, in an information-theoretic sense [SHANNON]. This depends on the number of different secret values possible and the probability of each value, as follows:
こうしたケースのほとんどでは、攻撃者は試行錯誤で「秘密」キーを判別しようと試みることができます。これは、キーがメッセージより十分小さく、正しいキーを一意に識別できる場合に限り可能です。攻撃者がこれに成功する確率は、特定のアプリケーションに応じて、許容できる程度に低くする必要があります。攻撃者が検索しなければならない空間のサイズは、情報理論的な意味で、存在するキー「情報」の量に関係しています [SHANNON]。これは、考えられる異なる秘密値の数と各値の確率によって次のように決まります。
-----
\
Bits of information = \ - p * log ( p )
/ i 2 i
/
-----
where i counts from 1 to the number of possible secret values and p sub i is the probability of the value numbered i. (Because p sub i is less than one, the log will be negative, so each term in the sum will be non-negative.)
ここで、i は 1 から可能な秘密の値の数までカウントされ、p sub i は番号 i の値の確率です。(p sub i は 1 未満なので、対数は負になり、合計の各項は負になりません。)
If there are 2^n different values of equal probability, then n bits of information are present and an adversary would have to try, on the average, half of the values, or 2^(n-1), before guessing the secret quantity. If the probability of different values is unequal, then there is less information present, and fewer guesses will, on average, be required by an adversary. In particular, any values that an adversary can know to be impossible or of low probability can be initially ignored by the adversary, who will search through the more probable values first.
2^n 個の異なる値が等確率で存在する場合、n ビットの情報が存在し、敵対者は秘密の量を推測する前に、平均して値の半分、つまり 2^(n-1) を試す必要があります。異なる値の確率が等しくない場合は、存在する情報が少なくなり、敵対者が推測する必要のある平均回数が少なくなります。特に、敵対者が不可能または確率が低いと知っている値は、最初は敵対者によって無視され、より可能性の高い値を最初に検索します。
For example, consider a cryptographic system that uses 128-bit keys. If these keys are derived using a fixed pseudo-random number generator that is seeded with an 8-bit seed, then an adversary needs to search through only 256 keys (by running the pseudo-random number generator with every possible seed), not 2^128 keys as may at first appear to be the case. Only 8 bits of "information" are in these 128-bit keys.
たとえば、128 ビットのキーを使用する暗号化システムについて考えてみましょう。これらのキーが、8 ビットのシードでシードされた固定の疑似乱数ジェネレータを使用して生成される場合、攻撃者は、一見すると 2^128 個のキーを検索する必要があるように見えるかもしれませんが、実際には 256 個のキーを検索するだけで済みます (疑似乱数ジェネレータをすべての可能なシードで実行することにより)。これらの 128 ビットのキーには、8 ビットの「情報」のみが含まれています。
While the above analysis is correct on average, it can be misleading in some cases for cryptographic analysis where what is really important is the work factor for an adversary. For example, assume that there is a pseudo-random number generator generating 128-bit keys, as in the previous paragraph, but that it generates zero half of the time and a random selection from the remaining 2^128 - 1 values the rest of the time. The Shannon equation above says that there are 64 bits of information in one of these key values, but an adversary, simply by trying the value zero, can break the security of half of the uses, albeit a random half. Thus, for cryptographic purposes, it is also useful to look at other measures, such as min-entropy, defined as
上記の分析は平均的には正しいが、暗号分析では敵対者の作業量が重要になる場合があり、誤解を招く可能性がある。たとえば、前の段落のように 128 ビットのキーを生成する疑似乱数生成器があるとするが、半分の時間はゼロを生成し、残りの時間は残りの 2^128 - 1 の値からランダムに選択するとする。上記のシャノン方程式は、これらのキー値の 1 つに 64 ビットの情報が含まれているが、敵対者は単にゼロの値を試すだけで、半分はランダムではあるものの、使用の半分のセキュリティを破ることができるとしている。したがって、暗号の目的のためには、次のように定義される最小エントロピーなどの他の尺度も調べると役立ちます。
Min-entropy = - log ( maximum ( p ) )
i
where i is as above. Using this equation, we get 1 bit of min-entropy for our new hypothetical distribution, as opposed to 64 bits of classical Shannon entropy.
ここで、i は上記のとおりです。この式を使用すると、従来のシャノン エントロピーの 64 ビットではなく、新しい仮想分布の最小エントロピーが 1 ビットになります。
A continuous spectrum of entropies, sometimes called Renyi entropy, has been defined, specified by the parameter r. Here r = 1 is Shannon entropy and r = infinity is min-entropy. When r = zero, it is just log (n), where n is the number of non-zero probabilities. Renyi entropy is a non-increasing function of r, so min-entropy is always the most conservative measure of entropy and usually the best to use for cryptographic evaluation [LUBY].
エントロピーの連続スペクトルは、Renyi エントロピーとも呼ばれ、パラメータ r によって指定され、定義されています。ここで、r = 1 は Shannon エントロピー、r = 無限大は最小エントロピーです。r = 0 の場合は、log (n) になります。ここで、n は非ゼロの確率の数です。Renyi エントロピーは r の非増加関数であるため、最小エントロピーは常に最も保守的なエントロピーの尺度であり、通常は暗号評価に使用するのが最適です [LUBY]。
Statistically tested randomness in the traditional sense is NOT the same as the unpredictability required for security use.
従来の意味での統計的にテストされたランダム性は、セキュリティ用途に必要な予測不可能性と同じではありません。
For example, the use of a widely available constant sequence, such as the random table from the CRC Standard Mathematical Tables, is very weak against an adversary. An adversary who learns of or guesses it can easily break all security, future and past, based on the sequence [CRC]. As another example, using AES with a constant key to encrypt successive integers such as 1, 2, 3, ... will produce output that also has excellent statistical randomness properties but is predictable. On the other hand, taking successive rolls of a six-sided die and encoding the resulting values in ASCII would produce statistically poor output with a substantial unpredictable component. So note that passing or failing statistical tests doesn't reveal whether something is unpredictable or predictable.
たとえば、CRC 標準数学表のランダム テーブルなど、広く利用可能な定数シーケンスの使用は、攻撃者に対して非常に脆弱です。それを知ったり推測したりする攻撃者は、シーケンス [CRC] に基づく将来および過去のすべてのセキュリティを簡単に破ることができます。別の例として、定数キーで AES を使用して 1、2、3、... などの連続する整数を暗号化すると、優れた統計的ランダム性特性を持ちながら予測可能な出力が生成されます。一方、6 面サイコロを連続して振って結果の値を ASCII でエンコードすると、予測不可能な要素がかなり含まれた統計的に貧弱な出力が生成されます。したがって、統計テストの合格または不合格は、何かが予測不可能か予測可能かを明らかにするものではないことに注意してください。
Entropy sources tend to be very implementation dependent. Once one has gathered sufficient entropy, it can be used as the seed to produce the required amount of cryptographically strong pseudo-randomness, as described in Sections 6 and 7, after being de-skewed or mixed as necessary, as described in Sections 4 and 5.
エントロピー源は非常に実装に依存する傾向があります。十分なエントロピーが集まったら、セクション4および5に記載されているように、セクション6および7に記載されているように、必要に応じて、必要に応じて歪んだり混合した後に必要な量の暗号的に強い疑似ランダム性を生成するためのシードとして使用できます。
Is there any hope for true, strong, portable randomness in the future? There might be. All that's needed is a physical source of unpredictable numbers.
将来、真の、強力な、移植可能なランダム性に対する希望はあるでしょうか? あるかもしれません。必要なのは、予測不可能な数字の物理的なソースだけです。
Thermal noise (sometimes called Johnson noise in integrated circuits) or a radioactive decay source and a fast, free-running oscillator would do the trick directly [GIFFORD]. This is a trivial amount of hardware, and it could easily be included as a standard part of a computer system's architecture. Most audio (or video) input devices are usable [TURBID]. Furthermore, any system with a spinning disk or ring oscillator and a stable (crystal) time source or the like has an adequate source of randomness ([DAVIS] and Section 3.3). All that's needed is the common perception among computer vendors that this small additional hardware and the software to access it is necessary and useful.
熱雑音（集積回路ではジョンソン雑音と呼ばれることもある）または放射性崩壊源と高速で自走する発振器があれば、直接この目的を達成できるだろう [GIFFORD]。これはわずかな量のハードウェアであり、コンピュータ システムのアーキテクチャの標準部分として簡単に組み込むことができる。ほとんどのオーディオ（またはビデオ）入力デバイスが使用可能である [TURBID]。さらに、回転ディスクまたはリング発振器と安定した（水晶）時間ソースなどを備えたシステムには、十分なランダム性源がある（[DAVIS] およびセクション 3.3）。必要なのは、この小さな追加ハードウェアとそれにアクセスするソフトウェアが必要かつ有用であるという、コンピュータ ベンダー間の共通認識だけである。
ANSI X9 is currently developing a standard that includes a part devoted to entropy sources. See Part 2 of [X9.82].
ANSI X9は現在、エントロピーソースに費やされた部分を含む標準を開発しています。[X9.82]のパート2を参照してください。
How much unpredictability is needed? Is it possible to quantify the requirement in terms of, say, number of random bits per second?
必要な不安定性が必要ですか？毎秒のランダムビット数の観点から、要件を定量化することは可能ですか？
The answer is that not very much is needed. For AES, the key can be 128 bits, and, as we show in an example in Section 8, even the highest security system is unlikely to require strong keying material of much over 200 bits. If a series of keys is needed, they can be generated from a strong random seed (starting value) using a cryptographically strong sequence, as explained in Section 6.2. A few hundred random bits generated at start-up or once a day is enough if such techniques are used. Even if the random bits are generated as slowly as one per second and it is not possible to overlap the generation process, it should be tolerable in most high-security applications to wait 200 seconds occasionally.
答えはあまり必要とされていないということです。AESの場合、鍵は128ビットになる可能性がありますが、セクション8の例で示すように、最高のセキュリティシステムでさえも、200ビット以上の強力なキーイング材料を必要とする可能性は低いです。一連のキーが必要な場合は、セクション6.2で説明したように、暗号的に強いシーケンスを使用して強いランダムシード（開始値）から生成できます。そのような技術が使用される場合、起動時または1日に1回生成された数百のランダムビットが十分である。ランダムビットが1秒あたりの1つと同じくらいゆっくりと生成されたとしても、生成プロセスと重なっても不可能であっても、時々200秒待ちます。
These numbers are trivial to achieve. It could be achieved by a person repeatedly tossing a coin, and almost any hardware based process is likely to be much faster.
これらの数字は達成するのに些細です。それは硬貨を繰り返し投げ、そしてほとんどすべてのハードウェアベースのプロセスがはるかに速くなる可能性が高いことによって達成され得る。
As described below, many computers come with hardware that can, with care, be used to generate truly random quantities.
後述するように、多くのコンピュータには、注意して、真にランダムな量を生成するために使用できるハードウェアが付属しています。
Many computers are built with inputs that digitize some real-world analog source, such as sound from a microphone or video input from a camera. The "input" from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise. If the system has enough gain to detect anything, such input can provide reasonably high quality random bits. This method is extremely dependent on the hardware implementation.
多くのコンピュータは、マイクロフォンやカメラからのビデオ入力の音など、いくつかの実世界のアナログソースをデジタル化する入力で構築されています。レンズキャップオンのカメラからの電源が入っていない音声デジタイザからの「入力」は、本質的に熱雑音です。システムが何も検出するのに十分な利得がある場合、そのような入力はかなり高品質のランダムビットを提供できます。このメソッドはハードウェア実装に非常に依存しています。
For example, on some UNIX-based systems, one can read from the /dev/audio device with nothing plugged into the microphone jack or with the microphone receiving only low level background noise. Such data is essentially random noise, although it should not be trusted without some checking, in case of hardware failure, and it will have to be de-skewed.
たとえば、一部の UNIX ベースのシステムでは、マイク ジャックに何も接続されていないか、マイクが低レベルのバックグラウンド ノイズのみを受信している状態で、/dev/audio デバイスから読み取ることができます。このようなデータは基本的にランダム ノイズですが、ハードウェア障害が発生した場合に何らかのチェックを行わずに信頼することはできず、歪みを補正する必要があります。
Combining this approach with compression to de-skew (see Section 4), one can generate a huge amount of medium-quality random data with the UNIX-style command line:
このアプローチを圧縮に組み合わせる（セクション4を参照）、UNIX形式のコマンドラインで膨大な量の中質ランダムデータを生成できます。
cat /dev/audio | compress - >random-bits-file
A detailed examination of this type of randomness source appears in [TURBID].
このタイプのランダム性の原因の詳細な調査は、[TURBID]に記載されています。
Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence [DAVIS, Jakobsson]. The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness. Such data is usually highly correlated, so significant processing is needed, as described in Section 5.2 below. Nevertheless, experimentation a decade ago showed that, with such processing, even slow disk drives on the slower computers of that day could easily produce 100 bits a minute or more of excellent random data.
ディスク ドライブは、無秩序な空気の乱流により、回転速度に小さなランダムな変動が生じます [DAVIS、Jakobsson]。低レベルのディスク シーク時間計測器を追加すると、このランダム性を含む一連の測定値が生成されます。このようなデータは通常、高い相関性があるため、セクション 5.2 で説明するように、重要な処理が必要です。ただし、10 年前の実験では、このような処理により、当時の低速コンピューターの低速ディスク ドライブでも、1 分あたり 100 ビット以上の優れたランダム データを簡単に生成できることが示されました。
Every increase in processor speed, which increases the resolution with which disk motion can be timed or increases the rate of disk seeks, increases the rate of random bit generation possible with this technique. At the time of this paper and with modern hardware, a more typical rate of random bit production would be in excess of 10,000 bits a second. This technique is used in random number generators included in many operating system libraries.
プロセッサ速度が上がると、ディスクの動きを計測できる解像度が上がり、ディスクのシーク速度も上がり、この技術で可能なランダム ビット生成速度も上がります。このホワイト ペーパーの執筆時点では、最新のハードウェアを使用した場合、ランダム ビット生成速度は 1 秒あたり 10,000 ビットを超えるのが一般的です。この技術は、多くのオペレーティング システム ライブラリに含まれる乱数ジェネレータで使用されています。
Note: the inclusion of cache memories in disk controllers has little effect on this technique if very short seek times, which represent cache hits, are simply ignored.
注意: キャッシュヒットを表す非常に短いシーク時間を単に無視する場合、ディスク コントローラにキャッシュ メモリを組み込んでも、この手法にはほとんど影響がありません。
If an integrated circuit is being designed or field-programmed, an odd number of gates can be connected in series to produce a free-running ring oscillator. By sampling a point in the ring at a fixed frequency (for example, one determined by a stable crystal oscillator), some amount of entropy can be extracted due to variations in the free-running oscillator timing. It is possible to increase the rate of entropy by XOR'ing sampled values from a few ring oscillators with relatively prime lengths. It is sometimes recommended that an odd number of rings be used so that, even if the rings somehow become synchronously locked to each other, there will still be sampled bit transitions. Another possible source to sample is the output of a noisy diode.
集積回路が設計されているかフィールドプログラムされている場合、奇数個のゲートを直列に接続してフリーランニングリングオシレータを生成することができる。固定周波数（例えば安定した水晶発振器によって決定されるもの）でリング内の点をサンプリングすることによって、自走発振器のタイミングのばらつきによりエントロピーのある程度のエントロピーを抽出することができる。比較的素数の長さを有するいくつかのリングオシレータからのサンプリングされた値をXOR 'のXOR'ER'を増やすことが可能である。時には奇数のリングを使用することをお勧めします。サンプルのもう1つの可能なソースは、ノイズの多いダイオードの出力です。
Sampled bits from such sources will have to be heavily de-skewed, as disk rotation timings must be (see Section 4). An engineering study would be needed to determine the amount of entropy being produced depending on the particular design. In any case, these can be good sources whose cost is a trivial amount of hardware by modern standards.
このような情報源からのサンプリングされたビットは、ディスクの回転タイミングがなければならないので、大きく歪む必要があります（セクション4を参照）。特定の設計に応じて生産されているエントロピーの量を決定するためには、エンジニアリング研究が必要になります。いずれにせよ、これらは現代の標準による些細な量のハードウェアである良いソースであり得る。
As an example, IEEE 802.11i suggests the circuit below, with due attention in the design to isolation of the rings from each other and from clocked circuits to avoid undesired synchronization, etc., and with extensive post processing [IEEE_802.11i].
例として、IEEE 802.11i では、不要な同期などを回避するためにリング同士およびクロック回路からの分離に十分な注意を払った設計と、徹底的な後処理を経た以下の回路を提案しています [IEEE_802.11i]。
|\ |\ |\
+-->| >0-->| >0-- 19 total --| >0--+-------+
| |/ |/ |/ | |
| | |
+----------------------------------+ V
+-----+
|\ |\ |\ | | output
+-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------>
| |/ |/ |/ | | |
| | +-----+
+----------------------------------+ ^ ^
| |
|\ |\ |\ | |
+-->| >0-->| >0-- 29 total --| >0--+------+ |
| |/ |/ |/ | |
| | |
+----------------------------------+ |
|
Other randomness, if available ---------+
Computer clocks and similar operating system or hardware values, provide significantly fewer real bits of unpredictability than might appear from their specifications.
コンピュータの時計と同様のオペレーティングシステムまたはハードウェア値は、それらの仕様から現れるよりも、予測不可能な不可能なビットを大幅に少なくします。
Tests have been done on clocks on numerous systems, and it was found that their behavior can vary widely and in unexpected ways. One version of an operating system running on one set of hardware may actually provide, say, microsecond resolution in a clock, while a different configuration of the "same" system may always provide the same lower bits and only count in the upper bits at much lower resolution. This means that successive reads of the clock may produce identical values even if enough time has passed that the value "should" change based on the nominal clock resolution. There are also cases where frequently reading a clock can produce artificial sequential values, because of extra code that checks for the clock being unchanged between two reads and increases it by one! Designing portable application code to generate unpredictable numbers based on such system clocks is particularly challenging because the system designer does not always know the properties of the system clock.
多数のシステムでクロックのテストが行われ、その動作は大きく異なり、予期しない結果になる可能性があることがわかりました。1セットのハードウェアで実行されているオペレーティング システムのバージョンによっては、実際にクロックでマイクロ秒単位の解像度が提供される場合がありますが、「同じ」システムの別の構成では、常に同じ下位ビットが提供され、上位ビットのカウントははるかに低い解像度でのみ行われる場合があります。 つまり、公称クロック解像度に基づいて値が「変更されるはず」の時間が経過した場合でも、クロックを連続して読み取ると、同じ値が生成される可能性があります。 また、2回の読み取り間でクロックが変更されていないかどうかをチェックして1つ増やす追加コードがあるため、クロックを頻繁に読み取ると、人工的な連続値が生成される場合もあります。 このようなシステム クロックに基づいて予測できない数値を生成するポータブル アプリケーション コードを設計することは、システム設計者がシステム クロックの特性を常に把握しているわけではないため、特に困難です。
Use of a hardware serial number (such as an Ethernet MAC address) may also provide fewer bits of uniqueness than one would guess. Such quantities are usually heavily structured, and subfields may have only a limited range of possible values, or values may be easily guessable based on approximate date of manufacture or other data.
ハードウェアのシリアル番号 (イーサネット MAC アドレスなど) を使用すると、一意性のビット数が予想よりも少なくなることもあります。このような量は通常、厳密に構造化されており、サブフィールドには限られた範囲の値しか含まれない場合や、製造日やその他のデータに基づいて値を簡単に推測できる場合があります。
For example, it is likely that a company that manufactures both computers and Ethernet adapters will, at least internally, use its own adapters, which significantly limits the range of built-in addresses.
たとえば、コンピュータとイーサネットアダプタの両方を製造する会社は、少なくとも内部的に独自のアダプタを使用しているため、内蔵アドレスの範囲を大幅に制限します。
Problems such as those described above make the production of code to generate unpredictable quantities difficult if the code is to be ported across a variety of computer platforms and systems.
上記のような問題は、コードがさまざまなコンピュータプラットフォームやシステムに移植されることになっている場合、予期しない数量を生成するためのコードの作成を行うことができます。
It is possible to measure the timing and content of mouse movement, key strokes, and similar user events. This is a reasonable source of unguessable data, with some qualifications. On some machines, input such as key strokes is buffered. Even though the user's inter-keystroke timing may have sufficient variation and unpredictability, there might not be an easy way to access that variation. Another problem is that no standard method exists for sampling timing details. This makes it hard to use this technique to build standard software intended for distribution to a large range of machines.
マウスの動き、キーストローク、および同様のユーザー イベントのタイミングと内容を測定することができます。これは、いくつかの条件付きで、推測不可能なデータの適切なソースです。一部のマシンでは、キー ストロークなどの入力がバッファリングされます。ユーザーのキー ストローク間のタイミングには十分な変動と予測不可能性があるかもしれませんが、その変動にアクセスする簡単な方法がない場合があります。もう 1 つの問題は、タイミングの詳細をサンプリングするための標準的な方法が存在しないことです。このため、この手法を使用して、さまざまなマシンに配布することを目的とした標準ソフトウェアを構築するのは困難です。
The amount of mouse movement and the actual key strokes are usually easier to access than timings, but they may yield less unpredictability because the user may provide highly repetitive input.
マウスの動きと実際のキーストロークの量は、通常、タイミングよりもアクセスが簡単ですが、ユーザーは反復的な入力を提供する可能性があるため、予測不可能性が低くなる可能性があります。
Other external events, such as network packet arrival times and lengths, can also be used, but only with great care. In particular, the possibility of manipulation of such network traffic measurements by an adversary and the lack of history at system start-up must be carefully considered. If this input is subject to manipulation, it must not be trusted as a source of entropy.
ネットワークパケットの到着時間や長さなどの他の外部イベントも使用できますが、細心の注意を払うだけです。特に、システム起動時の敵対的および歴史の欠如によるそのようなネットワーク交通測定の操作の可能性は慎重に検討されなければならない。この入力が操作の対象となる場合は、エントロピーの源として信頼されてはいけません。
In principle, almost any external sensor, such as raw radio reception or temperature sensing in appropriately equipped computers, can be used. But in each case, careful consideration must be given to how much this data is subject to adversarial manipulation and to how much entropy it can actually provide.
原則として、RAW無線受信または適切な搭載されたコンピュータにおける温度検知などのほとんどすべての外部センサを使用することができる。しかし、それぞれの場合では、このデータが敵対的な操作の対象となる量とそれが実際にどのくらいのエントロピーを提供できるかには慎重に検討されなければなりません。
The above techniques are quite powerful against attackers that have no access to the quantities being measured. For example, these techniques would be powerful against offline attackers who had no access to one's environment and who were trying to crack one's random seed after the fact. In all cases, the more accurately one can measure the timing or value of an external sensor, the more rapidly one can generate bits.
上記の技術は、測定されている量にアクセスできない攻撃者に対して非常に強力です。例えば、これらの技術は、自分の環境にアクセスできないオフライン攻撃者に対して強力であり、その事実後に自分のランダムな種を亀裂しようとしていた人は。全ての場合において、より正確に外部センサのタイミングまたは値を測定することができるが、より急速にビットを生成することができる。
The best source of input entropy would be a hardware-based random source such as ring oscillators, disk drive timing, thermal noise, or radioactive decay. However, if none of these is available, there are other possibilities. These include system clocks, system or input/output buffers, user/system/hardware/network serial numbers or addresses and timing, and user input. Unfortunately, each of these sources can produce very limited or predictable values under some circumstances.
入力エントロピーの最良の情報源は、リングオシレータ、ディスクドライブのタイミング、熱ノイズ、または放射性崩壊などのハードウェアベースのランダムソースです。ただし、これらのどれも利用可能な場合は他の可能性があります。これらには、システムクロック、システム、または入出力バッファ、ユーザー/システム/ハードウェア/ネットワークのシリアル番号、またはアドレスとタイミング、およびユーザー入力が含まれます。残念ながら、これらの各情報源は状況によっては非常に限られたまたは予測可能な値を生み出すことができます。
Some of the sources listed above would be quite strong on multi-user systems, where each user of the system is in essence a source of randomness. However, on a small single-user or embedded system, especially at start-up, it might be possible for an adversary to assemble a similar configuration. This could give the adversary inputs to the mixing process that were well-enough correlated to those used originally to make exhaustive search practical.
上記のいくつかの情報源は、システムの各ユーザがエッセンスであるマルチユーザシステムでは非常に強いであろう。ただし、特に起動時には、小型のシングルユーザーまたは組み込みシステムでは、敵対的な構成を組み立てることが可能かもしれません。これにより、徹底的な検索を実用化するためにもともとに使用されるものとよく相関している混合プロセスへの敵対的な入力が与える可能性があります。
The use of multiple random inputs with a strong mixing function is recommended and can overcome weakness in any particular input. The timing and content of requested "random" user keystrokes can yield hundreds of random bits, but conservative assumptions need to be made. For example, one reasonably conservative assumption would be that an inter-keystroke interval provides at most a few bits of randomness, but only when the interval is unique in the sequence of intervals up to that point. A similar assumption would be that a key code provides a few bits of randomness, but only when the code is unique in the sequence. Thus, an interval or key code that duplicated a previous value would be assumed to provide no additional randomness. The results of mixing these timings with typed characters could be further combined with clock values and other inputs.
強力な混合機能を持つ複数のランダム入力の使用が推奨されており、特定の入力の弱点を克服できます。要求された「ランダム」なユーザー キーストロークのタイミングと内容から、数百のランダム ビットが生成される可能性がありますが、保守的な仮定を行う必要があります。たとえば、合理的に保守的な仮定の 1 つは、キーストローク間の間隔によって最大で数ビットのランダム性が提供されるが、その間隔がその時点までの間隔のシーケンス内で一意である場合のみである、というものです。同様の仮定は、キー コードによって数ビットのランダム性が提供されるが、そのコードがシーケンス内で一意である場合のみである、というものです。したがって、前の値を複製した間隔またはキー コードは、追加のランダム性を提供しないと見なされます。これらのタイミングと入力された文字を混合した結果は、クロック値やその他の入力とさらに組み合わせることができます。
This strategy may make practical portable code for producing good random numbers for security, even if some of the inputs are very weak on some of the target systems. However, it may still fail against a high-grade attack on small, single-user, or embedded systems, especially if the adversary has ever been able to observe the generation process in the past. A hardware-based random source is still preferable.
この戦略は、いくつかのターゲットシステムでいくつかの入力が非常に弱い場合でも、セキュリティのために良い乱数を生成するための実用的な携帯コードを作ることができます。ただし、特に敵対者が過去の生成プロセスを観察できたことがある場合は、まだ小型、シングルユーザー、または組み込みシステムでの高級攻撃に対して失敗する可能性があります。ハードウェアベースのランダムソースが依然として好ましい。
Is there any specific requirement on the shape of the distribution of quantities gathered for the entropy to produce the random numbers? The good news is that the distribution need not be uniform. All that is needed to bound performance is a conservative estimate of how non-uniform it is. Simple techniques to de-skew a bit stream are given below, and stronger cryptographic techniques are described in Section 5.2.
乱数を生成するためにエントロピーに集められた量の分布の形状に、特別な要件はありますか? 幸いなことに、分布は均一である必要はありません。パフォーマンスを制限するために必要なのは、分布がどの程度不均一であるかを控えめに見積もることだけです。ビット ストリームを歪ませる簡単な手法は以下に示され、より強力な暗号化手法はセクション 5.2 で説明されています。
As a simple but not particularly practical example, consider taking a sufficiently long string of bits and mapping the string to "zero" or "one". The mapping will not yield a perfectly uniform distribution, but it can be as close as desired. One mapping that serves the purpose is to take the parity of the string. This has the advantages that it is robust across all degrees of skew up to the estimated maximum skew and that it is trivial to implement in hardware.
単純ですが特に実用的ではない例として、十分に長いビットの文字列を取り、その文字列を「0」または「1」にマッピングすることを考えてみましょう。マッピングによって完全に均一な分布は得られませんが、希望どおりに近づけることができます。目的にかなうマッピングの 1 つは、文字列のパリティを取ることです。これには、推定最大スキューまでのすべてのスキュー度にわたって堅牢であり、ハードウェアで実装するのが簡単であるという利点があります。
The following analysis gives the number of bits that must be sampled:
次の分析では、サンプリングする必要があるビット数を示します。
Suppose that the ratio of ones to zeros is ( 0.5 + E ) to ( 0.5 - E ), where E is between 0 and 0.5 and is a measure of the "eccentricity" of the distribution. Consider the distribution of the parity function of N bit samples. The respective probabilities that the parity will be one or zero will be the sum of the odd or even terms in the binomial expansion of (p + q)^N, where p = 0.5 + E, the probability of a one, and q = 0.5 - E, the probability of a zero.
1 と 0 の比率が ( 0.5 + E ) から ( 0.5 - E ) であるとします。ここで、E は 0 から 0.5 までで、分布の「偏心度」の尺度です。N ビット サンプルのパリティ関数の分布を考えてみましょう。パリティが 1 または 0 になるそれぞれの確率は、(p + q)^N の二項展開における奇数項または偶数項の合計になります。ここで、p = 0.5 + E (1 の確率)、q = 0.5 - E (0 の確率) です。
These sums can be computed easily as
これらの合計は簡単に計算できます
N N
1/2 * ( ( p + q ) + ( p - q ) )
and
そして
N N
1/2 * ( ( p + q ) - ( p - q ) ).
(Which formula corresponds to the probability that the parity will be 1 depends on whether N is odd or even.)
(どの式がパリティが 1 になる確率に対応するかは、N が奇数か偶数かによって異なります。)
Since p + q = 1 and p - q = 2E, these expressions reduce to
p + q = 1、p - q = 2Eなので、これらの式は次のように簡約されます。
N
1/2 * [1 + (2E) ]
and
そして
N
1/2 * [1 - (2E) ].
Neither of these will ever be exactly 0.5 unless E is zero, but we can bring them arbitrarily close to 0.5. If we want the probabilities to be within some delta d of 0.5, e.g., then
Eがゼロでない限り、どちらも0.5にはなりませんが、0.5に任意に近づけることができます。例えば、確率を0.5のデルタd以内に収めたい場合、
N
( 0.5 + ( 0.5 * (2E) ) ) < 0.5 + d.
Solving for N yields N > log(2d)/log(2E). (Note that 2E is less than 1, so its log is negative. Division by a negative number reverses the sense of an inequality.)
N について解くと、N > log(2d)/log(2E) となります。(2E は 1 未満なので、その対数は負になることに注意してください。負の数で割ると、不等式の意味が逆になります。)
The following table gives the length N of the string that must be sampled for various degrees of skew in order to come within 0.001 of a 50/50 distribution.
次の表は、50/50 分布の 0.001 以内に収まるように、さまざまな程度の歪度でサンプリングする必要がある文字列の長さ N を示しています。
+---------+--------+-------+
| Prob(1) | E | N |
+---------+--------+-------+
| 0.5 | 0.00 | 1 |
| 0.6 | 0.10 | 4 |
| 0.7 | 0.20 | 7 |
| 0.8 | 0.30 | 13 |
| 0.9 | 0.40 | 28 |
| 0.95 | 0.45 | 59 |
| 0.99 | 0.49 | 308 |
+---------+--------+-------+
The last entry shows that even if the distribution is skewed 99% in favor of ones, the parity of a string of 308 samples will be within 0.001 of a 50/50 distribution. But, as we shall see in section 5.2, there are much stronger techniques that extract more of the available entropy.
最後のエントリは、分布が 1 に有利に 99% 偏っている場合でも、308 個のサンプルの文字列のパリティは 50/50 分布の 0.001 以内になることを示しています。ただし、セクション 5.2 で説明するように、利用可能なエントロピーをさらに抽出する、はるかに強力な手法があります。
Another technique, originally due to von Neumann [VON_NEUMANN], is to examine a bit stream as a sequence of non-overlapping pairs. One could then discard any 00 or 11 pairs found, interpret 01 as a 0 and 10 as a 1. Assume that the probability of a 1 is 0.5+E and that the probability of a 0 is 0.5-E, where E is the eccentricity of the source as described in the previous section. Then the probability of each pair is shown in the following table:
フォンノイマン [VON_NEUMANN] が考案した別の手法は、ビットストリームを重複しないペアのシーケンスとして調べるというものです。見つかった 00 または 11 のペアは破棄し、01 を 0、10 を 1 と解釈します。1 の確率は 0.5+E、0 の確率は 0.5-E であると仮定します。ここで、E は前のセクションで説明したソースの離心率です。各ペアの確率は次の表のようになります。
+------+-----------------------------------------+
| pair | probability |
+------+-----------------------------------------+
| 00 | (0.5 - E)^2 = 0.25 - E + E^2 |
| 01 | (0.5 - E)*(0.5 + E) = 0.25 - E^2 |
| 10 | (0.5 + E)*(0.5 - E) = 0.25 - E^2 |
| 11 | (0.5 + E)^2 = 0.25 + E + E^2 |
+------+-----------------------------------------+
This technique will completely eliminate any bias but requires an indeterminate number of input bits for any particular desired number of output bits. The probability of any particular pair being discarded is 0.5 + 2E^2, so the expected number of input bits to produce X output bits is X/(0.25 - E^2).
この手法では、偏りは完全に排除されますが、特定の出力ビット数を得るには不確定な入力ビット数が必要になります。特定のペアが破棄される確率は 0.5 + 2E^2 なので、X 出力ビットを生成するために必要な入力ビット数は X/(0.25 - E^2) と予想されます。
This technique assumes that the bits are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are uncorrelated, i.e., that the bits come from identical independent distributions. If alternate bits are from two correlated sources, for example, the above analysis breaks down.
この技術は、ビットが、ストリーム内の他のどのビットとして0または1と同じ確率があるストリームから、そのビットは無相関、すなわちビットが同一の独立した分布から来ることを仮定する。たとえば、代替ビットが2つの相関ソースからのものである場合は、上記の分析が切断されます。
The above technique also provides another illustration of how a simple statistical analysis can mislead if one is not always on the lookout for patterns that could be exploited by an adversary. If the algorithm were misread slightly so that overlapping successive bits pairs were used instead of non-overlapping pairs, the statistical analysis given would be the same. However, instead of providing an unbiased, uncorrelated series of random 1s and 0s, it would produce a totally predictable sequence of exactly alternating 1s and 0s.
上記の手法は、敵が悪用する可能性のあるパターンを常に監視していなければ、単純な統計分析がいかに誤った結果を導く可能性があるかを示すもう 1 つの例でもあります。アルゴリズムがわずかに読み間違えられ、重複しないビット ペアではなく、重複する連続ビット ペアが使用される場合、提供される統計分析は同じになります。ただし、偏りのない、相関のない一連のランダムな 1 と 0 を提供する代わりに、完全に予測可能な 1 と 0 が正確に交互に並ぶシーケンスが生成されます。
When real-world data consists of strongly correlated bits, it may still contain useful amounts of entropy. This entropy can be extracted through various transforms, the most powerful of which are described in section 5.2 below.
実世界のデータが強く相関のあるビットで構成されている場合、それでも有用なエントロピーが含まれている可能性があります。このエントロピーはさまざまな変換を通して抽出できますが、最も強力なものは以下のセクション5.2で説明されています。
Using the Fourier transform of the data or its optimized variant, the FFT, is interesting primarily for theoretical reasons. It can be shown that this technique will discard strong correlations. If adequate data is processed and if remaining correlations decay, spectral lines that approach statistical independence and normally distributed randomness can be produced [BRILLINGER].
データのフーリエ変換またはその最適化されたバリエーションを使用して、FFTは主に理論的な理由から興味深いものです。この技術は強い相関を捨てることを示すことができます。適切なデータが処理され、残りの相関が崩壊した場合、統計的独立および通常分布したランダム性に近づくスペクトル線を生成することができる。
Reversible compression techniques also provide a crude method of de-skewing a skewed bit stream. This follows directly from the definition of reversible compression and the formula in Section 2 for the amount of information in a sequence. Since the compression is reversible, the same amount of information must be present in the shorter output as was present in the longer input. By the Shannon information equation, this is only possible if, on average, the probabilities of the different shorter sequences are more uniformly distributed than were the probabilities of the longer sequences. Therefore, the shorter sequences must be de-skewed relative to the input.
可逆的な圧縮技術はまた、斜めのビットストリームを逆スキューするための粗い方法を提供する。これは、シーケンス内の情報量については、リバーシブル圧縮の定義と式2の式の定義から直接次のとおりです。圧縮は可逆的であるため、長い入力に存在していたのと同じ出力に同じ量の情報が存在しなければなりません。シャノン情報方程式によって、平均して、異なる短シーケンスの確率がより長いシーケンスの確率よりも均一に分布している場合にのみ可能です。したがって、より短いシーケンスは入力に対して逆スキューされなければなりません。
However, many compression techniques add a somewhat predictable preface to their output stream and may insert a similar sequence periodically in their output or otherwise introduce subtle patterns of their own. They should be considered only rough techniques compared to those described in Section 5.2. At a minimum, the beginning of the compressed sequence should be skipped and only later bits should used for applications requiring roughly-random bits.
しかしながら、多くの圧縮技術はそれらの出力ストリームに対して幾分予測可能な序文を追加し、それらの出力において周期的に同様のシーケンスを挿入することができ、あるいはそれら自身の微妙なパターンを導入することができる。それらは、セクション5.2で説明されているものと比較して、大まかな技術のみを考慮する必要があります。最低では、圧縮シーケンスの始まりはスキップされるべきであり、後のビットだけが粗大なランダムなビットを必要とするアプリケーションに使用されるべきです。
What is the best overall strategy for obtaining unguessable random numbers in the absence of a strong, reliable hardware entropy source? It is to obtain input from a number of uncorrelated sources and to mix them with a strong mixing function. Such a function will preserve the entropy present in any of the sources, even if other quantities being combined happen to be fixed or easily guessable (low entropy). This approach may be advisable even with a good hardware source, as hardware can also fail. However, this should be weighed against a possible increase in the chance of overall failure due to added software complexity.
強力で信頼性の高いハードウェア エントロピー ソースがない場合に、推測不可能な乱数を取得するための最善の総合戦略は何でしょうか。それは、相関関係のない複数のソースから入力を取得し、強力な混合関数を使用してそれらを混合することです。このような関数は、結合される他の量が固定または簡単に推測できる (エントロピーが低い) 場合でも、ソースのいずれかに存在するエントロピーを保持します。ハードウェアも故障する可能性があるため、優れたハードウェア ソースを使用する場合でも、このアプローチが推奨される場合があります。ただし、ソフトウェアの複雑さが増すことで全体的な障害の可能性が高まる可能性があることを考慮する必要があります。
Once one has used good sources, such as some of those listed in Section 3, and mixed them as described in this section, one has a strong seed. This can then be used to produce large quantities of cryptographically strong material as described in Sections 6 and 7.
セクション 3 にリストされているような優れたソースを使用し、このセクションで説明されているようにそれらを混合すると、強力なシードが得られます。その後、セクション 6 と 7 で説明されているように、これを使用して暗号的に強力な素材を大量に生成できます。
A strong mixing function is one that combines inputs and produces an output in which each output bit is a different complex non-linear function of all the input bits. On average, changing any input bit will change about half the output bits. But because the relationship is complex and non-linear, no particular output bit is guaranteed to change when any particular input bit is changed.
強力な混合関数とは、入力を組み合わせて、各出力ビットがすべての入力ビットの異なる複雑な非線形関数である出力を生成する関数です。平均すると、入力ビットを変更すると、出力ビットの約半分が変更されます。ただし、関係が複雑で非線形であるため、特定の入力ビットが変更されても、特定の出力ビットが必ず変更されるわけではありません。
Consider the problem of converting a stream of bits that is skewed towards 0 or 1 or which has a somewhat predictable pattern to a shorter stream which is more random, as discussed in Section 4. This is simply another case where a strong mixing function is desired, to mix the input bits and produce a smaller number of output bits. The technique given in Section 4.1, using the parity of a number of bits, is simply the result of successively XORing them. This is examined as a trivial mixing function, immediately below. Use of stronger mixing functions to extract more of the randomness in a stream of skewed bits is examined in Section 5.2. See also [NASLUND].
セクション 4 で説明したように、0 または 1 に偏っているか、ある程度予測可能なパターンを持つビット ストリームを、よりランダムな短いストリームに変換する問題を考えてみましょう。これは、入力ビットを混合して少数の出力ビットを生成するために、強力な混合関数が求められる別のケースです。セクション 4.1 で説明した、多数のビットのパリティを使用する手法は、単にそれらを連続的に XOR した結果です。これは、すぐ下で、自明な混合関数として検討されます。偏ったビット ストリームからより多くのランダム性を抽出するために、より強力な混合関数を使用する方法については、セクション 5.2 で検討します。[NASLUND] も参照してください。
For expository purposes we describe a trivial example for single bit inputs using the Exclusive Or (XOR) function. This function is equivalent to addition without carry, as show in the table below. This is a degenerate case in which the one output bit always changes for a change in either input bit. But, despite its simplicity, it provides a useful illustration.
説明のために、排他的論理和 (XOR) 関数を使用した単一ビット入力の簡単な例を示します。この関数は、下の表に示すように、桁上げなしの加算に相当します。これは、どちらかの入力ビットが変化すると、1 つの出力ビットが常に変化するという退化したケースです。しかし、その単純さにもかかわらず、これは有用な例証となります。
+-----------+-----------+----------+
| input 1 | input 2 | output |
+-----------+-----------+----------+
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
+-----------+-----------+----------+
If inputs 1 and 2 are uncorrelated and combined in this fashion, then the output will be an even better (less skewed) random bit than the inputs are. If we assume an "eccentricity" E as defined in Section 4.1 above, then the output eccentricity relates to the input eccentricity as follows:
入力1と2が無相関でこのように組み合わされている場合、出力は入力よりもさらに優れた（スキューされていない）ランダムビットになります。上記のセクション4.1で定義されているように「偏心」Eを仮定した場合、出力偏心は次のように入力偏心に関係します。
E = 2 * E * E
output input 1 input 2
Since E is never greater than 1/2, the eccentricity is always improved, except in the case in which at least one input is a totally skewed constant. This is illustrated in the following table, where the top and left side values are the two input eccentricities and the entries are the output eccentricity:
Eは1/2以上ではないので、少なくとも1つの入力が全く歪んだ一定である場合を除いて、偏心は常に改善されます。これは次の表に示されています。ここで、上面と左側の値は2つの入力偏心率であり、エントリは出力偏心です。
+--------+--------+--------+--------+--------+--------+--------+
| E | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
| 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| 0.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 |
| 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 |
| 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 |
| 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 |
| 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
However, note that the above calculations assume that the inputs are not correlated. If the inputs were, say, the parity of the number of minutes from midnight on two clocks accurate to a few seconds, then each might appear random if sampled at random intervals much longer than a minute. Yet if they were both sampled and combined with XOR, the result would be zero most of the time.
ただし、上記の計算は入力が相関していないと仮定していることに注意してください。入力が数秒から数秒までの2クロックでの午前中の分数のパリティが、1分以上のランダムな間隔でサンプリングされた場合、それぞれがランダムに表示されることがあります。それでも、それらがサンプリングされてXORと組み合わされた場合、その結果はほとんどの場合ゼロになります。
The US Government Advanced Encryption Standard [AES] is an example of a strong mixing function for multiple bit quantities. It takes up to 384 bits of input (128 bits of "data" and 256 bits of "key") and produces 128 bits of output, each of which is dependent on a complex non-linear function of all input bits. Other encryption functions with this characteristic, such as [DES], can also be used by considering them to mix all of their key and data input bits.
米国政府高度な暗号化標準[AES]は、複数のビット数量に対する強力な混合関数の一例です。それは最大384ビットの入力（128ビットの "データ"および256ビットの "キー"）を必要とし、それぞれ128ビットの出力を生成し、それぞれがすべての入力ビットの複素非線形関数に依存します。[DES]などのこの特性を持つ他の暗号化関数も、それらのすべてのキーとデータ入力ビットを混在させることを考慮して使用することもできます。
Another good family of mixing functions is the "message digest" or hashing functions such as the US Government Secure Hash Standards [SHA*] and the MD4, MD5 [MD4, MD5] series. These functions all take a practically unlimited amount of input and produce a relatively short fixed-length output mixing all the input bits. The MD* series produces 128 bits of output, SHA-1 produces 160 bits, and other SHA functions produce up to 512 bits.
混合関数のもう1つの良いファミリーは、米国政府の安全なハッシュ標準[SHA *]、MD4、MD5 [MD5]シリーズなどの「メッセージダイジェスト」またはハッシュ機能です。これらの関数はすべて実質的に無制限の量の入力を取り、すべての入力ビットを混在させる比較的短い固定長出力を生成します。MD *シリーズは128ビットの出力を生成し、SHA-1は160ビットを生成し、他のSHA関数は最大512ビットを生成します。
Although the message digest functions are designed for variable amounts of input, AES and other encryption functions can also be used to combine any number of inputs. If 128 bits of output is adequate, the inputs can be packed into a 128-bit data quantity and successive AES "keys", padding with zeros if needed; the quantity is then successively encrypted by the "keys" using AES in Electronic Codebook Mode. Alternatively, the input could be packed into one 128-bit key and multiple data blocks and a CBC-MAC could be calculated [MODES].
メッセージダイジェスト関数は可変量の入力用に設計されていますが、AESやその他の暗号化機能を使用して任意の数の入力を組み合わせることもできます。128ビットの出力が適切であれば、入力を128ビットのデータ量と連続するAES "キー"に詰め込むことができ、必要に応じてゼロを搭載することができます。その後、電子コードブックモードでAESを使用して数量を「キー」で順次暗号化されます。あるいは、入力を1つの128ビットキーにパックすることができ、複数のデータブロックおよびCBC-MACを計算することができます[モード]。
More complex mixing should be used if more than 128 bits of output are needed and one wants to employ AES (but note that it is absolutely impossible to get more bits of "randomness" out than are put in). For example, suppose that inputs are packed into three quantities, A, B, and C. One may use AES to encrypt A with B and then with C as keys to produce the first part of the output, then encrypt B with C and then A for more output and, if necessary, encrypt C with A and then B for yet more output. Still more output can be produced by reversing the order of the keys given above. The same can be done with the hash functions, hashing various subsets of the input data or different copies of the input data with different prefixes and/or suffixes to produce multiple outputs.
128ビット以上の出力が必要な場合は、より複雑なミキシングを使用する必要があります。たとえば、入力が3つの量、A、B、およびCにパックされているとすると、AESを使用してBを使用し、次いでCをキーとして暗号化して出力の最初の部分を生成し、次にCをCで暗号化してAを出力し、必要に応じて、さらにBでCを暗号化するためにCを暗号化します。上記のキーの順序を反転させることによって、さらに出力を作成することができる。ハッシュ関数を用いても同じことができ、入力データの様々なサブセットまたは入力データの異なるコピーを異なる接頭辞および/または接尾辞を用いて複数の出力を形成することができる。
For an example of using a strong mixing function, reconsider the case of a string of 308 bits, each of which is biased 99% toward zero. The parity technique given in Section 4.1 reduces this to one bit, with only a 1/1000 deviance from being equally likely a zero or one. But, applying the equation for information given in Section 2, this
強力な混合関数を使用する例については、308ビットのストリングの場合を再検討し、その各々はゼロに向かって99％バイアスされています。セクション4.1に示されているパリティ技法は、これを1ビットに減らし、1/1000の逸脱はゼロまたは1の偏差だけであります。しかし、セクション2で与えられた情報のための方程式を適用します。
308-bit skewed sequence contains over 5 bits of information. Thus, hashing it with SHA-1 and taking the bottom 5 bits of the result would yield 5 unbiased random bits and not the single bit given by calculating the parity of the string. Alternatively, for some applications, you could use the entire hash output to retain almost all of the 5+ bits of entropy in a 160-bit quantity.
308ビットスキューシーケンスには5ビット以上の情報が含まれています。したがって、SHA-1とそれをハッシュし、結果の底部5ビットを取得すると、5ビットが5つの不偏ランダムビットが得られ、文字列のパリティを計算することによって与えられた単一ビットではありません。あるいは、いくつかのアプリケーションでは、ハッシュ出力全体を使用して、160ビットのエントロピーの5ビットのエントロピーのほぼ全部を保持することができます。
Many modern block encryption functions, including DES and AES, incorporate modules known as S-Boxes (substitution boxes). These produce a smaller number of outputs from a larger number of inputs through a complex non-linear mixing function that has the effect of concentrating limited entropy from the inputs into the output.
DESとAESを含む多くの最新のブロック暗号化機能、Sボックス（置換ボックス）として知られるモジュールを組み込んでいます。これらは、制限されたエントロピーを入力から出力に集中させる効果を有する複雑な非線形混合関数を介して、より少ない数の出力から小数の出力を生成します。
S-Boxes sometimes incorporate bent Boolean functions (functions of an even number of bits producing one output bit with maximum non-linearity). Looking at the output for all input pairs differing in any particular bit position, exactly half the outputs are different. An S-Box in which each output bit is produced by a bent function such that any linear combination of these functions is also a bent function is called a "perfect S-Box".
Sボックスには、BENBENブール関数を組み込んだ（偶数ビット数の関数を最大限の非線形性を持つ1つの出力ビットを生成）。特定のビット位置が異なるすべての入力ペアの出力を見て、出力の半分半分は異なります。これらの機能の線形組み合わせも曲がった機能であるように、各出力ビットが曲がった機能によって生成されるSボックスは、「完璧なSボックス」と呼ばれます。
S-boxes and various repeated applications or cascades of such boxes can be used for mixing [SBOX1, SBOX2].
このような箱のSボックスや様々な繰り返しのアプリケーションやカスケードを使用して[SBOX1、SBOX2]を混合することができます。
Diffie-Hellman exponential key exchange is a technique that yields a shared secret between two parties. It can be computationally infeasible for a third party to determine this secret even if they can observe all the messages between the two communicating parties. This shared secret is a mixture of initial quantities generated by each of the parties [D-H].
Diffie-Hellman指数関数交換は、2人の締約国間の共有秘密を生じる技術です。2つの通信当事者間のすべてのメッセージを観察できる場合でも、この秘密を判断することは、この秘密を判断できるようにすることができます。この共有秘密は、各締約国によって生成された初期量の混合物[D-H]です。
If these initial quantities are random and uncorrelated, then the shared secret combines their entropy but, of course, can not produce more randomness than the size of the shared secret generated.
これらの初期量がランダムで無相関である場合、共有秘密はエントロピーを組み合わせるが、もちろん、生成された共有秘密のサイズよりもランダム性を生じさせることはできません。
Although this is true if the Diffie-Hellman computation is performed privately, an adversary who can observe either of the public keys and knows the modulus being used need only search through the space of the other secret key in order to be able to calculate the shared secret [D-H]. So, conservatively, it would be best to consider public Diffie-Hellman to produce a quantity whose guessability corresponds to the worse of the two inputs. Because of this and the fact that Diffie-Hellman is computationally intensive, its use as a mixing function is not recommended.
Diffie-Hellmanの計算が個人的に行われた場合、公開鍵のいずれかを観察し、使用されているモジュラスを知っている敵対者は、共有を計算できるようにするために他の秘密鍵のスペースを検索するだけである。秘密[DH]。それで、保守的には、推測性が2つの入力の悪化に対応する量を生み出すために、公的なDiffie-Hellmanを考慮することが最善でしょう。このため、Diffie-Hellmanが計算的に集約されているという事実は、ミキシング機能としての使用はお勧めできません。
Although it is not necessary for a mixing function to produce the same or fewer output bits than its inputs, mixing bits cannot "stretch" the amount of random unpredictability present in the inputs. Thus, four inputs of 32 bits each, in which there are 12 bits worth of unpredictability (such as 4,096 equally probable values) in each input, cannot produce more than 48 bits worth of unpredictable output. The output can be expanded to hundreds or thousands of bits by, for example, mixing with successive integers, but the clever adversary's search space is still 2^48 possibilities. Furthermore, mixing to fewer bits than are input will tend to strengthen the randomness of the output.
混合関数が、入力と同じかそれより少ない出力ビットを生成する必要はありませんが、ビットを混合しても、入力に存在するランダムな予測不可能性の大きさを「拡張」することはできません。したがって、各入力に 12 ビット相当の予測不可能性 (4,096 個の等確率値など) がある 32 ビットの 4 つの入力では、48 ビット相当を超える予測不可能性の出力を生成することはできません。たとえば、連続する整数と混合することで、出力を数百または数千ビットに拡張できますが、賢い敵の探索空間は依然として 2^48 の可能性のままです。さらに、入力よりも少ないビットに混合すると、出力のランダム性が強化される傾向があります。
The last table in Section 5.1 shows that mixing a random bit with a constant bit with Exclusive Or will produce a random bit. While this is true, it does not provide a way to "stretch" one random bit into more than one. If, for example, a random bit is mixed with a 0 and then with a 1, this produces a two bit sequence but it will always be either 01 or 10. Since there are only two possible values, there is still only the one bit of original randomness.
セクション 5.1 の最後の表は、排他的論理和を使用してランダム ビットと定数ビットを混合すると、ランダム ビットが生成されることを示しています。これは事実ですが、1 つのランダム ビットを複数のビットに「引き伸ばす」方法は提供されません。たとえば、ランダム ビットを 0 と混合してから 1 と混合すると、2 ビットのシーケンスが生成されますが、常に 01 または 10 のいずれかになります。可能な値は 2 つしかないため、元のランダム性は 1 ビットだけになります。
For local use, AES has the advantages that it has been widely tested for flaws, is reasonably efficient in software, and is widely documented and implemented with hardware and software implementations available all over the world including open source code. The SHA* family have had a little less study and tend to require more CPU cycles than AES but there is no reason to believe they are flawed. Both SHA* and MD5 were derived from the earlier MD4 algorithm. They all have source code available [SHA*, MD4, MD5]. Some signs of weakness have been found in MD4 and MD5. In particular, MD4 has only three rounds and there are several independent breaks of the first two or last two rounds. And some collisions have been found in MD5 output.
ローカルでの使用では、AES は、欠陥が広くテストされており、ソフトウェアでかなり効率的であり、オープンソース コードを含む世界中で入手可能なハードウェアおよびソフトウェア実装で広く文書化および実装されているという利点があります。SHA* ファミリは AES よりも研究が少し少なく、より多くの CPU サイクルを必要とする傾向がありますが、欠陥があると考える理由はありません。SHA* と MD5 はどちらも、以前の MD4 アルゴリズムから派生したものです。これらはすべてソース コードが利用可能です [SHA*、MD4、MD5]。MD4 と MD5 には、いくつかの弱点の兆候が見つかっています。特に、MD4 には 3 ラウンドしかなく、最初の 2 ラウンドまたは最後の 2 ラウンドに独立したブレークがいくつかあります。また、MD5 出力でいくつかの衝突が見つかりました。
AES was selected by a robust, public, and international process. It and SHA* have been vouched for by the US National Security Agency (NSA) on the basis of criteria that mostly remain secret, as was DES. While this has been the cause of much speculation and doubt, investigation of DES over the years has indicated that NSA involvement in modifications to its design, which originated with IBM, was primarily to strengthen it. There has been no announcement of a concealed or special weakness being found in DES. It is likely that the NSA modifications to MD4 to produce the SHA algorithms similarly strengthened these algorithms, possibly against threats not yet known in the public cryptographic community.
AES は、堅牢で公開された国際的なプロセスによって選択されました。AES と SHA* は、DES と同様に、ほとんどが秘密にされている基準に基づいて米国国家安全保障局 (NSA) によって保証されています。これは多くの憶測と疑念を引き起こしましたが、長年にわたる DES の調査により、IBM が発案した DES の設計変更に NSA が関与したのは、主に DES を強化するためだったことがわかっています。DES に隠された、または特別な弱点が見つかったという発表はありません。SHA アルゴリズムを生成するために NSA が MD4 を変更したことで、同様にこれらのアルゴリズムが強化され、おそらく一般の暗号コミュニティではまだ知られていない脅威に対して強化されたと考えられます。
Where input lengths are unpredictable, hash algorithms are more convenient to use than block encryption algorithms since they are generally designed to accept variable length inputs. Block encryption algorithms generally require an additional padding algorithm to accommodate inputs that are not an even multiple of the block size.
入力長が予測不可能である場合、ハッシュアルゴリズムは、一般に可変長入力を受け入れるように設計されているため、ブロック暗号化アルゴリズムよりも使用が便利です。ブロック暗号化アルゴリズムでは、一般に、ブロックサイズの偶数倍ではない入力に対応するための追加のパディングアルゴリズムが必要です。
As of the time of this document, the authors know of no patent claims to the basic AES, DES, SHA*, MD4, and MD5 algorithms other than patents for which an irrevocable royalty free license has been granted to the world. There may, of course, be essential patents of which the authors are unaware or patents on implementations or uses or other relevant patents issued or to be issued.
この文書の執筆時点では、取り消し不能なロイヤリティフリーのライセンスが全世界に付与されている特許を除き、基本的な AES、DES、SHA*、MD4、および MD5 アルゴリズムに対する特許請求は著者らは知りません。もちろん、著者らが知らない必須特許や、実装または使用に関する特許、あるいは発行済みまたは発行予定のその他の関連特許が存在する可能性もあります。
When a seed has sufficient entropy, from input as described in Section 3 and possibly de-skewed and mixed as described in Sections 4 and 5, one can algorithmically extend that seed to produce a large number of cryptographically-strong random quantities. Such algorithms are platform independent and can operate in the same fashion on any computer. For the algorithms to be secure, their input and internal workings must be protected from adversarial observation.
セクション3および5に記載されているように、シードが十分なエントロピーを、セクション4および5に記載されているように歪んで混合された場合、そのシードをアルゴリズム的に拡張して、多数の暗号的に強いランダムな量を生成することができる。そのようなアルゴリズムはプラットフォームに依存しないため、どのコンピュータでも同じ方法で動作できます。アルゴリズムが安全であるためには、それらの入力と内部の作業は敵対的な観察から保護されなければなりません。
The design of such pseudo-random number generation algorithms, like the design of symmetric encryption algorithms, is not a task for amateurs. Section 6.1 below lists a number of bad ideas that failed algorithms have used. To learn what works, skip Section 6.1 and just read the remainder of this section and Section 7, which describes and references some standard pseudo random number generation algorithms. See Section 7 and Part 3 of [X9.82].
このような疑似乱数生成アルゴリズムの設計は、対称暗号化アルゴリズムの設計と同様に、アマチュアの仕事ではありません。以下のセクション 6.1 では、失敗したアルゴリズムで使用されたいくつかの悪いアイデアをリストします。何が機能するかを学ぶには、セクション 6.1 をスキップして、このセクションの残りの部分と、いくつかの標準的な疑似乱数生成アルゴリズムについて説明し、参照しているセクション 7 だけを読んでください。[X9.82] のセクション 7 とパート 3 を参照してください。
The subsections below describe a number of ideas that might seem reasonable but that lead to insecure pseudo-random number generation.
以降の節では、一見合理的に見えるかもしれないが、それが不安な擬似乱数生成につながるかもしれない多くのアイデアを説明しています。
One approach that may give a misleading appearance of unpredictability is to take a very complex algorithm (or an excellent traditional pseudo-random number generator with good statistical properties) and to calculate a cryptographic key by starting with limited data such as the computer system clock value as the seed. Adversaries who knew roughly when the generator was started would have a relatively small number of seed values to test, as they would know likely values of the system clock. Large numbers of pseudo- random bits could be generated, but the search space that an adversary would need to check could be quite small.
予測不可能性の誤解を招く可能性のある外観を与える可能性がある1つのアプローチは、非常に複雑なアルゴリズム（または優れた統計的プロパティを持つ優れた従来の疑似乱数発生器）を取り、コンピュータシステムクロック値などの制限されたデータを開始することによって暗号鍵を計算することです。種として。生成器が開始されたときにおおよそ知っていた敵対者は、システムクロックの値の可能性が高いことを知っているので、テストするシード値の数が比較的少数であろう。多数の擬似ランダムビットを生成することができますが、敵対者がチェックする必要がある検索スペースはかなり小さいかもしれません。
Thus, very strong or complex manipulation of data will not help if the adversary can learn what the manipulation is and if there is not enough entropy in the starting seed value. They can usually use the limited number of results stemming from a limited number of seed values to defeat security.
したがって、敵対者が操作が何であるか、および開始シード値に十分なエントロピーがない場合には、データの非常に強いまたは複雑な操作が役立ちません。それらは通常、限られた数のシード値からの限られた数の結果を使用してセキュリティを軽減することができます。
Another serious strategic error is to assume that a very complex pseudo-random number generation algorithm will produce strong random numbers, when there has been no theory behind or analysis of the algorithm. There is a excellent example of this fallacy near the beginning of Chapter 3 in [KNUTH], where the author describes a complex algorithm. It was intended that the machine language program corresponding to the algorithm would be so complicated that a person trying to read the code without comments wouldn't know what the program was doing. Unfortunately, actual use of this algorithm showed that it almost immediately converged to a single repeated value in one case and a small cycle of values in another case.
もう1つの重大な戦略的エラーは、アルゴリズムの背後にある理論や分析がない場合、非常に複雑な擬似乱数生成アルゴリズムが強い乱数を生成すると仮定することです。この誤謬の優れた例が、「Knuth」の最初の初めに近い例があります。ここで、著者は複雑なアルゴリズムを説明しています。このアルゴリズムに対応する機械語プログラムは、コメントなしでコードを読みようとしている人がプログラムが何をしていたのかわからないことを理解することが意図されていました。残念ながら、このアルゴリズムの実際の使用は、1つのケースで1つの繰り返し値と別の場合には小さいサイクルの値にほぼ直ちに収束することを示しました。
Not only does complex manipulation not help you if you have a limited range of seeds, but blindly-chosen complex manipulation can destroy the entropy in a good seed!
シードの範囲が限られている場合、複雑な操作は役に立たないだけでなく、盲目的に選択された複雑な操作は、適切なシードのエントロピーを破壊する可能性があります。
Another approach that can give a misleading appearance of unpredictability is to randomly select a quantity from a database and to assume that its strength is related to the total number of bits in the database. For example, typical USENET servers process many megabytes of information per day [USENET_1, USENET_2]. Assume that a random quantity was selected by fetching 32 bytes of data from a random starting point in this data. This does not yield 32*8 = 256 bits worth of unguessability. Even if much of the data is human language that contains no more than 2 or 3 bits of information per byte, it doesn't yield 32*2 = 64 bits of unguessability. For an adversary with access to the same Usenet database, the unguessability rests only on the starting point of the selection. That is perhaps a little over a couple of dozen bits of unguessability.
予測不可能性の誤解を招く可能性を与えることができるもう1つの方法は、データベースから数量をランダムに選択し、その強さがデータベース内のビットの総数に関連していると仮定することです。たとえば、典型的なUSENETサーバーは、1日あたりの多くのメガバイトの情報をプロセスします[USENET_1、USENET_2]。このデータのランダムな開始点から32バイトのデータを取得することによってランダムな数量が選択されたとする。これは、32 * 8 = 256ビット価値のない不履行性をもたらさない。データの大部分が1バイト当たり2または3ビット以下の情報を含む人類言語であっても、不合格性の32 * 2 = 64ビットではありません。同じUSENETデータベースへのアクセスを持つ敵対者の場合、不正な性別は選択の開始点でのみ依頼します。それはおそらく数十二十分の不気味なビットにわたって少しずつです。
The same argument applies to selecting sequences from the data on a publicly available CD/DVD recording or any other large public database. If the adversary has access to the same database, this "selection from a large volume of data" step buys little. However, if a selection can be made from data to which the adversary has no access, such as system buffers on an active multi-user system, it may be of help.
同じ議論は、公開されている CD/DVD 記録またはその他の大規模な公開データベースのデータからシーケンスを選択する場合にも当てはまります。攻撃者が同じデータベースにアクセスできる場合、この「大量のデータから選択する」手順ではほとんど意味がありません。ただし、アクティブなマルチユーザー システムのシステム バッファーなど、攻撃者がアクセスできないデータから選択できる場合は、役に立つ可能性があります。
This section talks about traditional sources of deterministic or "pseudo-random" numbers. These typically start with a "seed" quantity and use simple numeric or logical operations to produce a sequence of values. Note that none of the techniques discussed in this section is suitable for cryptographic use. They are presented for general information.
このセクションでは、伝統的な決定論的または「疑似ランダム」数の源について説明します。これらは通常、「シード」の量で始まり、単純な数値または論理演算を使用して一連の値を生成します。このセクションで説明されているテクニックのどれも暗号化の使用に適していません。それらは一般的な情報のために提示されています。
[KNUTH] has a classic exposition on pseudo-random numbers. Applications he mentions are simulations of natural phenomena, sampling, numerical analysis, testing computer programs, decision making, and games. None of these have the same characteristics as the sorts of security uses we are talking about. Only in the last two could there be an adversary trying to find the random quantity. However, in these cases, the adversary normally has only a single chance to use a guessed value. In guessing passwords or attempting to break an encryption scheme, the adversary normally has many, perhaps unlimited, chances at guessing the correct value. Sometimes the adversary can store the message to be broken and repeatedly attack it. Adversaries are also be assumed to be aided by a computer.
[Knuth]は擬似乱数に古典的な博覧会を持っています。適用彼は、自然現象、サンプリング、数値解析、テストコンピュータプログラム、意思決定、およびゲームのシミュレーションです。これらのどれも、私たちが話しているセキュリティの種類と同じ特性を持っていません。最後の2つだけでは、ランダムな量を見つけようとしている敵対的なものがある可能性があります。しかし、これらの場合、敵対者は通常、推測値を使用する機会が1つだけです。パスワードを推測するか暗号化方式を破ることを試みると、敵対者は正しい値を推測することで、通常、多くの人、おそらく無制限です。時々敵対者は壊れて繰り返し攻撃するようにメッセージを保存することができます。敵対者はまた、コンピュータによって支援されると仮定されています。
For testing the "randomness" of numbers, Knuth suggests a variety of measures, including statistical and spectral. These tests check things like autocorrelation between different parts of a "random" sequence or distribution of its values. But these tests could be met by a constant stored random sequence, such as the "random" sequence printed in the CRC Standard Mathematical Tables [CRC]. Despite meeting all the tests suggested by Knuth, that sequence is unsuitable for cryptographic us, as adversaries must be assumed to have copies of all commonly published "random" sequences and to be able to spot the source and predict future values.
数字の「ランダム性」をテストするために、ノードは統計的およびスペクトルを含むさまざまな尺度を示唆しています。これらのテストは、「ランダムな」シーケンスの異なる部分またはその値の分布の間の自己相関のようなものをチェックします。しかし、これらのテストは、CRC標準の数学表[CRC]で印刷された「ランダム」シーケンスのような一定の格納されたランダムシーケンスによって満たすことができます。ノースで提案されたすべてのテストを満たすにもかかわらず、そのシーケンスは暗号化米国には不適切であるため、敵対者は一般に公開されたすべての「ランダムな「ランダムな」シーケンスのコピーを持ち、将来の値を予測できるようにする必要があるためです。
A typical pseudo-random number generation technique is the linear congruence pseudo-random number generator. This technique uses modular arithmetic, where the value numbered N+1 is calculated from the value numbered N by
典型的な擬似乱数生成技術は線形合同擬似乱数生成器である。この技術はモジュラー演算を使用し、N+1の値はNの値から次のように計算される。
V = ( V * a + b )(Mod c)
N+1 N
The above technique has a strong relationship to linear shift register pseudo-random number generators, which are well understood cryptographically [SHIFT*]. In such generators, bits are introduced at one end of a shift register as the Exclusive Or (binary sum without carry) of bits from selected fixed taps into the register. For example, consider the following:
上記の手法は、暗号学的によく理解されている線形シフト レジスタ疑似乱数ジェネレータと密接な関係があります [SHIFT*]。このようなジェネレータでは、選択された固定タップからのビットの排他的論理和 (キャリーなしの 2 進和) として、シフト レジスタの一方の端にビットが導入されます。たとえば、次の例を考えてみましょう。
+----+ +----+ +----+ +----+
| B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+
| 0 | | 1 | | 2 | | n | |
+----+ +----+ +----+ +----+ |
| | | |
| | V +-----+
| V +----------------> | |
V +-----------------------------> | XOR |
+---------------------------------------------------> | |
+-----+
V = ( ( V * 2 ) + B XOR B ... )(Mod 2^n)
N+1 N 0 2
The quality of traditional pseudo-random number generator algorithms is measured by statistical tests on such sequences. Carefully-chosen values a, b, c, and initial V or carefully-chosen placement of the shift register tap in the above simple process can produce excellent statistics.
従来の擬似乱数発生器アルゴリズムの品質は、そのようなシーケンス上の統計的検定によって測定されます。上記の簡単なプロセスにおけるシフトレジスタタップの慎重に選択された値A、B、C、および初期vまたは慎重に選択された配置は、優れた統計を生み出すことができる。
These sequences may be adequate in simulations (Monte Carlo experiments) as long as the sequence is orthogonal to the structure of the space being explored. Even there, subtle patterns may cause problems. However, such sequences are clearly bad for use in security applications. They are fully predictable if the initial state is known. Depending on the form of the pseudo-random number generator, the sequence may be determinable from observation of a short portion of the sequence [SCHNEIER, STERN]. For example, with the generators above, one can determine V(n+1) given knowledge of V(n). In fact, it has been shown that with these techniques, even if only one bit of the pseudo-random values are released, the seed can be determined from short sequences.
これらの配列は、シーケンスが調べられている空間の構造と直交している限り、シミュレーション（モンテカルロ実験）において適切であり得る。そこでも、微妙なパターンが問題を引き起こす可能性があります。しかしながら、そのようなシーケンスは、セキュリティアプリケーションでの使用には明らかに悪い。初期状態がわかっている場合、それらは完全に予測可能です。擬似乱数発生器の形態に応じて、シーケンスの短い部分[シュナエ、シュンテル]の観察から決定可能であり得る。例えば、上記の生成器では、V（n）の知識が与えられたV（n 1）を決定することができる。実際、これらの技術では、1ビットの疑似ランダム値のみが解放されていても、シードを短いシーケンスから決定することができることが示されている。
Not only have linear congruent generators been broken, but techniques are now known for breaking all polynomial congruent generators [KRAWCZYK].
線形一致生成器が壊れているだけでなく、すべての多項式合同生成器[Krawczyk]を破るために技術が知られています。
In cases where a series of random quantities must be generated, an adversary may learn some values in the sequence. In general, adversaries should not be able to predict other values from the ones that they know.
一連のランダムな量を生成しなければならない場合、敵対者はシーケンス内のいくつかの値を学ぶことができます。一般に、敵対者は彼らが知っているものから他の値を予測することができないはずです。
The correct technique is to start with a strong random seed, to take cryptographically strong steps from that seed [FERGUSON, SCHNEIER], and not to reveal the complete state of the generator in the sequence elements. If each value in the sequence can be calculated in a fixed way from the previous value, then when any value is compromised, all future values can be determined. This would be the case, for example, if each value were a constant function of the previously used values, even if the function were a very strong, non-invertible message digest function.
正しい手法は、強力なランダム シードから始めて、そのシードから暗号的に強力な手順を実行し [FERGUSON、SCHNEIER]、シーケンス要素のジェネレータの完全な状態を明らかにしないことです。シーケンス内の各値が前の値から固定された方法で計算できる場合、いずれかの値が侵害されたときに、将来のすべての値を特定できます。たとえば、各値が以前に使用された値の定数関数である場合、その関数が非常に強力で逆変換不可能なメッセージ ダイジェスト関数であっても、これが当てはまります。
(Note that if a technique for generating a sequence of key values is fast enough, it can trivially be used as the basis for a confidentiality system. If two parties use the same sequence generation technique and start with the same seed material, they will generate identical sequences. These could, for example, be XOR'ed at one end with data being sent to encrypt it, and XOR'ed with this data as received to decrypt it, due to the reversible properties of the XOR operation. This is commonly referred to as a simple stream cipher.)
(キー値のシーケンスを生成する技術が十分に高速であれば、機密保持システムの基礎として簡単に使用できることに注意してください。2 つの当事者が同じシーケンス生成技術を使用し、同じシード マテリアルから開始すると、同一のシーケンスが生成されます。たとえば、XOR 演算の可逆性により、一方の端で送信データと XOR 演算して暗号化し、受信したデータと XOR 演算して復号化することができます。これは、一般にシンプル ストリーム暗号と呼ばれます。)
One way to produce a strong sequence is to take a seed value and hash the quantities produced by concatenating the seed with successive integers, or the like, and then to mask the values obtained so as to limit the amount of generator state available to the adversary.
強いシーケンスを生成する1つの方法は、シード値をとり、シードを連続した整数または整数を含む量を連結してから生成された量をハッシュし、次いで敵対者に利用可能な発生器状態の量を制限するために得られた値をマスクすることである。。
It may also be possible to use an "encryption" algorithm with a random key and seed value to encrypt successive integers, as in counter (CTR) mode encryption. Alternatively, one can feedback all of the output value from encryption into the value to be encrypted for the next iteration. This is a particular example of output feedback mode (OFB) [MODES].
カウンタ（CTR）モード暗号化のように、連続する整数を暗号化するために、ランダムキーとシード値を使用して「暗号化」アルゴリズムを使用することも可能であり得る。あるいは、暗号化からのすべての出力値を次の反復のために暗号化される値にフィードバックすることができます。これは出力フィードバックモード（OFB）[モード]の特定の例です。
An example is shown below in which shifting and masking are used to combine part of the output feedback with part of the old input. This type of partial feedback should be avoided for reasons described below.
次に、出力フィードバックの一部を古い入力の一部と組み合わせるためにシフトとマスキングを使用する例を示します。以下に説明する理由で、このタイプの部分フィードバックを回避する必要があります。
+---------------+
| V |
| | n |--+
+--+------------+ |
| | +---------+
shift| +---> | | +-----+
+--+ | Encrypt | <--- | Key |
| +-------- | | +-----+
| | +---------+
V V
+------------+--+
| V | |
| n+1 |
+---------------+
Note that if a shift of one is used, this is the same as the shift register technique described in Section 6.1.3, but with the all-important difference that the feedback is determined by a complex non-linear function of all bits rather than by a simple linear or polynomial combination of output from a few bit position taps.
1つのシフトが使用されている場合、これはセクション6.1.3で説明されているシフトレジスタの技法と同じですが、フィードバックはすべてのビットの複雑な非線形関数によって決まることをすべての重要な差ではありません。数ビット位置タップからの出力の単純な線形または多項式の組み合わせによって。
Donald W. Davies showed that this sort of shifted partial output feedback significantly weakens an algorithm, compared to feeding all the output bits back as input. In particular, for DES, repeatedly encrypting a full 64-bit quantity will give an expected repeat in about 2^63 iterations. Feeding back anything less than 64 (and more than 0) bits will give an expected repeat in between 2^31 and 2^32 iterations!
Donald W. Davies は、このようなシフトされた部分的な出力フィードバックは、すべての出力ビットを入力としてフィードバックする場合と比べて、アルゴリズムを大幅に弱めることを示しました。特に DES の場合、64 ビットの量全体を繰り返し暗号化すると、約 2^63 回の反復で繰り返しが予想されます。64 ビット未満 (0 より大きい) のビットをフィードバックすると、2^31 回から 2^32 回の間で繰り返しが予想されます。
To predict values of a sequence from others when the sequence was generated by these techniques is equivalent to breaking the cryptosystem or to inverting the "non-invertible" hashing with only partial information available. The less information revealed in each iteration, the harder it will be for an adversary to predict the sequence. Thus it is best to use only one bit from each value. It has been shown that in some cases this makes it impossible to break a system even when the cryptographic system is invertible and could be broken if all of each generated value were revealed.
これらの技術によってシーケンスが生成された場合に、シーケンスの値を他のシーケンスから予測することは、暗号システムを破ること、または部分的な情報のみを使用して「非可逆」ハッシュを反転することと同じです。各反復で明らかにされる情報が少ないほど、敵がシーケンスを予測することが難しくなります。したがって、各値から 1 ビットのみを使用するのが最適です。場合によっては、暗号システムが可逆で、生成された各値がすべて明らかにされた場合に破られる可能性がある場合でも、これによりシステムを破ることができなくなることが示されています。
Currently the generator which has the strongest public proof of strength is called the Blum Blum Shub generator, named after its inventors [BBS]. It is also very simple and is based on quadratic residues. Its only disadvantage is that it is computationally intensive compared to the traditional techniques given in Section 6.1.3. This is not a major drawback if it is used for moderately-infrequent purposes, such as generating session keys.
現在、最も強力な公開強度証明を持つジェネレーターは、発明者 [BBS] にちなんで Blum Blum Shub ジェネレーターと呼ばれています。これは非常にシンプルで、2 乗剰余に基づいています。唯一の欠点は、セクション 6.1.3 で説明した従来の手法に比べて計算量が多いことです。ただし、セッション キーの生成など、あまり頻繁に使用されない目的で使用する場合は、大きな欠点にはなりません。
Simply choose two large prime numbers (say, p and q) that each gives a remainder of 3 when divided by 4. Let n = p * q. Then choose a random number, x, that is relatively prime to n. The initial seed for the generator and the method for calculating subsequent values are then:
4 で割ったときに 3 の余りになる 2 つの大きな素数 (たとえば p と q) を選択します。n = p * q とします。次に、n と互いに素である乱数 x を選択します。ジェネレータの初期シードと後続の値を計算する方法は次のようになります。
2
s = ( x )(Mod n)
0
2
s = ( s )(Mod n)
i+1 i
Be careful to use only a few bits from the bottom of each s. It is always safe to use only the lowest-order bit. If one uses no more than the:
各 s の下部から数ビットのみを使用するように注意してください。最下位ビットのみを使用するのが常に安全です。以下のいずれかのみを使用する場合:
log_2(log_2(s_i))
low-order bits, then predicting any additional bits from a sequence generated in this manner is provably as hard as factoring n. As long as the initial x is secret, n can be made public if desired.
下位ビットを予測する場合、この方法で生成されたシーケンスから追加のビットを予測することは、n を因数分解するのと同じくらい難しいことが証明されています。最初の x が秘密である限り、n は必要に応じて公開できます。
An interesting characteristic of this generator is that any of the s values can be directly calculated. In particular,
この生成器の興味深い特徴は、S値のいずれかを直接計算できることです。特に、
( (2^i) (Mod ((p-1)*(q-1)) ) )
s = ( s )(Mod n)
i 0
This means that in applications where many keys are generated in this fashion, it is not necessary to save them all. Each key can be effectively indexed and recovered from that small index and the initial s and n.
つまり、この方法で多数のキーが生成されるアプリケーションでは、すべてのキーを保存する必要はありません。各キーは、その小さなインデックスと最初の s と n から効果的にインデックス付けおよび復元できます。
Many modern pseudo-random number sources, such as those described in Sections 7.1.2 and 7.1.3 utilize the technique of maintaining a "pool" of bits and providing operations for strongly mixing input with some randomness into the pool and extracting pseudo-random bits from the pool. This is illustrated in the figure below.
セクション7.1.2および7.1.3に記載されているもののような多くの最新の疑似乱数ソースは、ビットの「プール」を維持し、いくつかのランダム性をプールに強く混合し、疑似ランダムを抽出するための操作を提供する技術を利用する。プールからのビット。これを下図に示します。
+--------+ +------+ +---------+
--->| Mix In |--->| POOL |--->| Extract |--->
| Bits | | | | Bits |
+--------+ +------+ +---------+
^ V
| |
+-----------+
Bits to be fed into the pool can come from any of the various hardware, environmental, or user input sources discussed above. It is also common to save the state of the pool on system shutdown and to restore it on re-starting, when stable storage is available.
プールに供給されるビットは、上述したさまざまなハードウェア、環境、またはユーザーの入力ソースのいずれかから来ることができます。システムシャットダウン時にプールの状態を保存し、安定したストレージが使用可能な場合は再起動時に復元することも一般的です。
Care must be taken that enough entropy has been added to the pool to support particular output uses desired. See [RSA_BULL1] for similar suggestions.
特定の出力使用をサポートするのに十分なエントロピーがプールに追加されたことを注意する必要があります。類似の提案については[RSA_BULL1]を参照してください。
Several public standards and widely deployed examples are now in place for the generation of keys or other cryptographically random quantities. Some, in section 7.1, include an entropy source. Others, described in section 7.2, provide the pseudo-random number strong-sequence generator but assume the input of a random seed or input from a source of entropy.
いくつかの公共標準および広く展開された例が、鍵の生成または他の暗号的にランダムな量のために任されています。セクション7.1では、エントロピーソースを含めます。セクション7.2で説明されている他のものは、疑似乱数強シーケンス発生器を提供しますが、ランダムなシードの入力またはエントロピー源からの入力を想定します。
Three standards are described below. The two older standards use DES, with its 64-bit block and key size limit, but any equally strong or stronger mixing function could be substituted [DES]. The third is a more modern and stronger standard based on SHA-1 [SHA*]. Lastly, the widely deployed modern UNIX and Windows random number generators are described.
3つの規格を以下に説明します。2つの古い標準は、その64ビットブロックとキーサイズの制限でDESを使用しますが、同様に強いまたは強い混合関数を代入することができます。3つ目は、SHA-1 [SHA*]に基づくより近代的で強力な標準です。最後に、広く展開された最新のUNIXおよびWindows乱数ジェネレータが記述されています。
The United States Department of Defense has specific recommendations for password generation [DoD]. It suggests using the US Data Encryption Standard [DES] in Output Feedback Mode [MODES] as follows:
米国国防総省は、パスワード生成に関する具体的な推奨事項を持っています[DOD]。次のように、出力フィードバックモード[MODES]のUSデータ暗号化標準[DES]を使用することをお勧めします。
Use an initialization vector determined from the system clock, system ID, user ID, and date and time; use a key determined from system interrupt registers, system status registers, and system counters; and, as plain text, use an external randomly generated 64-bit quantity such as the ASCII bytes for 8 characters typed in by a system administrator.
システムクロック、システムID、ユーザーID、および日時から決定された初期化ベクトルを使用してください。システム割り込みレジスタ、システムステータスレジスタ、およびシステムカウンタから決定されたキーを使用してください。また、プレーンテキストとして、システム管理者が入力した8文字のASCIIバイトなど、外部ランダムに生成された64ビット数量を使用します。
The password can then be calculated from the 64 bit "cipher text" generated by DES in 64-bit Output Feedback Mode. As many bits as are needed can be taken from these 64 bits and expanded into a pronounceable word, phrase, or other format if a human being needs to remember the password.
パスワードは、64ビット出力フィードバックモードで生成された64ビットの「暗号テキスト」から計算できます。必要なのと同じくらい多くのビットをこれらの64ビットから取得することができ、人間がパスワードを覚えている必要がある場合は、発音不可の単語、フレーズ、またはその他のフォーマットに拡張されます。
Several versions of the UNIX operating system provide a kernel-resident random number generator. Some of these generators use events captured by the Kernel during normal system operation.
UNIXオペレーティングシステムのいくつかのバージョンがカーネル - 常駐乱数発生器を提供します。これらのジェネレータの中には、通常のシステム操作中にカーネルによってキャプチャされたイベントを使用します。
For example, on some versions of Linux, the generator consists of a random pool of 512 bytes represented as 128 words of 4 bytes each. When an event occurs, such as a disk drive interrupt, the time of the event is XOR'ed into the pool, and the pool is stirred via a primitive polynomial of degree 128. The pool itself is treated as a ring buffer, with new data being XOR'ed (after stirring with the polynomial) across the entire pool.
たとえば、いくつかのバージョンのLinuxでは、ジェネレータは4バイトの4バイトの128ワードとして表される512バイトのランダムプールで構成されています。ディスクドライブ割り込みなどのイベントが発生した場合、イベントの時刻はプールにXORされ、プールは次数128の原始多項式を介して攪拌されます。プール自体はリングバッファとして扱われます。プール全体にわたって（多項式で撹拌した後）データがXor 'されています。
Each call that adds entropy to the pool estimates the amount of likely true entropy the input contains. The pool itself contains a accumulator that estimates the total over all entropy of the pool.
プールにエントロピーを追加する各呼び出しは、入力に含まれる本当のエントロピーの可能性の高い量を推定します。プール自体には、プールのすべてのエントロピーを越えて合計を推定するアキュムレータが含まれています。
Input events come from several sources, as listed below. Unfortunately, for server machines without human operators, the first and third are not available, and entropy may be added slowly in that case.
入力イベントは以下のようにいくつかのソースから来ています。残念ながら、人間の演算子がないサーバーマシンの場合、最初と3番目は利用できず、その場合はエントロピーをゆっくり追加することができます。
1. Keyboard interrupts. The time of the interrupt and the scan code are added to the pool. This in effect adds entropy from the human operator by measuring inter-keystroke arrival times.
1. キーボード割り込み割り込みの時間とスキャンコードがプールに追加されます。これは、キー間到着時間を測定することによって、人間のオペレータからエントロピーを追加します。
2. Disk completion and other interrupts. A system being used by a person will likely have a hard-to-predict pattern of disk accesses. (But not all disk drivers support capturing this timing information with sufficient accuracy to be useful.)
2.ディスクの完了とその他の割り込み。人が使用しているシステムは、予測困難なディスクアクセスのパターンを持つ可能性があります。（ただし、すべてのディスクドライバがこのタイミング情報をキャプチャするのではありません。
3. Mouse motion. The timing and mouse position are added in.
3. マウスの動きタイミングとマウスの位置が追加されます。
When random bytes are required, the pool is hashed with SHA-1 [SHA*] to yield the returned bytes of randomness. If more bytes are required than the output of SHA-1 (20 bytes), then the hashed output is stirred back into the pool and a new hash is performed to obtain the next 20 bytes. As bytes are removed from the pool, the estimate of entropy is correspondingly decremented.
ランダムバイトが必要な場合は、プールをSHA-1 [SHA *]でハッシュして、返されたランダム性のバイトを生成します。SHA-1（20バイト）の出力よりも多くのバイトが必要な場合は、ハッシュ出力をプール内に戻し、次の20バイトを取得するために新しいハッシュが実行されます。バイトがプールから取り外されると、エントロピーの推定値はそれに対応して減分されます。
To ensure a reasonably random pool upon system startup, the standard startup and shutdown scripts save the pool to a disk file at shutdown and read this file at system startup.
システムの起動時に合理的にランダムなプールを確保するために、標準の起動とシャットダウンスクリプトは、シャットダウン時にプールをディスクファイルに保存し、システム起動時にこのファイルを読み込みます。
There are two user-exported interfaces. /dev/random returns bytes from the pool but blocks when the estimated entropy drops to zero. As entropy is added to the pool from events, more data becomes available via /dev/random. Random data obtained from such a /dev/random device is suitable for key generation for long term keys, if enough random bits are in the pool or are added in a reasonable amount of time.
ユーザーエクスポートされたインターフェイスが2つあります。/dev/random プールからバイトを返しますが、推定エントロピーがゼロになるとブロックします。エントロピーがイベントからプールに追加されると、/dev/random を介してデータが多くなる。そのような /dev/random デバイスから得られたランダムデータは、十分なランダムビットがプール内にあるか、または妥当な時間で追加されている場合、長期キーの鍵生成に適しています。
/dev/urandom works like /dev/random; however, it provides data even when the entropy estimate for the random pool drops to zero. This may be adequate for session keys or for other key generation tasks for which blocking to await more random bits is not acceptable. The risk of continuing to take data even when the pool's entropy estimate is small in that past output may be computable from current output, provided that an attacker can reverse SHA-1. Given that SHA-1 is designed to be non-invertible, this is a reasonable risk.
/dev/urandom は /dev/random と同様に動作しますが、ランダム プールのエントロピー推定値がゼロになった場合でもデータを提供します。これは、セッション キーや、ランダム ビットを待つためにブロックすることが許容されないその他のキー生成タスクには適している可能性があります。攻撃者が SHA-1 を逆変換できる場合、プールのエントロピー推定値が小さい場合でも、データを取得し続けるリスクは、過去の出力が現在の出力から計算できる可能性があるからです。SHA-1 は逆変換できないように設計されているため、これは妥当なリスクです。
To obtain random numbers under Linux, Solaris, or other UNIX systems equipped with code as described above, all an application has to do is open either /dev/random or /dev/urandom and read the desired number of bytes.
上記のようなコードを搭載したLinux、Solaris、または他のUNIXシステムの下で乱数を取得するには、すべてのアプリケーションが /dev/random または /dev/urandom のいずれかを開く必要があり、必要なバイト数を読み取る必要があります。
(The Linux Random device was written by Theodore Ts'o. It was based loosely on the random number generator in PGP 2.X and PGP 3.0 (aka PGP 5.0).)
(Linux の Random デバイスは Theodore Ts'o によって作成されました。これは PGP 2.X および PGP 3.0 (別名 PGP 5.0) の乱数ジェネレーターを大まかにベースにしています。)
Microsoft's recommendation to users of the widely deployed Windows operating system is generally to use the CryptGenRandom pseudo-random number generation call with the CryptAPI cryptographic service provider. This takes a handle to a cryptographic service provider library, a pointer to a buffer by which the caller can provide entropy and into which the generated pseudo-randomness is returned, and an indication of how many octets of randomness are desired.
広く展開されているWindowsオペレーティングシステムのユーザーへのマイクロソフトの推奨事項は、一般的に、CryptAPI暗号化サービスプロバイダを使用してCryptGenrandom擬似乱数生成呼び出しを使用することです。これにより、暗号化サービスプロバイダライブラリにハンドルが取り込まれ、発信者がエントロピーを提供することができ、生成された擬似ランダム性が返される可能性があるバッファへのポインタ、およびランダム性の数のオクテットが望まれることがある。
The Windows CryptAPI cryptographic service provider stores a seed state variable with every user. When CryptGenRandom is called, this is combined with any randomness provided in the call and with various system and user data such as the process ID, thread ID, system clock, system time, system counter, memory status, free disk clusters, and hashed user environment block. This data is all fed to SHA-1, and the output is used to seed an RC4 key stream. That key stream is used to produce the pseudo-random data requested and to update the user's seed state variable.
Windows暗号化暗号化サービスプロバイダは、シード状態変数をすべてのユーザーに格納します。CryptGenRandomが呼び出されると、これは、呼び出しに提供され、プロセスID、スレッドID、システムクロック、システム時間、システムカウンタ、メモリステータス、空きディスククラスタ、およびハッシュされたユーザーなどのさまざまなシステムとユーザーデータと組み合わされます。環境ブロックこのデータはすべてSHA-1に供給され、出力はRC4キーストリームをシードするために使用されます。そのキーストリームは、要求された疑似ランダムデータを生成し、ユーザーのシード状態変数を更新するために使用されます。
Users of Windows ".NET" will probably find it easier to use the RNGCryptoServiceProvider.GetBytes method interface.
Windows ".NET"のユーザーは、RNGCryptoServiceProvider.GetBytesメソッドインターフェイスを使いやすくすることが容易になります。
For further information, see [WSC].
詳細については、[WSC]を参照してください。
The pseudo-random number generators described in the following three sections all assume that a seed value with sufficient entropy is provided to them. They then generate a strong sequence (see Section 6.2) from that seed.
以下の3つのセクションで説明されている擬似乱数発生器はすべて、十分なエントロピーを持つシード値がそれらに提供されていると仮定します。それから彼らはその種から強いシーケンス（セクション6.2を参照）を生成します。
The ANSI X9F1 committee is in the final stages of creating a standard for random number generation covering both true randomness generators and pseudo-random number generators. It includes a number of pseudo-random number generators based on hash functions, one of which will probably be based on HMAC SHA hash constructs [RFC2104]. The draft version of this generator is described below, omitting a number of optional features [X9.82].
ANSI X9F1委員会は、真のランダム性発生器と擬似乱数発生器の両方をカバーする乱数生成のための標準を作成する最終段階にあります。それはハッシュ関数に基づく数多くの擬似乱数発生器を含み、そのうちの1つはおそらくHMAC SHAハッシュ構築物[RFC2104]に基づいているでしょう。この生成器のドラフトバージョンは以下のとおりです。
In the subsections below, the HMAC hash construct is simply referred to as HMAC but, of course, a particular standard SHA function must be selected in an particular use. Generally speaking, if the strength of the pseudo-random values to be generated is to be N bits, the SHA function chosen must generate N or more bits of output, and a source of at least N bits of input entropy will be required. The same hash function must be used throughout an instantiation of this generator.
以下のサブセクションでは、HMACハッシュ構文は単にHMACと呼ばれますが、もちろん、特定の標準SHA関数を特定の用途で選択する必要があります。一般的に言って、生成される擬似ランダム値の強度がNビットである場合、選択されたSHA関数は、N個以上の出力ビットを生成しなければならず、入力エントロピーの少なくともNビットのソースが必要とされなければならない。このジェネレータのインスタンス化を通して同じハッシュ関数を使用する必要があります。
In the following sections, the notation give below is used:
以下のセクションでは、以下の表記法が使用されます。
hash_length is the output size of the underlying hash function in use.
Hash_Lengthは、使用中の基礎となるハッシュ関数の出力サイズです。
input_entropy is the input bit string that provides entropy to the generator.
INPUT_ENTROPYは、ジェネレータにエントロピーを提供する入力ビット列です。
K is a bit string of size hash_length that is part of the state of the generator and is updated at least once each time random bits are generated.
kは、ジェネレータの状態の一部であり、ランダムビットが生成されるたびに少なくとも1回更新されるサイズhash_lengthのビット列である。
V is a bit string of size hash_length and is part of the state of the generator. It is updated each time hash_length bits of output are generated.
vはサイズhash_lengthのビット列であり、ジェネレータの状態の一部です。HASH_LENGTHビットが生成されるたびに更新されます。
"|" represents concatenation.
"|" は結合を表します。
Set V to all zero bytes, except the low-order bit of each byte is set to one.
各バイトの下位ビットが1に設定されていることを除いて、Vをすべてのゼロバイトに設定します。
Set K to all zero bytes, then set:
kをすべてのゼロバイトに設定してから設定します。
K = HMAC ( K, V | 0x00 | input_entropy )
V = HMAC ( K, V )
K = HMAC ( K, V | 0x01 | input_entropy )
V = HMAC ( K, V )
Note: All SHA algorithms produce an integral number of bytes, so the lengths of K and V will be integral numbers of bytes.
注: すべての SHA アルゴリズムは整数バイトを生成するため、K と V の長さは整数バイトになります。
When output is called for, simply set:
出力が必要な場合は、次のように設定するだけです。
V = HMAC ( K, V )
and use the leading bits from V. If more bits are needed than the length of V, set "temp" to a null bit string and then repeatedly perform:
V の先頭ビットを使用します。V の長さよりも多くのビットが必要な場合は、「temp」をヌルビット文字列に設定し、次の操作を繰り返し実行します。
V = HMAC ( K, V )
temp = temp | V
stopping as soon as temp is equal to or longer than the number of random bits requested. Use the requested number of leading bits from temp. The definition of the algorithm prohibits requesting more than 2^35 bits.
temp が要求されたランダム ビット数以上になるとすぐに停止します。temp から要求された数の先頭ビットを使用します。アルゴリズムの定義では、2^35 ビットを超える要求は禁止されています。
After extracting and saving the pseudo-random output bits as described above, before returning you must also perform two more HMACs as follows:
上記のように疑似ランダム出力ビットを抽出して保存した後、戻る前に、次のようにさらに 2 つの HMAC を実行する必要があります。
K = HMAC ( K, V | 0x00 )
V = HMAC ( K, V )
The American National Standards Institute has specified the following method for generating a sequence of keys [X9.17]:
American National Standards Instituteは、次の手順を作成するための次の方法を指定しました[X9.17]
s_0 is the initial 64 bit seed.
s_0 は最初の64ビットシードです。
g_0 is the sequence of generated 64-bit key quantities
g_0 は生成された64ビット鍵数nのシーケンスです
k is a random key reserved for generating this key sequence.
kはこのキーシーケンスを生成するために予約されているランダムキーです。
t is the time at which a key is generated, to as fine a resolution as is available (up to 64 bits).
Tは、鍵が生成される時刻であり、利用可能な（最大64ビット）のように細かい解像度として。
DES ( K, Q ) is the DES encryption of quantity Q with key K.
DES ( K, Q ) は、キーKとの数量QのDES暗号化です。
Then:
それから：
g = DES ( k, DES ( k, t ) XOR s )
n n
s = DES ( k, DES ( k, t ) XOR g )
n+1 n
If g sub n is to be used as a DES key, then every eighth bit should be adjusted for parity for that use, but the entire 64 bit unmodified g should be used in calculating the next s.
G SUB NがDESキーとして使用される場合、その使用のためにすべての8ビットをパリティに調整する必要がありますが、64ビットの未修正G全体を次のSの計算に使用する必要があります。
Appendix 3 of the NIST Digital Signature Standard [DSS] provides a method of producing a sequence of pseudo-random 160 bit quantities for use as private keys or the like. This has been modified by Change Notice 1 [DSS_CN1] to produce the following algorithm for generating general-purpose pseudo-random numbers:
NIST デジタル署名標準 [DSS] の付録 3 では、秘密鍵などとして使用するための 160 ビットの疑似乱数シーケンスを生成する方法が提供されています。これは変更通知 1 [DSS_CN1] によって変更され、汎用疑似乱数を生成する次のアルゴリズムが生成されます。
t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0
XKEY = initial seed
0
For j = 0 to ...
XVAL = ( XKEY + optional user input ) (Mod 2^512)
j
X = G( t, XVAL )
j
XKEY = ( 1 + XKEY + X ) (Mod 2^512)
j+1 j j
The quantities X thus produced are the pseudo-random sequence of 160-bit values. Two functions can be used for "G" above. Each produces a 160-bit value and takes two arguments, a 160-bit value and a 512 bit value.
このようにして生成された量 X は、160 ビット値の疑似ランダム シーケンスです。上記の「G」には 2 つの関数を使用できます。それぞれが 160 ビット値を生成し、160 ビット値と 512 ビット値の 2 つの引数を取ります。
The first is based on SHA-1 and works by setting the 5 linking variables, denoted H with subscripts in the SHA-1 specification, to the first argument divided into fifths. Then steps (a) through (e) of section 7 of the NIST SHA-1 specification are run over the second argument as if it were a 512-bit data block. The values of the linking variable after those steps are then concatenated to produce the output of G [SHA*].
最初の方法は SHA-1 に基づいており、5 つのリンク変数 (SHA-1 仕様では下付き文字で H と表記) を 5 等分された最初の引数に設定することで機能します。次に、NIST SHA-1 仕様のセクション 7 の手順 (a) から (e) が、2 番目の引数に対して 512 ビットのデータ ブロックであるかのように実行されます。これらの手順の後のリンク変数の値は連結され、G [SHA*] の出力が生成されます。
As an alternative method, NIST also defined an alternate G function based on multiple applications of the DES encryption function [DSS].
代替方法として、NIST は DES 暗号化関数 [DSS] の複数のアプリケーションに基づく代替 G 関数も定義しました。
Below are two examples showing rough calculations of randomness needed for security. The first is for moderate security passwords, while the second assumes a need for a very high-security cryptographic key.
以下は、セキュリティに必要なランダム性の大まかな計算を示す2つの例です。1つ目は中程度のセキュリティパスワードのためのものですが、2番目のセキュリティは非常に高いセキュリティの暗号化キーの必要性を想定しています。
In addition, [ORMAN] and [RSA_BULL13] provide information on the public key lengths that should be used for exchanging symmetric keys.
さらに、[ORMAN]と[RSA_BULL13]は、対称キーの交換に使用される公開鍵の長さに関する情報を提供します。
Assume that user passwords change once a year and that it is desired that the probability that an adversary could guess the password for a particular account be less than one in a thousand. Further assume that sending a password to the system is the only way to try a password. Then the crucial question is how often an adversary can try possibilities. Assume that delays have been introduced into a system so that an adversary can make at most one password try every six seconds. That's 600 per hour, or about 15,000 per day, or about 5,000,000 tries in a year. Assuming any sort of monitoring, it is unlikely that someone could actually try continuously for a year. Even if log files are only checked monthly, 500,000 tries is more plausible before the attack is noticed and steps are taken to change passwords and make it harder to try more passwords.
ユーザーのパスワードは 1 年に 1 回変更され、攻撃者が特定のアカウントのパスワードを推測できる確率は 1,000 分の 1 未満であることが望まれるものとします。さらに、パスワードを試す唯一の方法は、システムにパスワードを送信することであるとします。この場合、重要な問題は、攻撃者が可能性を試すことができる頻度です。システムに遅延が導入され、攻撃者が最大で 6 秒に 1 回のパスワード試行しかできないとします。これは、1 時間あたり 600 回、1 日あたり約 15,000 回、1 年あたり約 5,000,000 回の試行に相当します。何らかの監視が行われていると仮定すると、実際に誰かが 1 年間継続して試行することは考えにくいです。ログ ファイルを毎月のみチェックする場合でも、攻撃に気付き、パスワードを変更してそれ以上のパスワードの試行を困難にする手順が踏まれるまでに、500,000 回の試行の方が妥当です。
To have a one-in-a-thousand chance of guessing the password in 500,000 tries implies a universe of at least 500,000,000 passwords, or about 2^29. Thus, 29 bits of randomness are needed. This can probably be achieved by using the US DoD-recommended inputs for password generation, as it has 8 inputs that probably average over 5 bits of randomness each (see section 7.1). Using a list of 1,000 words, the password could be expressed as a three-word phrase (1,000,000,000 possibilities). By using case-insensitive letters and digits, six characters would suffice ((26+10)^6 = 2,176,782,336 possibilities).
500,000 回の試行でパスワードを推測できる確率が 1,000 分の 1 であるということは、少なくとも 500,000,000 個のパスワード、つまり約 2^29 個のパスワードが存在することを意味します。したがって、29 ビットのランダム性が必要です。これは、米国国防総省が推奨するパスワード生成の入力を使用することで実現できる可能性があります。この入力には、それぞれ平均して 5 ビットを超えるランダム性を持つ 8 つの入力があるためです (セクション 7.1 を参照)。1,000 語のリストを使用すると、パスワードは 3 語のフレーズとして表現できます (1,000,000,000 通りの可能性)。大文字と小文字を区別しない文字と数字を使用すると、6 文字で十分です ((26+10)^6 = 2,176,782,336 通りの可能性)。
For a higher-security password, the number of bits required goes up. To decrease the probability by 1,000 requires increasing the universe of passwords by the same factor, which adds about 10 bits. Thus, to have only a one in a million chance of a password being guessed under the above scenario would require 39 bits of randomness and a password that was a four-word phrase from a 1,000 word list, or eight letters/digits. To go to a one-in-10^9 chance, 49 bits of randomness are needed, implying a five-word phrase or a ten-letter/digit password.
よりセキュリティの高いパスワードの場合、必要なビット数が増えます。確率を 1,000 倍下げるには、パスワードの範囲を同じ係数で増やす必要があり、約 10 ビットが追加されます。したがって、上記のシナリオでパスワードが推測される確率を 100 万分の 1 にするには、39 ビットのランダム性と、1,000 語のリストから 4 語のフレーズ、または 8 文字/数字のパスワードが必要になります。確率を 10^9 分の 1 にするには、49 ビットのランダム性が必要であり、5 語のフレーズまたは 10 文字/数字のパスワードが必要になります。
In a real system, of course, there are other factors. For example, the larger and harder to remember passwords are, the more likely users will bed to write them down, resulting in an additional risk of compromise.
もちろん、実際のシステムでは、他の要因もあります。たとえば、パスワードが長くて覚えにくいほど、ユーザーがそれを書き留める可能性が高くなり、侵害のリスクが高まります。
Assume that a very high security key is needed for symmetric encryption/decryption between two parties. Assume also that an adversary can observe communications and knows the algorithm being used. Within the field of random possibilities, the adversary can try key values in hopes of finding the one in use. Assume further that brute force trial of keys is the best the adversary can do.
2つの当事者間の対称暗号化/復号化には非常に高いセキュリティキーが必要とされているとします。また、敵対者が通信を観察し、使用されているアルゴリズムを知っていると仮定する。ランダムな可能性の分野内で、敵対者は使用中のものを見つけることを期待して重要な値を試すことができます。さらに鍵のブルートフォース試験が敵対者ができることができることをさらに想定していると仮定する。
How much effort will it take to try each key? For very high-security applications, it is best to assume a low value of effort. Even if it would clearly take tens of thousands of computer cycles or more to try a single key, there may be some pattern that enables huge blocks of key values to be tested with much less effort per key. Thus, it is probably best to assume no more than a couple of hundred cycles per key. (There is no clear lower bound on this, as computers operate in parallel on a number of bits and a poor encryption algorithm could allow many keys or even groups of keys to be tested in parallel. However, we need to assume some value and can hope that a reasonably strong algorithm has been chosen for our hypothetical high-security task.)
各キーを試すのにどれくらいの労力がかかりますか? 非常に高度なセキュリティが求められるアプリケーションの場合、労力は低いと想定するのが最善です。 1 つのキーを試すのに明らかに何万回ものコンピュータ サイクル以上かかる場合でも、キーごとにはるかに少ない労力でキー値の巨大なブロックをテストできるパターンがあるかもしれません。 したがって、キーごとに数百サイクル以下と想定するのが最善でしょう。 (コンピューターは多数のビットで並列に動作し、暗号化アルゴリズムが貧弱だと多数のキーまたはキーのグループを並列にテストできるため、明確な下限はありません。 ただし、ある程度の労力を想定する必要があり、仮想的な高度なセキュリティ タスクには適度に強力なアルゴリズムが選択されていることを期待できます。)
If the adversary can command a highly parallel processor or a large network of work stations, 10^11 cycles per second is probably a minimum assumption today. Looking forward a few years, there should be at least an order of magnitude improvement. Thus, it is reasonable to assume that 10^10 keys could be checked per second, or 3.6*10^12 per hour or 6*10^14 per week, or 2.4*10^15 per month. This implies a need for a minimum of 63 bits of randomness in keys, to be sure that they cannot be found in a month. Even then it is possible that, a few years from now, a highly determined and resourceful adversary could break the key in 2 weeks; on average, they need try only half the keys.
敵が高度に並列化されたプロセッサや大規模なワークステーション ネットワークを制御できる場合、1 秒あたり 10^11 サイクルは、おそらく今日の最低想定です。数年後には、少なくとも 1 桁の改善が見られるはずです。したがって、1 秒あたり 10^10 個のキーをチェックできると想定するのが妥当です。つまり、1 時間あたり 3.6*10^12 個、1 週間あたり 6*10^14 個、1 か月あたり 2.4*10^15 個です。これは、1 か月以内にキーが見つからないようにするには、キーに最低 63 ビットのランダム性が必要であることを意味します。それでも、数年後には、非常に決意が固く機知に富んだ敵が 2 週間でキーを破る可能性があり、平均すると半分のキーを試すだけで済みます。
These questions are considered in detail in "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security: A Report by an Ad Hoc Group of Cryptographers and Computer Scientists" [KeyStudy] that was sponsored by the Business Software Alliance. It concluded that a reasonable key length in 1995 for very high security is in the range of 75 to 90 bits and, since the cost of cryptography does not vary much with the key size, it recommends 90 bits. To update these recommendations, just add 2/3 of a bit per year for Moore's law [MOORE]. This translates to a determination, in the year 2004, a reasonable key length is in the 81- to 96-bit range. In fact, today, it is increasingly common to use keys longer than 96 bits, such as 128-bit (or longer) keys with AES and keys with effective lengths of 112-bits with triple-DES.
これらの疑問については、Business Software Alliance が後援した「適切な商用セキュリティを提供するための対称暗号の最小キー長: 暗号学者とコンピュータ科学者の特別グループによるレポート」[KeyStudy] で詳細に検討されています。このレポートでは、1995 年に非常に高いセキュリティを実現するための適切なキー長は 75 ～ 90 ビットの範囲であると結論付けられ、暗号化のコストはキー サイズによって大きく変わらないため、90 ビットを推奨しています。この推奨事項を更新するには、ムーアの法則 [MOORE] に 1 年あたり 2/3 ビットを追加するだけです。これは、2004 年に適切なキー長は 81 ～ 96 ビットの範囲であるとの結論に相当します。実際、今日では、AES の 128 ビット (またはそれ以上) のキーや、トリプル DES の有効長が 112 ビットのキーなど、96 ビットを超えるキーの使用がますます一般的になっています。
If chosen or known plain text and the resulting encrypted text are available, a "meet-in-the-middle" attack is possible if the structure of the encryption algorithm allows it. (In a known plain text attack, the adversary knows all or part (possibly some standard header or trailer fields) of the messages being encrypted. In a chosen plain text attack, the adversary can force some chosen plain text to be encrypted, possibly by "leaking" an exciting text that is sent by the adversary over an encrypted channel because the text is so interesting.
選択されたプレーン テキストまたは既知のプレーン テキストと、その結果の暗号化されたテキストが利用できる場合、暗号化アルゴリズムの構造が許せば、「中間者」攻撃が可能になります。(既知のプレーン テキスト攻撃では、攻撃者は暗号化されるメッセージのすべてまたは一部 (標準のヘッダー フィールドまたはトレーラー フィールドの一部) を知っています。選択プレーン テキスト攻撃では、攻撃者は、テキストが非常に興味深いため、暗号化されたチャネルを介して攻撃者が送信した興味深いテキストを「漏洩」するなどして、選択されたプレーン テキストの一部を強制的に暗号化できます。
The following is an oversimplified explanation of the meet-in-the-middle attack: the adversary can half-encrypt the known or chosen plain text with all possible first half-keys, sort the output, and then half-decrypt the encoded text with all the second half-keys. If a match is found, the full key can be assembled from the halves and used to decrypt other parts of the message or other messages. At its best, this type of attack can halve the exponent of the work required by the adversary while adding a very large but roughly constant factor of effort. Thus, if this attack can be mounted, a doubling of the amount of randomness in the very strong key to a minimum of 192 bits (96*2) is required for the year 2004, based on the [KeyStudy] analysis.
以下は、中間者攻撃の非常に簡略化された説明です。攻撃者は、既知のまたは選択されたプレーン テキストを、考えられるすべての最初の半分のキーで半分暗号化し、出力をソートし、エンコードされたテキストをすべての 2 番目の半分のキーで半分復号化できます。一致が見つかった場合、半分から完全なキーを組み立てて、メッセージの他の部分または他のメッセージを復号化するために使用できます。このタイプの攻撃は、最良の場合、攻撃者に必要な作業の指数を半分に減らすことができますが、非常に大きいがほぼ一定の労力要因が追加されます。したがって、この攻撃を仕掛けることができる場合、[KeyStudy] の分析に基づいて、2004 年までに非常に強力なキーのランダム性の量を 2 倍にして、最小で 192 ビット (96*2) にする必要があります。
This amount of randomness is well beyond the limit of that in the inputs recommended by the US DoD for password generation and could require user-typing timing, hardware random number generation, or other sources of randomness.
このランダム性の程度は、米国国防総省がパスワード生成に推奨する入力の限度をはるかに超えており、ユーザーの入力タイミング、ハードウェアによる乱数生成、またはその他のランダム性のソースが必要になる可能性があります。
The meet-in-the-middle attack assumes that the cryptographic algorithm can be decomposed in this way. Hopefully no modern algorithm has this weakness, but there may be cases where we are not sure of that or even of what algorithm a key will be used with. Even if a basic algorithm is not subject to a meet-in-the-middle attack, an attempt to produce a stronger algorithm by applying the basic algorithm twice (or two different algorithms sequentially) with different keys will gain less added security than would be expected. Such a composite algorithm would be subject to a meet-in-the-middle attack.
中間者攻撃は、暗号アルゴリズムをこのように分解できることを前提としています。最新のアルゴリズムにこの弱点がないことを願いますが、その弱点がわからない場合や、キーがどのアルゴリズムで使用されるかさえわからない場合があります。基本アルゴリズムが中間者攻撃の対象にならない場合でも、異なるキーを使用して基本アルゴリズムを 2 回 (または 2 つの異なるアルゴリズムを連続して) 適用してより強力なアルゴリズムを作成しようとすると、期待されるほどセキュリティは強化されません。このような複合アルゴリズムは中間者攻撃の対象になります。
Enormous resources may be required to mount a meet-in-the-middle attack, but they are probably within the range of the national security services of a major nation. Essentially all nations spy on other nations' traffic.
中間的な攻撃をマウントするためには莫大なリソースが必要になるかもしれませんが、おそらく主要な国の国家セキュリティサービスの範囲内です。基本的にすべての国々が他の国の交通をスパイします。
[KeyStudy] also considers the possibilities of special-purpose code-breaking hardware and having an adequate safety margin.
[KeyStudy] では、専用の暗号解読ハードウェアの可能性と十分な安全マージンについても検討しています。
Note that key length calculations such as those above are controversial and depend on various assumptions about the cryptographic algorithms in use. In some cases, a professional with a deep knowledge of algorithm-breaking techniques and of the strength of the algorithm in use could be satisfied with less than half of the 192 bit key size derived above.
上記のようなキーの長さの計算は議論の余地があり、使用されている暗号化アルゴリズムに関するさまざまな仮定に依存することに注意してください。場合によっては、アルゴリズムを破るテクニックと使用されているアルゴリズムの強度に関する深い知識を持つ専門家は、上記で導出された 192 ビットのキー サイズの半分以下で満足できる可能性があります。
For further examples of conservative design principles, see [FERGUSON].
保守的な設計原則のさらなる例については、[FERGUSON]を参照してください。
Generation of unguessable "random" secret quantities for security use is an essential but difficult task.
セキュリティ使用のための不燃性の「ランダムな」秘密数量の生成は不可欠ではなく困難な作業です。
Hardware techniques for producing the needed entropy would be relatively simple. In particular, the volume and quality would not need to be high, and existing computer hardware, such as audio input or disk drives, can be used.
必要なエントロピーを生産するためのハードウェア技術は比較的簡単です。特に、音量と品質は高くする必要はないであろうとし、音声入力またはディスクドライブなどの既存のコンピュータハードウェアを使用することができる。
Widely-available computational techniques can process low-quality random quantities from multiple sources, or a larger quantity of such low-quality input from one source, to produce a smaller quantity of higher-quality keying material. In the absence of hardware sources of randomness, a variety of user and software sources can frequently, with care, be used instead. However, most modern systems already have hardware, such as disk drives or audio input, that could be used to produce high-quality randomness.
広く利用可能な計算技術は、複数のソースからの低品質のランダムな量、あるいは1つのソースからのこのような低品質の入力の低品質の量を処理して、より少ない量の高品質のキーイング材料を生成することができる。ランダム性のハードウェアソースがない場合、さまざまなユーザーおよびソフトウェアの情報源が頻繁に介護される可能性があります。ただし、最近のシステムでは、高品質のランダム性を生み出すために使用できるディスクドライブやオーディオ入力など、すでにハードウェアがあります。
Once a sufficient quantity of high-quality seed key material (a couple of hundred bits) is available, computational techniques are available to produce cryptographically-strong sequences of computationally-unpredictable quantities from this seed material.
十分な量の高品質なシードキー素材（数百ビット）が利用可能になると、計算技術を使用して、このシード素材から計算上予測不可能な量の暗号的に強力なシーケンスを生成できるようになります。
The entirety of this document concerns techniques and recommendations for generating unguessable "random" quantities for use as passwords, cryptographic keys, initialization vectors, sequence numbers, and similar security applications.
この文書全体は、パスワード、暗号鍵、初期化ベクトル、シーケンス番号、および同様のセキュリティアプリケーションとして使用するための不燃性の「ランダムな」数量を生成するための技術および推奨事項に関する。
Special thanks to Paul Hoffman and John Kelsey for their extensive comments and to Peter Gutmann, who has permitted the incorporation of material from his paper "Software Generation of Practically Strong Random Numbers".
Paul HoffmanとJohn Kelseyのおかげで、豊富なコメントやPeter Gutmannのための特別なおかげで、彼の論文からの資料の「実質的に強い乱数のソフトウェア生成」からの材料の組み込みを許可しました。
The following people (in alphabetic order) have contributed substantially to this document:
以下の人々（アルファベット順）は実質的にこの文書に貢献しています。
Steve Bellovin, Daniel Brown, Don Davis, Peter Gutmann, Tony Hansen, Sandy Harris, Paul Hoffman, Scott Hollenback, Russ Housley, Christian Huitema, John Kelsey, Mats Naslund, and Damir Rajnovic.
Steve Bellovin、Daniel Brown、Don Davis、Peter Gutmann、Tony Hansen、Sandy Harris、Paul Hoffman、Scott Harenback、Russ Housle、Christian Huitema、John Kelsey、Mats Naslund、Damir Rajnovic。
The following people (in alphabetic order) contributed to RFC 1750, the predecessor of this document:
以下の人々（アルファベット順）はRFC 1750に貢献し、この文書の前身です。
David M. Balenson, Don T. Davis, Carl Ellison, Marc Horowitz, Christian Huitema, Charlie Kaufman, Steve Kent, Hal Murray, Neil Haller, Richard Pitkin, Tim Redmond, and Doug Tygar.
David M. Balenson、Don T. Davis、Carl Ellison、Marc Horowitz、Christian Huitema、Christian Huitema、Christian Huitema、Steve Kent、Hal Murray、Neil Haller、Richard Pitkin、Tim Redmond、Doug Tygar。
Appendix A: Changes from RFC 1750
付録A：RFC 1750からの変更
1. Additional acknowledgements have been added.
1. 追加の確認応答が追加されました。
2. Insertion of section 5.3 on mixing with S-boxes.
2. Sボックスとの混合時のセクション5.3の挿入
3. Addition of section 3.3 on Ring Oscillator randomness sources.
3. リングオシレータランダム性源についてのセクション3.3の追加。
4. Addition of AES and the members of the SHA series producing more than 160 bits. Use of AES has been emphasized and the use of DES de-emphasized.
4. AESの追加とSHAシリーズのメンバーは160ビット以上を生み出します。AESの使用が強調され、デスの使用が強調されました。
5. Addition of section 6.3 on entropy pool techniques.
5. エントロピープール技術に関するセクション6.3の追加
6. Addition of section 7.2.3 on the pseudo-random number generation techniques given in FIPS 186-2 (with Change Notice 1), 7.2.1 on those given in X9.82, section 7.1.2 on the random number generation techniques of the /dev/random device in Linux and other UNIX systems, and section 7.1.3 on random number generation techniques in the Windows operating system.
6. セクション7.2.3の追加は、FIPS 186-2（変更通知1を付ける）、7.2.1のx9.82で示されている擬似乱数生成技術について、7.1.2項の乱数生成技術についてLinuxおよび他のUNIXシステムの/ dev /ランダムデバイス、およびWindowsオペレーティングシステム内の乱数生成技術に関するセクション7.1.3。
7. Addition of references to the "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security" study published in January 1996 [KeyStudy] and to [RFC1948].
7. 1996年1月[KeyStudy]と[RFC1948]に発行された「対称暗号の最小キー長」の参照の追加。
8. Added caveats to using Diffie-Hellman as a mixing function and, because of those caveats and its computationally intensive nature, recommend against its use.
8. 混合関数としてDiffie-Hellmanを使用する警告を追加し、それらの警告およびその計算的に集約的な性質のために、その使用に推奨する。
9. Addition of references to the X9.82 effort and the [TURBID] and [NASLUND] papers.
9. X9.82の取り組みと[濁り]および[ナスルンド]の論文への参照の追加。
10. Addition of discussion of min-entropy and Renyi entropy and references to the [LUBY] book.
10. 最小エントロピーとレニティエントロピーと[唇]本への参照の議論の追加。
11. Major restructuring, minor wording changes, and a variety of reference updates.
11. 主要なリストラ、マイナーな表現の変更、およびさまざまな参照更新プログラム。
Informative References
参考引用
[AES] "Specification of the Advanced Encryption Standard (AES)", United States of America, US National Institute of Standards and Technology, FIPS 197, November 2001.
[AES]「高度な暗号化規格（AES）」、アメリカ合衆国、米国国立標準技術研究所、FIPS 197、2001年11月。
[ASYMMETRIC] Simmons, G., Ed., "Secure Communications and Asymmetric Cryptosystems", AAAS Selected Symposium 69, ISBN 0-86531-338-5, Westview Press, 1982.
[非対称] Simmons、G.、ED。、「安全な通信と非対称暗号システム」、AAAS選択シンポジウム69、ISBN 0-86531-338-5、WestView Press、1982。
[BBS] Blum, L., Blum, M., and M. Shub, "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, v. 15, n. 2, 1986.
[BBS] Blum、L.、Blum、M.およびM. Shub、「単純な予測不可能な疑似乱数発生器」、コンピューティングに関するSIAMジャーナル、v。15、n。1986年2月2日。
[BRILLINGER] Brillinger, D., "Time Series: Data Analysis and Theory", Holden-Day, 1981.
[Brillinger] Brillinger、D.、「時系列：データ分析と理論」、Holden日、1981年。
[CRC] "C.R.C. Standard Mathematical Tables", Chemical Rubber Publishing Company.
[CRC]「C.R.c.標準数学表」、化学ゴム出版会社。
[DAVIS] Davis, D., Ihaka, R., and P. Fenstermacher, "Cryptographic Randomness from Air Turbulence in Disk Drives", Advances in Cryptology - Crypto '94, Springer-Verlag Lecture Notes in Computer Science #839, 1984.
[Davis] Davis、D.、Ihaka、R.、およびP.フェンシュタルサッハ、「ディスクドライブの空気乱流からの暗号ランダム性」、暗号学 - Crypto '94、Springer-Verlag講義では、コンピュータサイエンスにおけるSpringer-Verlag講義についての進歩＃839,1984。
[DES] "Data Encryption Standard", US National Institute of Standards and Technology, FIPS 46-3, October 1999. Also, "Data Encryption Algorithm", American National Standards Institute, ANSI X3.92-1981. See also FIPS 112, "Password Usage", which includes FORTRAN code for performing DES.
「データ暗号化アルゴリズム」、ANSI X3.92-1981「データ暗号化アルゴリズム」、米国国立標準化学技術研究所、FIPS 46-3。FIPS 112、「パスワード使用量」も参照してください。これには、DESを実行するためのFortranコードが含まれています。
[D-H] Rescorla, E., "Diffie-Hellman Key Agreement Method", RFC 2631, June 1999.
[D-H] RESCORLA、E.、「DIFFIE-HELLMAN鍵協定方法」、RFC 2631、1999年6月。
[DNSSEC1] Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose, "DNS Security Introduction and Requirements", RFC 4033, March 2005.
[DNSSEC1]、R.、Austein、R.、Larson、M.、M。、D.、S. Rose、「DNSセキュリティ紹介および要件」、RFC 4033、2005年3月。
[DNSSEC2] Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose, "Resource Records for the DNS Security Extensions", RFC 4034, March 2005.
[DNSSEC2] Arends、R.、Austein、R.、Larson、M.、Massey、D.、およびS. Rose、「DNSセキュリティ拡張のリソースレコード」、RFC 4034、2005年3月。
[DNSSEC3] Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose, "Protocol Modifications for the DNS Security Extensions", RFC 4035, March 2005.
[DNSSEC3] Arends、R.、Austein、R.、Larson、M.、Massey、D.、およびS. Rose、「DNSセキュリティ拡張のためのプロトコル変更」、RFC 4035、2005年3月。
[DoD] "Password Management Guideline", United States of America, Department of Defense, Computer Security Center, CSC-STD-002-85, April 1885.
[DOD]「パスワード管理ガイドライン」、アメリカ合衆国、国防総省、コンピュータセキュリティセンター、CSC-STD-002-85、1885年4月。
(See also "Password Usage", FIPS 112, which incorporates CSC-STD-002-85 as one of its appendices. FIPS 112 is currently available at: http://www.idl.nist.gov/fipspubs/fip112.htm.)
（「パスワードの使用量」、CSC-STD-002-85をその付録の1つとして組み込んだFIPS 112も参照してください。FIPS 112は現在http://www.idl.nist.gov/fipspubs/fip112.htmで現在入手可能です。。）
[DSS] "Digital Signature Standard (DSS)", US National Institute of Standards and Technology, FIPS 186-2, January 2000.
[DSS]米国国立基準技術研究所、FIPS 186-2、2000年1月、米国国立署名標準（DSS） "。
[DSS_CN1] "Digital Signature Standard Change Notice 1", US National Institute of Standards and Technology, FIPS 186-2 Change Notice 1, 5, October 2001.
[DSS_CN1]「デジタル署名標準変更通知1」、米国国立基準技術研究所、FIPS 186-2の変更1,5、2001年10月5日。
[FERGUSON] Ferguson, N. and B. Schneier, "Practical Cryptography", Wiley Publishing Inc., ISBN 047122894X, April 2003.
[ファーガソン]ファーガソン、N.およびB.Schneier、「実用的な暗号」、Wiley Publishing Inc.、ISBN 047122894X、2003年4月。
[GIFFORD] Gifford, D., "Natural Random Number", MIT/LCS/TM-371, September 1988.
[Gifford] Gifford、D.、「自然乱数」、MIT / LCS / TM-371、1988年9月。
[IEEE_802.11i] "Amendment to Standard for Telecommunications and Information Exchange Between Systems - LAN/MAN Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and physical layer (PHY) specifications: Medium Access Control (MAC) Security Enhancements", IEEE, January 2004.
[IEEE_802.11i] "システム間の電気通信および情報交換のための標準化の修正 - LAN / MAN特有の要件 - 第11報：無線中アクセス制御（MAC）および物理層（PHY）仕様：中アクセス制御（MAC）セキュリティの強化、2004年1月、Ieee。
[IPSEC] Kent, S. and R. Atkinson, "Security Architecture for the Internet Protocol", RFC 2401, November 1998.
[IPSEC]ケント、S.およびR. Atkinson、1998年11月、RFC 2401、RFC 2401。
[Jakobsson] Jakobsson, M., Shriver, E., Hillyer, B., and A. Juels, "A practical secure random bit generator", Proceedings of the Fifth ACM Conference on Computer and Communications Security, 1998.
[Jakobsson] Jakobsson、M.、Shiver、E.、Hillyer、B.、およびA.ジュール、「実用的な安全なランダムビットジェネレータ」、コンピュータ通信セキュリティに関する第5回ACM会議の手続き、1998年。
[KAUFMAN] Kaufman, C., Perlman, R., and M. Speciner, "Network Security: Private Communication in a Public World", Prentis Hall PTR, ISBN 0-13-046019-2, 2nd Edition 2002.
Kaufman、C.、Perlman、R.、M. Speciliner、「ネットワークセキュリティ：公共の世界のプライベートコミュニケーション」、Prentis Hall Ptr、ISBN 0-13-046019-2、第2版2002。
[KeyStudy] Blaze, M., Diffie, W., Riverst, R., Schneier, B. Shimomura, T., Thompson, E., and M. Weiner, "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security: A Report by an Ad Hoc Group of Cryptographers and Computer Scientists", January 1996. Currently available at: http://www.crypto.com/papers/keylength.txt and http://www.securitydocs.com/library/441.
[KeyStudy] Blaze、M.、Diffie、W.、Riverst、R.、Schneier、B. Shimomura、T.、Thompson、E.、M.Weiner、「対称的な繊維のための重要な長さは、適切な商務保障を提供するための主要な長さ：1996年1月の暗号化器とコンピュータ科学者のアドホックグループによる報告書。現在、http：//www.crypto.com/papers/keylength.txtとhttp://www.securitydocs.com/library/441。
[KNUTH] Knuth, D., "The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Chapter 3: Random Numbers, Addison-Wesley Publishing Company, 3rd Edition, November 1997.
[KNUTH]ナイート、D.、「コンピュータプログラミングの技術」、第2巻：セミュニカルアルゴリズム、第3章：乱数、Addison-Wesley出版会社、第3版、1997年11月。
[KRAWCZYK] Krawczyk, H., "How to Predict Congruential Generators", Journal of Algorithms, V. 13, N. 4, December 1992.
[Krawczyk] Krawczyk、H。、「合同生成器の予測方法」、アルゴリズムジャーナル、V.13、N. 4、N. 4、1992年12月。
[LUBY] Luby, M., "Pseudorandomness and Cryptographic Applications", Princeton University Press, ISBN 0691025460, 8 January 1996.
[唇]リビー、M。、「疑似逆らさと暗号アプリケーション」、プリンストン大学プレス、ISBN 0691025460、1996年1月8日。
[MAIL_PEM1] Linn, J., "Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures", RFC 1421, February 1993.
[MAIL_PEM1] LINN、J。、「インターネット電子メールのプライバシー強化：第1部：メッセージ暗号化および認証手順」、RFC 1421、1993年2月。
[MAIL_PEM2] Kent, S., "Privacy Enhancement for Internet Electronic Mail: Part II: Certificate-Based Key Management", RFC 1422, February 1993.
[Mail_PEM2]ケント、S。、「インターネット電子メールのプライバシー強化：その2：証明書ベースの鍵管理」、RFC 1422、1993年2月。
[MAIL_PEM3] Balenson, D., "Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers", RFC 1423, February 1993.
[MAIL_PEM3] Balenson、D.、「インターネット電子メールのプライバシー強化：そのIII：アルゴリズム、モード、識別子」、RFC 1423、1993年2月。
[MAIL_PEM4] Kaliski, B., "Privacy Enhancement for Internet Electronic Mail: Part IV: Key Certification and Related Services", RFC 1424, February 1993.
[MAIL_PEM4]カリスキ、B.、インターネット電子メールの「プライバシー強化：そのIV：KEY認証および関連サービス」RFC 1424、1993年2月。
[MAIL_PGP1] Callas, J., Donnerhacke, L., Finney, H., and R. Thayer, "OpenPGP Message Format", RFC 2440, November 1998.
[mail_pgp1] Callas、J.、Donnerhacke、L.、Finney、H.、およびR. Thayer、 "OpenPGPメッセージフォーマット"、RFC 2440、1998年11月。
[MAIL_PGP2] Elkins, M., Del Torto, D., Levien, R., and T. Roessler, "MIME Security with OpenPGP", RFC 3156, August 2001.
[Mail_PGP2] Elkins、M.、Del Torto、D.、Levien、R.、およびT. Roessler、「OpenPGPとのMIMEセキュリティ」、RFC 3156、2001年8月。
[S/MIME] RFCs 2632 through 2634:
[S / MIME] RFCS 2632から2634：
Ramsdell, B., "S/MIME Version 3 Certificate Handling", RFC 2632, June 1999.
Ramsdell、B.、「S / MIMEバージョン3証明書処理」、RFC 2632、1999年6月。
Ramsdell, B., "S/MIME Version 3 Message Specification", RFC 2633, June 1999.
Ramsdell、B.、「S / MIMEバージョン3メッセージ仕様」、RFC 2633、1999年6月。
Hoffman, P., "Enhanced Security Services for S/MIME", RFC 2634, June 1999.
Hoffman、P.、「S / MIMEの強化されたセキュリティサービス」、RFC 2634、1999年6月。
[MD4] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, April 1992.
[MD4] Rivest、R.、「MD4メッセージ - ダイジェストアルゴリズム」、RFC 1320、1992年4月。
[MD5] Rivest, R., "The MD5 Message-Digest Algorithm ", RFC 1321, April 1992.
[MD5] Rivest、R.、「MD5メッセージダイジェストアルゴリズム」、RFC 1321、1992年4月。
[MODES] "DES Modes of Operation", US National Institute of Standards and Technology, FIPS 81, December 1980. Also: "Data Encryption Algorithm - Modes of Operation", American National Standards Institute, ANSI X3.106-1983.
[MODES]米国国立標準技術研究所、FIPS 81、1980年12月の「データ暗号化アルゴリズム」、ANSI X3.106-1983。
[MOORE] Moore's Law: the exponential increase in the logic density of silicon circuits. Originally formulated by Gordon Moore in 1964 as a doubling every year starting in 1962, in the late 1970s the rate fell to a doubling every 18 months and has remained there through the date of this document. See "The New Hacker's Dictionary", Third Edition, MIT Press, ISBN 0-262-18178-9, Eric S. Raymond, 1996.
[ムーア]ムーアの法則：シリコン回路の論理密度の指数関数的増加1964年に1964年に毎年2倍のGordon Mooreによって策定された1970年代後半に、18ヶ月ごとに倍増し、この文書の日付を通して残っています。「新しいハッカーの辞書」、第3版、MIT PRESS、ISBN 0-262-18178-9、Eric S. Raymond、1996年を参照してください。
[NASLUND] Naslund, M. and A. Russell, "Extraction of Optimally Unbiased Bits from a Biased Source", IEEE Transactions on Information Theory. 46(3), May 2000.
[Naslund] Naslund、M.およびA. Russell、「バイアスソースからの最適な不偏ビットの抽出」、情報理論に関するIEEEトランザクション。2000年5月46（3）。
[ORMAN] Orman, H. and P. Hoffman, "Determining Strengths For Public Keys Used For Exchanging Symmetric Keys", BCP 86, RFC 3766, April 2004.
[Orman] Orman、H.およびP. Hoffman、「対称鍵の交換に使用される公開鍵の長さの決定」、BCP 86、RFC 3766、2004年4月。
[RFC1750] Eastlake 3rd, D., Crocker, S., and J. Schiller, "Randomness Recommendations for Security", RFC 1750, December 1994.
[RFC1750]イーストレイク3RD、D.、Crocker、S.、J.Schiller、「セキュリティのためのランダム性推奨」、RFC 1750、1994年12月。
[RFC1948] Bellovin, S., "Defending Against Sequence Number Attacks", RFC 1948, May 1996.
[RFC1948] Bellovin、S.、「シーケンス番号攻撃に対する防御」、RFC 1948、1996年5月。
[RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, February 1997.
[RFC2104] Krawczyk、H.、Bellare、M.、R. Canetti、「HMAC：メッセージ認証用鍵付きハジング」、RFC 2104、1997年2月。
[RSA_BULL1] "Suggestions for Random Number Generation in Software", RSA Laboratories Bulletin #1, January 1996.
[RSA_BULL1]「ソフトウェアにおける乱数生成の提案」、RSA Laboratories Bulletin＃1、1996年1月1日。
[RSA_BULL13] Silverman, R., "A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths", RSA Laboratories Bulletin #13, April 2000 (revised November 2001).
[RSA_BULL13] Silverman、R.、「対称および非対称キー長のコストベースのセキュリティ分析」、2000年4月13日（2001年11月改訂）。
[SBOX1] Mister, S. and C. Adams, "Practical S-box Design", Selected Areas in Cryptography, 1996.
[SBOX1]ミスター、S、およびC. ADAMS、「実用的なSボックスデザイン」、暗号化された領域、1996年。
[SBOX2] Nyberg, K., "Perfect Non-linear S-boxes", Advances in Cryptography, Eurocrypt '91 Proceedings, Springer-Verland, 1991.
[SBOX2] Nyberg、K。、「完璧な非線形Sボックス」、暗号化、eurocrypt '91議事録、Springer-Verland、1991年。
[SCHNEIER] Schneier, B., "Applied Cryptography: Protocols, Algorithms, and Source Code in C", 2nd Edition, John Wiley & Sons, 1996.
[シュナリエ]シュナリエ、B.、「CRYPTOGRAGHOGRAGHAGRAGHAGLS：C内のプロトコル、アルゴリズム、およびソースコード」、第2版、John Wiley＆Sons、1996年。
[SHANNON] Shannon, C., "The Mathematical Theory of Communication", University of Illinois Press, 1963. Originally from: Bell System Technical Journal, July and October, 1948.
[Shannon] Shannon、C.、「Illinois大学コミュニケーションの数学理論」、1963年：Bell System Technical Journal、1948年7月および10月。
[SHIFT1] Golub, S., "Shift Register Sequences", Aegean Park Press, Revised Edition, 1982.
[Shift1] Golub、S.、「シフトレジスタシーケンス」、Aegean Park Press、Revised Edition、1982年。
[SHIFT2] Barker, W., "Cryptanalysis of Shift-Register Generated Stream Cypher Systems", Aegean Park Press, 1984.
[Shift2] Barker、W、「シフトレジスタ生成ストリームCypherシステムの暗号解読」、Aegean Park Press、1984。
[SHA] "Secure Hash Standard", US National Institute of Science and Technology, FIPS 180-2, 1 August 2002.
【SHA】米国国立科学技術研究所、FIPS 180-2、2002年8月1日。
[SHA_RFC] Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 1 (SHA1)", RFC 3174, September 2001.
[SHA_RFC]イーストレイク3RD、D.およびP. Jones、2001年9月、RFC 3174、「Secure Hash Algorithm 1（SHA1）」
[SSH] Products of the SECSH Working Group, Works in Progress, 2005.
[SSH] SECSHワーキンググループの製品は、2005年、進行中の作品です。
[STERN] Stern, J., "Secret Linear Congruential Generators are not Cryptographically Secure", Proc. IEEE STOC, 1987.
[Stern] Stern、J.、「Secret Linear Contribenty Generatorsは暗号的に安全ではありません」、Proc。IEEE STOC、1987年。
[TLS] Dierks, T. and C. Allen, "The TLS Protocol Version 1.0", RFC 2246, January 1999.
[TLS] Dierks、T.およびC. Allen、 "Thels Protocol Version 1.0"、RFC 2246、1999年1月。
[TURBID] Denker, J., "High Entropy Symbol Generator", <http://www.av8n.com/turbid/paper/turbid.htm>, 2003.
[Turbid] Denker、J.、「高エントロピーシンボルジェネレータ」、<http://www.av8n.com/turbid/paper/turbid.htm>、2003。
[USENET_1] Kantor, B. and P. Lapsley, "Network News Transfer Protocol", RFC 977, February 1986.
[USENET_1] Kantor、B.およびP. Lapsley、「ネットワークニュース転送プロトコル」、RFC 977、1986年2月。
[USENET_2] Barber, S., "Common NNTP Extensions", RFC 2980, October 2000.
[USENET_2] Barber、S.、Common NNTP Extensions "、RFC 2980、2000年10月。
[VON_NEUMANN] Von Nuemann, J., "Various techniques used in connection with random digits", Von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963.
[Von Neumann]フォンノイマン、J.、「ランダムな数字に関連して使用されるさまざまなテクニック」、Von Neumannの収集された作品、Vol。5、Pergamon Press、1963。
[WSC] Howard, M. and D. LeBlanc, "Writing Secure Code, Second Edition", Microsoft Press, ISBN 0735617228, December 2002.
[WSC]ハワード、M.およびD. Leblanc、「セキュアコードの書き込み、第2版」、マイクロソフトプレス、ISBN 0735617228、2002年12月。
[X9.17] "American National Standard for Financial Institution Key Management (Wholesale)", American Bankers Association, 1985.
[X9.17]「金融機関鍵管理（卸売）」、アメリカンバンカー協会、1985年。
[X9.82] "Random Number Generation", American National Standards Institute, ANSI X9F1, Work in Progress. Part 1 - Overview and General Principles. Part 2 - Non-Deterministic Random Bit Generators Part 3 - Deterministic Random Bit Generators
[x9.82]「乱数生成」、アメリカ国立規格Institute、ANSI X9F1、進行中の業務。第1部 - 概要と一般原則。第2部 - 非決定論的ランダムビットジェネレータパート3 - 決定論的ランダムビットジェネレータ
Authors' Addresses
著者の住所
Donald E. Eastlake 3rd Motorola Laboratories 155 Beaver Street Milford, MA 01757 USA
Donald E.イーストレイク3rd Motorola Laboratories 155 Beaver Street Milford、MA 01757 USA
Phone: +1 508-786-7554 (w)
+1 508-634-2066 (h)
EMail: Donald.Eastlake@motorola.com
Jeffrey I. Schiller MIT, Room E40-311 77 Massachusetts Avenue Cambridge, MA 02139-4307 USA
Jeffrey I. Schiller Mit、部屋E40-311 77マサチューセッツ州アベニューケンブリッジ、MA 02139-4307アメリカ
Phone: +1 617-253-0161
EMail: jis@mit.edu
Steve Crocker
スティーブクロッカー
EMail: steve@stevecrocker.com
Full Copyright Statement
完全著作権宣言
Copyright (C) The Internet Society (2005).
著作権（C）インターネット社会（2005）。
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.
この文書は、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.
この文書と本明細書に含まれる情報は、「現状のまま」基準で提供されており、投稿者、または（いずれかの場合）、インターネット社会とインターネットエンジニアリングのタスクフォースがすべての保証を損なう、または本明細書における情報の使用が、特定の目的のためのあらゆる権利または黙示の保証を侵害しないことを含むがこれらに限定されないが、これに限定されない。
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は、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事務局へのIETF事務局と利用可能なライセンスの保証のコピー、またはこの仕様書の実装者や利用者による一般的なライセンスまたは許可を得るための試みの結果を得ることができます。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エディタ機能のための資金は、現在インターネット社会によって提供されています。