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).




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
1. Introduction and Overview
1. 概要と概要

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.


2. General Requirements
2. 一般要件

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.


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].


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].


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:


        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.)

ここで、1から可能な秘密値の数、およびPサブ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ビットの情報が存在し、承認の数量を推測する前に、平均、値の半分、または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ビットシードを播種された固定擬似乱数発生器を使用して導出された場合、敵対者は256のキーを通して(すべての可能なシードで疑似乱数ジェネレータを実行することによって)256のキーを検索する必要があります。^ 128キーは、まずケースのように見えます。これらの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の残りの2 ^ 128 - 1の値から半分の半分半分を生成するとします。時間。上記のシャノン式は、これらの重要な値の1つに64ビットの情報があると言いますが、単に値ゼロを試すことによって、敵対者は、ランダムな半分になることを示しています。したがって、暗号化の目的のために、そのまま定義されたMin-Entropyなどの他の措置を調べることも有用です。

Min-entropy = - log ( maximum ( p ) ) i

Min-Entropy = - ログ(最大(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.


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 Entropyと呼ばれるエントロピーの連続スペクトルは、パラメータRによって指定されています。ここで、R = 1はシャノンエントロピーであり、R =無限大は最小エントロピーである。R =ゼロのとき、それはただログ(n)です。ここで、nはゼロ以外の確率の数です。Renyi EntropyはRの非増加機能です。そのため、最小エントロピーは常にエントロピーの最も控えめな尺度です。

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.


3. Entropy Sources
3. エントロピーソース

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.


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.


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を参照してください。

3.1. Volume Required
3.1. 必要量

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.


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.


3.2. Existing Hardware Can Be Used For Randomness
3.2. 既存のハードウェアはランダム性に使用できます

As described below, many computers come with hardware that can, with care, be used to generate truly random quantities.


3.2.1. Using Existing Sound/Video Input
3.2.1. 既存のサウンド/ビデオ入力を使用してください

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 /オーディオデバイスから読み取ることができます。そのようなデータは本質的にランダムなノイズですが、ハードウェアの障害の場合には何度もチェックすることなく信頼されるべきではなく、歪んでいなければならないでしょう。

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:


        cat /dev/audio | compress - >random-bits-file

A detailed examination of this type of randomness source appears in [TURBID].


3.2.2. Using Existing Disk Drives
3.2.2. 既存のディスクドライブを使用してください

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.


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.


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.


3.3. Ring Oscillator Sources
3.3. リングオシレータソース

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.


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].


             |\     |\                |\
         +-->| >0-->| >0-- 19 total --| >0--+-------+
         |   |/     |/                |/    |       |
         |                                  |       |
         +----------------------------------+       V
             |\     |\                |\         |     | output
         +-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------>
         |   |/     |/                |/    |    |     |
         |                                  |    +-----+
         +----------------------------------+      ^ ^
                                                   | |
             |\     |\                |\           | |
         +-->| >0-->| >0-- 29 total --| >0--+------+ |
         |   |/     |/                |/    |        |
         |                                  |        |
         +----------------------------------+        |
             Other randomness, if available ---------+
3.4. Problems with Clocks and Serial Numbers
3.4. 時計とシリアル番号に関する問題

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.


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.


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.


3.5. Timing and Value of External Events
3.5. 外部イベントのタイミングと値

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.


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.


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.


3.6. Non-hardware Sources of Randomness
3.6. ランダム性の非ハードウェアソース

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.


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.


4. De-skewing
4. 汚れた

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.


4.1. Using Stream Parity to De-Skew
4.1. ストリームパリティを使用して解読されます

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.


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.

ゼロ対ゼロの比率が(0.5 e)〜(0.5°E)であると仮定すると、Eは0から0.5の間であり、分布の「偏心」の尺度であるとします。Nビットサンプルのパリティ関数の分布を考慮してください。パリティが1またはゼロになることのそれぞれの確率は、(PQ)^ nの二項展開における奇数または偶数の用語の合計であり、ここで、p = 0.5e、1、Q = 0.5 - e、ゼロの確率。

These sums can be computed easily as


                         N            N
        1/2 * ( ( p + q )  + ( p - q )  )

and N N 1/2 * ( ( p + q ) - ( p - q ) ).

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.)


   Since p + q = 1 and p - q = 2E, these expressions reduce to

