解析视频地址：https://www.bilibili.com/video/BV16i4y1d7g6/

此题没有反调试，只有一定的混淆。

对于初级参赛者，需要对抗本题的混淆。

对于中级参赛者，需要熟悉平方剩余算法。

对于高级参赛者，需要发现并修复CrackMe中的bug。

出题团队在赛前发布了一部情感短视频，并将解题思路隐藏于其中。赛后又发布了一部解析视频，深入讲解了破解方法。

作为第一个配短视频的CTF赛题，此题出题思路别致，视频制作专业，是一个有里程碑意义的CTF赛题！

截至比赛结束，此题共计围观人数：1957人，攻破战队数：4。

分别是：金左手、中娅之戒、mininep、辣鸡战队。从围观人数来看，此题吸引了不少参赛成员。特意为CTF赛题制作高水准的配套微电影还是头一次见吧！这不，解析版的视频也为大家奉上啦～

《生命的馈赠》出题视频：https://www.bilibili.com/video/bv1Uh411s7u4

出题团队简介

第十题《生命的馈赠》出题方：【GRAFFINDOR】战队。

【GRAFFINDOR】战队成员如下：

赛题设计思路

题目设计说明：防守有两部分，程序代码混淆和数学保护。

一、混淆

1、代码乱序处理

行与行之间加入jmp，通过jmp衔接每一行代码。

定义：定义了一个结构体管理每行代码，结构体如下。

