LCG

LCG

线性同余（LCG）是产生伪随机数的方法。

基本形式：

\[ X_{n+1}=(aX_n+b)\;mod\;m \]

基本公式

公式一

求递归数组元素

\[X_n=a^{-1}(X_{n+1}-b)\;mod\;m\]

公式二

求参数 a 利用两个递归式消去 b 得到 a

\[a=(X_{n+2}-X_{n+1})(X_{n+1}-X_n)^{-1}\]

公式三

求参数 b \[b=(X_{n+1}-aX_{n})\;mod\;m\]

公式四

求参数 m

\[t_n=X_{n+1}-X_n\] \[t_n=(aX_n+b)-(aX_{n-1}+b)\;mod\;m\] \[t_{n+1}t_{n-1}-t_nt_n=0\;mod\;m\] \[T_n=t_{n+1}t_{n-1}-t_nt_n是 m 的倍数\] \[m=gcd(T_n,T_{n-1})\]

相关求解代码

from Crypto.Util.number import *
from functools import *


def crack_unknown_increment(states, modulus, multiplier):  # 求增量

    increment = (states[1] - states[0]*multiplier) % modulus

    return modulus, multiplier, increment


def crack_unknown_multiplier(states, modulus):  # 求乘数

    multiplier = (states[2] - states[1]) * \
        inverse(states[1] - states[0], modulus) % modulus

    return crack_unknown_increment(states, modulus, multiplier)


def crack_unknown_modulus(states):  # 求模数

    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]

    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]

    modulus = abs(reduce(GCD, zeroes))

    return crack_unknown_multiplier(states, modulus)


print(crack_unknown_modulus([2818206783446335158, 3026581076925130250,
      136214319011561377, 359019108775045580, 2386075359657550866, 1705259547463444505]))