文章/答案/技术大牛

发布

社区首页 >问答首页 >关于Novotney关于弱曲线的论文的问题

问关于Novotney关于弱曲线的论文的问题
EN

Cryptography用户

提问于 2021-04-19 13:00:29

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

这是纸- https://wstein.org/edu/2010/414/projects/novotney.pdf

第2.1节

我在SageMath中看到了2块代码/命令

sage: #Group Order Compare SLOW
sage: m = 21345332
sage: p = 4516284508517
sage: E = EllipticCurve(GF(p), [7,1])
sage: Q = E.gens()[0]
sage: mQ = m*Q;
sage: print E.order().factor()
sage: time mRec = PolligHellman(Q,mQ)
sage: print mRec
11 * 13 * 31582419389 
Time: CPU 49.14 s, Wall: 49.14 s
21345332

sage: #Group Order Compare FAST
sage: m = 21345332
sage: p = 4516284508517
sage: E = EllipticCurve(GF(p), [7,1])
sage: Q = E.gens()[0]
sage: mQ = m*Q;
sage: print E.order().factor()
sage: time mRec = PolligHellman(Q,mQ)
sage: print mRec
2^3 * 19 * 23 * 67 * 2089 * 18913
Time: CPU 0.16 s, Wall: 0.16 s
21345332

E在这两种情况下似乎是相同的，但是E.order.factor()是不同的。怎么会发生这种事？

我也看到这里提到的这个pdf - http://koclab.cs.ucsb.edu/teaching/ecc/project/2015Projects/Sommerseth+Hoeiland.pdf

从第3页起

本文“弱曲线InElliptic曲线密码学”(弱曲线Novotney.He )研究了椭圆曲线E:y2=x3+ 7x+ 1和素数p= 4516284508517上的Galios场:当点P的阶数为4516285972627时，其素数因子为11·13·31582419389。用Pohlig求解ECDLP需要49.14秒.当P点的阶数为9254332285624时，其prime因子为2^3·19·23·67·2089·18913。用相同的Pohlig码求解ECDLP需要0.16秒。

9254332285624 = 2^3 * 19 * 23 * 67 * 2089 * 18913

所以两者是一回事。

所以-真的是E.order() or P.order()吗？

我怎样才能得到有9254332285624号订单的点数&

我在鼠尾草里试过

p = 4516284508517
E = EllipticCurve(GF(p), [7,1])
P = E.gens()[0]

print (E.order())
4516285972627

print (P.order())
4516285972627

我怎样才能得到订单为9254332285624的点？

elliptic-curves

回答 1

Cryptography用户

回答已采纳

发布于 2021-04-21 01:11:12

显然，这两个讲座项目都缺少信息。通过一次小小的尝试，我找到了一条符合所需订单的曲线。

如果将字段设置为素数字段F_P，其中p=9254331510119，则曲线

E(F_p) : y^2 = x^3 + 7x + 1

p = 9254331510119
E = EllipticCurve(GF(p), [7,1])
print(E.order().factor())

输出

9254332285624 = 2^3 \cdot 19 \cdot 23 \cdot 67 \cdot 2089 \cdot 18913视需要而定。

实际上，我很幸运，因为我只是从9254332285624-1000000开始，而且我没有使用Hasse界。

|N - (q+1)| \le 2 \sqrt{q}，N是曲线上的点数，这里是N= 9254332285624，q是有限域的元素数，这里有素域F_p。去掉绝对值后，我们就有了以下形式

q+1-2{\sqrt q} ≤ N ≤ q+1+2{\sqrt q}

q+1-2{\sqrt q} ≤ 9254332285624 ≤ q+1+2{\sqrt q}

和计算

9254332285625 - 4 \sqrt{2313583071406} \leq q \leq 9254332285625 + 4 \sqrt{2313583071406}

9254326201438 < q < 9254338369812

因此，如果在上述范围内寻找素数(可能使用next_prime函数为SageMath)，则一定会找到候选素数，这些素数期望很小(在此范围内只有407391个素数)，以满足所需的曲线顺序。

具有Hasse界的SageMath码；

expected_order = 2^3 * 19 * 23 * 67 * 2089 * 18913

#This is specific to this order!
start = floor(expected_order - 4 * sqrt(expected_order/4))
end   = floor(expected_order + 4 * sqrt(expected_order/4))

p = start -1

primeCount = 0

for x  in range(start,end):
    p = p.next_prime()
    primeCount = primeCount + 1
    if p > end:
        break
        
    E = EllipticCurve(GF(p), [7,1])
    
    if E.order() == expected_order:
        print ( p)
        break
    
print("Finished")
print("Number of tested primes =", primeCount)

以及输出；

9254331510119
Finished
Number of tested primes = 177222

票数 3

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

原文链接：

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

复制

相似问题

问关于Novotney关于弱曲线的论文的问题
EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问关于Novotney关于弱曲线的论文的问题EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问关于Novotney关于弱曲线的论文的问题
EN