struct CodeLineToExpand{OrderType m_Type;//原来代码的类型Param1;Param2;OldAddr;  //原来代码的地址OldAddrToJmpOrCall;//原来代码中要跳转的目标地址OldIndexValue;NewSize;//已经加入了远相对jmp后的大小NewAddr;NewAddrToJmpOrCall;RamdomValue;//随机值NewCode;//新的代码}CTE[nCodeLines];int MapNewToOld[nCodeLines];//存储新的Line和旧的Line之间的对应关系int CodeLineOldAddrBegin;//原来代码地址的开始int CodeLineOldAddrEnd;//原来代码地址的结束（不包含本地址）

步骤：

（1）将某一行代码nCodeLines的原始信息填入CTE数组。
计算出nCodeLines，填好CTE数组的每个元素的m_Type、Param1、Param2、OldAddr、OldAddrToJmpOrCall、OldIndexValue。

（2）对CTE每个元素赋予随机值，以该随即值的从小到大顺序重新组合代码。
计算出随机值填入RamdomValue，然后以此排序，排序后的结果放入MapNewToOld数组。

MapNewToOld数组按照索引顺序（NewIndex）来放置OldValue的值，顺序为从小到大。

（3）某行代码新地址的计算方法（CTE: NewAddr）
遍历MapNewToOld数组，除去第0个，每个元素对应的CodeLineToExpand结构体的NewAddr都为前面的元素CodeLineToExpand结构体的NewAddr+NewSize。

（4） 新CodeLine中的远相对跳转中相对地址的计算方法
遍历CTE数组，找它下一个元素的NewAddr配合自己的NewAddr进行计算。

（5）新的jmp\call目标地址的计算方法（假设源代码仅为代码，不做它用，且代码为Jmp或者Call）

相对跳转的修正：若原来代码要跳转的地址not in [CodeLineOldAddrBegin,
CodeLineOldAddrEnd]中，则用NewAddr和OldAddrToJmpOrCall进行修正；反之，寻找原来代码跳转地址对应的CodeLineToExpand，用NewAddr和原来代码跳转地址对应的CodeLineToExpand中的NewAddr进行修正。

绝对跳转的修正：若原来代码要跳转的地址not in [CodeLineOldAddrBegin,
CodeLineOldAddrEnd]中，则不需要修正；反之，寻找原来代码跳转地址对应的CodeLineToExpand，原来代码跳转地址对应的CodeLineToExpand中的NewAddr进行修正。

2、初步替换jmp指令

按长度分为9种。

// 第一种  长度：6push Addrret// 第二种  长度：0x1Cpush eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eaxret// 第三种1 长度：0xCmov dword ptr[esp-4],Addrjmp[esp - 4]         // 第三种2 长度：Cmov dword ptr[esp-4],Addrsub esp,4ret// 第四种  长度：0x2Dpush eaxmov dword ptr[esp-4],Addrmov eax,[esp-4]mov [esp-8],eaxsub esp,4mov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxmov eax,[esp]add esp,8   //add esp,4jmp [esp-4] //ret// 第五种  长度：0x34push Addrpush eaxmov eax,Addrmov eax,[esp]//push eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eax//add esp,4pop eaxadd esp,4jmp [esp-4]// 第六种（4+5） 长度：0x86push Addrpush eaxmov eax,Addrpush eaxmov dword ptr [esp-4],Addrmov eax,[esp-4]mov [esp-8],eaxsub esp,4mov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxmov eax,[esp]add esp,8   //add esp,4mov eax,[esp]push eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]push eaxmov dword ptr[esp-4],Addrmov eax,[esp-4]mov [esp-8],eaxsub esp,4mov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxmov eax,[esp]add esp,8   //add esp,4mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eaxadd esp,4pop eaxadd esp,4jmp [esp-4]// 第7种  长度：0x59push Addrpush 0x7FFA08ACjmp [esp]nopnopnopnopnopnopnopnopnopnopnopnopnoppush ebpmov ebp,espadd esp,-34push ebxpush ecxpush eaxpush esipush edilea edi,[ebp-34h]mov ecx,Dmov eax,0x0CCCCCCCCrep stos dword ptr [edi]mov [ebp-4],ecxmov eax,[ebp+8]mov edx,dword ptr [esp+4]mov ecx,dword ptr [esp+8]mov dword ptr [ebp-30h],1mov edx,dword ptr [ebp-30h]mov dword ptr [ebp-34h],edxmov ecx,[ebp-4h]pop edipop esipop eaxpop ecxpop ebxleaveret// 第8种  长度：0x42pushfdpush eaxmov eax, 4mul eaxlea eax, [4 * eax]mov[esp - 4], eaxmov eax, 4shl eax, 4sub eax, 4sub[esp - 4], eaxmov eax, [esp - 4]sub eax, 4mov[esp - 4], eaxpop eaxjne $ + 0x13call $+5add dword ptr [esp],0x13mov eax,[esp+4]mov [esp-4],eaxpopfdadd esp,4mov dword ptr[esp - 4], Addrsub esp, 4ret// 第9种（7+8） 长度：0x99// 第10种 长度：0x46pushfdpush eaxxor eax,Addrxor eax,64test eax,eax//push eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eaxadd esp,4//xor eax,64xor eax,[esp]push eaxadd esp,8popfdsub esp,8pop eaxpop [esp-4]jmp [esp-C]7FFBDD3B pushfd + retn7FFAF6DF popfd + retnaddreaxfd

3、通过计算得出jmp的目标地址

有8种计算方式，以长度区分。

// 第1种 长度：0x2dpushfd\npush eax\npush $1\nadd dword ptr[esp], $2\nshl dword ptr[esp], $3\nxor dword ptr[esp], $4\nadd dword ptr[esp], $5\nxchg eax,[esp]\nxchg eax,[esp+8]\nxchg eax,[esp]\npopfd\npop eax\nret // 第2种 长度：0x31push eax\nmov eax, $1\nlea eax, [eax + $2]\npush eax\nmov[esp - 4], eax\nmov eax, [esp + 4]\nmov[esp], eax\nmov eax, dword ptr[esp - 4]\npushfd\nshl eax, $3\nadd eax, $4\nxor eax, $5\npopfd\nmov[esp + 4], eax\npop eax\nret// 第3种 长度：0x2fpushfd\npushfd\nadd esp,8\nmov dword ptr[esp - 4], $1\nshl dword ptr[esp - 4], $2\nadd dword ptr[esp - 4], $3\nxor dword ptr[esp - 4], $4\nadd dword ptr[esp - 4], $5\nsub esp, 8\npopfd\nret// 第4种 长度：0x65pushfd\npush eax\nmov dword ptr[esp - 4], $1\nmov eax, [esp - 4]\nmov[esp - 8], eax\nsub esp, 4\nshl dword ptr[esp - 4], $2\nmov eax, [esp + 4]\nadd dword ptr[esp - 4], $3\nmov dword ptr[esp], eax\nmov eax, [esp - 4]\nmov[esp + 4], eax\nmov eax, [esp]\nmov [esp-8],eax\nadd dword ptr[esp + 4], $4\nxor dword ptr[esp + 4], $5\nmov eax,[esp+4]\nmov [esp-8],eax\nlea esp, [esp + 8]\npopfd\nlea esp,[esp-4]\nmov eax,[esp-4]\nmov [esp],eax\nmov eax,[esp-8]\nret// 第5种 长度：0x5dpushfd\npush $1\npush eax\nmov eax, $2\nmov eax, [esp]\nshl dword ptr[esp + 4], $2\npush eax\nmov eax, 1\npush eax\nmov[esp - 4], eax\nmov eax, [esp + 4]\nmov[esp], eax\nmov eax, [esp - 4]\nmov[esp + 4], eax\npop eax\nxor dword ptr[esp + 8], $3\nadd esp, 4\nmov eax, $4\nadd eax, $5\nadd dword ptr[esp + 4], eax\npop eax\nadd esp,4\npopfd\nlea esp,[esp-4]\nmov eax,[esp-4]\nmov [esp],eax\nmov eax,[esp-8]\nret// 第6种 长度：0x82push $1\npush eax\nmov eax, edi\npush eax\npushfd\npushfd\npushfd\nadd esp, 0ch\nmov dword ptr[esp - 4], $3\nmov eax, [esp - 4]\nmov[esp - 8], eax\nsub esp, 4\nmov eax, [esp + 4]\nmov[esp], eax\nmov eax, [esp - 4]\nmov[esp + 4], eax\nmov eax, [esp]\nadd esp, 8\nmov eax, [esp]\nxor eax, [esp]\nmov eax, [esp + 4]\nadd eax, $2\nxor eax, $3\nmov[esp + 4], eax\npush eax\nmov eax, $4\npush eax\nmov[esp - 4], eax\nmov eax, [esp + 4]\nmov[esp], eax\nmov eax, [esp - 4]\nmov[esp + 4], eax\npop eax\nadd esp, 4\npop eax\nshl dword ptr[esp], $4\nadd dword ptr[esp], $5\nsub esp,14h\npopfd\nlea esp,[esp + 10h]\nret// 第7种 长度：0x98push $1\npush eax\nmov eax, $4\npush eax\nmov[esp - 4], eax\nmov eax, [esp + 4]\nmov[esp], eax\nmov eax, [esp - 4]\nmov[esp + 4], eax\npop eax\nlea esp, [esp + 4]\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\npush ebp\nmov ebp, esp\nlea esp, [esp - 34h]\npushfd\npush ebx\npush ecx\npush eax\npush esi\npush edi\npush edx\nlea edi, [ebp - 34h]\nmov ecx, 0xD\nmov eax, 0x0CCCCCCCC\nrep stos dword ptr[edi]\nmov[ebp - 4], ecx\nmov eax, [ebp + 8]\nmov eax, ebp\nmov edx, dword ptr[esp + 4]\nmov ecx, [eax + 4]\nadd ecx, $2\nxchg ecx, edx\nmov ecx, dword ptr[esp + 8]\nmov dword ptr[ebp - 30h], 1\nadd edx, $3\nshl edx, $4\nmov ecx, edx\nmov edx, dword ptr[ebp - 30h]\nxor ecx, $5\nlea ebx, [eax + 4]\nmov dword ptr[ebp - 34h], edx\nmov [ebx], ecx\nmov ecx, [ebp - 4h]\npop edx\npop edi\npop esi\npop eax\npop ecx\npop ebx\npopfd\nleave\nret// 第8种 长度：0xafpushfd\npush $1\npush eax\npush edx\nmov eax, 4\nmul eax\nlea eax, [4 * eax]\nmov[esp - 4], eax\nmov eax, 4\nshl eax, 4\nsub eax, 4\nsub[esp - 4], eax\nmov eax, [esp - 4]\nsub eax, 4\nmov[esp - 4], eax\npop edx\npop eax\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\nnop\npush ebp\nmov ebp, esp\nadd esp, -34h\npush edx\npush ebx\npush ecx\npush eax\npush esi\npush edi\nlea edi, [ebp - 34h]\nmov ecx, 0xD\nmov eax, 0xCCCCCCCC\nrep stos dword ptr[edi]\nmov[ebp - 4], ecx\nmov eax, [ebp + 8]\nmov edx, dword ptr[esp + 4]\nmov ecx, dword ptr[ebp + 4]\ntest edx, 3\nlea ebx, [ebp + 8]\nmov dword ptr[ebp - 30h], 1\nmov edx, ecx\nxor edx, $2\nshl edx, $3\nmov eax, edx\nmov edx, dword ptr[ebp - 30h]\nmov dword ptr[ebp - 34h], edx\ncmp dword ptr[ebp - 34h], 0\nadd eax, $4\nadd eax, $5\n

4、替换后的代码进行拆分成块 

拆分的方法和步骤0一致，相当于做二次处理。

5、为了降低拆分后代码的规律性，引入了无效的代码片段 

四种片段，随机填充。

1、长度 58push ebpmov ebp, esplea esp, [esp - 34h]push ecxpush edxpush ebxpush esipush edipushfdmov edi, fs: [30h]lea edi, [edi + 8h]mov edi, [edi]lea ebx, [ebp]mov ecx, edixchg edx, [ebp]add ecx, 3chmov ecx,[ecx]add edi, ecxcall $ + 5pop ecxlea edi,[edi + 74h]lea ecx,[ecx + 29h]sub ebp, 4mov[ebp], edxlea ebx,[ebp]mov[ebx + 4], ecxcmp edi, 12hje $ - 55hpopfdpop edipop esipop ebxpop edxpop ecxleaveretnopnopnopnopnopnopnop        2、长度 21push ebpmov ebp,espsub esp,-34hpushadmov edi,fs:[30h]lea edi,[edi+8h]mov edi,[edi]mov eax,edilea eax,[4*eax]push eaxpop edipopadleave3、长度 21mov edi,edipush ebpmov ebp,esplea esp,[esp-22h]mov dword ptr [ebp-4h],ecxmov dword ptr [ebp-8h],ecxmov dword ptr [ebp-ch],ecxmov dword ptr [ebp-1ch],ecxmov esp,ebppop ebpjmp $+8nopnopnop4、长度 42call $ +0x2Emov eax, eaxcall $ +0xBmov eax, eaxlea esp, [esp + 12]lea esp, [esp + 10h]mov eax, eaxmov eax, eaxcall $ +0x24mov eax, eaxmov eax, eaxcall $ +0x14mov eax, eaxlea esp, [esp - 4]call $ -0xDmov eax, eaxmov eax, eaxcall $ -0x30mov eax, eaxlea esp, [esp + 8h]5、长度 42call $ +0x2Emov eax, eaxcall $ +0x37mov eax, eaxlea esp, [esp + 12]lea esp, [esp + 10h]mov eax, eaxmov eax, eaxcall $ +0x24mov eax, eaxmov eax, eaxcall $ +0x14mov eax, eaxlea esp, [esp - 4]call $ -0xDmov eax, eaxmov eax, eaxcall $ -0x30mov eax, eaxlea esp, [esp + 8h]

二、数学保护

数学公式（逆运算）：((format(Serial) ^2 mod P) * A + B) mod P) ^2 mod P = MD5(name)

