看雪学院 08月20日
2025 KCTF | 第三题《邪影显现》设计思路及解析
index_new5.html
../../../zaker_core/zaker_tpl_static/wap/tpl_guoji1.html

 

2025 KCTF比赛中的《邪影显现》题目,考查了RSA逆向与大数运算能力。题目核心在于对输入串进行多轮模逆与扰动操作,幂次为质数序列,并结合特定常量和MD5值进行校验,整体流程可还原为可逆的RSA运算。解题的关键在于模数分解、逐步推演可逆性以及识别大数库差异,对选手的数学功底和工程实现能力提出了较高要求。

🔐 题目核心是基于RSA加密的逆向工程,通过对输入数据进行一系列复杂的模逆和扰动操作,并结合特定的字符串和哈希值进行验证。这要求参赛者深入理解RSA算法以及大数运算的细节。

🔢 题目的关键在于识别并利用了freelip大数计算库的特性,包括其内部数据表示和特定的运算函数。通过分析反编译代码和引用库的常量字符串,可以推断出大数运算的类型(如乘法、取模、模逆)和具体实现。

🔢 题目中包含9轮重复的计算模式,每轮都涉及对上一轮结果进行乘法累加(部分轮次穿插取模)、一次取模、一次模逆,最后进行一次特定的扰动操作(大端序高位DWORD自增)。每轮的幂次构成了一个递增的质数序列(-3, -7, -11, ..., -37)。

🔑 题目通过对大数库的引用和对特定算法流程的模拟,考验了选手对底层计算原理的理解。解题思路需要从反编译代码入手,结合AI分析和对库函数的猜测验证,最终还原出完整的加密验证流程。

💻 最终的解题过程可以转化为Python代码,通过逆向工程推导出计算serial(密钥)的公式,从而解决此题。这体现了CTF比赛中理论知识与实践操作相结合的重要性。

2025 KCTF 2025-08-20 17:59 上海

本题共有8支战队成功提交flag

2025 KCTF 于8月15日中午12点正式开赛!比赛设置了多维度的评分体系,包括难度值、火力值和精致度积分。今天中午12点,第三题《邪影显现》已截止答题。

*注意:签到题《废柴少年觉醒》持续开放,整个比赛期间均可提交答案获得积分

本题共有8支战队成功提交flag,其中前3名分别是:hzqmwne】、【Namikaze】、【COMPASS

KCTF评委团队点评:

这题考查RSA逆向与大数运算理解。核心逻辑是对输入串执行多轮模逆与扰动操作,幂次依次为质数序列(-3、-7、-11…-37)。

结合常量"KCTF2025"与MD5(name)进行对齐校验,整体流程可还原为可逆的RSA运算。题目重点在模数分解、逐步推演可逆性以及大数库差异识别,既考数学功底也考工程实现,非常适合作为进阶逆向练习。

一起来看看本题的设计思路和解题思路吧~

一、

设计思路

出题战队:金左韭

战队成员ID:ccfer、KevinsBobo、大帅锅、linhanshi、Lyxk

题目描述

easy rsa192

运行环境

WIN10,VCRUNTIME140

公开组序列号

name: EA35B2C3F2B5FCE4

code: 20DB698F803FB15F6DFFBADD0E125ABEBE96494B0CCCA620

python版验证逻辑

def kctf2025_cm(name, code):

    n = 0x56F67550F16A00390DCF0B2715708E61C5B3F23101862FC1

    e = [0x03,0x07,0x0B,0x11,0x13,0x17,0x1D,0x1F,0x25]

    a = 2 ** 184

    x = int.from_bytes(bytes.fromhex(code), byteorder='big')

    for i in e:

        x = pow(x,i,n)

        x = gmpy2.invert(x,n)

        x = x + a

    h = 'KCTF2025'.encode('utf-8') + hashlib.md5(name.encode('utf-8')).digest()

    r = int.from_bytes(h, byteorder='big')

    if x == r:

        print('ok')

    else:

        print('error')

二、

赛题解析

该解析由论坛会员ID:mb_mgodlfyn提供

主要逻辑在 sub_402380 里,此函数非常长,不过 AI 的初步分析还是给出了很多有价值的信息:

接下来提示AI,a1是已知的name,a2是待求的serial,AI给出了进一步的分析:

