RSA算法

RSA算法

1.隨機選擇兩個不相等的質數p和q。

2.計算p和q的乘積n。

3.計算n的歐拉函數φ(n)。

? φ(n) = (p-1)(q-1)

4.隨機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。

5.計算e對于φ(n)的模反元素d

　ed ≡ 1 (mod φ(n))

6.加密和解密

（1）加密要用公鑰 (n,e)

? me ≡ c (mod n)

（2）解密要用私鑰(n,d)

? cd ≡ m (mod n)