N 1/2 * [1 + (2E) ]

N 1/2 * [1(2E)]

and N 1/2 * [1 - (2E) ].

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


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.


                | 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.


4.2. Using Transition Mappings to De-Skew
4.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 [Von_neumann]による他の技術は、重ならないペアのシーケンスとしてビットストリームを調べることである。次いで、0または11対を廃棄し、0を0および10と解釈することができ、0.5 eの確率は0.5 eであり、0の確率は0.5°であると仮定します。ここで、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.


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.


4.3. Using FFT to De-Skew
4.3. FFTを使って汚れた

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.


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].


4.4. Using Compression to De-Skew
4.4. 圧縮を使用して歪み

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.


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. Mixing
5. 混合

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.


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].


5.1. A Trivial Mixing Function
5.1. 些細な混合機能

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.


                |  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:


E = 2 * E * E output input 1 input 2

E = 2 * E * E出力入力1入力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   |  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.


5.2. Stronger Mixing Functions
5.2. より強い混合機能

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.


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-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.


5.3. Using S-Boxes for Mixing
5.3. ミキシングのためのSボックスを使用する

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.


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-boxes and various repeated applications or cascades of such boxes can be used for mixing [SBOX1, SBOX2].


5.4. Diffie-Hellman as a Mixing Function
5.4. ミキシング関数としてのDiffie-Hellman

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].


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.


5.5. Using a Mixing Function to Stretch Random Bits
5.5. ランダムビットをストレッチするためのミキシング関数を使用する

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.

混合関数がその入力よりも同じまたは少ない出力ビットを生成する必要はないが、ミキシングビットは入力に存在するランダムな予測不能性の量を「ストレッチ」することはできない。したがって、それぞれ4つの入力には4つの入力(4,096等が等しく考えられる値など)が各入力で、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つのランダムビットを複数に "String"する方法はありません。たとえば、ランダムビットが0と0で混合されている場合、これは2ビットのシーケンスを生成しますが、01または10のいずれかになります。オリジナルのランダム性の。

5.6. Other Factors in Choosing a Mixing Function
5.6. 混合機能を選択する際のその他の要因

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は、堅牢で一般、そして国際的なプロセスによって選択されました。それとSha *は、ほとんど秘密のままである基準に基づいて、米国国家安全保障庁(NSA)が救済されています。これは多くの投機と疑いの原因であるが、何年も経過すると、IBMに由来するその設計への修正へのNSAの関与は主にそれを強化することを示した。DESで見つかる隠されたまたは特別な弱さの発表はありませんでした。SHAアルゴリズムを生成するためのMD4へのNSA修正は、おそらく公衆暗号化コミュニティにおいてまだ知られていない脅威に対しても同様に強化する可能性が高い。

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アルゴリズムを認識していません。もちろん、著者らは、実装または使用または発行された他の関連特許に関する認識または特許であるか、または特許の本質的な特許であるかもしれません。

6. Pseudo-random Number Generators
6. 擬似乱数ジェネレータ

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.


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. Some Bad Ideas
6.1. 悪いアイデア

The subsections below describe a number of ideas that might seem reasonable but that lead to insecure pseudo-random number generation.


6.1.1. The Fallacy of Complex Manipulation
6.1.1. 複雑な操作の誤謬

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.


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.


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!


6.1.2. The Fallacy of Selection from a Large Database
6.1.2. 大規模データベースからの選択の誤謬

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記録またはその他の大規模な公開データベース上のデータからのシーケンスの選択に適用されます。敵対者が同じデータベースにアクセスできる場合は、この「大量のデータからの選択」ステップが少し購入します。しかしながら、敵対的マルチユーザシステム上のシステムバッファのような逆境がないデータから選択が行われた場合、それは助けのものであり得る。

