---
tags : '資安'
---

# ch7 Pseudorandom Number Generation and Stream Ciphers

隨機亂數產生

### Randomness 隨機性
1. 0跟1出現頻率要相同
2. 獨立性:每個位元或數字不能是有相關的

### Unpredictability(不可預測性)
無法由前一個推到其他個

### Test of Randomness
目前沒有任何方法驗證是不是隨機變數
* Uniformity
* Scalability
* Consistency

### Pseudorandom Numbers
由於大部分產生亂數的方法為演算法，只要有演算法，就不可能達到全部獨立

### True Random Number Generator (TRNG)
由於input是隨機取材 EX:滑鼠移動距離，風聲等等 ，將這些輸入化成binary輸出，就等於亂數

### Pseudorandom Number Generator (PRNG)

用演算法來產生亂數→由於事由確定的演算法來計算，因此只要知道種子(seed)和演算法就能重現整個stream

有兩種形式：
Pseudorandom Number Generator (PRNG)
Pseudorandom function(PRF)

同樣的演算法可以用於兩種形式上
兩種只在於產生的位數不同，PRF是用來產生固定長度的隨機值

### PRNG Requirements

1. Randomness 隨機性
2. Unpredictability 不可預測性
3. Characteristics of the seed 種子特徵

#### Randomness
沒有任何**單一**測試能決定隨機性，但只要能通過多個測試就承認有隨機性
NIST SP 800-22 規定了應該要能在測試中有三種屬性

Uniformity (均勻度) → 產出的每個數字或字母分布頻率應相同
Scalability (可擴展性)→ 如果一個序列為隨機，那從中挑選出來的子序列也要為隨機
Consistency (一致性) → generator的行為必須在不同的初始值都保持一致

##### Randomness Test
Frequency test → 測試出現的 1 和 0 個數是否一樣 Uniformity (均勻度)
Runs test(趨勢測試) → Scalability (可擴展性)

Maurer’s universal statistical test → 測試訊息能否壓縮，可壓縮的訊息就會被視為非隨機 Consistency (一致性)

#### Unpredictability
必須符合兩種形式的不可預測性：
Forward unpredictability:
如果初始值(seed)未知，則任何一個數都不能從前一個數值推出來

Backward unpredictability：
不能從數值推回seed，且生產出的值跟seed不能有關連性

而用Randomness Test同時也能證明該數列是否擁有不可預測性(畢竟都隨機了怎麼還能預測)

### Seed Requirements
作為輸入的種子一定要夠安全且不可預測，所以通常由TRNG產生

## Algorithm Design
演算法可分為兩種:
Purpose-built algorithms：
為了製造出隨機變數而發明的演算法

Algorithms based on existing cryptographic algorithms:
原本就有其他用途的演算法但剛好能有隨機變數的特性

有三種演算法最常被用來當作PRNG:
• Symmetric block ciphers
• Asymmetric ciphers
• Hash functions and message authentication codes

### PRNG - Linear Congruential Generators(線性同餘法)
在線性同餘法裡，選擇一個很大的整數m(約2^31^)，然後依下面的遞回方程式，創造出在0至m-1間之一連串整數群。

X~0~ :種子值(seed)
a :固定乘數(constant multiplier)
c :增加量(increment)
m :模數(modulus)
X~n+1~ = (aX~n~ + c) mod m

每個產生出來的值會被當作下一個種子，因此會產生出一個週期

m=(2^31^)-1=2,147,483,647本身剛好就是一個質數而且為了符合在32位元環境下執行，所以這個數為最大的質數
而a也被驗證過a=16807與a=630,360,016是最廣泛使用，強度也最強的

### PRNG - Blum Blum Shub Generator

也被視為cryptographically secure pseudorandom bit generator (CSPRBG)

選兩個夠大的質數p，q
使得p ≡ q ≡ r mod m
令n=p*q，指定一數s跟n互質

### Block cipher of PRNG
通常會用到CTR與OFB模式

圖中的Key跟V就是seed → 每產出一個block就會換新的值

#### ANSI X9.17 PRNG
Cryptographic strength:
– 112 bits key (i.e. K1, K2)
– Three EDE encryptions (total of 9 DES encryptions)
– Two inputs
• Date and time
• A seed from other generator
– i.e. initial Vi, then updated during the generation process

### NIST CTR_DRBG
是一種用CTR模式做的PRNG，用3DES或AES來加密
**Initial function**
Seed：將K和V做運算混合

### Stream Ciphers

優點：比block cipher快且通常使用較少code來完成
缺點：每次加密要用不同的Key

## RC4
* 有多種key size可以使用(1~256byte)
* 週期超過10^100^
* 複雜度低

Key 用來初始化 vector S → S[0], S[1], …, S[255]
S包含了0~255 (8 bits)

<!-- [ch8 進階數論](https://hackmd.io/@Ired/ISch8N0t3) -->