公鑰加密

上一個

下一個

公鑰加密

與對稱金鑰加密不同，我們沒有發現公鑰加密的歷史應用。這是一個相對較新的概念。

對稱加密非常適合政府、軍事和大型金融公司等組織，這些組織參與了機密通訊。

在過去幾十年中，隨著越來越多的不安全的計算機網路的普及，人們真正感受到了大規模使用加密的需求。由於對稱金鑰在金鑰管理方面面臨的挑戰，發現它不切實際。這催生了公鑰密碼系統。

加密和解密的過程在下面的插圖中描述：

公鑰加密方案最重要的屬性是：

加密和解密使用不同的金鑰。這是使該方案與對稱加密方案不同的屬性。
每個接收者都擁有一個唯一的解密金鑰，通常稱為其私鑰。
接收者需要釋出一個加密金鑰，稱為其公鑰。
此方案需要確保公鑰的真實性，以避免對手冒充接收者。通常，這種型別的密碼系統涉及可信的第三方，該第三方證明特定的公鑰僅屬於特定的人或實體。
加密演算法足夠複雜，可以禁止攻擊者根據密文和加密（公鑰）推斷明文。
儘管私鑰和公鑰在數學上相關，但從公鑰計算私鑰是不可行的。事實上，任何公鑰密碼系統中的智慧部分都在於設計兩個金鑰之間的關係。

公鑰加密方案有三種類型。我們在以下部分討論它們：

RSA 密碼系統

該密碼系統是最初的系統之一。即使在今天，它仍然是最常用的密碼系統。該系統由三位學者羅恩·萊維斯特、阿迪·薩莫爾和倫納德·阿德曼發明，因此被稱為 RSA 密碼系統。

我們將看到 RSA 密碼系統的兩個方面，首先是金鑰對的生成，其次是加密解密演算法。

RSA 金鑰對的生成

每個希望使用加密參與通訊的人或一方都需要生成一對金鑰，即公鑰和私鑰。金鑰生成過程中遵循的過程如下所述：

生成 RSA 模數 (n)
- 選擇兩個大素數 p 和 q。
- 計算 n=p*q。對於強大的不可破解加密，讓 n 為一個大數，通常至少為 512 位。
查詢匯出數字 (e)
- 數字e必須大於 1 且小於 (p − 1)(q − 1)。
- e 和 (p − 1)(q − 1) 之間除了 1 之外沒有公因子。換句話說，兩個數字 e 和 (p – 1)(q – 1) 是互質的。
形成公鑰
- 數字對 (n, e) 形成 RSA 公鑰，並公開。
- 有趣的是，雖然 n 是公鑰的一部分，但難以對大素數進行因式分解確保攻擊者無法在有限時間內找到用於獲得 n 的兩個素數 (p & q)。這是 RSA 的優勢。
生成私鑰
- 私鑰 d 由 p、q 和 e 計算得出。對於給定的 n 和 e，存在唯一的數字 d。
- 數字 d 是 e 模 (p - 1)(q – 1) 的逆。這意味著 d 是小於 (p - 1)(q - 1) 的數字，當乘以 e 時，它等於 1 模 (p - 1)(q - 1)。
- 這種關係用數學表示如下：

ed = 1 mod (p − 1)(q − 1)

擴充套件歐幾里得演算法以 p、q 和 e 作為輸入，並以 d 作為輸出。

示例

下面給出了生成 RSA 金鑰對的示例。（為了便於理解，這裡取的素數 p & q 是小值。實際上，這些值非常高）。

令兩個素數為 p = 7 和 q = 13。因此，模數 n = pq = 7 x 13 = 91。
選擇 e = 5，這是一個有效的選擇，因為除了 1 之外，5 和 (p − 1)(q − 1) = 6 × 12 = 72 沒有公因子。
數字對 (n, e) = (91, 5) 形成公鑰，可以提供給任何我們希望能夠向我們傳送加密訊息的人。
將 p = 7、q = 13 和 e = 5 輸入擴充套件歐幾里得演算法。輸出將為 d = 29。
透過計算檢查計算出的 d 是否正確：

de = 29 × 5 = 145 = 1 mod 72

因此，公鑰為 (91, 5)，私鑰為 (91, 29)。

加密和解密

金鑰對生成後，加密和解密過程相對簡單且計算量少。

有趣的是，RSA 不像對稱金鑰加密那樣直接對位串進行操作。它對模 n 的數字進行操作。因此，有必要將明文表示為一系列小於 n 的數字。

RSA 加密

假設傳送方希望向某個人的公鑰為 (n, e) 的人傳送一些文字訊息。
然後，傳送方將明文表示為一系列小於 n 的數字。
要加密第一個明文 P，它是模 n 的一個數字。加密過程是一個簡單的數學步驟，如下所示：

C = P^e mod n

換句話說，密文 C 等於明文 P 自乘 e 次，然後模 n。這意味著 C 也是小於 n 的數字。
回到我們的金鑰生成示例，明文 P = 10，我們得到密文 C：

C = 10⁵ mod 91

RSA 解密

RSA 的解密過程也非常簡單。假設公鑰對 (n, e) 的接收者已收到密文 C。
接收者將 C 提升到其私鑰 d 的冪。模 n 的結果將是明文 P。

Plaintext = C^d mod n

再次回到我們的數值示例，密文 C = 82 將使用私鑰 29 解密為數字 10：

Plaintext = 82²⁹ mod 91 = 10

RSA 分析

RSA 的安全性取決於兩個獨立函式的強度。RSA 密碼系統是最流行的公鑰密碼系統，其強度基於對非常大的數字進行因式分解的實際困難。