参数：

验证：
(((S^2 Mod P) * A + B) Mod P) ^2 Mod P = N 满足该式子则成功。

破解思路：

1、把无效的代码片段替换为空，去除垃圾代码，保留有效代码。
2、去除拆分后成块的代码中的jmp，将代码块整合成有序代码。
3、通过trace找出最终跳转地址的计算模板，然后通过文本处理计算出地址进行替换。
4、处理乱序：通过trace跟踪出执行乱序的代码，截获原始地址进行处理。

赛题解析

一、分析篇

代码被混淆了。

混淆规律：6个call之后，类似下面这样平衡堆栈的指令下面一条，就是真实指令。

lea     esp, dword ptr ss:[esp+0x14]lea     esp, dword ptr ss:[esp+0x8]

二、逆向篇

输入预设的 name/serial，内存访问断点，返回到这里。

0043D6E1    51              push    ecx0043D6E2    E8 82FAFDFF     call    0041D169 ; 获取serial0043D6E7    68 80B57D1F     push    0x1F7DB580 ; 这里能看到name/serial0043D6EC    89DB            mov     ebx, ebx0043D6EE    50              push    eax0043D6EF    89E4            mov     esp, esp0043D6F1    B8 1D000000     mov     eax, 0x1D0043D6F6    90              nop

