ElGamal 離散對數方法發送密鑰
在我的文字學課程中，我得到了以下練習：
ElGamal 提出了以下使用離散對數在域上的數字簽名方案 $ \mathbb{F}_p $ ， 在哪裡 $ p $ 是一個大素數。
- 步驟 1) 每個人都同意質數 $ p $ 和一個發電機 $ g $ 為了 $ \mathbb{F}_p^* $ .
- 步驟 2）A（和所有其他用途）選擇一個秘密指數 $ d_A $ ，並公開 $ e_A\equiv g^{d_A}\mod p $ （就像在 ElGamal 密碼系統中一樣）。
- 步驟 3) 對消息進行簽名，編碼為整數 $ m $ 和 $ 0\le m\le p-1 $ , A 選擇一個隨機整數 $ k $ 相對於 $ p-1 $ （IE $ \gcd(k,p-1)=1 $ ）。然後計算 $ r\equiv g^k \mod p $ 並解方程 $ g^m\equiv e_A^r r^s \mod p $ 在未知 $ s $ . 如果 $ s=0 $ （不太可能），她又以不同的方式開始 $ k $ . 最後，A 向 B 發送消息 $ m $ 和這對一起 $ (r,s) $ ，這是她對該消息的簽名。
- 步驟 4) Beatriz 檢查 $ g^m \equiv e_A^r r^s \mod p $ . 如果這成立，B 接受簽名 $ (r,s) $ 確實屬於A。
a) 檢查安娜是否知道她需要計算的一切 $ s $ .
b) 檢查 C 不能在不知情的情況下偽裝成 A $ d_A $ ，也就是說，無法解決離散對數問題，因此 $ B $ 可以確定消息確實來自 A。
c) 為什麼 A 必須丟棄 $ k $ 如果事實證明 $ s=0 $ ?
這就是我所擁有的：
a) 因為 $ r\equiv g^k\mod p $ 和 $ e_A=g^{d_A}\mod p $ 然後： $$ g^m\equiv e_A^rr^s\equiv (g^{d_A})^{r}(g^k)^s=g^{d_Ar+ks}\mod p $$ 而且，費馬小定理意味著 $ m\equiv d_Ar+ks\mod p-1\Rightarrow ks\equiv m-d_Ar\mod p-1 $ . 因此，由於 $ \gcd(k,p-1)=1 $ 我們有 $ k $ 是可逆的 $ \mathbb{F}^*_p $ 所以 $ s\equiv k^{-1}(m-d_Ar)\mod p-1 $ . 因此，我們完成了，因為 Ana 知道 $ p,k,m,d_A $ 和 $ r $ .
b) 如果 $ C $ 想假裝是 $ A $ , 它需要發送 $ m $ 和 $ (r,s) $ 這樣 $ g^m\equiv e_A^rr^s\mod p $ . 但 $ s $ 取決於 $ d_A $ 正如我們在 $ a) $ . 因此，我們不能構造 $ s $ 不知道 $ d_A $ ，所以，如果 $ C $ 想假裝是 $ B $ , 它需要找到 $ d_A $ . 但這很難，因為我們只知道 $ d_A $ （如果我們不是 $ A $ ） 就是它 $ e_A\equiv g^{d_A}\mod p $ 所以，假裝是 $ A $ 相當於解決一個離散對數問題。
c) 如果 $ s=0 $ 然後 $ g^m\equiv e_A^r\equiv g^{d_Ar}\mod p $ 所以 $ m\equiv d_Ar\mod p-1 $ . 從這裡我被卡住了，因為這是我擁有的唯一資訊，但我不明白這如何使我們能夠在不知道的情況下建構簽名 $ d_A $ . 當然，我們可以解決 $ m\equiv d_Ar\mod p-1 $ , 這將有 $ \gcd(r,p-1) $ 解決方案，然後檢查哪個是正確的 $ d_A $ ， 但 $ \gcd(r,p-1) $ 可以接近 $ p-1 $ 如果我們運氣不好，那意味著這個過程是指數時間，並不比求解離散對數好。
如果你能檢查 a) 和 b) 是否正確，並給我關於 c) 的提示，我將非常感激。
給a的解決方案很好。
對b的嘗試證明是錯誤的：有可能 C“發送 $ m $ 和 $ (r,s) $ 這樣 $ g^m\equiv(e_A)^r,r^s\pmod p $ ”.
這樣做的一種方法，即使 A 沒有使用 $ d_A $ 超越步驟 1：C 選擇 $ r=s=(p-1)/2 $ , 併計算 $ (e_A)^r,r^s\bmod p $ . 那要麼 $ p-1 $ 或者 $ 1 $ . C對應選擇 $ m=(p-1)/2 $ 或者 $ m=0 $ , 現在有 $ m $ 和 $ (r,s) $ 通過了步驟 4 的驗證。這是一個存在的偽造（還有其他導致隨機外觀的 $ m $ ）。通過要求在步驟 4 中，B 只接受有意義的 $ m $ 對於有意義的一些定義。或將驗證方程更改為 $ g^{H(m)}\equiv(e_A)^r,r^s\pmod p $ .
但是，有一個問題是 C 可以擷取一個 $ m $ 和 $ (r,s) $ 由 A 在步驟 3 的先前執行中準備好，並將其發送給 B。這是對b中概述的協議的重放攻擊。阻止這些的一種方法是讓 B 選擇 $ m $ 在每次執行步驟 3 之前。
但是，C 可以將 C 從 B 得到的任何消息中繼到 A，並將 C 從 A 得到的任何消息中繼到 B。這是對b中概述的協議的中繼攻擊。在問題範圍內對該問題的解決方案相當有限：確定這不是問題，或者假設 A 與 B 和 C 之間的互動是隔離的。
如果問題正確地轉錄了問題陳述，那麼後者就是錯誤的！如果僅僅指出它被認為是有風險的，我建議將b中概述的協議改寫為：假設 $ m $ 是隨機選擇的 $ [0,p-1) $ B 在第 3 步之前，A 不參與 B 和 C 之間的交換。 $ m $ 到完成步驟 4。證明如果 C 能夠以非零機率通過步驟 4 的測試，則 C 可以找到 $ d_A $ 以相同的機率。我希望（不確定）有一個相對簡單的解決方案來重新制定。
c提示：首先假設 $ (p-1)/2 $ 是主要的（幫助使 DLP 變得困難的常見要求），並且竊聽者掌握了 $ m $ 和 $ (r,s=0) $ 通過 4 的測試，並且 $ m\not\equiv0\pmod{(p-1)/2} $ . 證明這個竊聽者能找到 $ d_A $ ，然後冒充A。
即使問題陳述最初沒有，我建議堅持使用標準符號 $ \bmod $ :
- $ a\equiv b\pmod q $ , 輸入為
$a\equiv b\pmod q$, 表示 $ q\ne0 $ 和 $ b-a $ 是的倍數 $ q $ , 沒有界限 $ a $ . 前面有一個左括號 $ \bmod $ ，意味著它沒有左操作數。這 $ \bmod $ 並且它的正確操作數可以更早地限定 $ \equiv $ 符號。可以有幾個，如 $ a\equiv b\equiv c\pmod q $ .- $ a=b\bmod q $ （輸入為
$a=b\bmod q$）表示 $ 0\le a<q $ 和 $ b-a $ 是的倍數 $ q $ . 在這個表達式中 $ \bmod $ 是一個有兩個參數的運算符，適用於左操作數 $ b $ 和右操作數 $ q $ . 沒有 $ \equiv $ 符號，前面沒有括號 $ \bmod $ . 我們可以等效地寫 $ a=(b\bmod q) $ , $ (b\bmod q)=a $ ， 或者 $ b\bmod q=a $ .