《 CTF 2019Q4 readyu's crackme 四季之歌 设计思路 》
20191124 版本
说明：密码学题目， VC++ 编译的Win32程序，取名“四季之歌”。
#1 序列号
这个程序默认只有一个SN，用户名内置为test。输入正确的SN提示good，错误的SN提示bad。
本题唯一序列号SN为：
test_KXCTF_flag{15011-45E75CD17B6411B91786C70A5D8627ED488DFC5BA-3680C3560AFC35998540EC8B4E259D93CC8EC999B}
就方程本身而言，每个name有1个key。格式为 ：name_KXCTF_flag{Z-Y-X}
Z,Y,X 都是大写字母的hex digit number，非0开头，对应一个射影平面上点的坐标G(X,Y,Z)。
彩蛋（额外赠送的）进入方式：
(a) SN验证通过，再点击2下，可进入解锁模式，可针对不同的用户名验证SN。
(b) SN框内输入11个字符，点击check： ////debugq4
#2 算法模型与解题分析
本题验证爱德华椭圆曲线上 “点加” 的相遇等式，
求 G。
G是未知量，其余的点和参数都是已知量。
L + G = M
或者记作:
L(G, hash1, m) + G = M(G, hash2, n
)
再展开，记作：
3^365*[ 12*(R1+R2+R3+R4) + h1*G ] + G = 2^365 *[ 4(W1 + W2 + W3 + W4) + h2*G ]
故事概要：在
爱德华
曲线的时空里， 李雷(L)和韩梅梅(M)从某一点G同时出发， 以不同步长走了365天，最终发现仅有一步之遥（G），就牵手成功。
下面会详细展开，讲述这个故事。
2.1 引言：爱德华椭圆曲线上的加法循环
2.1.1 从爱德华椭圆曲线说起
看雪的2019 Q1到Q3， 我出的三个题目分别为 Q1 欧拉函数（“青梅竹马”）之 多因子小素数RSA ，Q2 一石二鸟（“开启时间之轮” ）之 二次剩余与离散对数，
Q3 完璧归赵（“大圣归来”）之Lucas序列上的RSA。 Q4继续沿着公钥密码学前行，这一次，采用了爱德华椭圆曲线模型。
我们知道，最常用的模p的素数域内的椭圆曲线方程，为 Weierstrass 形式：
y^2 + a1*x*y + a3*y= x^3 + a2*x^2 + a4*x + a6 (mod p) ... (0)
当域的特征不为2或者3时（p取大素数），Weierstrass 短形式可记为：
y^2 = x^3 + a*x + b (mod p) ... (1)
2007 年,Edwards curve被引入密码学，其特点是 加法与倍加的公式统一（可以抵抗计时攻击，能量攻击等），运算效率高。
这种曲线由数学家Harold Edwards 研究得出， 被密码学家 Daniel J. Bernstein 和 Tanja Lange 引入到椭圆曲线密码学应用里。
参考： https://en.wikipedia.org/wiki/Harold_Edwards_(mathematician)
Edwards
曲线的典型应用为EdDSA
(Edwards-curve Digital Signature Algorithm )
, 在RFC8032 有规范描述。
用以取代传统
Weierstrass
椭圆曲线上使用的ECDSA (Elliptic Curve Digital Signature Algorithm）。
参考： https://en.wikipedia.org/wiki/EdDSA
这类曲线具有非常简洁的方程，通用形式称之为 Twisted Edwards Curve（扭爱华德曲线），仅含有两个有理参数a和d, 并且 a*d(a-d) != 0 .
a*x^2 + y^2 = 1 + d*x^2*y^2 ... (2)
或者，它的一个等价写法是：
x^2 + a*y^2 = x^2*y^2 + d ... (3)
特别是，a=1称之为 Edwards curve（爱华德曲线），它具有很优雅的几何图像，这条平面曲线图形是轴对称和中心对称图形，因此它有四块。
这个特点很重要，自然地想到Edwards curve 上的点数，总是4的倍数，因此它是Weierstrass curve的一个特例：
x^2 + y^2 = 1 + d*x^2*y^2 ... (4)
可以作图： d = 100, 10, (1), 1/10, 1/100, 0 , 1/100, -1/10, -1, -10, -100
我们想象一下（可以用wolframalpha作图看一下），d的变化（因为a=1， 所以d !=1, 否则退化为井字型四条直线）：
d从大的正有理数比如100,10,到 1/10,1/100， 再变为0，然后变为负有理数 -1/100,-1/10, -1, -10, -100,
这一过程中，d*x^2*y^2 这一项的影响：
导致曲线从发散的四瓣形，收敛到单位圆，再压扁到四角星形。如果d -> 0 将退化为1个单位圆 。
实际上，可以做一个动画， 随着d的减少，曲线从发散的四瓣形逐渐变得丰满圆润，最后充满到整个单位圆，然后苗条到尖锐，变成四角星形。
2.1.2 椭圆曲线上“加法”的一个初等比喻
我们知道，椭圆曲线上的有理点基本运算是 可交换群（阿贝尔群）的“加法”， “加法”在不同的方程形式下，有不同的表现形式。
不管方程如何变， “加法”的基本规律是不变的。那么这条曲线上有理点的“加法”，实际上在极限的情况下，应该符合单位圆上有理点的“加法”。
单位圆上有理点的“加法”，那就是在复变函数 |z|=1 做运算，要保证两个点“相加”得到的第三点，仍在单位圆上，并且要满足交换律，意味着各点平等。
这实际上对应着单位圆上复数的乘法(指数相加，而模长不变)，就是角度旋转，欧拉公式揭示了这一点。
e^(i*φ) = cos(φ) + i*sin(φ) ... (4)
给定2个点：
P1 （X1，Y1）= cos(A) + i*sin(A) , P2
（X2，Y2）
= cos(B) + i*cos(B) ... (5)
加法定义为：
P3（ X3，Y3） = P1 + P2 = cos(A+B) + i*sin(A+B) ... (6)
"加法"这样计算： (x1,y1)+(x2,y2)=(x3,y3)
显然，当P1，P2均为单位圆上的有理点，它们的“加法和” P3 仍然是单位圆上的有理点，并且是唯一的。这里面蕴含着朴素的群论思想,群里的点加，始终在这群里。点在单位圆上这么运行，进而推广到点在四角星形，四瓣形上的运行，就好比时间的轮回，一年四季春夏秋冬这么循环着，也就是这道题目名字“四季之歌”的寓意。
以上只是从初等几何和初等复变函数的观点解释 爱德华曲线，让它形象一点，在人的脑海里动起来。此处可以参考wiki上的词条：
https://en.wikipedia.org/wiki/Edwards_curve
其中有一幅 Clock group 的单位圆示意图。
但是，请注意，应用到椭圆曲线加密，椭圆曲线不再具有几何图像。因为加密上用的是模素数P的整数点，是有限域内的点的集合，这些点构成一个可交换的加法群（称为阿贝尔群）。这些点在模P下才能满足方程，与原本的几何曲线上的点已经没有什么关系了。
2.2 本题的椭圆曲线方程与算法
2.2.1 椭圆曲线方程的参数
X^2 + a*Y^2 = X^2*Y^2 + d mod p ... (7)
采用以下参数：
p= 7182818284590452353602874713526624977572470936999
a= 2019
d= 3033
p的取值：自然对数的底e的十进制展开，小数部分前49位，恰好是一个素数，在程序里用代码计算e的展开序列，生成这个素数。
bits=163, p =
7182818284590452353602874713526624977572470936999
a的选择，取2019年的意思；然后d：搜索了1到9000以内的d，得到比较适合的一个数值, np/4是一个素数。
这条曲线的点数（number of points ）:
np = 7182818284590452353602871807190217533637006531716
prime_order = np/4 = 1795704571147613088400717951797554383409251632929
2.2.2 爱德华椭圆曲线点数的计算
这里的算法需要参考wiki上的
Montgomery_curve （
蒙哥马利曲线，Peter L. Montgomery 1987年提出，当时他在读博士年纪40岁，研究用椭圆曲线分解整数因子，即ECM， 发现使用这类曲线计算上有优势， University of California, Los Angeles）。
Peter L. Montgomery还有一个知名的贡献是
Montgomery reduction，在RSA幂模运算里常用。参考页面：
https://en.wikipedia.org/wiki/Peter_Montgomery_(mathematician)
Montgomery 属于
Weierstrass曲线的一类特例，以下页面描述了这一变换。
https://en.wikipedia.org/wiki/Montgomery_curve
参考这一节 # Equivalence with twisted Edwards curves
一条爱德华曲线，双向有理等价于 一条蒙哥马利曲线（一个知名的特例是 Ed25519: 蒙哥马利曲线
与 扭爱德华曲线 的等价）
。
所以，爱德华
曲线点数的计算方法：转换为Weierstrass形式，用schoof算法计算。
可通过miracl lib里的schoof.cpp源代码，自己编译一个schoof.exe计算出来。或者用sage math计算。
使用sage 更方便一些，代码如下：
# Sage Math Code by readyu @20191124
# sage math find Edwards Curve Number Points:
# a*x^2 + y^2 = 1 + d*x^2*y^2 mod p
# prime 163 bits - cpu time cost about 1 seconds
t = cputime()
p=7182818284590452353602874713526624977572470936999
a=2019
d=3033
R=IntegerModRing(p)
A = R(2*(a+d)) / R(a-d)
B = R(4)/R(a-d)
a1 = 0
a3 = 0
a2 = A*B%p
a4 = B*B%p
a6 = 0
set_verbose(2)
print "Edwards Curve: a*x^2 + y^2 = 1 + d*x^2*y^2 mod p "
print "p=%d" %(p)
print "a=%d" %(a)
print "d=%d" %(d)
print "Weierstrass Model:"
print "y^2 + a1*x*y + a3*y= x^3 + a2*x^2 + a4*x + a6"
print "a2 = %d" %(a2)
print "a4 = %d" %(a4)
E=EllipticCurve(GF(p),[a1,a2,a3,a4,a6])
np=E.cardinality()
print "np = %d" %(np)
order = Integer(np)
while order%2 == 0 :
order = Integer(order/2)
cof = Integer(np/order)
if order.is_prime() :
print "prime order(np/%d) = " %(cof)
print "%d" %(order)
t = cputime(t)
print "cpu time cost %.3f seconds" %(t)
#End of file
放到在线的sagecell 运行， 也可以PC上安装一个sage，运行。
https://sagecell.sagemath.org/
结果：
Edwards Curve: a*x^2 + y^2 = 1 + d*x^2*y^2 mod p
p=7182818284590452353602874713526624977572470936999
a=2019
d=3033
Weierstrass Model:
y^2 + a1*x*y + a3*y= x^3 + a2*x^2 + a4*x + a6
a2 = 4484409758247046184232953793931039722585130776278
a4 = 5916368345885347562026212334888880044763786492373
np = 7182818284590452353602871807190217533637006531716
prime order(np/4) =
1795704571147613088400717951797554383409251632929
cpu time cost 0.819 seconds
2.2.3 爱德华椭圆曲线上的加法公式
曲线可以写成：
2019*x^2 + y^2 = 1 + 3033*x^2*y^2 mod p ... (8)
或者写成双向有理等价形式：
x^2 + 2019*y^2 = x^2*y^2 + 3033 mod p ... (9)
射影坐标：
(X^2 + 2019*Y^2)*Z^2 = X^2*Y^2 + d*Z^4 ...(10)
简要证明如下：
E(a,d): a*x^2 + y^2 = 1 + d*x^2*y^2 ...(a1)
=> 有理变换，令 X = 1/x, Y = 1/y
=> a/X^2 + 1/Y^2 = 1 + d/（X^2*Y^2）
=> 两边同乘以 X^2*Y^2
E'(a,d): a*Y^2 + X^2 = X^2+Y^2 + d ... (a2)
所以 (a1) 与 (a2) 等价。
对这样一条曲线： a*x^2+y^2=1+d*x^2*y^2 ，
两个有理点的加法这样定义： (x1,y1)+(x2,y2)=(x3,y3) Daniel J. Bernstein
x3 = (x1*y2+y1*x2)/(1+d*x1*x2*y1*y2)
y3 = (y1*y2-a*x1*x2)/(1-d*x1*x2*y1*y2)
题目里，为了加快计算效率，采用倒置的射影坐标(X,Y,Z)，Inverted coordinates。
在 (a1) 中，令 x = Z/X, y = Z/Y
a*(Z^2/X^2) + Z^2/Y^2 = 1 + d*Z^4/(X^2*Y^2)
=> 两边同乘以 X^2*Y^2
(X^2 + a*Y^2)*Z^2 = X^2*Y^2 + d*Z^4 ...(b1) 参见 Twisted Edwards Curves pp12-13 of total page 17, Daniel J. Bernstein
(b1)的加法形式 (X3, Y3, Z3) = (X1, Y1, Z2) + (X2, Y2, Z2) , 按如下规则计算：
X3 = (X1*X2 - a*Y1*Y2) * (X1*Y1*X2*Y2 + d*Z1^2*Z2^2)
Y3 = (X1*Y2 + Y1*X2) * (X1*Y1*X2*Y2 - d*Z1^2*Z2^2)
Z3 = Z1*Z2*(X1*X2 - a*Y1*Y2)(X1*Y2 + Y1*X2)
2.3 本题的算法模型
倒置的射影坐标 扭爱德华曲线方程:
(X^2 + 2019*Y^2)*Z^2 = X^2*Y^2 + 3033*Z^4 mod p ...(11)
在椭圆曲线上，已知条件：两组点，每组4个点 R1-R4， W1-W4， 再给定h1，h2, 求出：G(X,Y,Z) 满足如下关系：
如下方程，恒有唯一解G，意味着G点，有且只有一个。
3^365*[ 12*(R1+R2+R3+R4) + h1*G ] + G = 2^365 *[ 4(W1 + W2 + W3 + W4) + h2*G ] ... (12)
简而言之, 题目最终验证这样一个等式：
L + G = M ... (13) ， 并且 L, M 都在曲线(11) 上。
其中 L = 3^365*[ 12*(R1+R2+R3+R4) + h1*G ] , M = 2^365 *[ 4(W1 + W2 + W3 + W4) + h2*G ] ...(14)
用文字描述 L + G = M 这个故事：
从 扭爱德华椭圆曲线(p,a,d) 上选取4个点作为x坐标，称为四季点：立春，立夏， 立秋， 立冬， 再选取其hash映射的4个点, 两组一一对应。
在这个椭圆曲线的时空里，李雷(L)和韩梅梅(M)从某一点G同时出发， 左右初始化， 然后叠加四季点，左边12倍之（寓意十二个月），右边4倍之（寓意四季） ，
然后开始前进： 李雷 一天走三步， 梅梅 一天走两步， 经过365 天（寓意一年）， 最终 李雷 再加上一步， 与梅梅 再次相遇。
一个向左，一个向右，李雷和梅梅以不同步长走了365天，最终发现仅有一步之遥，再加一步就牵手成功。
方程(12)的解法, 用符号代替, 实际操作形同初等数学里的解一元一次方程：
m*[ 12*(R1+R2+R3+R4) + h1*G ] + G = n*[ 4*(W1+W2+W3+W4) + h2*G ] ... (15)
=> 把未知量G都移到方程的左侧，然后就得到G：
(m*h1 - n*h2 + 1) G = 4[n(W1+W2+W3+W4) - 3*m(R1+R2+R3+R4)]
=>
G = 4 * invmod(m*h1 - n*h2 + 1, np) * [n(W1+W2+W3+W4) - 3*m(R1+R2+R3+R4)] ... (16)
其中： m = 3^365, n=2^365,
h1 = 1 + 365 + (H1 % (365 + H1 % 2019) >> 1) << 1) // even ，偶数
h2 = 1 + 365 + (H1 % (365 + H2 % 3033） >> 1) << 1) // even ，偶数
h1 和 h2 为偶数， 这样确保 w = (m*h1 - n*h2+ 1)为奇数, np = 4* primeorder , np是偶数且仅含有大素数因子primeorder，
所以 gcd(w, np) = 1, 于是w模np的逆，即 w(^-1) mod np 存在，保证了方程有唯一解。
2.4 本题的参数与解答：
四季点的坐标(16进制):
R1(x,y,z) = (20190204, 294F20E7B5DC2D408E4D05A35FACEB13D3DCF5C69, 1)
R2(x,y,z) = (20190506, 6458A8D5AEEE40A2C95B667FC705F19112E17397, 1)
R3(x,y,z) = (20190808, 330A0818BC327794D974BA7AA8070AB6917482491, 1)
R4(x,y,z) = (20191108, 2F5AE3DEC2A4D95E9E01A2B6D9F226162BBE2B3AD, 1)
计算Rx[i]的sha1 hash如下：
sha1-hash-hex-byte(20190204) ed8531111214bc69c1fd64adbe59ab9fb14687ed
sha1-hash-hex-byte(20190506) 1f0a0d84eafc1b108fe21c0d707f2a2ef76b6d52
sha1-hash-hex-byte(20190808) 6e2acf46fcc73564c4d84f566a558ed748fafe2e
sha1-hash-hex-byte(20191108) a4ca755463fc535192413dabf67c2c84ab86cd20
四季hash点的坐标(16进制):
W1(x,y,z) = (ed8531111214bc69c1fd64adbe59ab9fb14687ed, 272ACFA35A56FB05D605D2B2F5B40E3AC4AAE8DDB, 1)
W2(x,y,z) = (1f0a0d84eafc1b108fe21c0d707f2a2ef76b6d52, 25A64AB69A29FF329A5BE8A7AFF8199602B890DAB, 1)
W3(x,y,z) = (6e2acf46fcc73564c4d84f566a558ed748fafe2e, 3489928D307F9D8C13D00ABA0065C262ECA4683AF, 1)
W4(x,y,z) = (a4ca755463fc535192413dabf67c2c84ab86cd20, 109F4C008A5E1BD1C3427796889230722A4AC40EB, 1)
G = 4 * invmod(m*h1 - n*h2 + 1, np) * [n(W1+W2+W3+W4) - 3*m(R1+R2+R3+R4)]
简化之： 记 k = 4 * invmod(m*h1 - n*h2 + 1, np) mod np ， T = n(W1+W2+W3+W4) - 3*m(R1+R2+R3+R4)
于是 G = k * T ， k是一个数值， T是点的坐标T(x,y,z)
所有量已知，可以求得T(Tx,Ty,Tz):
Tx= 45541CE1CAE581BA6A21204F2611D05B1B9299CEC , Ty= 2DD8AFD9115FE66385D4B356A31A1EB3C13E30B5D , Tz= 1
k是与h1,h2有关的数值（用户名的hash运算得出），意味着一个用户名对应一个k。
所以 G = f(name, T) 是一个用户名对应一个key的。
我们再来看这个方程：
(X^2 + a*Y^2)*Z^2 = X^2*Y^2 + d*Z^4 ...(b1)
这里要特别注意射影坐标的线性关系，因为爱德华曲线是齐次的，(x,y,z) 与(kx,ky,kz) 是同一个点。
也就是说，开始取z=1，椭圆曲线上一点G(x,y,1) ，当Z变动时( Z !=0 mod p) , G(Z*X, Z*Y, Z) 和 G(x,y,1) 是同一点。
G(x,y, 1) = G(Z*X, Z*Y, Z) , for any Z = [1, P-1] , 对(X,Y)固定，Z可以取P-1种可能。
为了使得flag对Name唯一，题目中必须用name信息去约束Z，使之唯一。这里采用HASH取余数，称之为 (checksum + delta) 来约束。
以name = test为例子，题目取
head = "KXCTF2019Q4_Crackme_by_Readyu_四季之歌"
name = "test"
full = "KXCTF2019Q4_Crackme_by_Readyu_四季之歌_test"
对应3个hash：
H1= hash(KXCTF2019Q4_Crackme_by_Readyu_四季之歌)=
ac7fc2865d908c75fc6698c3b0aaa9cb89515185
H2= hash(name)=
a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
H3= hash(KXCTF2019Q4_Crackme_by_Readyu_四季之歌_test)=
047e8e0068522d9d32c36b28279759d657072e0d
checksum 用如下代码生成：
unsigned int checksum = 0x10000; // 初始化，以保证 at least 5 hex-digits
for(i = 0; i < 20; i++)
{
checksum += (unsigned int) H1[i];
checksum += (unsigned int) H2[i];
checksum += (unsigned int) H3[i];
}
if(checksum % 2019 != 0)
checksum += 2019;
if(checksum % 3033 != 0)
checksum += 3033;
if(checksum % 365 != 0)
checksum += 365;
delta = (Gx + Gy + H3) % (2019+3033+365);
Gz = checksum + delta
Gz 就被约束为一个16进制的5位数，大大减少了SN的长度，并且由name唯一确定了。
在本题中：给定name，可以得出：
The Flag is k * T(x,y,z), k = 4411616999826018012798317037064642790047178656264, z = 15011
name=test, flag=
test_KXCTF_flag{15011-45E75CD17B6411B91786C70A5D8627ED488DFC5BA-3680C3560AFC35998540EC8B4E259D93CC8EC999B}
因为椭圆曲线点的运算涉及到大整数乘法，取模等运算，用文字描述不太方便，我这里给出了keygen的源代码。
crackme里只用到点的加法， 而写keygen，则必须用到点的加法，再用二进制展开法实现点的倍乘。
详细运算过程，参加 附件里的 edwards_keygen.cpp
补充说明：（彩蛋）
如果进入彩蛋模式，可解锁用户名。
比如用户名： 四季之歌
name=四季之歌, flag=
四季之歌_KXCTF_flag{1549C-411147C1B409EC1B1C731895DC048039FFAA217BF-316AC5FE4265868E04C3A3B5148B204902ADC4504}
#3 参考文档， 见附件打包下载。
文档（已上传）：
013_Twisted Edwards Curves-20080313.pdf
代码（回帖附上）：
keygenme2019q4_a2019_keygen.rar
crackme主程序
（已上传）
：
crackme2019q4_readyu_四季之歌.exe
Size: 119296 bytes
File Version: 1, 0, 0, 1
Modified: 2019年11月24日, 9:17:30
MD5: 661817843A8BC4469E8D5D48C1CBA833
SHA1: 1FBB5307E5088C5B47C919D39450D69FFF7466DF
CRC32: BDBA1A39
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2019-12-27 15:21
被readyu编辑
，原因：
上传的附件：
