一、RSA 加密算法

密鑰生成：

1. 選兩個大素數 p 和 q
2. 計算 n = p × q
3. 計算 φ(n) = (p-1)(q-1)
4. 選整數 e 滿足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
5. 計算 d 滿足 d × e ≡ 1 mod φ(n)

公鑰：(e, n)
私鑰：(d, n)

加密：

c ≡ m? mod n

解密：

m ≡ c? mod n

手算示例：

p = 3, q = 11
n = 33
φ(n) = 20
e = 3 (滿足 gcd(3,20)=1)
d = 7 (3×7=21≡1 mod20)加密 m=5：
c = 53 mod 33 = 125 mod 33 = 26解密 c=26：
m = 26? mod 33
262 = 676 ≡ 16 mod 33
26? = (262)2 ≡ 162 = 256 ≡ 25 mod 33
26? = 26? × 262 ≡ 25×16 = 400 ≡ 4 mod 33
26? = 26? × 26 ≡ 4×26 = 104 ≡ 5 mod 33 → 解密成功

二、ElGamal 加密算法

密鑰生成：

1. 選大素數 p 和生成元 g
2. 選私鑰 x (1 < x < p-1)
3. 計算公鑰 y ≡ g? mod p

公鑰：(p, g, y)
私鑰：x

加密：

1. 選隨機數 k
2. 計算 c? ≡ g? mod p
3. 計算 c? ≡ m × y? mod p
   密文：(c?, c?)

解密：

m ≡ c? × (c??)?1 mod p

手算示例：

p=23, g=5, x=6
y = 5? mod 23 = 15625 mod 23 = 8加密 m=10 (k=3)：
c? = 53 mod 23 = 125 mod 23 = 10
c? = 10×83 mod 23 = 10×512 mod 23 = 10×6 = 60 ≡ 14 mod 23
密文：(10,14)解密：
c?? = 10? mod 23
102=100≡8, 10?=(102)2≡82=64≡18, 10?=10?×102≡18×8=144≡6 mod 23
m = 14×6?1 mod 23
6?1=4 (6×4=24≡1) → 14×4=56≡10 mod 23 → 解密成功

三、橢圓曲線加密（ECC）

密鑰生成：

1. 選橢圓曲線 E 和基點 G
2. 選私鑰 $n_B$(整數)
3. 計算公鑰 $P_B=n_B\times G$
   公鑰：($E,G,P_B$)
   私鑰：$n_B$

加密：

1. 在橢圓群中選擇一點$P_t=(x_t,y_t)$
2. 選取一個隨機數$k$，計算點$P_1:P_1=(x_1,y_1)=kG$
3. 計算 $P_2=(x_2,y_2)=k{P}_B$
4. 計算 $C=m{x}_t+y_t$
   密文：($kG,P_t+k{P}_B,C$)

解密：

$P_t=P_t+k{P}_B?n_B(kG)=P_t+k(n_{B}G)?n_B(kG)$
$m=(C?y_t)/x_t$

手算示例（在曲線 $y^2=x+13x^3+22(mod23)$）：

取$p=23,a=13,b=2$,取生成元$G=(10,5)$
私鑰為$n_B=7$，明文為$m=15$,$P_t=(11,1)$

加密:
選取隨機數$k=13$，則得
$P_1=kG=13(10,5)=(16,5)$
$P_2=k{P}_B=13(17,21)=(20,18)$
$P_t+k{P}_B=(11,1)+(20,18)=(18,19)$
$C=m{x}_t+y_t=15\times 11+1(mod23)=5$
因此，$C_m=\{(16,5),(18,19),5\}$

解密:
$P_t=P_t+k{P}_B?n_B(kG)=(18,19)?7(16,5)=(11,1)$
$m=(C?y_t)/x_t=(5?1)/11(mod23)=15$

四、RSA 簽名

設代簽名的消息為m,利用Hash函數計算信息摘要h(m)

簽名：

s ≡ h(m)? mod n
簽名信息(s,m)

驗證：

計算h(m)
h(m) ≡ s? mod n

手算示例（接RSA加密參數）：

p = 3, q = 11
n = 33
φ(n) = 20
e = 3 (滿足 gcd(3,20)=1)
d = 7 (3×7=21≡1 mod20)簽名 h(m)=8：
s = 8? mod 33
82=64≡31, 8?=(82)2≡312=961≡4 mod 33
8?=8?×82≡4×31=124≡25 mod 33
8?=8?×8≡25×8=200≡2 mod 33 → 簽名=(2,8)驗證：
h(m) = 23 = 8 mod 33 → 驗證成功

五、ElGamal 簽名

利用Hash函數計算信息摘要h(m)

簽名：

1. 選隨機數 k
2. 計算$r\equiv g^{k}modp$
3. 計算 $s\equiv k^{?1}(h(m)?xr)mod(p?1)$
   簽名：(r, s)

驗證：

$g^{h(m)}\equiv y^r\times r^{s}modp$

手算示例（接ElGamal參數）：

$p=23,g=5,x=6$

簽名 $h(m)=10(k=3)：$
$r=g^k=5^3\equiv 10mod23$
$s=3^{?1}(10?6\times 10)mod22$
$3^{?1}=15(3\times 15=45\equiv 1mod22)$
$s=15\times (10?60)=15\times (?50)\equiv 15\times 16=240\equiv 20mod22$
簽名：$(10,20)$