从最终情况看,其中关于椭圆曲线/有限域的结论是错误的,但其他分析结论完全正确(而且此时提供给AI的上下文只包含 sub_402380 的反编译伪代码,还不包含任何它调用的子函数,因此这只是对sub_402380整体逻辑的初步印象),特别的是给出了a1(name)参数经过运算的比较串"KCTF2025" || MD5(a1)[0..11]、大数运算、++v262[0]的扰动这三项提示,对后续的人工分析启发很大。

优先查看 AI 指出的几个子函数,注意到引用了常量区的一些字符串:

.rdata:0045A7E8 ; const char aFatalErrorSExi[]
.rdata:0045A7E8 aFatalErrorSExi db 'fatal error:',0Ah   ; DATA XREF: zhalt+6↑o
.rdata:0045A7F5                 db '   %s',0Ah
.rdata:0045A7FB                 db 'exit...',0Ah,0
.rdata:0045A804 ; const char aDBytesReallocF[]
.rdata:0045A804 aDBytesReallocF db '%d bytes realloc failed',0Ah,0
.rdata:0045A804                                         ; DATA XREF: zsetlength+7F↑o
.rdata:0045A81D                 align 10h
.rdata:0045A820 aReallocationFa_0 db 'reallocation failed in zsetlength',0
.rdata:0045A820                                         ; DATA XREF: zsetlength+98↑o
.rdata:0045A842                 align 4
.rdata:0045A844 ; const char aDBytesCallocFa[]
.rdata:0045A844 aDBytesCallocFa db '%d bytes calloc failed',0Ah,0
.rdata:0045A844                                         ; DATA XREF: zsetlength+AA↑o
.rdata:0045A85C aAllocationFail db 'allocation failed in zsetlength',0
.rdata:0045A85C                                         ; DATA XREF: zsetlength+C3↑o
.rdata:0045A87C aNegativeSizeAl_0 db 'negative size allocation in zsetlength',0
.rdata:0045A87C                                         ; DATA XREF: zsetlength:loc_454EFD↑o
.rdata:0045A8A3                 align 4
.rdata:0045A8A4 ; const char aZstartFailureR[]
.rdata:0045A8A4 aZstartFailureR db 'zstart failure: recompile with smaller NBITS',0Ah,0
.rdata:0045A8A4                                         ; DATA XREF: zstart+4D↑o
.rdata:0045A8D2                 align 4
.rdata:0045A8D4 aInZzeroFirstAr db 'in zzero, first argument',0
.rdata:0045A8D4                                         ; DATA XREF: z2div+E5↑o
.rdata:0045A8D4                                         ; z2mul+1B↑o ...
.rdata:0045A8ED                 align 10h
.rdata:0045A8F0 aInZcopySecondA db 'in zcopy, second argument',0
.rdata:0045A8F0                                         ; DATA XREF: zcopy+4E↑o
.rdata:0045A90A                 align 4
.rdata:0045A90C aInZintozSecond db 'in zintoz, second argument',0
.rdata:0045A90C                                         ; DATA XREF: zintoz+14↑o
.rdata:0045A927                 align 4
.rdata:0045A928 aInZuintozSecon db 'in zuintoz, second argument',0
.rdata:0045A928                                         ; DATA XREF: zultoz+28↑o
.rdata:0045A944 aInZsubposThird db 'in zsubpos, third argument',0
.rdata:0045A944                                         ; DATA XREF: sub_4555A0+1B↑o
.rdata:0045A95F                 align 10h
.rdata:0045A960 aInZaddThirdArg db 'in zadd, third argument',0
.rdata:0045A960                                         ; DATA XREF: zadd+76↑o
.rdata:0045A978 aInZsubThirdArg db 'in zsub, third argument',0
.rdata:0045A978                                         ; DATA XREF: zsub+106↑o
.rdata:0045A990 aInZsmulThirdAr db 'in zsmul, third argument',0
.rdata:0045A990                                         ; DATA XREF: sub_454F60+72↑o
.rdata:0045A9A9                 align 4
.rdata:0045A9AC aInKarMulThirdA db 'in kar_mul, third argument',0
.rdata:0045A9AC                                         ; DATA XREF: sub_452D20+14↑o
.rdata:0045A9C7                 align 4
.rdata:0045A9C8 aInKarMulLocals db 'in kar_mul, locals',0Ah,0
.rdata:0045A9C8                                         ; DATA XREF: sub_452D20+7C↑o
.rdata:0045A9DC aInKarSqSecondA db 'in kar_sq, second argument',0
.rdata:0045A9DC                                         ; DATA XREF: sub_453230+F↑o
.rdata:0045A9F7                 align 4
.rdata:0045A9F8 aInKarSqLocals  db 'in kar_sq, locals',0Ah,0
.rdata:0045A9F8                                         ; DATA XREF: sub_453230+5D↑o
.rdata:0045AA0B                 align 4
.rdata:0045AA0C aDivisionByZero_4 db 'division by zero in zsdiv',0
.rdata:0045AA0C                                         ; DATA XREF: zsdiv:loc_454E81↑o
.rdata:0045AA26                 align 4
.rdata:0045AA28 aInZsdivThirdAr db 'in zsdiv, third argument',0
.rdata:0045AA28                                         ; DATA XREF: zsdiv+6F↑o
.rdata:0045AA41                 align 4
.rdata:0045AA44 aDivisionByZero_1 db 'division by zero in zdiv',0
.rdata:0045AA44                                         ; DATA XREF: zdiv:loc_4540C3↑o
.rdata:0045AA5D                 align 10h
.rdata:0045AA60 aInZdivLocals   db 'in zdiv, locals',0Ah,0 ; DATA XREF: zdiv+108↑o
.rdata:0045AA71                 align 4
.rdata:0045AA74 aInZdivThirdArg db 'in zdiv, third argument',0
.rdata:0045AA74                                         ; DATA XREF: zdiv+12C↑o
.rdata:0045AA8C aInZdivFourthAr db 'in zdiv, fourth argument',0
.rdata:0045AA8C                                         ; DATA XREF: zdiv+141↑o
.rdata:0045AAA5                 align 4
.rdata:0045AAA8 aDivisionByZero_3 db 'division by zero in zmod',0
.rdata:0045AAA8                                         ; DATA XREF: zmod:loc_4547D1↑o
.rdata:0045AAC1                 align 4
.rdata:0045AAC4 aInZmodLocal    db 'in zmod, local',0   ; DATA XREF: zmod+D8↑o
.rdata:0045AAD3                 align 4
.rdata:0045AAD4 aInZmodThirdArg db 'in zmod, third argument',0
.rdata:0045AAD4                                         ; DATA XREF: zmod+EC↑o
.rdata:0045AAEC aModulusZeroInZ db 'modulus zero in zinvmod',0
.rdata:0045AAEC                                         ; DATA XREF: zinvmod:loc_454214↑o
.rdata:0045AB04 aDivisionByZero_2 db 'division by zero in zinvmod',0
.rdata:0045AB04                                         ; DATA XREF: zinvmod:loc_45421E↑o
.rdata:0045AB20 aUndefinedInver db 'undefined inverse in zinvmod',0
.rdata:0045AB20                                         ; DATA XREF: zinvmod:loc_454228↑o
.rdata:0045AB3D                 align 10h
.rdata:0045AB40 aInZxxeuclLocal db 'in zxxeucl, locals',0Ah,0
.rdata:0045AB40                                         ; DATA XREF: sub_455960+31↑o
.rdata:0045AB54 aInZxxeuclThird db 'in zxxeucl, third argument',0
.rdata:0045AB54                                         ; DATA XREF: sub_455960:loc_455A2F↑o
.rdata:0045AB6F                 align 10h
.rdata:0045AB70 aInZxxeuclFourt db 'in zxxeucl, fourth argument',0
.rdata:0045AB70                                         ; DATA XREF: sub_455960+E4↑o
.rdata:0045AB8C aZeroOrNegative db 'zero or negative argument(s) in zinv',0
.rdata:0045AB8C                                         ; DATA XREF: sub_454190:loc_4541DB↑o
.rdata:0045ABB1                 align 4
.rdata:0045ABB4 aInZ2mulSecondA db 'in z2mul, second argument',0
.rdata:0045ABB4                                         ; DATA XREF: z2mul+52↑o
.rdata:0045ABCE                 align 10h
.rdata:0045ABD0 aInZ2divSecondA db 'in z2div, second argument',0
.rdata:0045ABD0                                         ; DATA XREF: z2div+35↑o
.rdata:0045ABEA                 align 4
.rdata:0045ABEC aInZlshiftThird db 'in zlshift, third argument',0
.rdata:0045ABEC                                         ; DATA XREF: zlshift+B9↑o
.rdata:0045AC07                 align 4
.rdata:0045AC08 aInZrshiftThird db 'in zrshift, third argument',0
.rdata:0045AC08                                         ; DATA XREF: zrshift+116↑o
.rdata:0045AC23                 align 4
.rdata:0045AC24 aInZlowbitsThir db 'in zlowbits, third argument',0
.rdata:0045AC24                                         ; DATA XREF: ztoul:loc_455780↑o

