2019 KCTF 晋级赛Q1 | 第五题点评及解题思路
郎骑竹马来，绕床弄青梅。同居长干里，两小无嫌猜。
当李白《长干行》中的“青梅竹马”穿越千年隐藏在代码中，会产生怎样的化学反应呢？接下来，让我们来探寻一下这其中的关联吧！
此题仅有20 支队伍攻破此题目，围观人数为2206 人。
出题战队
战队成员：readyu
个人主页：https://bbs.pediy.com/user-23454.htm
个人简介：毕业于中国科学技术大学自动控制专业，从事软件开发多年。在软件保护技术、加密算法方面有一些体验。曾在北京多看科技从事电子阅读加密技术的研究，以及在MIUI从事系统安全方面工作。
看雪CTF crownless 评委 点评
这道题结合了密码学和简单的逆向，需要参赛者对RSA算法、密码学基础十分熟悉。此外，这道题取名“青梅竹马”，意指小素数的组合，十分形象贴切。
题目设计思路
根据规则，crackme SN唯一且为大小写字母+数字。
本题CODE为： PEDIyV9102dVreadyu
正确提示：yes, correct sn!
crackme 取名 青梅竹马 ，意指代 小素数的组合， 字面隐含谜底 "两小无猜" （方程右边为2） 。
设计思路:
（1）原始解：M
考虑100以内的素数，顺序生成一个数列:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
基于这些小素数的乘积，根据RSA的原理拓展出一个题目。
第一项2， 比较特殊，把它排除开来，然后考虑N适当的长度，经过计算，取
N = 3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73 =
20364840299624512075310661735
N的欧拉函数计算如下：
φ(N)=
2*4*6*10*12*16*18*22*28*30*36*40*42*46*52*58*60*66*70*72 =
5133855159158901099724800000
然后在后续较大的其余项里，任取一个素数，比如取 e = 83，建立一个幂模方程。
求解大整数M ( 2 < M < N), 使得M^e = 2 mod N
等价于求解:
e*d = 1 mod φ(N) , 且 1 < d < φ(N)
2^d = M mod N , 且 2 < M < N
由前面的条件可知，
(a) N的素因子不包含2；
(b) 并且 φ(N) 的每个因子项都小于e， 且e是一个素数, 所以e，φ(N)互素, 那么逆元d存在。
所以上面方程有唯一解(d, M)。
计算可得
d = 1/e mod φ(N) = 1855610298491169072189686747
所以
M = 2^d mod N = 6602940601029543050476765433
转为16进制的大数：
M = 1555D30F38B0DBCAEC83C0F9
M就是最原始的解。
（2）M转换为有意义的CODE
为了使得M “看起来有意义” ，用base64缩短，嵌入信息，伪代码如下：
M = HEX(1555D30F38B0DBCAEC83C0F9) ,
M长度为12个字节， 相当于3个int32。
base64table=
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
M_b64= FVXTDziw28rsg8D5
然而这个注册码并不具有明确意义。
做字母替换，可以手动计算取一个特殊的
custom_base64table=
ABCyVPGHTJKLMNOFQRSIUEWDYZgbc8sfah1jklmnopqret5v0xX9wi234u67dz+/
得到
SN = M_b64(custom_base64table)
= PEDIy9102dreadyu
起初打算把注册码定为
code = PEDIy-9102d-readyu
考虑到规则只允许用数字和字母，用V做分隔符，最终code定为：
CODE = PEDIyV9102dVreadyu
注册码判断的提示信息，也用前面的custom_base64table 编码了。
"bmdeTH8Xb2unTHN5TSVhTQ" // no, wrong sn!!!!
"bWzXZSB3b3JrTHRvTGRvTQ" // more work to do!
"sWE9LCBjb3JXZWNwTHN5TQ" // yes, correct sn!
"c24aZGzlc24n8CB3b3JrTQ" // sn doesn't work!
程序里的custom_base64table简单地异或加密，避免暴露明文, 每一项 c[i] ^ 0x50
（3）验证注册码
1. 对code有效字符集和长度作检测, 不通过的，提示错误信息。trim后得到干净的sn。
2. sn 通过custom_base64 decode转换为hex M，也就是一个大整数。
3. 用筛法生成100以内的小素数列表，primes[i]。
4. 计算N = 3*5*7...*73 （p=79时截止，79=0x4F，恰好是大写字母O的ascii值）。
5. 判断输入 2 =< M <= N, 不通过的，提示错误信息。
6. 计算大整数 X = M^e mod N , 其中e=83, 程序里固定。
X转换回int值，最多只能转换32bit。
bits(X) >= 32 bit时，转换为INT_MAX， 提示 sn doesn't work!
当且仅当 bits(X) <32bit, 并且X=2 时，提示 yes, correct sn!
说明：
大整数运算采用polarssl-0.10 里的bignum.c/bignum.h，这个库比openssl, gmp, miracl 等常见大整数运算库小巧很多。
https://tls.mbed.org/download-archive
为了使代码尽可能简单，M^e mod N 没有采用bignum里面的mpi_exp_mod()。
考虑到e是一个小指数，采用的是power left to right的简单算法。
解题思路
本题解题思路由梦游枪手 提供
打开程序，随便输入点什么，弹出'no,wrong sn!!!"。
在MessageBoxA下断，回溯到402652，用IDA分析，下面的代码我已经分析过并重命名函数了。
