是什麼激發了 RSA 和 ECDH 的創建？
最近我一直在學習密碼學，到目前為止我很喜歡它。但是，有些事情我不明白。
據我所知，RSA 於 1979 年出版，而Diffie 和 Hellman 的*《密碼學新方向*》於 1976 年出版。我想知道的是，是什麼推動了 RSA 的誕生？是因為他們想創造比 Diffie-Hellman 更安全的東西嗎？如果是這樣，為什麼它更安全？還是因為它是為其他目的而設計的，而 Diffie-Hellman 無法實現？
另一方面，直到 1985 年，Neal Koblitz 才提出基於橢圓曲線的密碼學。有人告訴我，橢圓曲線比經典的 Diffie-Hellman 提供更多的安全性，但我想了解並知道如何做。我對安全級別了解不多。我見過像*“ $ n $ -bit 鍵給出 $ m $ -bit security”*，但我不完全理解它們的含義。我看到 ECDH 提供比 DH 更多的位安全性，但是如果兩者的攻擊不同，如何衡量呢？
謝謝！不要擔心拋出一些數學問題，我可能會理解。
我想知道的是，是什麼激發了 RSA 的創建？是因為他們想創造比 Diffie-Hellman 更安全的東西嗎？如果是這樣，為什麼它更安全？
The New Directions In Cryptography論文介紹了公鑰密碼學的思想（雖然它之前由 Merkle 提出），公鑰密碼學旨在解決兩個主要問題：密鑰分配問題和身份驗證問題，即現在稱為“數字簽名”。
除了打開一個全新的研究領域的普遍興奮之外，RSA 的動機之一是定義一個原語來解決密鑰分發（或公鑰加密）以及數字簽名的*問題。*這實際上很容易從原始 RSA 論文的標題中看出：“一種獲取數字簽名和公鑰密碼系統的方法”。
他們的論文明確指出了這一點（強調我的）：
…這種方法提供了“公鑰密碼系統”的實現，這是 Diffie 和 Hellman 發明的一個優雅的概念。他們的文章激發了我們的研究，因為他們提出了這個概念，但沒有提出這種系統的任何實際實現。
是因為他們想創造比 Diffie-Hellman 更安全的東西嗎？如果是這樣，為什麼它更安全？
如您所見，這個問題的答案是“否”——總的來說，這只是完成壯舉的問題。在您至少擁有該概念的工作範例之後，才會出現給定數量的安全性與給定數量的效率的問題。
還是因為它是為其他目的而設計的，而 Diffie-Hellman 無法實現？
如前面的引文所示，是的。不過，世界後來會開發出允許公鑰加密和數字簽名 而不需要陷門函式/排列的技術。
至於你問題的第二部分，這個其他答案試圖詳細說明。
但基本上，Diffie-Hellman 對任何有限循環群都有效（因為保證了正確性）（實際上只需要一個半群，因為不使用逆和恆等式）。無論您使用的實際組如何，都存在適用的通用攻擊，但對於給定的組，可能存在比通用攻擊更有效的攻擊。在有限域 Diffie-Hellman（例如經典或“正常”Diffie-Hellman）中，存在不適用或不知道在橢圓曲線設置中具有等價物的非泛型攻擊。
可悲的是，我也想知道您的第一個問題的答案。
對於第二個問題，您只需要查看協議描述與其實際實例化（即加密方案）之間的區別。Diffie-Hellman 是一種密碼協議，描述了一種雙方在固定環境阿貝爾有限群中交換公共元素的方式 $ G $ , 有基數 $ p $ （通常是素數）。然後，DH 的安全性將本質上定義為您可以執行的組中破壞協議的最小操作量。暴力破解是最自然的方法：列舉所有可能的解決方案，您會找到正確的解決方案。在最壞的情況下，您將需要列舉所有 $ p $ 元素。這些傢伙由大小的二進製字元串表示 $ \log p $ ，所以電腦將採取 $ p = 2^{\log p} $ 操作，輸入大小的指數數。如果我們不能做得更好，那麼這個協議是“安全的”並且給你 $ \log p $ 一點安全感。拿 $ p \approx 2^{128} $ 而且你有一個 128 位的安全密鑰交換……也就是說，如果你不能比蠻力做得更好的話。
假設您沒有關於該組的任何資訊 $ G $ 除了計算它的群體法則和測試平等（這是一種非正式的說法，你認為你的群體是一個通用群體）。如果您不是兩方之一，那麼恢復共享元素的最佳方法是解決離散對數問題 $ G $ ：給定 $ g $ 發電機，和 $ h = g^x $ , 計算 $ x $ . 我希望不要被那些注意到 DLP 和 ECDH 不完全相同的問題的人活活燒死，但為了便於討論，假設它們是。
眾所周知（Shoup 或 Nechaev 的定理，如果你能讀懂俄語）你將需要（至少） $ \Omega(\sqrt p) $ 分組運算來計算 $ x $ . 事實上，有一些眾所周知的算法執行在 $ O(\sqrt{p}) $ 這樣做：Big-step-Giant-steps，或 $ \rho $ -Pollard 風格的隨機漫步。因此，這些算法在通用組“模型”中是最優的，您可以看到它們需要組元素大小的指數時間。要實現 128 位的安全性，您需要一個 $ 256 $ 位素數。
現在在現實生活中，您將實例化 $ G $ 到一些實際的群體。例如，您可以選擇 $ (\mathbb Z/p\mathbb Z, +) $ . 然而，這裡的 DLP 解決起來很簡單：它本質上是擴展的 Euclid 算法，執行於 $ O(\log^2 p) $ ：這是組元素大小的二次方，因此您絕對不會對此進行加密：您的素數需要非常大才能保證 128 位的安全性（然後所有輸入都將具有此素數的大小） .
但是您也可以選擇在素數域上定義的橢圓曲線的有理點組：這通常定義為 ECDH。在後一組中，在目前最先進的技術中，我們不知道比我在通用模型中給你的算法更好的算法（除了現在不相關的非常特殊的情況，因為它們可以很容易地避免） . 換句話說，解決 ECDH 的最著名算法是在指數時間內執行的。因此，與 DH 相比 $ \mathbb Z/p\mathbb Z $ ，它“提供了更多的安全性”，但請注意，這與組相關，而不是協議本身。
還有其他可能的實例化。有限域的可逆，擴展域上的橢圓曲線，更複雜的代數群。橢圓曲線很好地結合了效率和安全性。