密码学备忘录-伪随机数

1. pseudorandom number generation

1.1. 随机数的作用

• 防止重放攻击
• keystream for a one-time pad（一次性密码的密钥流）
• public key generation 生成公钥

1.2. 伪随机数和随机数区别

• deterministic algorithm
• seed

1.3. 种类

1.3.1. 1. Linear Congruential Generator 线性同余生成器

• $x_{n+1}=(aX_n+c)\bmod{m}$

特点

• 存在周期
• 32bit计算

1.3.2. 2. Blum Blum Shub (B.B.S.) 算法

• $x_0=seed^2\bmod{n}$
• $LOOP x_i == x_{i-i}^2\bmod{n}$
• $b_i=x_i\bmod{2}$
  • p,q is prime
  • p,q mod 3 == 4

特点

• based on public key algorithms
• 安全性基于分解n的困难性(同rsa)

1.3.3. 3. Using Block Ciphers as PRNG 运用分组（对称）加密算法作为生成器

• CRT
• OFB
• CBC-MAC

e.g. ANSI X9.17 PRGN

• date and time(DTi)
• uses 2-key (K1,K2) triple DES
• feeds back between rounds (Vi)

1.3.4. 4. 运用非对称加密算法作为生成器

• 总体上慢，因此只应用于生成短伪随机数
• PRNG based on RSA

• PRNG based on ECC

1.3.5. 5. 运用哈希和MAC

• PRNG using a Hash Function

• PRNG using a MAC

2. Stream Ciphers

• 是一种对称加密算法
  • 加密和解密双方使用相同伪随机加密数据流（pseudo-random stream）作为密钥
• 该算法解决了对称加密完善保密性（perfect secrecy）的实际操作困难
  • 具有该性质的密文不应该透露任何明文的信息
  • 完善保密性要求密钥长度不短于明文长度，故而实际操作存在困难，改由较短数据流通过特定算法得到密钥流

2.1. 攻击

一种严重的错误即反复使用同一密码本对不同明文进行加密。攻击者可利用这种方式对密文进行解密。用p表示明文，C表示密文，k表示种子，PRG表示密钥流生成算法，则：

• C1 = p1 xor PRG (k)
• C2 = p2 xor PRG (k)
  攻击者监听到此段消息（包含两段相同密钥流加密的密文）后，即可利用：
• C1 xor C2得到p1 xor p2
  足量的冗余（此处表示p1，p2）则可破解明文。

2.2. RC4

• Key-scheduling algorithm (KSA)
  • 临时向量 T
  • 状态向量 S
  • 初始密钥 K
    • 注意和最终生成的密钥流t区别开

• RC4 Encryption

• 注意直到最后一步$C_i$之前，都只是在生成伪随机序列(密钥流)
  • S的每个元素每256次迭代至少与另一个元素互换一次
  • PRGA(Pseudo-random generation algorithm)
• 最后一步异或才算是C=M+K

2.2.1. 优点

• result is very non-linear

2.2.2. 问题

• these days, RC4 is known to be biased (unequal numbers of 0s and 1s in the keystream)
• 永远不应该重复使用密码本

3. true random numbers

• best source is natural randomness in real world 最好的来源是现实世界中的自然随机性