-
-
[推荐]2019 KCTF 总决赛 | 第九题《四季之歌》点评及解题思路
-
2019-12-27 18:03
-
1、题目简介
霓虹闪烁，交通工具在建筑物之间穿梭，抬头可以看到巨型的立体灯牌和全息投影。
地面是透明的，可以看到地下深不见底，建筑破败老旧，在雨夜中显得十分深沉。
经过一番调查我发现这个空间整体是一个巨大的时钟，每天向前走一格，昼夜交替，四季更迭，上层的人们永远享受着春夏秋冬，时钟指向12，空间再次重置，一切又重新出发。
下层人们的大半辈子都在黑夜里无限循环，度过365天，他们在另一个黎明时分转向地下。
四季在这个空间里仿佛是一个闭合之环，人们害怕的不是未知， 而是提前知道自己的命运。
时间是个圈，空间是个圈，宇宙也是个圈。圈里的人在四季轮回中无限循环，而我要怎么帮助他们？
这个谜题等待我去探索。
[说明：本题是一道Windows逆向题]
本题攻破人数较少，可见其难度较大，接下来让我们一起来看一下这道题的点评和详细解析吧。
2、看雪评委crownless点评
这道题的密码学部分比较难，考查了对公钥密码学中椭圆曲线的理解，要求在理解题目算法的基础上实现点乘算法，具有一定的复杂度。
3、出题团队简介
团队简介：readyu的米兔安全小分队。
4、设计思路
一、序列号
本题唯一序列号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
本题验证爱德华椭圆曲线上 “点加” 的相遇等式， 求 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），就牵手成功。
G点的坐标(X,Y,Z)对应了Flag。
下面会详细展开，讲述这个故事。
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被引入密码学，其特点是 加法与倍加的公式统一（可以抵抗计时攻击，能量攻击等），运算效率高。
二、算法模型与解题分析
本题验证爱德华椭圆曲线上 “点加” 的相遇等式， 求 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），就牵手成功。
G点的坐标(X,Y,Z)对应了Flag。
下面会详细展开，讲述这个故事。
引言：爱德华椭圆曲线上的加法循环
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. 椭圆曲线上“加法”的一个初等比喻
我们知道，椭圆曲线上的有理点基本运算是 可交换群（阿贝尔群）的“加法”， “加法”在不同的方程形式下，有不同的表现形式。
不管方程如何变， “加法”的基本规律是不变的。那么这条曲线上有理点的“加法”，实际上在极限的情况下，应该符合单位圆上有理点的“加法”。
单位圆上有理点的“加法”，那就是在复变函数 |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)
x3 = cos(A+B) = cosA*cosB − sinA* sinB = x1*x2 - y1*y2
y3 = sin(A+B) = sinA*cosB + cosA * sinB = x1*y2 + y1*x2
显然，当P1，P2均为单位圆上的有理点，它们的“加法和” P3 仍然是单位圆上的有理点，并且是唯一的。这里面蕴含着朴素的群论思想,群里的点加，始终在这群里。点在单位圆上这么运行，进而推广到点在四角星形，四瓣形上的运行，就好比时间的轮回，一年四季春夏秋冬这么循环着，也就是这道题目名字“四季之歌”的寓意。
以上只是从初等几何和初等复变函数的观点解释 爱德华曲线，让它形象一点，在人的脑海里动起来。此处可以参考wiki上的词条：
https://en.wikipedia.org/wiki/Edwards_curve
其中有一幅 Clock group 的单位圆示意图。
但是，请注意，应用到椭圆曲线加密，椭圆曲线不再具有几何图像。因为加密上用的是模素数P的整数点，是有限域内的点的集合，这些点构成一个可交换的加法群（称为阿贝尔群）。这些点在模P下才能满足方程，与原本的几何曲线上的点已经没有什么关系了。
本题的椭圆曲线方程与算法
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. 爱德华椭圆曲线点数的计算
这里的算法需要参考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: 蒙哥马利曲线 与 扭爱德华曲线 的等价） 。
参考这一节 # 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
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
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)
本题的算法模型
倒置的射影坐标 扭爱德华曲线方程：
(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 存在，保证了方程有唯一解。
本题的参考与解答
四季点的坐标(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 用如下代码生成：
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}
三、参考文档
文档（已上传）：
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
5、解题思路
本题解题思路由辣鸡战队战队 xym提供：
首先进行逆向分析，这次题目和Q3的结构很像，基本是一个框架写的，因此前面的分析过程可以参考上次题目的。
最终输入要求答案具有 test_KXCTF_flag{key1-key2-key3} 的形式，其中key1可以算是key2和key3的校验，所以真正要求解的是key2和key3。
判断key2和key3是否符合条件的具体运算过程可以提炼成以下python代码。
v162_P = 0x4EA28B61F4C3B12B0B544814578629410ECCF55A7 def Add_Rol(a1): P = v162_P a1 = a1 % P if a1 < 0: a1 += P if a1 % 2: a1 += P a1 = a1 / 2 return a1 % P def sub_404860(a1, a2, a3, a4, a5, a6): P = v162_P # v61 = a1 * a5 # v60 = a2 * a4 # v59 = a3 * a6 # v58 = a1 * a4 + a2 * a5 #(a1 + a2) * (a4 + a5) - v60 - v61 # v57 = v60 - 0x7E3 * v61 # v56 = v60 * v61 # v55 = 0xBD9 * v59 * v59 # v64 = v59 * v57 * v58 v64 = (0x7E3 + 0xBD9) * a3 * a6 * (a2 * a4 - 0x7E3 * a1 * a5) * (a1 * a4 + a2 * a5) #(0x7E3 * v64 + 0xBD9 * v64) out3 = ((v64 % P + P) % P) * 2 #v63 = (v56 - v55) * v58 v63 = (0x7E3 + 0xBD9) * (a2 * a4 * a1 * a5 - 0xBD9 * a3 * a6 * a3 * a6) * (a1 * a4 + a2 * a5)#(0x7E3 * v63 + 0xBD9 * v63) out2 = ((v63 % P + P) % P) * 2 #v62 = (v55 + v56) * v57 v62 = (0x7E3 + 0xBD9) * (0xBD9 * a3 * a6 * a3 * a6 + a2 * a4 * a1 * a5) * (a2 * a4 - 0x7E3 * a1 * a5) #(0x7E3 * v62 + 0xBD9 * v62) out1 = ((v62 % P + P) % P) * 2 return out1, out2, out3 def sub_404E90(sha3,sha1,sha2,k3,k2,const0x13D00,inputadd): v163 = [0 for i in range(4)] v167 = [0 for i in range(4)] v168 = [0 for i in range(4)] v164 = [0 for i in range(4)] v165 = [0 for i in range(4)] v166 = [0 for i in range(4)] v163[0] = 0x0294F20E7B5DC2D408E4D05A35FACEB13D3DCF5C69 * 2 * 1 * inputadd * sha1 v163[1] = 0x006458A8D5AEEE40A2C95B667FC705F19112E17397 * 2 * 2 * inputadd * sha1 v163[2] = 0x0330A0818BC327794D974BA7AA8070AB6917482491 * 2 * 3 * inputadd * sha1 v163[3] = 0x02F5AE3DEC2A4D95E9E01A2B6D9F226162BBE2B3AD * 2 * 4 * inputadd * sha1 v167[0] = 0x20190204 * 2 * 1 * inputadd * sha1 v167[1] = 0x20190506 * 2 * 2 * inputadd * sha1 v167[2] = 0x20190808 * 2 * 3 * inputadd * sha1 v167[3] = 0x20191108 * 2 * 4 * inputadd * sha1 v168[0] = 1 * 2 * 1 * inputadd * sha1 v168[1] = 1 * 2 * 2 * inputadd * sha1 v168[2] = 1 * 2 * 3 * inputadd * sha1 v168[3] = 1 * 2 * 4 * inputadd * sha1 v164[0] = 0x1DB0A6222242978D383FAC95B7CB3573F628D0FDA * inputadd * sha2 v164[1] = 0x7C283613ABF06C423F887035C1FCA8BBDDADB548 * inputadd * sha2 v164[2] = 0x29500DBA9ECAB405C9D11DC067E01590BB5E1F514 * inputadd * sha2 v164[3] = 0x52653AAA31FE29A8C9209ED5FB3E164255C366900 * inputadd * sha2 v165[0] = 0x4E559F46B4ADF60BAC0BA565EB681C758955D1BB6 * inputadd * sha2 v165[1] = 0x96992ADA68A7FCCA696FA29EBFE066580AE2436AC * inputadd * sha2 v165[2] = 0x13B396F4F22FDB14876E0405C02628E518BDA7161A * inputadd * sha2 v165[3] = 0x84FA600452F0DE8E1A13BCB444918391525620758 * inputadd * sha2 v166[0] = 2 * 1 * inputadd * sha2 v166[1] = 2 * 2 * inputadd * sha2 v166[2] = 2 * 3 * inputadd * sha2 v166[3] = 2 * 4 * inputadd * sha2 v139 = sha3 * k3 v136 = sha3 * k2 v135 = sha3 * const0x13D00 v158 = sha1 * k3 v157 = sha1 * k2 v160 = sha1 * const0x13D00 v150 = sha2 * k3 v149 = sha2 * k2 v152 = sha2 * const0x13D00 P = v162_P # v128 = sha1 % (sha1%0x7E3 + 0x16D) v43 = 0x439 v44 = 0x4B7 for i in range(v43): (v158, v157, v160) = sub_404860(v136, v139, v135, v158, v157, v160) v139 = Add_Rol(v139) v136 = Add_Rol(v136) v135 = Add_Rol(v135) for i in range(v44): (v150, v149, v152) = sub_404860(v136, v139, v135, v150, v149, v152) v139 = Add_Rol(v139) v136 = Add_Rol(v136) v135 = Add_Rol(v135) for i in range(12): v167[i % 4] = (v167[i % 4] * v43) % P v163[i % 4] = (v163[i % 4] * v43) % P v168[i % 4] = (v168[i % 4] * v43) % P v158 = v158 * 0x7E3 v157 = v157 * 0x7E3 v160 = v160 * 0x7E3 (v158, v157, v160) = sub_404860(v163[0], v167[0], v168[0], v158, v157, v160) (v158, v157, v160) = sub_404860(v163[1], v167[1], v168[1], v158, v157, v160) (v158, v157, v160) = sub_404860(v163[2], v167[2], v168[2], v158, v157, v160) (v158, v157, v160) = sub_404860(v163[3], v167[3], v168[3], v158, v157, v160) for i in range(4): v164[i] = (v164[i] * v44) % P v165[i] = (v165[i] * v44) % P v166[i] = (v166[i] * v44) % P v150 = v150 * 0xBD9 v149 = v149 * 0xBD9 v152 = v152 * 0xBD9 (v150, v149, v152) = sub_404860(v165[0], v164[0], v166[0], v150, v149, v152) (v150, v149, v152) = sub_404860(v165[1], v164[1], v166[1], v150, v149, v152) (v150, v149, v152) = sub_404860(v165[2], v164[2], v166[2], v150, v149, v152) (v150, v149, v152) = sub_404860(v165[3], v164[3], v166[3], v150, v149, v152) for i in range(365): (v134, v133, v132) = sub_404860(v157, v158, v160, v158, v157, v160) v158 = Add_Rol(v158) v157 = Add_Rol(v157) v160 = Add_Rol(v160) (v158, v157, v160) = sub_404860(v133, v134, v132, v158, v157, v160) v158 = Add_Rol(v158) v157 = Add_Rol(v157) v160 = Add_Rol(v160) (v150, v149, v152) = sub_404860(v149, v150, v152, v150, v149, v152) v150 = Add_Rol(v150) v149 = Add_Rol(v149) v152 = Add_Rol(v152) v157 = v157 * 0x7E3 v158 = v158 * 0x7E3 v160 = v160 * 0x7E3 v137 = ((v158**2 + v157**2*0x7E3) * v160**2) % P v138 = (v158**2 * v157**2 + v160**2*0xBD9*v160**2) % P print "assret(v137 == v138) ",Hex(v137 - v138) print Hex(v137) print Hex(v138) v150 = v150 * 0xBD9 v149 = v149 * 0xBD9 v152 = v152 * 0xBD9 v137 = ((v150**2 + v149**2*0x7E3) * v152**2) % P v138 = (v150**2 * v149**2 + v152**2*0xBD9*v152**2) % P print "assret(v137 == v138) ",Hex(v137 - v138) print Hex(v137) print Hex(v138) v134 = v139*0x7E3 * (v158+v157+v160) v133 = v136*0x7E3 * (v158+v157+v160) v132 = v135*0x7E3 * (v158+v157+v160) v134 = Add_Rol(v134) v133 = Add_Rol(v133) v132 = Add_Rol(v132) (v158, v157, v160) = sub_404860(v133, v134, v132, v158, v157, v160) v158 = Add_Rol(v158) v157 = Add_Rol(v157) v160 = Add_Rol(v160) v137 = ((v158*v152 - (v150*v160)%P)*0x7E3)%P #(v158*v152)%P == (v150*v160)%P v138 = ((v157*v152 - (v149*v160)%P)*0xBD9)%P #(v157*v152)%P == (v149*v160)%P print "assret(v137 == 0) ",Hex(v137) print "assret(v138 == 0) ",Hex(v138) sha1 = 0xac7fc2865d908c75fc6698c3b0aaa9cb89515185 sha2 = 0xa94a8fe5ccb19ba61c4c0873d391e987982fbbd3 sha3 = 0x047e8e0068522d9d32c36b28279759d657072e0d key1 = 0x6789 key2 = 0xABCDEF223456789 key3 = 0xABCDE sub_404E90(sha3, sha1, sha2, key3, key2, 0x13D00, 0x2507A)
根据sub_404860里面的运算，发现可以对每组数的公因子进行消除而不影响最后结果，因此可以对题目进行化简。
最后发现Add_Rol应该也不会影响结果，所以得到化简版的代码如下：
v162_P = 0x4EA28B61F4C3B12B0B544814578629410ECCF55A7 Const_0x7e3 = 0x7e3 Const_0xBD9 = 0xbd9 v163 = [0 for i in range(4)] v167 = [0 for i in range(4)] v168 = [0 for i in range(4)] v164 = [0 for i in range(4)] v165 = [0 for i in range(4)] v166 = [0 for i in range(4)] v163[0] = 0x0294F20E7B5DC2D408E4D05A35FACEB13D3DCF5C69 v163[1] = 0x006458A8D5AEEE40A2C95B667FC705F19112E17397 v163[2] = 0x0330A0818BC327794D974BA7AA8070AB6917482491 v163[3] = 0x02F5AE3DEC2A4D95E9E01A2B6D9F226162BBE2B3AD v167[0] = 0x20190204 v167[1] = 0x20190506 v167[2] = 0x20190808 v167[3] = 0x20191108 v168[0] = 1 v168[1] = 1 v168[2] = 1 v168[3] = 1 v164[0] = 0x1DB0A6222242978D383FAC95B7CB3573F628D0FDA v164[1] = 0x7C283613ABF06C423F887035C1FCA8BBDDADB548 v164[2] = 0x29500DBA9ECAB405C9D11DC067E01590BB5E1F514 v164[3] = 0x52653AAA31FE29A8C9209ED5FB3E164255C366900 v165[0] = 0x4E559F46B4ADF60BAC0BA565EB681C758955D1BB6 v165[1] = 0x96992ADA68A7FCCA696FA29EBFE066580AE2436AC v165[2] = 0x13B396F4F22FDB14876E0405C02628E518BDA7161A v165[3] = 0x84FA600452F0DE8E1A13BCB444918391525620758 v166[0] = 2 * 1 v166[1] = 2 * 2 v166[2] = 2 * 3 v166[3] = 2 * 4 def sub_404860(a1, a2, a3, a4, a5, a6): P = v162_P v64 = a3 * a6 * (a2 * a4 - Const_0x7e3 * a1 * a5) * (a1 * a4 + a2 * a5) out3 = v64 % P v63 = (a2 * a4 * a1 * a5 - Const_0xBD9 * a3 * a6 * a3 * a6) * (a1 * a4 + a2 * a5) out2 = v63 % P v62 = (Const_0xBD9 * a3 * a6 * a3 * a6 + a2 * a4 * a1 * a5) * (a2 * a4 - Const_0x7e3 * a1 * a5) out1 = v62 % P return out1, out2, out3 def sub_404E90(sha3, sha1, sha2, k3, k2, const0x13D00): v139 = k3 v136 = k2 v135 = const0x13D00 v158 = k3 v157 = k2 v160 = const0x13D00 v150 = k3 v149 = k2 v152 = const0x13D00 P = v162_P for i in range(0x439): (v158, v157, v160) = sub_404860(v136, v139, v135, v158, v157, v160) for i in range(0x4B7): (v150, v149, v152) = sub_404860(v136, v139, v135, v150, v149, v152) for i in range(12): (v158, v157, v160) = sub_404860(v163[0], v167[0], v168[0], v158, v157, v160) (v158, v157, v160) = sub_404860(v163[1], v167[1], v168[1], v158, v157, v160) (v158, v157, v160) = sub_404860(v163[2], v167[2], v168[2], v158, v157, v160) (v158, v157, v160) = sub_404860(v163[3], v167[3], v168[3], v158, v157, v160) for i in range(4): (v150, v149, v152) = sub_404860(v165[0], v164[0], v166[0], v150, v149, v152) (v150, v149, v152) = sub_404860(v165[1], v164[1], v166[1], v150, v149, v152) (v150, v149, v152) = sub_404860(v165[2], v164[2], v166[2], v150, v149, v152) (v150, v149, v152) = sub_404860(v165[3], v164[3], v166[3], v150, v149, v152) for i in range(365): (tmpv134, tmpv133, tmpv132) = sub_404860(v157, v158, v160, v158, v157, v160) (v158, v157, v160) = sub_404860(tmpv133, tmpv134, tmpv132, v158, v157, v160) (v150, v149, v152) = sub_404860(v149, v150, v152, v150, v149, v152) print 'v150', Hex(v150) print 'v149', Hex(v149) print 'v152', Hex(v152) tmp1 = ((v158 ** 2 + v157 ** 2 * Const_0x7e3) * v160 ** 2) % P tmp2 = (v158 ** 2 * v157 ** 2 + v160 ** 2 * Const_0xBD9 * v160 ** 2) % P print "assret(tmp1 == tmp2) ", Hex(tmp1 - tmp2) print Hex(tmp1) print Hex(tmp2) tmp1 = ((v150 ** 2 + v149 ** 2 * Const_0x7e3) * v152 ** 2) % P tmp2 = (v150 ** 2 * v149 ** 2 + v152 ** 2 * Const_0xBD9 * v152 ** 2) % P print "assret(tmp1 == tmp2) ", Hex(tmp1 - tmp2) print Hex(tmp1) print Hex(tmp2) tmp1 = ((v158 * v152 - (v150 * v160) % P) * Const_0x7e3) % P # (v158*v152)%P == (v150*v160)%P tmp2 = ((v157 * v152 - (v149 * v160) % P) * Const_0xBD9) % P # (v157*v152)%P == (v149*v160)%P print "assret(tmp1 == 0) ", Hex(tmp1) print "assret(tmp2 == 0) ", Hex(tmp2) sub_404E90(sha3, sha1, sha2, key3, key2, 0x13D00)
对代码初步分析可以知道这可能是一道椭圆曲线相关的题目。
在00406839位置有一个判断，经过化简形式如下：
((v158**2 + v157**2*0x7E3) * v160**2) % v162和(v158**2 * v157**2 + v160**2*0xBD9*v160**2) % v162是否相等。
在00406AEA位置有一个判断：
((v150**2 + v149**2*0x7E3) * v152**2) % v162和(v150**2 * v149**2 + v152**2*0xBD9*v152**2) % v162是否相等。
已知v162=0x4EA28B61F4C3B12B0B544814578629410ECCF55A7。
对v162进行素性检测，发现v162是一个素数，记为Prime。由此，可以推测这是一个FiniteField(Prime)有限域上的问题。
又总结上面两个判断的特点，使用变量xyz表示的话，形式如下：
x^2*z^2+0x7E3*y^2*z^2=x^2*y^2+0xBD9*z^4
令x'=x/z,y'=y/z，上面的方程可以改为
x'^2+0x7E3*y'^2=x'^2*y'^2+0xBD9
也就是
x^2+0x7E3*y^2=x^2*y^2+0xBD9
猜测这是一个椭圆曲线的问题，查看维基百科英文版elliptic curve的介绍，发现twisted edwards curve跟该方程曲线比较像，在twisted edwards curve的维基百科的
英文版上查看。
http://www.hyperelliptic.org/EFD/g1p/index.html
查看Twisted Edwards curves: a*x2+y2=1+d*x2*y2下的Projective coordinates: x=X/Z, y=Y/Z，可以看到有各种椭圆曲线上点的加法实现方式，并且与sub_404E90函数调用的sub_404860函数具有非常高的相似性。由此推测sub_404860函数是椭圆曲线的加法实现方式。
使用python实现的等价函数，在后期验证各种猜想时起到了重要作用。因为是射影坐标下的表示方式，在验证两个点在只有xy的直角坐标系上是否为同一个点时，需要考虑到z对xy大小的影响，具体判断方式就容易实现了。
根据以上分析，选取x^2+0x7E3*y^2=x^2*y^2+0xBD9曲线上的整数点P，对P点进行倍加2次更新，这样能得到4P点，再通过递增更新也能得到4P点，验证这两种方式得到的为同一个点（xy直角坐标系下的同一个点）就可以确定sub_404860函数就是椭圆曲线的加法实现。
更进一步，令射影坐标下的点P=(x,y,z)乘以或除以相同的数，不会影响点P在xy直角坐标系上的位置，据此可以简化sub_404E90函数且不影响对输入的判断。
经过对函数的详细分析总结，发现有3个关键判断，上面已经提到的2个判断（00406839位置和00406AEA位置的判断）为点是否在椭圆曲线上，第3个判断是两个点是否为同一个点。
问题最后变成了(0x43A*x+c1)*3^365+x=(0x4B8*x+c2)*2^365，其中c1和c2是v163和v164等数据决定的固定的点，需要求取z为0x13D00的点x。
问题归结为，对于已知整数k、点Q，求点P，使得kP=Q。该问题可以转为求取椭圆曲线的阶。
为此，需要下面3个条件。
1. sagemath中给出了Weierstrass形式的椭圆曲线的阶的求取函数，使用方法是
K =GF(Prime)
R.<x,y,z>=K[]
EC=EllipticCurve(x^3+c1*x^2+c2*x-y^2)
print(EC.order())
2. 记不起来怎么搜索到了论文《Edwards Elliptic Curves》，http://fse.studenttheses.ub.rug.nl/10478/，发现论文第4章提到了从Edwards曲线到Weierstrass曲线的一种映射方式。
3. 通过求取发现0x7E3是模Prime的二次剩余，也就是存在整数c使得c^2=0x7E3(mod Prime)。使用sagemath实现，命令是F=FiniteField(Prime);print(F(0x710bbc3150967cdd76c3915d3afda635d3ad7206).sqrt())。
那么x^2+0x7E3*y^2=x^2*y^2+0xBD9方程可以通过利用0x7E3是模Prime的二次剩余这个性质来进行变换，可以通过几步简单变换得到从本题的曲线到Edwards曲线的一种映射方式。
根据以上3点就可以利用sagemath求取得到该题中的椭圆曲线的阶，记为ord。求取k关于ord的逆，记为d，则P=dQ，到此问题解决。
这次的解题说明是总结性质的，解题过程碰到的问题比这里更复杂，在探索阶段进行了很多猜测，这里给出的结果已经把不正确的猜测都去掉了，所以显得解题过程比较顺利。
#END
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2019-12-31 15:45
被kanxue编辑
，原因：
|
|
|---|---|
