Elgamal 問題問_p問Rpmathbb{QR}_p和ppp安全的素數
我需要一些方向來解決以下問題：
讓 $ p = 2q+1 $ 是一個安全的素數和 $ s(x) $ 的兩個平方根中的最小者 $ x $ 模組 $ p $ . 然後：
- 確定分佈 $ s(g^{ab}) $ 為了 $ a,b $ 統一選擇在 $ \mathbb{Z}_q $ .
- 明確制定 Elgamal wrt $ \mathbb{QR}_p $ 以安全素數為模 $ p $ . 利用 $ s(x) $ 從上面為十二月。
- 讓 $ G = \langle g \rangle $ 是任意一組素數 $ q $ . 確定分佈 $ g^{ab} $ 為了 $ a,b $ 均勻分佈在 $ \mathbb{Z}_q $ .
我的解決方案
1）看來我得研究一下分佈 $ ab ; mod ; q = c $ . 因為映射 $ s^{-1}: {1,\ldots,\frac{p-1}{2}} \to \mathbb{QR}_p $ 是一對一且有效可逆的。自從 $ g $ 可以假設為生成器 $ \mathbb{QR}_p $ 那麼研究指數就足夠了（每個指數將完全對應於一個“最小”平方根。
現在，考慮到可能 $ q^2 $ 對。有 $ q+(q-1) $ 對產生零。為了 $ c \neq 0 $ , 可以修復 $ a $ 並立即解決 $ b $ 產生 $ q-1 $ 的可能性 $ c $ . 加起來，我們有 $ 2q-1+(q-1)^2 = q^2 $ 正如預期的那樣。
所以分佈是 $ P[s(g^{ab}) = i] = \frac{q-1}{q^2} $ 如果 $ i \neq 1 $ 和 $ \frac{2q-1}{q^2} $ 如果 $ i = 1 $ .
- 我目前不知道如何服用 $ s $ 在這裡玩。
3）我相信推理等於第1點）。
$ P[s(g^{ab}) = i] = \frac{q-1}{q^2} $ 如果 $ i \neq 1 $ 和 $ \frac{2q-1}{q^2} $ 如果 $ i = 1 $ .
我們假設 $ g $ 是一個生成器 $ \mathbb{QR}_p = \mathbb Z_q $ . 然後，正如你所說，為了研究機率 $ g^{ab} = i = g^c $ 對於一個固定的 $ c $ ，我們可以計算出機率 $ ab = c\bmod q $ .
一般來說，隨機對的機率 $ (a,b)\in\mathbb Z_q\times\mathbb Z_q $ 給你一個固定的非零數 $ c $ 是 $ (q-1)/q^2 $ ， 而如果 $ c=0 $ 那麼這個機率是 $ (2q-1)/q^2 $ .
- 我目前不知道如何服用 $ s $ 在這裡玩。
ElGamal 加密方案允許您加密元素 $ m\in\mathbb{QR}_p $ 作為 $ m\cdot g^{ab} $ . 但是，您要加密的消息可能不是該集合的元素。在實踐中，您加密位串，這更容易映射到 $ {1,\ldots,(p-1)/2} $ . 然後你取一個元素 $ y $ 在這個區間並將其映射到 $ m\in\mathbb{QR}_p $ 通過 $ m = y^2 $ , 並使用 $ m $ 如上。現在你可以看到你需要 $ s $ 用於解密以恢復 $ y $ 從 $ m $ .
3）我相信推理等於第1點）。
同意。這個想法是，有一個安全的素數 $ p = 2q+1 $ 你知道的 $ \mathbb{QR}_p = \mathbb{Z}_q $ ，而一般來說，這種結構可能會涉及更多。然而，一旦你工作結束 $ \mathbb{Z}_q $ ，分析是一樣的。