在前兩篇文章中我們介紹了DES、AES、IDEA等多種對稱加密算法，雖然這些算法通過複雜的運算邏輯來保證其加密的安全性，但所有對稱加密算法都會存在密鑰配送問題。
密鑰配送問題的存在是因為對稱加密算法在加密和解密時使用的是相同的密鑰，所以當信息發送者將密文傳遞給接收者的同時，也需要傳遞用以解密的密鑰。這就給了竊聽者以可乘之機。所以為了實現真正的安全，需要解決密鑰的配送問題，保證其在配送過程中不被竊聽者獲取和更改。這就需要非對稱加密了。
本文將主要介紹非對稱加密的方法、RSA算法的原理以及常見的攻擊方法與對策。一、非對稱加密
1.1 簡介
非對稱加密又稱為公鑰加密，這裡說它是非對稱加密是相對對稱加密而言的。對稱加密的加密密鑰和解密密鑰是相同的，而非對稱加密的這兩個密鑰是不同的。
在非對稱加密中，其加密密鑰由密文的接收者發出，密文的發送者利用該密鑰對明文進行加密，然後將密文發出，因為它是可以被公開的，所以又稱為「公鑰」；解密密鑰僅密文接收者自己擁有，且密文只能被該密鑰解密，因此又稱為「私鑰」。
公鑰和私鑰的關係可以用三個詞來形容：
①數學：即數學上的關係。私鑰是基於公鑰、利用數學方法生成的；
②成對：非對稱加密的密鑰是成對出現的，即（公鑰，私鑰）；
③一一對應：對於一個密鑰對A（公鑰A，私鑰A），公鑰A加密得到的密文，只有密鑰A才能夠解密。
2.1 加密流程
如上圖所示，非對稱加密需要經歷以下五個步驟：
密文接收者生成密鑰對；密文接收者保留私鑰，將公鑰發送給密文發送者；密文發送者收到公鑰後，利用公鑰進行加密，生成密文；密文發送者將密文發送給密文接收者；收到密文後，密文接收者利用私鑰解密，得到明文信息。
在上述過程中，公鑰和密文是有被竊取的風險的（也就是圖中標紅的兩部分內容）。因為只要私鑰才能解密，所以只要密文接收者能夠保管好私鑰，就不容易出現密文被破解的情況。但如果公鑰被竊取，就容易遭受中間人攻擊，所以需要公鑰證書來保證公鑰的正確性。
不同非對稱加密算法的加密流程是相同的，但密鑰對生成的原理、加解密的原理卻是不同的。下面這一節我們來具體了解一下現在使用最廣泛的非對稱加密算法——RSA。二、RSA
RSA算法發布於1977年，被廣泛應用於數字籤名和信息加密傳輸的場景中。
2.1 加密原理
假設公鑰是（E，N），沒錯，每個公鑰和私鑰都是由兩個數字組成的。而且，在RSA算法中的明文和密文也都是用數字表示的。所以在加密前需要將明文轉換為一個不大於N的二進位數字（不大於N的原因我們在「2.2 解密原理」中進行講解）。
其中「mod」是指求模運算。也就是說，密文是明文的E次方除以N的餘數。所以密文一定小於或等於N。
2.2 解密原理
假設私鑰是（D，N）。這裡的N與公鑰中的N是相同的。
同理，明文就是密文的D次方除以N的餘數。這也就是為什麼明文不能大於N的原因。
以上就是RSA算法的加解密原理。其實RSA算法的加解密原理比我們之前認識的那些對稱加密算法都要簡單得多，其公鑰和私鑰的生成也是保障其安全性的關鍵。
2.3 密鑰對的生成
由上述加解密的原理可知，RSA算法的密鑰對是由E、D、N這三個數字組成的。所以密鑰對的生成過程實質上就是這三個數字的生成過程。同時中間量——L也是這個過程中的一個很重要的值。
接下來我們就來分別討論一下這四個值是如何生成的。
1. N
這裡的p和q兩個隨機的、足夠大的質數。因為這兩個質數還被應用到後續的步驟中，所以p和q的保密對RSA的安全性至關重要。然後我們來討論一下如何保證p、q的「隨機」、「足夠大」和「是質數」。
（1）p、q的隨機性
p和q是通過偽隨機數生成器生成的。所以我們需要選擇一個好的偽隨機數生成器來保證p和q的隨機性。如果生成的p或q不是質數，那就需要再重新生成一個新的值，直到兩者都是質數為止。那如何判斷p和q是不是質數呢？
（2）p、q是質數
質數，也稱為素數，其約數就只有兩個——1和它本身。但我們判斷p、q是不是質數的方法不是看它是不是能不能分解質因數，而是通過專業的數學方法——費馬測試和米勒∙拉賓測試（這兩種測試方法的參考連結：http://www.matrix67.com/blog/archives/234）。
（3）p、q足夠大
保證p、q足夠大的原因是要保證N足夠大。N作為公鑰的一部分是被公開的，所以要防止N被分解。如果N能被分解，破解者就可以推測出私鑰的值，進而破解密文。
目前，NIST建議RSA的密鑰安全強度（也就是「N」）是2048 bits。但在2030年之後，就應增加到3072 bits。
2. L
L是「 p-1 」和「 q-1 」的最小公倍數，利用公式表示如下：
3. E
對於E的取值，有兩個要求：一是L的取值範圍是（1，L）；二是E和L的最大公約數為1，即E和L互質。用公式表示如下：
這裡，E的生成仍需要藉助偽隨機數生成器，同時可以藉助歐幾裡得的輾轉相除法來判斷E和L是否互質。
4. D
D的取值要求用公式表示如下：
這樣就生成了RSA加密的密鑰對——[（E，N），（D，N）]。
綜上所述，密鑰對的生成流程如下圖所示：
2.4 對RSA的攻擊方法及對策
1.對模數N的質因數分解攻擊
由密鑰對的生成過程可知，p、q是整個運算過程的基礎，如果知道p、q，就可以求出對應的私鑰。
雖然RSA算法的p、q是未知的，但「N = p × q」是已知的。所以如果N能被質因數分解，就能夠求出D，就破解了RSA。也就是說，N值越大，越不容易被質因數分解，RSA算法也就越安全。NIST提供的關於RSA密鑰強度與近似的對稱加密密鑰強度的對應關係如下表所示：
RSA密鑰強度
對稱加密密鑰強度（對應算法）
1024
80（2DES）
2048
112（3DES）
3072
128（AES-128）
7680
192（AES-192）
15360
256（AES-256）
截止至2019年，能被分解的N的最大長度為795 bits。所以NIST建議目前的RSA密鑰安全強度是2048 bits，但在2030年後，密鑰安全強度需增加至3072 bits。
2.公共模數攻擊
公共模數是指一個多用戶系統只使用一個模數N，也就是說不同的用戶擁有相同的N和不同的E、D，當然他們的p、q、L也是相同的。這次情況下，他們的公鑰是互質的（因為gcd（ E，L ）= 1），所以若同一消息用不同的公鑰加密，其密文不需要私鑰也能被解密。
假設公共模數為N，兩個加密公鑰為E1、E2，明文消息為P，對應的密文分別為C1、C2。所以有：
C1 = P^E1 mod NC2 = P^E2 mod N攻擊者是很容易獲得N、E1、E2 和C1、C2的，通過這些值就可以計算出原來的明文消息P。計算過程如下：
因為：E1、E2互質；所以：存在不全為零的常數r、s，使得gcd（ E1 ，E2 ）= r∙E1 + s∙E2 = 1；設r < 0；則C1^r ∙ C2^s = （P^E1 mod N）^r ∙（P^E2 mod N）^s = P^(r∙E1 + s∙E2) mod N = P mod N；如果P < N，則P mod N = P，此時就得到了明文消息P。
綜上所述，多個用戶使用同一模數N是很不安全的。因此在多用戶系統中必須採用多個模數。
3.選擇密文攻擊
選擇密文攻擊指的是攻擊者能選擇不同的密文，並擁有對應的明 文，由此推出想要的信息。一般攻擊者會偽裝若干信息，讓擁有私鑰的用戶籤名，由此獲得有用的明文-密文對，然後推算想要的信息。
常見的選擇密文攻擊主要有以下兩種情況：
情況一：攻擊者想要偽造用戶對消息X的籤名
攻擊者先生成兩個消息X1、X2，使得x = （X1∙X2）mod N。然後騙取用戶對X1、X2的籤名，分別為S1 = X1^D mod N、S2 = X2^D mod N。然後攻擊者就可以計算出消息X的籤名，計算過程如下：
S = X^D mod N = （（X1∙X2）mod N ）^D mod N = （（X1^D mod N ）∙（X2^D mod N ））mod N = （S1∙S2）mod N情況二：攻擊者想要破解他竊取到的密文
假設攻擊者竊取的密文是C = ME mod N（M是對應的明文）。攻擊者首先生成一個小於N的隨機數——R，計算C』 = RE mod N。令C』』 = （C∙C'）mod N，然後騙取用戶對C』』的籤名，為M'' = C』'^D mod N。這樣攻擊者就可以計算出密文C對應的明文M，計算過程如下：
M = C^D mod N = （ C^D∙C』^D∙C』^(-D) ） mod N = （ C』』^D∙C』^(-D) ） mod N = （ C』』^D∙（C』^D mod N）^-1 ） mod N = （ C』』^D ∙ R^-1 ） mod N = （ M』』∙ R^-1 ） mod N該攻擊方法並不是針對算法本身，所以我們需要注意的是使用該算法的系統和用戶。對策主要有以下兩條：
①私鑰持有者不能對不信任的消息進行籤名；
②籤名時，要先使用哈希函數生成消息摘要，然後再對摘要籤名。
4.低加密指數E攻擊
對於選定的p、q，雖然選擇一個滿足「gcd（ E，L ）= 1」的E很容易，但所選擇的E的大小卻非常重要。選擇值較小的E，可加快加密的速度，但也會增加密文被暴力破解以及遭受低加密指數攻擊的風險。
①密文被暴力破解
若E、明文P都很小，就可容易出現P^E < N的情況。所以密文C = P^E mod N = P^E 。也就是說只要將密文C開E次方就能得到對應的明文P。
②低加密指數攻擊
若有三個用戶均選擇了E = 3，他們使用了不同的模數N1、N2、N3，並假設N1、N2、N3兩兩互質。
註：若不滿足N1、N2、N3兩兩互質的要求，那破解其私鑰就會變的非常簡單。以N1、N2有公因數為例，它們的公因數就是對應的p、q中的一個，所以就相當於破解了它們對應的p、q值，即破解了私鑰。當某人想要將同一明文P傳遞給著三個用戶的時候，就會先加密成三個密文，分別為：
C1 = P^3 mod N1C2 = P^3 mod N2C3 = P^3 mod N3設C = P^3 mod （N1∙N2∙N3），根據中國剩餘定理可通過N1、N2、N3、C1、C2、C3求出C的值。因為明文P是小於對應模數N1、N2、N3的，所以P3 < N1∙N2∙N3，因此C = P^3，由此即可求出明文P = ∛C。
可見，對於較小的E，可通過密文C直接算出明文P。因此在計算公鑰指數E的過程中，不能選擇過小的E。
5.中間人攻擊
中間人攻擊就是主動攻擊者混入發送者和接收者中間，對發送者偽裝成接收者，對接收者偽裝成發送者的攻擊方式。
如圖所示，中間人攻擊可分為以下幾個步驟：
發送者發出請求「請把你的公鑰發送給我」，並被攻擊者竊聽到了；接收者發送公鑰，被攻擊者攔截；攻擊者將自己的公鑰發送給發送者；發送者把用攻擊者公鑰加密的密文發送給接收者，但被攻擊者攔截，然後攻擊者用自己的私鑰破解得到了正確的消息；攻擊者偽造一份消息，並用接收者的公鑰進行加密，發送偽造密文給接收者，使接收者解密獲得的是偽造消息。
針對這種情況，我們需要使用公鑰證書來保證得到的公鑰來自可信任的人。
以上即為五種常見的RSA攻擊方法，一方面我們需要慎重考慮參數的選擇來保證算法本身的安全性，另一方面也需要通過公鑰證書、身份認證、使用哈希函數等輔助手段來保護RSA安全。
參考文獻
【1】RSA公鑰密碼的低指數攻擊.
【2】RSA算法的攻擊方法研究.李家蘭.
【3】RSA 算法中幾種可能洩密的參數選擇.謝建全,陽春華.
【4】圖解密碼技術 第3版.