## Double Miff### Challenge>A new approach, a new attack. Can you attack this curve?[double_miff.txz](https://cr.yp.toc.tf/tasks/double_miff_58336b2ad5ed82754ac8e9b3bdcc8f25623c909c.txz)
```python#!/usr/bin/env python3
from Crypto.Util.number import *from secret import a, b, p, P, Qfrom flag import flag
def onmiff(a, b, p, G):    x, y = G    return (a*x*(y**2 - 1) - b*y*(x**2 - 1)) % p == 0
def addmiff(X, Y):    x_1, y_1 = X    x_2, y_2 = Y    x_3 = (x_1 + x_2) * (1 + y_1*y_2) * inverse((1 + x_1*x_2) * (1 - y_1*y_2), p) % p    y_3 = (y_1 + y_2) * (1 + x_1*x_2) * inverse((1 + y_1*y_2) * (1 - x_1*x_2), p) % p    return (x_3, y_3)
l = len(flag) // 2m1, m2 = bytes_to_long(flag[:l]), bytes_to_long(flag[l:])
assert m1 < (p // 2) and m2 < (p // 2)assert onmiff(a, b, p, P) and onmiff(a, b, p, Q)assert P[0] == m1 and Q[0] == m2
print(f'P + Q = {addmiff(P, Q)}')print(f'Q + Q = {addmiff(Q, Q)}')print(f'P + P = {addmiff(P, P)}')```
```pythonP + Q = (540660810777215925744546848899656347269220877882, 102385886258464739091823423239617164469644309399)Q + Q = (814107817937473043563607662608397956822280643025, 961531436304505096581595159128436662629537620355)P + P = (5565164868721370436896101492497307801898270333, 496921328106062528508026412328171886461223562143)```
### SolutionWe have a curve equation $ax(y^2 - 1) \equiv by(x^2 - 1) \mod p$ with unknown $a$, $b$, $p$; $P$ and $Q$ are some points on it, and we have $P + Q$, $Q + Q$ and $P + P$.
We need to recover $x$-coordinates of $P$ and $Q$, since they contain parts of the flag.Addition here is commutative and associative, so we have 
$$(P + P) + (Q + Q) = P + P + Q + Q = P + Q + P + Q = (P + Q) + (P + Q).$$
We have 2 ways of representing $x$- and $y$-coordinates of $P + P + Q + Q$. Set $P + Q = (x_1, y_1)$, $Q + Q = (x_2, y_2)$, $P + P = (x_3, y_3)$, $P + P + Q + Q = (x_0, y_0)$. Then from addition formulas for $x$ we have 
$$x_0 \equiv \frac{(x_2+x_3)(1+y_2y_3)}{(1+x_2x_3)(1-y_2y_3)} \mod p \\x_0 \equiv \frac{2x_1(1+y_1^2)}{(1+x_1^2)(1-y_1^2)} \mod p$$,
from where we get this:
$$p|((1+x_1^2)(1-y_1^2)(x_2+x_3)(1+y_2y_3) - 2x_1(1+y_1^2)(1+x_2x_3)(1-y_2y_3))$$
Analogously from addition formulas for y we get 
$$p|((1+y_1^2)(1-x_1^2)(y_2+y_3)(1+x_2x_3)-2y_1(1+x_1^2)(1+y_2y_3)(1-x_2x_3))$$
We can compute gcd of 2 numbers above to get a small multiple of $p$ ($8p$ in this case), and from there we get $p = 1141623079614587900848768080393294899678477852887$.
Recall that for any point on the curve we have $ax(y^2-1) \equiv by(x^2-1) \mod p$, from where we can compute $k \equiv \frac{a}{b} \equiv \frac{y(x^2 - 1)}{x(y^2-1)} \mod p$ by using any known point. 
Note that we also have $\frac{y}{y^2-1} \equiv k\frac{x}{x^2-1} \mod p$.
Set $P = (x_4, y_4)$, and from addition formulas we get:
$$x_3 \equiv \frac{2x_4(1+y_4^2)}{(1+x_4^2)(1-y_4^2)} \mod p \\y_3 \equiv \frac{2y_4(1+x_4^2)}{(1+y_4^2)(1-x_4^2)} \mod p$$
from where we get 
$$x_3y_3 \equiv \frac{4x_4y_4}{(x_4^2-1)(y_4^2-1)} \equiv 4k(\frac{x_4}{x_4^2 - 1})^2 \mod p$$
and then $(\frac{x_4^2-1}{x_4})^2 \equiv \frac{4k}{x_3y_3} \mod p$ and have $\frac{x_4^2-1}{x_4} \equiv \pm l \mod p$, where $l \equiv (\frac{4k}{x_3y_3})^{\frac{p+1}{4}} \mod p$, since $p \equiv 3 \mod 4$.
From here we get $x_4^2 \mp lx_4 - 1 \equiv 0 \mod p$. Discriminant in both cases is equal to $D \equiv l^2 + 4 \mod p$, and we get roots of both equations with $\frac{\pm l \pm \sqrt{D}}{2} \mod p$. Check each one of them, the one that results into printable text gives us the first half of the flag. Analogously we can recover $x$-coordinate of $Q$ and get second half of the flag. By concatenating them, we will have the full flag. Judging by the flag, though, this may be an unintended solution.
### Implementation```python#!/usr/bin/env python3from Crypto.Util.number import isPrime, long_to_bytesfrom math import gcd
x1, y1 = (540660810777215925744546848899656347269220877882, 102385886258464739091823423239617164469644309399)x2, y2 = (814107817937473043563607662608397956822280643025, 961531436304505096581595159128436662629537620355)x3, y3 = (5565164868721370436896101492497307801898270333, 496921328106062528508026412328171886461223562143)num1 = (1 + x1 ** 2) * (1 - y1 ** 2) * (x2 + x3) * (1 + y2 * y3) - 2 * x1 * (1 + y1 ** 2) * (1 + x2 * x3) * (1 - y2 * y3)num2 = (1 + y1 ** 2) * (1 - x1 ** 2) * (y2 + y3) * (1 + x2 * x3) - 2 * y1 * (1 + x1 ** 2) * (1 + y2 * y3) * (1 - x2 * x3)pmult = gcd(num1, num2)for i in range(2, 10):    while pmult % i == 0:        pmult //= i    if isPrime(pmult):        p = pmult        break
def recover_half(x, y):    k = y * (x ** 2 - 1) * pow(x * (y ** 2 - 1), -1, p) % p    l = pow(4 * k * pow(x * y, -1, p), (p + 1) // 4, p)    D = (l ** 2 + 4) % p    sqrtD = pow(D, (p + 1) // 4, p)    for i in range(-1, 2, 2):        for j in range(-1, 2, 2):            num = (i * l + j * sqrtD) * pow(2, -1, p) % p            text = long_to_bytes(num)            if b'CCTF{' in text or b'}' in text:                return text
first_half = recover_half(x3, y3)second_half = recover_half(x2, y2)flag = (first_half + second_half).decode()print(flag)```
##### Flag`CCTF{D39enEr47E_ECC_4TtaCk!_iN_Huffs?}`