ElGamal 的弱點與小訂單的公鑰
認為 $ p=29 $ , $ \alpha = 2 \in F_p^* $ 是一個生成器 $ F_p^* $ . 鮑勃選擇 $ d \in {2,…,27} $ 這樣 $ \beta = \alpha ^d=28 \pmod{29} $ . 然後他發送他的 $ (p,\alpha ,\beta) $ 給愛麗絲，她自己挑了一個 $ i_j \in {2,…,27} $ 十一個不同的明文值 $ m_j $ , $ 0\leq j\leq 10 $ 並通過加密這些 $ c_j=m_j*28^{i_j} \pmod{29} $ . 自從 $ |28|=2 $ , 遮罩鍵的唯一可能性 $ k_M = 28^{i_j} \pmod{29} $ 是 $ 1 $ 和 $ 28 $ .
Alice 以如下形式發送以下密文-密鑰對 $ ({k_E}_j, c_j) $ :
$$ (3,15),(19,14),(6,15),(1,24),(22,13),(4,7),(13,24),(3,21),(18,12),(26,5),(7,12) $$ 在哪裡 $ a=0, …, z=25, ä=26, ö=27, ü=28 $ . 因此我們有密文 $$ p,o,p,y,n,r,y,v,m,f,m $$ 任務是在不計算 Bob 的私鑰的情況下解密消息，方法是“查看密文並使用只有很少的遮罩密鑰和一些猜測”這一事實。由於唯一的可能性 $ k_M $ 是 $ 1 $ 和 $ 28 $ , 對應的明文 $ c_j $ 或者是 $ c_j $ 本身或 $ c_j*28^{-1} \pmod{29} $ . 這產生了兩種可能性 $ c_j $ : $$ p,o,p,y,n,r,y,v,m,f,m $$ $$ o,p,o,f,q,m,f,i,r,y,r $$ 我無法理解這兩者，所以我還是計算了 Bob 的私鑰來檢查結果。原來 Bob 的私鑰是 $ 14 $ ( $ 2^{14}=28 \pmod{29} $ ）。計算 $ {k_M}_j = {k_E}_j^{14} $ ，結果變成了 $$ o,p,p,y,n,r,y,i,r,y,m $$這對我來說仍然沒有任何意義。 所以我的問題是：我在路上有沒有混淆？如果不是，那麼“猜測”應該在哪裡發生？我也沒有使用過這樣一個事實 $ \alpha = 2 $ .
編輯
我之前好像一直不清楚。我問這個是因為這屬於一個練習（在不計算 Bob 的私鑰的情況下解密給定的密文），我相信我錯過了一些東西。使用不允許的密鑰計算的實際結果似乎是隨機的。所以我不知道猜測應該有什麼用，或者如何在不使用私鑰的情況下確定哪個是正確的序列。
編輯2
正如評論中所建議的，我將在此處引用完整的練習：
如果使用小階公鑰，我們將調查 Elgamal 加密中出現的弱點。我們看下面的例子。假設 Bob 使用該組 $ \mathbb{Z}_{29}^* $ 與原始元素 $ \alpha = 2 $ . 他的公鑰是 $ \beta = 28 $ .
i) 公鑰的順序是什麼？
ii) 哪些屏蔽鍵 $ k_M $ 有可能嗎？
iii) Alice 加密文本消息。每個字元都根據簡單規則進行編碼 $ a=0,…,z=25 $ . 還有三個額外的密文符號： $ ä=26, ö=27, ü=28 $ . 她傳輸以下11個密文 $ (k_E,y): $ （見上面的 11 對）
在不計算 Bob 的私鑰的情況下解密消息。只需查看密文並使用只有很少的遮罩密鑰和一些猜測的事實。
謝謝
首先，在 ElGamal 加密中，密文的形式為 $ (c_1,c_2)=(\alpha^k,m\cdot \beta^k) $ 在你的描述中是 $ (c_1,c_2)=(\beta^k,m\cdot \beta^k) $ （這不是 ElGamal 的工作方式）。但我認為這只是你的文章中的一個錯誤。
然後，當您觀察第二個組件時 $ c_2 $ 屏蔽消息的值 $ m $ 可以是 $ 1 $ 或者 $ \beta $ （作為 $ \beta $ 有訂單 2 $ Z_{29}^* $ ).
因此，鑑於密文的所有第二個組成部分，您知道它們可以是任何一種形式 $ m\cdot 1 $ 或者 $ m\cdot \beta $ ，即，要麼您已經擁有消息本身，要麼您擁有使用公鑰值屏蔽的消息。因此，如果您給定的密文元組是正確的（特別是元組中元素的順序），那麼您的發現是正確的。每個密文都有兩種可能性，用於掩蔽值 $ 1 $ 和 $ \beta $ 分別：
$$ p,o,p,y,n,r,y,v,m,f,m $$ $$ o,p,o,f,q,m,f,i,r,y,r $$ 現在，由於猜測（據我所知）不會給你任何有意義的明文，你可以做的是使用關於二次剩餘的資訊來確定明文。由於這是家庭作業，我不會填寫所有細節。
您可以快速、確定您的元素 $ \alpha $ 是二次非殘差（使用Eluers 準則- 的生成器 $ Z_p^* $ 順便說一句，將始終是二次非殘差。）。觀察到構造的密文元組的每個第一個元素都具有以下形式 $ c_{1}=\alpha^k $ 對於一些未知的 $ k $ .
現在您可以輕鬆地測試您的 $ c_1 $ 二次剩餘的分量，如果密文的第一個元素 $ c_{1} $ 是一個二次殘差，你可以得出 $ k $ 必須是均勻的。因此，對於密文的第二個元素，你有 $ c_{2}=m\cdot 1 $ . 另一方面，如果元素 $ c_{1} $ 是二次非殘差，那麼你的 $ k $ 必須是奇數，因此，對於密文的第二個元素，你有 $ c_{2}=m\cdot 28 $ （為什麼會這樣，作為練習留空）。
現在，你可以用這個事實來計算明文而不用解密，你會發現明文一定是
$$ o,p,p,y,n,r,y,i,r,y,m $$這是您在破解方案並解密密文後獲得的結果。