公開密鑰加密算法,也被稱為非對稱加密算法。
該算法的加密過程需要兩個密鑰,一個用作加密,另一個則用作解密。 使用其中一個密鑰把明文加密後所得的密文,只能用相對應的另一個密鑰才能解密得到原本的明文。 由於加密和解密需要兩個不同的密鑰,故被稱為非對稱加密。
雖然兩個密鑰在數學上相關,但如果知道了其中一個,並不能憑此計算出另外一個。
其中一個可以公開,稱為公鑰,任意向外發布;不公開的密鑰為私鑰,必須由用戶自行嚴格保管,不能向向任何人提供,也不需要透露給要通信的另一方。
公開密鑰加密算法的關鍵在於公鑰私鑰生成,因此通常都根據數學難題設計公鑰私鑰。 常用的三個難題為:質數分解,離散對數和橢圓曲線問題。
例如被廣泛使用的 RSA 算法就是基於極大整數因數分解難題設計的。
下面演示一下簡化版的 RSA 加密解密流程:
Alice 隨意選擇兩個素數(實際使用中會使用足夠長的素數)p = 11 和 q = 13。
p 和 q 的模數為 n = p * q = 143,其歐拉函數值為 r = (p-1)*(q-1) = 120。
接下來是公鑰私鑰生成。 公鑰是從小於 r 且與 r 互質的數中選擇一個數字,例如 e = 7。 私鑰則是 e 關於 r 的模反元素。
根據擴展歐幾里得算法可以計算出私鑰 d = 103,可以驗證 e * d = 7 * 103 = 721,721 與 1 關於 120 同餘。
此時對於 Alice 來說,其公鑰為(n, e),私鑰為(n, d)。
當 Bob 要向 Alice 傳遞信息時,那麼 Bob 首先要獲取 Alice 的公鑰,然後 Bob 開始加密信息。
假設發送信息為 m = 9(實際中雙方按照約定格式將信息轉為一個小於 n 且與 n 互質的整數形式)。
則加密後的密文為 c = m^e mod n = 9^7 mod 143 = 48。
Alice 收到密文後用自己的私鑰解密。 c^d mod n = 48^103 mod 143 = 9。
當攻擊者獲得 Alice 的公鑰(n, e) 以及密文 c 時,他無法直接獲取到私鑰(n, d)。 獲得 d 的最簡單方法是將 n 分解為 p 和 q。 只要人類無法改進對極大整數進行因數分解的算法,那麼用足夠長(4096位或以上) RSA 公鑰加密的信息就可以被認為是無法破解的。
當然,實際使用要比理論上複雜得多。 例如,非對稱加密通常要比對稱加密算法計算複雜、性能差,一般會先用對稱加密算法生成密文,再由非對稱加密算法來加密對稱密鑰。
另外,為了防止中間人攻擊,公開密鑰加密算法需要由可靠的第三方機構簽發數字證書,用來證明公開密鑰擁有者的身份。 。
除了用於加密,公開密鑰加密算法還有一個重要的應用:數字簽名。