求解由 2 個安全素數的乘積形成的群的離散對數問題的複雜度

求解離散對數問題的複雜度取決於組的選擇 $ G $ . 一個流行的選擇是 $ Z_p^* $ 在哪裡 $ p $ 是一個安全素數（ $ {p=2p’ +1} $ 和 $ p’ $ 也是素數）。在這種情況下， $ G $ 是一組素數，因此其中的每個元素都是一個生成器。我們可以這樣做：

1. 挑選 $ {g} $ 作為一個隨機元素 $ Z_p^* $
2. 隨機選擇 $ x $
3. 評估 $ {y = g^x : mod : p} $

現在我們可以假設解決 $ x = {log_g(y)} $ 如果很難 $ p $ 足夠大。

不過我經常看到群 $ G $ 被選為 $ Z_N^* $ 在哪裡 $ N=pq $ 和兩者 $ p $ 和 $ q $ 是安全素數。算法如下：

1. 挑選 $ g $ 作為一個隨機元素 $ Z_N^* $
2. 挑選 $ x $ 作為一個隨機元素 $ (0, N’) $ 在哪裡 $ {N’ = p’ q’} $ 在哪裡 $ {p=2p’ + 1} $ 和 $ {q=2q’ + 1} $
3. 評估 $ {y = g^x : mod : N} $

這種結構用於 MacKenzie 和 Fujisaki&Okamoto 的各種出版物中。

那是什麼組？做 $ Z_N^* $ 保證計算離散對數很難？自從 $ {Z_N^*} $ 不是一組素數，有沒有保證 $ g $ 是發電機？

那是什麼組？

代數上，它同構於群 $ \mathbb{Z}{p-1} \times \mathbb{Z}{q-1} = \mathbb{Z}{p’} \times \mathbb{Z}{q’} \times \mathbb{Z}_2 \times \mathbb{Z}_2 $ .

做 $ \mathbb{Z}_N^* $ 保證計算離散對數很難？

可以證明它至少和因式分解一樣難 $ N $ （就好像你可以計算離散對數一樣，你可以考慮）。

因此，如果因式分解 $ N $ 是不可行的，計算離散對數也是不可行的。

自從 $ \mathbb{Z}_N^* $ 不是一組素數，有沒有保證 $ g $ 是一個發電機。

其實有保證 $ g $ 不是整個組的生成器；那是因為 $ \mathbb{Z}_N^* $ 不是循環群，因此沒有生成器。

特別是，由單個值生成的子組 $ g $ 永遠不會同時包含這兩個元素 $ a $ 和 $ b $ 在哪裡：

• $ a \bmod p $ 是二次殘差 $ \bmod p $ ， 和 $ a \bmod q $ 是二次非殘差 $ \bmod q $
• $ b \bmod p $ 是二次非殘差 $ \bmod p $ ， 和 $ b \bmod q $ 是二次殘差 $ \bmod q $

（這樣的元素 $ a $ 和 $ b $ 將永遠存在於 $ \mathbb{Z}_N^* $ )

引用自：https://crypto.stackexchange.com/questions/61736