<div style="text-align:center">
<h1>Imaginary CTF 2025</h1>
</div>

## scalar-division

Source code :

assert ((E:=EllipticCurve(GF(0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21),[5,7])).order().factor(limit=2**10)[3][0]*E.lift_x(ZZ(int.from_bytes((flag:=input('ictf{')).encode())))).x() == 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5 and not print('\033[53C\033[1A}')

Vâng bạn không nhìn nhầm đâu, Source code challenge chỉ có duy nhất một dòng. Nếu viết lại dưới dạng bình thường thì ta sẽ có Source như này :

from sage.all import *

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
a = 5
b = 7

E = EllipticCurve(GF(p), [a, b])
n = E.order()
k = n.factor(limit=2**10)[3][0]

P = E.lift_x(ZZ(int.from_bytes((flag:=input('ictf{')).encode()))).x()
Q = k * P
xQ = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5
assert Q == xQ

Nhìn qua Source code thì ta có thể thấy Flag của ta sẽ là tọa độ $x$ của một điểm $P$ thỏa mãn đẳng thức :
$$
k.P=Q
$$

Với việc biết được tọa độ $x$ của điểm $Q$ và giá trị $k$, ta sẽ phải tìm lại được giá trị tọa độ của điểm $P$ thì mới khôi phục được Flag.

Đây chính là bài toán Inverse Scalar Multiplication trên ECC. Cụ thể hơn thì ta sẽ có cách tính như sau :
- Giả sử trên một Elliptic Curve ta có hai điểm $P$ và $Q$ và một số nguyên $k$ thỏa mãn :
$$
Q=[k]P
$$
- Nếu ta biết được giá trị $k$ và tọa độ điểm $Q$ thì ta có thể khôi phục lại tọa độ của điểm $P$ bằng cách :
- Tính giá trị $h\equiv k^{-1}\pmod{n}$, với $n=|E(\mathbb{F}_p)|$ là order của $E$ trong trường hữu hạn $\mathbb{F}_p$
- Khi đó ta sẽ có :
$$
P=[h]Q=[h.k]P
$$

Đó chính là cách để tìm lại được tọa độ của $P$. Vậy nếu áp dụng trong Challenge này liệu có được không? Tất nhiên là không được rồi. Bởi vì ta có ở đoạn này :

k = n.factor(limit=2**10)[3][0]
P = E.lift_x(ZZ(int.from_bytes((flag:=input('ictf{')).encode()))).x()
Q = k * P

Ta có thể thấy, $k$ ở đây lại chính là một thừa số nguyên tố của $n$. Điều đó khiến cho việc tìm nghịch đảo của $k$ trong Modulo $n$ là không thể. Vậy thì ta sẽ phải tính như thế nào đây?

Ta có được đẳng thức :
$$
Q=[k]P
$$

Với $k$ là một thừa số nguyên tố thỏa mãn $|E(\mathbb{F}_p)|=n=k.h$. Khi biết được $k$ và $Q$ thì theo trực giác thì để tính được điểm $P$ thì ta sẽ biến đổi như này :
$$
P=\frac{1}{k}Q
$$

Tuy nhiên trong ECC, ta sẽ không thể trực tiếp thực hiện phép chia như vậy được mà thay vào đó ta sẽ tính :
$$
s\equiv k^{-1}\pmod{h}
$$

$$
\Leftrightarrow sk=1+th
$$

Bây giờ ta đặt $P_0=[s]Q$. Khi đó ta có :
$$
[k]P_0=[sk]Q
$$

Thay $sk=1+th$ ta có :
$$
[k]P_0=[sk]Q=[1+th]Q=Q+[th]Q
$$

Mà vì ta có được :
$$
hQ=h(kP)=nP=\mathcal{O}
$$

Nên :
$$
[k]P_0=Q
$$

Điều đó cho ta thấy được : Ngoài $P$ ra vẫn sẽ tồn tại một điểm $P_0$ khác cũng thỏa mãn đẳng thức :
$$
[k]P=Q
$$

Hay nói cách khác, ta sẽ có một dạng tổng quát hơn của điểm $P$ như sau : $$P=P_0+R$$