驗證：
$g^{h(m)}=5^{10}mod23$
$5^2=25\equiv 2,5^4=2^2=4,5^8=4^2=16,5^{10}=5^8\times 5^2\equiv 16\times 2=32\equiv 9mod23$
$y^r\times r^s=8^{10}\times 10^{20}mod23$
$8^2=64\equiv 18,8^4=18^2=324\equiv 2,8^8=2^2=4,8^{10}=8^8\times 8^2\equiv 4\times 18=72\equiv 3$
$10^2=100\equiv 8,10^4=8^2=64\equiv 18,10^8=18^2=324\equiv 2,10^{16}=2^2=4,10^{20}=10^{16}\times 10^4\equiv 4\times 18=72\equiv 3$
$3\times 3=9\equiv 左邊\to 驗證成功$

六、Schnorr 簽名

密鑰生成:

1. 選擇兩個大素數p和q,q是p-1的大素因子
2. 選擇選擇一個生成元g,且$g^q\equiv 1(modp)$
3. 選隨機數 x,計算$y=g^{x}modp$
   公鑰為(p,q,g,y)
   私鑰為x

簽名：

1. 選隨機數k，計算r= g? mod p
2. 計算 e = H(m || r)
3. 計算 s = k + xe mod q
   簽名：(e, s)

驗證：

r? = g? × y?? mod p
驗證 H(m || r?) = e

手算示例：

p=23, q=11, g=2, x=5, y=2?=32≡9 mod 23簽名 m=10 (k=3)：
r = 23=8 mod 23
設有e = H(10||8) =7
s = 3 + 5×7 = 38 ≡ 5 mod 11 (38-3×11=5)
簽名：(7,5)驗證：
r? = g?×y?? = 2?×9?? mod 23
2?=32≡9
9?1：9×18=162≡162-7×23=162-161=1 → 18
9??=(9?1)?=18? mod 23
182=324≡324-14×23=324-322=2
18?=(182)2≡22=4
18?=18?×182≡4×2=8
18?=18?×18≡8×18=144≡144-6×23=144-138=6
r?=9×6=54≡54-2×23=8 mod 23
H(m||r?)=H(10||8)=7=e → 驗證成功

七、DSA 簽名

密鑰生成:

1. 選擇兩個素數p和q,p-1能被q整除
2. 選擇選擇一個生成元g,且$g^q\equiv 1(modp)$
3. 選隨機數 x,計算$y=g^{x}modp$
   公鑰為(p,q,g,y)
   私鑰為x

簽名：

1. 選隨機數 k
2. 計算 r = (g? mod p) mod q
3. 計算 s = k?1(H(m) + xr) mod q
   簽名：(r, s)

驗證：

1. 計算 w = s?1 mod q
2. 計算 u? = H(m)w mod q
3. 計算 u? = rw mod q
4. 計算 v = (g?1 × y?2 mod p) mod q
   驗證 v = r

手算示例：

p=23, q=11, g=2, x=5, y=9
H(m)=10簽名 H(m)=10 (k=3)：
r = (23 mod 23) mod 11 = 8 mod 11=8
s = 3?1(10+5×8) mod 11 = 4×50=200≡200-18×11=200-198=2
簽名：(8,2)驗證：
w = 2?1 mod 11 = 6
u? = 10×6=60≡5 mod 11
u? = 8×6=48≡4 mod 11 
v = (2?×9? mod 23) mod 11
2?=32≡9
92=81≡12, 9?=122=144≡6
9×6=54≡8 mod 23
8 mod 11=8=r → 驗證成功

八、ECDSA 簽名

密鑰生成:

1. 選橢圓曲線 E 和基點 G
2. 選擇G的階滿足安全要求的素數n
3. 選私鑰d(整數)
4. 計算公鑰 Q=dG
   公鑰：(n,Q)
   私鑰：d

簽名：

1. 選隨機數 k
2. 計算 (x?,y?) = k×G
3. 計算 r = x? mod n
4. 計算 s = k?1(H(m) + dr) mod n
   簽名：(r, s)

驗證：

1. 計算 w = s?1 mod n
2. 計算 u? = H(m)w mod n
3. 計算 u? = rw mod n
4. 計算 (x?,y?) = u?×G + u?×Q
   驗證 x? mod n = r

算法對比與應用場景

算法	安全基礎	簽名大小	速度	典型應用
RSA	大數分解	大 (3072位)	慢	SSL證書, 加密文件
ElGamal	離散對數	大 (3072位)	慢	PGP加密
ECC	橢圓曲線	小 (256位)	快	移動設備, IoT
Schnorr	離散對數	小	快	比特幣閃電網絡
DSA	離散對數	中等 (320位)	中等	政府文檔
ECDSA	橢圓曲線	小 (512位)	快	區塊鏈, 數字錢包

通過以上手算示例，我們可以直觀感受公鑰加密和簽名的數學本質。盡管實際應用使用大數（通常1024-4096位），但這些小規模計算揭示了算法的核心原理。現代密碼學正是建立在這些優雅的數學結構之上，守護著數字世界的安全邊界。

“密碼學是安全與效率的永恒舞蹈——在數學的約束中尋找完美平衡。”
—— Bruce Schneier