## 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!}`

Original writeup (https://blog.cryptohack.org/cryptoctf2021-hard#ecchimera).## 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!}`

Original writeup (https://blog.cryptohack.org/cryptoctf2021-hard#ecchimera).