从Nintendo密码挑战到乘法的直觉理解

· 2026-11-19 18:04 · 5 阅读

逆向大聪明 2026-11-19 18:04 上海

看雪论坛作者ID:逆向大聪明

几年前在CodinGame上遇到过一道没解出的题。最近再看到,思路阔然开朗,感慨颇多。

题目是一段简单代码,核心只有一行表达式(原题见附件):

READ Size
READ size / 16 integers in array a 
WRITE size / 16 zeros in array b
For i from 0 to size - 1:
    For j from 0 to size - 1:
        b[(i+j)/32] ^= ((a[i/32] >> (i%32)) & (a[j/32 + size/32] >> (j%32)) & 1) << ((i+j)%32)
PRINT b

输出 array b 为:

541a42315d324646 27219a26 12497b0e 724eddcb 0e131617 9521bedf 55544dc7

要求反推输出 array a

一些反思

一直觉得相关专业的教材,行文逻辑对新人极不友好。比如抽象代理中介绍RSA原理,开篇就是:

给定两个大素数 p 和 q

这不是在解释密码学原理,只是凭空给到的实现工序。如果诚心教学,应该从设计初衷讲起:

message encrypt = cipher

cipher decrypt = message

有了最简PoC之后 => 再披露安全缺陷 => 然后才有动机引入欧拉函数,而不是颠倒过来讲。至于AI,在稍复杂数学问题上的解释能力,更是惨不忍睹。

我们无法去改变行业现状,只能轮到自己写writes up的时候,更用心一点。

理解题面

ij 双循环即是二维平面,每个格子代表了第i列、第j行,直观来看代码逻辑就是在遍历棋盘。

不难看出,a[i/32] >> (i%32) 中的 i/32  代表了入参的第几个block、 i%32 代表了第几个block下的偏移量,合在一起就是在取整体入参序列的第 i 位(j同理)。

... & ... & 1 可以理解为取行、列值同时为1的格。

b[(i+j)/32] ^= ... << ((i+j)%32) ,可以理解为上述格在斜线上的求和(因为同一斜线中每个格子的 i+j 恒定)。

至此,我们对这段代码的几何意义有了直觉理解。接下来要做的就是配平这枚魔方。

寻找体系

几何理解只是一个锚点,他帮助我们产生进一步联想。看到这个纺锤状的图形,很容易回忆起小学时的乘法竖式。

我们列出 x3x2x1x0 * y3y2y1y0 的竖式,体会下

不难发现:末行的表达式恰好贴合本题的代码逻辑(只不过这里的加法需要重定义为不进位加法,即:异或)。

那么,这份代码本质上在做以下事情:

输出B = 输入A的前半段 x 输入A的后半段

至此,课题退化为已知公案:大数因数分解“易题”(与RSA的整数环分解不同,由于这里乘法不带进位,应属于伽罗瓦域运算)

路线选择

从这里开始,解题思路走到了一个关键的岔路口,摆在面前有两个方向。

方向 1. 解魔方

我认为本手就应该继续配平魔方,机制很明确:

  • 每拨动1位横坐标+1位纵坐标,会产生1个新增黑点,同时产生若干灰点(余数)。

  • 多个余数组合,又恰好产生新的黑点。

核心命题是如何在这套体系下,归纳出能独立扰动单格输出槽位的公式。这是人类最能直观理解的方向。

方向 2. 解因数

另外一种取巧的方向,是直接复用整数环上的因数分解攻击方案,在本题的语境下做合理外推。

套用既有公式得到端到端的答案,代价是丢失对计算过程的直觉理解。

碍于精力有限,我暂时选了方向 2。

但我们很难评判,鸡兔同笼的巧思,被解方程这种工具彻底取代后,到底是人类思想的进步还是退化。

我粗浅的理解是,数学只是人类对世界规律的有损压损,不是世界本身。如果不回归到生活经验,最终会走向歧途。

因数分解

从大家熟悉的RSA出发

因数分解问题主要有三个攻击方案(不考虑Shor算法)

  • Pollard Rho(差速指针)

  • 二次筛法

  • 数域筛法

理论上RSA的攻击方案,在重载操作符后,对本题都应该适用。

我最先尝试了 Pollard Rho,由于算法本身存在概率缺陷,解不了本题。

紧接着尝试二次筛法。在伽罗瓦域上确实存在一个与二次筛法思路接近的方案,即:Berlekamp算法。

让我们从零开始反推下Berlekamp算法的设计思路。

Berlekamp算法设计思路

目标

把 B 分解为 A1 * A2

第一感

如果我们想要地毯式搜寻 A1 * A2 这株独苗,命中概率显然小得可怜。有没有可能放宽条件呢?

可以尝试先找到A1的一个倍数,与B辗转相除求最大公约数,这样也能得出A1(平凡因子除外)

如此,问题从找A1,转变为找n倍的A1,靶面立刻被放大了无数倍。

