只有 3 个运算操作的解密函数，破解奖励一杯咖啡
周末写了一个非常简单的解密函数：将参数 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 ），暴力运算大概率会超时，因此需要一些数学技巧来优化。如果能找到优化方案，我再发一个新的测试~ x ^= x >> 32; 好像不是高低位交换。是高位不变，低位变成高低位的异或和 这是一个典型的伪随机数生成器（ PRNG ）性质的混淆算法。代码中乘上的常数 0xD1342543DE82EF95 是一个精心挑选的奇数，且循环次数高达 $10^{14}$ 次。直接暴力运行该程序需要消耗极长的时间（在单核上大约需要运行数天甚至数周），因此我们必须通过数学规律来寻找破绽。最终的运行结果是：x42961 。
这是 Gemini 推算的，不到 5 秒，结果不知道对不对？ 有人拿到结果了吗 Opus 的回答：
为什么常规方法都不行：
矩阵快速幂：操作不是单一线性结构下的线性，行不通
找环周期：状态空间 2^64 ，期望环长 ~10^19 步，找环本身比直接跑还慢
暴力 C++：单核约 46 小时（每步有严格数据依赖，无法 SIMD ），在我的执行环境里跑不完
只取低位：第二步把高 32 位流入低位，1 步后低 17 位就依赖全部 64 位输入，无法局部计算
如果你有几十核机器或愿意等几小时，可以用上面的 C++ 直接跑出来。如果题目预期能在合理时间内解出，那应该存在我没看出的代数结构（也许跟常数 0xD1342543DE82EF95 在某种环里的阶有关，这正是 SplitMix64 用的乘子）——但我没找到。
直接告诉你正确答案的话我会瞎编，所以宁愿如实说没解出来。如果你后来知道答案了，我也很想听听用的是什么思路。 好奇怪的初始值🐸 Opus 4.7 的答案：
我会怎么做（按推荐顺序）
1. 先怀疑题面：0xD1342543DE82EF95 是 SplitMix64 的乘数，而 SplitMix 这类混合器在 CTF 题里经常被搬到 GF(2) 上当作"伪 SplitMix"——出题人很可能心里想的就是无进位乘法（路 A
的代码直接出答案，几十微秒）。先把上一条回答的 CLMUL 矩阵快速幂代码跑一遍，看 x????? 和题目预期对不对得上。如果对得上——结案。
2. 如果题面就是要整数乘法：那这道题在我看来不存在 poly(log n) 的解。可选退路：
- 用 __int128 或 BMI 把内层循环写紧一点（已经够紧了，省不了多少）
- 上多机/云：分段不行（链式依赖），但你可以并行跑多个起点碰运气；不过本题只有一个起点，所以也没用
- 认命跑一天，或者租台 7-8 GHz 的高频机器（如 9950X3D / EPYC 调高频）压到 12-16 小时
3. 再试一招（成本低）：把 Floyd 龟兔跑 10^9~10^10 步看看，万一这个特定起点恰好掉进短循环（概率很低但代价小）。 我们没有发现可用的快速结构。
已检查的自然结构给出负面结果。
在伪随机置换假设下，跳步计算应当困难。
但无法严格证明不存在更快算法。
页:
[1]