Với $R$ là các điểm thuộc $\text{ker}([k])$, tức là các điểm $R$ thỏa mãn $[k]R=\mathcal{O}$. Sau cùng, ta sẽ có đẳng thức sau :
$$
[k]P=[k](P_0+R)=[k]P_0+[k]R=[k]P_0=Q
$$

Nhưng ta sẽ tìm $R$ như nào? Đơn giản là ta chỉ cần lấy một điểm bất kì thuộc Elliptic Curve $E$ ban đầu và nhân điểm đó với $h$ là được. Đó là bởi vì nếu đặt $T$ là một điểm bất kì thuộc $E$, ta có :
$$
kR=k(hT)=nT=|E(\mathbb{F}_p)|T=\mathcal{O}
$$

Như vậy là ta tìm được lại được điểm $P$ rồi. Nó sẽ có dạng tổng quát là :
$$
P=P_0+iR
$$

với :
- $P_0=[k^{-1}\mod(h)]Q$
- $R=[h]T$, với $T$ là một điểm bất kì thuộc Elliptic Curve ban đầu Challenge cho
- $i\in [1,457]$

Giờ chỉ cần brute-force $i$ rồi kiểm tra từng giá trị toạ độ $x$ cho mỗi điểm $P$ sao cho khi chuyển về bytes ta thu được một chuỗi kí tự có nghĩa là được rồi!!!

Full script :

from sage.all import * 
from Crypto.Util.number import *
import string

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
a = 5
b = 7

E = EllipticCurve(GF(p), [a, b])
n = E.order()
# k = n.factor(limit=2**10)[3][0]
k = 457

xQ = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5

Q = E.lift_x(ZZ(xQ))
h = n // k
inv_k = pow(k, -1, h)
s = inv_k

P0 = s * Q
R = E.random_point() * h
for i in range(1, k):
    tmp = P0 + R*i
    if all([i in (string.ascii_letters + string.digits + '_').encode() for i in long_to_bytes(int(tmp.x()))]):
        print("ictf{" + long_to_bytes(int(tmp.x())).decode() + "}")

Tuy nhiên, ngoài cách giải như trên thì mình vẫn còn một cách khác hay hơn. Trong SageMath, ta có một phương thức như này : `multiplication_by_m()`. Cụ thể, phương thức này sẽ trả về cho ta một hàm phân thức hệ số nguyên biểu diễn sự phụ thuộc của giá trị $[n]P.x()$ vào giá trị $P.x()$. Phương thức này sẽ nhận vào hai tham số là :
- `n` : Giá trị Scalar của một điểm, tức là giá trị $n$ dùng để tính $[n]P$
- `x_only=` : Dùng để hiển thị sự phụ thuộc của giá trị $[n]P.x()$ vào giá trị $P.x()$. Mặc định sẽ là False, tức sẽ hiện sự phụ thuộc vào cả hai giá trị $P.x()$ và $P.y()$. Còn nếu đặt là True thì chỉ hiện sự phụ thuộc vào giá trị $P.x()$ thôi.

Vậy ta sẽ áp dụng nó vào bài này như thế nào? Khi sử dụng phương thức này ta sẽ nhận về một đa thức dạng :
$$
\frac{N_n(x_P)}{D_n(x_P)}
$$

với $N_n$ và $D_n$ là hai đa thức có biến là $x_P$. Mục tiêu của ta là tìm được tọa độ điểm $P$ thỏa mãn : $$[n]P=Q$$ Ta có được giá trị của $n$ và tọa độ $x$ của điểm $Q$, nên không khó để xây dựng được một phương trình có dạng : $$\frac{N_n(x_P)}{D_n(x_P)}=x_Q$$ Khi này ta sẽ có được một phương trình chỉ có duy nhất một ẩn $x_P$, và chỉ cần giải nó là sẽ có được $x_P$ thỏa mãn rồi. Nhưng liệu điều đó có khả thi không? Khi ta thử chạy phương thức đó với $n=457$ thì ta có :

from sage.all import *

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
a = 5
b = 7

