密碼學基礎與應用
以小數字確認RSA加密的機制。由質數 p = 5、q = 11 作出 n = pq，公開指數設為 e = 3。令 φ(n) = (p − 1)(q − 1)，滿足 e × d ≡ 1 (mod φ(n)) 的私密指數 d（0 < d < φ(n)）為下列何者？
- A5
- B27
- C37
查看答案與解析
正確答案：B. 27
n = 5 × 11 = 55，φ(n) = 4 × 10 = 40。尋找使 3 × d 除以40餘1的 d，因為 3 × 27 = 81 = 2 × 40 + 1，所以 d = 27。公開金鑰為 (n, e) = (55, 3)，私密金鑰為 d = 27；不知道 p 與 q 就無法得知 φ(n)，也就求不出 d，這就是安全性的根據。實際的RSA加密中，p 與 q 各是超過1000位元的大質數，e 常使用65537。
- A. 5是把 φ(n) 誤當成 (p − 1) + (q − 1) = 14，由 3 × 5 = 15 ≡ 1 (mod 14) 求得的值。
- B. 正確。3 × 27 = 81 ≡ 1 (mod 40)。
- C. 37是用 n = 55 代替 φ(n)，由 3 × 37 = 111 ≡ 1 (mod 55) 求得的值。