# Codegate CTF 2020 Finals

We are ranked 6th in CODEGATE CTF 2020 Finals. The result is a little disappointing to me, but I think we did our best, so I have no regrets!

My position is crypto and little misc problems.

I solved `cloud9`

, `gaemgam`

, `MIC Check`

, `patternmania`

. I want to write my solutions about `cloud9`

.

## cloud9

This problem is `crypto`

and gives `chall.sage`

and `output`

. Get this File.

### Solution

I studied this attacks about three days before the competition. What a lucky guy.. Actually, I don’t know these two attacks specifically.

We should solve `sd`

, `ld`

. `sd`

is easy to solve.

First, let’s solve `sd`

.

```
n = 2183
order = 35 # elliptic curve's order
G = (132, 1142)
Q = (910, 1641)
```

We can get the a and b by substitute G and Q in Elliptic Curve.

```
a = 940
b = 2178
```

Just bruteforce the `sd`

! And we can get 2.

Second, let’s solve `ld`

.

We should use `Zero-Value Point Attack`

. I will explain this attack soon.. maybe..

```
a = 38240914061990796438737366831519229758147826122081713763266278781817042433002
b = 46190729283374747896507274087688474070284211702985162903204546328076483000624
```

If you multiply order and G, there occurs the error and we can factorize the n.

The reason is that we know if we multiply order and G, the output is Origin. However, n is not a prime so we can’t get the inverse of Origin and get the error instead of Origin.

If \(Q=ld*Q\) in mod n, it also satisfies in mod p and q. So I make the elliptic curve with mod q and I know that order of elliptic curve is same with q!!! If we do `smart attack`

to elliptic curve, we can get `ld`

easily.

## Here is my Smart Attack Solution.

```
n = 5836992596022446937012188954528837967652088799787297418688161952734029742601918639776384293816907277293165804095447608755394244018171460874413413360601287
a = 38240914061990796438737366831519229758147826122081713763266278781817042433002
b = 46190729283374747896507274087688474070284211702985162903204546328076483000624
p = 97940012926710762153437884674079301076391785734843620993390248274679651111717
q = 59597629422310897332995051052435766506780710137496164204389350135087152537211
E2 = EllipticCurve(Zmod(q), [a,b])
G = E2(4791064145174837833113077069599757584947381216841105432787931481123835537923996904590176334618000141035959257993847069760040827648845993882710813263422518, 2007135516277895026771627676893419200766568709594031697039637947675097596595809713825936430608820664600227626467013163201670055105153466868380086912003923)
Q = E2(2906660915459424515040277093002683642589488507112805139726386938933880929506501185082819430093812825540133325640097413100449877310669418449600698325701077, 3812143203765395705358551712573539116980648501774991245491977901798688330759954052153901303962483747022229555022370548381218346760417689877969168781021420)
def HenselLift(P,p,prec):
E = P.curve()
Eq = E.change_ring(QQ)
Ep = Eq.change_ring(Qp(p,prec))
x_P,y_P = P.xy()
x_lift = ZZ(x_P)
y_lift = ZZ(y_P)
x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')
f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6
g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)
gDiff = g.diff()
for i in range(1,prec):
uInv = ZZ(gDiff(y=y_lift))
u = uInv.inverse_mod(p^i)
y_lift = y_lift - u*g(y_lift)
y_lift = ZZ(Mod(y_lift,p^(i+1)))
y_lift = y_lift+O(p^prec)
return Ep([x_lift,y_lift])
def SmartAttack(P, Q, p, prec):
E = P.curve()
Eqq = E.change_ring(QQ)
Eqp = Eqq.change_ring(Qp(p,prec))
P_Qp = HenselLift(P, p, prec)
Q_Qp = HenselLift(Q, p, prec)
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P, y_P = p_times_P.xy()
x_Q, y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q / phi_P
k = Mod(k, p)
return k
print(SmartAttack(G, Q, q, 8))
```

If you get the `ld`

, make the key with `sd`

and `ld`

and decrypt the encrypted message!

The flag is `CODEGATE2020{Here_comes_the_crypto_genius}`

.

I will update the solution of `sculptor`

soon.