金鑰產生是建立 RSA 金鑰對的過程，也就是產生：

• 公鑰：模數 n 與公開指數 e
• 私鑰：秘密指數 d

數 p 與 q（滿足 n = pq）以及階 φ(n) 也必須保密，因此它們常被視為私鑰的一部分。

產生流程#

1. 隨機挑兩個質數 p 與 q。
2. 從它們算出 φ(n)。
3. 把 d 算成 e 的反元素。

用 SageMath（一個開源的類 Python 數學環境）示範：

sage: p = random_prime(2^32); p
1103222539
sage: q = random_prime(2^32); q
17870599
sage: n = p*q; n
19715247602230861
sage: phi = (p-1)*(q-1); phi
19715246481137724
sage: e = random_prime(phi); e
13771927877214701
sage: d = xgcd(e, phi)[1]; d
15417970063428857
sage: mod(d*e, phi)
1

流程說明：

• 用 random_prime() 挑出小於給定引數的隨機質數 p 與 q。
• 相乘得到模數 n 與 φ(n)（變數 phi）。
• 挑一個小於 phi 的隨機質數當公開指數 e，藉此確保 e 在模 phi 下存在反元素。
• 用 Sage 的 xgcd() 產生對應的私有指數 d。這個函式用擴展歐幾里得演算法，對兩數 a、b 計算滿足 as + bt = GCD(a, b) 的 s 與 t。
• 最後檢查 ed mod φ(n) = 1，確保 d 能正確反轉 RSA 置換。

為了避免好幾頁的輸出，上例用了 64 位元的模數 n。實務上 RSA 模數應該至少 2048 位元。

套用陷門置換#

sage: x = 1234567
sage: y = power_mod(x, e, n); y
19048323055755904
sage: power_mod(y, d, n)
1234567

power_mod(x, e, n) 就是模 n 的指數運算 x^e mod n。算出 y 之後，用陷門 d 計算 y^d mod n 就取回了原本的 x。

沒有陷門有多難#

攻擊 RSA 有兩條路：

• 能分解大數的攻擊者可以還原 p 與 q，進而得到 φ(n)，再從 e 算出 d，攻破 RSA。
• 另一個風險是攻擊者能從 x^e mod n 算出 x——也就是計算模 n 的 e 次方根——而不必真的分解 n。

這兩個風險看似緊密相連，但我們並不確定它們是否等價。

安全等級的三個因素#

假設因式分解確實困難、且求 e 次方根大致一樣難，RSA 的安全等級取決於三件事：

1. n 的大小#

若 n 太小，它就能在現實的時間內被分解，洩漏私鑰。

安全起見，n 至少應為 2048 位元（約 90 位元安全等級，需要約 2^90 次運算），最好是 4096 位元（約 128 位元安全等級）。

2. p 與 q 的選擇#

若它們太小、或彼此太接近，就更容易從 n 判定它們的值。

3. 陷門置換的使用方式#

原因見後續章節。