0x01 隨機數的使用
- Key distribution and reciprocal authenticaltion schemes.
- Generation of session keys or keys for RSA.
- Generation of a bit stream for symmetric encryption.
0x02 成為隨機數的條件
- 均勻分佈：序列中比特分佈必須均勻，也就是說1和0的出現頻率應該近似相等。
- 獨立性：序列中沒有任何一個單獨序列可以從其他序列推斷出來。
- 不可預測性：必須令攻擊者無法從現有的隨機數推斷出之後可能會生成的隨機數。
0x03 偽隨機數生成器(PRNGs)
偽隨機數生成器會輸入一個成為種子(Seed)的固定值，然後再通過使用可決定性(Deterministic）的演算法來生成一系列的比特。通常，種子由TRNG生成。通常，如圖所示，存在一些反饋路徑，通過該反饋路徑將算法的一些結果反饋為輸入作為附加輸出位。重要的是要注意的是，輸出比特流完全由輸入值或值確定，以便知道算法和種子的對手可以再現整個比特流。
A PRNG takes as input with a fixed value, called the seed, and produces a sequence of output bits using a deterministic algorithm. Quite often, the seed isgenerated by a TRNG. Typically, as shown, there is some feedback path by which some of the results of the algorithm are fed back as input as additional output bits are produced. The important thing to note is that the output bit stream is determined solely by the input value or values, so that an adversary who knows the algorithm and the seed can reproduce the entire bit stream.
An algorithm that is used to produce an open-ended sequence of bits is referred to as a PRNG. A common application for an open-ended sequence of bits is as input to a symmetric stream cipher, as discussed in Section 8.4. Also, see Figure 4.1a.
Pseudorandom function (PRF): A PRF is used to produce a pseudorandom string of bits of some fixed length. Examples are symmetric encryption keys and nonces. Typically, the PRF takes as input a seed plus some context specific values, such as a user ID or an application ID. A number of examples of PRFswill be seen throughout this book, notably in Chapters 17 and 18.
0x04 (TRNGs)
a true random number generator (TRNG) with two forms of pseudorandom number generators. A TRNG takes as input a source that is
effectively random; the source is often referred to as an entropy source. We discuss such sources in Section 8.6. In essence, the entropy source is drawn from the physical environment of the computer and could include things such as keystroke timing patterns, disk electrical activity, mouse movements, and instantaneous values of the system clock. The source, or combination of sources, serve as input to an algorithm that produces random binary output. The TRNG may simply involve conversion ofan analog source to a binary output. The TRNG may involve additional processing to overcome any bias in the source.
0x05 True Random Number Generator
- Non-deterministic source, physical environment
- Detect ionizing radiation events, leaky capacitors,thermal noise from resistors or audio inputs
- Mouse/keyboard activity, I/O operations, interrupts
- Inconvenient, small number of values
Pseudo Random Number Generator
- Deterministic algorithms to calculate numbers in “relatively random” sequence
- Seed is algorithm input
- Produces continuous stream of random bits
- Pseudo Random Function
- Same as PRNG but produces string of bits of some
Requirements of PRNG
Hard to determine pseudo-random stream if don’t know seed(but know algorithm)
- Randomness
Test for uniformity, scalability, consistency
Examples: Frequency, runs, compressability - Unpredictability
-Forward and backward unpredictability
-Seed must be secure(Use TRNG to generate seed)
Linear Congruential Generator
Parameters:
m, the modulus, m > 0
a, the multiplier, 0 < a < m
c, the increment, 0 ≤ c < m
X0, the seed, 0 ≤ X0 < m
Generate sequence of pseudo-random numbers, {Xn}:
Xn+1 = (aXn + c) mod m
Choice of a, c and m is important:
m should be large, prime, e.g. 231 − 1
If c=0, few good values of a, e.g. 75 = 16807
If attacker knows parameters and one number, can easily
determine subsequent numbers
Blum Blum Shub Generator
Parameters:
p, q: large prime numbers such that p ≡ q ≡ 3 (mod 4)
n = p × q
s, random number relatively prime to n
Generate sequence of bits, Bi
:
X0 = s
2 mod n
for i = 1 → ∞
Xi = (Xi−1)
2 mod n
Bi = Xi mod 2
Cryptographically secure pseudo-random bit generator
Example Operation of BBS Generator
n = 192649 = 383 × 503, s = 101355
PRNG Mechanisms Based on Block Ciphers
Use symmetric block ciphers (e.g. AES, DES) to produce pseudo-random bits
Seed is encryption key, K, and value V (which is updated)
ANSI X9.17 PRNG
Cryptographically secure PRNG using Triple DES
Parameters:
64-bit date/time representation, DTi
64-bit seed value, Vi
Pair of 56-bit DES keys, K1 and K2
Operation:
Uses Triple DES three times
(see next slide)
Output:
64-bit pseudo-random number, Ri
64-bit seed value, Vi+1
Stream Ciphers
Encrypt one byte at a time by XOR with pseudo-random byte
Output of generator is called keystream
Design Criteria for Stream Ciphers
Important Considerations
Encryption sequence should have large period
Keystream should approximate true random number
stream
Key must withstand brute force attacks
Comparison to Block Ciphers
Stream ciphers often simpler to implement, faster
Block ciphers can re-use keys
RC4
Designed by Ron Rivest in 1987
Used in secure web browsing and wireless LANs
Very simple and efficient implementation
Can use variable size key: 8 to 2048 bits
Several theoretical limitations of RC4
No known attacks if use 128-bit key and discard initial values of stream
RC4 is used in WEP (shown to be weak security for wireless LANs)—problem with how keys are used, not RC4 algorithm
RC4 Algorithm
Parameters and Variables
Variable length key, K, from 1 to 256 Bytes
State vector, S, 256 Bytes
Temporary vector, T, 256 Bytes
A byte from keystream, k, generated from S
Steps
- Initialise S to values 0 to 255; initialise T with
repeating values of key, K - Use T to create initial permutation of S
- Permutate S and generate keystream, k from S
- Encrypt a byte of plaintext, p, by XOR with k
Initial State of S and T
for i = 0 to 255 do
S[i] = i;
T[i] = K[i mod keylen];
Initial Permutation of S
j = 0;
for i = 0 to 255 do
j = (j + S[i] + T[i]) mod 256;
Swap (S[i], S[j]);