背景
让我对加密社区感到困惑的一件事是人们似乎讨厌LCG并写它们不费吹灰之力就可以修复它们的缺陷，但是它们也很像LFSR，并且经常对其进行修复。
原始的LCG和LFSR都很弱
在施耐尔的应用密码学（1996）中），他关于LCG的评论令人作呕：
不幸的是，线性同余生成器不能用于密码学。他们是可以预见的。线性同余生成器首先由Jim Reeds（1977，1979a，1979b）打破，然后由Joan Boyar（1982）打破。 [...]
其他研究人员扩展了Boyar的研究来打破任何多项式同余生成器（Lagarias和Reeds 1988，Krawczyk 1989，Krawczyk 1992）。截断的线性同余生成器也被破坏（Frieze等，1984； Hastad＆Shamir 1985，Frieze等，1988），以及参数未知的截断线性同余生成器（Stern 1987，Boyar 1989）。大量证据表明，同余生成器对密码学没有用。
相比之下，这本书发送了有关LFSR的混合信息，说出了积极的含义，例如：
由于简单的反馈序列，大量的数学理论可以用于分析LFSR。密码学家喜欢分析序列，以使自己确信它们的随机性足以确保安全。 LFSR是密码术中最常见的移位寄存器类型。
又说：
另一方面，已经破解了数量惊人的看似复杂的基于移位寄存器的生成器。当然，像国家安全局这样的军事密码分析机构已经破解了很多。有时候，一次又一次地提出简单的建议令人惊奇。
最近，迅达2009同意了后者的建议，说：
因此，LFSR不能满足R2的要求[缺乏可预测性] ，它们绝对不适合敏感的密码应用程序。
更多的安全变体…？
“应用密码学”的RNG章节的其余大部分都集中在LFSR变体以复杂的非线性方式组合了LFSR，使它们更难以破解。
但在我看来，这是一个奇怪的对比，它完全不赞成尝试改进LCG，他说：
许多人研究了线性同余生成器的组合（Wichmann＆Hill 1982，L'Ecuyer 1988）。结果不再具有密码安全性，但是组合的周期更长，并且在某些随机性测试中表现更好。
这里令我感到惊讶的是，与本书的其他大部分内容不同，引用并不支持这些主张。所引用的论文均未提及安全性或加密技术，因此Schneier在何处声称“结果不再具有加密安全性？”？
之所以有趣，是因为1985年Knuth提出了另一种说法，即：
尽管我们已经看到线性同余序列本身并不能导致安全加密，但是稍加修改就会破坏此处介绍的方法。特别是，似乎没有办法解密由经过改组的线性同余序列生成的高阶位的序列。[...]
当然，这些参考文献的年代很久，但是我看到的大多数讨论似乎都回溯到1980年代和1990年代，因为它们不再使用LCG。
LCG破解技术有多脆弱……？
，这最终导致了我的问题。这些破解LCG的技术到底有多脆？它们真的有致命的缺陷，无法修复吗？
让我们用一些示例C代码使其变为现实：
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t result;
uint64_t state = SEED;
for (int i=0; i < 32; ++i) {
state = state * MULT + INC;
result = state >> 32;
result ^= XOR;
printf("0x%08x, ", result);
}
printf("\n");
}
案例0：一切都知道
因此，如果我们设置
SEED=0x35e647cfd3423fd0ull，MULT=0xc278c0d1c04a88d9ull和INC=0 XOR=0，程序将产生0x59502137, 0xb6152ece, 0xbbd2cb88, 0xef05249f, 0x3ec02cd5, 0x2b0eca82, 0x0a3120be, 0x5116f6fb, 0x8b06b68c, 0x01367995, 0xca5789bd, 0xa40f57ff, 0x5f6d75bb, 0x544951f7, 0x8f9e70c8, 0x74307957, 0x70aab16c, 0x0ec42e72, 0x9bb2a42d, 0x2c5aa6aa, 0xe3cff469, 0x37881c03, 0x8d7853ba, 0xd6beb049, 0xa9fc0e6e, 0xbbc5bd2b, 0x33462a03, 0xad508c7e, 0xe31313e9, 0xf30418ae, 0xbefc1b02, 0xc0134d22,
情况1：普通情况
现在
SEED是未知的，MULT=0xc278c0d1c04a88d9ull INC=0 XOR=0，输出是0x8b1294a5, 0xae5cbf0d, 0x2da164bd, 0xcbe27c6d, 0x6d800d17, 0x8f576a33, 0x6ea4915b, 0x97ada3d5, 0x8ab31e5d, 0x0bb313d2, 0xfbee8ebf, 0xf1d09659, 0x5a54428e, 0x34d32f9a, 0xe800efdb, 0x5a313abd, 0x844a1328, 0xed9cf267, 0x5883910f, 0x7a44aa80, 0x0e34d575, 0x7e3453df, 0x2267bf41, 0x8c234c85, 0xa359f8b8, 0xf78f0126, 0x7902934e, 0x5ae97dc1, 0x1ba40108, 0x67f5ca64, 0x7aed8c5e, 0xceccf54b,
上面的内容应该很容易破解。甚至蛮力也是可行的，因为我们只需要搜索2 ^ 32个可能的状态。
情况2：已知技术
现在
SEED和INC未知，MULT=0xc278c0d1c04a88d9ull和XOR=0以及输出是0x8c005b3e, 0x27e3338e, 0x1bb199bb, 0x46449299, 0x4b747cca, 0x290032ca, 0x2a6e907f, 0x6b1bd36f, 0xab7f4d33, 0x9b7a73be, 0xe9ae522c, 0x171e7e55, 0x95b0dcd2, 0xd93e6986, 0xddd1a6d2, 0xf2e197e5, 0x8e621adc, 0x0ac2dd7e, 0x31fafcce, 0xc7e19a1a, 0x5f9b0788, 0x9f3a790e, 0xe0e76b17, 0x6fcf2716, 0x0106a4fb, 0x3e64838a, 0x508cc169, 0x690a7b96, 0xde80a6cc, 0xbbcc6546, 0x76e80fe9, 0x6683486d,
这也应该是可中断的，但是我们需要使用文献中的技术，因为强行方法是不可行的。我很想看看能真正打破这一点并弄清楚下一个数字将是什么的代码。
案例3：添加了非线性（更难？）
现在
SEED，INC和XOR是未知的MULT=0xc278c0d1c04a88d9ull，输出是0x5e3af925, 0x1b7f8e1a, 0x268c64d1, 0x4b614b92, 0xba6c7a4d, 0xe4103860, 0xfe373528, 0x768f9a04, 0xedab3415, 0x2605ff3f, 0xb01e70bb, 0xff65e40a, 0x50980bee, 0xe9fb0d78, 0xdf3754bd, 0x46cce80d, 0xfe1395ac, 0x2e663615, 0xdebea707, 0x4d2cd17d, 0x30f0c21c, 0xb15a64ee, 0x21d38d72, 0xbb8e8c6d, 0x114447d1, 0x5362837c, 0xed46a733, 0x37526997, 0xf7ac14c2, 0xc33e7134, 0x96a9d739, 0x3ee606ba
所以，这是我的问题的症结所在。这个变化比上一个变化难吗？从我对打破截断的LCG的标准技术的阅读中，这种增加的非线性是一个问题。我们可以抵消XOR，但这打破了我们已经为抵消增量所做的减法。我们可以取消一个，但不能两个都取消。
（如果仍然很简单，我的常数是什么？要分享破坏它的实际代码吗？）
4：更难吗？
因此，现在
SEED，INC，XOR和MULT都是未知的，输出为0xc325ad70, 0x5ac2c779, 0xafa3561b, 0xa39f9107, 0x256264b5, 0x8d07c2e8, 0x55d53f9e, 0xb090eacc, 0x8b5a28a9, 0xa5e2a296, 0xc0650347, 0x0718efdb, 0x66c331c5, 0xd00236cf, 0x22118dc5, 0x4f9d67d0, 0xa6793bfe, 0x00ad774d, 0xd8337c8f, 0x49aab5b3, 0x96e419c8, 0xd6a9385b, 0x47108063, 0xde06326f, 0x2d4cd28c, 0xb0f97be8, 0x494f5df1, 0x8d53de30, 0x0eee9cbc, 0x9ea6beb1, 0xbefa03b6, 0x5a3d1fea,
破解有多难？ （如果还是容易的话，我的常量是什么？要共享破坏它的实际代码？）
以前的StackExchange问题
我知道这里的先前讨论，在这里，但是这些答案中没有一个与这个问题匹配，它们解决的问题是特定种类的LCG有多弱（通常从一个容易破解的示例开始），而不是所使用技术的脆弱性。
Update：问题已澄清
（某些用户希望将我的原始问题归为“过于广泛”，因此我澄清了此问题，已解决了该问题。）
所以，明确地说，我的问题是：
我知道案例1很简单，案例2已经发布了解决它的技术。但是，我的问题是：
是否存在用于破解案例3或4的有效已知技术？如果是的话，它们是什么？
那里是否存在用于破解案例2的任何实现代码。
我希望这足够简单易懂，或者让人们说“我”在密码学领域做了很多工作，我不知道答案。”
#1 楼
此答案解决了问题中的案例1和2，以提供基线，而案例3（我最感兴趣的案例）仍未解决。案例1，零增量
在这种情况下，我们将考虑一个简单的Lehmer风格的LCG（又称MCG），其中包含种子$ s_1 $，乘数$ a $和$ b $状态位，并返回$ r $位。模量$ M = 2 ^ b $，内部状态为$ s_1，a s_1，a ^ 2 s_1，a ^ 3 s_1，a ^ 4 s_1，\ ldots \ mod M $。输出值通过整数除以$ m = 2 ^ {b-r} $产生。
如果说已知的高阶位是$ h_1，h_2，h_3，h_4，\ ldots $，未知的低阶位是$ l_1，l_2，l_3，l_4，\ ldots $，因此可以这样说：
$$
\ begin {eqnarray *}
s_1＆=＆h_1 m + l_1 \ mod M \\
a s_1 ＆=＆h_2 m + l_2 \ mod M \\
a ^ 2 s_1＆=＆h_3 m + l_3 \ mod M \\
＆\ vdots＆
\ end {eqnarray *}
$$
在给定的示例中，$ a = 14013162247670106329 $，$ b = 64 $，$ r = 32 $，$ M = 2 ^ {64} $，$ m = 2 ^ {32} $。
LLL公式
在LLL公式中，我们将采用等式
$$
\ begin {eqnarray *}
M s_1＆=＆0 \ mod M \\
a s_1-s_2＆=＆0 \ mod M \\
a ^ 2 s_1-s_3＆= ＆0 \ mod M
\ end {eqnarray *}
，并将它们表示为格子$ L $，其中每行$ L_i。 （s_1，s_2，s_3）= 0 $。
$$
L = \ left（
\ begin {array} {ccc}
M＆0＆ 0 \\
a＆-1＆0 \\
a ^ 2 \ bmod M＆0＆-1
\ end {array}
\ right）
$$
在示例中，它变为
$$
\ left（
\ begin {array} {ccc}
18446744073709551616 ＆0＆0 \\
14013162247670106329＆-1＆0 \\
9716750713725077489＆0＆-1 \\
\ end {array}
\ right）
$$
如果应用格化约简（例如Mathematica中的
LatticeReduce），则会得到：$$
\ left（
\ begin {数组} {ccc}
238170＆2443922＆662052 \\
-2629560＆974809＆-465865 \\
\ end {array}
\ right）
$$
这告诉我们
$$
\ begin {eqnarray *}
238170 s_1 + 2443922 s_2 + 662052 s_3＆= ＆0 \ mod M \\
-2629560 s_1 + 974809 s_2 + -465865 s_3＆=＆0 \ mod M \\
341923 s_1 + -550461 s_2 + 2727218 s_3＆=＆0＆mod M
\ end {eqnarray *}
$$
从某种意义上说，这是“更好的”，因为它是一个更好的线性方程组，但是为了实际解决手头的问题，我没什么用，因为我的方程式求解器（Mathematica）即使不使用晶格约简也不费力地求解方程。
直接求解
给定我们的方程式，我们可以用Mathematica编写，
SolveMCG[a_, b_, r_, h1_, h2_, h3_] :=
With[{M = 2^b, m = 2^(b - r)},
Solve[{ s == l1 + h1 m,
a s == l2 + h2 m + k2 M,
a^2 s == l3 + h3 m + k3 M,
l1 >= 0, l1 < m,
l2 >= 0, l2 < m,
l3 >= 0, l3 < m},
Integers]]
，然后运行
SolveMCG[14013162247670106329, 64, 32,
2333250725, 2925313805, 765551805]
以下结果（大约百分之一秒）：
{{k2 -> 7612682177356138107,
k3 -> 106677750491238099311986697652283092078,
l1 -> 3882613991, l2 -> 3819575247, l3 -> 2041194103,
s -> 10021235561125903591}}
这里是正确的只能推断出低阶位和初始种子，而我们仅使用了三个32位输出就可以做到这一点。
实际上，三个输出可以说是过大了。实际上，我们仅需两个输出就可以解决它！给出类似的定义：
SolveMCG[a_, b_, r_, h1_, h2_] :=
With[{M = 2^b, m = 2^(b - r)},
Solve[{ s == l1 + h1 m,
a s == l2 + h2 m + k2 M,
l1 >= 0, l1 < m,
l2 >= 0, l2 < m},
Integers]]
运行
SolveMCG[14013162247670106329, 64, 32, 2333250725, 2925313805]
（我们甚至可以用Wolfram Alpha解决） ，给出
{{k2 -> 7612682176901725222, l1 -> 3284430794, l2 -> 491393594,
s -> 10021235560527720394},
{k2 -> 7612682177356138107, l1 -> 3882613991, l2 -> 3819575247,
s -> 10021235561125903591}}
唯一的问题是，在这种情况下，我们对系统有两种解决方案（第二种是我们实际想要的解决方案）。
三个输出为我们提供了独特的解决方案（在这种情况下），实际上，即使下降到24位，我们仍然具有三个输出的独特解决方案。
看看随着我们进一步减少输出位数而发生的事情很有趣。对于来自64位状态的16位输出，我们需要四个输出以找到唯一的解决方案。同样，12位输出需要6个输出，10位输出需要7个，8位输出需要8个（在0.5秒内求解），而4位输出需要16个（但需要一分钟才能解决！）。后一种情况很有趣，因为一些作者声称，如果我们仅返回$ \ log_2 b $位，但是$ \ log_2 64 = 6 $，则LCG可以保证安全，这时我们仍然可以轻松地解决问题。
但是也许这些主张确实有一定的依据-3位输出需要22个输出（不是很多），但是需要76分钟来解决，这使我猜测要解决2个问题位输出将需要近两个月的时间，而且（如果我的推断是正确的！），如果仅采用高位输出，Mathematica将需要大约五亿年的时间才能解决。糟糕！
情况2，未知增量
这里的技巧是观察if
$$
\ begin {eqnarray *}
s_2＆=和a s_1 + c \ mod M \\
s_3＆=和a s_2 + c \ mod M \\
s_4＆=和a s_3 + c \ mod M \\
＆\ vdots＆
\ end {eqnarray *}
$$
然后
$$
\ begin {eqnarray *}
s_2-s_1 ＆=＆（（（a-1）s_1 + c）\ mod M \\
s_4- s_3＆=＆a ^ 2（（a-1）s_1 + c）\ mod M \\
＆\ vdots＆
\ end {eqnarray *}
$$
换句话说，如果我们取连续值之间的差，我们将再次得到Lehmur风格的LCG。
一个缺点是，减去截断的高阶位可能不会产生与减去实际值，然后将其截断（由于缺少借位），因此我们必须稍作搜索。但这很容易做到：
SolveLCG[a_, b_, r_, lh1_, lh2_, lh3_, lh4_] :=
Flatten[Table[SolveMCG[a, b, r, h1, h2, h3],
{h1, Mod[{lh2 - lh1 - 1, lh2 - lh1}, 2^(b - r)]},
{h2, Mod[{lh3 - lh2 - 1, lh3 - lh2}, 2^(b - r)]},
{h3, Mod[{lh4 - lh3 - 1, lh4 - lh3}, 2^(b - r)]}], 3]
对于我们的问题，运行
SolveLCG[14013162247670106329, 64, 32,
2348833598, 669201294, 464624059, 1178899097]
产生
{{k2 -> 8533036703073522045, k3 -> 5916822271048598914,
l1 -> 111392721, l2 -> 2094520361, l3 -> 3114664641,
s -> 11232778258835814353}}
此结果不能完全解决问题，因为它仅计算差值的低阶位，而无需告诉我们原始种子的低阶位。不过，这将使我们非常接近RNG的输出。
但是请注意，我们的减法技术在第3种情况下被异或运算所破坏。
此外，请注意，在尝试使用Mathematica之前，我尝试使用几种ILP求解器（例如lp_solve，GLPK和Mathematica的
LinearProgramming），但取得的成功要少得多。 ILP求解器在可行解决方案数量很多的优化方面效果最佳。在这种情况下，只有一个可行的解决方案，并且LP无法帮助求解器找到它，因此，在没有帮助的情况下（即使告诉他们答案），求解器也无法找到解决方案。 Ma，Mathematica的Solve函数没有说明如何找到解决方案。评论
$ \ begingroup $
很高兴看到Mathematica提供的自动化提供了与我尝试过的SMT求解器相似的结果-轻松地解决了情况1，并为情况2提供了部分解决方案。
$ \ endgroup $
– Thomas M. DuBuisson
2014年12月9日20:30在
$ \ begingroup $
Thomas，如果您为案例1和案例2（例如，在Cryptol中）构建了解决方案，那么我很乐意看到您写下答案并发布，因为很高兴看到可以解决问题的其他方法！
$ \ endgroup $
–慈善
2014年12月9日在22:37
$ \ begingroup $
如果有足够的输出，您的方法（或Contini＆Shparlinski改进了Stern的方法）可以仅用输出的前4位来解决情况2，则我们可以列举XOR的$ 2 ^ 4 $可能值遮罩，并通过最多解决案例2来解决案例3。
$ \ endgroup $
–fgrieu♦
2014-12-10 8:36
$ \ begingroup $
@fgrieu，我认为您的想法适用于案例1的XOR，但对于案例2（大多数论文都用“哦，减去！”来掩饰），由于计算量大，因为借位的可能性（通过减去低位）。我们需要十六个术语来解决它，还有十六个未知借位，这使$ 2 ^ {16} $成为可能。加上我们的$ 2 ^ 4 $ XOR，我们有$ 2 ^ {20} $个案例需要搜索，每个案例的时间间隔为1分钟。那是大约两年的工作。蛮力地使用32位XOR常数实际上更快，您将在17个月内完成！
$ \ endgroup $
–慈善
2014-12-10 18:05
$ \ begingroup $
一种改进的攻击方法：因为$ M = 2 ^ {64} $是$ 2 $的幂，所以我们可以删除问题中每个常量和变量的最左边的$ 32-r $位，例如，用$ r \ approx6 $。现在我们知道状态的$ r /（r + 32）$（在情况3中：我们可以枚举未知的$ r $位XOR进行XOR），而不是我先前的攻击中的$ r / 64 $；根据Contini＆Shparlinski的说法，这是一个容易解决的问题。如果解决带有$ r /（r + 32）$暴露位的情况2的运行时间是$ f（r）$，请选择将$ 2 ^ rf（r）$最小化的$ r $以最小化总时间以找到正确的XOR 。然后，一个接一个地查找其他位非常容易。
$ \ endgroup $
–fgrieu♦
2014-12-10 21:38
#2 楼
这是一个进行中的工作，主要是试图解决问题中的案例3，因为案例2的问题已在另一个答案中进行了处理，并且已经过深入研究：雅克·斯特恩（Jacques Stern）：秘密线性同余生成器在1987年第28届计算机科学基础年度研讨会上进行了加密（不是盲目搜索）；在密码学上也不安全；
艾伦·弗里兹（Alan M. Frieze），约翰·哈斯塔德（Johan Hastad），拉维·坎南（Ravi Kannan） Jeffrey C. Lagarias，Adi Shamir：《重构满足线性一致的截断整数变量》，在《 SIAM计算杂志》，第17卷，1988年第2期，也可以从第一作者的网站上免费获得；
Scott Contini，Igor E.Shparlinski：关于斯特恩对秘密截断的线性同余生成器的攻击，在ACISP 2005程序中。
我将首先建立线性同余生成器的特征：远离$ t $步的LCG的状态通过简单关系（复杂度独立于$ t $，如果我们知道乘数），对于使用迭代密码构建的CSPRNG时，复杂度标价为$ t $。结合对LCG内部状态的直接暴露，这就是从加密的角度通常认为LCG较差的原因。
让$ \ forall j \ in \ mathbb N，\ s_ {j + 1} = \ big（s_j \ cdot a + c \ big）\ bmod M $是LCG的重复关系。因此，
$ \ \ \ \ \ \ forall j \ in \ mathbb N，\ s_ {j + 2} = \ big（s_j \ cdot a ^ 2 + c \ cdot（a + 1）\ big ）\ bmod M $
$ \ \ \ \ \ \ forall j \ in \ mathbb N，\ s_ {j + 3} = \ big（s_j \ cdot a ^ 3 + c \ cdot（a ^ 2 + a + 1）\ big）\ bmod M $
并归纳
$$ \ forall j \ in \ mathbb N，\ forall t \ in \ mathbb N，\ s_ {j + t} = \ big（s_j \ cdot a ^ t + c \ cdot {a ^ t-1 \ over a-1} \ big）\ bmod M $$
这无需明确计算中间步骤即可从当前状态得出未来状态。此外，如果$ \ gcd（a，M）= 1 $（应如此），则此等式链接说明与等式$ s_ {j + t} = s_j \ cdot a_t + c的距离$ t \ in \ mathbb Z $步距\ cdot b_t \ bmod M $，具有乘法器$ a $和$ t $的$ a_t $和$ b_t $简单已知函数。
用于案例3的具体解决方案按措辞（$ M = 2 ^ {64} $，$ a = \ text {c278c0d1c04a88d9} _ {16} $，未知的64位
INC = $ c $，未知的32位XOR = $ x $和32连续输出），一个值得尝试的想法是在布尔可满足性的框架内构建问题的表达。我猜想，通过合并许多关系$ s_ {j + t} = s_j \ cdot a_t + c \ cdot b_t \，使问题严重过分指定是有利的。预先计算了$ a_t $和$ b_t $的bmod M $（希望是SAT解算器将利用额外的关系）； 也许将变量$ c $更改为等效的$ c'$略微简化了乘法常数$ b_t $;
可能会在一定程度上修剪给定值，以便相应地修剪大小。
暂定草图：
知道$ a $，以$ 0 <| t | <32 $计算$ a_t $，$ b_t $，这样$ s_ {j + t} = s_j \ cdot a_t + c \ cdot b_t \ bmod M $上面的公式；
选择$ r $的不同值$ j_p \ in \ {1,32 \} $对应于我们保留的$ s_j $的索引（通过熵参数，我们需要$ 5 \ le r \ le32 $，这样我们至少拥有与未知数一样多的给定位；我将尝试从$ r \ approx8 $开始）；对于给定的$ r $，有利的是至少$ a_ {j_p-j_q} $中的某些汉明权重较低；
选择一些奇数的64位$ z $，以使汉明权重至少为一些$ b'_t = z ^ {-1} \ cdot b_t \ bmod M $非常低；我们将使用$ c'= z \ cdot c \ bmod M $而不是
INC / $ c $作为增量的未知数，等式变为$ s_ {j + t} = s_j \ cdot a_t + c'\ cdot b'_t \ bmod M $; 分配SAT变量：
$ c'$的64个变量，
XOR / $ x $的32个变量（注意，这些变量是在给定的极性变化内$ s_ {j_p} $的高32位）； 每个$ r $状态的低32位的32个变量$ s_ {j_p} $被选择
表达$ r \ cdot（r-1）$关系$ s_ {j_p} = s_ {j_q} \ cdot a_ {j_p-j_q} + c'\ cdot b'_ {j_p-j_q} \ bmod M $ for $ p \ ne q $作为二进制变量之间的关系，转换为SAT子句：
模数缩减是完全免费的，因为$ M = 2 ^ {64} $;
乘以已知常数$ a_ {j_p-j_q} $和$ b'_ {j_p-j_q} $很简单，减少了$ s_ {j_p} $或$ c'$位的二进制加法；
我们的基本构件是具有3个输入和2个输出的完整二进制加法器$ S = （I_0 \ wedge I_1 \ wedge I_2）\ vee（I_0 \ wedge \ overline {I_1} \ wedge \ overline {I_2}）\ vee（I_1 \ wedge \ overline {I_2} \ wedge \ overline {I_0}）\ vee（ I_2 \ wedge \ overline {I_0} \ wedge \ overline {I_1}）$和$ C =（I_0 \ wedge I_1）\ vee（I_1 \ wedge I_2）\ vee（I_2 \ wedge I_0）$我的加法器不需要$ C $的输出或$ I_2 $的输入；对于每个关系，我们需要大约$ 65 \ cdot32 $二进制加法器（$ j_p $和$ z $的一个不错的选择会有所减少）；
对于每个加法器，我们最多需要2个额外的变量（每个使用的输出一个，除了那些有点$ s_ {j_p} $的变量）；
特别是在低位，会有一些重复的变量，我们可以将其删除；
输入最先进的SAT解算器，并希望它吐出解！规模可控制的遗体；但我无法证明它可以有效解决，而无需尝试！
评论
$ \ begingroup $
首先，感谢您成为第一个写下答案的人！对于LLL算法部分，您提到了经常引用的结果（Frieze，Stern等），但是最好一直进行到最后，因为使用LLL算法后有很多部分是通常是粗略的/手挥手的，细节是魔鬼！您还说：“但是我不能证明它可以有效地解决，而无需尝试”，我认为实际尝试解决问题是关键。毕竟，可以使用数字逻辑计算出的任何问题都可以解释为SAT实例。
$ \ endgroup $
–慈善
2014年12月8日18:53
$ \ begingroup $
@Charphacy：我很想尝试SAT方法（没有保险）。我认为我不能使用LLL，因为输出的内容太少了，至少是我绘制草图的方式（没有详细检查参考文献）。
$ \ endgroup $
–fgrieu♦
2014年12月8日21:12
$ \ begingroup $
FWIW，对于情况1和2，我添加了自己的答案，表明对于只有三个输出的第一种情况，您可以获得很好的答案，对于只有四个输出的第二种情况，您可以获得很好的近似值。我还提到了一些有关LLL算法的信息，但我大多不使用/不需要它。
$ \ endgroup $
–慈善
2014年12月9日在9:55
$ \ begingroup $
您说“如果我们知道乘数，则复杂度与t无关”，但是此属性意味着存在超前的情况，并且对于某些加密安全的RNG（例如ChaCha20）实际上是正确的，因此我不认为必然会跟随前进意味着不安全感。可能会实现跳转功能的简单性，但即使对于LCG，其本质上也是求幂运算。
$ \ endgroup $
–慈善
2014年12月9日17:56
$ \ begingroup $
@Charphacy：我已根据您的最后评论对我的回答进行了修改。
$ \ endgroup $
–fgrieu♦
2014年12月9日18:21
#3 楼
把我的一些评论写成文字。这还不算是一个答案，但对于评论来说太多了。在我声称要使用SMT解决案例1的评论中-这是错误的，我弄错了。我曾经在案例2和案例3中运行SMT（扩音器，Z3，CVC4，yices）一段时间，但没有成功。与成功最接近的事情是识别可产生前约96位匹配输出的种子。超过该点，求解器似乎每增加一小段匹配输出，就会在几何上（或更糟）花费更多的时间匹配种子。该公式是对Cryptol的简单使用：lcg : {n} (fin n) => [64] -> [64] -> [64] -> [64] -> [n][32]
lcg seed inc ex mult =
[rand | (_,rand) <- take`{n} (drop`{1} seq) ]
where
seq = [(seed,0)] # [(st * mult + inc, drop (((st * mult + inc) >> 32) ^ ex)) | (st,_) <- seq]
harderOutput : [4][32]
harderOutput = [0x5e3af925, 0x1b7f8e1a, 0x268c64d1, 0x4b614b92]
harderMult : [64]
harderMult = 0xc278c0d1c04a88d9
knownMult : [64]
knownMult = 0xc278c0d1c04a88d9
knownXor : [64]
knownXor = `0x0
knownOutput : [4][32]
knownOutput = [0x8c005b3e, 0x27e3338e, 0x1bb199bb, 0x46449299]
trivialMult : [64]
trivialMult = 0xc278c0d1c04a88d9
trivialOutput : [4][32]
trivialOutput = [0x8b1294a5, 0xae5cbf0d, 0x2da164bd, 0xcbe27c6d]
doneSeed : [64]
doneSeed = 0x35e647cfd3423fd0
doneMult : [64]
doneMult = 0xc278c0d1c04a88d9
doneOutput : [4][32]
doneOutput = [0x59502137, 0xb6152ece, 0xbbd2cb88, 0xef05249f]
// case 1:
// :sat \s -> lcg s zero zero trivialMult == trivialOutput
// case 2:
// :sat \s i -> lcg s i knownXor knownMult == knownOutput
// case 3:
// :sat \s i x -> lcg s i x harderMult == harderOutput
一个例子，它很快终止，在其中我们发现初始值产生相同的前3个字（96位） ）包括：
Main> :sat \s i x -> lcg s i x harderMult == take `{3} harderOutput
(\s i x -> lcg s i x harderMult ==
take`{3} harderOutput) 0x897c9820380325ef 0xa75286c029abc35f
0x00000000dd1aa469 = True
请注意，这种方法实际上很难（好，慢）来获得唯一未知的是种子的解决方案：
Main> :sat \s -> lcg s zero zero trivialMult == take `{3} trivialOutput
... still waiting after many minutes ...
因此，与我之前的评论相反，看来@Charphacy的思维能力加上Mathematica在此问题上比典型的SMT做得更好。
编辑：并且我的一个很长时间的SAT会话，案例2运行了不到两周，完成了
:sat \s i -> lcg s i knownXor knownMult == knownOutput
(\s i -> lcg s i knownXor knownMult ==
knownOutput) 0x48f0d1a3afc9565e 0x2f21de6409b2bc69 = True
所以种子是
0x48f0d1a37afa2b67，增量是0x25eff26152b834d1。...所以真正的种子是
0x48f0d1a3afc9565e并增加0x2f21de6409b2bc69（除非我输入了错误的内容）。评论
$ \ begingroup $
感谢您编写代码！我已经将您的lcg函数的通用版本放在pastebin上（在此注释中没有空格！），这对于尝试使用不同的位长以查看它们如何影响性能可能很有用。使用您的代码（以及我的调整），我确认您的96位大小写情况可以很快解决（yices2几乎可以立即解决），其他情况很难解决，但是我认为这是因为它的约束很有限（不同的求解器得到不同的答案）。
$ \ endgroup $
–慈善
2014-12-11 18:46
$ \ begingroup $
@Charphacy查看我的编辑。
$ \ endgroup $
– Thomas M. DuBuisson
2014年12月22日下午5:40
$ \ begingroup $
A，您的SAT求解器发现的种子和增量不是正确的。第8个和第9个输出应分别为0x6b1bd36f和0xab7f4d33，但是您的解决方案将产生0x6b1bd36e和0xab7f4d32。只有种子的高32位是正确的；低阶32位和整个增量不匹配。
$ \ endgroup $
–慈善
2015年3月2日在1:44
$ \ begingroup $
@Charphacy啊，为消除约束以加速求解器而做的很多。我现在发布了新的号码。显然，尽管SAT解算器比暴力破解更有效，但它不足以快速解决此问题。
$ \ endgroup $
– Thomas M. DuBuisson
15年4月17日在3:08
$ \ begingroup $
干得好。添加这些约束后是否需要更长的时间？有趣的是，尽管您的常量再现了我在示例中提供的数据，但它们不是我使用的那些。但是要显示出差异，我们需要在顺序上走得更远。实际上，您的输出在以下位置（以从1开始的顺序编号）关闭了一个：94、232、292、485、633、724、797、871、944、1325、1409、1421、1549、1575， 1803、1883、1897、1992、2069、2106、2140、2159、2297、2479、2546、2615、2626、2663等。它似乎永远保持“足够接近”，但是发生错误的地方似乎是随机的。
$ \ endgroup $
–慈善
15年7月6日在17:29
#4 楼
tl; dr：案例2和3都没有比案例1安全得多。我怀疑人们基于SMT的解决方案存在的问题是这些LCG问题非常严重-受约束：
XOR的高位始终不受约束。
有效XOR的按位求反始终有效。不管可用的输出数量如何，这些总和会产生4个有保证的有效XOR。
此外，任何增量未知的LCG都仅受32个输出的限制。
突破案例3
以下是原始帖子中案例3的结果：
$ time ./breaklcg
......
xorstate = 54e3e355, diff = 44c352df2ab9dd75.........................
state[0] = 0ad91a70c3b723ed, incr = fb9919619a9ba57d, xorstate = 54e3e355........
Success! 386624648 solutions
.....................
xorstate = 2b1c1caa, diff = bb3cad20d546228b.......
state[0] = 7526e58f30c325cf, incr = b5cb57a4d6b243e3, xorstate = 2b1c1caa..........................
Success! 386624648 solutions
......
Success! 773249296 solutions
real 3m21.893s
user 3m19.457s
sys 0m0.927s
（请注意，上面的state [0]不等于SEED，但是是SEED * MULT + INC。速度更快。）
有7.73亿个不同的元组（初始状态，增量，异或状态）与所有输出匹配，分布在4种可能的异或状态（未翻转高位）显示）。打印出来的解决方案只是第一个使用xorstate的解决方案（又名示例）。
此算法是对案例2和3 LCG的完全破解（状态恢复），可以有效地搜索隐藏的种子（种子位-输出位+ 2）。您不会从隐藏的增量或XOR中获得任何实际收益，因为我们可以按顺序解决它们。如您所见，在64分钟的种子和32位的输出下，问题在4分钟之内就可以解决。
但是，由于这是一个搜索，因此如果状态更多，它就不会扩展隐藏。而且，如果每轮只输出高位，那么该算法实际上会通过（初始状态，增量）元组变成完全的蛮力。
破坏情况2
只是为了好玩，这里是情况2的结果：
$ time ./breaklcg
.
xorstate = 00000000, diff = 9be2d85006a3b7d1..........
state[0] = 8c005b3e4d5b6951, incr = ba801c1c0025d379, xorstate = 00000000.......................
Success! 1582435690 solutions
...............................
xorstate = 7fffffff, diff = 641d27aff95c482f.................
state[0] = f3ffa4c1837b8ffa, incr = fd4a9dc24659fd3f, xorstate = 7fffffff................
Success! 1582435690 solutions
.
Success! 3164871380 solutions
real 4m2.416s
user 3m59.766s
sys 0m0.927s
由于xorstate == 0，所以只有第一组结果的一半有效，但仍然有7.91亿个解决方案。这也是@Thomas M. DuBuisson提供的解决方案。 :-)
我不知道如何解决案例4的LCG，但我怀疑它只有32个输出的数量不足。无论如何，今天没有时间了，但是我会尽快返回算法背后的理论，实际代码以及一些实验结果，说明需要多少输出才能完全解决这些问题！
算法
从根本上讲，这是未知物的“分层”，可以让我们按顺序攻击它们。
首先，我们将通过LCG'攻击未知XOR：LCG原始LCG的输出之间的差异。根据定义，LCG'的增量为零（因为它抵消了）。同时猜测XOR和初始状态仍然不是很可行，因为它至少是64位的熵。但是请注意，LCG和LCG'是三角函数：新状态的某一位仅取决于状态和增量的低位以及XOR的一位。因此，我们将从猜测XOR的最低2位开始，如果我们发现一个状态+ 2位的xor有效，我们将猜测较高的位，直到拥有全部为止。平均工作约为2 ^ 33个状态更新。
现在我们有了XOR和LCG'的初始状态，我们可以立即计算LCG初始状态的高32位（输出[0 ] ^ XOR）。如果我们知道整个状态，则可以通过一些简单的数学计算增量，因为我们已经有了LCG'的初始状态。所以最后一步就是我们只猜测初始状态的低32位-近似工作2 ^ 31状态更新。
这些约束的约束程度如何？
很多:-)即使使用随机选择的XOR，增量和初始状态生成的2 ^ 32输出，也总是存在多个相同的具有完全相同输出的LCG。在唯一确定LCG之前，需要花费2 ^ 34以上的输出。这完全与破解成本比未知数的熵所暗示的要小得多完全一致。
摘要
我认为可以这样说：包含未知增量将为您提供约1位安全性，而包含未知XOR将为您提供约2位安全性-几乎不值得麻烦。仅增加隐藏状态的数量会使这种特殊攻击更加困难。由于这并不是真正的复杂攻击-基本上是蛮力攻击，因此这些技术是微不足道的，并且实际上是我的第一个非玩具密码分析工作-我怀疑与普通LCG可以使用的分析技术类似的分析技术将使整个结构像普通的LCG一样不安全。很好;-)
评论
$ \ begingroup $
谢谢你！我期待着承诺的下一批！！
$ \ endgroup $
–慈善
16年1月22日在7:36
$ \ begingroup $
我几乎忘了这个！感谢ping @Charphacy。我添加了所有我记得的细节，但不久前我完成了这一工作。希望它有用！
$ \ endgroup $
–安德鲁·波兹（Andrew Bortz）
16年1月24日在5:54
评论
我不确定您的报价有何意义。斐波那契滞后生成器不是线性同余生成器。无论如何，我们在这里谈论的是可预测性而不是统计质量。 （有可能使RNG通过合理的统计测试却是可预测的。）在当前的tAoCP版本（1998年第3版）中，第3.6节（第193卷，第2卷）末尾的问题7是书中唯一谈论基于RNG的加密的地方。这个问题的答案（第599页）毫无保留地引用了他1985年的论文，还引用了Boyar，Frieze等其他许多论文。
问题是您不能只选择INC作为任何值，因为某些值会缩短您的时间。因此在实践中INC可以假定为固定常数。
@Thomas M. DuBuisson：我的直觉是，即使案例3也可以使用Cryptol和SAT / SMT求解器来解决，就像您对一个更为琐碎的问题的很好回答中所做的那样。 $ \; $如果确实可行，那将是一个非常令人信服的演示！
fgrieu：我怀疑是同一件事，并且已经了解到1）SMT求解器在这种情况下的运行速度很慢（该领域的其他人已经知道，所以我发现了）2）Cryptol或SMT中都存在错误发现解决方案时使用了Cryptol异常退出的原因，而不是打印种子等。