# System of Equations
> 1 chút hệ phương trình

$$
\begin{equation}
\begin{cases}
x^2+2xy+8z=4z^2+4y+8\\
x^2+y+2z=4(2p+1)
\end{cases}\
\end{equation}
$$

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os

FLAG = b'W1{???}'

x = int(input("Nhap x nguyen: "))
y = int(input("Nhap y nguyen: "))
z = int(input("Nhap z nguyen: "))

assert x**2 + 2*x*y - 8 == 4*z**2 + 4*y - 8*z
assert x**5 + y**3 == 10823714993004958804353333960725385073542379465721 - z**4 
assert 8864612849141*x**2 + 8864612849141*y + 17729225698282*z == 205022233466935232483321764396

mode = str(input("Nhap phuong thuc (encrypt hoac decrypt): "))

secret = (str(x**10) + str(y**10) + str(z**10)).encode()
key = hashlib.sha256(secret).digest()

if mode == "encrypt":
    iv = os.urandom(16)
    c = AES.new(key, AES.MODE_CBC, iv).encrypt(pad(FLAG, 16))

    print(f'iv = {iv}')
    print(f'ciphertext = {c}')
    
elif mode == "decrypt":
    iv = b'\x8d\r\x19\xbc\xfd\x84\x13N,\xf85\xdb\xd3\x92i\x93'
    ciphertext = b'\xe9\xa2\x8c\x8b\xc3\xb4\x88\xe2\xbb\x96\xc6\xac`\x1c}\xd1\xca\xc1ZB\xf1@\x01\x92\xca\xc4Z[\x96o\xdeFv\xdf\r\x13u+\x89\xac3\xa3\xc9X\xfb\x07u\x1bO\x9c\xb0\xbdN\xa4\xb6\xca&T\xabmx\xdb\xae\xc2'
    
    FLAG = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext), 16)
    print(FLAG.decode())
    
else:
    exit(1)

### Giải
Phương trình đầu cho ta biết rằng x chẵn, sau đó phương trình thứ 2 cho ta biết y chẵn.
Đặt $x=2x_1, y=2y_1$, hệ phương trình trở thành:
$$
\begin{equation}
\begin{cases}
x_1^2+2x_1y_1+2z=z^2+2y_1+2\\
2x_1^2+y_1+z=2(2p+1)
\end{cases}\
\end{equation}
$$

Tiếp tục, phương trình 1 cho ta biết: $x_1\equiv z\mod 2$, phương trình 2 cho ta biết: $x_1\equiv z\mod 2$. Nếu $x_1, y_1, z$ chẵn, phương trình 1 không thỏa vì vế trái chia hết cho 4, vế phải $\equiv 2\mod 4$.

Như vậy, tất cả cùng lẻ. Đặt $x_1=2u+1, y_1 = 2v-1,z=2w+1$ và hệ trở thành:
$$
\begin{equation}
\begin{cases}
u^2+2uv=w^2\\
4u^2+4u+v+w=2p
\end{cases}\
\end{equation}
$$
1) Nếu $u=0$
Nghĩa là w = 0 và v = 2p và có nghiệm $(x, y, z) = (2, 8p-2, 1)$
2) Nếu $u\ne0$

Phương trình đầu chứng minh là $u|w^2$ và vì thế ta có thể viết $u=ab^2, w=abc$ với 1 vài số square-free a và b, c khác 0.
Hệ trở thành:
$$
\begin{equation}
\begin{cases}
v=\dfrac{a(c^2-b^2)}{2}\\
v=2p-4a^2b^4-4ab^2-abc
\end{cases}\
\end{equation}
$$

và từ đó: $a(c^2-b^2)$ chẵn và $a(c^2-b^2)=4p-8a^2b^4-8ab^2-2abc$
$\Leftrightarrow a(b+c)^2=4p-8a^2b^4-8ab^2 \ (1)$

Vì thế số square-free a chia hết 4p và $a\in \{1,2, p, 2p\}$ vì a dương
Đặt $(b+c)=N$, phương trình trở thành: $(8ab^2+3)^2+8aN=32p+9$

Vì a > 0, ta có $8ab^2+3\le\sqrt{32p+9}$ và từ đó $1\le b^2\le\dfrac{\sqrt{32p+9}-3}{8a}$
Suy ra: $a\le\dfrac{\sqrt{32p+9}-3}{8}$. Rõ ràng, $\dfrac{\sqrt{32p+9}-3}{8} < p,\forall p>1\Leftrightarrow\sqrt{32p+9}<8p+3,\forall p>1\Leftrightarrow64p^2-16p>0,\forall p>1$
Nghĩa là $a < p$ nên a chỉ nhận được hai giá trị $\{ 1, 2\}$.

- $a = 1$, thay vào $(1)$ ta có: $-8b^4-6b^2+4p$ là số chính phương k nào đó
- $a = 2$, thay vào $(1)$ ta có: $-16b^4-6b^2+2p$ là số chính phương k nào đó
Brute-force đoạn này sẽ đơn giản và ta sẽ có bộ nghiệm:
$(x,y,z)=(4ab^2+2,2a(c^2-b^2)-2,2abc+1)$, với $c = \sqrt{k} - b$

Script:

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from tqdm import trange
import hashlib, math

def check_scp(n: int) -> bool:
    if n < 0:
        return False
    root = int(math.isqrt(n))
    return root * root == n

ans = 23128165544962556
p = (ans - 4) // 8
print("Voi a = 1: ")
a = 1
for b in trange(2**12):
    k = -8*b**4 - 6*b**2+4*p
    if check_scp(k):
        cp = math.isqrt(k)
        c = cp - b
        x, y, z = 4*a*b**2+2, 2*a*(c**2-b**2) - 2, 2*a*b*c + 1
        print(f'Bộ nghiệm: {x, y, z}')
        
print("Voi a = 2: ")
a = 2
for b in trange(2**12):
    k = -16*b**4 - 6*b**2+2*p
    if check_scp(k):
        cp = math.isqrt(k)
        c = cp - b
        x, y, z = 4*a*b**2+2, 2*a*(c**2-b**2) - 2, 2*a*b*c + 1
        print(f'Bộ nghiệm: {x, y, z}')
        
secret = (str(x**10) + str(y**10) + str(z**10)).encode()

key = hashlib.sha256(secret).digest()

# copy the iv and ciphertext
iv = b'\x8d\r\x19\xbc\xfd\x84\x13N,\xf85\xdb\xd3\x92i\x93'
ciphertext = b'\xe9\xa2\x8c\x8b\xc3\xb4\x88\xe2\xbb\x96\xc6\xac`\x1c}\xd1\xca\xc1ZB\xf1@\x01\x92\xca\xc4Z[\x96o\xdeFv\xdf\r\x13u+\x89\xac3\xa3\xc9X\xfb\x07u\x1bO\x9c\xb0\xbdN\xa4\xb6\xca&T\xabmx\xdb\xae\xc2'

FLAG = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext), 16)
print(FLAG.decode())

# https://artofproblemsolving.com/community/c6t281f6h1965032_problem_6_of_third_round