容易查到这些字符串出自 freelip 大数计算库(https://github.com/lrobot/freelip/blob/master/lip.c)而在对a2(serial)参数做hexdecode的代码后面,第一段代码恰好调用到了这些函数:

  zultoz((int)v275, 6, &v191);

  v26 = Buffer;

  if strlen(Buffer) == 48 )

  {

    for ( j = 0; j < 24; ++j )

    {

      v28 = *v26;

      if ( (*v26 < 48 || v28 > 57) && (unsigned __int8)(v28 - 65) > 5u )

        goto LABEL_209;

      v29 = v26[1];

      if ( (v29 < 48 || v29 > 57) && (unsigned __int8)(v29 - 65) > 5u )

        goto LABEL_209;

      if sscanf(v26, "%02X", &v275[j]) != 1 )

        goto LABEL_209;

      v26 += 2;

    }

    v30 = 0;

    v31 = &v275[23];

    do

    {

      v32 = *v31--;

      v274[v30++] = v32;

    }

    while ( v30 < 24 );

    v227 = 0;

    zultoz((int)v274, 6, &v227);                // sub_455880,  v274 (first arg) is reversed hexdecoded a2 , which is serial

    zmul(v227, v227, &v245);                    // sub_4547E0,  v245 = v227 * v227 = x * x = x**2

    zmul(v227, v245, &v263);                    // sub_4547E0,  v263 = v227 * v245 = x* x**2 = x**3

    zmod(v263, v191, &v245);                    // sub_454440

    zinvmod(v245, v191, &v245);                 // sub_4541F0,  tmp2 = pow(tmp1, -3, pp)

    v266 = 6;

    ztoul(v245, (int *)v274, &v266);            // sub_4556D0,  now v274 (second arg) is serial ** (-3) % pp

    v33 = 0;

    v34 = 4 * v266;

    v266 = v34;

    if ( v34 > 0 )

    {

      do

      {

        v275[v33] = v273[v34 - v33 + 255];

        ++v33;

      }

      while ( v33 < v34 );

    }

    ++*(_DWORD *)v275;                          // ?? tmp1 -> tmp2

