銀行等機構如何使用大質數進行 RSA？
當使用 RSA 加密時，僅僅通過做來解密通常是不可行的
c^d mod n，因為例如在使用素數時 $ (p,q)=(12553,1233) $ ，與銀行使用的素數相比，它們是較小的素數，人們通常會選擇費馬數 $ 65537 $ 作為公共指數 $ e $ ，然後是私人指數 $ d $ 是 $ 4267793 $ ，當用作指數時，這是一個巨大的數字。銀行等在選擇質數時如何解密其數據 $ p $ 和 $ q $ 哪些是 100 位數字？
首先要加密/解密數據，如銀行等機構使用一些塊或流密碼，例如 AES（高級加密標準），與 RSA 算法相比速度非常快，處理相同數量的數據要快數百倍。但是塊密碼和流密碼使用對稱密鑰（通常是 128-256 位隨機數，遠小於 RSA 密鑰），這意味著交換使用密碼加密的數據的雙方 A 和 B 需要具有相同的對稱密鑰，因此他們需要安全地共享此密鑰。
為了交換對稱密鑰，使用了非對稱加密。RSA 是非對稱加密系統的一個例子。大多數非對稱加密系統比對稱密碼慢得多，這主要是由於在計算中使用了大數字（如您所提到的）。
因此，為了交換一個用於加密大量數據的共享對稱密鑰，我們使用接收者的 RSA 公鑰對該密鑰進行加密。因為只有小密鑰（例如 256 位長）使用 RSA 加密，所以使用的時間非常短（例如 0.5-1 秒）。之後，大型對稱加密數據和小型非對稱（使用 RSA）加密密鑰被發送給接收者。在接收方則相反 - 首先使用 RSA 私鑰解密對稱密鑰，然後使用帶有塊或流密碼（如 AES）的對稱密鑰解密第二個大數據。
通常還會進行一些完整性檢查，例如通過使用 MAC（消息驗證碼） - MAC 在發送方計算並在接收方進行檢查。或者代替MAC，在發送方使用發送方的私鑰創建數字簽名（使案例如DSA，數字簽名算法），並在接收方使用發送方的公鑰進行驗證。MAC 是使用對稱算法（例如 AES、3DES）創建的完整性校驗值，而數字簽名是使用非對稱算法（例如 RSA 或 DSA）創建的。
要回答關於大數的問題 - 為了通過一些大模數任意長度的大數模擬來計算那些大指數，模擬是用具有數千位的數字完成的，即大約一千位十進制數字。我將舉一個例子，說明如何以一種非常快速的方式計算求冪，而不是簡單的乘法（這可能需要很長時間）。所有的乘法、加法、減法和除法都被模擬為記憶體中的一個巨大的數字算術，使用類似於我們在學校學習的算法，例如在紙上乘或除長數字。要進行快速取冪，請使用一種稱為平方取冪的技術用來。我們將計算 C = M^E (mod N) 的值。該算法與指數 E 中的位數成正比，即數 E 中的每個位執行幾個大數運算（大約兩次乘法和兩次除法），因此如果 E 是從 1024 到 2048 位（這些長度對於 RSA 來說很常見） ) 然後算法對大數進行大約 1024 到 2048 塊 2 到 4 算術運算。該算法有兩個主要版本，一個是從左到右迭代指數位（MSB-first（Most Significant Bit first）順序），另一個是從右到左迭代（LSB-first（Least Significant Bit first）順序）（引自此處）：
// LSB Binary Exponentiation Algorithm (scans exponent's E bits right to left) // Input: Exponent: E of k bits, message M // Output: Ciphertext: C = M^E (mod N) C =1 ; S = M; // Scan E's bits from LSB to MSB (right to left). for i := 0 to k-1 begin // Multiply by degree of M. if (E_i = 1) C = C * S (mod N); // Square degree of M. S = S * S (mod N); end; // MSB Binary Exponentiation Algorithm (scans exponent's E bits left to right) // Input: Exponent: E of k bits, message M // Output: Ciphertext: C = M^E (mod N) C = 1; // Scan E's bits from MSB to LSB (left to right). for i := k-1 downto 0 do begin // Square result. C = C * C (mod N); // Multiply by M if E's bit is set. if (E_i = 1) C = C * M (mod N); end;
用於 RSA 加密和解密的標準算法是平方求冪。
基本思想是以二進制形式寫出指數。例如，對於 $ d = 4267793 $ ,
$$ \begin{aligned} 4267793 &= 10000010001111100010001_2 \ &= 2^{22} + 2^{16} + 2^{12} + 2^{11} + 2^{10} + 2^9 + 2^8 + 2^4 + 2^0.\end{aligned} $$ 現在，給定一些 RSA 密文 $ c $ ，我們可以表示解密操作 $ m = c^d $ 作為
$$ \begin{aligned} c^{4267793} &= c^{2^{22} + 2^{16} + 2^{12} + 2^{11} + 2^{10} + 2^9 + 2^8 + 2^4 + 2^0} \ &= c^{2^{22}} c^{2^{16}} c^{2^{12}} c^{2^{11}} c^{2^{10}} c^{2^9} c^{2^8} c^{2^4} c^{2^0}.\end{aligned} $$ （這裡，所有的乘法和冪都取模 $ n $ ，當然，但我不想把它明確寫出來。）因此，我們只需要計算所有這些冪 $ c $ （模組 $ n $ ）並將它們相乘（再次取模 $ n $ ， 當然）。
我們如何做到這一點？好， $ c^{2^0} = c^1 = c $ ，當然，並且 $ c^{2^1} = c^2 = c^1 \cdot c^1 $ . 更進一步，我們有 $ c^{2^2} = c^4 = c^2 \cdot c^2 $ ， 和 $ c^{2^3} = c^8 = c^4 \cdot c^4 $ ， 等等。事實上，我們有以下通用公式：
$$ c^{2^{k+1}} = c^{2^k} \cdot c^{2^k}. $$ 因此，我們可以從 $ c^{2^0} = c $ 並反復平方它（模 $ n $ ) 獲得 $ c^{2^k} $ 對於任何 $ k $ .
計算 $ c^d = c^{4267793} $ ，我們需要這樣做（至少）22次，以獲得所有權力 $ c^{2^{22}} $ ，然後將它們相乘 $ c^{2^k} $ 為此 $ k $ - 第一點 $ d = 4267793 $ 是 $ 1 $ . 因此，總的來說，我們需要做 $ 2 \cdot 22 = 44 $ 模乘法（實際上更少；但見下文），比 $ 4267793 $ 我們需要天真的求冪的乘法。
有各種優化可以進一步減少所需的乘法次數；有關詳細資訊，請參見連結的 Wikipedia 文章。
**附言。**此方法的一個潛在安全問題是所需的乘法次數取決於私有指數 $ d $ . 在某些情況下，如果攻擊者可以監控解密（或簽名）所需的時間，這可能會將有關私有指數的資訊洩露給攻擊者。事實上，在某些情況下，攻擊者甚至可以監控進行解密的設備的功耗，這可能會洩露更多關於哪些特定位的資訊 $ d $ 被設置。
為了避免這種側通道攻擊，我們可以修改算法以始終執行相同數量的乘法運算，而不管 $ d $ . 一個這樣的變體是蒙哥馬利的梯子方法，它總是對每個位做兩次乘法（其中一個是平方） $ d $ .