Rockfox的密码记录

伪随机数生成器(PRNG)

前言

随机数生成分为伪随机，真随机。真随机是利用现实中的电子元件噪音来生产的。

伪随机数：用真随机数生成种子，用伪随机数生成器生成伪随机数位流

PRNG算法大致分为两类：

• 专用算法：为生成伪随机位流而专门设计。

• 基于现有密码算法的算法：密码算法会随机化输入数据。

  • 对称分组密码、
  • 哈希函数
  • 消息验证码

专用算法

LCG(线性同余生成器)

$x_{n+1}=(aX_n+b)mod m$

m，是模量，a是乘数，b是增量

$X_n=(a^{-1}(X_{n+1}-b))mod m$

$a≡(X_{n+1}−b)⋅X_n^{−1}(modM)$或$a = (X_{n+2} - X_{n+1})(X_{n+1} - X_n)^{-1} (mod m)$

$b = X_{n+1} - aX_n (mod m)$

设$t_n = X_{n+1}- X_n$
$t_n = (aX_n+b) - (aX_{n-1}+b) = at_{n-1}(mod m)$
$t_{n+1}t_{n-1} - t_nt_n = (aat_{n-1}t_{n-1} - at_{n-1}at_{n-1}) = 0 (mod m)$
即$T_n = t_n+1t_{n-1} - t_nt_n$是m的倍数，求Tn , Tn-1最大公因数即为m
$m = gcd((t_{n+1}t_{n-1} - t_nt_n) , (t_nt_{n-2} - t_{n-1}t_{n-1}))$

BBS生成器