弱公钥ElGamal

Question

假设这个设置:素数$p$，$\mathbb{Z}_p^\ast$中的生成器$\alpha$。爱丽丝从$d$中选择她的私人指数$$，并计算出她的公钥$\beta$ = $\alpha^d$。

然后鲍勃选择他的私钥$i$。然后将用于加密消息的结果掩码密钥$k_M$计算为$k_M =\β^$。

我想知道，从数学上讲，是否有可能发生以下攻击：

如果$\beta$结果是$p-1$，那么$k_M$指数只有两个可能的结果：$1$和$p-1$。这是因为循环乘法组中的元素$p-1$总是有$ord(p-1) = 2$，所以只有这两个元素可以由$\beta$生成。这反过来意味着只存在两个掩码键$k_M$。然后，攻击者可以轻松地尝试这两个密钥，并将立即能够解密该消息。

您能确认这种攻击是否有效吗?如果是的话，如果现实中的ElGamal实现易受攻击的话？

Answer 1

你能确认一下这次攻击是否有效吗？

这取决于一种令人难以置信的不可能发生的情况，但如果确实发生了，是的，它会起作用的。

我们将让$\beta =p-1$当且仅当$d$恰好是值$(p-1)/2$；这发生在概率$1 / (p-2)$上。

为了确保El的安全，$p$必须是大的，比如说，至少2048位。这意味着发生这种情况的概率约为$2^{-2048}$。我们通常不会无所事事地担心在接下来的10秒内我们会被流星击中；这比我们选择糟糕的$d$更有可能发生。