然后serial比较长度，必须是32字节：

00466750    5D              pop     ebp00466751    83F8 20         cmp     eax, 0x20                                       ; 比较长度00466754    9C              pushfd

单步到这：

004DD1DE   C785 00FFFFFF 7>mov   dword ptr ss:[ebp-0x100], 0x10325476 ；md5初始化

看看内存中：

0019FD38  01 23 45 67 89 AB CD EF FE DC BA 98 76 54 32 10  #Eg壂惋簶vT2

猜测是md5算法，但此时内存中已经出现了正确的md5值：

0019FDC4  F4 D5 16 EF CE 55 11 93 B6 6E E1 68 26 51 5A 4F  粽镂U摱n醜&QZO

这正好是name（1A5FBFD826E1D12E）的md5值，所以，这里应该是serial逆推回去算出来的，改一个字节会发现验证错误。

重新分析，发现这个call是关键：

004C4F17    E8 8840F7FF     call    00438FA4  ; 验证call，ecx = name, edx = serial004C4F1C    68 66757D1C     push    0x1C7D7566 ; 这里验证完毕， al = 1 成功， al = 0 失败004C4F21    50              push    eax

0049BFAE    B8 F8414000     mov     eax, 004041F8                              ; ASCII "验证正确\n"0049BFB3    9C              pushfd0049BFB4    89E4            mov     esp, esp0049BFB6    9C              pushfd0049BFB7    89DB            mov     ebx, ebx

