只有 3 个运算操作的解密函数，破解奖励一杯咖啡

[iqoo]

周末写了一个非常简单的解密函数：将参数 x 乘以一个常数，然后高低位置换，重复 n 次。

代码：

#include <cstdint>
#include <iostream>

uint64_t solve(uint64_t x, uint64_t n) {
    while (n--) {
        x *= 0xD1342543DE82EF95;
        x ^= x >> 32;
    }
    return x;
}

int main() {
    uint64_t result = solve(11451419260817, 1e14);
    std::cout << "x" << result % 100000 << "\n";
    return 0;
}

结果是支付宝口令红包，最先破解者奖赏一杯咖啡☕️。（明天 11 点过期）

⚠️ 上述代码大约需运行一天时间（ 5GHz ），暴力运算大概率会超时，因此需要一些数学技巧来优化。如果能找到优化方案，我再发一个新的测试~

[CapNemo]

x ^= x >> 32; 好像不是高低位交换。是高位不变，低位变成高低位的异或和

[kchanlee43]

x72901

[zizon]

The key mathematical insight: the mod 100000 sequence must repeat within ≤100001 steps (only 10⁵ possible values). Found cycle starting at step 248, length 14. Then:

n = 10¹⁴ → idx = 248 + (10¹⁴ − 248) mod 14 = 254
Only 254 iterations needed instead of 10¹⁴
Answer: x99826


deepseek v4 flash ~ 23min
126,935 (126,656 prompt tokens + 279 completion tokens)

[godall]

这是一个典型的伪随机数生成器（ PRNG ）性质的混淆算法。代码中乘上的常数 0xD1342543DE82EF95 是一个精心挑选的奇数，且循环次数高达 $10^{14}$ 次。直接暴力运行该程序需要消耗极长的时间（在单核上大约需要运行数天甚至数周），因此我们必须通过数学规律来寻找破绽。最终的运行结果是：x42961 。

这是 Gemini 推算的，不到 5 秒，结果不知道对不对？

[godall]

@godall 这段代码的核心就在于它保留了低位对高位的单向依赖，也就是说，低 $k$ 位（ x 的低位）的演变完全不受高位的影响。
1. 为什么只要关注低 17 位？题目最后要求输出的是 result % 100000 。因为 $100000 < 2^{17} = 131072$，所以我们只需要准确知道最后结果的低 17 位，就能完美计算出它模 100000 的余数。

[iqoo]

@CapNemo 是置换（ xorshift ），不是交换。

@kchanlee43 AI 算出来的都是这个结果~

[iqoo]

@zizon
@godall 把次数改小点，比如 1e10 ，十秒钟就可以验证 AI 的答案对不对。

[msg7086]

@zizon 想想就知道不对，mod 100000 怎么可能说明循环节小于 100001 呢，函数输入又不是 mod 完的数。

[godall]

@iqoo 59985 ？ Gemini 又算了一遍

[Haolijia1107]

x75573

[409164]

有人拿到结果了吗

[iqoo]

@godall 我的 Gemini 这样回复的：

因为代码交替使用了两种互不兼容的数学运算：

整数乘法：在二进制位运算看来是非线性的（因为存在“进位”）。

异或移位：在普通代数乘法看来也是非线性的。

这种交替混合彻底破坏了代数规律（密码学中称为“混淆”），导致无法推导出任何可以直接跳过循环的通项公式。每一次迭代都严格依赖上一步的结果，除了老老实实硬算，没有任何数学捷径。

[godall]

@iqoo 你提到的这种混合运算，在密码学中有一个专门的称呼——ARX 架构（ Addition, Rotation, XOR ）或其变体。你说的完全正确：从严格的全局代数逻辑来看，这个算法是不存在任何可以跨越任意步数的“通用闭式解”（通项公式）的。我此前尝试去寻找纯代数通项公式（试图通过周期律直接跳过 $10^{14}$ 步），这在数学上确实是不可能的，因为进位和异或的混合会迅速让位与位之间的关系变成高度非线性的多项式，产生所谓的雪崩效应。💡 为什么在这里纯“硬算”行不通，但“降维”能抓到耗子？既然你提到的“混合运算破坏了代数规律”完全成立，那为什么我们最后依然能通过 (1014) % 4 这种降维的方法精确锁定最后的 5 位数（ 59985 ）呢？
计算机一本正经的胡说八道起来，人类实在不是对手，我也不知道它说的对还是错。

[vincentWdp]

好奇怪的初始值🐸

[zizon]

@iqoo 既然你说 n 这个强度值是可替换的.
那么 n=0 应该也是等价的.

说明你也根本没有一个快捷算法能够算出来.

[zhongzhaoguo]

Opus 的回答：
为什么常规方法都不行：

