问Q的顺序如何影响求解ECDLP所需的时间？
EN

Cryptography用户

提问于 2019-10-22 16:37:59

回答 1查看 276关注 0票数 2

我使用Sagemath的内置函数discrete_log()来求解ECDLP，根据文档，它使用Pohling-Hellman算法求解ECDLP。

对于我的电子商务来说是这样的：

P-order => 176648753626148987385153422443570230330
Q-order() => 2

P-阶具有以下主要因素:2*3*5* 5888291787538299579505114081452341011

即使最高的素因子是超大型的，通过discrete_log()的ECDLP在一秒钟内就得到了解决。

我读过关于波林-赫尔曼攻击的文章，它只提到P应该有小的素因素才能使攻击成功。它从来没有提到Q的顺序。

Q的顺序如何影响攻击成功所需的时间？

发布于 2019-10-22 17:28:34

我相信萨格玛斯正在做的事情是：

考虑到寻找x s.t的问题。xP = Q，一个步骤是计算x' = x \bmod 5888291787538299579505114081452341011；它通过计算P' = (2\cdot 3 \cdot 5)P和Q' = (2 \cdot 3 \cdot 5)Q来实现这一点，并试图解决x'P' = Q'问题。
由于P'的顺序是2^{122}，我们通常期望这个计算要花费大约2^{61}时间(相当长的时间)。但是，在这种情况下，Q'是中性元素。我怀疑萨格马斯注意到了这一点，因此立即得出结论：x' = 0
Pohlig所涉及的其他计算都相对较快，因此它快速地报告了答案(3 \cdot 5 \cdot 5888291787538299579505114081452341011)。

总结是:如果您的实现特例是这个Q' = 0情况，那么我们可以跳过没有按Q顺序出现的任何素数；Polhig所花费的时间主要是以P和Q的顺序出现的最大素数。

票数 2

页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://crypto.stackexchange.com/questions/75248

复制

相似问题

问Q的顺序如何影响求解ECDLP所需的时间？EN