對 Diffie-Hellman 的小型子群限制攻擊
我試圖了解對Diffie -Hellman算法的小型子群限制攻擊。我將介紹攻擊並嘗試解釋它為什麼有效。
對 Diffie-Hellman 算法的小子群限制攻擊
讓我們成為一個群體 $ \mathbb{Z}_p^* $ 在哪裡 $ p $ 是一個大素數並且 $ \alpha $ 原始根模 $ p $ . 讓我們考慮 Alice 和 Bob 想要對整個循環組做一個密鑰協議 $ \mathbb{Z}^*_p $ 使用 Diffie-Hellman 算法。以下序列圖說明了 Eve 如何執行小型子組限制攻擊：
通過這樣做，如果 $ k $ 選得好，秘訣 $ S $ 可以通過詳盡的搜尋找到。
如何選擇 $ k $ -價值
作為 $ p $ 是一個素數，階數為 $ \mathbb{Z}^*_p $ 是合集，所以存在子群。說 $ \mathbb{G}_w $ 是素數的一個小子群 $ w $ . 所以通過採摘 $ k = \frac{p-1}{w} $ , 秘密值 $ S \in \mathbb{G}_w $ 因為它是一個小的子群， $ S $ 可以通過窮舉搜尋有效地找到。
為什麼它有效？
在本節中，我將嘗試證明 $ S \in \mathbb{G}_w $ .
我們知道 $ w\text{ | } (p-1) $ 所以 $ \exists k $ 作為 $ p-1 = w \times k $ . 另外我們知道 $ ord(\alpha) = p - 1 $ 因為它是一個原始根模 $ p $ 並且柯西定理的一個結果是給定一個元素 $ x $ , $ ord(x^k) = \frac{ord(x)}{(ord(x) \wedge k)} $ . 所以在我們的例子中，我們有：
$ ord(\alpha^{ab(p-1)/w}) = ord(\alpha^{abk}) = \frac{ord(\alpha)}{(ord(\alpha) \wedge abk)} = \frac{(p-1)}{((p-1) \wedge abk)} = \frac{wk}{ (wk \wedge abk)} $ 我們知道 $ (wk \wedge abk) = k $ 因為 $ w $ 是一個素數。所以我們得到 $ ord(\alpha^{ab(p-1)/w}) = \frac{wk}{k} = w $ 所以我們可以得出結論 $ S \in \mathbb{G}_w $ .
有人可以批准或不批准我的展示嗎？
問題中提供的證明是正確的，但正如Chris Peikert在評論中指出的那樣，有一種更簡單的方法可以證明 $ S \in \mathbb{G}_w $ :
$ ord(\alpha^k) = \frac{ord(\alpha)}{ord(\alpha) \wedge k} = \frac{p - 1}{(p-1) \wedge k} = \frac{p - 1}{k} = w $ 所以這意味著 $ \alpha^k \in \mathbb{G}_w $ .
作為 $ A^k = (\alpha^a)^k = (\alpha^k)^a $ 是一種力量 $ \alpha^k $ ，這也意味著 $ A^k \in \mathbb{G}_w $ .
同樣的方式， $ S $ 是一種力量 $ A^k $ 所以 $ S \in \mathbb{G}_w $ .