ElGamal，message >p

Question

假设我们有：

p = 89
g = 5
public key: 17
private key: 73

如果我们试图加密消息M= 53 (M < p)，则得到(c1，c2) == (55，67)，并进一步解密消息。

但是，如果我们试图加密消息M= 91 (M > p)，则得到(c1，c2) == (44，57)，而进一步的消息解密失败(结果是"2“)。

有三个问题：

• 为什么会发生这种事？
• 如果我们知道(m > p)使用、p、g、公钥和拥有(c1，c2)这一事实，是否有可能恢复原始消息M？
• 如果我们知道(m > p)使用，p，g，公钥并且有多个加密消息(c1，c2)，那么是否有可能恢复原始消息M？

Answer 1

为什么会发生这种事？

这是因为，就算术mod 89而言，数字2和91是等价的：91 \bmod 89 = 2。您通常会看到这表示为91 \equiv 2 \pmod{89}。

如果你对模块化算法还不熟悉--就像传统时钟上的小时数( 0 )和时间( 12 )是等价的一样--它就“绕了过来”。

如果我们知道(m > p)使用、p、g、公钥和拥有(c1，c2)这一事实，是否有可能恢复原始消息M？

一般情况下不允许对消息m < p进行解密。

在特定情况下，您有一个密文，并且知道原始消息在例如[2p, 3p - 1]中，您可以通过在解密后添加适当的偏移量来恢复它。

在实践中，这并不特别有用，因此，正如上面的注释所提到的，将消息m分解为m_1, \ldots, m_n，从而使m_i < p。然后对每个部分消息分别进行加密。