0CTF 2019 Elements Writeup

阅读量    69663 | 评论 2   稿费 300

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

0ctf 2019的一道逆向题

题目逆向

先拖进ida简单看一下,又是典型的输入flag过check的逆向题。如果通过check则输出Congratz。我们一个一个检查看:

检查1

check1

首先是一个常规的检查,读取输入,然后检查输入的长度是0x2c,检查输入是否以flag{开头,以}结尾。

检查2

之后对输入掐头去尾,对中间剩余的内容用-来分割,得到一个字符串序列。之后会解析这个序列里的每一个元素,检查其长度是否为12,把字符串转化为对应的数字,比如把字符串dead转化为数字0xdead,即57005。此外,如果是序列中的第一个元素,会判定其是否是一个特定值0x391bc2164f0a,代码如图:

check2

因此我们可以得到flag的第一部分就是391bc2164f0a

检查3

检查3是最复杂的部分。首先程序会把之前从字符串解析出来的数字做一个转换:

check3_0

这个转换用了一些奇怪的API,我们先不管。

当解析了3个序列之后会进入检查3,代码如图:

check3_1

input1input2input3分别是我们输入的3个序列,其中input1已知。首先会对三个序列的大小关系做了一个比较,然后对这三个序列做了一系列复杂的运算,包括开根号和浮点数运算,最后得到两个浮点数的值tmp3tmp4,如果这两个值分别是1.94003…和4.77705….则通过检查。
虽然现在我们只有两个未知数和两个等式,但是这并不是一次方程,运算过程中有平方和开根号,可以尝试用平方消去根号,最后得到了一个四次方程,很难直接求出input2input3

 

三角函数公式和三斜求积术

我们大胆猜测,题目所做的运算应该不是无意义随便构造出来的,而是有其物理/数学意义的。经过一些搜索,我们发现tmp2进行的运算,实际是秦九韶公式,或称为三斜求积术,是海伦公式的一种等价表示。

对于三角形三边a,b,c;其中c为最长边,a为最短边,则三角形的面积S可以表示为:

在题目中,根据check3中一开始对三个值的比较可知input1是最短边(a),input3是最长边(c)。tmp2是三角形面积S。这样我们可以把tmp3tmp4改写为:

    tmp3 = 2S/(a+b+c)
    tmp4 = abc/(4*S)

根据三角函数的相关知识我们可以知道tmp3表示三角形内切圆半径,tmp4表示三角形外接圆半径。

    tmp3 = 2S/(a+b+c)=r
    tmp4 = abc/(4*S)=R

题目转化为已知三角形最短边a以及三角形外接圆半径R和三角形内切圆r,求三角形的其他两边。

 

列出方程

下面就要列方程解这个三角函数问题。

首先利用正弦定理

a/sin A = 2*R

得到

sin A = a/(2R)

根据余弦定理,

cos A = (b^2+c^2-a^2)/(2bc)= sqrt(1-(sin A)^2)

联立上述多个等式得到

4Rr(1+cosA)/a = T1 = 4 * tmp3 * tmp4 *(b^2+c^2-a^2+2bc)/2bc =(abc) * (b+c+a) * (b+c-a)/(a * bc * (a+b+c)) = b + c - a

b + c = a + T1 = T2

之后联立两个面积公式得到

S = abc/4R = (a + b + c)r/2
abc = 2Rr(a+b+c)=2Rr(a+T2)
bc= 2Rr(a+T2)/a = T3

得bc后计算c-b,并得到最终的解

c-b = sqrt((c+b)^2 - 4bc) = sqrt(T2^2-4T3) = T4
c = (T2+T4)/2
b = (T2-T4)/2

 

解题脚本

from math import sqrt

r = 1.940035480806554e13
R = 4.777053952827391e13
a = 62791383142154.0
sinA = a / (2.0 * R)
cosA2 = 1 - sinA**2
cosA = sqrt(cosA2)
T2 = a+4*R*r*(1+cosA)/a#b+c
T3 = 2*R*r*(a+T2)/a #bc
T4 = sqrt(T2*T2-4*T3)#c-b

c = int((T2+T4)/2)
b = int((T2-T4)/2)
print c
print b

这个脚本算的b和c会有一些精度的丢失,我们可以手动调整一下b和c的个位,输到程序里检查b和c是否正确。

最后得到flag{391bc2164f0a-4064e4798769-56e0de138176}

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多