Diffie 和 Hellman 在密碼學新方向中公鑰密碼系統屬性的確切含義是什麼

我對密碼學很陌生，沒有太多的數學知識。我正在研究密碼學，尤其是公鑰算法。我有一些公鑰算法的基本知識，所以我知道 RSA 算法是如何工作的。但是我在閱讀Diffie 和 Hellman 的密碼學新方向時發現了很多我不明白的東西。

在第三節。PUBLIC KEY CRYPTOGRAPHY 在論文中，他們定義了公鑰密碼系統的四個屬性，如下所示。

---

公鑰密碼系統是一對家族 {E K } K∈{K}和 {D K } K∈{K}表示可逆變換的算法，

E K : {M} → {M}

D K : {M} → {M}

在有限消息空間 {M} 上，使得

1. 對於每個 K ∈ {K}，E K是 D K的倒數，
2. 對於每個 K ∈ {K} 和 M ∈ {M}，算法 E K和 D K很容易計算，
3. 對於幾乎每一個 K ∈ {K}，每一個等價於 D K的容易計算的算法在計算上都不能從 E K推導出來，
4. 對於每個 K ∈ {K}，從 K計算逆對 E K和 D K是可行的。

---

我的理解如下。

1. E K是 apublic key並且 D K是 a private key，因此 E K是 D K的倒數。
2. E K和 D K易於計算，因此可以在多項式時間內計算。
3. D K從 E K推導在計算上應該是不可行的，因此不可能在多項式時間內從 E K （公鑰）推導出 D K （私鑰）。
4. 從 K計算 apublic key和 a對很容易。private key

這是我不明白的。

1. 是什麼K？據我了解，K就像p和q在RSA？因為我們首先選擇素數p，q然後我們選擇一個公鑰並從歐幾里得算法中派生出e相應的私鑰。d``e``(p-1)(q-1)
2. 為什麼在屬性 3 中，對於***“幾乎”***每個 K，從 E K推導出 D K在計算上是不可行的？的確切含義是什麼？可能有一個例外，從 E K推導出 D K是可行的？for 'almost' every K

嗯，你努力學習很好。但是，從原始的開創性論文中學習確實有一些您需要注意的問題。

一方面，有時原始作者沒有預料到後來的貢獻發現的一些問題（並且針對這些問題進行了調整）。

例如，現在認識到公鑰加密需要隨機化；也就是說，具有確定性函式通常並不安全 $ \text{Encrypt}(E_k, M) $ . 畢竟，如果對手獲得 $ \text{Encrypt}(E_k, M) $ 並且猜到了消息 $ M’ $ ，他可以判斷是否 $ M = M’ $ 通過計算 $ \text{Encrypt}(E_k, M’) $ （並查看是否與他看到的密文匹配）。正因為如此，我們總是使用隨機加密函式 $ \text{Encrypt}(E_k, M, r) $ （在哪裡 $ r $ 是一個隨機輸入），其屬性為 $ \text{Decrypt}(D_k, \text{Encrypt}(E_k, M, r)) = M $ , 對於（幾乎）所有 $ M, r $ （“幾乎”存在是因為我們發現了一些解密失敗機率很小的方法）。

感覺需要指出的另一件事（即使它與您的實際問題幾乎沒有關係）是簽名 - Diffie 和 Hellman 在陷門單向函式的上下文中提到簽名。事實證明，我們有多種不基於陷門單向功能的公鑰簽名方法。

順便說一句：我並不是批評 Diffie 或 Hellman 沒有預見到所有可能的問題——他們的工作確實具有開創性。但是，在擴展這項工作方面已經投入了很多心思。有些人發現了原本錯過的東西，這並不奇怪。

話雖如此，以下是您的問題的答案：

1. 是什麼K？據我了解，K就像p和q在RSA？因為我們首先選擇素數p，q然後我們選擇一個公鑰並從歐幾里得算法中派生出e相應的私鑰。d``e``(p-1)(q-1)

嗯，不。對於任何公鑰密碼系統，都有一個生成公鑰和私鑰的隨機過程。這個隨機過程可以建模為基於一些“種子”或“隨機硬幣翻轉”（更現代的術語實際上是“隨機硬幣”）。價值K就是這個種子。

Diffie 和 Hellman 在編寫時引用了這個過程：

    In practice, the cryptoequipment must contain a true random number generator
    (e.g., a noisy diode) for generating K, together with an algorithm for generating
    the EK ~- n, pair from its outputs. 

後來的工作讓密碼系統專門將此算法稱為“密鑰生成”（Gen）算法，作為定義密碼系統的算法之一，並假設真正的隨機數生成器輸出是在密碼系統之外生成的，作為顯式輸入Gen算法。

對於 RSA，我們通常做的是獲取這個種子K，並使用它來選擇隨機素數p和q（並且可能e；細節取決於所使用的確切算法）。p和q值實際上是私鑰的一部分，而不是原始種子。

2. 為什麼在屬性 3 中，對於***“幾乎”***每個 K，從 E K推導出 D K在計算上是不可行的？的確切含義是什麼？可能有一個例外，從 E K推導出 D K是可行的？for 'almost' every K

好吧，一個無法避免的問題是，如果攻擊者猜測原始種子值K'，然後將其輸入密鑰生成過程（這是公開的）。如果他的猜測是正確的，那將生成完全相同的公鑰值 $ E_k $ ，所以他知道他的猜測是正確的（他也會得到私鑰值 $ D_k $ ，讓他解密。這是無法避免的，因此他們需要對這種不可避免的攻擊（可能還有類似的攻擊）提出警告。實際上，對於大多數公鑰密碼系統（不會立即想到例外），有比僅僅猜測更好的攻擊K；但是這種攻擊仍然存在。

引用自：https://crypto.stackexchange.com/questions/81417