6.1.3. Traditional Pseudo-random Sequences
6.1.3. 伝統的な疑似ランダムシーケンス

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.


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.


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が番号が付けられた値から数字が付けられた値から計算されます。

        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 *]。そのような発電機では、選択された固定タップからレジスタへのビットの排他的論理和または(キャリーなし)ビットの一端にビットが導入される。たとえば、次の点を考慮してください。

      +----+     +----+     +----+                      +----+
      | 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.


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].


6.2. Cryptographically Strong Sequences
6.2. 暗号的に強いシーケンス

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.


(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.)


6.2.1. OFB and CTR Sequences
6.2.1. OFBおよびCTRシーケンス

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.


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].


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.


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.


6.2.2. The Blum Blum Shub Sequence Generator
6.2.2. Blum Blum Shubシーケンス発電機

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.

現在、最も強力な強さの証明を持つ発電機は、その発明者らのINSTROVERS [BBS]に命名されたBlum Blum Shub Generatorと呼ばれています。それはまた非常に単純でありそして二次残基に基づいている。その唯一の欠点は、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:


         s    =  ( x  )(Mod n)
         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:


log ( log ( s ) ) 2 2 i

ログ(ログ)2 2

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.


An interesting characteristic of this generator is that any of the s values can be directly calculated. In particular,


               ( (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.


6.3. Entropy Pool Techniques
6.3. エントロピープールテクニック

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.


             +--------+    +------+    +---------+
         --->| 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.


7. Randomness Generation Examples and Standards
7. ランダム性生成の例と標準

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. Complete Randomness Generators
7.1. 完全なランダム性発電機

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乱数ジェネレータが記述されています。

7.1.1. US DoD Recommendations for Password Generation
7.1.1. パスワード生成に関する米国のDODの推奨事項

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:


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.


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.


7.1.2. The /dev/random Device
7.1.2. / dev /ランダムデバイス

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.


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.)


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ランダムデバイスはTheoDore TS'oによって書かれました。PGP 2.xおよびPGP 3.0(AKA PGP 5.0)の乱数発生器に緩く並べて基づいていました。)

7.1.3. Windows CryptGenRandom
7.1.3. Windows CryptGenrandom

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.


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.


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].


7.2. Generators Assuming a Source of Entropy
7.2. エントロピー源を想定している発電機

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.


7.2.1. X9.82 Pseudo-Random Number Generation
7.2.1. x9.82擬似乱数の世代

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ビットのソースが必要とされなければならない。このジェネレータのインスタンス化を通して同じハッシュ関数を使用する必要があります。 Notation 表記

In the following sections, the notation give below is used:


hash_length is the output size of the underlying hash function in use.


input_entropy is the input bit string that provides entropy to the generator.


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.


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.


"|" represents concatenation.

"" Initializing the Generator 発電機の初期化

Set V to all zero bytes, except the low-order bit of each byte is set to one.


Set K to all zero bytes, then set:


K = HMAC ( K, V | 0x00 | input_entropy )


V = HMAC ( K, V )

V = HMAC(k、v)

K = HMAC ( K, V | 0x01 | input_entropy )


V = HMAC ( K, V )

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の長さは整数バイト数になります。 Generating Random Bits ランダムビットの生成

When output is called for, simply set:


V = HMAC ( K, V )

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 = 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が要求されたランダムビット数以上のようにすぐに停止します。一時的な先頭のビットの要求された数を使用してください。アルゴリズムの定義は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:


K = HMAC ( K, V | 0x00 ) V = HMAC ( K, V )


7.2.2. X9.17 Key Generation
7.2.2. X9.17キーの生成

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 is the initial 64 bit seed. 0


g is the sequence of generated 64-bit key quantities n


k is a random key reserved for generating this key sequence.


t is the time at which a key is generated, to as fine a resolution as is available (up to 64 bits).


DES ( K, Q ) is the DES encryption of quantity Q with key K.




g = DES ( k, DES ( k, t ) XOR s ) n n

g = des(k、des(k、t)xor s)n n

s = DES ( k, DES ( k, t ) XOR g ) n+1 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の計算に使用する必要があります。

7.2.3. DSS Pseudo-random Number Generation
7.2.3. DSS疑似乱数生成

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

T = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0

XKEY = initial seed 0

XKEY =初期シード0.

For j = 0 to ...

j = 0から...

             XVAL = ( XKEY  + optional user input ) (Mod 2^512)

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.


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*].

1つ目はSHA-1に基づいており、5分の1つの引数に、5分の1の引数に、5つのリンク変数をSHA-1仕様に設定し、5つのリンク変数を設定することによって機能します。その後、NIST SHA-1仕様のセクション7のステップ(a)から(e)は、512ビットのデータブロックであるかのように2番目の引数を介して実行されます。これらのステップの後のリンク変数の値は、次に連結されてG [SHA *]の出力を生成する。

As an alternative method, NIST also defined an alternate G function based on multiple applications of the DES encryption function [DSS].


8. Examples of Randomness Required
8. ランダム性の例が必要です

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.


In addition, [ORMAN] and [RSA_BULL13] provide information on the public key lengths that should be used for exchanging symmetric keys.


8.1. Password Generation
8.1. パスワードの生成

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.


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千千千台の機会を持つことは、少なくとも500,000,000のパスワード、または約2 ^ 29の宇宙を意味します。したがって、29ビットのランダム性が必要です。これはおそらく、それぞれ5ビットのランダム性を超える4つの入力を持つ8つの入力を持つので、パスワード生成のための米国のDOD推奨された入力を使用することによって達成されます(セクション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ビットが追加されます。したがって、上記のシナリオの下でパスワードの百万のチャンスを推測することは、1,000ワードリスト、または8文字/桁の4ワードの句である39ビットのランダム性とパスワードを必要とするでしょう。1 in-10 ^ 9のチャンスに移動するには、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.


8.2. A Very High Security Cryptographic Key
8.2. 非常に高いセキュリティ暗号鍵

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.


8.2.1. Effort per Key Trial
8.2.1. キートライアルあたりの努力

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.)


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.

敵対者が高度に並列プロセッサまたは大規模なワークステーションネットワークを指揮することができる場合、毎秒10 ^ 11サイクルは今日の最小の仮定です。数年前に楽しみにして、少なくとも一桁の改善があるはずです。したがって、10 ^ 10のキーを毎秒1秒あたり、3.6 * 10 ^ 12、週あたり3.6 * 10 ^ 12、または1ヶ月あたり2.4 * 10 ^ 15であると仮定することは合理的です。これは、鍵で最低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.


8.2.2. Meet-in-the-Middle Attacks
8.2.2. ミドル攻撃

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.


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.


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.


8.2.3. Other Considerations
8.2.3. その他の考慮事項

[KeyStudy] also considers the possibilities of special-purpose code-breaking hardware and having an adequate safety margin.


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].


9. Conclusion
9. 結論

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.


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.


10. Security Considerations
10. セキュリティに関する考慮事項

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.


11. Acknowledgements
11. 謝辞

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.


[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.


(See also "Password Usage", FIPS 112, which incorporates CSC-STD-002-85 as one of its appendices. FIPS 112 is currently available at:

(「パスワードの使用量」、CSC-STD-002-85をその付録の1つとして組み込んだFIPS 112も参照してください。FIPS 112は現在で現在入手可能です。。)

[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: and

[KeyStudy] Blaze、M.、Diffie、W.、Riverst、R.、Schneier、B. Shimomura、T.、Thompson、E.、M.Weiner、「対称的な繊維のための重要な長さは、適切な商務保障を提供するための主要な長さ:1996年1月の暗号化器とコンピュータ科学者のアドホックグループによる報告書。現在、と。

[KNUTH] Knuth, D., "The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Chapter 3: Random Numbers, Addison-Wesley Publishing Company, 3rd Edition, November 1997.


[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", <>, 2003.

[Turbid] Denker、J.、「高エントロピーシンボルジェネレータ」、<>、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.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)

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

Steve Crocker



Full Copyright Statement


Copyright (C) The Internet Society (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に含まれている権利、ライセンス、制限の対象となり、その中に述べた場合を除き、著者らはすべての権利を保持しています。



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


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




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