题目是一段简单代码,核心只有一行表达式(原题见附件):
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 为:
541a4231 5d324646 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
程序输出符合要求:
541a4231 5d324646 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 !
后记
回顾整个解题过程,没有什么高深的东西,每一步都是自然反应。算法就是这样,经不起揭密的。

看雪ID:逆向大聪明
https://bbs.kanxue.com/user-home-835839.htm

# 往期推荐
一台"锁死"的 Pixel 7 自救记:把 GhostLock 内核漏洞移植到真机 root
Unreal Engine 4引擎基础及其2024第九届游戏安全竞赛-初赛-安卓客户端安全为例
Android MetaSec 签名链逆向:从 TTNet 到 Unidbg Native 还原


球分享

球点赞

球在看

点击阅读原文查看更多
