RSA 是一種非對稱加密算法，用“公鑰”加密，用“私鑰”解密，保證數據傳輸安全。
比喻理解：鎖和鑰匙
想象一下：
-
公鑰是“上鎖的鎖”，別人可以用它鎖住箱子（加密），但打不開。
-
私鑰是“鑰匙”，只有你自己有，可以打開鎖（解密）。
所以：
-
我給你一個“鎖”（公鑰），你用它鎖住一個箱子（加密數據）送回來。
-
只有我有鑰匙（私鑰），我能打開箱子（解密數據）。
注意事項
-
明文必須小于 n，也就是 m<n 否則需分塊加密
-
實際使用中，RSA 通常只加密 對稱密鑰（比如 AES），而不是大量數據
-
使用填充算法（如 OAEP）防止加密攻擊
第一步：選兩個質數
我們先選兩個質數（不能被整除的整數）：
p = 3
q = 11
第二步：計算 n 和 φ(n)
n = p × q = 3 × 11 = 33
φ(n) = (p - 1) × (q - 1) = 2 × 10 = 20
其中 φ(n) 是一種叫“歐拉函數”的東西，是 RSA 算法的核心之一。
第三步：選一個公鑰 e
我們要選一個跟 φ(n) = 20 互質的整數 e，通常選一個小的質數。
e = 7 （因為 7 跟 20 沒有公因數，合法）
第四步：求私鑰 d（讓它能反過來解密）
找一個整數 d，讓它滿足：
(e × d) % φ(n) = 1
(7 × d) % 20 = 1
試試：
7 × 3 = 21，21 % 20 = 1
所以：
d = 3
總結密鑰對：
公鑰 (e, n) = (7, 33)
私鑰 (d, n) = (3, 33)
加密過程
假設明文 m = 4，我們用公鑰 (7, 33) 加密：
c = m^e % n = 4^7 % 33= 16384 % 33= 16
得到密文：c = 16
解密過程
我們收到密文 16，用私鑰 (3, 33) 解密：
m = c^d % n = 16^3 % 33 = 4096 % 33 = 4
恢復出原文：m = 4
歐拉定理
歐拉定理（非常關鍵）
如果：
-
n是兩個大質數p * q -
m與n互質（也就是說 m 不能被 n 的質因子整除）
那么一定成立：m^φ(n) mod n = 1?（其中 φ(n) 是歐拉函數）
φ(n)：如果 n?是兩個質數 p?和 q?的乘積：n =?p * q，那么歐拉函數就是：φ(n)=(p?1)(q?1) ，這表示從 1 到 n?1 里面，有多少個數跟 n 互質。
假設：
-
p=7?，q=11
-
那么 n=p ? q=7
*11 = 77 -
則：
φ(77) = (7 ? 1)(11 ? 1) = 6*10 = 60
所以如果 m 與 77 互質，那：m ^ 60 mod??77 = 1
深入理解
我們選 d 的時候，是專門選出來能“抵消” e 的效果的。
所以：
-
加密是：
先做 e 次方 -
解密是：
再做 d 次方 -
e 和 d 是互相“取消”的
就像是這樣理解（m是需要用rsa加密的數據）
m^e 再 ^d 就等于 m^(e*d) 而我們生成 d 的時候，保證 e*d 剛好變成 “1 + φ(n) 的倍數”這個時候 m^(e*d) 就剛好又變回 m 本人。
解釋：
如果：e?* d = 1 mod φ(n)? ?? e * d = 1 + k * φ(n)
所以：m ^ (e * d) = m ^ (1+k * φ(n)) = m * ???????m ^ (k * φ(n))
然后根據歐拉定理：m ^ φ(n) mod n = 1? ?????????m ^ (k * φ(n)) mod n = 1
所以：m^(e * d) mod n = m mod n =? m 數據被解密（rsa要求被加密的數據滿足 m < n）
總結
| 步驟 | 操作 |
|---|---|
| 選質數 | p = 3, q = 11 |
| 計算 n | n = 33 |
| 計算 φ(n) | φ(n) = 20 |
| 選公鑰 e | e = 7 |
| 求私鑰 d | d = 3 |
| 加密 | m = 4 → c = 16（用公鑰） |
| 解密 | c = 16 → m = 4（用私鑰） |
)
