[推荐]2019 KCTF 总决赛 | 第九题《四季之歌》点评及解题思路

发表于: 2019-12-27 18:03 7038

[推荐]2019 KCTF 总决赛 | 第九题《四季之歌》点评及解题思路

Editor

2019-12-27 18:03

7038

第九道题《四季之歌》历时3天，已于23号中午12点关闭攻击通道。此题共有909人围观，最终仅有1支战队攻破，即辣鸡战队。

1、题目简介

霓虹闪烁，交通工具在建筑物之间穿梭，抬头可以看到巨型的立体灯牌和全息投影。
地面是透明的，可以看到地下深不见底，建筑破败老旧，在雨夜中显得十分深沉。
经过一番调查我发现这个空间整体是一个巨大的时钟，每天向前走一格，昼夜交替，四季更迭，上层的人们永远享受着春夏秋冬，时钟指向12，空间再次重置，一切又重新出发。
下层人们的大半辈子都在黑夜里无限循环，度过365天，他们在另一个黎明时分转向地下。
四季在这个空间里仿佛是一个闭合之环，人们害怕的不是未知，而是提前知道自己的命运。
时间是个圈，空间是个圈，宇宙也是个圈。圈里的人在四季轮回中无限循环，而我要怎么帮助他们？
这个谜题等待我去探索。

[说明：本题是一道Windows逆向题]

前期赛况胶着，各个战队苦思冥想而不得解，最终辣鸡战队成为整个赛场上唯一成功破解的战队，并保持攻击方排行榜第一名。

本题攻破人数较少，可见其难度较大，接下来让我们一起来看一下这道题的点评和详细解析吧。

2、看雪评委crownless点评

这道题的密码学部分比较难，考查了对公钥密码学中椭圆曲线的理解，要求在理解题目算法的基础上实现点乘算法，具有一定的复杂度。

3、出题团队简介

本题出题战队 ReadPage：

团队简介：readyu的米兔安全小分队。

题目作者readyu，毕业于中国科学技术大学自动控制专业，从事软件开发多年。在软件保护技术、加密算法方面有一些深入的研究，编写了ECCTool（椭圆曲线加密工具），RDLP（RSA与离散对数实用工具）。曾在北京多看科技从事电子阅读加密技术的研究，现任职于小米AIoT安全实验室。

4、设计思路

说明：密码学题目， VC++ 编译的Win32程序，取名“四季之歌”。

一、序列号

这个程序默认只有一个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

二、算法模型与解题分析

本题验证爱德华椭圆曲线上 “点加” 的相遇等式，求 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: 蒙哥马利曲线与扭爱德华曲线的等价）。

所以，爱德华曲线点数的计算方法：转换为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

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代码。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

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应该也不会影响结果，所以得到化简版的代码如下：

100

101

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

[注意]看雪招聘，专注安全领域的专业人才平台！

最后于 2019-12-31 15:45 被kanxue编辑，原因：

收藏・0

免费

支持