...

其中sub_454440和sub_4541F0可以直接从函数里面引用的常量字符串确认是zmod和zinvmod,头尾的sub_455880和sub_4556D0按照常理应该是大数的导入和导出(与源代码对照后可以确认是zultoz和ztoul),那么中间的sub_4547E0必然是某种大数运算函数。

freelip这个库的大数内部表示有些奇怪,它内部的int数组好像每一项只使用了30bit左右,导致经过zultoz后内部的数组与原始字节并不一致,这点与其他常见库完全不同,导致不太方便通过调试判断sub_4547E0的变换,但是可以猜测大概率不是加法就是乘法

不过既然前面的zultoz以及后面的zmod和zinvmod已知,那么可以先从最上面0x402ADC处的zultoz导出v275的内存值确认v191的模数的值(记为pp),再分别测试一下x*(-3)%ppx**(-3)%pp,然后调试查看ztoul导出的v274,即可确定sub_4547E0是zmul,执行的是乘法运算。

顺便导出了模数为0x56f67550f16a00390dcf0b2715708e61c5b3f23101862fc1,是0x402780附近的赋值的量。

通过yafufactordb可以得到模数的质因数分解,它恰好可以分解为两个质数的乘积:

1

0x56f67550f16a00390dcf0b2715708e61c5b3f23101862fc1 = 2132319876367679106148824069448800305036941072478331350977 = 45424490472579293708671645907 * 46942075831425428541187578011