这类倍数思想在素数领域很常见,所以最先容易联想到。比如最简单的判断素数方法,就是在自然数序列中,把2的倍数、3的倍数、4的倍数依次拉黑,那么剩余没人认领的数就是素数。

构造一个支点

但我们现在手上只有B,要怎么得到n倍的A1呢?

可以这样想:只要撞见两个数相乘的结果为B的整数倍,那么这两个数中必然有人持有一部分B的因数,这就是我们要找的“A1的倍数”。

为了简化运算,我们大胆使用两个相邻数来做尝试(选相邻数能享受到非常多便利属性,可选的尝试方案在实践中不是唯一的,此处不赘述)。

即:寻找满足以下等式的X

X(X-1) ≡ 0 (mod B)

群/环/域论中另一个极其高频的概念就是周期。定宽的二进制比特位,不断自增、溢出再从0开始,经常表现出惊人的轮回巧合。所以引入B的倍数几乎是必然。

纯粹的化简

构思有了,接下来就是初二基本功了

备注:本段所有运算,除2ⁿ为了书写简便保持在Z环,其余均转义到GF(2)。

原式:

 X(X-1) ≡ 0 (mod B)

乘法分配律:

 X²-X ≡ 0 (mod B)

把X二进制展开:

 (x₀2⁰ + x₁2¹ + x₂2² + ... + xₖ2ᵏ)² - (x₀2⁰ + x₁2¹ + x₂2² + ... + xₖ2ᵏ) ≡ 0 (mod B)

关键洞察:

以完全平方式为例,(x₀+x₁)² 展开后原本应为 x₀²+x₀x₁+x₀x₁+x₁²

1. 由于我们重载了“+”,此处x₀x₁+x₀x₁为异或操作,抵消之后剩余(x₀+x₁)²=x₀²+x₁²

2. 又由于x₀只能为0或1,那么x₀²恒等于x₀

因此 (x₀+x₁)² = x₀+x₁

所以原式的完全平方展开后为:

 (x₀2⁰ + x₁2² + x₂2⁴ + ... + xₖ2²ᵏ) - (x₀2⁰ + x₁2¹ + x₂2² + ... + xₖ2ᵏ) ≡ 0 (mod B)

加法交换律:

 x₀(2⁰-2⁰) + x₁(2²-2¹) + x₂(2⁴-2²) + ... + xₖ(2²ᵏ-2ᵏ) ≡ 0 (mod B)

乘法分配律:

 x₀((2⁰-2⁰) mod B) + x₁((2²-2¹) mod B) + x₂((2⁴-2²) mod B) + ... + xₖ((2²ᵏ-2ᵏ) mod B) = 0

表达式中固定的常数都可以提前计算完,即:

 x₀C₀ + x₁C₁ + x₂C₂ + ... + xₖCₖ = 0

由于x只能取0或1,所以二进制数C的每一位展开,可以得到如下方程组:

 x₀c₀₀ + x₁c₀₁ + x₂c₀₂ + ... + xₖc₀ₖ = 0

 x₀c₁₀ + x₁c₁₁ + x₂c₁₂ + ... + xₖc₁ₖ = 0

                             ...                       

 x₀cₖ₀ + x₁cₖ₁ + x₂cₖ₂ + ... + xₖcₖₖ = 0  

随机填入一组c值,体会下:

 1x₀ + 0x₁ + 1x₂ = 0

 0x₀ + 0x₁ + 1x₂ = 0

 0x₀ + 1x₁ + 1x₂ = 0

即:

 x₀ + x₂ = 0

        x₂ = 0

 x₁ + x₂ = 0

显然这是个k元线性方程组,高斯消元求解,时间复杂度O(n³)。

至此本题得解。

验证结果

a[0] =0xcafefeed;
a[1] =0xfeedf00d;
a[2] =0xf00dfeed;
a[3] =0xfeedd00d;
a[4] =0xc0def00d;
a[5] =0xfacef00d;
a[6] =0xfee1dead;
a[7] =0xfeedface;

依旧LeetSpeak风格短语:

cafe feed feed food food feed feed dood code food face food feel dead feed face

程序输出符合要求:

541a42315d324646 27219a26 12497b0e 724eddcb 0e131617 9521bedf 55544dc7
The program '/Users/steven.zhu/Documents/scripts/crypto-trial/nintendo/encrypt' has exited with code 0 (0x00000000).

Check mate !

后记

回顾整个解题过程,没有什么高深的东西,每一步都是自然反应。算法就是这样,经不起揭密的。

*本文为看雪论坛优秀文章,由 逆向大聪明原创,转载请注明来自看雪社区

图片

球分享

球点赞

球在看

点击阅读原文查看更多

阅读原文

跳转微信打开

本文转载自微信公众号「看雪学院」,查看原文。版权归原作者所有,如有侵权请联系删除。