密码学备忘录-伪随机数

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 最好的来源是现实世界中的自然随机性