找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 398|回复: 0

【.Net】System.Random伪随机数求逆实现

[复制链接]

3

主题

5

回帖

11万

积分

用户组: 技术宅的结界VIP成员

UID
8229
精华
2
威望
84 点
宅币
114704 个
贡献
80 次
宅之契约
0 份
在线时间
10 小时
注册时间
2023-2-9
发表于 2023-5-12 16:50:22 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
本帖最后由 Kagamia 于 2023-5-12 23:04 编辑

前情提要

我们群里有一个.net Roslyn repl BOT,只要你输入一个合法的C# Expression,它就会自动Eval返回结果。
现在群友想要整这么一个活:
  1. You> new Random(seed).Next()
  2. Bot> 6502
复制代码

那么这个seed应该填多少呢?
答案是:1624687907

这件事你可以在.net framework. net core .net 5+上随意验证,但不要在mono平台上做这件事。
按我对mono的有限理解,为了保证代码版权洁净,它们不允许反编译.net Framework的实现向mono代码库提交代码,所以它们的伪随机数生成器使用的是完全不同的实现。
  1. // ps5, ps core 6+
  2. (New-Object System.Random 1624687907).Next()
  3. // C# .net Framework, .net core, .net 5+
  4. Console.WriteLine(new Random(1624687907).Next());
复制代码


这个解不会很难获得,一个显而易见的方法,你可以执行seed=range(0, 2^32-1)挨个试探一遍,总能找到满足你要求的种子
更有甚者,你可以从微软那里拿到.net Framework的源代码,然后转写成c去做这件事。群友给了这样一个例子:https://pastebin.com/NwVqMswD

按你胃(anyway),我们似乎有了一个还不错的方案。但如果我们灵机一动,想让它生成今天的日期(20230512),那这个循环爆破可能耗时稍微有那么一丢丢久。
那么有没有一种算法,可以响应国家节能减排号召,降低时间与空间复杂度,一瞬间返回想要的种子呢?

答案是,有的。

我先给出结论,然后再慢慢解释:
  1. int InferenceSeed(int next) {
  2.   long n = 1559595546L - next;
  3.   if (n < 0) n += Int32.MaxValue;
  4.   return (int)((n * 350788151L) % Int32.MaxValue);
  5. }
复制代码

用这个算法可以求得,当输入种子为1775349364的时候,第一个随机数返回值为20230512。

如果你感兴趣它是怎么来的,那请继续看下去。

System.Random

.Net基础库内置了伪随机数生成器System.Random,从直觉上你一定认为它是基于线性同余算法。
即使你不去阅读那晦涩难懂的代码,你也可以通过一个小实验轻松验证出这件事:
  1. for(int seed=1;seed<=10;seed++)
  2.   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

现在你可以进行一个验证:
  1. ps> (1624687907L * 1121899819L + 1559595546) % 2147483647
  2. 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)

它刚好符合参考资料中的这一段:
QQ截图20230512154926.png

我们使用excel,带入这些个参数,我们就可以计算出最重要的参数k和Tk
QQ图片20230512160922.png
因为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[1]-seedArray[22],为了拿到简化正向公式,我只需要拿到seedArray和seed的关系即可。
这个公式并不好获取,我对Initialize方法进行了逐行阅读,发现它大概做了这样一系列工作:
  • 先用Φ-seed,赋值给seedArray[55]。
  • 以(21*i)%55的索引顺序初始化seedArray,通项公式为(-1)^i * fib(i-1) * k + (-1)^(i-1) * fib(i),因为是相邻项相减,这里构成了一个斐波那契序列乘一个交错级数。
  • 再进行4轮错位相减,得到最终初始化seedArray。

因为每一项都是一个和seed相关的线性表达式,两项求和差后依然是一个和seed相关的线性表达式,做完mod以后依然是一个和seed相关的不那么线性的表达式(总之有解析解),所以我们可以丧心病狂地算出来
  seedArray[1]=5446822953*(Φ-seed)-13882665879 mod INT32_MAX
  seedArray[22]=-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

这是一篇原创文章,转载请注明作者和出处。
文中资料引用来源已标注链接。
回复

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-28 19:41 , Processed in 0.036128 second(s), 33 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表