004CA73A    8D6424 08       lea     esp, dword ptr ss:[esp+0x8]004CA73E  ^ 0F85 BE38FAFF   jnz     0046E002                                   ; 爆破点，jmp，验证成功004CA744    68 BAEB7025     push    0x2570EBBA

call 438fa4004318D5    81EC 28010000   sub     esp, 0x128

这里提升堆栈空间，可以直接清0堆栈，看看堆栈会出现哪些变量。

0043E967                      8D6424 14                               lea     esp, dword ptr ss:[esp+0x14]0043E96B                      E8 A3B90900                             call    004DA313 ; 似乎是 string to bignum0043E970                      9C                                      pushfd

004C0B29                      89C0                                    mov     eax, eax004C0B2B                      8D6424 14                               lea     esp, dword ptr ss:[esp+0x14]004C0B2F                      E8 D059F9FF                             call    Mul ; 这里似乎是 pow2 004C0B34                      9C                                      pushfd

456504这个函数，传入2个参数（eax, ecx) ，传出1个参数（[esp+4]）。

执行完看输出地址，这个正好是：

EEA43B9D52515B49838AFAA50490DA0B * EEA43B9D52515B49838AFAA50490DA0B = DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC790019FDA4  79 BC 16 5E F4 66 87 22 E2 0E 92 AE 2A FE A9 9A  y?^鬴??挳*?0019FDB4  AB 4C 42 5D 3F 07 1D 39 99 A2 82 F4 34 C8 75 DE  獿B]?9櫌傯4萿?

所以上面是Mul，在Mul上面下断点。

然后经过一个函数：

00444D59                      67:E8 21020100                   call    <modN>00444D5F                      50                               push    eax                                                          ; 返回1

返回结果为：

0019FDA4  C3 E1 2D 54 FD 5A A8 FC 4F DC D5 D1 6D D8 04 93  冕-T齔O苷裮??0019FDB4  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

看上去像是取模。

我们用：

DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC79 - 9304D86DD1D5DC4FFCA85AFD542DE1C3 = DE75C834F482A299391D073F5D424CAB07A525BCDCBC329225DF0BF709E8DAB

