尋找aaa和kkk對於給定的 el gamal 密碼系統

我收到了這個問題：

假設 Alice 使用帶參數的 ElGamal 簽名方案

$ p = 31847 $ , $ \alpha = 5 $ ， 和 $ \beta = 25703 $

假設我們已經收到簽名消息

$ (x_1,(\gamma_1,\space \delta_1)) = (8990, (23972,\space 31396)) $

和

$ (x_2,(\gamma_2,\space \delta_2)) = (31415,(23972,\space 20481)) $

確定整數 $ k $ 和 $ a $ 愛麗絲在沒有解決任何離散對數問題實例的情況下使用了它。

我還從我的演講幻燈片中知道以下等式是正確的

1. $ \beta = a^\alpha \bmod p $
2. $ \gamma = a^k \bmod p $
3. $ a\gamma + k\delta = x \bmod p-1 $

由於問題指定不使用離散對數問題，我們只能使用等式 3

所以我們有一個由兩個方程組成的系統：

1. $ a\gamma_1 + k\delta_1 = x_1 \bmod p-1 \rightarrow a(23972) + k(31396) = 8890 \bmod (31846) $
2. $ a\gamma_2 + k\delta_2 = x_2 \bmod p-1 \rightarrow a(23972) + k(20481) = 31415 \bmod (31846) $

解決 $ k $ 很簡單，只需取 1. - 2. 作為等式 3. 下面：

3. $ k(10915) = -22425 \bmod(31846) = 9421 \bmod(31846) $

並解決 $ k $ :

$ k = 1165 \bmod(31846) $

現在這就是我被卡住的地方，通過插入 $ k $ 到等式2。我們得到：

$ a(23972) + (1165)(20481) = 31415 \bmod 31846 \rightarrow a(23972) = (23704) \bmod 31846 $

但我們不能隔離 $ a $ 因為 $ \text{gcd}(23972, 31846) > 1 $ 所以沒有倒數 $ 23972 \bmod 31846 $

注意堵塞 $ k $ 進入方程 3. 得到類似的結果。

這個問題來自我的教科書，所以它應該是可以解決的，但數學告訴我它無法解決。

有人可以解釋一下是否有一些工作可以找到 $ a $ 當它乘以一個不可逆的數字？

在得到教授的提示後我找到了答案

基本上，如果我們有一個方程來形成

$$ mx = (my) mod (m*z) $$

我們可以分解出 m 使得：

$$ x = (y) mod (z) $$

但是…唯一需要注意的是 x 有 m 個解決方案： $$ x, x+z, x+2z, …, x+(m-1)z = (my) mod (m*z) $$ 使用這個我們可以解決問題中的方程$$ a(23972)=(23704) mod (31846) $$

即使23972 不是可逆的mod 31846。

首先從所有內容中提取 2

$$ 2a(11986) = 2(11852) mod 2(15923) $$

這給出了：

$$ a(11986) = 11852 mod 15923 $$

解決一個： $$ a = (11852)(11986)^{-1} mod 15923 = (11852)(182) mod 15923 = 7459 mod 15923 $$ 現在是多重解決方案部分：

在哪裡 $$ m = 2 $$和$$ z = 15923 $$在我們的例子中

a = 7459 mod mz 和 7459 + z mod mz

所以$$ a = (7459) mod (31846), (23382) mod (31846) $$ 和$$ k = (1162) mod (31846) $$

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