只有 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 又算了一遍

[YYDC]

x75573

[i67c6NJ0r33nC667]

有人拿到结果了吗

[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.