然后用yafu分解一下：

factor(0xDE75C834F482A299391D073F5D424CAB07A525BCDCBC329225DF0BF709E8DAB6)

fac: factoring 100621555269000733341031010157969998386759504095520400047147427430100793612982fac: using pretesting plan: normalfac: no tune info: using qs/gnfs crossover of 95 digits

starting SIQS on c72: 146405049556078485019294860272741026808150808686274920697977580425648851

==== sieving in progress (1 thread):   16656 relations needed ========           Press ctrl-c to abort and save state           ====

SIQS elapsed time = 0.6650 seconds.Total factoring time = 0.6730 seconds

factors found

P39 = 340282366920938463463374607424628147107P33 = 430245771712568276625619760299793ans = 1

其中P33太小，P39 = FFFFFFFFFFFFFFFFFFFFFFFE566B43A3。

验证一下：

DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC79 Mod FFFFFFFFFFFFFFFFFFFFFFFE566B43A3 = 9304D86DD1D5DC4FFCA85AFD542DE1C3

所以上面那个函数是 Mod 0xFFFFFFFFFFFFFFFFFFFFFFFE566B43A3。

设N=FFFFFFFFFFFFFFFFFFFFFFFE566B43A3，在ModN位置下断点，然后F9跑，然后发现Mul断下来了。

6805A57D5B006445AC1B0675EB188435 *  9304D86DD1D5DC4FFCA85AFD542DE1C3  = 3BBD360EF483631109E77CAB8B604BE7252D7537F13655FA919F38844130495F

断下了后，发现内存中值发生了变化：

3BBD360EF483631109E77CAB8B604BE768906BBC53C8BB20F644044205801BE2

跟上面乘的结果比较，发现是大了一点点：

3BBD360EF483631109E77CAB8B604BE768906BBC53C8BB20F644044205801BE2 - 3BBD360EF483631109E77CAB8B604BE7252D7537F13655FA919F38844130495F = 4362F6846292652664A4CBBDC44FD283

再跑，发现ModN断下来了：

00473134                      E8 471EFEFF                      call    <modN>00473139                      50                               push    eax

结果：24938628338F43651192F4F03FD24328

再跑，Mul断下来了：

24938628338F43651192F4F03FD24328 * 24938628338F43651192F4F03FD24328 = 0539D2BEA6F99DC5F4B8C6AAD5DCBB1F9927D007969D817073CB54BFEF3DF6400019FD10  40 F6 3D EF BF 54 CB 73 70 81 9D 96 07 D0 27 99  @?锟T藄p仢???0019FD20  1F BB DC D5 AA C6 B8 F4 C5 9D F9 A6 BE D2 39 05  卉摘聘襞濝?

再跑，ModN断下来，正好是0x4F5A512668E16EB6931155CEEF16D5F4

内存中结构，恰好等于 md5(name)的值：

0019FD10  F4 D5 16 EF CE 55 11 93 B6 6E E1 68 26 51 5A 4F  粽镂U摱n醜&QZO

3、算法篇

整理一下算法：

设N = FFFFFFFFFFFFFFFFFFFFFFFE566B43A3

A = 6805A57D5B006445AC1B0675EB188435

B = 4362F6846292652664A4CBBDC44FD283

M = MD5(name) ， 注意，内存中是little eddian的

S = hex(serial)

整个验证算法，可以用表达式来表示：

M = (((S ^ 2) Mod N) * A + B) ^ 2 Mod N

看数学表达式，实际上是 两次平方模，然后比较name的md5。逆运算就是求平方剩余。

平方剩余公式是：

当 Y = X^2 Mod N ，且 N mod 4 = 3的时候

X1 = Y ^ ((N+1)/4) Mod N

平方剩余有多解：另一解是 X2 = N - X1

所以这题其实有4解。

name: 1A5FBFD826E1D12E

serial: 

EEA43B9D52515B49838AFAA50490DA0B

115BC462ADAEA4B67C75055951DA6998

41B8103BEC6C05BC8D4E37DD2DF5D1E8

BE47EFC41393FA4372B1C821287571BB

经测试，这4解都可以通过验证。

4、音乐篇

