ezzzecc

和[HGAME 2022 week4]ECC差不多的一道题，多了两个点，一个是p的解密，一个是k的获取

先是p的解密，是一个base62+多次base64+多次ROT47，真是逆天...

原来

koZP3YQAklARRNrmYfjxoKIAXegOcG4jMOmKb08uESOkCCn72d6UM2NWgefYPEMq4EJ1M0jKaqt02Guo5Ubccjqg4QZaaHbScREx38UMLQKwG0LcDd8VFX1zkobc1ZQn4L3DhKQrgJZI55todgOdJuHN532bxScAvOF26gJyQclPtRHn3M6SHrRCEXzzmszd68PJlLB6HaabrRrCW9ZoAYSZetM5jDBtNCJLpR0CBZUUk3Oeh2MZQu2vk8DZ1QqNG49hlxGfawp1FXvAZPdMwixzkhEQnbCDcOKzYyT6BZF2Dfd940tazl7HNOswuIpLsqXQ2h56guGngMeYfMXEZV09fsB3TE0N934CLF8TbZnzFzEkOe8TPTK2mWPVSrgmbsGHnxgYWhaRQWg3yosgDfrEa5qfVl9De41PVtTw024gltovypMXK5XMhuhogs0EMN7hkLapLn6lMj

base62之后

VmpKNFUxTXlVWGRsU0VKcFRXcFdUVmxXVWtOa01VMTZZVE5rYWsxSVVURlpha2t4VXpKR1ZWVnVVbFJOVlRWaFdUSjBkMDVYVFhsTlZYaHNWa1ZLTmxVeU5YTk5NbEpXWlVoQ2EwMHhXazFWVkVrMVpXeE5lbUpJY0d0U1dFSlZWMnBPUTFSV1ZYaGlTRlpWVWxVMGVsa3hWalJXUlRGSVRWVjBWazB3TlRaV1JXUnlUVWRKZDJSSVFrOVRSVXBNVmxST2EyUXhVa2RVYm5CcVZsaG9SVlpzWkRSVVJsVjZWRzVhVkUxdGMzZFpla0l3VGxacmVsUnJkRlpOYldjeA==

多次base64之后

e2p.*'*-)+-,+*'&.&)&+'+&+-,',..,.(*,++-%()-&',,*--&%+,..(*.)%,)-+*,%%)+(*.,+',%(r

ROT47之后得到p

p={95258468765219141626168727997935766803481277588106799359407486570046359762703}

然后是私钥k的获取，由于这题给了私钥k是18位的，所以可以爆破得到k（所以其实那个k小于1000000的条件没什么用...

爆破k的sage代码：

1
2
3
4
5
6
7
8
9
10
p = 95258468765219141626168727997935766803481277588106799359407486570046359762703
a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
E = EllipticCurve(GF(p),[a,b])
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939, 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565, 74331715224220154299708533566163247663094029276428146274456519014761122295496)
for k in range(2^17, 2^19):
    if K == k*G:
        print(k)
        break

得到k为166909

得到私钥k，由题有

1
2
c1 = m + r * K
c2 = r * G

那么有

1
m = c1 - k * c2

求解的sage代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import libnum

p = 95258468765219141626168727997935766803481277588106799359407486570046359762703
a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
k = 166909
E = EllipticCurve(GF(p),[a,b])
c1 = E(3315847183153421424358678117707706758962521458183324187760613108746362414091, 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = E(12838481482175070256758359669437500951915904121998959094172291545942862161864, 60841550842604234546787351747017749679783606696419878692095419214989669624971)
m = c1 - k * c2
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815
print(libnum.n2s(int(cipher_left//m[0])))
print(libnum.n2s(int(cipher_right//m[1])))

另一种求p的方法

已知4个椭圆曲线上的点：K、G、c1、c2，每个点都满足x**3+a*x+b-y**2=kp，故可以通过求gcd来得到p，而且实际上只用两个点就可以得到

1
2
3
4
5
6
7
8
9
10
import gmpy2

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939, 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565, 74331715224220154299708533566163247663094029276428146274456519014761122295496)
l = K[0] ** 3 + a * K[0] + b - K[1] ** 2
w = G[0] ** 3 + a * G[0] + b - G[1] ** 2
p = gmpy2.gcd(l, w)
print(p)

另外一种爆破k的方法

上面爆破k的方法是用K和G算出k的具体值，其实可以直接爆破，不用关心它的具体值，我们关心的是解出的明文字符串中是否有flag

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
import gmpy2
from Crypto.Util.number import *
from tqdm import tqdm

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939, 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565, 74331715224220154299708533566163247663094029276428146274456519014761122295496)

KK = K[0]^3 + K[0]*a + b - K[1]^2 
GG = G[0]^3 + G[0]*a + b - G[1]^2
p = gmpy2.gcd(KK, GG)
print(p)

E = EllipticCurve(GF(p),[a,b])
c1 = (3315847183153421424358678117707706758962521458183324187760613108746362414091, 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = (12838481482175070256758359669437500951915904121998959094172291545942862161864, 60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815

c1 = E(c1)
c2 = E(c2)

for k in tqdm(range(2^17, 2^18)):
    m = c1 - c2*k
    flag1 = long_to_bytes(int(cipher_left // m[0]))
    flag2 = long_to_bytes(int(cipher_right // m[1]))
    flag = flag1 + flag2
    if b'flag' in flag:
        print(flag)
        break