破解兩個不同消息的 ElGammal 加密
我在 ElGammal 加密上遇到了以下問題。
我們致力於 $ \mathbb{Z}{p}^* $ 在哪裡 $ p $ 是素數，我們得到 $ p $ , 生成器 $ g $ 的 $ \mathbb{Z}{p}^* $ , 使用的公鑰 $ y $ 和五種加密 $ (u_1,v_1), \cdots, (u_5,v_5) $ 其中每個都是消息的加密 $ m $ 那可以是 $ 1 $ 或者 $ -1 $ .
如果您需要有關我正在使用的 ElGammal 密碼系統的更多詳細資訊，請參閱此問題的第二個方案。
作為提示，我被告知要尋找索引二的子組。我試圖用 sage 解決該子組中的離散對數問題，但正如這篇文章所討論的那樣，複雜性僅減少了一個常數，因此它仍然難以處理。
我給你我正在使用的程式碼，以防你有一些意見。
F = Integers(p) gmod = F(g) q = p // 2 F2 = Integers(q) gmod2 = F2(g) ymod2 = F2(y) gmod2 = F2(g) ymod2 = F2(y)你能弄清楚如何解決這個問題嗎？
編輯：
就我而言 $ \frac{p-1}{2} $ 已經是素數了。
感謝雨披的提示，我們可以如下工作：
1.計算 $ (g^r)^q $ . 我聲稱：
$ (g^r)^q = \begin{cases} 1 &\quad\text{if r is even}\ \neq 1 &\quad\text{if r is odd}
\end{cases} $對於第一種情況，我們有 $ (g^{r})^{\frac{p-1}{2}} = (g^{p-1})^{\frac{r}{2}} = 1 $ . 對於第二種情況，結果是一個 $ ord(g) = p-1 $ 劃分 $ r \frac{p-1}{2} $ . 然而， $ p-1 $ 是偶數，我們假設 $ r $ 和 $ \frac{p-1}{2} $ 是奇數。偶數不能整除奇數。
2.計算 $ (my^r)^q = m^q y^{rq} = m y^{rq} $ 我們用的地方 $ m \in {-1,1} $ .
3.計算 $ y^{rq} $ . 我聲稱（假設 x 是算法的私鑰）：
$ y^{rq} = \begin{cases} 1 &\quad\text{if (r is even) or (r is odd and x is even)}\ -1 &\quad\text{if r is odd and x is odd}
\end{cases} $如果 r 是偶數，我們可以像第一種情況那樣進行推理。假設 r 是奇數。然後 $ (y^{rq})^2 = y^{2rq} = 1 $ 並作為 $ \mathbb{Z}_p $ 是一個域，我們知道這個方程最多有 2 個解，即 -1 和 1。
如果假設 $ y^{rq} = 1 $ 然後根據定義 $ y $ 我們得到 $ y^{rq} = g^{xrq} = 1 $ 以便 $ ord(g) = p-1 $ 劃分 $ xr \frac{p-1}{2} $ . 這裡 $ r $ 和 $ \frac{p-1}{2} $ 是奇數（在我的編輯中我指定了 $ \frac{p-1}{2} $ 是素數）所以必然 $ x $ 必須是均勻的。因此，如果我們現在假設 $ y^{rq} = g^{xrq} = -1 $ , $ x $ 需要奇怪。
4.計算 $ y^q = g^{xq} $ 這樣在第一種情況下你會得到：
$ g^{xq} = \begin{cases} 1 &\quad\text{if x is even}\ \neq 1 &\quad\text{if x is odd}
\end{cases} $讓我們結束吧。我們可以決定是否 $ x,r $ 是奇數還是偶數。這意味著我們可以決定是否 $ y^{rq} $ 是 1 或 -1，這意味著我們可以決定是否 $ (my^r)^q $ 是 m 或 -m。
進一步提示：假設我們計算了 $ q = (p-1)/2^\lambda $ 奇怪的，給定的 $ (u_1, v_1) = (g^r, m y^r) $ , 我們計算 $ (g^r)^q, (m y^r)^q $ . 一旦我們這樣做了，您如何區分 $ m=1 $ 和 $ m= -1 $ 案例？