我最近在收听 security now 播客,他们顺便提到线性同余生成器 (LCG) 很容易破解。我在第一年的统计计算课程中使用 LCG,并认为破解它会成为一个很好的“额外”问题。
有什么不涉及蛮力破解LCG的好方法吗?
我不确定这个问题是否过时,但我不确定在哪里发布这个问题。此外,我的标签也不是很有帮助,因为我没有足够的代表来创建新标签。
我最近在收听 security now 播客,他们顺便提到线性同余生成器 (LCG) 很容易破解。我在第一年的统计计算课程中使用 LCG,并认为破解它会成为一个很好的“额外”问题。
有什么不涉及蛮力破解LCG的好方法吗?
我不确定这个问题是否过时,但我不确定在哪里发布这个问题。此外,我的标签也不是很有帮助,因为我没有足够的代表来创建新标签。
是的。有非常有效的方法可以打破线性同余生成器。
线性同余生成器由s n+1 = 定义为n + b mod m,其中m是模数。在其最简单的形式中,生成器仅输出s n作为第n个伪随机数。如果攻击者知道m并且不知道a,b,那么 Thomas 描述了如何破解它。
如果a,b,m都不知道,仍然可以通过首先恢复m来破坏线性同余生成器。推导出如何有效地做到这一点是一个有趣的练习;可以办到。我将在下面展示如何;如果您想自己弄清楚,请不要继续阅读。
要恢复m,定义t n = s n+1 - s n和u n = | t n+2 t n - t 2 n+1 |; 那么很有可能你会得到m = gcd( u 1 , u 2 , ..., u 10 )。10 这里是任意的;如果您将其设为 k,则此失败的概率在k中呈指数级小。如果有人有兴趣,我可以分享一个为什么这有效的指针。
重要的教训是线性同余生成器是不可挽回的不安全并且完全不适合加密使用。
补充:@AviD 会更讨厌我 :),但对于那些要求它的人来说,这是为什么它有效的数学原理。
关键思想:t n+1 = s n+1 - s n = (as n - b) - (as n-1 - b) = as n - as n-1 = at n mod m和t n+ 2 = a 2 t n mod m,并且t n+3 = a 3 t n mod m。因此t n+2 t n - t n+1 2 = 0 mod m,即 | 吨n+2吨n - t n+1 2 | 是 m 的随机倍数。漂亮的数论事实: m的两个随机倍数的 gcd将为m,概率为 6/π 2 = 0.61;如果你取其中k个的 gcd,这个概率会非常接近 1(k 中的指数快)。是不是很酷,还是什么?
线性同余生成器是线性的,这应该说明一切。
也就是说,你有一个状态s,它更新为:s ← as + b mod w,对于两个常数a和b,以及一个方便的模数w(通常2 32:s,a和b是 32 位字);输出包含s的连续值。如果您有三个连续的输出(s 0、s 1和s 2),那么您将得到两个未知数(a和b )的两个线性方程),用初等算术很容易解决。
这可以扩展到仅获得部分值s 的变体,可能不是连续的。如果a和b是两个 32 位常量,则只需要大约 96 位的输出来重新计算常量。
求解 m 的另一种方法来自本文。
本质上,这种方法利用了线性同余生成器在平面测试中显着失败的事实。使用 4 个输出的 3x3 矩阵的行列式是m的倍数。
如果x_1 = n_1 / m和x_2 = n_2 / m是互质数,则两个倍数(m的n_1和n_2的gcd 为m 。
k 个整数互质的概率由 1/ζ(k) 给出,因此x_1和x_2互质的概率为 1/ζ(2) 或 6/π^2,约为 61%。
就像@Thomas 所说,一旦找到m,问题的其余部分就很容易了。