This was the first challenge i solve for CSAW 2020 finals. It’s a crypto
challenge that revolves around ECC (Elliptic Curve Cryptography). This is
the content of the file provided.
1
2
3
4
5
6
7
8
9
|
y^2 = x^3 + 2648089252143182574153823745896834765345361977855346851913065097972752819834370636007433949219153563353347621929792473352056603689300142308595500196681484715*x + 2640636613554195662803492377273397651071872147133797068159853320493797794760382065905880626537982439844385071174905293170870708493176922431618220384167739340
FF: 4079211623412602159436576854880565404392213421245358163957062650219138441233389311290884236330989600198400158483251311640833420916559186996716661065534756331
G = (2835124931680967399292763715241068733082955010482692941778975060177550045565873252916114065386731072675933657202784918206609499173114199830285672822076666812 : 3917051964324124246182777370059493628017925319159214920394084902768106573682907256149476836382399752202209827189288072241452544996871460642902049422562450204 : 1)
P = (1201673966464508597332511457607538250497935144691770661539122404983678691094166105235067949576773833297917476372671447578123390251450634078667903889944175974 : 2549728089376241701979352238534953850683927781198029880111780652469308144313884103159306596064169377751896432424056208861929610592541122265583809022865481983 : 1)
P = d*G
d = ?
|
So after googling a bit here, here and pain attention specifically here we can understand that we have a elliptic curve function in the first line with two major big numbers, the first one is the parameter a and the second one b. The next big number is what describes the Finite Field (hence FF). G is the generator coordinates, P is the public key coordinates which by definition is equal to d (the secret) times G. I googled more about elliptic curve attacks and found ones on small primes (which is not the case). After fiddling a bit with sage and these numbers i noticed that the order of the Elliptic Curve function and the Finite Field are the same. I searched to see if this was a problem and stumbled upon what’s called Smart’s Attack. After reading a bit on how it works (a lot of math to be honest), i found a solution online that solved the discrete logarithm for curves and fields in this specific situation.
I tuned the parameters to my challenge and this is the resulting script. In the script the generator G is in fact P whereas the public key is Q.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
p = 4079211623412602159436576854880565404392213421245358163957062650219138441233389311290884236330989600198400158483251311640833420916559186996716661065534756331
A = 2648089252143182574153823745896834765345361977855346851913065097972752819834370636007433949219153563353347621929792473352056603689300142308595500196681484715
B = 2640636613554195662803492377273397651071872147133797068159853320493797794760382065905880626537982439844385071174905293170870708493176922431618220384167739340
xP = 2835124931680967399292763715241068733082955010482692941778975060177550045565873252916114065386731072675933657202784918206609499173114199830285672822076666812
yP = 3917051964324124246182777370059493628017925319159214920394084902768106573682907256149476836382399752202209827189288072241452544996871460642902049422562450204
xQ = 1201673966464508597332511457607538250497935144691770661539122404983678691094166105235067949576773833297917476372671447578123390251450634078667903889944175974
yQ = 2549728089376241701979352238534953850683927781198029880111780652469308144313884103159306596064169377751896432424056208861929610592541122265583809022865481983
E = EllipticCurve(GF(p), [0, 0, 0, A, B])
assert E.order() == p
Qp = Qp(p, 2)
Ep = EllipticCurve(Qp, [0, 0, 0, A, B])
yPp = sqrt(Qp(xP) ** 3 + Qp(A) * Qp(xP) + Qp(B))
Pp = Ep(Qp(xP), (-yPp, yPp)[yPp[0] == yP])
yQp = sqrt(Qp(xQ) ** 3 + Qp(A) * Qp(xQ) + Qp(B))
Qp = Ep(Qp(xQ), (-yQp, yQp)[yQp[0] == yQ])
print('Pp = {}'.format(Pp))
print('Qp = {}'.format(Qp))
print('-' * 40)
lQ = Ep.formal_group().log()(- (p * Qp)[0] // (p * Qp)[1]) / p
print('log(Q) = {}'.format(lQ))
lP = Ep.formal_group().log()(- (p * Pp)[0] // (p * Pp)[1]) / p
print('log(P) = {}'.format(lP))
print('-' * 40)
e = lQ / lP
print('e = {}'.format(e))
assert e[0] * E(xP, yP) == E(xQ, yQ)
print('\n--> FLAG: {:d}\n'.format(e[0]))
3861630529751007946125725817429448910343014844234314632147321534461941961750782142919269219206320480006113471293020487377758051318748395159429681468344962189
|
After running this i got a number, submitted and got the flag back. Done! 🙂
