Homomorphic-Encryption
從加法 ElGamal 中檢索正確的密文
我一直在研究添加劑 ElGamal，我想我已經掌握了它，除了消息的部分 $ M $ 必須通過計算離散對數來檢索 $ g^M $ .
從我讀過的內容來看，這種計算的結果是 $ k $ 例如對於 $ g=3, M=4, \pmod{17} $ 我們有 $ 3^4=13 \pmod{17} $ 但是計算離散對數卻給出了 $ M=4 + 16k $ . 我怎麼知道 $ M=4 $ 並不是 $ M=20 $ ?
請注意，對於 $ g=3,M=20 \pmod{17} $ 我們也得到 $ M=4+16k $ .
如果你知道這個問題的答案，答案很簡單：
- 明文可以用 20 而不是 4 嗎？
- 如果可以的話，它們將是相同的加密並且沒有問題，因為 20 和 4 對你來說是相同的。
- 因此，如果你不能，你就無法在解密後決定明文。
要解決此問題，您必須將消息空間限制為 $ \pmod{17} $ 並以適當的方式劃分較長的消息塊。現在，你知道，你必須在哪裡取最小的正值 $ k=0 $ .
同態相加的問題是另一個問題。在計算之前，您必須考慮計算的上限並根據它選擇模數。例如，如果要添加 4 和 8，則沒有問題，但是，如果要添加 10 和 9，則必須考慮更大的模數。