# 後量子密碼學 02：一個簡易的二維晶格密碼學
在本篇中，將介紹一個「看起來相當簡易」的密碼系統，卻能從中看出晶格密碼學（Lattice Based Cryptography）的雛形。別擔心，你或許會疑惑「這不就兩個整數再做些運算而已嗎？那晶格 Lattice 在哪？」——我們會在下一篇文章揭露它和晶格的關聯，以及如何進行正確性證明與可能的破解方式。
## 密鑰生成
假設 Alice 想要生成一組公私鑰，用於加解密。步驟如下：
一、選擇一個整數 $q$ 作為公共參數（public parameter）
二、選擇秘密整數 $f$ 和 $g$，並滿足：
\begin{align}
f < \sqrt{\frac{q}{2}}\\
\sqrt{\frac{q}{4}} < \text{g} <\sqrt{ \frac{q}{2} } \\
\mathrm{gcd}(f,qg)=1
\end{align}
（這些不等式在解密的正確性證明中會派上用場，故在此不需特別研究。）
三、計算公鑰 $h$
\begin{align}
h = f^{-1}g \mod q
\end{align}
四、最終，Alice 將公鑰發布為 $(q,h)$，私鑰則是 $(f,g)$。
以下是使用 SageMath 進行的範例
```python=+
def keygen():
"""
生成公私鑰 (q, h) 與 (f, g)。
條件：
1) q 為整數公共參數
2) f, g 為秘密整數，需滿足以下限制：
- f < sqrt(q/2)
- sqrt(q/4) < g < sqrt(q/2)
- gcd(f, q*g) == 1
3) h = f^(-1) * g (mod q)
回傳：
pk = (q, h)
sk = (f, g)
"""
while True:
# 隨機生成 q
q_candidate = randint(2, (2**32) - 1)
if q_candidate < 4:
continue # 避免 sqrt(q/2) 出現問題
# 根據定義生成 f, g
f_candidate = randint(1, int(sqrt(q_candidate/2)))
g_lower = int(sqrt(q_candidate/4))
g_upper = int(sqrt(q_candidate/2))
if g_lower < 1:
g_lower = 1
g_candidate = randint(g_lower, max(g_lower, g_upper))
# 判斷 gcd(f, q*g) == 1
if gcd(f_candidate, q_candidate*g_candidate) == 1:
q = q_candidate
f = f_candidate
g = g_candidate
break
# 進行模運算
R_q = quotient(ZZ, q*ZZ)
f_mod = R_q(f)
g_mod = R_q(g)
# 計算 h = f^(-1) * g (mod q)
h_mod = f_mod^(-1) * g_mod
# 封裝公私鑰
pk = (q, h_mod) # 公鑰
sk = (f_mod, g_mod) # 私鑰
return pk, sk
# 1. 生成公私鑰
pk, sk = keygen()
q_val, h_mod = pk
print("=== 公鑰 (pk) ===")
print("q =", q_val)
print("h =", h_mod)
print("\n=== 私鑰 (sk) ===")
print("f =", sk[0])
print("g =", sk[1])
# Outputs
# === 公鑰 (pk) ===
# q = 3965666550
# h = 2989066081
# === 私鑰 (sk) ===
# f = 7829
# g = 36599
```
## 加密訊息
現在 Bob 想要傳送訊息給 Alice：
Bob 先選擇要傳送的訊息 $m$ 以及一個隨機的 $r$ ，其中
\begin{align}
0 < m <\sqrt{ \frac{q}{4} } \\
0 < r <\sqrt{ \frac{q}{2} }
\end{align}
計算密文為
\begin{align}
e = r h + m \mod q
\end{align}
程式範例如下：
```python=+
def encrypt(pk, m, r=None):
"""
加密函式：
給定公鑰 pk = (q, h)，以及訊息 m 與隨機數 r，
計算 e = r*h + m (mod q)。
- 若 r 未指定，則自動隨機產生適當範圍的 r。
- m 需滿足 0 < m < sqrt(q/4)
- r 需滿足 0 < r < sqrt(q/2)
回傳：
e：加密後的密文
"""
q, h_mod = pk
R_q = quotient(ZZ, q*ZZ)
# 簡易的範圍檢查
if not (1 <= m < int(sqrt(q/4))):
raise ValueError("m 值超出建議範圍 (0, sqrt(q/4))。")
# 若 r 未指定，則自動生成
if r is None:
r = randint(1, int(sqrt(q/2)))
if not (1 <= r < int(sqrt(q/2))):
raise ValueError("r 值超出建議範圍 (0, sqrt(q/2))。")
# 模運算轉換
r_mod = R_q(r)
m_mod = R_q(m)
# e = r*h + m (mod q)
e_mod = r_mod * h_mod + m_mod
return e_mod
# 2. 隨機選個訊息 m 來加密
m_val = randint(1, int(sqrt(q_val/4)))
print(f"\n=== Message to encrypt: {m_val} ===")
# 進行加密
e_mod = encrypt(pk, m_val)
print("=== Ciphertext e ===")
print(e_mod)
# Outputs
# === Message to encrypt: 6863 ===
# === Ciphertext e ===
# 1131212074
```
## 解密訊息
接下來，Alice 使用私鑰 $(f,g)$ 要解開密文 $e$，步驟如下：
\begin{aligned}
a &= fe \mod q
\\
b &= f^{-1}a \mod g
\end{aligned}
則可得 $b=m$。
```python=+
def decrypt(sk, e_mod):
"""
解密函式：
給定私鑰 sk = (f, g) 與密文 e_mod：
1) a = f * e (mod q)
2) b = f^(-1) * a (mod g)
得到 b = m。
回傳：
m：解密後的訊息
"""
f_mod, g_mod = sk
# 從 f_mod.parent() 中取出 q，也就是 f, e 的模數
q = f_mod.parent().modulus()
# a = f * e (mod q)
a_mod = f_mod * e_mod
a_int = a_mod.lift() # 提升成普通整數
# 在 g 的環上繼續做運算
R_g = quotient(ZZ, g_mod.lift() * ZZ)
a_mod_in_g = R_g(a_int)
f_int = f_mod.lift()
f_mod_in_g = R_g(f_int)
# b = f^(-1) * a (mod g)
b_mod = f_mod_in_g^(-1) * a_mod_in_g
m = b_mod.lift() # 還原成一般整數
return m
# 3. 解密
decrypted_m = decrypt(sk, e_mod)
print("\n=== Decrypted message ===")
print(decrypted_m)
# 驗證
print("\n=== Correctness check ===")
print(f"Original m: {m_val}, Decrypted m: {decrypted_m}")
print("Is correct:", m_val == decrypted_m)
# Outputs:
# === Decrypted message ===
# 6863
#
# === Correctness check ===
# Original m: 6863, Decrypted m: 6863
# Is correct: True
```
## 整合程式碼
有了三大函式後，就能在 `__main__` 裡面跑一遍示範整個流程：
1. 生成公私鑰
2. 選定訊息 m 並加密
3. 用私鑰解密後驗證正確性
以下程式碼放在同一個檔案中，藉由 `if __name__ == "__main__":` 區塊執行：
```python=+
if __name__ == "__main__":
# 1. 生成公私鑰
pk, sk = keygen()
q_val, h_mod = pk
print("=== 公鑰 (pk) ===")
print("q =", q_val)
print("h =", h_mod)
print("\n=== 私鑰 (sk) ===")
print("f =", sk[0])
print("g =", sk[1])
# 2. 隨機選個訊息 m 來加密
m_val = randint(1, int(sqrt(q_val/4)))
print(f"\n=== Message to encrypt: {m_val} ===")
# 進行加密
e_mod = encrypt(pk, m_val)
print("=== Ciphertext e ===")
print(e_mod)
# 3. 解密
decrypted_m = decrypt(sk, e_mod)
print("\n=== Decrypted message ===")
print(decrypted_m)
# 驗證
print("\n=== Correctness check ===")
print(f"Original m: {m_val}, Decrypted m: {decrypted_m}")
print("Is correct:", m_val == decrypted_m)
# Outputs
# === 公鑰 (pk) ===
# q = 3965666550
# h = 2989066081
# === 私鑰 (sk) ===
# f = 7829
# g = 36599
# === Message to encrypt: 6863 ===
# === Ciphertext e ===
# 1131212074
# === Decrypted message ===
# 6863
# === Correctness check ===
# Original m: 6863, Decrypted m: 6863
# Is correct: True
```
透過以上範例程式和解說，相信你已經了解「在二維情況下的晶格式密碼系統」是如何產生公私鑰、進行加解密，以及證明它在某些條件下能安全傳輸訊息。接下來，我們會更進一步，從「數學正確性證明」及「破解策略」的角度深入探討，並說明為何可以視它為「晶格密碼學」的簡化版本，讓我們在進入高維晶格前，先打好基礎。