但是，当我们使用KCTF的时候：

MD5('KCTF') = 0xA0D99FB4D5ABF597979F99A2C6B11A7A ( 内存中字节码：7A 1A B1 C6 A2 99 9F 97 97 F5 AB D5 B4 9F D9 A0 )

求出来的4解是：

2EA6060B597BA4D12D2FC0A1DF7A5FB5

D159F9F4A6845B2ED2D03F5C76F0E3EE

48538B7EADCDD321FB83E1F4D227BAD9

B7AC748152322CDE047C1E09844388CA

遗憾的是，一个都无法通过！

看了一遍又一遍《生命的馈赠》，“所有曲目我都试过了，这密码还是打不开”

为什么会不对呢？各种百度，谷歌，原来，平方剩余是有条件的。

Y = X^2 Mod N，X有解的条件是 Y^ ((N-1)/2) == 1 Mod N

第一次的时候，是有平方剩余的，所以能解出两解。

Z1 = 0000000000000000B0D3C2D4E7B7A3BA

Z2 = 6E000A013A6DF57F8ABD86D0120C88AD

但是第二次的时候，两组数据都没有平方剩余！

这就有意思了，到底哪里出问题了呢？再看一遍视频，发现缺了个琴音是破解的关键！

有没有可能，Mod的时候，没有模尽，使得结果多了一个N，然后取了低128bit，正好就有平方剩余了呢？

于是，把Z1,Z2，分别 

Z1 + 2^128 - N = B0D3C2D6914C6017

求两组平方剩余:

05A6CC68CF60E9606195E9912BBF332A

FA593397309F169F9E6A166D2AAC1079

Z2 + 2^128 - N = 6E000A013A6DF57F8ABD86D1BBA1450A

求两组平方剩余：

6E66D51BBB5DFD0200F5BF564A7F1052

91992AE444A202FDFF0A40A80BEC3351

验证发现，FA593397309F169F9E6A166D2AAC1079 是唯一通过的解！

注意：【最受欢迎战队奖】&【新思路奖】正在火热评选中！欢迎大家投上宝贵的一票～

待评选（一）：【最受欢迎战队奖】

长按二维码立即投票！【最受欢迎战队奖】

【最受欢迎战队奖】

评选对象：

2021 KCTF秋季赛 参赛战队（包含防守方所有战队+攻击方前20名战队）

评选方式：

登陆看雪账号，在本帖为喜欢的战队投票，每个账号可投1票。

投票时间：

12月15日 14:00 ～12月22日 14：00

奖品：

【最受欢迎战队奖】得票第一名：可获得「HUAWEI WATCH GT2 华为手表」

待评选（二）：【新思路奖】

长按二维码立即投票！

【新思路奖】

评选对象：

2021 KCTF秋季赛 参赛防守方战队

评选方式：

1、会员投票（占比50%）：在KCTF答题页面投票，只有提交答案的选手才可投票。【快使用你们的特权～】

2、看雪KCTF专家评审团投票（占比50%）：评审团成员投票，每人一票。

投票时间：

比赛开始，直到比赛结束后一周。（12月22日12：00关闭投票通道）

奖品：

【新思路奖】得票第一名：可获得「HUAWEI WATCH GT2 华为手表」

往期解析

1、看雪·众安 2021 KCTF 秋季赛 | 第二题设计思路及解析

2、看雪·众安 2021 KCTF 秋季赛 | 第三题设计思路及解析

3、看雪·众安 2021 KCTF 秋季赛 | 第四题设计思路及解析

4、看雪·众安 2021 KCTF 秋季赛 | 第五题设计思路及解析

5、看雪·众安 2021 KCTF 秋季赛 | 第六题设计思路及解析

6、看雪·众安 2021 KCTF 秋季赛 | 第七题设计思路及解析

7、看雪·众安 2021 KCTF 秋季赛 | 第八题设计思路及解析

8、看雪·众安 2021 KCTF 秋季赛 | 第九题设计思路及解析

9、看雪·众安 2021 KCTF 秋季赛 | 第十一题设计思路及解析

- End -

公众号ID：ikanxue

官方微博：看雪安全

商务合作：wsc@kanxue.com