Rating:
## Tiny ECC
### Challenge
> Being Smart will mean completely different if you can use [special numbers](https://cr.yp.toc.tf/tasks/tiny_ecc_f6ba20693ddf6ba78f1537889d2c46a17b7a4d8b.txz)!
>
> `nc 01.cr.yp.toc.tf 29010`
```python
#!/usr/bin/env python3
from mini_ecdsa import *
from Crypto.Util.number import *
from flag import flag
def tonelli_shanks(n, p):
if pow(n, int((p-1)//2), p) == 1:
s = 1
q = int((p-1)//2)
while True:
if q % 2 == 0:
q = q // 2
s += 1
else:
break
if s == 1:
r1 = pow(n, int((p+1)//4), p)
r2 = p - r1
return r1, r2
else:
z = 2
while True:
if pow(z, int((p-1)//2), p) == p - 1:
c = pow(z, q, p)
break
else:
z += 1
r = pow(n, int((q+1)//2), p)
t = pow(n, q, p)
m = s
while True:
if t == 1:
r1 = r
r2 = p - r1
return r1, r2
else:
i = 1
while True:
if pow(t, 2**i, p) == 1:
break
else:
i += 1
b = pow(c, 2**(m-i-1), p)
r = r * b % p
t = t * b ** 2 % p
c = b ** 2 % p
m = i
else:
return False
def random_point(p, a, b):
while True:
gx = getRandomRange(1, p-1)
n = (gx**3 + a*gx + b) % p
gy = tonelli_shanks(n, p)
if gy == False:
continue
else:
return (gx, gy[0])
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " Dual ECC means two elliptic curve with same coefficients over the ", border)
pr(border, " different fields or ring! You should calculate the discrete log ", border)
pr(border, " in dual ECCs. So be smart in choosing the first parameters! Enjoy!", border)
pr(border*72)
bool_coef, bool_prime, nbit = False, False, 128
while True:
pr(f"| Options: \n|\t[C]hoose the {nbit}-bit prime p \n|\t[A]ssign the coefficients \n|\t[S]olve DLP \n|\t[Q]uit")
ans = sc().lower()
if ans == 'a':
pr('| send the coefficients a and b separated by comma: ')
COEFS = sc()
try:
a, b = [int(_) for _ in COEFS.split(',')]
except:
die('| your coefficients are not valid, Bye!!')
if a*b == 0:
die('| Kidding me?!! a*b should not be zero!!')
else:
bool_coef = True
elif ans == 'c':
pr('| send your prime: ')
p = sc()
try:
p = int(p)
except:
die('| your input is not valid :(')
if isPrime(p) and p.bit_length() == nbit and isPrime(2*p + 1):
q = 2*p + 1
bool_prime = True
else:
die(f'| your integer p is not {nbit}-bit prime or 2p + 1 is not prime, bye!!')
elif ans == 's':
if bool_coef == False:
pr('| please assign the coefficients.')
if bool_prime == False:
pr('| please choose your prime first.')
if bool_prime and bool_coef:
Ep = CurveOverFp(0, a, b, p)
Eq = CurveOverFp(0, a, b, q)
xp, yp = random_point(p, a, b)
P = Point(xp, yp)
xq, yq = random_point(q, a, b)
Q = Point(xq, yq)
k = getRandomRange(1, p >> 1)
kP = Ep.mult(P, k)
l = getRandomRange(1, q >> 1)
lQ = Eq.mult(Q, l)
pr('| We know that: ')
pr(f'| P = {P}')
pr(f'| k*P = {kP}')
pr(f'| Q = {Q}')
pr(f'| l*Q = {lQ}')
pr('| send the k and l separated by comma: ')
PRIVS = sc()
try:
priv, qriv = [int(s) for s in PRIVS.split(',')]
except:
die('| your input is not valid, Bye!!')
if priv == k and qriv == l:
die(f'| Congrats, you got the flag: {flag}')
else:
die('| sorry, your keys are not correct! Bye!!!')
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
```
The challenge is to supply $a,b,p,q=2p+1$ to generate two curves
$$
E_p: y^2 = x^3 + ax + b \pmod p \\
E_q: y^2 = x^3 + ax + b \pmod q
$$
The goal of the challenge is to solve the discrete log for a pair of points on each of these curves. Submitting the correct private keys gives you the flag.
### Solution
I solved this challenge in a fairly ugly and inelegant way. So I'll go through it quickly, then discuss what seems to be the intended solution after.
My idea was to generate a curve $E_p$ with $\\#E_p = p$. This is an anomalous curve, and using Smart's attack, the discrete log problem can be moved to solving a simple division by lifting the curve of the p-adics, which is just division! Then after making one curve easy, I would keep generating primes $p$ until I found a $(q,a,b)$ where $E_q$ had a smooth order, allowing us to solve the discrete log easily.
#### Generating anomalous curves
I refered to [Generating Anomalous Elliptic Curves](https://www.monnerat.info/publications/anomalous.pdf) to generate anomalous curves, and iterated through all primes $p$ where $E_p$ was anomalous. If $q = 2p + 1$ was prime, then I stored the tuple $(p,a,b)$ in a list. I did this until I had plenty of curves to look through.
```python
# https://www.monnerat.info/publications/anomalous.pdf
D = 19
j = -2^15*3^3
def anon_prime(m):
while True:
p = (19*m*(m + 1)) + 5
if is_prime(p):
return m, p
m += 1
curves = []
def anom_curve():
m = 2**61 + 2**60 # chosen so the curves have bit length 128
while True:
m, p = anon_prime(m)
a = (-3*j * inverse_mod((j - 1728), p)) % p
b = (2*j * inverse_mod((j - 1728), p)) % p
E = EllipticCurve(GF(p), [a,b])
if E.order() == p:
G = E.gens()[0]
print(f'Found an anomalous prime of bit length: {p.nbits()}')
if is_prime(2*p + 1):
print(f'Found an anomalous prime with safe prime q = 2p+1. p={p}')
if p.nbits() != 128:
exit()
curves.append([p,a,b])
print(curves)
m += 1
```
Going through curves, I then looked to find $E_q$ of smooth order:
```python
for param in curves:
p, a, b = param
q = 2*p + 1
E1 = EllipticCurve(GF(p), [a,b])
E2 = EllipticCurve(GF(q), [a,b])
assert E1.order() == p
print(factor(E2.order()))
```
Pretty quickly, I found a curve (I think the 15th one?) with order:
```python
E2.order() = 2 * 11 * 29 * 269 * 809 * 1153 * 5527 * 1739687 * 272437559 * 1084044811
```
This is more than smooth enough to solve the dlog (about 10 seconds).
Sending the parameters to the server:
```python
p = 227297987279223760839521045903912023553
q = 2*p + 1
a = 120959747616429018926294825597988269841
b = 146658155534937748221991162171919843659
```
I can solve this discrete log using Smart's attack, and the inbuilt discrete log on $E_q$ as it has smooth order.
```python
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 = 227297987279223760839521045903912023553
q = 2*p + 1
a = 120959747616429018926294825597988269841
b = 146658155534937748221991162171919843659
Ep = EllipticCurve(GF(p), [a,b])
G = Ep(97161828186858857945099901434400040095,76112161730436240110429589963792144699)
rG = Ep(194119107523766318610516779439078452539,111570625156450061932127850545534033820)
print(SmartAttack(G,rG,p))
Eq = EllipticCurve(GF(q), [a,b])
H = Eq(229869041108862357437180702478501205702,238550780537940464808919616209960416466)
sH = Eq(18599290990046241788386470878953668775,281648589325596060237553465951876240185)
print(H.discrete_log(sH))
```
##### Flag
`CCTF{ECC_With_Special_Prime5}`
### Intended Solution?
Thanks to Ariana for suggeting this solution to me after the CTF ended.
The challenge checks for $a * b \neq 0$ , but it does not do this modulo the primes, so if we pick any two primes $p, q = 2p+1$ we can send
```python
p = 227297987279223760839521045903912023553
q = 2*p + 1
a = p*(2*p + 1)
b = p*(2*p + 1)
```
Such that the two curves are given by
$$
E_p: y^2 = x^3 + pq x + pq \pmod p = x^3 \\
E_q: y^2 = x^3 + pq x + pq \pmod q = x^3 \\
$$
Which are singular curves (in particular, these singular curves have triple zeros, known as cusps). We can translate the discrete log over these curves to solving in the additive group of $F_p$ and so the discrete log is division, and trivial. See this [link](https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp) for an example.
Basically, we use the homomorphism
$$
\phi(x,y) \to \frac{x}{y}
$$
such that we can solve this discrete log in the following way
$$
H = [k] G, \;\; g = \frac{G_x}{G_y}, \;\; h = \frac{H_x}{H_y}, \;\; k = \frac{h}{g}
$$
```python
p = 227297987279223760839521045903912023553
q = 2*p + 1
Fp = GF(p)
Fq = GF(q)
Px, Py = (171267639996301888897655876215740853691,17515108248008333086755597522577521623)
kPx, kPy = (188895340186764942633236645126076288341,83479740999426843193232746079655679683)
k = Fp(Fp(kPx) / Fp(kPy)) / Fp(Fp(Px) / Fp(Py))
Qx, Qy = (297852081644256946433151544727117912742,290511976119282973548634325709079145116)
lQx, lQy = (83612230453021831094477443040279571268,430089842202788608377537684275601116540)
l = Fq(Fq(lQx) / Fq(lQy)) / Fq(Fq(Qx) / Fq(Qy))
print(f'{k}, {l}')
```
However, these primes aren't special (re: the flag), so maybe this also isn't intended?