根据RSA的计算原理,对于 c = pow(m, e, n) ,在已知n的分解为p*q时,可以由c反向计算mphi = (p-1)*(q-1) , d = pow(e, -1, phi) , m = pow(c, d, n)

因此,这里对a2(serial)的第一次运算tmp1 = pow(a2, -3, pp)完全可逆。

再注意到 0x402C47 出的运算 ++*(_DWORD *)v275; (回顾开始,AI也注意到了这处扰动) ,在 tmp1 的大端内存表示的前四个字节做了一次自增。虽然运算很奇怪,但可逆,于是暂记结果为 tmp2

再看接下来的一段代码:

v35 = &v275[23];

v220[0] = 0;

for ( k = 0; k < 24; ++k )

{

  v37 = *v35--;

  *((_BYTE *)v221 + k) = v37;

}

v220[0] = 6;

v220[2] = 0;

sub_4065C0(v220);

v38 = (_DWORD *)v220[0];

v238[1] = bignumber_mul___((int)v221, (int)v221, v220[0], (int)v239, (int)v238);// sub_406450,  v232 = v214 * v214 = x ** 2

v238[2] = 0;

sub_4065C0(v238);

v256[1] = bignumber_mul___((int)v221, (int)v239, v238[0], (int)v257, (int)v256);// v250 = v214 * v232 = x ** 3

v256[2] = v220[2] ^ v238[2];

sub_4065C0(v256);

v203[0] = bignumber_mul___((int)v257, (int)v257, v256[0], (int)v204, (int)&v202);// v199 = v250 * v250 = x ** 6

v203[1] = 0;

sub_4065C0(&v202);

v256[1] = bignumber_mul___((int)v204, (int)v221, (int)v38, (int)v257, (int)v256);// v250 = v199 * v214 = x ** 7

v256[2] = v220[2] ^ v203[1];

sub_4065C0(v256);

bignumber_mod(v256, v188, v238);            // sub_4067B0,  first arg v245 is x ** 7 , second arg v185 is pp (same as above)

bignumber_invmod(v238, v188, v238);         // sub_4074B0,  tmp3 = pow(tmp2, -7, pp)

v39 = (v238[1] + 7) >> 3;

v266 = v39;

sub_4065C0(v238);

memset(v275, 0, v39);

for ( m = 0; m < v39; v274[v42 + 255] = v41 )

{

  v41 = v239[m];

  v42 = v39 - m++;

}

++*(_DWORD *)v275;                          // // ?? tmp3 -> tmp4

sub_406450函数被多次调用,它的传入参数有点混乱(除了栈,还包含ecx和eax)。在最后还调用了sub_4067B0和sub_4074B0,整体的调用模式与第一段看起来非常相似。

这里仍然先猜测是大数运算,这里应该是换了一个大数库,但经过调试验证,容易验证sub_406450、sub_4067B0、sub_4074B0分别是mul、mod、invmod,模数与上面相同,计算结果为tmp3 = pow(tmp2, -7, pp),加上最后0x402E19处的++*(_DWORD *)v275;,仍然是大端序高位DWORD自增扰动得到的tmp4。


接下来的一组sub_41A180、sub_41AB20、sub_41AF50分别也是mul、mod、invmod,以及0x402FC7处相同的扰动,得到tmp5 = pow(tmp4, -11, pp)tmp6

以 ++*(_DWORD *)v275; 为支点,发现 sub_402380 大函数里相同的计算模式反复出现了9次,每次都换了一个大数库,但都是先对上一轮的结果做若干次乘法累加(后面几轮的中间穿插了取模)、一次取模、一次模逆、一次扰动。

因此,后面的逻辑无需再仔细逆向,直接找到每组重复次数最多的函数记为mul,然后静态计算出每轮mul的次数(这里也很有规律,每一轮最终的mul指数构成了递增的质数序列)并通过调试验证即可。

以下整理出每轮的三个大数运算函数以及最终的幂次:

