LCG是什么

小安 in 问答 2023-09-20 9:19:23

目前我们在编程中经常会使用随机数，但是其中会不会存在什么问题呢？要知道CPU计算中的各种状态都是确定的，在其中的随机数不是凭空产生的，所以这种随机数真的随机吗？目前生成随机数的方式主要分为以下几种:PS: RDRAND指令产生的随机数目前存在争议，在此不做详细讨论。有兴趣可以参考虽然选择很多，但是目前还是主要采用伪随机数的方式来应对实际开发中需要的场景。用于产生这些看起来随机但实际是由确定性算法生成数字的机制被称为”伪随机数发生器”，简称为PRNG

目前我们在编程中经常会使用随机数，但是其中会不会存在什么问题呢？要知道 CPU 计算中的各种状态都是确定的，在其中的随机数不是凭空产生的，所以这种随机数真的随机吗？目前生成随机数的方式主要分为以下几种:
a92878fc8bed4304bfcb994afa9187e7

硬件随机数生成器
利用现有硬件，从非预期方式产生随机数(比如利用音频的产生、硬盘寻址时间等)
伪随机数
量子技术

RDRAND 指令产生的随机数目前存在争议，在此不做详细讨论。有兴趣可以参考 RdRand

虽然选择很多，但是目前还是主要采用伪随机数的方式来应对实际开发中需要的场景。用于产生这些看起来随机但实际是由确定性算法生成数字的机制被称为”伪随机数发生器”，简称为 PRNG。

PRNG 的中心是确定的，如果攻击者知道其内部的完整状态，则可以对未来的值和过去的值进行预测。如果 PRNG 被用于加密密钥、生成证书等场景，就会出现安全问题。

接下来我将详细讲解对线性同余发生器的攻击。

线性同余生成器(LCG)

线性同余方法

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

它是根据递归公式：

其中 A,B,M 是产生器设定的常数。

LCG 的周期最大为 M，但大部分情况都会少于 M。要令 LCG 达到最大周期，应符合以下条件：

B,M 互质；
M 的所有质因数都能整除 A-1；
若 M 是 4 的倍数，A-1 也是；
A,B,N[0]都比 M 小；
A,B 是正整数。

Python 代码实现

由上面的原理我们可以看到，其中最重要的是定义了三个整数，乘数 A、增量 B 和模数 M，因此我们在此用简单的几行 Python 代码实现一下:


class prng_lcg:
    m = 672257317069504227  # "乘数"
    c = 7382843889490547368  # "增量"
    n = 9223372036854775783  # "模数"

    def __init__(self, seed):
        self.state = seed  # the "seed"

    def next(self):
        self.state = (self.state * self.m + self.c) % self.n
        return self.state


def test():
    gen = prng_lcg(123)  # seed = 123
    print gen.next()  # 第一个生成值
    print gen.next()  # 第二个生成值
    print gen.next()  # 第三个生成值

LCG 的优缺点

LCG 目前是分流行，得益于其在数学表达实现上十分优雅、非常容易理解并且容易设计实现、计算速度可以非常快。但是它也存在一些缺点，比如它在加密安全性方面十分弱。接下来将从以下几种情况对其进行攻击。

攻击 LCG

对于 A、B、M 以及 N0 已知的情况
假设我们观察到有一个 LCG 系统产生了以下三组连续的值，并且我们知道内部的参数如下:


# 三组连续的值
s0 = 2300417199649672133
s1 = 2071270403368304644
s2 = 5907618127072939765
# 内部的参数
m = 672257317069504227   # the "multiplier"
c = 7382843889490547368  # the "increment"
n = 9223372036854775783  # the "modulus"

在已知了这些参数之后我们可以很快的推算出未来的数值或者之前的某个数值，所以还是存在安全问题的。


In [1]: m = 672257317069504227

In [2]: c = 7382843889490547368

In [3]: n = 9223372036854775783

In [4]: s0 = 2300417199649672133

In [5]: s1 = (s0*m + c) % n

In [6]: s2 = (s1*m + c) % n

In [7]: s3 = (s2*m + c) % n