矩阵快速幂：操作不是单一线性结构下的线性，行不通
找环周期：状态空间 2^64 ，期望环长 ~10^19 步，找环本身比直接跑还慢
暴力 C++：单核约 46 小时（每步有严格数据依赖，无法 SIMD ），在我的执行环境里跑不完
只取低位：第二步把高 32 位流入低位，1 步后低 17 位就依赖全部 64 位输入，无法局部计算

如果你有几十核机器或愿意等几小时，可以用上面的 C++ 直接跑出来。如果题目预期能在合理时间内解出，那应该存在我没看出的代数结构（也许跟常数 0xD1342543DE82EF95 在某种环里的阶有关，这正是 SplitMix64 用的乘子）——但我没找到。
直接告诉你正确答案的话我会瞎编，所以宁愿如实说没解出来。如果你后来知道答案了，我也很想听听用的是什么思路。

[EggtartZ]

Opus 4.7 的答案：

我会怎么做（按推荐顺序）
1. 先怀疑题面：0xD1342543DE82EF95 是 SplitMix64 的乘数，而 SplitMix 这类混合器在 CTF 题里经常被搬到 GF(2)[x] 上当作"伪 SplitMix"——出题人很可能心里想的就是无进位乘法（路 A
的代码直接出答案，几十微秒）。先把上一条回答的 CLMUL 矩阵快速幂代码跑一遍，看 x????? 和题目预期对不对得上。如果对得上——结案。

2. 如果题面就是要整数乘法：那这道题在我看来不存在 poly(log n) 的解。可选退路：
- 用 __int128 或 BMI 把内层循环写紧一点（已经够紧了，省不了多少）
- 上多机/云：分段不行（链式依赖），但你可以并行跑多个起点碰运气；不过本题只有一个起点，所以也没用
- 认命跑一天，或者租台 7-8 GHz 的高频机器（如 9950X3D / EPYC 调高频）压到 12-16 小时

3. 再试一招（成本低）：把 Floyd 龟兔跑 10^9~10^10 步看看，万一这个特定起点恰好掉进短循环（概率很低但代价小）。

[wubajie]

我们没有发现可用的快速结构。
已检查的自然结构给出负面结果。
在伪随机置换假设下，跳步计算应当困难。
但无法严格证明不存在更快算法。

[iqoo]

@zizon 是的，我也是完整跑了一天算出来的。目前当做离线计算的 VDF 。

[Mohanson]

密码学爱好者, 说一下这个算法的漏洞

这看起来是一种类似线性同余的伪随机数算法, 正规 LCG 第二步是 x = x + c(常量); 你发明的算法第二步是 x ^= x >> 32, 这会引入一个问题, 就是会有零值问题.

在 x ^= x >> 32 这一步, 如果 x 是 0x00000000ffffffff, 那么结算的输出 x 也是 0x00000000ffffffff, 这会导致进入纯乘法循环, 也就是这个函数会塌缩到一个乘法循环的周期再也出不去.

如果综合看 "x *= 0xD1342543DE82EF95; x ^= x >> 32;" 两步, 当 x 初始值为 0 时, 结算结果也为 0, 会进入更加明显的乘法循环周期(零值黑洞), 也就是说一旦你的某一步的计算结果是 0x00000000ffffffff 或者 0, 要么进入周期要么进入零值黑洞.

简单的说, 虽然没法一眼看出来 solve(11451419260817, 1e14) 的值是多少, 但有 99.9999% 的把握告诉你 solve(11451419260817, 1e140); 的结果是 0.

我来做的话, 我首先想到的是找这个算法的周期; 只要知道了周期就能得到任意步的结果了. 然后下一步是翻文献, 因为这个算法与 LCG 算法如此雷同, 当年大概率有文献告诉你这个算法为什么不行, 业界为什么选择了 x = x + c 而不是 x ^= x >> 32.

[CapNemo]

至少 2 亿步以内无环

[CapNemo]

以及不会是 0 ，这个运算是可逆的，0 在一个单独的环里

[CapNemo]

@CapNemo #22 那这还意味着所有环都是简单环，不存在 p 形的结构

[csfreshman]

claude code 消耗了 30%的 current session
我把这个程序仔细看完了。结论先说在前面：这段程序在合理时间内无法得到精确结果，下面解释原因。
程序在做什么
这是一个 PCG 风格的状态更新，迭代函数为

