寻找 elgamal 的生成器
如何找到 elgamal 签名方案的生成器？大多数程序使用的值是否是良好的生成器？或者有没有一种方法可以找到质数生成器？如果是这样，怎么办？说质数至少有 1 个生成元是真的吗？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
如何找到 elgamal 签名方案的生成器？大多数程序使用的值是否是良好的生成器？或者有没有一种方法可以找到质数生成器？如果是这样，怎么办？说质数至少有 1 个生成元是真的吗？
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
使用 DSA 代替 ElGamal 签名方案。
实施 ElGamal 时可能会犯太多错误。这些错误之一就是 GregS 提出的建议：使用 IKE 参数。这些参数是为 ElGamal 加密生成的，而不是为签名方案生成的。这两个方案有不同的要求。特别是使用 g=2 作为生成器对于加密来说是一个不错的选择，但对于签名方案来说却是一个非常糟糕的选择。 （参见《应用密码学手册》http://www.cacr.math.uwaterloo .ca/hac/ 请参阅第 11 章中的 11.67 了解一些详细信息）。正确的是随机选择生成器。但再次强调，如果您只使用 DSA，那么您可以通过遵循标准来避免这些陷阱。
只是添加一点：OpenPGP https://www.rfc-editor.org/rfc/ rfc4880 曾经允许 ElGamal 签名，但不久前已弃用它们。这种弃用是相当合理的，因为 DSA 只有优点：它更高效、更安全和标准化。当然，您可以查看旧的 PGP 实现，但如果不先阅读文献，它不会告诉您这些实现是否为您提供了合理的选择。
Use DSA instead of the ElGamal signature scheme.
There are just too many mistakes that can be made implementing ElGamal. One of those mistakes is what GregS proposed: to use the IKE parameters. These parameters were generated for the ElGamal encryption and not for the signature scheme. The two schemes have distinct requirements. In particular using g=2 as a generator is a good choice for the encryption, but a very bad choice for the signature scheme. (See e.g. the "Handbook of Applied Cryptography" http://www.cacr.math.uwaterloo.ca/hac/ note 11.67 in chapter 11 for some details). Correct would be to select the generator randomly. But once again, if you just use DSA then you can simply avoid these pitfalls by following the standard.
Just to add a little more: OpenPGP https://www.rfc-editor.org/rfc/rfc4880 used to allow ElGamal signatures, but has deprecated them some time ago. This deprecation was quite reasonable, since DSA has only advantages: it is more efficient, more secure and standardized. Of course, you could look at old PGP implementations, but it wouldn't tell you if these implementations give you reasonable choices without reading the literature first.
您可以使用应用密码学手册中的通用概率算法 4.86。不过，您仍然需要从此类算法的输出中清除已知对 Elgamal 签名不安全的值。至少可以整除 p-1 的任何值（例如 2）以及其倒数可以整除 p-1 的任何值。请注意，这些是我今天所了解的情况。可能需要对就此主题发表的论文进行一些深入研究。
就我个人而言，我不会信任现有程序中已使用的域参数。作者可能没有考虑上述所有条件，而且研究可能强调了自选择以来的新条件。
绝对正确：对于以 p 为模的整数（其中 p 是素数）的乘法群，总是至少有一个生成器。它实际上还有更多：phi(phi(p))，phi 是 totient 函数。但并非所有这些对于 Elgamal 签名方案都是安全的。
You can use the generic, probabilistic algorithm 4.86 in Handbook of Applied Cryptography. You still need to weed out from the output of such algorithm the values known to be insecure for Elgamal signature though. At the very least any value that divides p-1 (for instance 2) and any value whose inverse divides p-1. Note that those are the conditions I am aware of today. Some in-depth research over papers published on the topic may be needed.
Personally, I would not trust domain parameters already used in existing programs. The authors may not have considered all the conditions above, plus research may have highlighted new conditions since they were chosen.
Absolutely true: there always is at least one generator for the multiplicative group over the integers modulo p (with p being a prime number). It has actually many more: phi(phi(p)), with phi being the totient function. Not all of them will be safe for the Elgamal signature scheme though.
El Gamal 可以看作是 Diffie Hellman 算法的变体，后者的参数可以用于前者。例如，您可以使用 RFC 2409 中的 IKE 组 1 和 2，以及更大的 IKE组散布在其他 RFC 中。您还可以关注 FIPS 186 中的讨论生成 DSA 参数。另请参阅有关原根的讨论。
编辑：
正如 @abc 所指出的，这对于 el gamal 签名来说是错误的。请点击 DSA 链接 (FIPS 186)。
El Gamal can be seen as a variant of the Diffie Hellman algorithm, and parameters for the latter can be used for the former. So for example you can use IKE groups 1 and 2 from RFC 2409, and larger IKE groups sprinkled in other RFCs. You can also follow the discussion in FIPS 186 for generating DSA parameters. Also, see this discussion of primitive roots.
EDIT:
As noted by @abc, this is wrong for el gamal signatures. Follow the DSA link (FIPS 186).