E = EllipticCurve(GF(p), [a, b])
n = 457
f = E.multiplication_by_m(n, x_only=True)
N_n = f.numerator()
D_n = f.denominator()

print(N_n.degree())	#208849
print(D_n.degree())	#208848

Có thể thấy, bậc của hai đa thức tử và mẫu của hàm phân thức trên là rất lớn. Điều đó khiến cho việc tìm nghiệm của chúng trở nên rất là khó, thậm chí là bất khả thi. Vậy chúng ta nên giải phương trình này như nào đây?

Tất nhiên là vẫn còn cách rồi. Thay vì giải phương trình trên một cách trực tiếp thì ta sẽ dùng một cách khác nhanh hơn (hay nó giống như là một trick lỏ :penguin:). Đó chính là tính GCD giữa hai đa thức với nhau. Trước hết, ta sẽ biến đổi lại đa thức ban đầu của ta như sau :
$$
\frac{N_n(x_P)}{D_n(x_P)}=x_Q
$$

$$
\Leftrightarrow N_n(x_P)=x_Q\times D_n(x_P)
$$

$$
\Leftrightarrow N_n(x_P)-x_Q\times D_n(x_P)=0
$$

Đặt : $$f(x_P)=N_n(x_P)-x_Q\times D_n(x_P)$$ Ta sẽ tính GCD của đa thức này với một đa thức khác là : $$g(x)=x^p-x$$ Tại vì sao lại tính GCD với đa thức này? Xét trong trường hữu hạn $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ (với $p$ là số nguyên tố), ta có **định lý Fermat nhỏ** như sau :
$$
x^p\equiv x\pmod{p}
$$

$$
\Leftrightarrow x^p-x\equiv 0\pmod{p}
$$

Có thể thấy, vì $p$ là số nguyên tố nên với mọi số nguyên $x_0$ bất kì thuộc khoảng $[0,p-1]$ đều sẽ là nghiệm của đa thức $g(x)=x^p-x$ trong Modulo $p$. Hay một cách ngắn gọn hơn, đa thức $g(x)=x^p-x$ trong trường hữu hạn $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ sẽ có tất cả $p$ nghiệm nguyên dương, từ $0$ cho tới $p-1$. Chính vì vậy, khi ta tính GCD giữa hai đa thức $f(x)$ và $g(x)$ sẽ cho ta một đa thức có bậc nhỏ hơn, và đa thức đó sẽ chứa nghiệm mà ta cần tìm.

Nhưng vẫn chưa hết! Số nguyên tố $p$ của ta lại là một số rất là lớn, dài tới khoảng $400$ bits. Điều đó khiến cho đa thức $g(x)$ cũng có bậc rất là lớn. Vậy thì ta sẽ phải xử lý như nào? Đơn giản là ta sẽ áp dụng Modulo đa thức $f(x)$ vào trong đa thức $g(x)$ này nhằm đưa bậc của nó về lại bằng hoặc bé hơn bậc của đa thức $f(x)$. Có như vậy ta sẽ có thể áp dụng được GCD cho cả hai đa thức này để cho ra được một đa thức có bậc nhỏ hơn, để từ đó có thể tìm được nghiệm $x_P$ thỏa mãn đa thức đó, và đó cũng chính là Flag của ta.

Full Script :

from Crypto.Util.number import *
from sage.all import *
import string

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
a = 5
b = 7

E = EllipticCurve(GF(p), [a, b])
n = E.order()
# k = n.factor(limit=2**10)[3][0]
k = 457

xQ = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5

f = E.multiplication_by_m(k, x_only=True)
f = f.numerator() - xQ * f.denominator()

R.<x> = PolynomialRing(Zmod(p))
f = R(f)
g = pow(x, p, f) - x

tmp = g.gcd(f).roots()
for i in tmp:
    x = i[0]
    if all([i in (string.ascii_letters + string.digits + '_').encode() for i in long_to_bytes(int(x))]):
        print("ictf{" + long_to_bytes(int(x)).decode() + "}")

<details>
<summary>Flag</summary>
ictf{mayb3_d0nt_m4ke_th3_sca1ar_a_f4ctor_0f_the_ord3r}
</details>