密碼學專題 - 非對稱加密算法 - RSA 算法

6.1 RSA 算法

第一個較完善的非對稱加密算法 RSA，它既能用于加密也能用于數(shù)字簽名。在已提出的非對稱加密算法中，RSA 是最容易理解和實現(xiàn)的。這個算法也是最流行的。RSA 以它的三個發(fā)明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的名字命名。該算法已經(jīng)經(jīng)受住了多年深入的密碼分析。雖然密碼分析者既不能證明也不能否定 RSA 的安全性，但這恰恰說明該算法有一定的可信度。

RSA 的安全基于大數(shù)分解的難度。其公開密鑰和私人密鑰是一對大素數(shù) (100 ~ 200 個十進制數(shù)或更大) 的函數(shù)。從一個公開密鑰和密文中恢復出明文的難度等價于分解兩個大素數(shù)之積。

為了產(chǎn)生兩個密鑰，選取兩個大素數(shù) $p$ 和 $q$ 。為了獲得最大程度的安全性，兩數(shù)的長度一樣。計算乘積：
$n = pq$

然后隨機選取加密密鑰 $e$ ，使 $e$ 和 $(p-1)(q-1)$ 互素。最后用毆幾里得擴展算法計算解密密鑰 $d$ ，以滿足
$ed \equiv 1 \ mod \ (p-1)(q-1)$

則

$d = e^{-1} \ mod \ (p-1)(q-1)$

注意 $d$ 和 $n$ 也互素。 $e$ 和 $n$ 是公開密鑰， $d$ 是私人密鑰。兩個素數(shù) $p$ 和 $q$ 不再需要，它們應該被舍棄，但絕不可泄露。

加密消息 $m$ 時，首先將它分成比 $n$ 小的數(shù)據(jù)分組 (采用二進制數(shù)，選取小于 $n$ 的 2 的最大次冪)。也就是說，如果 $p$ 和 $q$ 為 100 位的素數(shù)，那么 $n$ 將有 200 位，每個消息分組 $m_i$ 應小于 200 位長 (如果你需要加密固定的消息分組，那么可以在它的左邊填充一些 0 并確保該數(shù)比 $n$ 小)。加密后的密文 $c$ ，將由相同長度的分組 $c_i$ 組成。加密公式簡化為：
$c_i = m_i^e \ (mod \ n)$