【.Net】System.Random伪随机数求逆实现
本帖最后由 Kagamia 于 2023-5-12 23:04 编辑前情提要
我们群里有一个.net Roslyn repl BOT，只要你输入一个合法的C# Expression，它就会自动Eval返回结果。
现在群友想要整这么一个活：
You> new Random(seed).Next()
Bot> 6502
那么这个seed应该填多少呢？
答案是：1624687907
这件事你可以在.net framework. net core .net 5+上随意验证，但不要在mono平台上做这件事。
按我对mono的有限理解，为了保证代码版权洁净，它们不允许反编译.net Framework的实现向mono代码库提交代码，所以它们的伪随机数生成器使用的是完全不同的实现。
// ps5, ps core 6+
(New-Object System.Random 1624687907).Next()
// C# .net Framework, .net core, .net 5+
Console.WriteLine(new Random(1624687907).Next());
这个解不会很难获得，一个显而易见的方法，你可以执行seed=range(0, 2^32-1)挨个试探一遍，总能找到满足你要求的种子。
更有甚者，你可以从微软那里拿到.net Framework的源代码，然后转写成c去做这件事。群友给了这样一个例子：https://pastebin.com/NwVqMswD
按你胃(anyway)，我们似乎有了一个还不错的方案。但如果我们灵机一动，想让它生成今天的日期(20230512)，那这个循环爆破可能耗时稍微有那么一丢丢久。
那么有没有一种算法，可以响应国家节能减排号召，降低时间与空间复杂度，一瞬间返回想要的种子呢？
答案是，有的。
我先给出结论，然后再慢慢解释：
int InferenceSeed(int next) {
long n = 1559595546L - next;
if (n < 0) n += Int32.MaxValue;
return (int)((n * 350788151L) % Int32.MaxValue);
}
用这个算法可以求得，当输入种子为1775349364的时候，第一个随机数返回值为20230512。
如果你感兴趣它是怎么来的，那请继续看下去。
System.Random
.Net基础库内置了伪随机数生成器System.Random，从直觉上你一定认为它是基于线性同余算法。
即使你不去阅读那晦涩难懂的代码，你也可以通过一个小实验轻松验证出这件事：
for(int seed=1;seed<=10;seed++)
Console.WriteLine(new Random(seed).Next()-new Random(seed-1).Next())
-1025583828
1121899819
-1025583828
1121899819
-1025583828
1121899819
-1025583828
1121899819
-1025583828
1121899819
Wtf！它竟然如此有规律，并且你可以一眼计算出来1121899819+1025583828=2147483647，这个数值和Random.Next()返回范围[0, 2147483647)一致，你可以认为它就是对种子进行一个简单线性计算然后取模。
所以现在，你假设随机数生成器生成的第一个值为y，种子为x，它们遵循了一个简单的规律y=f(x)=(ax+b) mod INT32_MAX。
现在你已知：
f(0)=new Random(0).Next()=1559595546
f(1)=f(0)-1025583828 = f(0)+1121899819 mod INT32_MAX
f(2)=f(1)+1121899819 mod INT32_MAX
...
你很容易得出结论：
a = 1121899819
b = 1559595546
y = (1121899819 * x + 1559595546) % 2147483647
现在你可以进行一个验证：
ps> (1624687907L * 1121899819L + 1559595546) % 2147483647
6502
好了，我们现在有了一个非常简单且优化的正向公式。回到最初的问题，现在我们已知y去求x，该怎么做呢？
这个解不会很难获得，一个显而易见的方法，你可以执行x=range(0, 2^32-1)挨个试探一遍，总能找到满足要求的x。
（这句话是不是有点眼熟）
Too Naive! 这里我们就要借助离散数学的方法，来寻找另一个公式了。
如果你不懂离散数学，不要慌，我也不懂。实话实说，我也是现场向群友询问，然后群友给我发了这个链接：https://www.cnblogs.com/gonghr/p/14927783.html
总而言之，我们的问题其实简化成了这样一个方程：
1121899819 * x ≡ y - 1559595546 (mod 2147483647)
它刚好符合参考资料中的这一段：
我们使用excel，带入这些个参数，我们就可以计算出最重要的参数k和Tk
因为2147483647是质数，我们的目标rk=1，最后求得k=19时，Tk=350788151
现在我们知道，
1 = (-1)^18 * 2147483647L * 183260610 + (-1)^19 * 1121899819L * 350788151
所以
x = sb = -350788151 * (y - 1559595546) mod 2147483647 = (1559595546-y)*350788151 mod 2147483647
这就是最上面公式的来源。
杂谈
实际上，这个求解过程只是一种马后炮，我本身并没有走这条路，而是真的参考了coreRuntime源代码System/Random.Net5CompatImpl.cs进行了正向攻破。
因代码稳定性考虑，最新版本的.net依然对指定seed的随机数生成器使用了一种前向兼容的算法，仅对默认随机数生成器有不同的实现，所以我们只需考虑Net5CompatSeedImpl这个类。
它的内部实现为CompatPrng结构体，对seed初始化后会生成一个长度为56（事实上索引0未用）的随机数表，从InternalSample函数可以看出，Next()获得的第一个值固定为seedArray-seedArray，为了拿到简化正向公式，我只需要拿到seedArray和seed的关系即可。
这个公式并不好获取，我对Initialize方法进行了逐行阅读，发现它大概做了这样一系列工作：
[*]先用Φ-seed，赋值给seedArray。
[*]以(21*i)%55的索引顺序初始化seedArray，通项公式为(-1)^i * fib(i-1) * k + (-1)^(i-1) * fib(i)，因为是相邻项相减，这里构成了一个斐波那契序列乘一个交错级数。
[*]再进行4轮错位相减，得到最终初始化seedArray。
因为每一项都是一个和seed相关的线性表达式，两项求和差后依然是一个和seed相关的线性表达式，做完mod以后依然是一个和seed相关的不那么线性的表达式（总之有解析解），所以我们可以丧心病狂地算出来
seedArray=5446822953*(Φ-seed)-13882665879 mod INT32_MAX
seedArray=-14906113698*(Φ-seed)+20985462189 mod INT32_MAX
firstRand=1025583828*(Φ-seed)-508389716 mod INT32_MAX
= (-1025583828 * seed + 1025583828 * 161803398 - 508389716) mod INT32_MAX
展开括号并且把参数标准化，你依然可以得到 (1121899819 * seed + 1559595546) mod INT32_MAX这个解。
殊途同归。
结论
在安全敏感等特殊场合，你不应该使用这个Random类型生成随机数或随机序列，它很容易通过一个短序列逆推种子或推导未来生成的值。
对应地，你可以尝试使用System.Security.Cryptography.RandomNumberGenerator或其他密码学安全的随机数生成器作为替代。
Copyright
这是一篇原创文章，转载请注明作者和出处。
文中资料引用来源已标注链接。
页:
[1]