(注意不同库的参数不同(例如,有的是三参数且出参可以分别位于三个位置或返回值,有的是两参数且出参复用某个入参的位置,还有多参数包含一些额外的长度信息等),中间还会穿插大数构造/析构/复制等辅助函数,排除干扰即可)

sub_402380的校验逻辑整理为python后非常短小:

def b2i(s):

    return int.from_bytes(s, "big")

 

 

def i2b(n):

    = n.to_bytes((n.bit_length()+7)//8"big")

    return r

 

 

def perturbation(v):

    bb = i2b(v)

    = int.from_bytes(bb[:4], 'little')

    = (f + 1) & 0xffffffff

    bbb = f.to_bytes(4'little'+ bb[4:]

    return b2i(bbb)

 

 

name = "..."

serial = "..."

 

= 2132319876367679106148824069448800305036941072478331350977

 

tmp = b2i(bytes.fromhex(serial))

for in [-3-7-11-17-19-23-29-31-37]:

    tmp = pow(tmp, e, n)

    tmp = perturbation(tmp)

 

assert b"KCTF2025" + hashlib.md5(name.encode()).digest() == b2i(tmp)

根据name计算serial的反向代码为:

def b2i(s):

    return int.from_bytes(s, "big")

 

 

def i2b(n):

    = n.to_bytes((n.bit_length()+7)//8"big")

    return r

 

 

def inverse_pow(v, e):

    = 45424490472579293708671645907

    = 46942075831425428541187578011

    = * q

    phi = (p-1* (q-1)

    = pow(e, -1, phi)

    = pow(v, d, n)

    return m

 

 

def inverse_perturbation(v):

    bb = i2b(v)

    = int.from_bytes(bb[:4], 'little')

    = (f - 1) & 0xffffffff

    bbb = f.to_bytes(4'little'+ bb[4:]

    return b2i(bbb)

 

 

name = "KCTF"

 

tmp = b2i(b"KCTF2025" + hashlib.md5(name.encode()).digest())

for in [-37-31-29-23-19-17-11-7-3]:

    tmp = inverse_perturbation(tmp)

    tmp = inverse_pow(tmp, e)

 

 

serial = i2b(tmp).hex().upper()

print(serial)

最终答案:

1

2

name: KCTF

serial: 1E28C86DABB02CF834913B52502645E388284470E700FC13

1

扫码参赛

第四题《血色试炼》火热挑战中

关于KCTF

看雪CTF(简称KCTF)是圈内知名度最高的技术竞技,从原CrackMe攻防大赛中发展而来,采取线上PK的方式,规则设置严格周全,题目涵盖Windows、Android、iOS、Pwn、智能设备、Web等众多领域。

扫码进入2025 KCTF

主办方

支持单位

看雪CTF比赛分为两个阶段,所有论坛会员均可参与,第一阶段是防守篇,防守方根据比赛要求制作题目,根据题目被破解的时间排名,被破解时间长者胜出。第二阶段为攻击篇,攻击第一阶段的题目,根据攻击成功的时间与题目排名,破解时间短且破解题目数多者胜。既给了防守方足够的施展空间,也避免过度浪费攻击方的时间。从攻防两个角度看,都是个难得的竞技和学习机会。

看雪CTF比赛历史悠久、影响广泛。自2007年以来,看雪已经举办十多个比赛,与包括金山、360、腾讯、阿里等在内的各大公司共同合作举办赛事。比赛吸引了国内一大批安全人士的广泛关注,历年来CTF中人才辈出,汇聚了来自国内众多安全人才,高手对决,精彩异常,成为安全圈的一次比赛盛宴,突出了看雪论坛复合型人才多的优势,成为企业挑选人才的重要途径,在社会安全事业发展中产生了巨大的影响力。

- End -

球分享

球点赞

球在看

“阅读原文一起来充电吧!

阅读原文

跳转微信打开

Fish AI Reader

Fish AI Reader

AI辅助创作,多种专业模板,深度分析,高质量内容生成。从观点提取到深度思考,FishAI为您提供全方位的创作支持。新版本引入自定义参数,让您的创作更加个性化和精准。

FishAI

FishAI

鱼阅,AI 时代的下一个智能信息助手,助你摆脱信息焦虑

联系邮箱 441953276@qq.com

相关标签

KCTF RSA 逆向工程 大数运算 CTF比赛
相关文章