流密码

# 流密码 LCG

# 线性同余生成器

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

• 增量计算 b：

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

# 代码块

1
2
3
4
5
6
7
8
9
10

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed

# LCG 公式推导

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

• 同理

$$X_{n+1}=(aX_{n}-ab)\mod m$$

# 已知结果恢复模 m

# 连续情况

• 结果案例：

  $$X_1,X_2,X_3,...,X_n$$

• 引入计算公式：

$$t_i=X_{i+1}-X_i$$

$$t_i=X_{i+1}-X_i=a^{i}(X_i-X_{i-1})$$

• 依据等比数列推导：

$$a_ia_j=a_m^2(m=(i+j)/2)$$

• 即：

$$t_{i+1}t_{i-1}=t_i^2$$

$$t_{i+1}t_{i-1}-t_i^2 \equiv 0\pmod{m}$$

通过求解 m 的倍数的公因式得到 m。

# 不连续情况

• 结果案例:

  $$X_1,X_3,X_5,X_7,X_9$$

• 模计算：

  $$X_{i+j}-X_{i}=a(X_{i+j-1}-X_{i-1})~~~(j为整数)$$

  $$X_3-X_1=aX_1+b-(aX_0+b)=a(X_2-X_0)$$

[!NOTE]

j 表示不连续结果情况下之间的间隔。

其他同理。

• a 的推导式：

  $$a^2=(X_{i+j}-X_{i})(X_{i}-X_{i-j})^{-1}\mod m ~~~(j为整数)$$

$$a^2=(X_5-X_3)(X_3-X_1)^{-1}\mod m$$

[!NOTE]

a 推导计算参考 RSA

$$a^2=c\pmod{n}$$