Public-Key
為什麼我不能通過暴力破解秘密指數來破壞 ElGamal 加密？
我正在 coursera 上開設一門密碼學課程，其中一個主題是 ElGamal 加密系統。我正在使用Wikipedia中定義的術語。
愛麗絲發布 $ g $ 和 $ g^x $ . 理論上攻擊者可以計算 $ g^i $ 對全部 $ i $ 從 0 到 $ n $ . 在某些時候，攻擊者將獲得公鑰的值 $ g^x $ . 不管數字多麼大 $ n $ 是，肯定它可能在計算上是可行的，試圖獲得價值 $ g^x $ 以這種方式，因此 $ x $ ，特別是如果預先計算是為了使用重複平方。
我確定我遺漏了一些明顯的東西 :-) 我猜這可能是組的大小 $ G $ 比我假設的要大得多。
為什麼上述方法不起作用？
為了確保 ElGamal 安全，“離散日誌問題”（即，給定 $ g $ 和 $ g^x $ ， 尋找 $ x $ ) 必須是棘手的。你給出了一個通用的方法來攻擊一個組的離散對數問題 $ n $ 類似的元素 $ n $ 步驟（我之所以這麼說是因為您的方法不是此類攻擊的最簡單版本；最簡單的方法確實需要 $ n $ 腳步）; 因此，為了確保 ElGamal 安全，子組的大小 $ n $ 必須足夠大。
如果對手的安全假設是他不可能執行 $ 2^{128} $ 計算，這立即意味著我們需要一個至少有 $ 2^{128} $ 元素左右。
這意味著，在實踐中，這種攻擊並不實用，因為（正如您所猜測的）我們將選擇對於攻擊來說太大的 ElGamal 組。
兩條評論：
- 當我談論組的大小時，實際上重要的是由生成的子組的大小 $ g $ ; 也就是說，不同值的數量 $ g^1, g^2, g^3, … $ . 當我們在一個以素數為模的乘法群中時，這個子群的大小可能比模數的大小要小得多。
- 事實證明，有更聰明的通用方法來解決離散對數問題；由於這些方式，事實證明，如果我們的假設是攻擊者不能做更多 $ 2^{128} $ 操作，子組的大小至少需要 $ 2^{256} $ 元素大。