2.3.2　RSA算法

Rivest-Shamir-Adleman（RSA）算法是最流行和最安全的公鑰加密方法之一。該算法利用了這樣一個(gè)事實(shí)：根據(jù)數(shù)論，尋求兩個(gè)大素?cái)?shù)相對(duì)比較簡單，但是將它們的乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開，作為加密密鑰。加密密鑰是公開的，解密密鑰由用戶保密。

假設(shè)使用加密密鑰key（e，n），其實(shí)現(xiàn)算法如下：

將消息表示為0到（n-1）之間的整數(shù)。大型消息可以分解為多個(gè)塊。然后，每個(gè)塊將由相同范圍內(nèi)的整數(shù)表示。

取其e次方再模n，得到密文消息C；

要解密密文消息C，取其d次方再模n；

加密密鑰（e，n）是公開的。解密密鑰（d，n）由用戶保密。

如何確定e，d和n的適當(dāng)值？

選擇兩個(gè)非常大（100位以上）的素?cái)?shù)，將其表示為p和q。

將n設(shè)為等于p * q。

選擇任何大整數(shù)d，使得GCD（d，（（p-1）*（q-1）））= 1。

求e使得e * d = 1（mod（（p-1）*（q-1）））。

Rivest、Shamir和Adleman為每個(gè)所需的操作提供了有效的算法。