readyu's crackme 2017

readyu@pediy
2017-05-31

根据规则，crackme 内部name固定。 SN唯一。
本题sn为：

7A7102F36F3B344D666132A6FF7EF4BA05B99640BB815C9E712A72C64B6ABC582C2

正确提示：
"Oh Yes! You got it.",


设计思路:

（1）
考虑一条有限域椭圆曲线上的已知点 G1, G2, 以及给定的系数 h1,h2,h3,
求点S(x,y) 满足方程, 以下大写字母表示有限域椭圆曲线上的点， 小写字母表示数值：

h1( S + h3*G1) = h2(S + h3*G2)   mod n

那么， 判断正确的key， 等价于判断方程两边运算的点的x坐标： 两个大数相等。

因此， 比较key，不会出现明文比较。这里S是可以计算的，并没有用到ECDLP（椭圆曲线离散对数）。

那么，如何求出S(x,y):

=> (h1 - h2) S = h2*h3*G2 - h1*h3*G1

S(x,y) = (h2*h3/(h1 - h2)) * G2-  (h1*h3/(h1 - h2)) * G1  mod n

sn = S(x,y) ， x,y is the point on the cuver ECC2K-130

椭圆曲线选取公开的ECC2K-130：

（参数取自如下pdf文档）

http://www.ecc-challenge.info/anon.pdf

========
ECC2K-130   GF(2^m)
========

E:     y^2  + xy =   x^3 + a*x^2 + b 

m = 131
f = x^131 + x^13 + x^2 + x + 1

a = 0
b = 1

E 即：  y^2 + xy = x^3 + 1  , over  GF(2^131)

point P (G1):
X= 51C99BFA6F18DE467C80C23B98C7994AA
Y= 42EA2D112ECEC71FCF7E000D7EFC978BD

Point Q (G2):
X= 6C997F3E7F2C66A4A5D2FDA13756A37B1
Y= 4A38D11829D32D347BD0C0F584D546E9A

np (number of points) =
80000000000000001353F755C0E8FC9A4

n  (prime order) =

200000000000000004D4FDD5703A3F269

（2）

补充细节的考虑 之一 关于hash。

为了使得h1, h2, h3 线性无关，并且与name, 和相关字符 关联起来， 这里取md5 hash作为系数。
h1 = hash1(0x1 name - pediy);
h2 = hash2(0x2 0x2 name - 2017);
h3 = hash3(0x3 0x3 0x3 name - crackme);
hash 采用md5

例如： name = readyu

readyu-pediy
hexstring= 017265616479752D7065646979
hash1=
51c75f1f444baa97ed18dd6c340835d7

readyu-2017
hexstring= 02027265616479752D32303137
hash2=
0e5cf7f068d6efa16f42f935ec424a75

readyu-crackme
hexstring= 0303037265616479752D637261636B6D65
hash3=
a4cd1d64486abde1be441944460cd41d

（3）

补充细节的考虑 之二 关于sn 编码。

采用一个素数P269， 把S（x,y） 用d加密编码。 结果就是sn。用到了费马小定理。

sn = S^d mod P

P269(prime)=
10000000000000000000000000000000000000000000000000000000000000000079

e=0x5

d=
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCD2D

这里有：

m^(P-1) = 1 (mod P)    (m为自然数， P为素数，  1 <= m < P) 费马小定理

e*d = 1   （ mod  (P-1) ）   , 素数P的欧拉函数是P-1

=〉
(m^d)^e  = m  ( mod P)

（4） 答案：

计算hash:
readyu-pediy
017265616479752D7065646979
hash1=
51c75f1f444baa97ed18dd6c340835d7

readyu-2017
02027265616479752D32303137
hash2=
0e5cf7f068d6efa16f42f935ec424a75

readyu-crackme
0303037265616479752D637261636B6D65
hash3=
a4cd1d64486abde1be441944460cd41d

计算S(x,y):
h1=51C75F1F444BAA97ED18DD6C340835D7
h2=0E5CF7F068D6EFA16F42F935EC424A75
h3=A4CD1D64486ABDE1BE441944460CD41D
G1(x,y)=(51C99BFA6F18DE467C80C23B98C7994AA , 42EA2D112ECEC71FCF7E000D7EFC978BD)
G2(x,y)=(6C997F3E7F2C66A4A5D2FDA13756A37B1 , 4A38D11829D32D347BD0C0F584D546E9A)

S(x,y) = (h2*h3/(h1 - h2)) * G2 - (h1*h3/(h1 - h2)) * G1  mod Order

Order =
200000000000000004D4FDD5703A3F269

h1 - h2 =
436A672EDB74BAF67DD5E43647C5EB62

r = (h1-h2)^(-1) mod Order =
173CB0D72C158E23F256FC94D6E74A97

w1=
h2*h3*r mod Order =
D6DBB08B9A3139CDE4385BE48605B58D0C593C6724E70BC8C21FD2A39E505C3C0FBFC877FAEDBE48FE7AD87269E557
mod Order =
150239A0F0A087516E1BE5BCFF3DF190C

w2=
h1*h3 *r mod Order =
4C753C126D9D285397077885BDE0BD787D08A9D14D8852E1407EA5104F9233AEC8B968908D546D31EB19E86B2A756AD
mod order =
1F4F0B773527332F8A002751439EBED29

Order - w2 =
B0F488CAD8CCD07AD4D6842C9B80540

S(x,y) = w1 * G2 - w2 * G1
= w1 * G2 + (Order - w2) * G1
= 150239A0F0A087516E1BE5BCFF3DF190C * G2 + B0F488CAD8CCD07AD4D6842C9B80540 * G1
=
(02D23461BA71B50AF182DC76E5A7C726F5 , 07BE013AF19BD185BCD20BB341EA31298B)


得到:
S(x,y) =
02D23461BA71B50AF182DC76E5A7C726F507BE013AF19BD185BCD20BB341EA31298B

因为:
d=CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCD2D

P269=
10000000000000000000000000000000000000000000000000000000000000000079

所以:
sn
= S(x,y) ^ d mod P269 =
7A7102F36F3B344D666132A6FF7EF4BA05B99640BB815C9E712A72C64B6ABC582C2  
(5)
错误key, 比如 2919D8E8C43615B9C9CB2CB807D148B2DCF8F363B57C0F493BFEECA52827F31C348
会提示  "Oh NO ! Invalid code.",
    "This is wrong SN!",
    "Please work hard!",

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界