公鑰與私鑰的產生原理
假設 Alice 想要通過一個不可靠的媒體接收 Bob 的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：
- 選擇兩個大的質數 p、q，且 p != q，計算 n = p * q
- 根據歐拉函數取得 r = $\phi$(n) = (p-1)(q-1)
- 自己挑一個數字 e，0 < e < r，且 e 與 r 互質
- 求得模反元素 d，
ed ≡ 1(mod r)≡是同餘符號，一樣餘數的意思- 意思就是
ed mod r = 1
- 將 p、q 銷毀
- (n, e) 是公鑰
- n 為模係數 (modulus)，e 為公鑰指數 (public key exponent)
- (n, d) 是私鑰
- n 為模係數，與公鑰模係數同值，d 為私鑰指數 (private key exponent)
Alice 將她的公鑰 (n, e) 傳給 Bob，而將她的私鑰 (n, d) 藏起來
加密原理
假設 Bob 想給 Alice 送一個訊息 m，他知道 Alice 產生的 n 和 e，就可以用以下這個公式將 m 加密為 c
- 注意：
0 ≤ m < n
c ≡ m^e (mod n)
計算 c 並不複雜。Bob 算出 c 後就可以將它遞移給 Alice。
解密原理
Alice 得到 Bob 的訊息 c 後就可以利用她的金鑰 d 來解碼。她可以用以下這個公式來將 c 轉換為 m
m ≡ c^d (mod n)
舉例
產生公私鑰
- 找到兩個質數 p = 61、q = 53
- n = 61 * 53 = 3233
- r = (61 - 1)(53 - 1) = 3120
- 找到一個 e = 17，0 < 17 < 3120，且 17 與 3120 互質
- 17d ≡ 1 (mod 3120) => 17d - 1 = 3120t => 假設 t 為 15 => 17d - 1 = 3120 * 15 => d = 2753
- 模組 n = 3233
- 公鑰 e = 17
- 私鑰 d = 2753
加解密
- 明文 m = 123
- m^17 = 123^17 mod 3233 = 885
- 密文 c = 885
- c^2753 = 885^2753 mod 3233 = 123
OpenSSL
- 告訴 OpenSSL 我們要產生 4096 bits 的 n，實際上他會在 4096 bits 附近找，不一定能找到完全符合的
- 公鑰係數 e 通常都會用 65537
- 私鑰係數 d 由公式算出，有多組可以選
- OpenSSL 的官網說會遵循 PKCS (公鑰密碼學標準)，根據 PKCS #1 (RSA密碼編譯標準) 得知加密的標準 明文必須在 0 到模係數 - 1 的範圍，即
0 <= m < nm < n如此一來才能確保在解密時的結果為唯一值，即是當初的明文c < n亦是如此
補充說明
同餘
x ≡ y (mod 3)
表示 x 和 y 除以 3 的餘數相同
x mod 3 = y mod 3
等價於 x - y 是 3 的倍數
或可寫成 x - y = 3t，t是整數
長度迷思
長度只是一個記憶體位置，和值不一樣
例如：
1 => 長度為1 => 記憶體位置 1 byte，但值是 01
2 => 長度為1 => 記憶體位置 1 byte，但值是 10
不要把上面值的比較，想成長度比較