In [8]: s4 = (s3*m + c) % n

In [9]: s1
Out[9]: 2071270403368304644L

In [10]: s2
Out[10]: 5907618127072939765L

In [11]: s3
Out[11]: 5457707446309988294L

增量未知
我们不清楚增量，但是我们知道以下信息:


m = 81853448938945944
c = # unknown
n = 9223372036854775783
# 初值和第一个计算值
s0 = 4501678582054734753
s1 = 4371244338968431602

我们稍稍改写下公式就可以将目标 c 计算出来


s1 = s0*m + c   (mod n)

c  = s1 - s0*m  (mod n)

此种类型 Python 攻击代码如下所示:


def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

print crack_unknown_increment([4501678582054734753, 4371244338968431602], 9223372036854775783, 81853448938945944)

增量和乘数都未知
我们虽然不知道增量和乘数但是我们知道以下数值


m = # unknown
c = # unknown
n = 9223372036854775783
# LCG 生成的初值和后面生成的两个值
s0 = 6473702802409947663
s1 = 6562621845583276653
s2 = 4483807506768649573

解决办法很简单，想想怎么解线性方程组就好了


s_1 = s0*m + c  (mod n)
s_2 = s1*m + c  (mod n)

s_2 - s_1 = s1*m - s0*m  (mod n)
s_2 - s_1 = m*(s1 - s0)  (mod n)
m = (s_2 - s_1)/(s_1 - s_0)  (mod n)

此种类型 Python 攻击代码如下所示:


def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

print crack_unknown_multiplier([6473702802409947663, 6562621845583276653, 4483807506768649573], 9223372036854775783)

这个算法中应用到了求模，所以我们就需要逆推。


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n

增量，乘数和模数均未知
现在内部状态基本是都不知道了，但是我们知道初值和随后 LCG 产生的连续的几个值。


m = # unknown
c = # unknown
n = # unknown
s0 = 2818206783446335158
s1 = 3026581076925130250
s2 = 136214319011561377
s3 = 359019108775045580
s4 = 2386075359657550866
s5 = 1705259547463444505
s6 = 2102452637059633432

这次用线性方程式不好解决的了，因为对于每一个方程，我们是不知道前一个模数，因此我们将形成的每个方程都会引入新的未知量：


s1 = s0*m + c  (mod n)
s2 = s1*m + c  (mod n)
s3 = s2*m + c  (mod n)
s1 - (s0*m + c) = k_1 * n
s2 - (s1*m + c) = k_2 * n
s3 - (s2*m + c) = k_3 * n

这就相当于六个未知数和三个方程。所以线性方程组是不可能行得通的了，但是数论里面有一条很有用:如果有几个随机数分别乘以 n，那么这几个数的欧几里德算法(gcd)就很可能等于 n。


In [944]: n = 123456789

In [945]: reduce(gcd, [randint(1, 1000000)*n, randint(1, 1000000)*n, randint(1, 1000000)*n])
Out[945]: 123456789

某些取模运算是会等于 0 的


X = 0 (mod n)

然后，根据定义，这相当于：


X = k*n

所以这种 X != 0 但是 X = 0 (mod n)的情况就很有趣。我们只需要取几个这样的值进行 gcd 运算，我们就可以解出 n 的值。这种是在模数未知的情况下十分常用的方法。

我们在此引入一个序列 – T(n) = S(n+1) – S(n):


t0 = s1 - s0
t1 = s2 - s1 = (s1*m + c) - (s0*m + c) = m*(s1 - s0) = m*t0 (mod n)
t2 = s3 - s2 = (s2*m + c) - (s1*m + c) = m*(s2 - s1) = m*t1 (mod n)
t3 = s4 - s3 = (s3*m + c) - (s2*m + c) = m*(s3 - s2) = m*t2 (mod n)

之后我们就可以得到我们想要的效果了:


t2*t0 - t1*t1 = (m*m*t0 * t0) - (m*t0 * m*t0) = 0 (mod n)

然后我们就可以生成几个这样模是 0 的值，进而利用我们上文讲述的技巧，此种类型 Python 攻击代码如下所示:


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])