在 Paillier 密碼系統中選擇素數
- 在此處給出的 Paillier 密碼系統中密鑰生成階段的第一步。
這是給定的
$$ \operatorname{length}(p) = \operatorname{length}(q) ) \implies \operatorname{gcd}(pq,(p-1)(q-1))=1 $$ 在哪裡
$ \operatorname{length}(k) $ = # 二進製表示的位 $ k $
$ \operatorname{gcd}(a,b) $ = 的最大公約數 $ a,b $
如何證明上述方程，或者它在哪裡被證明？ 2. 在密鑰生成的第三步中，我們要選擇一個隨機整數 $ g $ 在哪裡 $ g \in \mathbb{Z}_{n^2}^* $ 在加密的第 2 步中，我們必須選擇一個隨機整數 $ r $ 在哪裡 $ r \in \mathbb{Z}_n^* $ .
我想知道的是“已知的有效選擇方法是什麼？ $ g,r $ 隨機”。我的意思是我們是否必須辦理登機手續 $ \mathbb{Z}_{n^2}^,\mathbb{Z}_n^ $ 對於這樣 $ g,r $ 直到 $ \operatorname{gcd}(g,n^2)=1 $ 和 $ \operatorname{gcd}(r,n)=1 $ 或者在編碼密碼系統時有什麼簡單的方法。 3. 在加密的第一步，給定明文 $ m\in \mathbb{Z}_n $ .
所以 $ m < n $ .
假設我們要加密 $ k $ 位消息，所以我們的 $ n $ 一定是 $ l $ - 位數，其中 $ l>k $ .
我們知道兩者的乘積 $ s $ -bit numbers 給出一個數字，其位數介於 $ s+1 $ 到 2 $ s $ , 假設我們取等長素數來保證性質 $ \operatorname{gcd}(pq,(p-1)(q-1))=1 $ , 那麼有必要取 $ k $ 位素數，因為 $ m<n $ .
它是否正確？
- 自從 $ p $ 和 $ q $ 是素數，您需要排除的唯一因素是這兩個數字。
認為 $ p $ 劃分 $ (p-1)(q-1) $ . 然後它劃分要麼 $ p-1 $ （顯然不是真的）或 $ q-1 $ . 後者的意思 $ q-1 = p \cdot x $ ， 對於一些 $ x \ge 2 $ （如果 $ x = 1 $ 任何一個 $ p $ 或者 $ q $ 是偶數，只有當數字是 2 和 3 時才有可能）。然而，那麼 $ q \ge 2p+1 $ ，所以它的二進製表示更長。
類似的論證證明 $ q $ 不能成為一個因素。因此，GCD 必須是 $ 1 $ . 2. 如果你只是隨機選擇 $ g $ 模組 $ n^2 $ 它是一個好的選擇的可能性很高（對於大素數），因此您通常只需驗證一次。但是，就像您的 Wikipedia 連結狀態一樣，您可以選擇 $ g=n+1 $ （當你的素數一樣長時）。
為了 $ r $ 您也可能會隨機獲得一個好數字，但您必須檢查兩者都不是 $ p $ 也不 $ q $ 劃分它。 3. >
我們知道兩者的乘積 $ s $ -bit numbers 給出一個數字，其位數介於 $ s+1 $ 到 2 $ s $ , 假設我們取等長素數來保證性質 $ \operatorname{gcd}(pq,(p-1)(q-1))=1 $ , 那麼有必要取 $ k $ 位素數，因為 $ m<n $ .
如果你乘以兩個 $ s $ -位數字產品總是要麼 $ 2s-1 $ - 位數或 $ 2s $ -位號。（這裡一個 $ s $ - 位號表示一個有它的 $ s $ 位設置。）
允許任何 $ k $ -bit 消息，有必要 $ 2s-1>k $ ， 所以 $ s=k/2+1 $ 足夠。