<center> <h1>
SAGE
</h1></center>
# I. Số học cơ bản
## 1. Các tập hợp và Vành/Trường
### ZZ (Interger Ring - Vành số nguyên)
Đây là tập các số nguyên $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$ và nó sẽ không giới hạn độ lớn
```py=
from sage.all import *
n = ZZ(5)
print(n) #5
```
### QQ (Rational Field - Trường số hữu tỉ)
Tập các phân số $a/b$ với $a, b \in \mathbb{Z}$
```py=
a = QQ(5/2)
print(a) # 5/2
print(a + QQ(1/2)) # 3
```
Một điều khác với python là sage sẽ lưu dưới dạng phân số chứ không tính thẳng ra giá trị như python, điều này làm tăng sự chính xác khi ta tính toán các giá trị phức tạp
### Zmod(n) (Vành số dư)
Vành số nguyên modulo n
```py=
n = ZZ(15)
R = Zmod(n)
a = R(2)
b = R(3)
print(a) # 2
print(a.inverse()) # 8 (2.8 = 1 mod 15)
print(b.inverse()) # lỗi vì gcd(3, 15) != 1
```
> Với $n$ là hợp số `Zmod(n)` sẽ là một vành, còn nếu ta khai báo `Zmod(p)` với $p$ là một số nguyên tố thì ta ngầm hiểu đó là một trường
### GF(q) (Galios Field - Trường Galios)
Là một trường hữu hạn, một tập hợp có số lượng phần tử hữu hạn
- GF(q)(giống với Zmod(q))
- GF(p^k) sẽ tạo ra trường mở rộng, các phần tử trong đó không còn là số nguyên nữa mà sẽ được biễu diễn dưới dạng đa thức
Ta có thể xem bậc của một trường bằng hàm `.order()` và tìm phần tử sinh bằng hàm `.multiplicative_generator()`
```py=
F = GF(13)
print(F.order()) # 13
print(F.multiplicative_generator()) # 2
```
## 2. Các hàm hữu ích
### `legendre_symbol()`
Nhận vào 2 tham số (a, p) và kiểm tra xem có tồn tại thặng dư bậc 2 của $a \mod (p)$
Hàm này trả về 3 giá trị:
- 1: Tồn tại $x^2 \equiv a \pmod p$
- -1: $a$ không phải thặng dư bậc 2
- 0: $a$ chia hết cho $p$
```py=
print(legendre_symbol(5, 11)) # 1 (4^2 = 5 mod 11)
print(legendre_symbol(6, 11)) # -1 (không tồn tại)
```
### jacobi_symbol()
Đôi khi ta gặp trường hợp $n$ không phải là số nguyên tố (ví dụ $n = p \cdot q$). Khi đó, không thể dùng Legendre mà phải dùng Ký hiệu Jacobi. phải kiểm tra jacobi_symbol(a, n), nó là tổng quát hóa của Legendre cho số $n$ lẻ bất kỳ.
- Lưu ý: Nếu jacobi_symbol(a, n) == 1, chưa chắc $a$ đã là số chính phương modulo $n$. Nhưng nếu nó bằng $-1$, chắc chắn $a$ không phải là số chính phương.
```py=
print(jacobi_symbol(1, 15)) # 1 (đúng vì 4^2 = 1 mod 15)
print(jacobi_symbol(2, 15)) # 1 (sai vì không tồn tại)
```
Vì sao có sự sai lệch này? Ta biết định nghĩa của ký hiệu Jacobi với $n = p.q$: $$\left(\frac{a}{n}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{a}{q}\right)$$
Vậy nên sẽ có tận 2 trường hợp mà $\left(\frac{a}{n}\right)$ trả về $1$:
- $\left(\frac{a}{p}\right) = 1$ và $\left(\frac{a}{q}\right) = 1$ thì tích $1.1 = 1$
- $\left(\frac{a}{p}\right) = -1$ và $\left(\frac{a}{q}\right) = -1$, kết quả $-1.-1$ vẫn $= 1$, mặc dù nó không thỏa điều kiện $a$ là thặng dư bậc hai của $p$ và $q$.
### .rational_reconstruction(x, m)
Hàm giúp tìm lại phân số $a / b$ từ một số nguyên $x$ mod $m$ trong sage.
Khi ta có phương trình $x \equiv \frac{a}{b} \pmod m$, ta biết $x, m$ muốn tìm $a,b$ thì ta dùng hàm này.
> Thường khi $m$ đủ lớn $m > 2.max(a, b)^2$ thì mới có thể tìm chính xác
```py=
m = 10^9 + 7
x = 2 * pow(3, -1, m) % m
# x = 666666672
frac = rational_reconstruction(x, m)
a = frac.numerator()
b = frac.denominator()
print(a, b)
```
### .nth_root(n)
Nếu hàm `sqrt(n)` chỉ có thể tìm căn bậc 2 và hoạt động với số nguyên thì hàm này có tìm căn bậc bất kỳ trong một vành hoặc trường (ZZ, GF(q), Zmod(n))
```py=
print(ZZ(125).nth_root(3)) # 5
F = GF(101)
a = F(3**7)
print(a.nth_root(7)) # 3
```
### .from_integer(n) và .to_integer()
Hàm `.from_integer(n)` sẽ chuyển một số nguyên $n$ thành một phần tử tương ứng trong trường $GF(p^k)$ bằng cách lấy khai triển hệ số $p$ của n, lúc này các hệ số của khai triển sẽ tương ứng với hệ số của đa thức đó.
>Đương nhiên $0 \le n < order(GF(p^k))$
Ngược lại `to_integer()` giúp ta từ một đa thức chuyển thành số nguyên $n$
```py=
F.<a> = GF(2^3)
n = 6 # 6 = 110
print(F.from_integer(n)) # 1.a^2 + 1.a + 0.1 = a^2 + a
f = a^2 + a + 1
print(f.to_integer()) # 111 = 7
```
### factor(n)
Là một hàm quen thuộc, có công dụng là phân tích thừa số nguyên tố của $n$, nhưng khi ta chuyền tham số `limit` vào, nó sẽ chỉ phân tích ra các thừa số nguyên tố nhỏ hơn `limit` và sẽ trả về phần dư còn lại.
```py=
n = 2^1000 - 1
print(factor(n, limit = 10^6))
# 3 * 5^4 * 11 * 17 * 31 * 41 * 101 * 251 * 401 * 601 * 1801 * 4001 * 4051 * 7001 * 8101 * 28001 * 61681 * 96001 * 268501 * 340801 * 156676046863599502836458698327219410402574061964242683502223413347159054226960751478295916857235114222606496339404360158071635721291683607883904861718750693565095955832002520007614258562501840791800642151094655878963546866324525147859373701
```
### crt()
Dùng định lý thặng dư Trung Hoa để giải hệ phương trình đồng dư, nhưng nó khác với `crt()` thông thường.
Thông thường, để giải hệ:
\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}
Ta cần điều kiện $gcd(n_i, n_j) = 1$ $\forall i, j$
Nhưng với `crt()` trong sage, nó có thể giải được ngay cả khi các modulo không nguyên tố cùng nhau (miễn là có nghiệm) và giải được trên cả đa thức.
```py=
a = [2, 3, 2]
n = [3, 5, 6]
print(crt(a, n)) # gcd(3, 6) = 3 nhưng vẫn giải được ra = 8
R.<x> = PolynomialRing(QQ)
a = [x + 1, x^2]
n = [x^2 + 1, x^2 - 1]
print(crt(a, n)) # -1/2*x^3 + 1/2*x + 1
```
### log() và discrete_log()
Hai hàm này đều có thể dùng để giải quyết bài toán logarithm rời rạc (DLP), tức là tìm $x$ với $g^x \equiv h \pmod p$, hai hàm sẽ có vài điểm khác biệt
- discrete_log(h, g, ord, operation). Trong đó:
- $h$ là giá trị đã biết ($g^x = h \pmod p$)
- $g$ là cơ số
- `order` là bậc của cơ số $g$ (tùy vào cách ta truyền tham số này mà thuật toán sẽ chạy với tốc độ khác nhau)
- `operation` là chọn toán tử, mặc định là '*', ta có thể chọn `operation = '+'` trong các bài đường cong Elliptic.
- log(h, g) thì đơn giản hơn, chỉ có 2 tham số là $h, g$
```py=
F = GF(11)
print(F(3).log(F(2))) # 8 (2^8 = 3 mod 11)
K = GF(3^6, 'b')
b = K.gen()
a = b^210
print(discrete_log(a, b, K.order() - 1)) # 210 (b^210 = a mod 3^6)
```
### contiued_fraction() và convergents()
Xét một liên phân số có dạng:
$$x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\dots}}}$$
hàm `continued_fraction()` sẽ trả về một danh sách các hệ số $[a_0; a_1, a_2, a_3, \dots]$, còn convergents() trả về các convergent, là các xấp xỉ của liên phân số đó. Trong Wiener's attack, $d$ sẽ nằm đâu đó trong mẫu số của các convergents này.
Ví dụ:
:::spoiler chall.py
```py=
from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b"crypto{?????????????????????????}"
m = bytes_to_long(FLAG)
def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getPrime(256)
e = pow(d,-1,phi)
if e.bit_length() == N.bit_length():
break
return N,e
N, e = get_huge_RSA()
c = pow(m, e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
# N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
# e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
# c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
:::
Ta thấy $d$ được sinh nhỏ hơn $N$ nhiều, cụ thể $d < \frac{1}{3}N^{\frac{1}{4}}$ nên chắc chắn Wiener's attack được:
::: spoiler solve.sage
```py=
from Crypto.Util.number import *
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
cf = (e/N).continued_fraction()
for frac in cf.convergents():
d = frac.denominator()
m = long_to_bytes(pow(c, d, N))
if b'crypto' in m:
print(m.decode())
```
:::
# II. Đa thức
### var("name") và solve()
- `var` dùng để khai báo các biến dạng ký hiệu. Nó không quan tâm biến đó thuộc tập hợp số nào.
- `solve()` thường đi kèm với `var`, là một trong những công cụ mạnh mẽ của sage dùng để giải phương trình và hệ phương trình, thậm chí là bất phương trình.
```py=
var('x, y')
print(solve(x^2 - 5*x + 6 == 0, x)) # [x == 3, x == 2]
print(solve([x + y == 10, x - y == 2], [x, y])) # [[x == 6, y == 4]]
print(solve(x^2 > 1, x)) # [[x < -1], [x > 1]]
```
Mặc định, `solve()` trả về kết quả dưới dạng biểu thức ký hiệu (ví dụ [x == 2]). Điều này rất khó để lấy giá trị số ra để tính toán tiếp.
Tham số `solution_dict=True` sẽ trả về một danh sách các **Dictionary** trong Python, giúp truy cập kết quả bằng tên biến.
```py=
var('x')
sol = solve(x^2 == 9, x, solution_dict=True)
for s in sol:
print(f"Nghiệm là: {s[x]}")
# Nghiệm là: -3
# Nghiệm là: 3
```
Cách khai báo này nhanh nhưng không thực hiện được các phép toán phức tạp hơn (như tìm nghiệm trong trường hữu hạn, Coppersmith...).
### PolynomialRing() và .roots()
Đây là cách tiếp cận đại số (algebraic). Ta định nghĩa biến thuộc một vành cụ thể.
```py=
# Cách 1
R.<x> = PolynomialRing(ZZ) # Vành đa thức biến x trên tập số nguyên
# Cách 2
R = PolynomialRing(GF(11), 'x')
x = R.gen()
```
`roots()` dùng để giải phương trình, nhưng khác với `solve()`, `solve()` không dùng để giải phương trình modulo $n$ (như $x^2 \equiv 1 \pmod n$). Để giải loại này, ta bắt buộc phải dùng `PolynomialRing` và `.roots()`.
Ví dụ: Tìm nghiệm của phương trình $x^2 + 5x + 6 \equiv 0 \pmod{11}$
```py=
P.<x> = PolynomialRing(GF(11))
f = x^2 + 5*x + 6
print(f.roots()) # [(9, 1), (8, 1)]
```
> Có thể thêm tham số multiplicities=False để bỏ qua tham số bội của nghiệm
```py=
P.<x> = PolynomialRing(Zmod(15))
f = x^2 - 1
roots = f.roots(multiplicities=False)
print(roots) # [1, 4, 11, 14]
```
### `.degree()` và `.factor()`
`.degree()` trả về bậc của đa thức (với đa thức nhiều biến thì nó trả về tổng các bậc)
```py=
R.<x> = PolynomialRing(QQ)
f = 3*x^5 + 2*x^2 - 1
print(f.degree())
```
Còn `.factor()` sẽ phân tích đa thức $f(x)$ ra thành các nhân tử
```py=
R.<x> = PolynomialRing(RationalField())
f = (x^3 - 1)^2 - (x^2 - 1)^2
print(f.factor())
# (x - 1)^2 * x^2 * (x^2 + 2*x + 2)
```
### Đa thức bất khả quy
Một đa thức $f(x)$ được gọi là bất khả quy trên một vành/trường nào đó nếu nó không thể viết được dưới dạng:$$f(x) = g(x) \cdot h(x)$$Trong đó $g(x)$ và $h(x)$ là các đa thức có bậc lớn hơn hoặc bằng 1.
Việc truyền đa thức bất khả quy vào `PolynomialRing` thường nhằm mục đích tạo ra một Trường mở rộng (Galois Field) hoặc một vành.
### .is_irreducible()
Đây là hàm kiểm tra xem đa thức đó có thực sự bất khả quy trên vành đang xét hay không
```py=
R.<x> = PolynomialRing(GF(2))
f = x^8 + x^4 + x^3 + x + 1
if f.is_irreducible():
print(f"{f} là đa thức bất khả quy trên GF(2)")
```
### Cách truyền đa thức bất khả quy vào PolynomialRing
Kỹ thuật khai báo trường mở rộng $\mathbb{GF}(p^k)$ bằng cách truyền trực tiếp đa thức bất khả quy (modulus) giúp tối ưu hóa hiệu năng trong sage.
Cú pháp:
```py=
F = GF((p, k), name="tên biến", modulus=đa thức)
```
> tuple (p, k) để tránh việc Sage phải phân tích số $p^k$ nếu nó quá lớn.
>
Giả sử ta cần giải phương trình:
$$g^x \equiv T \pmod{f(x), 2}$$
Về bản chất đây là giải bài toán logarithm rời rạc (DLP) trên Trường mở rộng $\mathbb{GF}(2^{128})$, nên chúng ta sẽ áp dụng cách khai báo như trên để tối ưu
```py=
R.<x> = GF(2)[]
f = x**128 + x**7 + x**2 + x + 1
F = GF((2, 128), name="a", modulus=f)
g = F.from_integer(2)
T = g**(9876543210123456789)
order = 2**128 - 1
res = discrete_log(T, g, ord=order)
print(res) # 9876543210123456789
```
### Ép đa thức từ var sang vành đa thức khác
Vì khi tạo bằng `var()`, có một số hàm phức tạp ta không dùng được, do đó để dùng các hàm như `.roots()`, `.small_roots()`, hay `.factor()`, bắt buộc phải đưa nó về Vành đa thức.
Cách đơn giản nhất là chỉ cần lấy tên của Vành đã khai báo và bọc biểu thức var lại như một hàm.
```py=
var('x')
f = x^2 + 5*x + 6
R.<x> = PolynomialRing(ZZ)
f_ring = R(f)
print(type(f)) # <class 'sage.symbolic.expression.Expression'>
print(type(f_ring)) # <class 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
```
### .subs()
Dùng hàm này ta có thể thay thế một biến bằng một số, hoặc thay thế một biến bằng một đa thức khác trong cùng một vành một cách mượt mà
Ví dụ khi ta có đa thức $f(x, y)$ và biết $y = x^2 + 1$, ta chỉ cần `f.subs(y = x^2 + 1)` để đưa về đa thức một biến.
```py=
R.<x, y> = PolynomialRing(GF(13))
f1 = x^2 + 3*x*y + y + 5
g = f1.subs(x=10)
print(g) # 5*y + 1
f2 = x + y^2
h = x^2 + 5
f2 = f2.subs(y=h)
print(f2) # x^4 - 3*x^2 + x - 1
```
### coefficients và coefficient
Trong SageMath, để lấy các hệ số của một đa thức, ta có thể dùng các hàm như sau:
- `f.coefficient(n)`: Trả về hệ số của bậc cụ thể $x^n$.
- `f.coefficients()`: Trả về một list gồm các hệ số khác 0.
- `f.list()`: Trả về list tất cả hệ số từ bậc 0 đến bậc cao nhất (bao gồm cả số 0).
```py=
R.<x> = PolynomialRing(ZZ)
f = 5*x^3 + 2*x + 7
print(f.coefficient(3)) # 5
print(f.coefficients()) # [7, 2, 5]
print(f.list()) # [7, 2, 0, 5]
```
### .monic()
Một đa thức được gọi là monic khi hệ số cao nhất của nó bằng 1. Ta sẽ dùng hàm này nhiều vì nhiều thuật toán (như small_roots) yêu cầu đa thức đầu vào phải là monic.
Nó chia toàn bộ đa thức cho hệ số của bậc cao nhất (hoặc nhân nghịch đảo trong modulo n)
```py=
R.<x> = PolynomialRing(GF(11))
f = 3*x^2 + 6*x + 9
print(f.monic()) # x^2 + 2*x + 3
```
### change_ring()
Đây là hàm dùng để "ép" đa thức từ vành này sang vành khác mà không phải định nghĩa lại từ đầu. Ví dụ ta có đa thức trên số nguyên $ZZ$ nhưng muốn giải nghiệm nó trên trường hữu hạn $GF(p)$:
```py=
R.<x> = PolynomialRing(ZZ)
f = x^2 + 10
f = f.change_ring(GF(7))
print(f) # x^2 + 3
print(f.roots(multiplicities = False)) # [5, 2]
```
### .digits(base)
Đây là hàm dùng để phân tích một số nguyên $n$ thành một danh sách các hệ số theo hệ cơ số base. Tức là phân tích:$$n = d_0 \cdot \text{base}^0 + d_1 \cdot \text{base}^1 + d_2 \cdot \text{base}^2 + \dots + d_{k-1} \cdot \text{base}^{k-1}$$
>Lưu ý: Danh sách trả về bắt đầu từ bậc thấp đến bậc cao. Chữ số đầu tiên là hàng đơn vị ($base^0$), chữ số cuối cùng là hàng cao nhất.
Thường ta dùng `digits(p)` trong trường mở rộng $\mathbb{GF}(p^k)$
Trong trường mở rộng như `Fp = GF(p^3)`, mỗi phần tử không phải là một số mà là một đa thức có bậc tối đa là $k-1$ ví dụ:$$A = a_0 + a_1 \cdot i + a_2 \cdot i^2$$
Với $a_i \in \mathbb{GF}(p)$.
Khi ta có một số rất lớn và muốn đưa nó vào trong trường Fp, ta coi số đó là tổng của các hệ số nhân với lũy thừa của $p$.
Gọi `n.digits(p)` sẽ cho ta chính xác bộ ba $[a_0, a_1, a_2]$.Sau đó có thể dựng nên một đa trong trường bằng cách: `Fp(n.digits(p))`.
```py=
p = 13
F.<z> = GF(p^3)
n = 200
d = n.digits(p)
print(d) # [5, 2, 1]
print(F(d)) # z^2 + 2*z + 5
```
### small_roots()
Đây là một hàm rất mạnh để tìm nghiệm (đủ nhỏ) khi modulo $N$ lớn (không thể dùng `.roots()`)
Giả sử ta có đa thức $f(x)$ và một số nguyên $N$. Ta cần tìm nghiệm $x_0$ sao cho:$$f(x_0) \equiv 0 \pmod B$$Trong đó $B$ là một ước của $N$ (có thể $B=N$) và nghiệm $|x_0| < X$
Cú pháp sẽ là `f.small_roots(X, beta, epsilon)`
Trong đó:
- X là cận trên, khi ta khai báo thì tức là xét nghiệm x nhỏ hơn cận trên đó.
- beta: Độ lớn của modulo $B$ so với $N$ ($B \ge N^\beta$). Nếu modulo chính là $N$, ta chọn beta=1. Nếu modulo là $p$ (trong RSA $N=pq$), chọn beta=0.5.
- epsilon: Tham số tối ưu hóa độ chính xác. Thường mặc định là $1/8$ bậc đa thức. Càng nhỏ thì tìm được nghiệm càng lớn nhưng chạy càng lâu.
Ví dụ với challenge:
:::spoiler chall.py
```py=
#! /usr/bin/env python2
from Crypto.PublicKey import RSA
key = RSA.generate(4096, e=5)
msg = "this challenge was supposed to be babyrsa but i screwed up and now i have to redo the challenge.\nhopefully this challenge proves to be more worthy of 250 points compared to the 200 points i gave out for babyrsa :D :D :D\nyour super secret flag is: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\nyou know what i'm going to add an extra line here just to make your life miserable so deal with it"
m = int(msg.encode("hex"), 16)
c = pow(m, key.e, key.n)
f = open("paparsa.txt", "w")
print >> f, "n = {}".format(key.n)
print >> f, "e = {}".format(key.e)
print >> f, "c = {}".format(c)
n = 805467500635696403604126524373650578882729068725582344971555936471728279008969317394226798274039587275908735628164913963756789131471531490012281262137708844664619411648776174742900969650281132608104486439462068493207388096754400356209191212924158917441463852311090597438686723680422989566039830705971272945580630621308622704812919416445637277433384864510484266136345300166188170847768250622904194100556098235897898548354386415341541887443486684297114240486341073977172459860420916964212739802004276614553755113124726331629822694410052832980560107812738167277181748569891715410067156205497753620739994002924247168259596220654379789860120944816884358006621854492232604827642867109476922149510767118658715534476782931763110787389666428593557178061972898056782926023179701767472969849999844288795597293792471883445525249025377326859655523448211020675915933552601140243332965620235850177872856558184848182439374292376522160931072677877590262080551636962148104050583711183119856867201924407132152091888936970437318064654447142605921825771487108398034919404885812834444299826080204996660391375038388918601615609593999711720104533648851576138805705999947802739408729788376315233147532770988216608571607302006681600662261521288802804512781133
e = 5
c = 321344338551168130701947757669249162791535374419225256466002854387287697945811581844875867845545337575193797350159207497966826027124926618458827324785590115214765980153475875175895244152171945352397663605222668892070894285036685408001675776259216704639659684767335997326195127379070104670798191048101430782486785148455557975065509824478935393935463232461294974471055239751453456270779997852527271795223623224696998441762750417393944955667837832299195592347653873362173157136283926817115042942127695355760288879165245940595259284499711202547364332122472169897570069773912201877037737474884548477516093671861643329899650704311880900221217905929830674467383904928054908475945599046498840246878554674443087280023564313470872269644230953001876937807402083390603760508851259383686896871724061532464374712413952574633098739843484563001012414107193262431117290853995664646176812763789444386869148000606985026530596652927567162641583951775993815884965569050328445927871220492529331846189285588168127051152438658813934744257031316581112434690871286836998078235766836485498780504037745116357109237384369621143931229920342036890494878183569174869563857473355851368119174926388706612127773670862261189669510108216517652686402185979222505401328291
```
:::
Đây là một bài toán kinh điển về tấn công Coppersmith khi biết flag ẩn trong plaintext và nhỏ hơn nhiều so với plaintext . Với $e = 5$ (rất nhỏ) và $n$ = 4096 bit, chúng ta hoàn toàn có thể tìm ra phần flag bị ẩn.
Điều kiện Coppersmith: Thuật toán `small_roots` có thể tìm được nghiệm $x$ nếu $|x| < n^{1/e}$.
Ở đây $n^{1/5} \approx 2^{4096/5} \approx 2^{819}$. Phần chưa biết là 480 bit, vì $480 < 819$, nên bài này chắc chắn giải được bằng `small_roots`.
Ta viết lại plaintext m:
$$m = p + x \cdot 2^{k} + s$$
Trong đó $x$ là số nguyên của flag và $k$ là số bit của phần $s$.
Vậy tương đương ta có đa thức:
$f(x) = (m + x \cdot 2^k)^e - c \equiv 0 \pmod N$
Đến đây ta có thể Coppersmith được rồi
:::spoiler solve.sage
```py=
from Crypto.Util.number import *
n = 805467500635696403604126524373650578882729068725582344971555936471728279008969317394226798274039587275908735628164913963756789131471531490012281262137708844664619411648776174742900969650281132608104486439462068493207388096754400356209191212924158917441463852311090597438686723680422989566039830705971272945580630621308622704812919416445637277433384864510484266136345300166188170847768250622904194100556098235897898548354386415341541887443486684297114240486341073977172459860420916964212739802004276614553755113124726331629822694410052832980560107812738167277181748569891715410067156205497753620739994002924247168259596220654379789860120944816884358006621854492232604827642867109476922149510767118658715534476782931763110787389666428593557178061972898056782926023179701767472969849999844288795597293792471883445525249025377326859655523448211020675915933552601140243332965620235850177872856558184848182439374292376522160931072677877590262080551636962148104050583711183119856867201924407132152091888936970437318064654447142605921825771487108398034919404885812834444299826080204996660391375038388918601615609593999711720104533648851576138805705999947802739408729788376315233147532770988216608571607302006681600662261521288802804512781133
e = 5
c = 321344338551168130701947757669249162791535374419225256466002854387287697945811581844875867845545337575193797350159207497966826027124926618458827324785590115214765980153475875175895244152171945352397663605222668892070894285036685408001675776259216704639659684767335997326195127379070104670798191048101430782486785148455557975065509824478935393935463232461294974471055239751453456270779997852527271795223623224696998441762750417393944955667837832299195592347653873362173157136283926817115042942127695355760288879165245940595259284499711202547364332122472169897570069773912201877037737474884548477516093671861643329899650704311880900221217905929830674467383904928054908475945599046498840246878554674443087280023564313470872269644230953001876937807402083390603760508851259383686896871724061532464374712413952574633098739843484563001012414107193262431117290853995664646176812763789444386869148000606985026530596652927567162641583951775993815884965569050328445927871220492529331846189285588168127051152438658813934744257031316581112434690871286836998078235766836485498780504037745116357109237384369621143931229920342036890494878183569174869563857473355851368119174926388706612127773670862261189669510108216517652686402185979222505401328291
p = b"this challenge was supposed to be babyrsa but i screwed up and now i have to redo the challenge.\nhopefully this challenge proves to be more worthy of 250 points compared to the 200 points i gave out for babyrsa :D :D :D\nyour super secret flag is: "
s = b"\nyou know what i'm going to add an extra line here just to make your life miserable so deal with it"
m = bytes_to_long(p + b"\x00"*60 + s)
k = len(s) * 8
R.<x> = PolynomialRing(Zmod(n))
f = (m + x * 2^k)^e - c
f = f.monic()
roots = f.small_roots(X=2^(60*8), epsilon = 0.05)
if roots:
print(long_to_bytes(int(roots[0])).decode())
#flag{bu7_0N_4_w3Dn3sdAy_iN_a_c4f3_i_waTcH3dD_17_6eg1n_aga1n}
```
:::
Và một bài DLP:
:::spoiler chall.py
```py=
from Crypto.Cipher import AES
from secret import key, FLAG
p = 4170887899225220949299992515778389605737976266979828742347
ct = bytes.fromhex("ae7d2e82a804a5a2dcbc5d5622c94b3e14f8c5a752a51326e42cda6d8efa4696")
def crack_safe(key):
return pow(7, int.from_bytes(key, 'big'), p) == 0x49545b7d5204bd639e299bc265ca987fb4b949c461b33759
assert crack_safe(key) and AES.new(key,AES.MODE_ECB).decrypt(ct) == FLAG
```
:::
Đây là một bài DLP vì mục tiêu của ta là tìm $key$ để giải mã AES tìm được flag, $key$ thì là $x$ trong phương trình:
$$7^x \equiv h \pmod p$$
Nhưng nếu ta dùng luôn hàm `discrete_log` có sẵn trong sage luôn thì chắc chắn không giải ra
```py=
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
p = 4170887899225220949299992515778389605737976266979828742347
h = 0x49545b7d5204bd639e299bc265ca987fb4b949c461b33759
g = 7
ct = bytes.fromhex("ae7d2e82a804a5a2dcbc5d5622c94b3e14f8c5a752a51326e42cda6d8efa4696")
F = GF(p)
g = F(g)
h = F(h % p)
x = discrete_log(h, g, ord=p-1)
key = long_to_bytes(int(x)).rjust(16, b'\x00')[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ct)
print(flag.decode())
```
Lý do là tác giả đã cố tình chọn $p-1$ có một thừa số nguyên tố rất lớn. factor p-1 ta sẽ thu được
```2 * 19 * 151 * 577 * 67061 * 18279232319 * 111543376699 * 9213409941746658353293481```
Nên để giải bài này ta phải tự chia trường hợp với từng thừa số sẽ dùng một thuật khác nhau, tên gọi chính xác là DLP trên nhóm con.
Ta phân tích x ra là: $x = x_0 + i.\delta$, với `delta` = p // q. ($q$ là cái thừa số lớn kia)
Làm như vậy để ta DLP tìm x0, đơn giản là:
```py=
x0 = discrete_log(h^q, g^q)
```
Bởi vì là:
Nâng cả hai vế phương trình $g^x \equiv h \pmod p$ lên lũy thừa $q$:
$$(g^x)^q \equiv h^q \pmod p$$
Mà ta có $x = x_0 + i \cdot \delta$:
$$(g^{x_0 + i \cdot \delta})^q \equiv h^q \pmod p$$
$$(g^q)^{x_0} \cdot (g^{\delta \cdot q})^i \equiv h^q \pmod p$$
Vì $\delta \cdot q = p-1$, theo định lý Fermat nhỏ: $g^{p-1} \equiv 1 \pmod p$.
Ta sẽ thu được phương trình khử được $i$
$$(g^q)^{x_0} \cdot 1^i \equiv h^q \pmod p$$
Sau khi có x0 ta tìm $i$ như sau:
```py=
i = discrete_log((h * (g^x0)^-1), (g^delta))
```
Vì
$$g^{x_0 + i \cdot \delta} \equiv h \pmod p$$
$$g^{i \cdot \delta} \equiv h \cdot (g^{x_0})^{-1} \pmod p$$
Nhìn phức tạp nhưng nó là dạng DLP luôn rồi
Đặt $G = g^{\delta}$ và $H = h \cdot (g^{x_0})^{-1}$.
Ta sẽ thấy phương trình quen thuộc:
$$G^i \equiv H \pmod p$$
Có x0 và $i$ là ta tính được x rồi.
:::spoiler
```py=
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
p = 4170887899225220949299992515778389605737976266979828742347
h = 0x49545b7d5204bd639e299bc265ca987fb4b949c461b33759
g = 7
ct = bytes.fromhex("ae7d2e82a804a5a2dcbc5d5622c94b3e14f8c5a752a51326e42cda6d8efa4696")
FF = GF(p)
g = FF(g)
h = FF(h % p)
factors = [f for f, e in factor(p-1)]
q = factors[-1]
delta = (p-1) // q
x0 = discrete_log(h^q, g^q)
print(x0)
i = discrete_log(h * (g^x0)^-1, g^delta)
x = x0 + i * delta
print(x)
key = long_to_bytes(int(x))[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ct)
print(flag.decode())
# uiuctf{Dl0g_w/__UnS4F3__pR1Me5_}
```
:::
# III. Ma trận/Vector
### Khởi tạo Ma trận
Trong SageMath, Ma trận không chỉ là một mảng số, nó phải thuộc về một Vành (Ring).
Cách dùng: `Matrix()`
Đầy đủ : Matrix(Vành, số hàng, số cột, dữ liệu)
```py=
M = Matrix(ZZ, 2, 3, [1, 2, 3, 4, 5, 6])
```
> Ma trận 2x3 trên vành số nguyên ZZ
```py=
M = Matrix(GF(2), [[1, 0], [1, 1]])
```
> Nếu dùng list lồng nhau, Sage tự hiểu kích thước
Tạo ma trận ngẫu nhiên:
```py=
M = random_matrix(ZZ, 4, 4, x=-10, y=10)
```
> Ma trận 4x4 ngẫu nhiên trên ZZ, các phần tử dtừ -10 đến 10
### `identity_matrix` và `diagonal_matrix`
`identity_matrix`(n): Ma trận đơn vị $I_n$ (đường chéo toàn số 1, còn lại là 0).
`diagonal_matrix`([list]): Ma trận đường chéo, trong đó mọi phần tử ngoài đường chéo chính đều bằng 0.
```py=
I = identity_matrix(3) # [1 0 0], [0 1 0], [0 0 1]
D = diagonal_matrix([5, 10, 15]) # [5 0 0], [0 10 0], [0 0 15]
```
> Ma trận đường chéo có thể là ma trận đơn vị
### Thao tác trên ma trận (`.augment`, `.stack`, `block_matrix`)
Ghép ma trận:
- .`augment(M)`: Ghép thêm cột vào bên phải (ngang).
- `.stack(M)`: Ghép thêm hàng vào bên dưới (dọc).
- `block_matrix([[A, B], [C, D]])`: Ghép các khối ma trận lại với nhau.
```py=
A = identity_matrix(2)
B = Matrix(ZZ, 2, 2, [5, 5, 5, 5])
print(A.augment(B))
"""
[1 0 5 5]
[0 1 5 5]
"""
print(B.stack(A))
"""
[5 5]
[5 5]
[1 0]
[0 1]
"""
print(block_matrix([[A, B], [B, A]]))
"""
[1 0|5 5]
[0 1|5 5]
[---+---]
[5 5|1 0]
[5 5|0 1]
"""
```
Ví dụ ta cần tính vector $C = K \cdot V$
với $K = \begin{pmatrix} x + 2 & 1 \\ 3 & x^2 + 5 \end{pmatrix}$, $V = \begin{pmatrix} x \\ 2 \end{pmatrix}$
Tính cụ thể tại x = 4:
```py=
R.<x> = PolynomialRing(GF(11))
K = Matrix(R, [[x + 2, 1], [3, x^2 + 5]])
V = vector(R, [x, 2])
C = K * V
res = C.subs(x=4)
print(res) # (4, 10)
```
Trích xuất và Chỉnh sửa
- Lấy hàng/cột: `M.row(i)`, `M.column(j)`.
- Xóa hàng/cột: `M.delete_rows([i])`, `M.delete_columns([j])`.
- Chuyển vị: `M.transpose()` hoặc M.T.
### `.det()`
Tính định thức của ma trận, có thể dùng để kiểm tra ma trận có khả nghịch không:
```py=
M = Matrix(ZZ, 2, 2, [3, 1, 5, 7])
print(M.det()) # 16
```
### `.solve_right` và `.solve_left`
Dùng để giải hệ phương trình, cụ thể cho hệ phương trình $A \cdot x = B$
- `.solve_right(B)`: sẽ tìm vector $x$ .
- `.solve_left(B):` thì tìm vector $x$ cho hệ $x \cdot A = B$.
Ví dụ ta cần giải hệ phương trình sau trên vành số hữu tỷ:$$\begin{cases} x + 2y + 3z = 1 \\ 4x + 5y + 6z = -2 \\ 7x + 8y + 10z = 5 \end{cases}$$
Ta sẽ ma trận hóa các hệ số trên để thu được phương trình: $A.x = B$, rồi dùng `.solve_right()` để tìm ẩn
```py=
A = Matrix(QQ, [[1, 2, 3], [4, 5, 6], [7, 8, 10]])
B = vector(QQ, [1, -2, 5])
x = A.solve_right(B)
print(x) # (7, -18, 10)
```
### `.right_kernel()` và `.left_kernel()`
Tương tự như trên, nhưng lúc này vế phải là $0$ chứ không phải ma trận $B$.
- `.right_kernel()`: Tìm tập hợp các vector $x$ sao cho $A \cdot x = 0$.
- `.left_kernel()`: Tìm tập hợp các vector $x$ sao cho $x \cdot A = 0$.
Bên cạnh đó, với một ma trận vuông khả nghịch ($\det \neq 0$), phương trình $A \cdot x = 0$ chỉ có một nghiệm duy nhất là $x = 0$.
Khi ma trận suy biến, thì Kernel mới có những vector $x \neq 0$ mà khi nhân với $A$ sẽ trở thành vector $0$).
```py=
M = Matrix(ZZ, [[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print(M.right_kernel().basis()) # [(1, -2, 1)]
```
> Khi tìm Kernel của một ma trận suy biến, SageMath sẽ trả về một đối tượng gọi là Vector Space. Nhưng đối tượng này không thể dùng để tính toán được. Ta dùng `.basis()` nó trả về những vector cụ thể.
### `.eigenvalues()` và `.eigenvectors_right()`
`.eigenvalues()`: Trả về các trị riêng $\lambda$ thỏa mãn $A \mathbf{v} = \lambda \mathbf{v}$.
`.eigenvectors_right()`: Trả về các tuple gồm trị riêng, vector riêng $\mathbf{v}$, số bội tương ứng.
```py=
M = Matrix(QQ, [[1, 2], [2, 1]])
print(M.eigenvalues()) # [3, -1]
print(M.eigenvectors_right()) # [ (3, [(1, 1)], 1), (-1, [(1, -1)], 1) ]
```
> Cũng giống như solve_right, chữ right ở đây có nghĩa là vector $\mathbf{v}$ nằm bên phải ma trận: $M \mathbf{v} = \lambda \mathbf{v}$.
Nếu dùng eigenvectors_left, Sage sẽ tìm vector hàng $\mathbf{u}$ nằm bên trái sao cho: $\mathbf{u} M = \lambda \mathbf{u}$.
### Khởi tạo vector
Cũng giống như Ma trận, Vector cần được xác định trên một Vành hoặc Trường.
Cú pháp: `vector(Vành, list)`
```py=
v1 = vector(ZZ, [1, 2, 3])
v2 = vector(RR, [1.5, 2.7, 3.1])
v3 = vector(GF(7), [1, 6, 2])
```
Có hai cách chính để tạo dữ liệu ngẫu nhiên cho vector:
Dùng hàm random_vector(): `random_vector(Vành, số_chiều)`
```py=
v_rand = random_vector(ZZ, 10, x=-100, y=100)
```
Lấy từ một VectorSpace:
```py=
V = VectorSpace(GF(2), 64)
v = V.random_element()
print(v)
```
### VectorSpace()
VectorSpace là không gian chứa các vector. Nó định nghĩa các quy tắc về số chiều và cơ sở.
Khởi tạo: `V = VectorSpace(Trường, Số_chiều)`
Các hàm phổ biến:
- `.dimension()`: Trả về số chiều của không gian.
- `.basis()`: Trả về tập hợp các vector cơ sở.
- `.subspace([danh_sách_vector])`: Tạo một không gian con từ các vector cho trước.
- ` a in V`: Kiểm tra xem một vector $a$ có nằm trong không gian $V$ hay không.
```py=
V = VectorSpace(QQ, 4)
v1 = vector(QQ, [1, 2, 0, 0])
v2 = vector(QQ, [0, 1, 1, 0])
W = V.subspace([v1, v2])
print(W.dimension()) # 2
print(W.basis()) # [(1, 0, -2, 0), (0, 1, 1, 0)]
v = vector(QQ, [1, 3, 1, 0])
u = vector(QQ, [0, 0, 0, 1])
print(v in W) # True
print(u in W) # False
```
### Ghép Ma trận và Vector
`M.augment(v)`: Ghép vector v vào làm cột cuối cùng của ma trận M.
> Điều kiện: Số phần tử của v phải bằng số hàng của M.
`M.stack(v)`: Ghép vector v vào làm hàng cuối cùng của ma trận M.
> Điều kiện: Số phần tử của v phải bằng số cột của M.
```py=
M = identity_matrix(ZZ, 3)
v = vector(ZZ, [7, 8, 9])
print(M.augment(v))
# [1 0 0 7]
# [0 1 0 8]
# [0 0 1 9]
print(M.stack(v))
# [1 0 0]
# [0 1 0]
# [0 0 1]
# [7 8 9]
```
Và mình đã vận dụng toàn bộ kiến thức đã học để giải lại bài này:
::: spoiler chall.py
```py=
from Crypto.Util.number import *
from random import randint
flag = b'KCSC{??????????????????????????????????????????????????????????????????????????????????????????}'
assert flag.startswith(b"KCSC{") and len(flag) == 96
# my prime generator
def get_prime(factor_bits, nbits):
while True:
p = 2
while p.bit_length() + factor_bits < nbits:
p *= getPrime(factor_bits)
current_len = p.bit_length()
needed_bits = nbits - current_len
if needed_bits < 2:
continue
try:
last_prime = getPrime(needed_bits)
except ValueError:
continue
p = p * last_prime + 1
if p.bit_length() == nbits and isPrime(p):
return p
p = get_prime(16, 128)
q = get_prime(16, 128)
n = p * q
phi = (p-1)*(q-1)
# 3 parts of the flag
m1, m2, m3 = [bytes_to_long(part) for part in [flag[i:i+32] for i in range(0, len(flag), 32)]]
assert all(part < n for part in [m1, m2, m3])
es = []
cs = []
for i in range(3):
# rsa encryption
e1, e2, e3 = [randint(1, phi-1) for _ in range(3)]
c1 = pow(m1, e1, n)
c2 = pow(m2, e2, n)
c3 = pow(m3, e3, n)
es.append((e1, e2, e3))
# cs.append((c1, c2, c3)) # nah, too easy
cs.append((c1 * c2 * c3) % n) # what if i multiply them together ?
# write outputs to file
with open("output.txt", "w") as f:
f.write(str(n) + "\n")
f.write(str(es) + "\n")
f.write(str(cs))
```
:::
Mình sẽ chỉ nói lại cách giải mới. Mục tiêu là tìm các $x_i$ trong phương trình:
$$g^{e_1 x_1 + e_2 x_2 + e_3 x_3} \equiv c \pmod p$$
Lấy log g 2 vế:
$$e_1 x_1 + e_2 x_2 + e_3 x_3 \equiv \log_g(c) \pmod{p-1}$$
> Vì $$g^{x + (p-1)} = g^x \cdot g^{p-1} \equiv g^x \cdot 1 \equiv g^x \pmod p$$
Với 3 phương trình, ta có hệ ma trận:
$$E \cdot X = L \pmod{\phi}$$
Hay:
$$\begin{pmatrix} e_{11} & e_{12} & e_{13} \\ e_{21} & e_{22} & e_{23} \\ e_{31} & e_{32} & e_{33} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \equiv \begin{pmatrix} L_1 \\ L_2 \\ L_3 \end{pmatrix} \pmod{p-1}$$
Hệ phương trình này được giải trên vành $\mathbb{Z}_{p-1}$ và $\mathbb{Z}_{q-1}$. Sau khi tìm được bộ $(x_1, x_2, x_3)$, ta khôi phục $m_{i,p} = g^{x_i} \pmod p$ và $m_{i,q} = g^{x_i} \pmod q$.
Sau đó CRT để kết hợp $m_{i,p}$ và $m_{i,q}$ tìm lại $m_i \pmod n$.
:::spoiler solve.sage
```py=
from Crypto.Util.number import *
from itertools import product
n = 47671780042231704413040913594725353438536469505015682546574752585718301112921
es = [(23977172217622484168774759837385378732502237507920113310285233140285669132645, 7377494923066904273449829226282557300745689267275904429462158991949281414682, 18432112474217778047559883846454066035490987127796230294276735606306725549777),(3124743981175141708117586893234378699895764583129200589303495951740637999914, 22762044917281148499181453892958515527103600842740372832842228589873412009197, 17680895854953441923244596894140851738984314699825793211831691205085172067322),
(37545236985478706251704483601220896064218212306586005333560412013908096438729, 20788835878098532955063747621021775806003893333625966206551591514326857932485, 32312926559646114857217655963694360470473973949883002194388252273197485497673),]
cs = [42267207336603045334786451171189000378049455207827292631901571990305135126669,33840845882520281865996502853093641414955191938495377599016576841954115079220,18018251336838883503303580652480693144525524464022122529153696030852723761647]
p, q = 208241528391730184734449228964657137983, 228925423331290125959230566821710134887
def DLP(mod):
phi = int(mod - 1)
F = GF(mod)
g = F.multiplicative_generator()
R = Zmod(phi)
E = Matrix(R, es)
L = vector(R, [F(c).log(g) for c in cs])
x_p = E.solve_right(L)
gens = E.right_kernel().gens()
B = Matrix(R, gens)
orders = [phi // gcd([int(x) for x in v] + [phi]) for v in gens]
sol = [x_p + vector(R, cf) * B for cf in product(*(range(o) for o in orders))]
return [[int(pow(g, i, mod)) for i in x] for x in sol]
for m1, m2 in product(DLP(p), DLP(q)):
flag = b""
for i in range(3):
flag += long_to_bytes(crt([m1[i], m2[i]], [p, q]))
if b"KCSC{" in flag:
print(flag.decode())
# KCSC{I_hope_you_used_factor_and_discrete_log_to_solve_this_challenge_9f72b5a7608c076684b6ca6157}
```
:::
Sign in with Wallet
Connect another wallet