看雪.纽盾 KCTF 2019 Q3 | 第十三题点评及解题思路
发布者：Editor
发布于：2019-10-08 14:35
“什么齐天大圣，没用的猴子罢了。”
“它是传奇。”
“失败者不配被历史铭记。”
时间又翻过多久呢……几百年？几千年？
昔日的当权者埋进坟墓。旅人们自青山脚下走说笑着走过，毫不在意路旁的青石，以及青石前默默矗立的僧侣。
沉睡，沉睡了多久?
是谁在呼唤我？
大陆的的风暴已经袭来，乱世争战，时空混乱。危机，超越了人类与魔种的界限。我要夺得星钻，我要登上天下最强者的宝座。
我是齐天大圣，我不会死。
回应着呼唤与呢喃，大地开始剧烈的颤抖。就像千百年前诞生时一样，冲破枷锁和束缚。它的身影如此高大，矗立于天地之间。
大圣，归来。
本题共有1223人围观，最终只有3支团队攻破成功。大圣闹天空，无人可挡，而赛场上的战士们也如同大圣再临一般，各显神通，英勇非凡。
这道题攻破人数较少，可见难度十分大，接下来我们一起来看一下这道题的点评和详细解析吧。
这是一道密码题，需要破解者了解Lucas公钥密码体制，并有一定的逆向能力、综合分析能力。应该是个挺难的题目。
序列号
这个程序默认只有一个SN，用户名内置为username。输入正确的SN提示good，错误的SN提示bad。
本题唯一序列号SN为：usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
就方程本身而言，每个name有1个key。格式为 ( || 表示字符串相加 )：
key = name || KXCTFXXXX || M0
方程缘由
经过分析，答案是肯定的，这样的模型存在。本题“完璧归赵”就是这个意思，也可以叫 “合二为一”。
本题方程是一个高度抽象的模同余方程， 题目验证：
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ] - h1 } mod N ... (b)
在本题中， V_e(m) mod N是Lucas序列函数的V序列, 或者简写为 Lucas V_e(m,1) mod N 。
参考luc公钥系统， 对公钥e有非对称解d， 可以求逆 （V可类比RSA的幂模运算）。
从而，这道题就可以求解了。具体求解代码，参见附件keygen的cpp源代码。
说明：公开的论文认为luc强度与RSA相当，至少不弱于RSA。
但是luc计算速度要慢于RSA。Lucas序列采用迭代算法，比RSA的快速幂模运算步骤要多，速度慢了不止一倍。所以实际上应用并不多。
Lucas序列有一些有趣的性质。参见（5）参考文档，或者wiki：https://en.wikipedia.org/wiki/Lucas_sequence
题目的参数设置
luc(m,e,N) = V_e(m, 1) mod N
head = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_"
name = "username"
body = head || name = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_username"
tail = "完璧归赵"
h1 = hash(head)
h2 = hash(name)
h3 = hash(body)
h4 = hash(tail)
hash取sha160，
h1 = 9071232e6b170092668255303e5d824f2879ad56
h2 = 249ba36000029bbe97499c03db5a9001f6b734ec
h3 = c4b73cb0dd1d750c69e1755b06bbaffff44d2600
h4 = 6dc844c73b34d6e6b8de48da64ef92ab2b11f461
N = sha-256("完璧归赵完璧归赵") = sha256(CDEAE8B5B9E9D5D4CDEAE8B5B9E9D5D4)
3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
N只有256bit，因子分解大概1到2分钟，N=P1*P2*P3, 有三个不同的素因子：
P1:1F7BF
P2:F1059E73CFB296F8B
P3:2267D9CC91A552E23D284260B563CE490B0F7475F9D
e1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133也就是FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF (20 bytes) || 4B5843544631395133 ("KXCTF19Q3" the HEX mode, 9 bytes)
e2 = N
验证过程
第1步，计算
m2 = luc(m0+h1, e1, N) , luc是lucas函数。
程序里采用了先分割，然后合并的算法， 使得分析的难度加大了。
e1被切分为H，K， e1=H+K ， H是某个hash，其实就是相当于一个伪随机数，H的值不重要。
因为后面会合并得到e1。
V_m1h, U_m1h = lucas u,v (m0+h1, H, N)
V_m1k, U_m1k = lucas u,v (m0+h1, K, N)
利用公式合并 e1，
V_i+j = (V_i * V_j + D * U_i * U_j ) / 2，其中D = (m^2 - 4) mod N是lucas(m,1) mod N的判别式。
m1 = luc(m0 + h1, e1, N) = (Vm1h * Vm1k + D *Um1h * Um1k) /2
第2步， 计算
m2 = luc(m1+h2, e2, N) ，程序里实际计算luc_vp(m1+h2, e2+1, N) ，等价于 luc(m1+h2, e2, N) 。
第3步， 计算
m3 = (m2 + h4) mod N
验证下式，成立则m0正确。
m3 == h3 。
求解方法：
以下lcm是最小公倍数。
参照RSA， RSA的最小phi函数 为卡迈克尔函数lcm(p-1,q-1) ,计算方便可取的phi函数为 欧拉函数(p-1)*(q-1) ，后者是前者的整数倍。
lucas的phi函数可以写作lcm(P-(Dp/P), Q-(Dq/Q))
(Dp/P) , (Dq/Q) , "()"是勒让德符号， 取值0， -1，+1。
Dp = (m^2 - 4) mod P , Dq = (m^2 - 4) mod Q 是 lucas(m,1) , 分别 mod P ， mod Q的判别式。
一般地， 加密消息一则消息m， 由于 p, q 是较大素数， (m^2 - 4) 与p互素, 与q互素， 要么是二次剩余，要么是非二次剩余， 符号 只取到-1，+1。
简单地，可直接取最大集合：
phi = (p-1)*(p+1)*(q-1)*(q+1)
N有3个素因子, N=p*q*r，即推广为
phi = lcm(p - 1,p + 1, q - 1, q + 1, r - 1, r + 1)。
或者简单地
phi = (p-1)*(p+1)*(q-1)*(q+1)*(r-1)*(r+1)。
比如：
phi = lcm(p1 - 1,p1 + 1,p2 - 1, p2 + 1,p3 - 1,p3 + 1)
phi = B492D4C14E9A74E225EC3FB39BD17C830072E04732255C87C350F579D51C03F8C130961AAD6C619EE804787627F4F2A31D71C1FA69474C51F1A1889DC8C0
e1= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133
e2= N =3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
d1 = 1/e1 mod phi
d2 = 1/e2 mod phi
d1=39027AEBF5B3D358B0075506CC37DF00393C5F191AA71B216F6F716A952206A55D9D3F81430FAE5E69E35AC4A58A98C51F472F18F347FBC300E0376DDBFB
d2=
8C7A26B58368185B65B10D3C6E9C0A6DEDAB758D3895F618A884127DCD5390470F2686B7F1771AFBE373E05DA70E382EE5DD75E71FFE1EE5BB1D63CC3CC1
按如下方程计算M0：
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ] - h1 } mod N
最后得到：
M0=753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
从而：
key=usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
彩蛋
如果进入彩蛋模式，额外赠送 ,可解锁用户名。
比如用户名：
name：
蔺相如
key：
蔺相如KXCTFXXXX19058E03B6FB04AAF15BD316B42B03D6D0769296F215E6604362CAA1F55036C2
参考文档
见附件打包下载。
文档：
lucas_paper.rar
代码：
keygenme2019q3_keygen.rar
lucas_paper.rar 包含如下部分文档：
wiki:
https://en.wikipedia.org/wiki/Lucas_sequence
LUC is a public-key cryptosystem based on Lucas sequences that
implements the analogs of ElGamal (LUCELG), Diffie-Hellman (LUCDIF), andRSA (LUCRSA).
cryptopp：
https://www.cryptopp.com/wiki/LUC_Cryptography
paper：
https://www.semanticscholar.org/paper/LUC%3A-A-New-Public-Key-System-Smith-Lennon/0ecfdb388bffbd623e536de70aee9ff811317cbc
LUC: A New Public Key System
Peter J. Smith, Michael J. J. LennonPublished in SEC 1993
中文文档：
Lucas公钥密码体制及其安全性.pdf
Lucas公钥密码体制及其性能公析.pdf
用OD在MessageBoxA下断，跟到校验代码。IDA F5一下。
check2函数伪代码太长了，就不放了，说下主要流程。
主要是计算一些字符串的hash作为大数，用LUC算法解密两次被KXCTFXXXX分割的第二部分input转成的大数，比较结果是否为0xC4B73CB0DD1D750C69E1755B06BBAFFFF44D2600。
总结一下就是：
怎么得到0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133的？
第一次解密，CM是将其分成两步来算的，第一步取得Lucas序列第 hash+KXCTF19Q3项的值，第二轮取第~hash项的值。
之后将第二轮的U,V值做72次快速递推，换算到项数上就是 ~hash * 2 ^ 0x72 = ~hash * 0x1000000000000000000。
然后再进行一次递推：
精简一下message2=((v243*v239*v240+v234*235 mod 0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01)>>1)+ 0x249BA36000029BBE97499C03DB5A9001F6B734EC //username
再加上一条性质：
将第二轮的项数和第一轮的项数相加（hash是20字节的），就得到0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133了。
之后，用LUC算法把0x56EEF7E9A1E89E25B1032C80A1CC1D54C93B319F加密回去就行，具体步骤如下：
1.分解N（N=0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01）
用ppsiqs或者在线分解都可以。分解得到：128959*277879388132275220363*804543020813130593505380215293268595059305396789149 = N。
2.计算它们的平方-1相乘的结果，也就是：
(128959^2-1)*( 277879388132275220363 ^2-1)*( 804543020813130593505380215293268595059305396789149 ^2-1)=0xFDEE7B2FD689345E05543994931E971838A18B641E848A1EEAA9D93353AF6595CFAC531583E0694776464966283075356167F8C8240C43533BCB281DE24E000（M）
3.求逆元
分别求出d1 * 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133 mod M = 1d2 * 0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01 mod M = 1
求得
d1 = 0xAC79CC5A4E51DFDF32C3234C5ABE56E90DF14AF9F0F659515C21C969F2B293EB7ED8C13072B634372A7EE3428573CA6655F11A369B1BCCE3FF76D4FE29191FB
d2 = 0xA8656E606751D95C207210B59A1ECB880B59F633BA64BF15367614212FBF642D0310EF5C6B1114B688B1E24EB03BA2DDF8725E63887AA9DA9555FDE6D9E0501
4.用d1，d2进行LUC加密（加密和解密其实用的同一个函数）
message2 = 0x56EEF7E9A1E89E25B1032C80A1CC1D54C93B319Fmessage = LUCencrypt(message2,d2,N) - 0x249BA36000029BBE97499C03DB5A9001F6B734EC
result = LUCencrypt(message,d1,N) - 0x9071232E6B170092668255303E5D824F2879AD56
解得
message = 0xD9C518135ED505550BE71C2430C33DFA16D8F8CFDF7F1FDD4C5471EAC2089D5
result = 0x753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
故flag为
usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
参考资料：
公钥加密算法LUC的并行实现方法
Some Remarks on Lucas-Based Cryptosystems
“它是传奇。”
“失败者不配被历史铭记。”
时间又翻过多久呢……几百年？几千年？
昔日的当权者埋进坟墓。旅人们自青山脚下走说笑着走过，毫不在意路旁的青石，以及青石前默默矗立的僧侣。
沉睡，沉睡了多久?
是谁在呼唤我？
大陆的的风暴已经袭来，乱世争战，时空混乱。危机，超越了人类与魔种的界限。我要夺得星钻，我要登上天下最强者的宝座。
我是齐天大圣，我不会死。
回应着呼唤与呢喃，大地开始剧烈的颤抖。就像千百年前诞生时一样，冲破枷锁和束缚。它的身影如此高大，矗立于天地之间。
大圣，归来。
题目简介
本题共有1223人围观，最终只有3支团队攻破成功。大圣闹天空，无人可挡，而赛场上的战士们也如同大圣再临一般，各显神通，英勇非凡。
这道题攻破人数较少，可见难度十分大，接下来我们一起来看一下这道题的点评和详细解析吧。
看雪评委crownless点评
这是一道密码题，需要破解者了解Lucas公钥密码体制，并有一定的逆向能力、综合分析能力。应该是个挺难的题目。
出题团队简介
毕业于中国科学技术大学自动控制专业，从事软件开发多年。在软件保护技术、加密算法方面有一些体验，编写了ECCTool椭圆曲线加密实用工具。
曾在北京多看科技从事电子阅读加密技术的研究，以及在小米安全团队从事IOT安全方面工作。
设计思路
序列号
这个程序默认只有一个SN，用户名内置为username。输入正确的SN提示good，错误的SN提示bad。
本题唯一序列号SN为：usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
就方程本身而言，每个name有1个key。格式为 ( || 表示字符串相加 )：
key = name || KXCTFXXXX || M0
方程缘由
经过分析，答案是肯定的，这样的模型存在。本题“完璧归赵”就是这个意思，也可以叫 “合二为一”。
本题方程是一个高度抽象的模同余方程， 题目验证：
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ] - h1 } mod N ... (b)
在本题中， V_e(m) mod N是Lucas序列函数的V序列, 或者简写为 Lucas V_e(m,1) mod N 。
参考luc公钥系统， 对公钥e有非对称解d， 可以求逆 （V可类比RSA的幂模运算）。
从而，这道题就可以求解了。具体求解代码，参见附件keygen的cpp源代码。
说明：公开的论文认为luc强度与RSA相当，至少不弱于RSA。
但是luc计算速度要慢于RSA。Lucas序列采用迭代算法，比RSA的快速幂模运算步骤要多，速度慢了不止一倍。所以实际上应用并不多。
Lucas序列有一些有趣的性质。参见（5）参考文档，或者wiki：https://en.wikipedia.org/wiki/Lucas_sequence
题目的参数设置
luc(m,e,N) = V_e(m, 1) mod N
head = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_"
name = "username"
body = head || name = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_username"
tail = "完璧归赵"
h1 = hash(head)
h2 = hash(name)
h3 = hash(body)
h4 = hash(tail)
hash取sha160，
h1 = 9071232e6b170092668255303e5d824f2879ad56
h2 = 249ba36000029bbe97499c03db5a9001f6b734ec
h3 = c4b73cb0dd1d750c69e1755b06bbaffff44d2600
h4 = 6dc844c73b34d6e6b8de48da64ef92ab2b11f461
N = sha-256("完璧归赵完璧归赵") = sha256(CDEAE8B5B9E9D5D4CDEAE8B5B9E9D5D4)
3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
N只有256bit，因子分解大概1到2分钟，N=P1*P2*P3, 有三个不同的素因子：
P1:1F7BF
P2:F1059E73CFB296F8B
P3:2267D9CC91A552E23D284260B563CE490B0F7475F9D
e1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133也就是FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF (20 bytes) || 4B5843544631395133 ("KXCTF19Q3" the HEX mode, 9 bytes)
e2 = N
验证过程
第1步，计算
m2 = luc(m0+h1, e1, N) , luc是lucas函数。
程序里采用了先分割，然后合并的算法， 使得分析的难度加大了。
e1被切分为H，K， e1=H+K ， H是某个hash，其实就是相当于一个伪随机数，H的值不重要。
因为后面会合并得到e1。
V_m1h, U_m1h = lucas u,v (m0+h1, H, N)
V_m1k, U_m1k = lucas u,v (m0+h1, K, N)
利用公式合并 e1，
V_i+j = (V_i * V_j + D * U_i * U_j ) / 2，其中D = (m^2 - 4) mod N是lucas(m,1) mod N的判别式。
m1 = luc(m0 + h1, e1, N) = (Vm1h * Vm1k + D *Um1h * Um1k) /2
第2步， 计算
m2 = luc(m1+h2, e2, N) ，程序里实际计算luc_vp(m1+h2, e2+1, N) ，等价于 luc(m1+h2, e2, N) 。
第3步， 计算
m3 = (m2 + h4) mod N
验证下式，成立则m0正确。
m3 == h3 。
求解方法：
以下lcm是最小公倍数。
参照RSA， RSA的最小phi函数 为卡迈克尔函数lcm(p-1,q-1) ,计算方便可取的phi函数为 欧拉函数(p-1)*(q-1) ，后者是前者的整数倍。
lucas的phi函数可以写作lcm(P-(Dp/P), Q-(Dq/Q))
(Dp/P) , (Dq/Q) , "()"是勒让德符号， 取值0， -1，+1。
Dp = (m^2 - 4) mod P , Dq = (m^2 - 4) mod Q 是 lucas(m,1) , 分别 mod P ， mod Q的判别式。
一般地， 加密消息一则消息m， 由于 p, q 是较大素数， (m^2 - 4) 与p互素, 与q互素， 要么是二次剩余，要么是非二次剩余， 符号 只取到-1，+1。
简单地，可直接取最大集合：
phi = (p-1)*(p+1)*(q-1)*(q+1)
N有3个素因子, N=p*q*r，即推广为
phi = lcm(p - 1,p + 1, q - 1, q + 1, r - 1, r + 1)。
或者简单地
phi = (p-1)*(p+1)*(q-1)*(q+1)*(r-1)*(r+1)。
比如：
phi = lcm(p1 - 1,p1 + 1,p2 - 1, p2 + 1,p3 - 1,p3 + 1)
phi = B492D4C14E9A74E225EC3FB39BD17C830072E04732255C87C350F579D51C03F8C130961AAD6C619EE804787627F4F2A31D71C1FA69474C51F1A1889DC8C0
e1= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133
e2= N =3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
d1 = 1/e1 mod phi
d2 = 1/e2 mod phi
d1=39027AEBF5B3D358B0075506CC37DF00393C5F191AA71B216F6F716A952206A55D9D3F81430FAE5E69E35AC4A58A98C51F472F18F347FBC300E0376DDBFB
d2=
8C7A26B58368185B65B10D3C6E9C0A6DEDAB758D3895F618A884127DCD5390470F2686B7F1771AFBE373E05DA70E382EE5DD75E71FFE1EE5BB1D63CC3CC1
按如下方程计算M0：
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ] - h1 } mod N
最后得到：
M0=753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
从而：
key=usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
彩蛋
如果进入彩蛋模式，额外赠送 ,可解锁用户名。
比如用户名：
name：
蔺相如
key：
蔺相如KXCTFXXXX19058E03B6FB04AAF15BD316B42B03D6D0769296F215E6604362CAA1F55036C2
参考文档
见附件打包下载。
文档：
lucas_paper.rar
代码：
keygenme2019q3_keygen.rar
lucas_paper.rar 包含如下部分文档：
wiki:
https://en.wikipedia.org/wiki/Lucas_sequence
LUC is a public-key cryptosystem based on Lucas sequences that
implements the analogs of ElGamal (LUCELG), Diffie-Hellman (LUCDIF), andRSA (LUCRSA).
cryptopp：
https://www.cryptopp.com/wiki/LUC_Cryptography
paper：
https://www.semanticscholar.org/paper/LUC%3A-A-New-Public-Key-System-Smith-Lennon/0ecfdb388bffbd623e536de70aee9ff811317cbc
LUC: A New Public Key System
Peter J. Smith, Michael J. J. LennonPublished in SEC 1993
中文文档：
Lucas公钥密码体制及其安全性.pdf
Lucas公钥密码体制及其性能公析.pdf
解题思路
用OD在MessageBoxA下断，跟到校验代码。IDA F5一下。
int __cdecl sub_407F30(HWND hDlg)
{
CHAR *v1; // edi
signed int v2; // esi
signed int v3; // eax
const CHAR *v4; // eax
const char *v5; // eax
CHAR *v6; // ecx
char v7; // al
const CHAR *v8; // eax
_BYTE *v9; // ecx
char v10; // al
char v11; // al
_BYTE *v12; // ecx
char v13; // al
CHAR *v14; // ecx
char pe; // [esp-40h] [ebp-3D8h]
char *v17; // [esp-3Ch] [ebp-3D4h]
int v18; // [esp-38h] [ebp-3D0h]
int v19; // [esp-34h] [ebp-3CCh]
char un; // [esp-30h] [ebp-3C8h]
char *v21; // [esp-2Ch] [ebp-3C4h]
int v22; // [esp-28h] [ebp-3C0h]
int v23; // [esp-24h] [ebp-3BCh]
int kx; // [esp-20h] [ebp-3B8h]
char *v25; // [esp-1Ch] [ebp-3B4h]
int v26; // [esp-18h] [ebp-3B0h]
int v27; // [esp-14h] [ebp-3ACh]
char *input; // [esp-10h] [ebp-3A8h]
char *v29; // [esp-Ch] [ebp-3A4h]
const CHAR *v30; // [esp-8h] [ebp-3A0h]
void (__thiscall *v31)(void *); // [esp-4h] [ebp-39Ch]
char v32; // [esp+13h] [ebp-385h]
char v33; // [esp+14h] [ebp-384h]
LPCSTR v34; // [esp+18h] [ebp-380h]
int v35; // [esp+1Ch] [ebp-37Ch]
int v36; // [esp+20h] [ebp-378h]
char v37; // [esp+24h] [ebp-374h]
int v38; // [esp+28h] [ebp-370h]
unsigned int v39; // [esp+2Ch] [ebp-36Ch]
int v40; // [esp+30h] [ebp-368h]
char v41; // [esp+34h] [ebp-364h]
int v42; // [esp+38h] [ebp-360h]
int v43; // [esp+3Ch] [ebp-35Ch]
int v44; // [esp+40h] [ebp-358h]
char v45; // [esp+44h] [ebp-354h]
const char *v46; // [esp+48h] [ebp-350h]
unsigned int v47; // [esp+4Ch] [ebp-34Ch]
char v48; // [esp+54h] [ebp-344h]
LPCSTR lpText; // [esp+58h] [ebp-340h]
int nIDDlgItem; // [esp+64h] [ebp-334h]
int v51; // [esp+68h] [ebp-330h]
int v52; // [esp+6Ch] [ebp-32Ch]
char *v53; // [esp+70h] [ebp-328h]
char *v54; // [esp+74h] [ebp-324h]
int *v55; // [esp+78h] [ebp-320h]
char **v56; // [esp+7Ch] [ebp-31Ch]
int v57[3]; // [esp+80h] [ebp-318h]
CHAR String; // [esp+8Ch] [ebp-30Ch]
char v59; // [esp+8Dh] [ebp-30Bh]
char v60; // [esp+18Ch] [ebp-20Ch]
char v61; // [esp+28Ch] [ebp-10Ch]
__int16 v62; // [esp+389h] [ebp-Fh]
char v63; // [esp+38Bh] [ebp-Dh]
int v64; // [esp+394h] [ebp-4h]
String = 0;
memset(&v59, 0, 0x2FCu);
v62 = 0;
v63 = 0;
nIDDlgItem = 1005;
v51 = 1000;
v52 = 1001;
v1 = &String;
v2 = 0;
while ( 1 )
{
v3 = GetDlgItemTextA(hDlg, *(int *)((char *)&nIDDlgItem + v2 * 4), v1, 255);
v57[v2] = v3;
if ( v3 < 1 || v3 > 100 )
return 0;
++v2;
v1 += 256;
if ( v2 >= 3 )
{
`eh vector constructor iterator'(&v45, 0x10u, 2, sub_408360, sub_40B410);
v64 = 0;
v33 = v32;
newstring(&v33, 0);
strcpy(&v33, &String, strlen(&String));
v37 = v32;
LOBYTE(v64) = 1;
newstring(&v37, 0);
strcpy(&v37, &v60, strlen(&v60));
LOBYTE(v64) = 2;
v41 = v32;
newstring(&v41, 0);
strcpy(&v41, aKxctf19q3, strlen(aKxctf19q3));
LOBYTE(v64) = 3;
if ( !check1(&v61, (int)&v45, (int)&v48) )// 以KXCTFXXXX分割字符串并判断长度，第一部分长度需大于等于4，第二部分长度需大于等于8
{
v4 = lpText;
if ( !lpText )
v4 = (const CHAR *)&unk_419144;
v31 = 0;
v30 = aBadCode;
goto LABEL_15;
}
v5 = v46;
if ( !v46 )
v5 = (const char *)&unk_419144;
if ( !strcmp(&v37, 0, v39, v5, v47) ) // 前8位是否为username
{
v56 = &input;
LOBYTE(input) = v48;
newstring(&input, 0);
substr_0(&input, &v48, 0, 0xFFFFFFFF);
v55 = &kx;
LOBYTE(v64) = 4;
strmove(&kx, &v41); // KXCTF19Q3
v53 = &un;
LOBYTE(v64) = 5;
strmove(&un, &v37); // username
v54 = &pe;
LOBYTE(v64) = 6;
strmove(&pe, &v33); // PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_
LOBYTE(v64) = 3;
if ( !check2((int)hDlg, pe, v17, v18, v19, un, v21, v22, v23, kx, v25, v26, v27, (char)input, v29, (int)v30) )
{
v8 = v34;
if ( !v34 )
v8 = (const CHAR *)&unk_419144;
MessageBoxA(hDlg, v8, aBadCheck, 0);
if ( v42 )
{
v9 = (_BYTE *)(v42 - 1);
v10 = *(_BYTE *)(v42 - 1);
if ( v10 && v10 != -1 )
*v9 = v10 - 1;
else
sub_40DF24(v9);
}
v42 = 0;
v43 = 0;
v44 = 0;
if ( v38 )
{
v11 = *(_BYTE *)(v38 - 1);
v12 = (_BYTE *)(v38 - 1);
if ( v11 && v11 != -1 )
*v12 = v11 - 1;
else
sub_40DF24(v12);
}
v38 = 0;
v39 = 0;
v40 = 0;
if ( v34 )
{
v13 = *(v34 - 1);
v14 = (CHAR *)(v34 - 1);
if ( v13 && v13 != -1 )
*v14 = v13 - 1;
else
sub_40DF24(v14);
}
v34 = 0;
v35 = 0;
v36 = 0;
v64 = -1;
goto LABEL_41;
}
success(hDlg);
LOBYTE(v64) = 2;
newstring(&v41, 1);
LOBYTE(v64) = 1;
newstring(&v37, 1);
if ( v34 )
{
v6 = (CHAR *)(v34 - 1);
v7 = *(v34 - 1);
if ( v7 && v7 != -1 )
*v6 = v7 - 1;
else
sub_40DF24(v6);
}
v31 = sub_40B410;
v30 = (const CHAR *)2;
v29 = (char *)16;
v34 = 0;
v35 = 0;
v36 = 0;
v64 = -1;
input = &v45;
}
else
{
v4 = v46;
if ( !v46 )
v4 = (const CHAR *)&unk_419144;
v31 = 0;
v30 = aBadName;
LABEL_15:
MessageBoxA(hDlg, v4, v30, (UINT)v31);
LOBYTE(v64) = 2;
newstring(&v41, 1);
LOBYTE(v64) = 1;
newstring(&v37, 1);
LOBYTE(v64) = 0;
newstring(&v33, 1);
v64 = -1;
LABEL_41:
v31 = sub_40B410;
v30 = (const CHAR *)2;
v29 = (char *)16;
input = &v45;
}
`eh vector destructor iterator'(input, (unsigned int)v29, (int)v30, v31);
return 0;
}
}
}check2函数伪代码太长了，就不放了，说下主要流程。
主要是计算一些字符串的hash作为大数，用LUC算法解密两次被KXCTFXXXX分割的第二部分input转成的大数，比较结果是否为0xC4B73CB0DD1D750C69E1755B06BBAFFFF44D2600。
总结一下就是：
N=0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01 message=0x9071232E6B170092668255303E5D824F2879AD56+inputnum message2=LUCdecrypt(message,0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133,N) message2+=0x249BA36000029BBE97499C03DB5A9001F6B734EC (LUCdecrypt(message2,N,N)+0x6DC844C73B34D6E6B8DE48DA64EF92AB2B11F461) % N==0xC4B73CB0DD1D750C69E1755B06BBAFFFF44D2600 //(LUCdecrypt(message2,N,N)% N==0x56EEF7E9A1E89E25B1032C80A1CC1D54C93B319F
怎么得到0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133的？
LUC( v206, // input+... v207, big_Nadd1, v209, big_Index, // 第一轮为：hash+KXCTF19Q3 // 第二轮为：~hash v211, big_Ncp, v213, (int *)v214, //U (int *)v215, //V (int *)v216);
第一次解密，CM是将其分成两步来算的，第一步取得Lucas序列第 hash+KXCTF19Q3项的值，第二轮取第~hash项的值。
之后将第二轮的U,V值做72次快速递推，换算到项数上就是 ~hash * 2 ^ 0x72 = ~hash * 0x1000000000000000000。
然后再进行一次递推：
v169 = big_mul((int)&v263, (int *)v234, (int *)&v235); LOBYTE(v362) = 122; v170 = (int *)big_mul((int)&v258, (int *)&v243, (int *)v239);// v243=(input+...)^2-4 LOBYTE(v362) = 123; v171 = big_mul((int)&v256, v170, (int *)&v240); LOBYTE(v362) = 124; v172 = (int *)big_add((int)&v246, v171, v169); LOBYTE(v362) = 125; v173 = (int *)big_mod((int)&v237, v172, big_hash64); LOBYTE(v362) = 126; big_cpy((int *)&v251, v173); LOBYTE(v362) = 125; free(&v237); LOBYTE(v362) = 124; free(&v246); LOBYTE(v362) = 123; free(&v256); LOBYTE(v362) = 122; free(&v258); LOBYTE(v362) = 18; free(&v263); big_num = (char *)&v215; strmove_0((int *)&v215, big_hash64); big_shr1((int *)&v251); v174 = (int *)big_add((int)&v237, (int)&v251, (int)&v271);// username
精简一下message2=((v243*v239*v240+v234*235 mod 0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01)>>1)+ 0x249BA36000029BBE97499C03DB5A9001F6B734EC //username
再加上一条性质：
将第二轮的项数和第一轮的项数相加（hash是20字节的），就得到0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133了。
之后，用LUC算法把0x56EEF7E9A1E89E25B1032C80A1CC1D54C93B319F加密回去就行，具体步骤如下：
1.分解N（N=0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01）
用ppsiqs或者在线分解都可以。分解得到：128959*277879388132275220363*804543020813130593505380215293268595059305396789149 = N。
2.计算它们的平方-1相乘的结果，也就是：
(128959^2-1)*( 277879388132275220363 ^2-1)*( 804543020813130593505380215293268595059305396789149 ^2-1)=0xFDEE7B2FD689345E05543994931E971838A18B641E848A1EEAA9D93353AF6595CFAC531583E0694776464966283075356167F8C8240C43533BCB281DE24E000（M）
3.求逆元
分别求出d1 * 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133 mod M = 1d2 * 0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01 mod M = 1
求得
d1 = 0xAC79CC5A4E51DFDF32C3234C5ABE56E90DF14AF9F0F659515C21C969F2B293EB7ED8C13072B634372A7EE3428573CA6655F11A369B1BCCE3FF76D4FE29191FB
d2 = 0xA8656E606751D95C207210B59A1ECB880B59F633BA64BF15367614212FBF642D0310EF5C6B1114B688B1E24EB03BA2DDF8725E63887AA9DA9555FDE6D9E0501
4.用d1，d2进行LUC加密（加密和解密其实用的同一个函数）
message2 = 0x56EEF7E9A1E89E25B1032C80A1CC1D54C93B319Fmessage = LUCencrypt(message2,d2,N) - 0x249BA36000029BBE97499C03DB5A9001F6B734EC
result = LUCencrypt(message,d1,N) - 0x9071232E6B170092668255303E5D824F2879AD56
解得
message = 0xD9C518135ED505550BE71C2430C33DFA16D8F8CFDF7F1FDD4C5471EAC2089D5
result = 0x753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
故flag为
usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
参考资料：
公钥加密算法LUC的并行实现方法
Some Remarks on Lucas-Based Cryptosystems
合作伙伴
上海纽盾科技股份有限公司（www.newdon.net）成立于2009年，是一家以“网络安全”为主轴，以“科技源自生活，纽盾服务社会”为核心经营理念，以网络安全产品的研发、生产、销售、售后服务与相关安全服务为一体的专业安全公司，致力于为数字化时代背景下的用户提供安全产品、安全服务以及等级保护等安全解决方案。
声明：该文观点仅代表作者本人，转载请注明来自看雪