# 2025 成大資安密碼學社課
:::warning
希望各位先跟著「環境建置」建好環境，想要獲得最好的課程體驗可以看看「基礎基礎數論」
:::
> 所有的 lab 和大部分的 exploit 都在這個專案裡面，感覺這種教學類的東西不給 exploit 好像蠻怪的，就都附上了。
Github: https://github.com/rota1001/NCKUCTF-Crypto-Course
錄影 1：[Crypto I](https://www.youtube.com/watch?v=_iAfJMaLHAo)
## 環境建置
以下都是在 ubuntu 裡面的，用其他發行板的話要自己想辦法，如果不是用 linux 的話那建議你裝 linux。
### 安裝 anaconda
因為等等會安裝很多 python 套件，為了不把環境弄髒，會使用 anaconda 這樣的虛擬環境：
```shell
$ wget https://repo.anaconda.com/archive/Anaconda3-2025.06-1-Linux-x86_64.sh
```
害怕內容被竄改可以先確定一下 hash：
```shell
$ sha256sum https://repo.anaconda.com/archive/Anaconda3-2025.06-1-Linux-x86_64.sh
# 82976426a2c91fe1453281def386f9ebebd8fdb45dc6c970b54cfef4e9120857 Anaconda3-2025.06-1-Linux-x86_64.sh
```
為執行檔加上可執行權限，然後執行它：
```shell
$ chmod +x Anaconda3-2025.06-1-Linux-x86_64.sh
$ sudo ./Anaconda3-2025.06-1-Linux-x86_64.sh
```
接下來一直按 enter 和輸入 yes 就會開始跑安裝。
跑了一段時間後，你會看到以下選項，意思是問你要不要讓你啟動 shell 的時候自動啟用 conda，我建議不要，但是這裡為了方便起見回答 yes，如果你覺得不舒服再想辦法修掉：
```shell
Do you wish to update your shell profile to automatically initialize conda?
This will activate conda on startup and change the command prompt when activated.
If you'd prefer that conda's base environment not be activated on startup,
run the following command when conda is activated:
conda config --set auto_activate_base false
You can undo this by running `conda init --reverse $SHELL`? [yes|no]
[no] >>> yes
```
確定一下有沒有裝好：
```shell
$ conda --version
conda 25.5.1
```
### 安裝 sagemath
前面的 conda 一定要先裝好，然後建立一個有 sagemath 的虛擬環境：
```shell
$ conda create --name sageenv sage=10.6 -c conda-forge
```
跑完之後，可以用以下命令去啟用虛擬環境：
```shell
$ conda activate sageenv
```
這時候，如果你的 prompt 的最前面出現了 `(sageenv)` 就代表你成功了。
如果你想退出可以用以下命令：
```shell
$ conda deactivate
```
接下來所有東西，建議都在啟用這個虛擬環境的情況下安裝。
### 安裝 pycryptodome
```shell
$ pip install pycryptodome
```
### 安裝 gmpy2
```shell
$ pip install gmpy2
```
### 安裝 pwntools
```shell
$ pip install pwntools
```
## 常用 python 語法
### bytes
他是 python 的另一種字串，基本上可以和 `str` 進行互換。
下面就是一個 `bytes` 的例子：
```python
b"helloworld"
```
如果要把一個 `bytes` 換成 `str` 可以用 `decode` 的方式：
```python
b"hello".decode() #b"hello"
```
如果要把一個 `str` 轉換為 `bytes` 可以用 `encode` 的方式：
```python
"hello".encode() #b"hello"
```
`bytes` 可以轉成 hex 字串：
```python
b"hello".hex() #68656c6c6f
```
hex 字串也能轉成 `bytes`：
```python
bytes.fromhex("68656c6c6f") #b'hello'
```
### pycryptodome
最常見的是 `long_to_bytes` 與 `bytes_to_long`。
這裡要先說明大端序（big endian）與小端序（little endian）。從例子出發比較容易解釋，現在有一個字串 `"\x01\x02\x03\x04"`，如果把它以大端序轉成數字的話就是 `0x01020304`，如果以小端序轉成數字就是 `0x04030201`。初學者可以找一個你比較好記憶的方式，我個人是直接用定義記的，下面做一些補充，如果覺得太無聊可以把下面一段跳掉：
> 會有這樣的分別，和計算機的底層設計有一定的相關性。從定義出發的話，就是以 byte（位元組）為單位，小端序的字串記憶體低位是數字的低位，大端序的字串記憶體低位是數字的高位。這樣講沒聽過的人一定聽不懂，這裡舉個實際例子。同樣是用 `"\x01\x02\x03\x04"`，如果這個字串的開頭記憶體位置是 `0x80000000` 的話，那 `\x01` 這個位元組的地址是 `0x80000000`、`\x02` 的地址是 `0x80000001`、`\x03` 的地址是 `0x80000002`、`\x04` 的地址是 `0x80000003`，會發現記憶體位置由低到高依序是 `\x01`、`\x02`、`\x03`、`\x04`。至於數字的低位的意思是離個位數比較近的位數，用小端序將它轉換成數字的話就是 `0x04030201`。
`long_to_bytes` 和 `bytes_to_long` 就是以大端序將 bytes 型別的字串與數字做轉換，是密碼學很常用的函式，是這樣使用的：
```python
from Crypto.Util.number import *
print(long_to_bytes(0x01020304)) #b'\x01\x02\x03\x04'
print(hex(bytes_to_long(b"\x01\x02\x03\x04"))) #0x1020304
```
### pwntools
這是一個可以拿來和遠端或本地程式互動的工具，在 crypto 與 pwn 都常用到。
:::warning
在 pwntools 裡，不管是接收訊息還是發送訊息都是使用 `bytes` 型別而不是 `str` 型別的，雖然說你發送訊息的時候如果用 `str` 只是會跳警告，但養成好習慣用 `bytes` 比較好。
:::
#### 建立遠端物件
可以建立一個遠端物件，之後會透過它和目標交互。可以用 `remote` 建立與對應 ip 與 port 的連線：
```python
r = remote("127.0.0.1", 10005)
```
也可以用 `process` 去與本地程式交互：
```python
r = process("./chal")
```
用 `process` 的時候也可以帶參數，譬如說今天我要用 python 執行某個程式的話可以這樣做：
```python
r = process(["python", "hello.py"])
```
以下我約定上都用 `r` 來作為遠端物件。
#### 接收訊息
有以下一些常用的接收訊息的方法：
```python
r.recvline() # 接收直到 b"\n"
r.recvuntil(b"a") # 接收直到 b"a"
r.recv(4) # 接收 4 個字元
```
以下舉個例子，如果和你互動的程式執行了以下這段程式碼：
```python
#!/usr/bin/python3
print("hello\nyyyya12345678")
```
然後你用下面這段程式碼與它交互：
```python
from pwn import *
r = process("./chal.py")
print(r.recvline())
print(r.recvuntil(b"a"))
print(r.recv(4))
```
那你會獲得以下的輸出：
```
b'hello\n'
b'yyyya'
b'1234'
```
#### 傳送訊息
```python
r.sendlineafter(b":", b"hello") # 在收到 b":" 後送出 b"hello\n"
r.sendline(b"hello") # 送出 b"hello\n"
r.send(b"hello") # 送出 b"hello"
```
#### interactive
這個功能可以把遠端的輸入輸出接到標準輸入輸出，讓你可以在 terminal 裡和遠端互動：
```python
r.interactive()
```
## 基礎基礎數論
沒有打錯字，是兩個基礎，因為基礎數論其實是沒那麼基礎的東西。這裡會補充一點數學小知識，但也不會講很多，也不會用精準的數學語言。
這裡社課大概不會全部講。
### mod（模除）
除以 mod 的餘數相等的數視為相等，譬如說：
$1 \equiv 4 \pmod{3}$
$22 \equiv 15 \pmod{7}$
==一個簡單性質是 $a \equiv b \pmod{m}$ 等價於 $m$ 是 $a-b$ 的因數==
譬如說：
$1 \equiv 4 \pmod{3}$，發現 3 是 $1-4$ 的因數
$22 \equiv 15 \pmod{7}$，發現 $7$ 是 $22-15$ 的因數
在 python 中，`%` 是取模的運算子，值得注意的細節是，在 python 中對負數取模，結果會是非負整數。
==這裡最重要的性質是，如果將等號兩邊同時加減乘除在模 $m$ 下相等的數字，等號依然成立。==
### 模逆元
有一個模數 $m$ 和一個整數 $a$，如果有個整數 $x$ 使得 $a\times x \equiv 1 \pmod{m}$，則 $x$ 是 $a$ 在模 $m$ 下的模逆元，譬如說：
$2\times 2 \equiv 1 \pmod{3}$，所以 $2$ 是 $2$ 在模 $3$ 下的模逆元
$3 \times 5 \equiv 1 \pmod{14}$，所以 $5$ 是 $3$ 在模 $14$ 下的模逆元
整數 $a$ 的模逆元，約定上可以用 $a^{-1}$ 來表示，而模逆元的模逆元是自己。
==模逆元可以想像成是在模 $m$ 下的 $a$ 的倒數，既然有倒數我們就能定義除法了。==
另外，在模 $m$ 下的乘法有結合律，所以可以有些可愛的性質。前面知道了 $3$ 是 $5$ 在模 $14$ 下的模逆元，可以觀察下下面的運算：
$6\times5 \equiv 2\times3\times5 \equiv2\times3\times3^{-1} \equiv2 \pmod{14}$
可以發現，$6$ 乘以 $5$ 這個操作，其實就像是 $6$ 除以 $3$。
並不是每個 $a$ 在模 $m$ 底下都有模逆元，更準確的來說只有與 $m$ 互質的那些 $a$ 有模逆元，證明很簡單可以自己反證一下。
==也可以很顯然的知道，在模質數 $p$ 下，除了 $p$ 的倍數以外的數都有模逆元==
在 python 中求模逆元很簡單，就是直接用 `pow` 傳 -1 次方就好。首先講一下 python 的 `pow` 有 3 個參數，第 1 個是底數，第 2 個是指數，第 3 個是模數。譬如說我要算 2 的 30 次方模 97 就是：
```python
pow(2, 30, 97)
```
那如果我要求 35 在模 87 底下的模逆元可以這樣：
```python
pow(35, -1, 87)
```
### 模方程
模方程就是在模 $m$ 下的方程式，譬如如果有一個模方程 $ax \equiv b \pmod{m}$，只有 $x$ 未知，要怎麼解呢？以下分成兩種情況討論：
第一種情況，如果 $a$ 與 $m$ 互質，代表 $a$ 在模 $m$ 下有模逆元 $a^{-1}$，於是可以兩邊同乘 $a^{-1}$，可以得到 $x\equiv a^{-1}b\pmod{m}$
第二種情況，$a$ 與 $m$ 不互質，就代表 $a$ 與 $b$ 有一個最大公因數 $d$ 且 $d$ 是 $m$ 的因數且 $\frac{a}{d}$ 與 $\frac{m}{d}$ 互質。於是我們可以列出另一個等價的方程式：$(\frac{a}{d})x=\frac{b}{d}\pmod{\frac{m}{d}}$，然後就能併入第一種情況討論。
同樣的運算技巧可以用在更多元或多次的模方程中。
### 中國剩餘映射
如果 n 是一個大於 1 的正整數，而他有質因數分解 $p_1^{k_1}\times p_2^{k_2}\times ... \times p_m^{k_m}$ 的話，然後對於一個在 $[0, n-1]$ 這個區間的整數 $a$，如果可以找到一組 $a_1$、$a_2$、...、$a_m$ 的整數滿足：
$a\equiv a_1 \pmod{p_1^{k_1}}$
$a\equiv a_2 \pmod{p_2^{k_2}}$
$...$
$a\equiv a_m \pmod{p_m^{k_m}}$
然後為了方便起見，先設 $a_i$ 都是符合條件的最小非負整數。
==重要的一件事情是 $a$ 與 $(a_1,a_2,...,a_m)$ 這個數組之間存在一對一的映射關係。==
從 $a$ 映射到 $(a_1,a_2,...,a_m)$ 非常簡單，至於怎麼做反向的映射呢？sagemath 幫我們寫好了：
```python
from sage.all import *
# n = p1^k1 * p2^k2 * p3^k3
a = crt([a1, a2, a3], [p1**k1, p2**k2, p3**k3])
```
### 費馬小定理
如果整數 $a$ 和質數 $p$ 互質的話，則
$a^{p-1}\equiv 1\pmod{p}$
### 歐拉函數
$\varphi(n)$ 代表小於 $n$ 的正整數中與 $n$ 互質的數字數量。
以下是簡單的計算方法：
如果 $p$ 是質數且 $n=p^k$ 的話（$k$ 是正整數），$\varphi(n)=p^{k-1}(p-1)$。
至於其他情況怎麼做呢？
歐拉函數是一個積性函數，意思是如果 $a$ 與 $b$ 互質，則 $\varphi(ab)=\varphi(a)\times\varphi(b)$。所以如果 $n=p_1^{k_1}\times p_2^{k_2}\times ... \times p_m^{k_m}$ 的話，則 $\varphi(n)=(p_1-1)p_1^{k_1-1}(p_2-1)p_2^{k_2-1}...(p_m-1)p_m^{k_m-1}$
### 歐拉定理
如果 $a$ 與 $n$ 互質的話，則：
$a^{\varphi(n)}\equiv 1\pmod{n}$
如果有興趣去看一些代數的東西的話，可以去看一下拉格朗日定理，你會對歐拉定理有更深刻的理解。
### 二次剩餘
二次剩餘就是模 $m$ 意義下的平方根。如果對於一個整數 $a$ 可以找到 $x$ 使得 $x^2\equiv a \pmod{m}$ 的話，那麼 $a$ 就是模 $m$ 下的二次剩餘，否則 $a$ 就是非二次剩餘。
先討論 $m$ 是 $p^k$ 的情況下（之後約定上不特別講 $p$ 都是質數），如果這個模方程存在一個解 $x$ 就必然存在另一個解 $-x$。
對於一個不是 $p^k$ 的 $m$ 我們可以利用中國剩餘映射把它映射到一堆 $p_i^{k_i}$，很顯然的把映射過去的模方程的解映射回來之後，同樣會是在模 $m$ 底下的模方程的解。如果對於每個 $p_i^{k_i}$ 這個模方程都有解的話，那麼每個 $p_i^{k_i}$ 都會提供兩個不同的解。
順道一題，如果有個模數 $n=p_1p_2$，在模 $n$ 底下平方根的難度等價於對 $n$ 做質因數分解的難度。
## base64
base64 是一種編碼而非加密，編碼是一對一，不需要金鑰的映射。base64 很常見，特徵是有時候結尾會有 `=` 或 `==`。
我最常用來計算 base64 的方法是 python：
```python
from base64 import b64encode, b64decode
s = b"hello world"
enc = b64encode(s)
print(enc)
dec = b64decode(enc)
print(dec)
```
## sagemath
sagemath 是一個很好用的數學庫，基本上就是密碼學的 IDA pro。
首先介紹一個東西叫做有限體 $GF(p)$。體用簡單的話講就是一個「數字的集合」和「加、減、乘、除」運算構成的東西，但是不能除以 0。有限體 $GF(p)$ 可以當作是所有數字都在模 $p$ 下做運算，加減乘不多說，除法就是用模逆元。
### 矩陣與向量
可以用 `matrix` 建立一個矩陣，第一個參數放一個體或環（最常用的是有限體 $GF(p)$），第二個參數放一個二維的 list：
```python
from sage.all import *
M = matrix(GF(2), [[1, 0], [1, 1]])
print(M)
# [1 0]
# [1 1]
```
用 `vector` 可以建立一個向量，第一個參數是環或體，第二個參數放一個一維的 list：
```python
from sage.all import *
v = vector(GF(2), [1, 0])
print(v)
# (1, 0)
```
### 解線性方程式
前面有提到 matrix 和 vector，如果我們在 $GF(2)$ 下要求 $Mx=v$ 的解的話，可以這樣：
```python
sol = list(M.solve_right(v))
print(sol)
# [1, 1]
```
### 用 `PolynomialRing` 解方程式
首先要說什麼是多項式環，你可以當作是係數在某個環（或體）下的多項式，譬如說是在 $GF(p)$ 下好了，就是係數運算都在模 $p$ 下的多項式。
在 sage 中你可以用 `PolynomialRing` 創建一個多項式環，第一個參數是一個環或體，第二個參數是有哪些變數，然後你可以用 `gens()` 把變數取出來：
```python
P = PolynomialRing(GF(97), "x")
x, = P.gens()
```
它也可以宣告多變數的多項式環：
```python
P = PolynomialRing(GF(97), "x, y")
x, y = P.gens()
```
多項式環中的變數可以組成多項式，也能使用 `roots` 對多項式求根（但 `sage` 預設只能對單變數多項式求根）：
```python
P = PolynomialRing(GF(97), "x")
x, = P.gens()
f = 2 * x - 100
print(f.roots()[0][0])
# 50
```
#### resultant
兩個多項式 $f(x_1, x_2, ..., x_n)$ 與 $g(x_1, x_2, ..., x_n)$ 對於 $x_1$ 的 resultant 就是 $f(x_1, x_2, ..., x_n) = 0$ 與 $g(x_1, x_2, ..., x_n) = 0$ 兩個方程式利用 $x_1$ 去做消去後得到的多項式 $h(x_2, x_3, ..., x_n)$。可以簡單的理解為 $f$ 與 $g$ 兩個多項式消去 $x_1$ 會變成 $h$。
實際操作比較好理解，以下是間接抄來的模板：
```python
# Copied from https://blog.maple3142.net/2021/08/01/cryptoctf-2021-writeups
from sage.all import *
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
# Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
return Matrix.determinant(f1.sylvester_matrix(f2, var))
P = PolynomialRing(ZZ, "x, y")
x, y = P.gens()
f = x + y - 5
g = x + 2 * y - 7
h = resultant(f, g, x)
print(h)
```
這先建立了 $f = x + y - 5$ 與 $g = x + 2y - 7$ 兩個多項式，$h$ 是他們兩個對於 $x$ 的結式，輸出的結果為以下：
```
y - 2
```
可見它就是兩個多項式消去 $x$ 所得到的多項式。
我們可以對 $h$ 求解求出 $y$ ，但要注意的是現在 $h$ 還是一個多變數的多項式環中的多項式，我們可以利用 `remove_var` 將一個多項式環去掉一些變數降級為另一個多項式環：
```python
Q = P.remove_var(x)
```
將 $h$ 變成一個在單變數環中的多項式（要注意的是強置轉型只能使用在單變數多項式環），並求根：
```python
h = Q(h)
print(h.roots()[0][0])
```
這是一個在 sage 中求複雜的聯立方程式的方便方法。
#### baby_polynomial
```python
def func1(x, y, z, p):
return (x * y**4 + y**2 + x * z) % p
def func2(x, y, z, p):
return (x * y * z ** 3 + y * z + x) % p
def func3(x, y, z, p):
return (x + y + x * z) % p
def challenge():
p = getPrime(128)
x, y, z = getRandomRange(1, p), getRandomRange(1, p), getRandomRange(1, p)
a = func1(x, y, z, p)
b = func2(x, y, z, p)
c = func3(x, y, z, p)
print(f"{p = }")
print(f"{a = }")
print(f"{b = }")
print(f"{c = }")
x, y, z = list(map(int, input("input x, y, z: ").strip().split(", ")))
if a == func1(x, y, z, p) and b == func2(x, y, z, p) and c == func3(x, y, z, p):
print("Success!!!")
print(f"The flag is {FLAG.decode()}")
else:
print("Something Wrong")
```
這題就是無趣的把各個變數一個一個消掉與帶入，以下是 exploit：
```python
from sage.all import *
from Crypto.Util.number import *
from pwn import *
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
# Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
return Matrix.determinant(f1.sylvester_matrix(f2, var))
def func1(x, y, z):
return x * y**4 + y**2 + x * z
def func2(x, y, z):
return x * y * z ** 3 + y * z + x
def func3(x, y, z):
return x + y + x * z
r = remote("127.0.0.1", 10005)
r.recvuntil(b" = ")
p = int(r.recvline().strip().decode())
r.recvuntil(b" = ")
a = int(r.recvline().strip().decode())
r.recvuntil(b" = ")
b = int(r.recvline().strip().decode())
r.recvuntil(b" = ")
c = int(r.recvline().strip().decode())
P = PolynomialRing(GF(p), "x,y,z")
x, y, z = P.gens()
f = func1(x, y, z) - a
g = func2(x, y, z) - b
h = func3(x, y, z) - c
fx = P.remove_var(y, z)(resultant(resultant(f, g, z), resultant(f, h, z), y))
x_sol = int(fx.roots()[0][0])
fx = x - x_sol
fy = P.remove_var(x, z)(resultant(resultant(f, g, z), fx, x))
y_sol = int(fy.roots()[0][0])
fy = y - y_sol
fz = P.remove_var(x, y)(resultant(resultant(f, fx, x), fy, y))
z_sol = int(fz.roots()[0][0])
print(f(x_sol, y_sol, z_sol))
print(g(x_sol, y_sol, z_sol))
print(h(x_sol, y_sol, z_sol))
payload = f"{x_sol}, {y_sol}, {z_sol}".encode()
r.sendlineafter(b": ", payload)
```
## PRNG
隨機數生成是電腦科學中一件重要的事情。隨機數分為真隨機數和偽隨機數，真隨機數就是透過一些幾乎無法預測的外部資訊來產生（如噪音雜訊之類的），大部分時候考慮到生成的效率，程式設計師會轉而使用偽隨機數，也就是 prng。prng 就是從一個初始 seed 通過特定的方法生成更多隨機數，簡單來說就是從一個隨機數生成更多的隨機數。
偽隨機數有時候會有一些基於算法的弱點，也就是當我們知道一部分的偽隨機數後就可以預測後面的偽隨機數。
### lcg
#### baby_lcg
$x_1 \equiv a\times secret + b \pmod{m}$
$x_2 \equiv ax_1 + b \pmod{m}$
$x_3 \equiv ax_2 + b \pmod{m}$
$x_4 \equiv ax_3 + b \pmod{m}$
於是我們可以發現：
$m\ |\ ax_1+b-x_2$
$m\ |\ ax_2+b-x_3$
$m\ |\ ax_3+b-x_4$
於是對這三個數字取最大公因數就可以求出 $m$ 了，那就可以解一個模方程得到 $secret$：
$secret=(x_1-b)a^{-1}$
```python
from Crypto.Util.number import *
from functools import reduce
k = [3789148457740350108916132915370947281028685563707348323881016374299882896679245929631358910297543154251086261216201631867332975067539825986528919990513841, 2145499982073699419438513017983799863618744752503782735449230604842559182998809288046915191987961627097857739473461538224549606412232279097077026759765365, 4967251727665233473804230430901510063299258542249797968374682896998177932623786506346773418383700206949451912147625851447724716094353399225438956773212589, 8046762133531701601499983436777547647421256490083329389543604238393425766694129431348280735528057828224058714132996152306004264783467501575390055204829135, 7883306212970583938172542885086636089646993834462858442515014676410203548285595572675859395216521442249631379541270181316944604363948625396825602200930687, 8820424737102766396286594249558652342286360215497202892435977499149235757040395993732788187577631876303327774060528891652517137465705206365647082105368311, 7197650061723133635473317387494140885735605522287272253312195047435893687376251975742085368549450397093328214176568146390518825840437832946486523499147198, 628179665400819037556977216514637417366062514363823800300056229976358326922094221014001508332732807617422670246276926169875290671171399993016391667489252, 4402391625419033407745650706485480329422008025656479758763273701932010115792640982022853411458857166628643955520778734467541619513624441441614320843117289, 6051606982205779367170774221083445325207246872109328216501569257036121158362122850776849339724029569811032045008349761480767883631354212158097894007954442]
a = 13105568607311865900719288866098594505025142450950723803234150868508669378850618674764530617802138416698278735457536272217755011333702651331642969928238378
b = 7609894268236428025470144180108229816262546135610797250928076003741685805220771552782762560301070130423255021856512797670433007975921480065990823381229326
muls = [a * k[i] + b - k[i + 1] for i in range(len(k) - 1)]
m = reduce(GCD, muls)
x = pow(a, -1, m) * (k[0] - b) % m
print(long_to_bytes(x))
```
### lfsr
LFSR 就是一種線性生成新的 bit 與位移組成的一種 prng。具體來說看看下面這個例子：
```python
def lfsr():
mask = getRandomNBitInteger(512)
x = getRandomNBitInteger(512)
while True:
for _ in range(512):
x = (x >> 1) | ((int(x & mask).bit_count() & 1) << 511)
yield x
```
我把 $x$ 的各個位元都各視為一個變數，數字比較小的是低位：
$[x_{511},x_{510},...x_{0}]$
經過一次的迭代它會右移一位，並且算出 $x_{512}$：
$[x_{512},x_{510},...x_{1}]$
$x_{512}$ 算出來的方法是透過計算 `x & mask` 的 bit 是 1 的數量，如果這個數量是奇數，它就是 1，如果是偶數，它就是 0。
我們同樣能把 $mask$ 的每個位元都各表示為一個變數：
$[mask_{511}, mask_{510}, ..., mask_{0}]$
`x_512` 可以表示為這樣：
`x_512 = (mask_511 & x_511) ^ (mask_510 & x_510) ^ ... ^ (mask_0 & x_0)`
這個 prng 只要有夠多的已知隨機數就能算出後面的隨機數了，怎麼做呢？
會發現，位元的 `&` 與 `^` 運算分別對應到了 $GF(2)$ 中的乘法與加法。所以 $x_{512}$ 的生成可以在 $GF(2)$ 下表示為以下：
$x_{512}=mask_{511}x_{511}+mask_{510}x_{510}+...+mask_{0}x_{0}$
同樣的關係式可以繼續往下列：
$x_{512}=mask_{511}x_{511}+mask_{510}x_{510}+...+mask_{0}x_{0}$
$x_{513}=mask_{511}x_{512}+mask_{510}x_{511}+...+mask_{0}x_{1}$
...
$x_{1023}=mask_{511}x_{1022}+mask_{510}x_{1021}+...+mask_{0}x_{511}$
這可以化成一個線性方程式：
$$
\left[
\begin{array}{ccc}
x_{512} \\
x_{513} \\
... \\
x_{1023}
\end{array}
\right] \\
= \left[
\begin{array}{ccc}
x_{511} & x_{510} & ... & x_{0}\\
x_{512} & x_{511} & ... & x_{1}\\
... & ...& ... & ...\\
x_{1022} & x_{1021} & ... & x_{511}\\
\end{array}
\right]
\left[
\begin{array}{ccc}
mask_{511} \\
mask_{510} \\
... \\
mask_{0}
\end{array}
\right]
$$
於是，我們可以用 sage 來解這個方程式。
#### baby_lfsr
```python
def lfsr(mask):
x = getRandomNBitInteger(512)
while True:
for _ in range(512):
x = (x >> 1) | ((int(x & mask).bit_count() & 1) << 511)
yield x
p = lfsr(bytes_to_long(FLAG))
k = [next(p) for i in range(2)]
print(k)
```
就裸題，把 flag 當作 mask，把用上述方式把它解出來。
#### strange_lfsr
Hint: ||做 `^` 運算對奇偶性的影響是什麼||
### MT19937
因為之前看蠻多 MT19937，這裡出了一個 MT19937 題組，實際的課程中不會全講。
MT19937 是一個由 624 個 32 位元的整數 state 構成的隨機數，每個 state 可以一一映射到一個 32 bit 的隨機數。生活中最常見到的 MT19937 使用情境就是 python 的 random：
```python
import random
print(random.getrandbits(32))
```
以上這段程式碼會去呼叫 `random.getrandbits(32)`，它會生出一個 32 位元的隨機數。
這裡不會去解釋 MT19937 裡面是怎麼做的，這個在一些進階的玩法裡面會用到，以下只講一些簡單的應用。
#### gf2bv
https://github.com/maple3142/gf2bv.git
這是一個有名的 CTF 玩家 [maple3142](https://github.com/maple3142/) 寫的專案，可以方便的求解一些在 $GF(2)$ 下的方程式，可以用以下命令安裝：
```shell
$ sudo apt update
$ sudo apt install -y libm4ri-dev
$ git clone https://github.com/maple3142/gf2bv.git
$ cd gf2bv
$ pip install .
```
根據專案的範例，可以知道他的使用方法。使用 `LinearSystem` 這個類別可以生成一些變數的 bitvec，輸入是一個 list，裡面每個數字代表一個變數的位元數，譬如如果我要宣告 2 個變數，都是 2 位元的話，就可以這樣宣告：
```python
from gf2bv import *
linear_system = LinearSystem([2, 2])
```
使用 `LinearSystem` 中的 `gens` 方法可以拿到裡面的變數，如我要用 `x` 和 `y` 這兩個變數來存這兩個 2 位元的變數可以這樣做：
```python
x, y = linear_system.gens()
```
`LinearSystem` 中的 `solve_one` 可以拿來求出方程組的一個解。他的輸入是一個 list，裡面每個元素都是等於 0 的方程式，譬如如果有個方程式叫做 `x ^ y = 1` 的話，那麼這個方程式在這個 list 中的表示是 `x ^ y ^ 1`。假如你要解 `x ^ y = 1` 與 `x = 1` 的解，那你可以這樣做：
```python
zeros = [x ^ y ^ 1, x ^ 1]
print(linear_system.solve_one(zeros))
```
你就能得到 `(1, 0)`
#### baby_mt19937
因為 MT19937 總共有 624 個 state，而因為 state 和 32 bit 的隨機數是一一對應的，我們可以把 624 個隨機數變成 624 個 state，於是就能預測後面所有隨機數了。
```python
import random
from Crypto.Util.number import *
from secret import FLAG
k = [random.getrandbits(32) for i in range(624)]
print(k)
print(bytes_to_long(FLAG) ^ random.getrandbits(512))
```
這題就是給 624 個連續的 32 bit 隨機數，一般來說普遍的密碼學教學會使用 [randcrack](https://github.com/tna0y/Python-random-module-cracker)，但因為他的使用情境受限，這裡直接使用 [gf2bv](https://github.com/maple3142/gf2bv/)。他有內建 MT19937 的演算法，能直接把 bitvec 作為 MT19937 的 state，生成由這些變數表示出來的隨機數。
使用 MT19937 這個類別可以用 624 個 32 bit 的 bitvec 生成一個 MT19937 的隨機數生成器：
```python
from gf2bv import *
from gf2bv.crypto.mt import MT19937
linear_system = LinearSystem([32] * 624)
mt = MT19937(linear_system.gens())
```
`MT19937` 這個類別有 `getrandbits` 這個方法，可以這樣生成方程式，並且去求解：
```python
import random
zeros = []
for i in range(624):
zeros.append(random.getrandbits(32) ^ mt.getrandbits(32))
sol = linear_system.solve_one(zeros)
```
`MT19937` 這個類別也可以傳入一個由 int 組成的 tuple，並且使用 `to_python_random` 轉換成一個 `Random` 物件：
```python
mt = MT19937(sol).to_python_random()
```
現在拿到的這個 `Random` 物件會與一開始的 `random` 的狀態一樣，所以要先生成 624 個 32 bit 的隨機數回到現在的狀態：
```python
for i in range(624):
mt.getrandbits(32)
print(mt.getrandbits(32) == random.getrandbits(32))
```
把上面的程式碼合起來後會發現我們成功的預測了下個 `random` 會生出的隨機數了。
如果我們再加個以下這行，會發現它同樣會輸出 `True`：
```python
print(mt.getrandbits(512) == random.getrandbits(512))
```
這是因為 `Random` 中的方法，大部分都是基於這個 state 生出來的，所以到這步我們就能預測絕大部分 `random` 生出來的隨機數了
這題的 exp 如下：
```python
from gf2bv import *
from gf2bv.crypto.mt import MT19937
from Crypto.Util.number import *
k = [2849927700, 535021263, 2811049904, 225959001, 1469934288, 3766367749, 3481129872, 1079454924, 2515878426, 676608532, 2051961264, 3985398266, 3929102228, 2348278814, 4160411242, 1301783174, 1445783338, 2719933889, 3462282962, 1687556045, 555252121, 3449210936, 1379739742, 2737520860, 2135800564, 1968403600, 803066257, 2750193679, 2242750002, 3504329669, 3731598632, 2221328161, 2162039091, 3752513393, 1413451772, 674120424, 2733161413, 967553646, 4209723869, 1032994191, 890885592, 1116535191, 4136393481, 2741723146, 2295687389, 3395844591, 3456266148, 651443231, 993543568, 2608816160, 4251345222, 1674931055, 64388364, 2265168910, 2574084807, 528173351, 1339633855, 3589286481, 2404135269, 4212528222, 165092560, 3521630647, 1234357837, 1221214421, 1580281724, 3735422781, 2357897072, 3607997478, 4275841654, 1194132595, 2102279096, 356087475, 2422410387, 2306923814, 2679041706, 1136695935, 1562888217, 3298331587, 1831781127, 3624660371, 2800530527, 2077140056, 2503113519, 3554861786, 1875344503, 483660915, 2582136516, 1930875970, 4019139667, 1841121214, 359821252, 4251628443, 1038092057, 3739124786, 2537593212, 1648045230, 3677630754, 3043886059, 167182926, 1616024975, 3167364157, 1262561077, 2992525269, 639813550, 3631490486, 2575886968, 1800902796, 3592505855, 2532883813, 3665721313, 306702905, 2543883169, 457430544, 3551578460, 2141544643, 40386051, 2715673266, 1444451610, 1150787206, 759559338, 1071472301, 2952061972, 3623326390, 2360927751, 1094927671, 4083728857, 2834080968, 1561788516, 3826871311, 1642894884, 976602778, 2474303657, 2374701833, 903480605, 2275753982, 672707838, 3681522844, 2794191768, 3635154652, 576489003, 1680824969, 484529970, 2651768564, 1609315950, 1692004680, 1434449186, 4254831197, 3798207040, 957371219, 1576503412, 2019371882, 3835069532, 2091616548, 3062009207, 1934921219, 1781796460, 3488154351, 1091817713, 2428690656, 133811988, 4146574219, 3621070372, 1104979426, 675323940, 455989384, 2326666009, 247333869, 4228727264, 824285669, 1687478584, 1454214626, 2406689111, 1043448415, 1828277732, 72552057, 2416268066, 4097625903, 2221486933, 3171558980, 1650885782, 1646227047, 619785603, 5854586, 2371606095, 1500370121, 3710895530, 477912378, 2933897040, 230239688, 1361779125, 909149452, 508152256, 2855951211, 2882886690, 2568557528, 3645700140, 2011474198, 3944520005, 540276470, 2524514685, 2511880892, 4185396363, 817130831, 648961250, 1071435612, 2228725053, 4089128477, 1251070128, 41018848, 4065825110, 1945398418, 2694336812, 15647380, 2903723297, 3815280968, 1728356935, 3470445548, 715494853, 3938512327, 2167849249, 1342600008, 507746211, 657820334, 2441559640, 65560404, 618623482, 3689476671, 2102627462, 2090636578, 236446227, 2799128796, 3192549928, 817183289, 1394206428, 3913651126, 1864572795, 1505355308, 1197104738, 3550089285, 2647768644, 3672505015, 2199660592, 4110675222, 814643382, 2848153469, 1882104345, 461521717, 622534665, 2202845477, 1176954857, 848873587, 1257654135, 371728291, 1266466644, 4199266623, 4152571685, 2780771468, 3536835052, 703979599, 1260355424, 874182734, 811615976, 2226497395, 3076975924, 2291264212, 927502048, 943973264, 2633348751, 2095571353, 2034701607, 1085425350, 1146911031, 1765550816, 3338171228, 4020058701, 237371931, 2059184324, 931863831, 2352422784, 4202136176, 903852263, 3820404878, 1070470885, 4157353567, 3787836882, 3357075371, 1641611681, 3622155456, 3764420410, 231110981, 94129586, 884659352, 2008160280, 1386474384, 2442035079, 1226889838, 139530109, 1328786660, 2960081790, 3120084905, 1534739213, 826192237, 3648104089, 2289201191, 175216923, 635252875, 2049533353, 347937847, 1395491078, 1983365801, 422250447, 1905596218, 137513519, 2453541453, 458393408, 3137597915, 2216728236, 2910480427, 2787767249, 2185171631, 1329020661, 1708161134, 3910631933, 3398813501, 569046097, 1807535794, 2845046988, 2605657221, 3375977602, 1384639645, 2212562724, 3784893348, 3645407211, 1395656042, 2239203708, 3988055800, 3199604951, 2285082274, 2306544705, 1031545798, 2880806332, 16382415, 433286182, 1635379992, 416228355, 166653201, 670854724, 772631292, 2423985306, 3931299717, 3676472475, 2113840165, 871547074, 1986318108, 2722046357, 3517571835, 2117124841, 1657213604, 1306101887, 4006668205, 3519620043, 1580408315, 692915266, 2361626584, 564599440, 2998741260, 653175690, 63636234, 4151447872, 2085712817, 3563148713, 3315588861, 1143228190, 2715385957, 1210460385, 2953074339, 944722992, 2043352211, 1029153623, 2600259173, 1489055618, 512519023, 3480279352, 3572142468, 1057938931, 599956320, 2344200788, 1812054919, 2464454879, 1997536052, 1265535573, 1848804878, 3025647877, 2321187824, 3027298127, 3795111727, 678143525, 2444260138, 1270559090, 3728698794, 1293136125, 580752957, 2028883871, 1944703934, 3777524814, 38703055, 2408382299, 3581024251, 1051814480, 759184406, 235929378, 618623547, 3976129097, 1523391007, 398067085, 2706221259, 2280319410, 3345381598, 3755579942, 1466571040, 1851772323, 1696045964, 4100149622, 3786178136, 22596493, 4092543489, 3625968048, 79142756, 1412380734, 1756632708, 2943574281, 4202505090, 2848889662, 3101637656, 1869917832, 2871675898, 2362155386, 1719627986, 538784127, 2780786840, 1827520939, 1017384251, 2298639577, 3031952662, 4219194469, 470445313, 3672446498, 3685632765, 1956270230, 2858000168, 2611628108, 2127649340, 3707438345, 3670399972, 902249210, 3244063223, 1720023898, 3816266128, 4170574436, 2784897153, 2082469528, 3196017243, 1324839952, 702705193, 4249415786, 1618853054, 3577716543, 2714339437, 1319182442, 2510616442, 3418383693, 740765309, 2158685408, 2800854773, 551261518, 3577503201, 1307020298, 587268655, 2710972058, 1913851560, 2418099054, 2107761657, 2094497945, 2041094540, 3757520216, 2465583159, 3685945993, 165001418, 4008696399, 790410732, 1794881858, 1441857135, 693781171, 1981896597, 835047946, 3285941351, 3472828197, 2636388946, 2756631872, 2318701259, 2923678679, 1291900347, 4107761563, 747777757, 1754927942, 2509491257, 1675055102, 2138149649, 845531344, 216561566, 1605151349, 481707524, 3272973645, 3252163827, 1699831090, 3094250214, 2498392195, 3538748338, 1533692457, 4257924518, 2597964691, 3265460977, 669291065, 71582386, 3451959756, 734554423, 716670123, 2972248938, 456182189, 3501834111, 3529047782, 3375964912, 4063113341, 3262886321, 1912846039, 1106603117, 1854940305, 3980187939, 4049804618, 783265205, 63986529, 2592297914, 4141558244, 3813413088, 4109047892, 364937931, 3307007423, 3154934340, 3191808190, 3074708922, 2042541337, 969807220, 3434984859, 3464374648, 1749694691, 762858735, 2560308318, 1890398819, 1853903041, 2692598279, 2700135825, 2924791809, 3515984582, 465616600, 2093438873, 1371848526, 899384807, 574839134, 2663163487, 4285596349, 1593757479, 947564481, 3974625298, 3640536107, 950910013, 1117579292, 1200212496, 1360737590, 3364782974, 3139142062, 2311946565, 2974026670, 390860079, 1642436914, 1601494606, 274768228, 3428523872, 1907874538, 3832424783, 2366352786, 1780790969, 585156195, 1883918657, 854082658, 909484560, 2350938523, 3873243553, 1193621609, 2230824537, 3814906305, 3975545269, 3930102680, 2841425190, 1189869699, 2817897124, 4267847602, 3449598669, 3531056529, 2771154323, 739656376, 2323802495, 137685024, 1585573564, 1566800832, 267418910, 671109186, 1320734785, 2758519834, 459065813, 453216734, 3579216044, 155106386, 1684855019, 215051955]
ct = 468224605284478429624402844003979810338942127932163644318478094677669568789719279238661649360060298858713146982469024237679875046005767037499078255963595
linear_system = LinearSystem([32] * 624)
mt = MT19937(linear_system.gens())
zeros = []
for i in range(624):
zeros.append(k[i] ^ mt.getrandbits(32))
sol = linear_system.solve_one(zeros)
mt = MT19937(sol).to_python_random()
for i in range(624):
mt.getrandbits(32)
print(long_to_bytes(mt.getrandbits(512) ^ ct))
```
#### easy_MT19937
```python
import random
from Crypto.Util.number import *
from secret import FLAG
k = [random.getrandbits(64) for i in range(312)]
print(k)
print(bytes_to_long(FLAG) ^ random.getrandbits(512))
```
這題不一樣的部份是我會給你 312 個 64 bit 的隨機數，於是我們要先看看 64 bit 的隨機數是怎麼生成的：
```python
import random
random.seed(0xdeadbeef)
a = [random.getrandbits(32) for _ in range(2)]
print(hex(a[1]), hex(a[0]))
random.seed(0xdeadbeef)
print(hex(random.getrandbits(64)))
```
會得到以下結果：
```
0x6d2e9cb7 0x4e5f152
0x6d2e9cb704e5f152
```
可以發現，64 bit 的隨機數其實是由 2 個 32 bit 的隨機數合起來的，所以也可以用相同的方法去預測。
然而，教學上是這樣說，gf2bv 的 `MT19937` 也可以生成 64 bit 的隨機數，以下是 exp：
```python
from gf2bv import *
from gf2bv.crypto.mt import MT19937
from Crypto.Util.number import *
k = [9318872265766295338, 2765469340085262554, 14176545129830988425, 9382198784590583125, 7839737444827915107, 8333261606456303824, 6323647254990659624, 15360576042547953389, 6034747902340825093, 781253118838197867, 17114026764044497479, 4561663952886640236, 15794392867696491878, 4808132225120110946, 16648044623154421451, 13933710659885819165, 15646548386581853592, 7170069920077061789, 8391544213113839324, 2299217623970845735, 10781349839348994585, 13405485601822163178, 8131320462547187444, 10115407090596117931, 3594605834491702427, 6274038602219703481, 17472515345938315152, 5665139574072671063, 16538703901453212604, 2896736789531968009, 1024748120339968137, 17134488299395767741, 17963709882710048171, 3745329418874099683, 11590263254417907165, 5579078754543487930, 4654066176738683105, 11344796279907870435, 2978584308758949272, 8866463723783445163, 3193619473277168733, 13661820976423077098, 16082640100773321661, 347009914450336398, 17066274334473259875, 7244307460722762386, 9580577727518990462, 15502654331721431077, 16968179936485564384, 9421311398656979824, 11007387820534836210, 10350207794508024462, 17036638302127094910, 8036415218755591515, 9838718950771276417, 7367959537618103308, 6528288743730367984, 10825655895632988131, 12500580556836504534, 11099244097119581832, 6081403999039370848, 7681081260960490264, 12111534657446513151, 5794658138351815648, 10806553249132284793, 10207876205184467440, 7887947186216669763, 3550475140686135260, 17300623029849496687, 8700071815817873903, 11847171451985286852, 4314763497465533714, 6192160030233760866, 1391393848661039632, 1881121077666964519, 1883344655230710391, 3782278105529691299, 960620380851463617, 11659030138879866330, 13672538250412151349, 4358807901020577958, 11151585891100927393, 11181374825000385952, 418853083708598560, 10633615924230345128, 2027155166303840159, 12976461062436951016, 6290568416350394260, 12149694739889607833, 2933265308637067074, 12740362568628150089, 11331123611263874204, 8719852820750413207, 3632745886392187506, 11917395456975601440, 9136575698907277727, 4187508705529698927, 1608183825004665695, 11571812661840991661, 8465540739356978024, 14027354421194270074, 4510351649400273856, 9960603677955279581, 11868639552494967705, 12229826409889614327, 1585407721895261436, 5586498594020174325, 3747845284317090609, 15662897190362612948, 9336210566260096533, 9884690432323848498, 1275563793723215447, 107166111520876804, 3036921039959701951, 280582601455481345, 8960130717329484072, 11711106103970886411, 6128788890387696311, 12799549970943630547, 17530897816361227368, 16120365029560235055, 16581278427350140509, 4509304919535920675, 10611805088297010170, 3337161234434615858, 15684384485985451476, 6112607066428064660, 15868704232652538349, 4781869552593983267, 2181999215096549463, 13031583299590495316, 5105161897421287180, 18393952087986733985, 417791003187068718, 9772293046231465433, 8583016703762416098, 9534425230865788200, 16945504542055036244, 11104263257610641068, 896608464588752689, 13356401445553654904, 6761021723368953128, 8525370523392590179, 8123910895034823886, 11431586113934842280, 16496213695940417288, 2882413521607299685, 14305648305041560486, 11392367388986147460, 8334234562571103877, 7626279539692705297, 7372766595428008898, 10978883243536905472, 17608365708958370078, 2451773324589890408, 11883793256441269198, 11461597511577647146, 16714880131379598744, 4094422125243654164, 1792647576043098531, 2298419444165822235, 8194085503244984268, 15297032508956775735, 16566248413015439705, 13543247041652212782, 10903703556892760917, 5356059389463826156, 11621915984334072768, 8903526365437927215, 7411784129474453710, 12641038895860139993, 4305112686279232330, 17331522111175966837, 17657601201354250948, 13667320267639805961, 750543297383183663, 10301523177750384892, 17497295579857402332, 6952737603000650237, 17606740010048765458, 3973147069390214497, 14527443385601038648, 1500636964008004474, 14426908413938015769, 15362210125520571545, 11986119087339171404, 8701656537012843454, 14810925436723317025, 4054959408809069473, 282786360352367383, 11594670225722800063, 1866612624433679558, 13691515509131264840, 17602307770685762802, 7065487279142395092, 5170973549681968286, 9318921434877232609, 12838111537415406793, 669282349882902618, 15835871384577341416, 1177188822070342965, 144162328465409774, 7344123907340674267, 7284610124031616118, 2056135822222687872, 7434440639874809917, 16457440697733829218, 16404037551617303694, 15300146575783113666, 16115420532067464446, 14516711989765871829, 10474541778783340053, 10915590381978047845, 16060441087160263084, 11842682063963833232, 11491194897635346199, 10282037732354183961, 10796621117502054021, 1643480745061146467, 12167894792174873446, 13763065052956492928, 1679825926381920334, 4142047993418722003, 811668013025900815, 16585778600692343879, 6989367668771739284, 12470448412913110546, 9902549982375239394, 8478134796999460470, 9622731299929736208, 334127849382309808, 10771457574222945813, 4704019347044882031, 17326237176799774899, 1223836469034025036, 3785515616270897983, 14757740263522760493, 1150983556780801147, 5759893263251499125, 4701267219182256340, 1842487759463591831, 7053015011502624438, 3030180565058229356, 7065741535294566471, 7957586002761449922, 12622278733295909180, 13699510609203038886, 15836985554426186251, 17172846814984338578, 4240950668465654913, 329272597628599496, 13346689273022650363, 7162539877056375200, 235453927025490617, 5588389783959828431, 11396226922796071227, 9385057654600289543, 8526194434693869106, 11584289488555379959, 8797029436159817899, 4366019192898644364, 4932386545616158742, 18100051322452512809, 8008622755971032849, 10156671441277860980, 9154167727619680844, 16877787109557733173, 10165202760168511636, 15733536335065600298, 18205133964711997491, 2451142893920676606, 7122296643725411660, 18206559652867393365, 9557112579791643427, 202357166467838807, 1119309368199886165, 3474463829932608362, 11362246982344171926, 17012514602040039453, 11234490043393882772, 2192775130801682128, 13648620248693876790, 16526366010556832365, 13749033916622821412, 16456223096874392510, 3146539266335319744, 5008937238615532581, 16333073246816736222, 1213528715354175476, 14601495628838900684, 8234529664061178844, 6971734083335959525, 4572846766052782283, 3170337129838896770, 1530872581443660007, 3374295538814873073, 14934165389447889588, 11696330328131375544, 14184146333610783252, 15700232097544710559, 13062778881929513461, 5236199474087641676, 10410784653469583824, 10490055868776481208, 1212016901971226073, 15203186260299970159, 1565353954709702906, 3680944056763719506, 4200033934118187270, 760596888431350291, 15620961633644428052, 14895065473829834012]
ct = 1892096687238360922193469559059483041172639986070470817603658035827064467613346512411252707432427245023112604539604777184850456409987473120817879495693560
linear_system = LinearSystem([32] * 624)
mt = MT19937(linear_system.gens())
zeros = []
for i in range(312):
zeros.append(k[i] ^ mt.getrandbits(64))
sol = linear_system.solve_one(zeros)
mt = MT19937(sol).to_python_random()
for i in range(312):
mt.getrandbits(64)
print(long_to_bytes(mt.getrandbits(512) ^ ct))
```
#### junior_MT19937
```python
from Crypto.Util.number import *
from secret import FLAG
k = [random.getrandbits(31) for i in range(1500)]
print(k)
x = random.getrandbits(512)
print(bytes_to_long(FLAG) ^ x)
```
這題給你的隨機數是每個有 31 位元的，這個怎麼辦呢？31 位元的隨機數其實是 32 位元的隨機數去掉一個 bit，我們可以以 bit 為單位去建一個方程組來解這個問題，這件事情其實就是 gf2bv 在做的事情，他的 MT19937 也可以 `getrandbits(31)`，我們繼續當腳本小子（當然也有另外的方式可以解它，可以參考 [LoTuX CTF: Where Is My Bit](https://hackmd.io/@LoTuX-CTF/Where_Is_My_Bit_CH) 的解法，它是使用 MT19937 的轉移式去做一些檢查）。
以下是 exp：
```python
from gf2bv import *
from gf2bv.crypto.mt import MT19937
from Crypto.Util.number import *
k = [29192402, 1000834817, 1994876482, 1699109358, 2144583975, 1246233979, 1953732341, 1247356818, 2141022409, 768683982, 229884900, 903611930, 624882080, 681048246, 1073287488, 465550218, 1492679637, 442473485, 1077664013, 1735850576, 298166444, 1427281159, 1585779197, 1894852440, 235777130, 2026549603, 1342272112, 921793329, 615716780, 936161009, 1585816230, 421641648, 792666780, 1489357731, 401787571, 2012927259, 1741484101, 221782763, 1811682403, 478683881, 824837819, 1667330855, 589641795, 584514952, 892019219, 243298684, 1751929354, 1221179825, 832019851, 1688967747, 278657159, 1849466684, 1748779629, 848300482, 609505379, 703888978, 784990547, 484485594, 336543617, 2080089744, 362947143, 1021605950, 1371645088, 393066378, 420754493, 1249403845, 2123532400, 287475710, 739159751, 1900815691, 2047504464, 1953435180, 1594091252, 1631069057, 719932677, 518455506, 1182765356, 88436977, 266622678, 1700707627, 524590368, 1266171577, 700729673, 135110641, 1519059303, 980597799, 67409236, 1394905362, 1852338347, 1134535900, 774200351, 1104465029, 1974861522, 1582509529, 1820438061, 1448039588, 169689824, 912560096, 973137883, 1993925857, 1812167904, 1680248913, 1857592186, 800390241, 388757318, 540796985, 1845932271, 65565603, 2033446891, 1345733011, 1934949011, 1166829619, 129329580, 389693272, 676685265, 1955622574, 888508236, 394272611, 1914503664, 1313413908, 1359410995, 799793593, 1187366937, 405734264, 1564313865, 1550264741, 1006477507, 942158305, 2001769639, 178435131, 636148306, 1096782650, 1928443895, 1418887890, 1180794990, 1387045914, 1383211407, 437621903, 1244336861, 392149316, 458410085, 1838532547, 442018413, 832920704, 430188118, 755229810, 1714763299, 574262694, 1138557316, 219964894, 1728494211, 1460412409, 857070471, 1903033816, 1331661786, 187530668, 431631705, 114563171, 235009329, 1425640840, 432143549, 884071609, 1374725418, 1854766622, 950254861, 303822833, 828912466, 288220142, 96031478, 1770950132, 1036556571, 1881699555, 1071499864, 508567377, 501828390, 329885240, 626928823, 1064583266, 542035255, 394847365, 1614295543, 2145556623, 1242844677, 412187307, 1141652882, 1521659957, 1703037715, 1156024562, 1505584464, 1640437666, 1051674604, 2058610281, 466467719, 1802684391, 1211736599, 1888716876, 1275572719, 2091903050, 1636398935, 1430926148, 846250392, 214214204, 851676888, 87614647, 247064165, 1867741494, 1260022225, 1265621911, 402172907, 509831987, 740194686, 339570072, 828002547, 1960855862, 1855485731, 1842870816, 410650280, 364497518, 665834351, 95696479, 150493942, 1165822891, 816138326, 600258963, 620724344, 1022424263, 361481811, 1526449924, 1387715020, 510755657, 1755217005, 1578299544, 636003746, 47461696, 180663009, 1654223433, 1682914288, 831750090, 1365054921, 1637428277, 310803021, 47639504, 1846742930, 1925918290, 1672701879, 239808063, 1565108028, 847098473, 1894211940, 1113273483, 761082267, 57580030, 530223693, 622664126, 1810057101, 869746518, 957821702, 971090815, 779537233, 371148036, 1139161776, 1551119551, 292630963, 558986184, 2146730872, 10040098, 1017399550, 158412794, 504046841, 497060885, 1090697447, 1916049925, 226169005, 73271024, 932764319, 454541728, 948956328, 2030520764, 1513725518, 2058787586, 1036359537, 135152449, 2001648074, 949183490, 24704339, 14119289, 1744645581, 1449262474, 309570340, 1975884249, 2034846240, 302989826, 321655007, 1951152334, 657344479, 452469287, 1382154116, 750092227, 1617214594, 1575641131, 919807045, 345075079, 2072129248, 863147235, 2058747196, 1935612339, 1621590657, 600181441, 1813208865, 287495635, 2110848780, 1348194703, 1546447543, 1780926299, 552333022, 39099288, 143890716, 789848180, 1372327871, 163926182, 1489555862, 1980749636, 318992922, 256058896, 657452635, 542846720, 1300594530, 1179955050, 159966748, 1785960573, 1050201130, 1963560083, 894252858, 502528972, 1270570787, 2039322347, 57227999, 1297151608, 1056378439, 1062246183, 494163968, 1496748899, 523630948, 548207181, 730467998, 1063339283, 188556025, 934631322, 1921830067, 119334602, 1540571466, 1877651234, 1452059072, 1947653361, 469058196, 630779556, 1661028612, 53826114, 926741207, 134620822, 1852432248, 1375517116, 1707906863, 1762475077, 680360565, 446768023, 667857953, 1013473626, 171993902, 447355634, 1448216476, 13707646, 1427872440, 176586620, 55189762, 1362818998, 261648685, 1542830454, 713009061, 390807850, 218085776, 1558009249, 828738549, 1227724456, 2113004837, 1578040696, 11882630, 1220360749, 1567970375, 770021475, 2030604058, 492301057, 1901326401, 143326778, 75704223, 497386591, 2776192, 1626076555, 172875129, 857739778, 744246777, 475036115, 991868026, 123891534, 1462187599, 760007034, 1185841024, 819935672, 1150479420, 790814183, 426795171, 290287070, 1597634930, 1639768932, 1557082128, 1662438982, 714127016, 1903452673, 1094645061, 103694258, 580627148, 1941477904, 107738632, 1109765252, 1813004843, 1654551298, 2012735839, 1043334761, 1563790602, 259552993, 2122618884, 33619320, 715768109, 755038931, 105184137, 332844716, 1585481516, 26307647, 519982056, 656290800, 621376480, 230893447, 1828808141, 2078377274, 991074357, 1965970152, 1773138862, 759572759, 1255324655, 701445614, 2096539868, 2020676101, 1888044347, 1859263675, 971203510, 1332446683, 375819423, 1851993028, 1685596400, 1488058392, 1655844565, 715983963, 724974516, 1324031096, 684152728, 1667011479, 936890761, 1700790491, 1940111133, 1875621399, 1840819765, 1905205992, 1851434773, 1762612226, 43192690, 401350083, 1549469668, 1817507363, 1238697132, 1336794234, 1651107889, 1726114757, 634857272, 1158682645, 408859419, 993172101, 1000218286, 273910046, 1250358200, 1439763571, 1236495641, 509681762, 505645760, 1891987668, 625720340, 1341597695, 2146049199, 328515669, 958364302, 1421828588, 1222192184, 1943721103, 1473708646, 1945761600, 815029313, 399237958, 954787647, 1796094237, 86485998, 586234852, 1674330534, 1535529924, 368377872, 229223083, 409207310, 489447995, 427200312, 1084289090, 267074005, 2043674420, 1078032090, 175518186, 670590573, 195467915, 966863404, 1924585664, 748286656, 1076371296, 1125626996, 853961354, 1737425211, 343370375, 524662025, 1973070624, 325133620, 1234078182, 1279259708, 249599193, 1510390730, 1806464959, 581601475, 852396196, 472595929, 1309425306, 76545946, 942363286, 1255354831, 1235580637, 1806797116, 51144178, 1128513257, 1558890739, 608207705, 463692991, 709942761, 265682422, 1032084841, 560168624, 423190175, 1346623958, 1821698263, 1671245004, 113124656, 1737686149, 677407860, 1474643112, 2147215940, 1040243282, 1626244990, 1124657352, 2039775221, 1040513716, 1507513559, 2144582284, 289213557, 274681966, 13909844, 11172200, 815988453, 1235534649, 1659596354, 964284452, 153008480, 1977434288, 1242998795, 1629077277, 1086159501, 1117079880, 262786966, 270945010, 779490798, 300077598, 1400915316, 1807790240, 1222966973, 985054780, 1656088622, 748932250, 517279956, 746920587, 2139880967, 1263626277, 59077497, 1331161023, 76471723, 1468373744, 1862698829, 782905435, 688417094, 771745562, 1826175653, 1677729273, 875519161, 808232870, 1997935315, 1571827772, 1839306204, 234677290, 1490049929, 1437781962, 393980355, 1367783250, 157287530, 822531829, 933356585, 1239207584, 347444600, 1889532900, 495760020, 1788781866, 1276114743, 1623071390, 1164443533, 653152112, 2059722348, 1865097317, 987135895, 1619830151, 1764253585, 1890423814, 1729262470, 711566172, 534538326, 805392418, 1934467662, 442797113, 898021098, 308955972, 803786476, 162159296, 1294086723, 474942456, 275824312, 714297057, 1274214629, 559583864, 381889254, 366897045, 1859238526, 1502936893, 1597820654, 733860281, 1311078901, 1923724574, 1887470016, 1529507960, 1619377260, 698358658, 558549359, 1376737894, 1537868461, 1502339780, 499280291, 949428688, 1694094817, 1132984207, 2124069384, 2015359865, 1823778787, 945322527, 2101077904, 1294746436, 952426119, 106949442, 711949056, 109262466, 1110493524, 308666232, 1672720497, 379957694, 1144330544, 760558622, 1253538277, 1200665845, 893059510, 1467892400, 1587998703, 2079874110, 1171053609, 1401803993, 1928446509, 1880184577, 1066901863, 1791585112, 1188389456, 627493528, 1886822901, 1943099389, 910058187, 200045276, 1563818513, 907635702, 1402913875, 765128416, 1261751743, 1168817996, 1585877472, 1339252451, 825362413, 1770931580, 1904924031, 2069977555, 305645764, 585726619, 2086564751, 1117317761, 1467627739, 337571951, 1186182446, 948517922, 2083248984, 1585252296, 1615295210, 1615008438, 247732455, 1406853301, 36659388, 1168363487, 1557186900, 737399529, 235601222, 1968501181, 1989125780, 1434018082, 47610802, 9963097, 753540768, 1217280874, 378177419, 1581883679, 755574325, 205123347, 1032703491, 938641326, 250726144, 1298008583, 20353285, 136352815, 251988067, 1901146309, 1020719862, 889993284, 1644630825, 686574772, 1215812495, 43861329, 475202288, 702153952, 1969031421, 1517949210, 1913813257, 1293019556, 118642804, 1200298268, 2070023029, 1610022668, 1758347043, 1099591709, 240259466, 838792649, 404633247, 1273165881, 1109550324, 449409336, 427841190, 1125285562, 1160882864, 803390332, 167527183, 411123515, 1161745720, 1424157880, 1791774285, 1789181543, 1198600382, 729533868, 1938868460, 190855618, 1942189736, 476114761, 475933552, 612596648, 1060348902, 268047907, 95243766, 20311264, 114828997, 1531724291, 424171424, 255387572, 521658019, 1195019327, 1250133714, 2139242913, 2146398384, 555353728, 1374371928, 1309197213, 1123030766, 1587201889, 1593724479, 1259777855, 80858250, 769615858, 2141545017, 174513900, 1924551067, 1014711418, 393452664, 1748291806, 921564659, 1377329600, 1288667319, 1172586541, 1208472543, 1612213552, 132104081, 1084241817, 767820230, 1192950927, 1898270820, 1708798342, 1118067300, 1574143908, 2124040585, 1172664347, 663339861, 662237600, 1457288633, 454432683, 2045143092, 1704486131, 1255592684, 50147663, 889556780, 1458032642, 2042726215, 271730356, 622335072, 12375914, 92099779, 1592462252, 1196547606, 1612082257, 1519135825, 1508658443, 643287660, 652714034, 1403720090, 266716235, 1348877280, 2023154418, 1370102436, 1962023409, 649521157, 1850332213, 2098535287, 124876937, 1847058683, 902382387, 1980369796, 864046619, 430021831, 1640090310, 216058027, 1616212812, 887521199, 1101290958, 121455387, 1649866210, 56137521, 427787490, 755223688, 2100053909, 1782409761, 1229724883, 282987365, 395222748, 1722477690, 607702748, 2113905972, 1207882692, 2101144242, 1681682593, 396118168, 1668487930, 1800229705, 985435831, 1951272222, 883962247, 792691123, 1767532693, 179228157, 1746800610, 706429511, 2036810314, 531666773, 1546861627, 814090086, 1024621862, 1266788134, 1990387165, 166039642, 859261971, 1288195427, 914741499, 1629096579, 547154330, 1147650222, 873354485, 2142135065, 1231167819, 290265535, 1473719429, 730043717, 137575830, 884821445, 1938631405, 265474246, 1947274796, 658298321, 2118446885, 15685906, 83877004, 1408755437, 1371007141, 20776756, 306190917, 2144249175, 21172348, 300980194, 31095509, 1129911233, 430205098, 1823078478, 527381517, 606988627, 877836100, 213520313, 1498417993, 737700078, 1529006439, 151383071, 2012589696, 956097051, 1576461965, 1869011195, 169286395, 1485499759, 902937336, 805876481, 495194222, 153183697, 1318840775, 23352668, 540980819, 100992338, 102007974, 1853109473, 1301192773, 143823825, 871412172, 301513605, 2139373308, 1159760874, 402153330, 869652803, 240960223, 1668336384, 968234280, 1215247, 1838070314, 182144844, 230684427, 1957691196, 1028430082, 1805260236, 1567145115, 1527686111, 146225820, 2073715485, 1209425845, 929006558, 1116776583, 489972473, 400819381, 1654492032, 381887680, 252233754, 2047244360, 1020492831, 476078323, 132762157, 396619928, 1607452633, 1189300262, 299324738, 1692076666, 733697233, 382655880, 1407946792, 429683312, 456890109, 653704902, 1328438774, 1952580702, 302744988, 612959270, 336796888, 1713173244, 1446367987, 687025677, 2131956414, 1448062847, 1746196563, 1670090830, 630454527, 55715911, 2093982695, 1372113958, 342923479, 36463937, 1612842898, 1514136508, 1585762533, 1239134697, 954401465, 675345863, 1495420068, 825518502, 2017244348, 142923926, 1889963655, 1738462695, 1908403571, 2044449521, 516680684, 76708068, 739698571, 1947067585, 1502387550, 1503563766, 1174146838, 1363166563, 330567143, 1161271004, 1874234309, 1435840112, 2084520554, 827357375, 711461833, 1191866148, 1353066081, 1657512341, 1889756186, 1991060973, 1922524712, 1037856125, 206353862, 1991177045, 115164397, 2091597616, 564251725, 581403842, 330688781, 108191938, 165349622, 1617025328, 941010199, 691457845, 1334500247, 472764483, 1543021372, 1098380653, 21202046, 1000858936, 1896836241, 825816440, 1143539045, 454088279, 802022661, 14984761, 1294853600, 1096711, 560311542, 1112314895, 36877441, 702656092, 1227495669, 396062601, 350517550, 572110297, 761097293, 664089133, 306934888, 1216320591, 240476368, 1462552591, 613051290, 868933328, 1597565932, 529663466, 54128203, 666300828, 478547142, 1529666610, 1464951805, 292971648, 332007859, 532376693, 2111978269, 24060055, 589201353, 353330195, 1388752475, 629435198, 688968271, 342618921, 1980148574, 1063937786, 2047810391, 1355784577, 1504690367, 1280803401, 242964310, 210002411, 1193168272, 2097952903, 1230930548, 241550825, 397461543, 744571381, 197879921, 290211422, 666829723, 1641860104, 1247183040, 1808583927, 113419685, 208444202, 1867619312, 1706508973, 1424496682, 1561720671, 172483188, 41156738, 2041843113, 487070304, 1657117391, 473938943, 913591924, 292752292, 1048632720, 817641644, 894805120, 2023430466, 670186555, 1291056476, 1434909351, 1535721201, 1885004673, 689605518, 243754516, 1596512335, 809258030, 1548660491, 783842371, 226534114, 704615356, 467945086, 360474699, 293166396, 1919423471, 1995911379, 1650957465, 1658039017, 1395168638, 1423487112, 595808535, 347709379, 21911059, 1175916454, 1034106648, 255562305, 1714161585, 1569986510, 722315206, 1876201283, 1590433130, 414273186, 1483426581, 418418180, 1451965495, 2023273165, 963368453, 488953951, 1359848586, 343529559, 1685443708, 753995367, 1006391110, 763068477, 424456791, 1110689588, 1475073447, 2027277921, 1298090835, 864147451, 1568306050, 135531246, 1882357523, 2087694761, 1924208950, 1335473352, 1161557638, 1350578437, 901121042, 1725299125, 958496299, 843044486, 1177774514, 1687998899, 388139429, 964792089, 2146904940, 1070146768, 1645902691, 1398756517, 1562133375, 182105195, 312412793, 211702181, 1674155670, 2027516178, 1215963682, 271463449, 940547705, 229800088, 1917314323, 702592787, 592129608, 325367814, 1265680002, 2006079998, 800474909, 282283476, 928389556, 1907714184, 743827755, 625732045, 1082745950, 488823939, 1435508750, 1037336977, 1717248112, 580532024, 835920249, 1551097539, 1512770474, 1180007060, 955866095, 684618734, 1750621849, 70148897, 1774444575, 2021761812, 429725535, 622202380, 51512972, 1250833960, 701043632, 946115401, 1356401813, 462546571, 2126945491, 2109225766, 955175274, 1412738645, 1062068870, 1328493424, 2013777689, 971147917, 410379451, 323761329, 938792208, 1623091745, 464438171, 102255345, 363537985, 1794146033, 1006196517, 1816784472, 726512966, 1160479156, 242955607, 1774773312, 1042052755, 1057199469, 141987462, 447438795, 1283712880, 1416207261, 1966315520, 1954981627, 717510213, 1101489127, 490653065, 1611439587, 603979615, 1846385148, 80601200, 1895272208, 457824313, 652430651, 925370070, 317803097, 465809148, 230188772, 973510345, 912311142, 1036450902, 1211737536, 939733311, 1973558499, 1009518862, 867266708, 583695328, 1493232142, 359068292, 1227745804, 230595498, 1389467414, 1763723697, 1778715169, 1710464974, 1963133852, 2061129982, 710368639, 1910516945, 1530574783, 1349307476, 1784688070, 1040291253, 2073069965, 637880642, 2037252955, 1067045592, 169820308, 67097142, 333020783, 384399526, 1037822574, 1019446492, 938171350, 980408593, 2061002245, 172224461, 1318785587, 941471462, 1875782612, 1111124948, 913910459, 1100047923, 538465394, 2087666556, 2135223956, 1567552617, 754263540, 670545602, 2036028208, 1681043577, 1063593421, 680252283, 2030964001, 394999572, 332957264, 1655475844, 220306099, 1663852299, 2141532661, 374575048, 343548740, 238501398, 1261495235, 1923530729, 2115552350, 1451085421, 1612607315, 1863332787, 2009701305, 1317171907, 227116415, 1600173453, 2009169474, 1864502318, 449966348, 736772158, 1519678336, 595934874, 205223007, 1762018950, 977811870, 1724107653, 968229162, 100713982, 1515525111, 414468810, 434884660, 1945558728, 1144609923, 2081460451, 751528917, 1954799894, 864108402, 1664816228, 1355825236, 1461360812, 867212834, 1910776738, 875496975, 1684906427, 1690418274, 1279853703, 1089125395, 31538508, 738288794, 2141742615, 1004787081, 166325059, 314695723, 637901071, 1729768809, 2145852932, 1680627119, 1585997466, 823819228, 1818898267, 1869823628, 2016799744, 214743966, 1697086331, 1497277080, 824855947, 2098217193, 1575171492, 1775861043, 50476673, 629553708, 187621998, 1867588774, 2130216700, 1040681367, 407940897, 218473318, 1658956004, 1406477953, 246672141, 1189860402, 1205728748, 1653484568, 1360633498, 616060325, 2001815044, 132259148, 1933678379, 1243790443, 527340698, 1649571155, 1017020992, 1203335724, 1963147135, 53920421, 1421338896, 1008326783, 1696095628, 1981241980, 1942365932, 1698965465, 1602196263, 768811175]
ct = 11612679413881167652206590639602112213975770244647390846059932445845823082647141252318752373897393532939620093927415476064773003849237189208270155429623695
linear_system = LinearSystem([32] * 624)
mt = MT19937(linear_system.gens())
zeros = []
for i in range(len(k)):
zeros.append(k[i] ^ mt.getrandbits(31))
sol = linear_system.solve_one(zeros)
mt = MT19937(sol).to_python_random()
for i in range(len(k)):
assert(mt.getrandbits(31) ^ k[i] == 0)
print(long_to_bytes(mt.getrandbits(512) ^ ct))
```
#### float_mt19937
Hint: ||可以去讀一下 cpython 中對於 `random.random()` 的實現 [Modules/_randommodule.c#L188](https://github.com/python/cpython/blob/ed672f7a8a3c843d8e6e6b673d5a7c1f752f208c/Modules/_randommodule.c#L188)||
#### seeeeeeeeeeeed
Hint: ||可以去讀一下 cpython 中是怎麼把 seed 轉換成 state 的。[Modules/_randommodule.c#L294](https://github.com/python/cpython/blob/ed672f7a8a3c843d8e6e6b673d5a7c1f752f208c/Modules/_randommodule.c#L294)||
#### more...
MT19937 還有很多可以玩的東西，最近有點忙我沒有放進來。
## hash
雜湊函數（hash function）是一種不可逆的映射關係，它可以將比較長的內容映射成一個比較短的內容，並且讓不同內容映射到同一個內容的機率極小。
兩個不同的內容有同樣的 hash 這種情況叫做「碰撞」。一個好的 hash 碰撞發生的機率極低，幾乎不可能，然後經由 hash 也無法推回原本的輸入。
在 python 裡面計算 hash 的方法是使用 hashlib，裡面有各種 hash 函數，譬如 md5、sha1、sha256，輸入一個 bytes 字串，使用 `digest()` 可以輸出一個 bytes 形式的 hash：
```python
from hashlib import md5, sha256, sha1
print(md5(b"hello").digest())
print(sha1(b"hello").digest())
print(sha256(b"hello").digest())
# b']A@*\xbcK*v\xb9q\x9d\x91\x10\x17\xc5\x92'
# b'\xaa\xf4\xc6\x1d\xdc\xc5\xe8\xa2\xda\xbe\xde\x0f;H,\xd9\xae\xa9CM'
# b',\xf2M\xba_\xb0\xa3\x0e&\xe8;*\xc5\xb9\xe2\x9e\x1b\x16\x1e\\\x1f\xa7B^s\x043b\x93\x8b\x98$'
```
另外，使用 `hexdigest()` 會輸出 hex 形式的 hash：
```python
print(md5(b"hello").hexdigest())
print(sha1(b"hello").hexdigest())
print(sha256(b"hello").hexdigest())
# 5d41402abc4b2a76b9719d911017c592
# aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
# 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
```
### MD5 hash collision
md5 的碰撞是可以找到的，以下是一個例子：
```python
from hashlib import md5
x1 = bytes.fromhex("d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70")
x2 = bytes.fromhex("d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70")
print(md5(x1).hexdigest())
print(md5(x2).hexdigest())
```
### Length Extension Attack (LEA)
hash 其實是一個區塊一個區塊輸入的，用之前的 hash 與這個區塊的內容算出加上這個區塊之後的 hash，具體來說如果有兩個區塊 A、B，我們要計算 hash(A \|\| B)，於是會先計算 hash(A)，再用 hash(A) 與 B 去算出 hash(A \|\| B)。（實際上沒有那麼簡單，但概念上可以這樣理解）
到這裡可以發現一個問題，我們即使不知道 A，只要知道 hash(A) 和 B 就能算出 hash(A \|\| B) 了，這就是 LEA。
一個好用的 LEA 套件就是 [HashTools](https://github.com/thecrabsterchief/hash-length-extension)，它支援 md5、sha1、sha256、sha512 的 LEA，可以這樣安裝：
```shell
$ pip install length-extension-tool
```
可以這樣進行 LEA：
```python
import HashTools
from hashlib import md5, sha256, sha1
A = b"secret"
hash_A = md5(A).hexdigest()
B = b"evil_text"
h = HashTools.new(algorithm="md5")
data, new_hash = h.extension(
secret_length=6, # length of A
original_data=b"",
append_data=B,
signature=hash_A
)
print(data)
print(new_hash == md5(A + data).hexdigest())
```
實際上你會發現我們真的可以 append 上去的 `data` 會比 `B` 多一些東西，那些是在處理 padding 的問題，有興趣可以去了解 LEA 是怎麼實作的，[AIS3 pre-exam 2024](https://hackmd.io/@rota1001/ais3-pre-exam-2024#md5_encryption) 有出現過進階的玩法。
#### baby_lea
這題你要對 md5、sha1、sha256、sha512 分別進行 LEA，我會檢查你的雜湊值是否正確與你的你的輸入中是否有 `b"give me the flag"` 字串。
```python
def challenge(hash):
m = os.urandom(16)
print(f"hash: {hash(m).hex()}")
evil_text = bytes.fromhex(input())
evil_hash = bytes.fromhex(input())
if hash(m + evil_text) != evil_hash:
print("HASH ERROR!!")
return False
if b"give me the flag" not in evil_text:
print("SOMETHING WRONG?")
return False
return True
```
以下是 exp：
```python
from pwn import *
import HashTools
r = remote("127.0.0.1", 10005)
for method in ["md5", "sha1", "sha256", "sha512"]:
r.recvuntil(b": ")
secret_hash = bytes.fromhex(r.recvline().strip().decode())
h = HashTools.new(method)
message, sig = h.extension(
secret_length=16,
original_data=b"",
append_data=b"give me the flag",
signature=secret_hash.hex()
)
r.sendline(message.hex().encode())
r.sendline(sig.encode())
r.interactive()
```
## z3
本來想講，但沒什麼太好的例子，講 MT19937 感覺又太無趣了，之後再說。
## 對稱式加密
加密和解密用同一把金鑰就叫做對稱式加密，由於我對對稱式加密涉略不深這裡簡單講。
### AES & DES
常見的對稱式加密的例子是 AES 與 DES，他們都是一個 block 一個 block 去做加密的，正因如此我們也稱它們為 block cipher，AES 的一個 block 是 16 bytes，DES 的一個 block 是 8 個 bytes。以下說明怎麼在 python 裡面分別使用這兩個加密方法。
#### AES
```python
from Crypto.Cipher import AES
key = b"a" * 16
msg = b"x" * 16
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.encrypt(msg))
```
#### DES
```python
from Crypto.Cipher import DES
key = b"a" * 8
msg = b"x" * 8
cipher = DES.new(key, DES.MODE_ECB)
print(cipher.encrypt(msg))
```
### 一些 mode
那這些 block cipher 要怎麼加密超過一個 block 的資訊呢？他們會把它 padding 到對齊 block size，並且依各種 mode 去做加密，以下分別介紹一些 mode：
#### ECB
知道一個 mode 最好的方式就是直接打開[維基百科](https://zh.wikipedia.org/zh-tw/%E5%88%86%E7%BB%84%E5%AF%86%E7%A0%81%E5%B7%A5%E4%BD%9C%E6%A8%A1%E5%BC%8F)，你會看到這樣的圖（圖片來自維基百科）：
它就是一個 block 一個 block 獨立的加密。
他的壞處也很明顯，就是如果把密文以 block 為單位去重新組合，解密回去之後看起來就會是明文以 block 為單位去重新組合，讓我們看以下的例子：
```python
from Crypto.Cipher import AES
import os
key = os.urandom(16)
msg = b"a" * 16 + b"b" * 16
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(msg)
print(ciphertext)
ciphertext = ciphertext[16:] + ciphertext[:16]
print(cipher.decrypt(ciphertext))
```
我們輸入 16 個 a 和 16 個 b，將密文前 16 bytes 和後 16 bytes 互換後，進行解密，得到的結果是先 16 個 a 後 16 個 b：
```
b'bbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaa'
```
#### baby_ecb
這題給你兩個函式，你可以選擇讓它加密還是你要拿 flag，加密可以加密一個不含 `"give me the flag"` 的訊息，`get_flag` 是你給它一個密文，它會檢查它解密後 `"give me the flag"` 有沒有在裡面
```python
def encrypt(key: bytes):
x = input("message: ").strip().encode()
if len(x) % 16 != 0:
print("Not aligned")
exit(1)
if b"give me the flag" in x:
print("Bad Hacker")
exit(1)
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.encrypt(x).hex())
def get_flag(key: bytes):
x = bytes.fromhex(input("cipher: ").strip())
if len(x) % 16 != 0:
print("Not aligned")
exit(1)
cipher = AES.new(key, AES.MODE_ECB)
if b"give me the flag" not in cipher.decrypt(x):
print("Something Wrong")
exit(1)
print(FLAG)
```
這題是用 ECB mode，所以可以把密文以 block 為單位重新排列，於是，一個直觀的想法就是送出 `b"g" * 16 + b"ggive me the fla"`，接下來把前 16 bytes 和後 16 bytes 的密文交換，解密出來的東西就會是 `b"ggive me the flagggggggggggggggg"`，以下是 exploit：
```python
from pwn import *
r = remote("localhost", 10005)
r.sendlineafter(b"> ", b"1")
r.sendlineafter(b":", b"g" * 16 + b"ggive me the fla")
x = r.recvline().strip()
r.sendlineafter(b"> ", b"2")
r.sendlineafter(b": ", x[32:] + x[:32])
r.interactive()
```
#### CBC
同樣套用維基百科的圖（圖片來自維基百科）：
CBC 模式就是每個 block 在加密前會先與前一回合的密文做 exclusive or，而一開始會決定一個長度為 block size 的 IV，第 0 個回合前面沒有密文，是和這個 IV 做 exclusive or。這樣的好處是確保前面的明文會影響後面所有的密文，達到 diffusion 的效果。
#### baby_cbc
這題題目和上一題大體相同，差別在於這題是使用 CBC mode，且給你的操作總次數提昇為 3 次
```python
def encrypt(key: bytes, iv: bytes):
x = bytes.fromhex(input("message: ").strip())
if len(x) % 16 != 0:
print("Not aligned")
exit(1)
if b"give me the flag" in x:
print("Bad Hacker")
exit(1)
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.encrypt(x).hex())
def get_flag(key: bytes, iv: bytes):
x = bytes.fromhex(input("cipher: ").strip())
if len(x) % 16 != 0:
print("Not aligned")
exit(1)
cipher = AES.new(key, AES.MODE_CBC, iv)
if b"give me the flag" not in cipher.decrypt(x):
print("Something Wrong")
exit(1)
print(FLAG)
exit(0)
```
解法也很直觀，就是想辦法在明文中沒有 `b"give me the flag"` 的情況下分別拿到你想拿到的明文加密後的每個 block。這樣講有點抽象，直接上例子。
首先送 `nonce || m1` 進去（以下 `||` 都是指串接起來的意思），你會得到這樣的結果：
```
nonce1 m1
| |
| XOR iv | XOR c1
| |
┌─────────┐ ┌─────────┐
│ E | | E |
└─────────┘ └─────────┘
| |
| |
c1 c2
```
接下來送 `nonce1 || (c1 ^ c2 ^ m2)` 進去，你會得到這樣的結果：
```
nonce1 (c1 ^ c2 ^ m2)
| |
| XOR iv | XOR c1
| |
┌─────────┐ ┌─────────┐
│ E | | E |
└─────────┘ └─────────┘
| |
| |
c1 c3
```
你會發現 $c_3=E((c_1 \oplus c_2 \oplus m_2)\oplus c_1) = E(m_2 \oplus c_2)$，接下來觀察一下 `nonce1 || m1 || m2` 的加密結果會長怎樣：
```
nonce1 m1 m2
| | |
| XOR iv | XOR c1 | XOR c2
| | |
┌─────────┐ ┌─────────┐ ┌─────────┐
│ E | | E | | E |
└─────────┘ └─────────┘ └─────────┘
| | |
| | |
c1 c2 c3
```
會發現，加密出來的結果剛好會是 `c1 || c2 || c3`，所以送 `c1 || c2 || c3` 會去解密就好，以下是 exploit：
```python
from pwn import *
r = remote("localhost", 10005)
def xor(a: bytes, b: bytes) -> bytes:
return bytes(x ^ y for x, y in zip(a, b))
# First: m = (nonce1 || m1)
# E(nonce1 ^ iv) = c1
# E(m1 ^ c1) = c2
# Second: m = (nonce1 || (c1 ^ c2 ^ m2))
# E(nonce1 ^ iv) = c1
# E((c1 ^ c2 ^ m2) ^ c1) = E(c2 ^ m2) = c3
target = b"ggive me the fla" + b"g" * 16
r.sendlineafter(b"> ", b"1")
nonce1 = b"a" * 16
m1 = target[:16]
m2 = target[16:]
r.sendlineafter(b":", (nonce1 + target[:16]).hex().encode())
rec = bytes.fromhex(r.recvline().strip().decode())
c1, c2 = rec[:16], rec[16:]
r.sendlineafter(b"> ", b"1")
r.sendlineafter(b":", (nonce1 + xor(xor(c1, c2), m2)).hex().encode())
rec = bytes.fromhex(r.recvline().strip().decode())
c3 = rec[16:]
r.sendlineafter(b"> ", b"2")
r.sendlineafter(b":", (c1 + c2 + c3).hex().encode())
r.interactive()
```
### padding oracle
當輸入不是 block size（也就是 16）的倍數的時候，就會需要 padding 成 16 的倍數，padding oracle 是針對 PKCS#7 這種 padding 且在 CBC 模式下的攻擊。
這個 padding 方式就是它 padding n 個 bytes 就用數字 n 來 padding，舉幾個例子：
譬如說今天有 `b"aaa"` 這樣的字串要做 padding，發現它長度是 3，所以需要 padding 13 個 bytes，13 又是 `0x0d`，所以它會在後面 padding 13 個 `0x0d` 的 bytes，於是結果會變成 `b"aaa\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d"`
那如果 padding 是 0 個呢？它會當作要 padding 16 個來看，所以會在後面 padding 16 個 0x10，所以如果輸入 `b"a" * 16`，結果會是 `b"a" * 16 + b"\x10" * 16`。
那 unpad 的時候，它就會看看是否有滿足最後的 $n$ 個 bytes 都是數字 $n$ 這樣的 padding，然後把它 unpad。
那如果沒有滿足這樣的 padding 怎麼辦呢？答案是它會跳錯誤，於是 padding oracle 就是透過有沒有跳錯誤來將明文洩漏出來。
看看以下例子，如果將 `c1 || c2` 進去解密，會像以下這樣，我們只需要關注 m2 的部份，因為 padding 最長就是 16，只要看最後一個 block 就好。
```
c1 c2
| |
| |
┌─────────┐ ┌─────────┐
│ E^-1 | | E^-1 |
└─────────┘ └─────────┘
| |
| XOR iv | XOR c1
| |
m1 m2
```
現在我們的目的是要得到 $m_2 = E^{-1}(c_2) \oplus c_1$，能做的操作是給它一個密文，它會把它做解密和 unpad，並且告訴我們這個過程中有沒有出現錯誤。
我們要做的事情是將 $E^{-1}(c_2)$ 從最右邊開始一個 byte 一個 byte 洩漏出來。
首先洩漏第 15 個 byte，固定 $c_2$，枚舉 $c_1$ 的最低位，如果 `c1 || c2` 在操作中沒有出現錯誤，就代表 $E^{-1}(c_2) \oplus c_1$ 是可以正常 unpad 的，有非常大的機率 $E^{-1}(c_2) \oplus c_1$ 的第 15 個 byte 是 1，因為是 1 才能在結尾有一個 1（之所以說非常大的機率是因為你有可能運氣真的很好遇到 2 個 2 或是 3 個 3 之類的）。於是我們能確定此時 $E^{-1}(c_2)$ 的第 15 個 byte 等於 $c_1$ 的第 15 個 byte 和 0x01 做 exclusive or 的結果。
接下來洩漏第 14 個 byte，因為我們知道了 $E^{-1}(c_2)$ 的第 15 個 byte，我們能知道 $c_1$ 要調整成什麼才能讓 $E^{-1}(c_2) \oplus c_1$ 的第 15 個 byte 是 0x02，做完這樣的調整之後再枚舉 $c_1$ 的第 14 個 byte，一樣送 `c1 || c2` 進去，如果操作中沒有出現錯誤，有非常大的機率 $E^{-1}(c_2) \oplus c_1$ 的第 14 和第 15 個 byte 都是 0x02，於是我們就確定了 $E^{-1}(c_2)$ 的第 14 與第 15 個 byte。
依此類推，最後我們能確定 $E^{-1}(c_2)$ 的所有的 bytes。
我們對密文的每個 block 都做這件事情，就能做到任意密文的解密了。
#### baby_padding_oracle
這題就是 padding oracle 的裸題，會給你 `iv` 和 flag 加密後的密文，你可以給它任意密文解密，它會告訴你有沒有發生錯誤。
```python
def challenge():
key = os.urandom(16)
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
print(f"ciphertext: {cipher.encrypt(pad(FLAG, 16)).hex()}")
print(f"iv: {iv.hex()}")
while True:
x = bytes.fromhex(input("Give me the ciphertext: ").strip())
cipher = AES.new(key, AES.MODE_CBC, iv)
try:
unpad(cipher.decrypt(x), 16)
print("Success")
except:
print("Fail")
```
這題就是照著以上的想法把 exploit 寫出來：
```python
from pwn import *
r = remote("localhost", 10005)
def xor(a: bytes, b: bytes) -> bytes:
return bytes(x ^ y for x, y in zip(a, b))
def check(iv: bytes, c: bytes):
r.sendlineafter(": ", (iv + c).hex().encode())
return b"Success" in r.recvline()
def decrypt_block(last_block: bytes, now: bytes) -> bytes:
iv = [0 for i in range(16)]
for i in range(1, 0x11):
for j in range(0x100):
iv[16 - i] = j
if check(bytes(iv), now):
break
if i != 0x10:
iv = list(xor(xor(bytes(iv), bytes([i for _ in range(16)])), bytes([i + 1 for _ in range(16)])))
return xor(xor(last_block, iv), b"\x10" * 16)
def decrypt(ciphertext: bytes) -> bytes:
plaintext = b""
for i in range(0, len(ciphertext) - 16, 16):
plaintext += decrypt_block(ciphertext[i: i + 16], ciphertext[i + 16: i + 32])
return plaintext
r.recvuntil(b": ")
ciphertext = bytes.fromhex(r.recvline().strip().decode())
r.recvuntil(b": ")
iv = bytes.fromhex(r.recvline().strip().decode())
print(decrypt(iv + ciphertext))
r.interactive()
```
## RSA
### RSA 101
來個最基礎的 RSA 吧，以下先定義幾個參數，後面會沿用這樣的變數名稱：
- `n`：模數，等同於 $p\times q$，其中 $p$ 和 $q$ 是質數
- `e`：公鑰
- `d`：私鑰
- `m`：明文，也就是要被加密的訊息
- `c`：密文，以就是被加密過後的訊息
RSA 加密的公式是這樣：
$$c=m^e \mod n$$
RSA 解密的公式是這樣：
$$m=c^d \mod n$$
只要有 $(e, n)$ 這樣一組密鑰就能做加密，只要有 $(d, n)$ 這樣一組密鑰就能做解密。而只知道公鑰有辦法計算出私鑰嗎？這個問題的難度和對 $n$ 做質因數分解的難度一樣。
### 歐拉定理
歐拉定理的內容是這樣的：
$$a^{\varphi(n)}\equiv 1\pmod{n}$$
那 $\varphi(n)$ 怎麼計算呢？如果 $n=p\times q$ 的話，那麼 $\varphi(n)=(p-1)\times (q-1)$。
### 由分解 $n$ 來得出 $d$
如果我們能將 $n$ 分解成 $p$ 和 $q$，那麼就能得出 $\varphi(n)$。
如果公鑰 $e$ 在模 $\varphi(n)$ 下有逆元 $d$，代表 $e\times d=k\varphi(n)+1$，其中 $k$ 是整數。
那麼 $c^d=m^{ed}=m^{k\varphi(n)+1}=(m^{k})^{\varphi(n)}\times m=m \pmod{n}$
直接看 code 吧：
```python
from Crypto.Util.number import *
p = getPrime(128)
q = getPrime(128)
n = p * q
e = 0x10001
m = bytes_to_long(b"This is the secret message")
c = pow(m, e, n)
print(f"This is the public key:\n{e = }\n{n = }")
print(f"This is the ciphertext: {c}")
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(f"This is the secret key: {d}")
leak_m = pow(c, d, n)
print(f"This is the decrypted message: {long_to_bytes(leak_m)}")
```
會有以下輸出：
```
This is the public key:
e = 65537
n = 85861257221965008526180540805033635899144373982062939968833333254594789382803
This is the ciphertext: 48885244052127160588091250623433713139565252569683729442678837737249498442864
This is the secret key: 72207198861537779344804316744273141012694849697590612302688936433603050616833
This is the decrypted message: b'This is the secret message'
```
我們成功的解密出訊息了
接下來大部分的攻擊都是教你怎麼利用各種弱點分解 $n$（通常是 $p$ 和 $q$ 選取不當）
### fermat attack
這是當 $p$ 與 $q$ 很相近的時候可以做的攻擊。
如果我們設 $x=p+q$、$y=p-q$，那麼可以求得 $p=\frac{x-y}{2}$ 與 $q=\frac{x+y}{2}$，把他們乘起來後可以得到 $n=\frac{(x+y)(x-y)}{4}$，經過一些化簡可以得到：
$$x^2=4n+y^2$$
由於 $p$ 和 $q$ 很接近，又因為 $y=p-q$，所以 $y$ 會很小，於是我們可以透過枚舉 $y$ 來看看 $4n+y^2$ 是否是完全平方數，如果是的話就用 $x$ 和 $y$ 反推 $p$ 和 $q$。
:::info
小技巧：可以用 gmpy2 來判斷一個數是不是完全平方數與開根號。
:::
```python
from gmpy2 import gmpy2
print(gmpy2.iroot(169, 2)[1]) # True
print(gmpy2.iroot(139, 2)[1]) # False
print(int(gmpy2.iroot(169, 2)[0])) # 13
```
#### baby_fermat
這題給 $e$、$n$、$c$，且你知道他的 $p$ 和 $q$ 很相近，要解密。
```python
from Crypto.Util.number import *
from secret import FLAG
def genprimes():
p = getPrime(256)
q = p + 1
while not isPrime(q):
q += 1
return p, q
p, q = genprimes()
n = p * q
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{c = }")
```
就實現 fermat attack，以下是 exploit：
```python
from Crypto.Util.number import *
from gmpy2 import gmpy2
def fermat(n: int):
y = 0
while True:
if gmpy2.iroot(4 * n + y * y, 2)[1]:
break
y += 1
x = int(gmpy2.iroot(4 * n + y * y, 2)[0])
return (x - y) // 2, (x + y) // 2
e = 65537
n = 9558365323804430125224398491472768124065498201264857389735016797868458055012813732749928571980343978789607762836762441871281845491756954407829149798403827
c = 2933931504771117003656633114504662392411084398465341266755990192988706974893746988836259911044835095715830055853893370510067330665935706752924762626510134
p, q = fermat(n)
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
```
### p - 1 光滑
光滑的意思就是可以分解成很多小質數的乘積，$p - 1$ 光滑與 $p + 1$ 光滑都分別有攻擊的手段。
先做個簡單的觀察，如果 $p - 1\ |\ k!$ 的話，$a^{k!} = 1 \mod{p}$（$a$ 是任意小於 $p$ 的正整數），所以 $p\ |\ a^{k!}-1$，於是 $a^{k!}-1$ 與 $n$ 的最大公因數就是 $p$（應該說有極高的機率是 $p$）
會發現，如果 $p-1$ 是平滑的，很簡單的能找到一個夠小的 $k$ 使得 $p - 1\ |\ k!$，於是可以枚舉 $k$ 直到 $a^{k!}-1$ 與 $n$ 的最大公因數不是 1。
#### baby_smooth
$p - 1$ 是 $2$ 到 $29$ 挑一些數字乘起來，所以是光滑的。
```python
from Crypto.Util.number import *
import random
from secret import FLAG
def genprimes():
while True:
p = 1
while p.bit_length() < 256:
p *= random.choice([2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
p += 1
if isPrime(p):
break
q = getPrime(256)
return p, q
p, q = genprimes()
n = p * q
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{c = }")
```
以下腳本中 `a` 就是上述的 $a^{k!}$，就只是按照上述意思實作：
```python
from Crypto.Util.number import *
e = 65537
n = 82880846368964461885454000628098013173671557290598193181983824623922138179015295170643274677513787487946999454971012467259576999736568700994695002230892407
c = 33609089360707292191345373812149426920472973547122567510209620546003844917909166780113283105702758381104688287574738651977040138113242671585102457257308232
k = 1
a = 2
while True:
if GCD(n, a - 1) != 1:
break
k += 1
a = pow(a, k, n)
p = GCD(n, a - 1)
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
```
### Williams's p+1
這是針對 $p+1$ 光滑的攻擊，數學比較複雜，就去網路上找腳本吧！
### wiener's attack
這個是解私鑰很小的問題（具體來說小於 $\frac{1}{3}N^{\frac{1}{4}}$），數學稍微有點複雜，這裡教大家使用套件 [owiener](https://github.com/orisano/owiener)：
```shell
$ pip install owiener
```
可以這樣去拿到私鑰：
```python
d = owiener.attack(e, n)
```
### baby_wiener
給你 $e$、$n$、$c$，已知 $d$ 很小。
```python
from Crypto.Util.number import *
from secret import FLAG
p, q = getPrime(256), getPrime(256)
n = p * q
d = getPrime(30)
e = pow(d, -1, (p - 1) * (q - 1))
m = bytes_to_long(FLAG)
c = pow(m, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{c = }")
```
以下是 exploit：
```python
from Crypto.Util.number import *
import owiener
e = 6898578254134577413148514554586623429691667642128682730491455392270556752758734939538568953708457554137574540370423492716478226275372806839473851762524193
n = 9893600454618326125697440966229674622027804891577200471221776425734143063227373269651360811534004862497912589981825975870687227828688509613361324590034517
c = 8111739387336555523255866756844268461467132515813315023377241801243417780212301407878172874268135549703876028861080342995310689279310050093484452257918913
d = owiener.attack(e, n)
m = pow(c, d, n)
print(long_to_bytes(m))
```
### broadcast attack
當我們有以下 3 個方程式時（這裡直接假設 $n_1$、$n_2$、$n_3$ 互質）：
$c_1=m^e \pmod {n_1}$
$c_2=m^e \pmod {n_2}$
$c_3=m^e \pmod {n_3}$
我們可以把它經過中國剩餘映射映射成以下的方程式：
$c=m^e \pmod {n_1n_2n_3}$
假如說 $n_1n_2n_3$ 大於 $m^e$ 的話，那麼對 $c$ 開 $e$ 次方根就好了。
在 sage 中可以用以下程式碼來做 CRT：
```python
from sage.all import *
c = crt([c1, c2, c3], [n1, n2, n3])
```
#### baby_broadcast
```python
from Crypto.Util.number import *
from secret import FLAG
p1, q1 = getPrime(256), getPrime(256)
p2, q2 = getPrime(256), getPrime(256)
p3, q3 = getPrime(256), getPrime(256)
n1 = p1 * q1
n2 = p2 * q2
n3 = p3 * q3
e = 3
print(f"{n1 = }")
print(f"{n2 = }")
print(f"{n3 = }")
print(f"{e = }")
m = bytes_to_long(FLAG)
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)
print(f"{c1 = }")
print(f"{c2 = }")
print(f"{c3 = }")
```
這題給你 3 個 $n_1$ 分別用他們加密，且 $e$ 是 3，可以知道 $m^e<n_1n_2n_3$，所以直接 broadcast attack：
```python
from Crypto.Util.number import *
from sage.all import *
from gmpy2 import gmpy2
n1 = 6649909188781024969950540034493953449464304636303410898018052274999026013472624421664796566247674879924215764415326271043310086001407288529345960813701303
n2 = 9554761989367922408265114639045941184060631978869184441376333038685565695588499594997225082780031100776634127334734551546743509380585268959004840618932043
n3 = 11404118611764294171249490675080728008845700570614348687585177732017124692882007637970060857442703074705266374035597048224899045396204530370810901469500567
e = 3
c1 = 2850667830620618811566985567877169049186668943999061833036549176327340513116935436861105160542011560677626145507411449153642488194205578503704319178076492
c2 = 3692298388820278901196705335215985800326385687913307002994382673803017247128242763705795707254024515802202614179855523586612990623258260181373786742736967
c3 = 9176828135676096970581961914258995404952132298320079425218508481831905837727723253462829059256566632945356368413401902842330147312431428955741378468512590
c = crt([c1, c2, c3], [n1, n2, n3])
m = int(gmpy2.iroot(c, 3)[0])
print(long_to_bytes(m))
```
### coppersmith 攻擊
這是將一些問題轉換成多項式的解的問題，當多項式的次數夠小，且有一個夠小的根，可以在好的時間複雜度下找出模 $N$ 下的解，至於要多小可以參考 [CTF wiki](https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_coppersmith_attack/#coppersmith)，以下講一些經典應用。
#### Related Message Attack
當有兩個使用相同模數的 RSA 加密時，可以將他們化為多項式的問題，取公因式。他們的公因式通常係數很小，就能得到解，以下是好用的模板（在 sagemath 中多項式可以直接互相取模）
```python
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
def related_message_attack(c1: int, c2: int, n: int, e: int, f: function) -> int:
P = PolynomialRing(Zmod(n), "x")
x = P.gens()[0]
f1 = x ** e - c1
f2 = f(x) ** e - c2
return int(-gcd(f1, f2)[0])
```
#### baby_franklin_reiter
$c_1$ 和 $c_2$ 分別是 $m$ 和 $12345\times m+54321$ 加密的結果。
```python
from Crypto.Util.number import *
from secret import FLAG
p, q = getPrime(256), getPrime(256)
n = p * q
e = 37
m = bytes_to_long(FLAG)
c1 = pow(m, e, n)
c2 = pow(12345 * m + 54321, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{c1 = }")
print(f"{c2 = }")
```
針對這兩個密文，我們可以構造出以下兩個方程式：
$x^e-c_1 = 0\pmod n$
$(12345\times m + 54321)^e - c_2=0 \pmod n$
於是對他們取最大公因式，就能得到解（這裡弄出來是一次多項式，所以直接取常數項）。
```python
from Crypto.Util.number import *
from sage.all import *
e = 37
n = 7135177822517373848903342570304910324225667475353468192462083754666937122170263639787755155262188293787441469945694922069593761090740847456042381914098373
c1 = 344411187960509559135586427256505967053366251302292479890437922784811150911449906964337353253059220956760188709021694404668518814729053089378448722558807
c2 = 6804920373021335051738091118953532555818691250338145681524438306494275417720139745870475492821217371171998197339101466030904828573682431671032972812661004
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
def related_message_attack(c1: int, c2: int, n: int, e: int, f: function) -> int:
P = PolynomialRing(Zmod(n), "x")
x = P.gens()[0]
f1 = x ** e - c1
f2 = f(x) ** e - c2
return int(-gcd(f1, f2)[0])
m = related_message_attack(c1, c2, n, e, lambda x: 12345 * x + 54321)
print(long_to_bytes(m))
```
#### known high bit attack
當我們知道了 $p$ 的很大一部份高位的話，就可以使用這個方法，實際上來說看以下例子：
$p=p_0+x$，且 $x$ 很小，這個時候就可以將它化成一個方程式：
$p_0+x=0\pmod p$，他有個小的根 $x$，於是可以使用 sagemath 提供的 small_root 來解。
在 sagemath 中可以使用 small_roots 對一個多項式求根，`X` 可以限制根的範圍，`beta` 是一個次數，代表 $N$ 有一個大於等於 $N^{\beta}$ 的因數，你要求這個多項式模那個因數的根。在這個例子就是求模 $p$ 的根。
```python
P = PolynomialRing(Zmod(n), "x")
x = P.gens()[0]
f = p0 * 2**128 + x
roots = f.small_roots(X=2**128, beta=0.4)
f.small_roots(X=2**128, beta=0.4)
```
#### baby_known_high_bits
這題就是很無趣的給你 $p$ 的 high bits：
```python
from Crypto.Util.number import *
from secret import FLAG
p, q = getPrime(1024), getPrime(1024)
m = bytes_to_long(FLAG)
p0 = p >> 128
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{c = }")
print(f"{p0 = }")
```
直接上腳本：
```python
from sage.all import *
from Crypto.Util.number import *
e = 65537
n = 11642986179173159275494293108902249941163744896614140627229814704174398599171007775943814548654906726821785476428519144876148691243586993755501152179266308444422723611495937256942193189744924294723271604018082727315357106745891816348999023423085703829338111774045668952425710630802977357127628099472333095659798405105853812777678348539364371021768305877268962170831943013157890741905235832106020420340327445918608778876472685036829878163082906925988573579198026895814861630882813754025669180951316748258341032921748331426218007123775811634421587691124638874574772800705762867581775779379006783451814887051666988522663
c = 5701733898259889584949079204374465890914606005870899984964005818511325386048672748691410142502365567088520319620450203277893986480101834407453934627500844860721101421283433120199716326261608543192295734406264899684929518662319787664136787895436713457202567255711230290587683912876512867390820072221140512797921229030043177160619814345590115256371928708085731659782333417575106156791659809846946117979901018986985908679944640978637244263912282275555380168850349512331043364246512988593832045847096335898164363217817326365967655019978900555422922948424238109484772174817483968254774715106091124873554630737640125319389
p0 = 271227653429424565734904660871789817305429934994789676879587489291412327853364449576125888367989149596359807178156224854651790282008837251384989783256171360112154681065572128198961928903910179693317807448558139665718592409224587880704334444829902834352211795893755186156
P = PolynomialRing(Zmod(n), "x")
x = P.gens()[0]
f = p0 * 2**128 + x
roots = f.small_roots(X=2**128, beta=0.4)
p = int(roots[0]) + p0 * 2**128
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
```
## 離散對數問題
### 原根
離散對數問題幾乎討論的都是模 $p$ 的情況下，在模 $p$ 的情況下一定有原根，它的定義可以這樣理解：
$\{g^k|k = 1,2,3,...,p-1\}$ 在模 $p$ 意義下的元素個數有 $p$ 個則 $g$ 是模 $p$ 底下的原根，更通俗的講就是 $g^k$ 當 $k=1,2,...,p-1$ 的時候沒有重複的。
離散對數問題就是給一個原根 $g$，有一個祕密 $x$，並用他們計算出 $y=g^x$，當只有 $g$ 和 $y$ 的時候，計算 $x$ 是困難的問題。
據我打競程的經驗，在沒有任何線索做這個問題的情況下，可以用大步小步演算法這個 $O(\sqrt n)$ 的方法，在取夠大的質數的情況下，以現代電腦的算力根本無法。
在解一個離散對數問題的時候，我判斷它可不可解大概是判斷 $\sqrt{這個群的階}$ 的數量級，一個群的階指的是這個群裡面有多少個元素。離散對數的題目解法基本上就是想辦法把它弄到一些階比較小的群上面來獲得解。
### Pohlig-Hellman
這個方法就是把 $\{g^k|k = 1,2,3,...,p-1\}$ 這個定義了乘法運算的群映射到一些階比較小的子群上，能這麼做的特徵是 $p-1$ 可以分解成一些小的因數的乘積，具體來說你可以用根號的量級與你電腦的算力來估，我自己甚至有在比賽中成功過 $10^{14}$ 大小的質數。
映射的方式很簡單，譬如 $d$ 是 $p-1$ 的因數，那 $\{(g^{\frac{p-1}{d}})^k|k = 1,2,3,...,d\}$ 就是一個階是 $d$ 的子群。
> 到這裡大概講一下什麼是子群，也是可以不用理我，如果有個群 $G$ 且 $P$ 是 $G$ 的子集且 $P$ 在相同的運算下也是一個群，那麼 $P$ 就是 $G$ 的子群。
在以上的例子裡，你可以想像有個環形跑道長度有 $p-1$ 公尺，我一步跳一公尺的話跳 $p-1$ 步就能跳一圈了，那如果我一次跳 $\frac{p-1}{d}$ 公尺的話，我跳 $d$ 次就能跳一圈了，而且我如果一直跳的話，我會跳到的點是固定的那 $d$ 個點，只要 $d$ 是 $p-1$ 的因數。
我們將 $p-1$ 分解成 $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$，分別將其映射到階為 $p_1^{k_1}$、$p_2^{k_2}$、...、$p_n^{k_n}$ 的子群中，解完離散對數問題後再映射回來，就解出來了。
為什麼能 CRT 呢？
以下通俗的解釋，看一下映射過去後這個方程式變了什麼。
假設原本 $y=g^x$ 有一個解 $x_1$，那兩邊都做 $\frac{p - 1}{d}$ 次方後，它等價於以下的方程式：
$$(\frac{p-1}{d})x=(\frac{p-1}{d})x_1\pmod {p - 1}$$
它又等價於以下方程式：
$$x=x_1 \pmod d$$
#### baby_smooth_dlog
給一個離散對數問題，他的階是平滑的。
```python
from Crypto.Util.number import *
from secret import FLAG
def genPrime():
while True:
p = 2
factors = []
while p.bit_length() < 512:
pi = getPrime(16)
p *= pi
factors.append(pi)
p += 1
success = True
for i in factors:
if pow(2, (p - 1) // i, p) == 1:
success = False
if isPrime(p) and success:
break
return p
p = genPrime()
g = 2
x = bytes_to_long(FLAG)
y = pow(g, x, p)
print(f"{p = }")
print(f"{y = }")
```
解法就是先把 $p-1$ 分解，並且映射到階比較小的子群，做完再 CRT 映射回來：
```python
from sage.all import *
from Crypto.Util.number import *
p = 128162445224451438593694361230966956955232018085784431600951620807481332716417653166981421150989647398625178769159691152916797982185045102972989706661566667
y = 45303731973078064819607976188255549271351224479162000359875975097556891294943382566167937828493029702380634137077825572624145306952003424959972306316046663
g = 2
primes = []
for i, j in factor(p - 1):
primes.append(i ** j)
sol = []
for prime in primes:
t = (p - 1) / prime
sol.append(discrete_log(GF(p)(y) ** t, GF(p)(g) ** t))
x = crt(sol, primes)
print(long_to_bytes(int(x)))
```
## 橢圓曲線加密
橢圓曲線加密就是基於在另一個群上的離散對數問題。
### 橢圓曲線
在橢圓曲線加密中使用的橢圓曲線可以用以下方式表示：
$$y^2=x^3+ax+b\pmod p$$
通常 $p$ 會是質數，一般來說在解釋上我們會先從實數域上的圖開始講起：
橢圓曲線在實數域上就是長以上這個樣子，我們會在上面定義運算與逆元。定義兩個點的加法是將兩點連成一線，交到曲線的另外一個點相對於 y 軸的對稱點，譬如以下圖來說，$A$ 和 $B$ 相加的結果就是 $-C$。
那如果兩個點連成的直線和 y 軸平行呢？那麼他們兩個相加的點則為無窮遠點，定義無窮遠點為 $0$。於是，有了 0 這個概念就能定義加法反元素，一個點的加法反元素就是相對於 x 軸的對稱點，譬如上圖中的 $C$ 點的加法反元素就是 $-C$。
自己加自己的話相當於化一條切線，與曲線的交點相對於 x 軸的對稱點。既然知道這個就能定義整數的常數乘法了，就是一直加自己。
這樣就把該定義的東西定義完了，那通常我們在橢圓曲線加密上用的是在模 $p$ 意義底下的橢圓曲線，一些運算可以直接用基礎代數來推導，有點瑣碎這裡不去推了，下面會用 sagemath 裡的內建函式。
#### sage 中的橢圓曲線語法
這樣可以宣告一個 $y^2=x^3+2x+3 \pmod {97}$ 的橢圓曲線：
```python
E = EllipticCurve(GF(97), [2, 3])
```
可以由 x 座標得到一個點：
```python
g = E.lift_x(GF(97)(3))
print(g)
```
你會看到輸出 `(3 : 56 : 1)`，這代表 $(3, 56)$ 這個點，你可以使用 `g.xy()` 獲得他的 x、y 組成的 tuple。
### 橢圓曲線上的離散對數問題
橢圓曲線上的離散對數問題是基於橢圓曲線的純量乘法。如同我們先前在離散對數取的原根，我們首先要在橢圓曲線 $E$ 上找到一個生成元 $G$，定義是使得 $\{kG|k=1,2,...\}$ 的元素總數和 $E$ 中的點的總數，也就是 $E$ 的階一樣大。它也等價於 $G$、$2G$、$3G$ 一直到 $order(E)G$ 都沒有重複。接下來我們有個祕密的數字 $x$，計算出 $y=xG$。橢圓曲線上的離散對數問題就是在知道 $y$ 與 $G$ 還有橢圓曲線的情況下，算出 $x$ 是一件困難的事情。
### 橢圓曲線上的 Pohlig-Hellman
在橢圓曲線的階是平滑的時候，同樣也可以做 Pohlig-Hellman。
要映射到階是 $d$ 的子群（$d$ 是橢圓曲線的階 $ord$ 的因數），就是同乘 $\frac{ord}{d}$，也就是將離散對數的等式化為以下：
$$(\frac{ord}{d})y=(\frac{ord}{d})xG$$
### singular curve
#### 同構
首先要講一下什麼是同構。現在有兩個群 $(G,\oplus)$ 和 $(H,*)$，如果存在 one to one 且 onto 的映射關係 $\varphi:G\rightarrow H$，使得所有 $G$ 中的 $x$、$y$ 都滿足 $f(x \oplus y)=f(x)*f(y)$，則 $f$ 是一個群同構，而 $G$ 與 $H$ 同構。
#### singular curve
前面說橢圓曲線的形式是 $y^2=x^3+ax+b \pmod p$，其實有個備註是取的 $a$ 和 $b$ 不能使得 $4a^3+27b^2=0\pmod p$，當滿足 $4a^3+27b^2=0\pmod p$ 時，這種曲線叫做 singular curve，他是有弱點的。
這樣的曲線一定可以被化為以下兩種曲線的其中一種：
- $y^2=(x-a)^3$
- $y^2=(x-a)^2(x-b)$
這兩種曲線都可以同構於另一個群中的相對簡單的運算，以下不會給證明，只會教怎麼用。
通常正常的橢圓曲線函式庫會禁止這樣的曲線出現，只有自己實作的才比較有可能出現這種問題。
#### 曲線 $y^2=(x-a)^3$
我們把這個曲線上的點 $(x, y)$ 都映射成 $(x-a)y^{-1}\pmod p$ 這個數，這是一個群同構，從橢圓曲線上的加法群映射到模 $p$ 的加法群，也就是說離散對數問題會被簡化為模 $p$ 下的乘法問題。
舉個具體一點的例子：
定義 $F((x, y)) = (x-a)y^{-1}$（以下都在模 $p$ 底下運算不多贅述），現在有 $G$、$x$ 與 $y=xG$。現在先把 $G$ 映射為 $F(G)$，把 $y$ 映射為 $F(y)$，那麼在映射過去的群裡面這個離散對數問題變成了普通的模 $p$ 意義底下的 $F(y)=xF(G)$，可以簡單的用模逆原來計算 $x=F(y)F(G)^{-1}$
#### 曲線 $y^2=(x-a)^2(x-b)$
一樣的概念，只是它會把 $(x, y)$ 映射成 $\frac{y+\sqrt{a - b}(x-a)}{y-\sqrt{a-b}(x-a)}$，這是一個從橢圓曲線加法群映射到模 $p$ 乘法群的群同構，也就是橢圓曲線上的離散對數問題被簡化為了普通的離散對數問題。
#### baby_singular_curve
這題在自己寫的一個橢圓曲線運算上出一個離散對數問題，其中 $a$ 和 $b$ 都是 $0$，很明顯是 singular，且符合以上第一種的形式。
```python
p = 9050530688715247120969729628492380160042134997240313989906806042561926071086167885723573703694486269088911077994875609728623164679961224421421355584310447
a = 0
b = 0
E = SingularCurve(GF(p), (a, b))
print("Notice that this curve equals to y^2 = x^3")
x = bytes_to_long(FLAG)
G = SingularPoint(4, 8, E)
y = x * G
print(f"{a = }")
print(f"{b = }")
print(f"{p = }")
print(f"{G = }")
print(f"{y = }")
```
直接把它映射成 $(x-a)y^{-1}\pmod p$，直接當一般的模方程來解：
```python
from sage.all import *
from Crypto.Util.number import *
a = 0
b = 0
p = 9050530688715247120969729628492380160042134997240313989906806042561926071086167885723573703694486269088911077994875609728623164679961224421421355584310447
G = (4, 8)
y = (6576354267832965830049779307568897574606493988629289191787533477590990920764180367362358931148464655380505097736427327645872184653337434195261496542736451, 5336510970772303219396349645635651134403294867797570299665640917043392655696246805948819755799345746267036016574552227623143249157838669332260732012993569)
def phi(x, y, p, alpha):
x = GF(p)(x)
y = GF(p)(y)
alpha = GF(p)(alpha)
return (x - alpha) / y
G = phi(G[0], G[1], p, 0)
y = phi(y[0], y[1], p, 0)
x = y / G
print(long_to_bytes(int(x)))
```
### invalid curve attack
第一次知道這個技術是在寫之前 AIS3 pre-exam 2022 的 [pekobot](https://github.com/maple3142/My-CTF-Challenges/tree/master/AIS3%20Pre-exam%202022/pekobot)。
有一個離散對數問題 $y=xG$，這是當 server 會幫你計算任意輸入點的 $x$ 倍，且不會檢查你輸入的點是否在這個曲線上的時候，可以用的攻擊。
#### 沒有 $b$ 的加法
一個不明顯的事實是，在橢圓曲線上做加法和乘二時，不會用到 $b$ 這個係數。
如果 $P_1(x_1,y_1) \neq P_2(x_2,y_2)$，則 $P_3=P_1+P_2$ 可以表示成以下：
$x_3=s^2-x_1-x_2$
$y_3=s(x_1-x_2) - y_1$
其中，$s=\frac{y_1-y_2}{x_1-x_2}$
如果 $P_1=P_2$ 的話，則 $P_3=P_1+P_2$ 可以表示成以下：
$x_3=s^2-2x_1$
$y_3=s(x_1-x_2)-y_1$
其中，$s=\frac{3x_1^2+a}{2y_1}$
#### invalid curve attack
既然加法沒用到 $b$，又不會檢查輸入點是否在曲線上，那麼我們可以生成出一個 $a$ 和原本曲線一樣但 $b$ 不一樣的曲線，在裡面選一個點送給 server 做操作，因為完全不會用到 $b$，所以等價於在新的曲線上做操作。那我們可以選擇一些有弱點的曲線來進行攻擊。
#### 想法 1：singular curve
如果可以找到一個 $b$ 使得 $4a^3+27b^2=0$ 的話，那麼就可以用 singular curve attack。判斷方法是使用[歐拉準則](https://en.wikipedia.org/wiki/Euler%27s_criterion)去判斷 $-4a^3\times27^{-1}$ 是否為模 $p$ 下的二次剩餘。
#### 想法 2：invalid curve attack
通常指的 invalid curve attack 是指這種，無法找到符合條件的 singular curve 的話，可以找一些有階比較小的子群的橢圓曲線，攻擊流程是這樣的：
固定 $a$，去枚舉 $b$，看看 $y^2=x^3+ax+b$ 這個橢圓曲線的階 $ord$ 有沒有一個小的質因數 $k$ 次方 $p^k$
如果有的話，找一個在這個曲線上的生成元 $G$，讓 server 幫我們計算出在這個曲線上的 $y=xG$，我們把它化為 $(\frac{ord}{p^k})y=x(\frac{ord}{p^k})G$，在階為 $p^k$ 的子群上考慮這個問題，於是成功的求出了 $x\pmod {p^k}$
聚集了足夠多互質的 $p^k$ 和對應的解之後，就能 CRT 映射回去，得到 $x$
#### baby_invalid_curve
這題給你橢圓曲線的參數和一個離散對數問題，然後你可以輸入任意 $P$ 點，它會回傳給你 $xP$，而且不會檢查 $P$ 是否在曲線上。
```python
def challenge():
key = os.urandom(16)
x = bytes_to_long(key)
p = 72364592471999048991746278474134824829105489436651145838157001475268386866299
a = 8604640036494654386860733898153642122179620931985649848848369802781091921371
b = 56971794987620162734644006973338772666664821136381881122328067160515831408060
G = (41812042345829448981995671495167223372573459468985716536568937365077238371758, 2499393139327142407391759590193587472717194978120088345893100098450726121503)
E = Curve(p, (a, b))
G = Point(G[0], G[1], E)
y = x * G
cipher = AES.new(key, AES.MODE_ECB)
print(f"a: {a}")
print(f"b: {b}")
print(f"p: {p}")
print(f"G: {G}")
print(f"y: {y}")
print(f"cipher: {cipher.encrypt(pad(FLAG, 16)).hex()}")
while True:
p0 = int(input("x: "))
p1 = int(input("y: "))
P = Point(p0, p1, E)
print(f"res: {x * P}")
```
以下是解法：
首先我會去枚舉 $b$，收集各種可以用的 $b$ 和子群：
```python
yees = []
prods = 1
done = False
for b in range(1, 100):
if done:
break
try:
if (4 * a**3 + 27 * b**2) % p == 0:
continue
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]
ord = E.order()
for pp, e in factor(ord):
if pp**e < 2**40:
if gcd(prods, pp) != 1:
continue
prods *= pp**e
if prods > 2**257:
done = True
print(pp**e)
yees.append((G.xy(), b, pp**e, ord))
except:
pass
```
接下來各個子群分開爆破，再 CRT 回來：
```python
for G, b, pp, ord in yees:
r.sendlineafter(b": ", str(G[0]).encode())
r.sendlineafter(b": ", str(G[1]).encode())
r.recvuntil(b"(")
P = tuple(map(int, r.recvline().strip(b")\n").decode().split(", ")))
print(a, b)
try:
E = EllipticCurve(GF(p), [a, b])
G = E(G)
P = E(P)
sol = discrete_log((ord // pp) * P, (ord // pp) * G, ord=pp, operation="+")
sols.append(sol)
primes.append(pp)
except:
pass
sol = crt(sols, primes)
```
## lattice
我猜也講不到，不過之後有空可以補一下筆記，可以去看 [lll_cvp](https://github.com/maple3142/lll_cvp) 與歷屆 HITCON 題。
Sign in with Wallet
Connect another wallet