Rating:
## Ecchimera
### Challenge
> The [mixed](https://cryp.toc.tf/tasks/ecchimera_da57494454cba7683105130b6161f4f65c41306f.txz) version is a hard version!
```python
#!/usr/bin/env python3
from sage.all import *
from flag import flag
n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982
flag = flag.lstrip(b'CCTF{').rstrip(b'}')
s = int(flag.hex(), 16)
assert s < n
E = EllipticCurve(Zmod(n), [0, U, 0, V, W])
G = E(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
print(f'G = {G}')
print(f's * G = {s * G}')
```
We have an elliptic curve defined over the ring of integers modulo n, or $Z_n$. Generally elliptic curves are defined over a field with a prime $p$, or $F_p$, but in this case we working with the ring $Z_n$.
The rest of the question is a typical ECDLP (Elliptic Curve Discrete Log Problem) problem, where we're given a generator point $G$ on the curve and the point $s * G$, where $s$ is our flag and the value we need to solve for.
Because $n$ isn't prime, we need to take a different approach to solve the discrete log problem. If we use [factordb](http://factordb.com/index.php?query=43216667049953267964807040003094883441902922285265979216983383601881964164181), we can factor $n$ into 2 primes $p$ and $q$.
According to this link https://link.springer.com/content/pdf/10.1007%2FBFb0054116.pdf (pg. 4), the number of points on the elliptic curve ($\\#E_{Z_n}$) is equivalent to the product of the order of the curve defined over $F_p$ and $F_q$. In other words,
$$
\#E_{Z_n} = \#E_{F_p} * \#E_{F_q}
$$
Now because $p$ and $q$ are prime, it's very simple to figure out $\\#E_{F_p}$ and $\\#E_{F_q}$, we can do it directly in Sage
```python
#!/usr/bin/env python3
n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982
E = EllipticCurve(Zmod(n), [0, U, 0, V, W])
G = E(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sG = E(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
p = 190116434441822299465355144611018694747
q = 227316839687407660649258155239617355023
assert p * q == n
# P and Q curves
Ep = EllipticCurve(GF(p), [0, ZZ(U % p), 0, ZZ(V % p), ZZ(W % p)])
Eq = EllipticCurve(GF(q), [0, ZZ(U % q), 0, ZZ(V % q), ZZ(W % q)])
kp = Ep.order()
kq = Eq.order()
```
Now in order to solve the discrete log on the curve over the ring $Z_n$, what we can do instead is solve the discrete log on the curve over the field $F_p$ and $F_q$ and then combine the results using the Chinese remainder theorem (from pg.11 of the same paper linked above). Another explanation is given here: https://crypto.stackexchange.com/questions/72613/elliptic-curve-discrete-log-in-a-composite-ring.
If we look at the order of the curve over $F_p$ and $F_q$ we notice a few things.
$$
\#E_{F_p} = p = 190116434441822299465355144611018694747 \\
\#E_{F_q} = 2^4 * 3 * 13 * 233 * 4253 * 49555349 * 7418313402470596923151
$$
If the order of a curve defined over a field $F_p$ is equal to $p$, then that means the curve is anomalous, and there's an attack (called Smart's attack) that we can apply to solve the discrete log easily. So we can apply this to the curve defined over $F_p$. This also implies that every point generated by the curve also has an order of $p$.
For the other curve defined over $F_q$, notice that the order is somewhat smooth, meaning that the number can be decomposed into small-ish primes. Other than the last prime factor, the other numbers are fairly small primes. This kind of smooth order implies the Pohlig Hellman attack, where we solve the discrete log problem by solving the discrete log over the subgroups of the group generated by the point $G$.
To summarize, we have a elliptic curve defined over $Z_n$ and we need to solve the discrete log problem to find a value $s$ given $G$ and $sG$. We can split the curve into 2 curves defined over $F_p$ and $F_q$. Then we solve the discrete log over these 2 curves for $s_p$ and $s_q$ such that
$$
s_p \equiv s \mod \#E_{F_p} \\
s_q \equiv s \mod \#E_{F_q}
$$
Using the Chinese remainder theorem we combine these results to find
$$
s \mod \\#E_{Z_n}
$$
because
$$
\#E_{Z_n} = \#E_{F_p} * \#E_{F_q}
$$
#### Pohlig Hellman
We'll start with the curve defined over $F_q$. First we find the order of the point $G$ defined on the curve:
```python
#!/usr/bin/env python3
from Crypto.Util.number import *
n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982
E = EllipticCurve(Zmod(n), [0, U, 0, V, W])
G = E(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sG = E(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
p = 190116434441822299465355144611018694747
q = 227316839687407660649258155239617355023
assert p * q == n
# P curve
Eq = EllipticCurve(GF(q), [0, ZZ(U % q), 0, ZZ(V % q), ZZ(W % q)])
kq = Eq.order()
Gq = Eq(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sGq = Eq(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
print(Gq.order())
```
Output is
$$
75772279895802553549752718413205785008 = 2^4 * 13 * 233 * 4253 * 49555349 * 7418313402470596923151
$$
Other than the last factor, the number is fairly smooth. Also notice that the order of $G$ isn't equal to the order of the curve $\\#E_{F_q}$ (there's a factor of 3 missing).
We will run the Pohlig Hellman algorithm using every factor except the last one, because solving the discrete log in that prime-order subgroup will take too long. If $s_q$ is small enough, we don't have use the last prime and we will still find the correct value.
Code below is to find $s_q$
```python
primes = [2^4, 13, 233, 4253, 49555349, 7418313402470596923151] #don't use 3 and last one
dlogs = []
for fac in primes[:-1]:
t = int(Gq.order()) // int(fac)
dlog = (t*Gq).discrete_log(t*sGq) #discrete_log(t*sGq, t*Gq, operation="+")
dlogs += [dlog]
#print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
q_secret = crt(dlogs, primes[:-1])
```
Running this we get $s_q = 9092500866606561$.
#### Smart's attack
Onto the other curve. We know the order of the curve equals the prime $p$ (anomalous curve), so we can apply Smart's attack to solve the discrete log quickly.
Code to apply this attack and solve for $s_p$ is below:
```python
n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982
E = EllipticCurve(Zmod(n), [0, U, 0, V, W])
G = E(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sG = E(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
p = 190116434441822299465355144611018694747
q = 227316839687407660649258155239617355023
assert p * q == n
# P curve
Ep = EllipticCurve(GF(p), [0, ZZ(U % p), 0, ZZ(V % p), ZZ(W % p)])
kp = Ep.order()
Gp = Ep(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sGp = Ep(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
print(Gp.order())
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
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
return ZZ(k)
p_secret = SmartAttack(Gp,sGp,p)
```
Running that code we get $s_p = 35886536999264548257653961517736633452$
#### CRT
All that's left is to combine our 2 answers with CRT and solve for the flag.
Let the order of $G$ on $E_{F_p}$ be $n_p$ and the order of $G$ on $E_{F_q}$ be $n_q$.
Also note that:
$$
\#E_{F_p} = n_p\\
\#E_{F_q} = n_q \cdot 3 \cdot 7418313402470596923151
$$
We have the following equations:
$$
s_p \equiv s \mod n_p\\
s_q \equiv s \mod n_q
$$
If the $s$ is small enough, CRT will be able to recover the flag.
```python
flag = long_to_bytes(int(crt([p_secret, q_secret], [Gp.order(), Gq.order() // 7418313402470596923151])))
print(flag)
```
### Solution
Full solution code below
```python
#!/usr/bin/env python3
from Crypto.Util.number import *
n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982
E = EllipticCurve(Zmod(n), [0, U, 0, V, W])
G = E(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sG = E(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
p = 190116434441822299465355144611018694747
q = 227316839687407660649258155239617355023
assert p * q == n
# P curve
Ep = EllipticCurve(GF(p), [0, ZZ(U % p), 0, ZZ(V % p), ZZ(W % p)])
Eq = EllipticCurve(GF(q), [0, ZZ(U % q), 0, ZZ(V % q), ZZ(W % q)])
kp = Ep.order()
kq = Eq.order()
Gp = Ep(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
Gq = Eq(6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
sGp = Ep(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
sGq = Eq(14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
print(Gp.order())
print(Gq.order())
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
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
return ZZ(k)
primes = [2^4, 13, 233, 4253, 49555349, 7418313402470596923151] #don't use 3 and last one
dlogs = []
for fac in primes[:-1]:
t = int(Gq.order()) // int(fac)
dlog = (t*Gq).discrete_log(t*sGq) #discrete_log(t*sGq, t*Gq, operation="+")
dlogs += [dlog]
#print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
p_secret = SmartAttack(Gp,sGp,p)
q_secret = crt(dlogs, primes[:-1]) #Gq.discrete_log(sGq) #9092500866606561 #discrete_log(sGq, Gq, ord=Gq.order(), bounds=2^4 * 3 * 13 * 233 * 4253 * 49555349, operation="+")
print(p_secret, q_secret)
flag = long_to_bytes(int(crt([p_secret, q_secret], [Gp.order(), Gq.order() // 7418313402470596923151])))
print(flag)
```
##### Flag
`CCTF{m1X3d_VeR5!0n_oF_3Cc!}`
