LCG 线性同余生成器

N1Key2023/6/2大约 2 分钟LCG流密码

概念

LCG既属于伪随机数发生器，也属于流密码。参考文章： https://goodapple.top/archives/404

递推公式

S_{n + 1} = a S_{n} + b (m o d m)

参数：

S 是伪随机序列；
$m ， 0 < m$ 表示模量；
$a ， 0 < a < m$ 表示乘数；
$b ， 0 \leq b < m$ 表示增量；
$S_{0} ， 0 \leq S_{0} < m$ 表示初始值。

阶

$a$ 与 $n$ 互素，使得

a^{x} \equiv 1 m o d n

成立的最小正整数 x 称为a模n的阶，记为 $o r d n (a)$ 。

原根

如果有

o r d n (a) = ϕ (n)

称 a 为模 n 的原根

若 gcd(a,n)=1，则周期 T=ordm(a)，所以选取系数时应尽量使得 a 为模 n 的原根，以此尽量延长 LCG 周期。

常见推导公式

公式一

此公式用于从 $S_{n + 1}$ 反推出 $S_{n}$ ，公式如下

S_{n} = (a^{- 1} (S_{n + 1} - b)) m o d m

推导过程如下

S_{n + 1} - b \equiv a S_{n} (m o d m)

进而

S_{n} = (a^{- 1} (S_{n + 1} - b)) m o d m

公式二

此公式用于求 a，公式如下

a = ((S_{n + 2} - S_{n + 1}) (S_{n + 1} - S_{n})^{- 1}) m o d m

推导过程如下

S_{n + 2} \equiv a S_{n + 1} + b m o d m

S_{n + 1} \equiv a S_{n} + b m o d m

两式相减

(S_{n + 2} - S_{n + 1}) \equiv a (S_{n + 1} - S_{n}) m o d m

进而得到

a = ((S_{n + 2} - S_{n + 1}) (S_{n + 1} - S_{n})^{- 1}) m o d m

公式三

此公式用于求b，公式如下

b = (S_{n + 1} - a S_{n}) m o d m

公式四

此公式用于求m，公式如下

令 t_{n} = S_{n + 1} - S_{n} ， 则 m = g c d ((t_{n + 1} t_{n - 1} - t_{n}^{2}), (t_{n} t_{n - 2} - t_{n - 1}^{2}))

推导过程如下：

令 $t_{n} = S_{n + 1} - S_{n}$ ，有

t_{n} \equiv (a S_{n} + b) - (a S_{n - 1} + b) \equiv a t_{n - 1} m o d m

t_{n + 1} t_{n - 1} - t_{n}^{2} \equiv (a a t_{n - 1} t_{n - 1} - a t_{n - 1} a t_{n - 1}) \equiv 0 m o d m

即 $T_{n} = t_{n + 1} t_{n - 1} - t_{n}^{2}$ 为 m 的倍数，求 $T_{n} 、 T_{n - 1}$ 最大公因数即为 m，所以

m = g c d ((t_{n + 1} t_{n - 1} - t_{n}^{2}), (t_{n} t_{n - 2} - t_{n - 1}^{2}))

实现程序

from Crypto.Util.number import long_to_bytes  
from sympy import *  
from gmpy2 import *  
  
  
# 还原初始种子  
def restore_seed_S0(states, modulus, multiplier, increment):  
    seed = (states[0] - increment) * invert(multiplier, modulus) % modulus  
    return seed, modulus, multiplier, increment  
  
  
# 计算增量  
def crack_unknown_increment(states, modulus, multiplier):  
    increment = (states[1] - states[0] * multiplier) % modulus  
    return restore_seed_S0(states, modulus, multiplier, increment)  
  
  
# 计算乘数  
def crack_unknown_multiplier(states, modulus):  
    multiplier = (states[2] - states[1]) * invert(states[1] - states[0], modulus) % modulus  
    return crack_unknown_increment(states, modulus, multiplier)  
  
  
# 计算模数  
def crack_unknown_modulus(S):  
    t4 = S[5] - S[4]  
    t3 = S[4] - S[3]  
    t2 = S[3] - S[2]  
    t1 = S[2] - S[1]  
    modulus = gcd(t4 * t2 - t3 ** 2, t3 * t1 - t2 ** 2)  
    return crack_unknown_multiplier(states, modulus)  
  
  
states = [6473702802409947663, 7762911616316678361, 8778349545254661087, 2182563361653435704, 1383751637647655272,  
          4512576578889812021, 4322633144718249958, 3959701111371594748, 7676663421477866678, 5009230933212388616,  
          3780469426700690705]  
seed, modulus, multiplier, increment = crack_unknown_modulus(states)  
print("模数n =", modulus)  
print("乘数a =", multiplier)  
print("增量b =", increment)  
print("初始S0 =", seed)