f(x)=S(K⋅x mod 264),S(y)=y⊕(y≫32)f(x) = S(K \cdot x \bmod 2^{64}),\quad S(y) = y \oplus (y \gg 32)f(x)=S(K⋅xmod264),S(y)=y⊕(y≫32)
其中 $K = $ 0xD1342543DE82EF95 ，这是 L'Ecuyer / Steele 给出的一个 2642^{64}
264 模数下的优质 MCG 乘子，也是 PCG 库里实际使用的乘子之一。
初始种子 $x_0 = $ 11451419260817 （=0xA6A3DC6F791 ，是个中日互联网梗号），迭代 N=1014N = 10^{14}
N=1014 次。
为什么算不出来
1. 直接模拟需要约 52 小时单核 CPU 时间。
内层循环的关键依赖链是 imul(3 周期) → shr(1) → xor(1) = 每次迭代 5 个时钟周期。我实测在 2.8 GHz 的 Xeon 上跑出 1.64 ns/迭代，已经接近这个理论下限。这条依赖链是串行的，下一次迭代的输入是上一次的输出，SIMD 用不了，多核也用不了。

[Mohanson]

@CapNemo 是的, 我再想了一下, 楼主这个函数会把 2^64 分割成无数孤立的环, 0 是其中一个环, 并非所有计算结果都会落入 0 值黑洞. 但可以确定的是这些孤立环的周期远远小于 2^64.

[Mohanson]

@Mohanson 反对这个回答.

虽然楼主的修改让随机数的质量和周期暴跌, 但有个好处是 x ^= x >> 32 是非线性的, 这让所有线性分析的数学工具都不再可用, 也就是我猜测这个算法短期内不存在可以快速计算的方案; 但是如果放宽时间, 只要成功暴力破解一次那整个算法就完全崩溃了.

[codingmiao]

这玩意真能作为加解密方法吗？即使明天你把答案发出来，也没有一个快速验证的方法验证你发的答案对不对。反之如果你有快速验证的方法并公布出来，那这个加解密方法也会像 MD5 彩虹表那样迅速被破解掉

[iqoo]

@codingmiao 目标不是用来加解密。用来证明客户端执行了一定的 CPU ，并且不可多线程加速。（题目可以用 GPU 离线出。校验时查表即可）

[iqoo]

@Mohanson 实际使用的时候算法不固定，会随机混合多个运算（例如乘法、位运算等），题目本身也是一个参数，有点类似 RandomX 的思路。本帖子只是其中一个案例。实际的题目是一段动态的 wasm 的字节码。

[tengxun]

单从这个迭代函数本身看，最小破解步骤就是完整串行迭代。

[ExplodingDragon]

@iqoo #29 所以这是打算利用 wasm 嵌入到浏览器做 PoW 来对抗爬虫或者其他自动化工具 ?

[ExplodingDragon]

顺便贴一下使用 chatgpt pro 的结果 , 无法跳步或 SIMD 就没继续看了 （：

这段原始代码不能直接用“常数快速幂”或“矩阵快速幂”跳过 1e14 轮。关键原因是：x ^= x >> 32 不是高低 32 位交换，而是把高 32 位异或进低 32 位；它虽然可逆，但和普通整数乘法的进位混在一起后，整体既不是模 2^64 乘法，也不是 GF(2) 线性变换。

设 B = 2^32 ，C = 0xD1342543DE82EF95 = aB + b ，x = hB + l 。一轮乘法后：

```
L = b*l mod B
H = b*h + a*l + floor(b*l / B) mod B
```

随后：

```
T(h, l) = (H, L xor H)
```

问题就在这里：H 里有整数乘法进位 floor(b*l / B)，而低位又用了 xor 。这会把“模加/乘”的结构和“GF(2) 异或线性”的结构打碎。

一个很小的反例就能排除快速幂假设：

T(1) = 0xd13425430fb6cad6
T(2) = 0xa2684a871f6d95ad

如果它等价于某个常数乘法 T(x)=Kx mod 2^64 ，那么应有：

```
2*T(1) mod 2^64 = 0xa2684a861f6d95ac
```

但实际 T(2) 多了 0x100000001 。这就是进位和异或混合造成的偏差。

同样，它也不是 GF(2) 线性的：

```
T(1 xor 2) != T(1) xor T(2)
```

所以这类写法都不成立：


```
// 错：只能用于纯乘法状态转移
x *= pow_mod(C, n, 2^64);

// 错：只能用于真正的 GF(2) 线性 xorshift
matrix_pow(M, n) * x;
```

这个常数本身确实是常见的 64 位 LCG/LXM 乘子； OpenJDK 相关实现也把 0xd1342543de82ef95 用作 LCG 乘子并说明其谱测试分数。也就是说，如果状态转移只是 LCG 乘法/加法，它能快进；但你这里把 mix 结果反馈回状态了，结构就变了。

[iqoo]

@ExplodingDragon 是的。比串行 sha256 简单多了，而且 wasm 和 native 性能差不多（损耗 2% 左右）。

[zisen]

@iqoo 看着好像 solana

[yolee599]

如果别人算出来了一个结果，你怎么快速验证呢？验证不了也没意义

[iqoo]

@yolee599 能领取成功就是正确🐶