Cryptowars2018 - 0e,5e,12e Writeup

crypto
, ,

The challenge asks to break the ECC keys finding the private exponent , i.e the smallest positive integer such that . The elliptic curves here are defined by the equation .

0e

We have the following parameters:

1
2
3
4
5
6
7
p=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1
A=0
B=7
xP=55066263022277343669578718895168534326250603453777594175500187360389116729240
yP=32670510020758816978083085130507043184471273380659243275938904335757337482424
xQ=72488970228380509287422715226575535698893157273063074627791787432852706183111
yQ=62070622898698443831883535403436258712770888294397026493185421712108624767191

Let’s try with an exhaustive search (the code is written in sage):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1
A=0
B=7
xP=55066263022277343669578718895168534326250603453777594175500187360389116729240
yP=32670510020758816978083085130507043184471273380659243275938904335757337482424
xQ=72488970228380509287422715226575535698893157273063074627791787432852706183111
yQ=62070622898698443831883535403436258712770888294397026493185421712108624767191

P=[xP,yP]
Q=[xQ,yQ]
F = FiniteField(p)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
R=P
k=1
while R!=Q:
    k+=1
    R=k*P

print(k)
print(k*P==Q)

which returns:

1
2
10
True

Thus and the key is broken.

5e

We have

1
2
3
4
5
6
7
p=12506217790875063466368723611056175369923
A=12506217790875063466368723611052784275139
B=12506217790875063466368723533070038257347
xP=7493372729181057645036574086903590138065
yP=359098907392057890604329721532958479621
xQ=9505420031620208163682758801913524369821
yQ=5460936589331844194485299189975059431657

This time we are unlucky and we can’t bruteforce the key. But if we look for the order of over the field we have:

1
print(E.order())

and the result is 12506217790875063466368723611056175369923, which is exactly . Hence we can find the private exponent with the additive transfer attack, aka the Smart-ASS attack.

The full code is then:

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
p=12506217790875063466368723611056175369923
A=12506217790875063466368723611052784275139
B=12506217790875063466368723533070038257347
xP=7493372729181057645036574086903590138065
yP=359098907392057890604329721532958479621
xQ=9505420031620208163682758801913524369821
yQ=5460936589331844194485299189975059431657
P=[xP,yP]
Q=[xQ,yQ]
F = FiniteField(p)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
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])lQ = Ep.formal_group().log()(- (p * Qp)[0] // (p * Qp)[1]) / p
lP = Ep.formal_group().log()(- (p * Pp)[0] // (p * Pp)[1]) / p

e = lQ / lP

assert e[0] * E(xP, yP) == E(xQ, yQ)

print(e[0])

And we have .

12e

This time we have

1
2
3
4
5
6
7
p=30772300251428474897541404692968263716949812908443831592876046737810737208988156271014198502145416667717788718445610314549722607794124248272637226302317
A=30772300251428474897541404692968263716949812908443831592876046737810737208988156271014198502145416667717788718445610314549722607794121899994681666878317
B=30772300251428474897541404692968263716949812908443831592876046737810737208988156271014198502145416667717788718445610314549721222720722172186131393854317
xP=29561516241345269685600719840366915070758730476477194843156185445081418419687711726455154356975229698728353175026723190494273440744152320729175746030047
yP=6271596900388272418806185389049176826094544788645246439903066132798365469828717343340379070431849309644910923054338004606592187702166087195126836872974
xQ=9803494533476252078182975745467080970879117115916552756575328888804137399672877069174914310927425369894015322041756406128521349864943085492910753608888
yQ=13144336243557287405975237486494628680060717357027253199829545937735714808116560433321436824035889516510417399701805550140250708344883560551017907939240

Again, the order of over the field equals and the attack is the same as before. We have now

.