加密函式 - 它被認為是一個將明文轉換為密文的單向函式，只有知道私鑰d才能將其逆轉。
金鑰生成 - 從RSA公鑰確定私鑰的難度等同於對模數n進行因式分解。因此，攻擊者無法利用RSA公鑰的知識來確定RSA私鑰，除非他能對n進行因式分解。它也是一個單向函式，從p和q值到模數n很容易，但反過來就不可能了。

如果這兩個函式中的任何一個被證明不是單向的，那麼RSA就會被破解。事實上，如果開發出一種有效的因式分解技術，那麼RSA將不再安全。

如果數字p和q不是大素數，和/或選擇的公鑰e是一個小數字，那麼RSA加密的強度會大幅下降，容易受到攻擊。

ElGamal密碼系統

除了RSA之外，還有其他提出的公鑰密碼系統。它們中的許多都基於離散對數問題的不同版本。

ElGamal密碼系統，稱為橢圓曲線變體，基於離散對數問題。它的強度源於這樣一個假設，即對於給定的數字，在實際時間範圍內無法找到離散對數，而冪運算的反運算可以有效地計算。

讓我們來看一下ElGamal的一個簡單版本，它使用模p的數字。在橢圓曲線變體的情況下，它是基於完全不同的數字系統。

ElGamal金鑰對生成

ElGamal密碼系統的每個使用者都透過以下方式生成金鑰對：

選擇一個大素數p。通常選擇一個長度為1024到2048位的素數。
選擇一個生成元g。
- 這個數字必須在1和p-1之間，但不能是任意數字。
- 它是模p整數乘法群的生成元。這意味著對於每個與p互質的整數m，都存在一個整數k，使得g^k=a mod n。
  
  例如，3是群5（Z₅ = {1, 2, 3, 4}）的生成元。

N	3ⁿ	3ⁿ mod 5
1	3	3
2	9	4
3	27	2
4	81	1

選擇私鑰。私鑰x是任何大於1且小於p-1的數字。
計算公鑰的一部分。值y根據引數p、g和私鑰x計算如下：

y = g^x mod p

獲取公鑰。ElGamal公鑰由三個引數（p、g、y）組成。

例如，假設p = 17且g = 6（可以確認6是群Z₁₇的生成元）。私鑰x可以是大於1且小於71的任何數字，因此我們選擇x = 5。然後計算值y如下：

y = 6⁵ mod 17 = 7

因此私鑰是62，公鑰是（17，6，7）。

加密和解密

與RSA等效的過程相比，ElGamal金鑰對的生成相對簡單。但加密和解密比RSA稍微複雜一些。

ElGamal加密

假設傳送方希望將明文傳送給某人，其ElGamal公鑰為（p、g、y），則：

傳送方將明文表示為一系列模p的數字。
要加密表示為模p數字的第一個明文P。獲取密文C的加密過程如下：
- 隨機生成一個數字k；
- 計算兩個值C1和C2，其中：

C1 = g^k mod p
C2 = (P^*y^k) mod p

將密文C傳送，密文C由兩個單獨的值（C1，C2）組成，一起傳送。
參考上面給出的ElGamal金鑰生成示例，明文P = 13加密如下：
- 隨機生成一個數字，比如k = 10
- 計算兩個值C1和C2，其中：

C1 = 6¹⁰ mod 17
C2 = (13^*7¹⁰) mod 17 = 9

傳送密文C = (C1，C2) = (15，9)。

ElGamal解密

要使用私鑰x解密密文（C1，C2），需要執行以下兩個步驟：
- 計算(C1)^x模p的模逆，即(C1)^-x，通常稱為解密因子。
- 使用以下公式獲取明文：

C2 × (C1)^-x mod p = Plaintext

在我們的示例中，要使用私鑰x = 5解密密文C = (C1，C2) = (15，9)，解密因子為

15^-5 mod 17 = 9

提取明文P = (9 × 9) mod 17 = 13。

ElGamal分析

在ElGamal系統中，每個使用者都有一個私鑰x，並且有三個組成部分的公鑰：素模p、生成元g和公鑰Y = g^x mod p。ElGamal的強度基於離散對數問題的難度。

安全金鑰大小通常> 1024位。如今甚至使用2048位長的金鑰。在處理速度方面，Elgamal相當慢，它主要用於金鑰認證協議。由於更高的處理效率，ElGamal的橢圓曲線變體正變得越來越受歡迎。

橢圓曲線密碼學（ECC）

橢圓曲線密碼學（ECC）是一個術語，用於描述一套密碼工具和協議，其安全性基於離散對數問題的特殊版本。它不使用模p的數字。

ECC基於與稱為橢圓曲線的數學物件相關聯的一組數字。這些數字有加法和計算倍數的規則，就像模p的數字一樣。

ECC包含許多最初為模數設計的密碼方案的變體，例如ElGamal加密和數字簽名演算法。

人們認為，當應用於橢圓曲線上的點時，離散對數問題要困難得多。這促使我們從模p的數字切換到橢圓曲線上的點。此外，如果我們使用基於橢圓曲線的變體，則可以使用更短的金鑰獲得等效的安全級別。

更短的金鑰帶來兩個好處：

金鑰管理簡便
計算效率高

這些優勢使基於橢圓曲線的加密方案變體對於計算資源受限的應用極具吸引力。

RSA和ElGamal方案 - 對比

讓我們簡要比較一下RSA和ElGamal方案在各個方面的差異。

RSA	ElGamal
它在加密方面效率更高。	它在解密方面效率更高。
它在解密方面效率較低。	它在解密方面效率更高。
對於特定的安全級別，RSA需要較長的金鑰。	對於相同的安全級別，需要非常短的金鑰。
它被廣泛接受和使用。	它比較新，在市場上並不流行。

列印頁面