# CurveCrypto - zer0pts CTF 2022
###### tags: `zer0pts CTF 2022`

Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9

## overview

A block cipher is implemented. The encryption algorithm can be shown in simple such like $c_{2k} = 2^kG.x \oplus m_{2k}$ and $c_{2k+1} = 2^kG.y \oplus m_{2k+1}$ where $G$ is the given point of the known curve $y^2 = x^3 + ax + b \mod n$.

Our purpose is to decrypt $\{ m_{i} \}$ from $\{ c_{i} \}$.

## observation

The algorithm is similar to Bulm-Goldwasser Cryptography but it uses the elliptic curve. Since Bulm-Goldwasser Cryptography is secure, it is difficult to breach the encryption scheme from the logical aspect.

Instead, it should be focused that $G.x$ and $G.y$ is likely 1024bit long, while $m_i$ is only 128bit. So we can write such that $c_{2k} = 2^kG.x + \alpha, c_{2k+1} = 2^kG.y + \beta$ where $\alpha$ and $\beta$ are relatively small value.

## solution

The following equation stands.

$(c_{2k+1} - \beta)^2 \equiv (c_{2k} - \alpha)^3 + a(c_{2k} - \alpha) + b \mod n$

The unknown variables $\alpha, \beta$ are small enough. So coppersmith's algorithm can find concrete values of $\alpha, \beta$.

Then we can easily get $2^kG.x$ and $2^kG.y$. It means we have the plaintext.

## exploit

In the exploit, https://github.com/defund/coppersmith is used as the `defund.sage`.

import ast

with open("output.txt") as f:
    n = int(f.readline().strip().split(" = ")[1])
    a = int(f.readline().strip().split(" = ")[1])
    b = int(f.readline().strip().split(" = ")[1])
    c = ast.literal_eval(f.readline().strip().split(" = ")[1])


load("./defund.sage")
PR.<dx, dy> = PolynomialRing(Zmod(n))

diffs = []
for i in range(len(c) // 2):
    x, y = c[2*i], c[2*i+1]
    f = (x + dx)**3 + a*(x + dx) + b - (y + dy)**2
    for r in small_roots(f, [2**128, 2**128])[0]:
         d = int(r)
         if d.bit_length() > 130:
            d = d - n
         diffs.append(d)

m = b''
for i in range(len(diffs)):
    p = c[i] + diffs[i]
    m += bytes.fromhex(hex(p ^^ c[i])[2:])
print(m)