Diffie-Hellman 在數學上與 RSA 相同嗎？
Diffie-Hellman 密鑰交換是否與 RSA 相同？
Diffie Hellman 允許在觀察到的線路上交換密鑰——但 RSA 也可以。
愛麗絲和鮑勃想交換一把鑰匙——老大哥在看著一切。
- Bob 製作了一個新的 RSA 密鑰對並將他的公鑰發送給 Alice。
- Alice 生成一個隨機會話密鑰並將其發送給使用 Bob 的公鑰加密的 Bob。
- Bob 用他的私鑰解密會話密鑰。
儘管任何人都可以觀察到所有流量，但 Alice 和 Bob 已經交換了一個密鑰。RSA 和 Hiffie Hellman 的數學非常相似，都涉及模冪運算。
他們都工作，因為 $ (A*B)^C \bmod N $ 可以分兩步完成，即通過計算 $ X = A^C \bmod N $ 在交易的一側，以及 $ X^B \bmod N $ 另一方面——這個技巧是 Hiffie Hellman 和 RSA 的基礎。這讓我想知道：它們真的是一回事嗎？
我們能否用代數證明 RSA 的正確性暗示了 Diffie-Hellman 的正確性？
RSA 和 Diffie-Hellman 都使用模冪運算。但它們以不同的方式工作：
在 RSA 中，有兩個相互取反的冪，即我們有 $ e $ 和 $ d $ 這樣 $ (x^e)^d \equiv x $ 對全部 $ x $ . 例如，如果 $ \square^e $ 是加密， $ \square^d $ 是對應的解密。打造這對 $ e $ 和 $ d $ （或從另一個派生），我們需要模數的素數分解 $ m $ （因此應該是私有的）。
在 Diffie-Hellman 中，兩個基礎 $ g $ 和模數 $ m $ 取冪是固定的。指數 $ x $ 和 $ y $ 是隨機選擇的私鑰，我們使用以下事實 $ (g^x)^y \equiv g^{x\cdot y} \equiv (g^y)^x $ ， 在哪裡 $ g^x $ 和 $ g^y $ 是公開的，而 $ x $ 和 $ y $ 是（並保持）私人的，並且 $ g^{x·y} $ 是共享的秘密。
要破解 RSA，我們必須得到 $ x $ 從 $ x^d $ , $ m $ 和 $ d $ - 這可以稱為離散 $ d $ -th 根問題。（最知名的方法是考慮因素 $ m $ 要得到 $ e $ …如果你有 $ e $ , 這也可以用來分解 $ m $ ).
要打破 Diffie-Hellman，我們必須得到 $ g^{x·y} $ 從 $ g^x $ , $ g^y $ , $ m $ 和 $ g $ . 最好的方法是得到 $ x $ 從 $ g^x $ 或者 $ y $ 從 $ g^y $ （和 $ m $ 和 $ g $ )，即所謂的離散對數問題。（順便說一句，沒有證明這確實是最好的方法，即沒有更快的方法來做到這一點。）
Diffie-Hellman 和 RSA 是不同的，並且不使用相同的“技巧”。
在 Diffie-Hellman 中，使用了交換律： $ (g^a)^b = (g^b)^a $ . Alice 和 Bob 都做兩個模冪運算（Alice 選擇 $ a $ , 計算 $ g^a $ 並將其發送給 Bob，接收 $ g^b $ 來自 Bob，最後計算 $ (g^b)^a $ ）。安全性依賴於離散對數的難度：給定一個素數 $ p $ , 一個整數 $ g $ ， 和 $ g^x \mod p $ , 實在是太難找了 $ x $ .
在 RSA 中，不涉及交換性；Alice 和 Bob 各只做一次模冪運算；計算不是以素數為模的 $ p $ , 但形成一個非素數 $ n $ . 愛麗絲隨機選擇 $ m $ , 計算 $ m^e \mod n $ 並將其發送給 Bob；Bob 計算 $ (m^e)^d \mod n $ 這等於 $ m $ 因為 $ d $ 和 $ e $ 已被選中為此工作。RSA依賴於提取的難度 $ e $ -th 根：給定 $ n $ , $ e $ 和 $ m^e \mod n $ , 實在是太難找了 $ m $ – 除非你知道“魔法陷阱”，即 $ d $ （或分解 $ n $ ）（如果 $ n $ 是素數，發現 $ m $ 會很容易）。
儘管這兩種算法都涉及模冪運算，但它們在工作方式、提供的內容以及依賴的難題方面有很大不同。注意區別：在離散對數中，您有 $ g $ 和 $ g^x $ , 並尋找 $ x $ ; 在 $ e $ -th 根，你有 $ m^e $ 和 $ e $ , 並尋找 $ m $ .
任何非對稱加密算法（例如 RSA）都可以用作密鑰交換算法，以您描述的方式（為了“交換”密鑰，Alice 選擇一個隨機 blob 並用 Bob 的公鑰對其進行加密）。SSL/TLS就是這樣做的。反之則不然：您不能將密鑰交換算法“單獨”轉換為非對稱加密算法（但您可以將交換的密鑰與對稱加密算法（如 AES）一起使用；同樣，SSL 在使用 Diffie-Hellman 時會這樣做） .