怎麼找rrr用於具有已知私鑰的 El-Gamal 簽名
對於公鑰 $ (g,b,P) $ 和私鑰 $ x $ 我有這個…
x = 8437809068483222013573558289468531414326215630180218801941732905 P = 7339893940555892950021117953932742794751344995120378281984000000000001 g = 89 b = 4912876245630500045238873065831524614701581692824065606616840403034906我正在嘗試找到簽名時使用的隨機數 r
M = 178197212211208201211210146110其中 (y,s) 是
y = 4888362675268704701803932900979085359299230032137217762234865463825395 s = 2972754454246783222682468852246694620839545754907463463768712881658815我在這裡使用簽名方案，我想我可以解決 $ r=\frac{M-xy}{s} \mod (P-1) $ 但我不斷得到
r=6586066995309612052451381515420731372587693346972879972770753040391021但是之後 $ y=g^r \mod P $ 不是真的。
說明表明：
$ r\cdot s\bmod (P-1) = 6586066995309612052451381515420731372587693346972879972770753040391021\cdot 2972754454246783222682468852246694620839545754907463463768712881658815 \bmod 7339893940555892950021117953932742794751344995120378281984000000000000 $
產量
720487199053255869302957380434219754352470619914582568375746711500115,
然而
$ M-x\cdot y\bmod (P-1) = 178197212211208201211210146110-8437809068483222013573558289468531414326215630180218801941732905\cdot 4888362675268704701803932900979085359299230032137217762234865463825395 \bmod 7339893940555892950021117953932742794751344995120378281984000000000000 $
產量
4218349912365743958467337126869664026873136130922995548817354564023635.
你確定你反轉 $ s $ 模組 $ (P-1) $ 正確嗎？
PS：如果您在 6 小時內沒有得到答案，則無需針對同一問題提出新問題。大多數普通使用者不會只看首頁。幾天后，您可以稍微更改一下文本（就像其他人一樣），讓您的問題再次出現在首頁。
你必須觀察給定的值， $ s $ 不是互質的 $ P-1 $ . 因此，您不能直接計算 $ r $ 作為 $ (M-xy)/s \bmod (P-1) $ .
我們有 $ \gcd(s,P-1) = 185 $ . 讓 $ q_1 = (P-1)/185 $ . 然後
$$ r \bmod q_1 = (M-xy)/s \bmod q_1 = 3956222280490813791400244134782922347290756609897677447028095051944 $$ 仍有待計算 $ r \bmod 185 $ . 注意 $ 185 = 5 \times 37 $ . 有一個輕微的並發症，因為 $ \gcd(q_1,185) = 5 $ . 定義 $ q_2 = 37 $ 和 $ q_3= 5 $ . 注意 $ P-1 = q_1 \times q_2 \times q_3 $ .
從 $ y = g^r \bmod P $ ，我們得到 $ y^{(P-1)/37} \equiv {g^{((P-1)/37)}}^{r \bmod 37} \pmod P $ . 通過蠻力，我們發現 $ r \bmod 37= 5 $ .
中國剩餘隻允許一個人獲得 $ r \bmod q_1 q_2 $ （自從 $ \gcd(q_1,q_3) \neq 1 $ ）。我們得到
$$ r \equiv 718108065145388506225887396409320059133908107486475023802228095051944\pmod {q_1q_2} $$
**編輯：**請檢查您的練習的正確性。另請注意 $ P-1 $ 光滑：
$$ P-1 = 2^{49} \times 3^{23} \times 5^{12} \times 7^9 \times 11^4 \times 13^5 \times 17^3 \times 19^2 \times 23^3 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47 $$ 因此，您可以使用 Poligh-Hellman 算法來計算 $ r $ 從 $ y = g^r \bmod P $ .