论DLP中的Sage与Magma
论DLP中的Sage与Magma
提问于 2020-07-09 11:23:23
一般来说，在几个密码相关的计算上，Magma比Sage快，但是，我遇到了一个DLP实例，其中Sage比Magma要快得多。
将GF(p)上的DLP定义为：
> p := 6361543437356954559572346626686588717116516698890765462106447;
> g := GF(p) ! 1169982245527655985681304256455302750237076631211621733238455;
> h := GF(p) ! 1724031992809937243501910413446727594466297753778440734817181;
> x := 692454894150576523734315040019069833755283562844584533346596;
> g^x eq h;
true
> time Log(g, h); // hangs现在，注意p-1是光滑的(它的因式分解包含34位的2和6个素数)：
> p - 1 eq &*[2, 4567141973, 12441069709, 12520152383, 15692237597, 16668636287, 17093685347];
true然而，Magma依赖于Log(g, h);，而Sage很快就输出了x：
sage: p = 6361543437356954559572346626686588717116516698890765462106447
sage: g = GF(p)(1169982245527655985681304256455302750237076631211621733238455)
sage: h = GF(p)(1724031992809937243501910413446727594466297753778440734817181)
sage: x = 692454894150576523734315040019069833755283562844584533346596
sage: g^x == h
True
sage: time discrete_log(h, g)
CPU times: user 3.7 s, sys: 165 ms, total: 3.87 s
Wall time: 3.92 s
692454894150576523734315040019069833755283562844584533346596有什么解释吗？我在岩浆文献中读到，2^{36}可能是一个截止点，但在这里，最大的质数低于这个临界值。Pohlig的快速手动实现似乎不会改变任何事情。
我的Magma版本是2.23-1，在运行2.25-5版本的在线计算器上也看到了同样的行为。
编辑:相关的后续问题:如何有效地解决这个DLP在Magma？
回答 1
Cryptography用户
发布于 2020-07-09 19:19:12
的确，这是一个阈值问题，但真正的阈值是2^{32}，而不是文档中的2^{36}。您可以通过以下测试来验证这一点：
SetVerbose("FFLog", 2);
repeat p := 2 * (2^32-5) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));
repeat p := 2 * (2^32+15) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));不幸的是，似乎没有一种方法可以直接调用Pohlig，或者至少禁用索引演算。
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://crypto.stackexchange.com/questions/81822
复制相关文章
相似问题
腾讯云开发者
