Diffie-Hellman 什麼是子群
我正在嘗試了解有關 Diffie-Hellman 中使用的變數的安全預防措施，並且我被引用了這篇文章答案Diffie-Hellman 中的生成器大小是否重要？.
更詳細地說：對於 DH，我們使用整數模 p（一個大素數）的大小為 q 的子群，並將乘法作為群操作。對於 2n 安全級別，q 應該是長度至少為 2n 位的素數（或者，至少 q 應該具有至少 2n 位的素數除數）。典型的參數大小是 q 為 160 位，p 為 1024 位，或者 q 為 256 位，p 為 2048 位。生成器 g 是 q 階元素。
for DH, we use a subgroup of size q of the integers modulo p我假設該組的含義是 $ \mod p $ ，但什麼是子群。由於生成器應該是的原始根，p這並不意味著該組是 $ [1,p-1] $ ? 這讓我相信 $ q = p-1 $ .q然而，當考慮到以下句子應該是一個安全級別的長度至少2n為比特的素數時，這是沒有意義的2n（或者，至少q應該有一個至少為2n比特的素數除數）。我不確定這個n變數代表什麼？
由於生成器應該是
p好吧，這是您的誤解；發電機 $ g $ 不需要生成整個組 $ \mathbb{Z}^*_p $ ; 相反，它可以生成一個適當的子組（在大多數情況下，我們選擇這樣的子組）。
問題來了，如果 $ h $ 是由生成的組大小的一個因素 $ g $ ，然後給定 $ g^x \bmod p $ ，我們可以計算 $ h \bmod n $ 在 $ O(\sqrt h) $ 時間。如果 $ g $ 生成整個組，好吧，它的大小將是 $ p-1 $ ，它總是有一個因子 2（假設 $ p>2 $ )，所以我們會放棄 $ x \bmod 2 $ 免費。
相反，如果子群的大小是一個大素數（這意味著它不是整個群），那麼上述觀察不會給攻擊者任何優勢；子組大小的唯一因素是 1（它不會告訴攻擊者任何事情）和大子組大小本身（太大而無法 $ O(\sqrt{h}) $ 時間可行。