3

我有椭圆曲线的所有参数。以及点Q和P的坐标。我想通过测试所有可能的k来解决Q=k*P（其中k是未知数）。

所以我用了这个类

然后：

a=-1
b=0
p=134747661567386867366256408824228742802669457
curve = EllipticCurve(a,b,p)
P=[18185174461194872234733581786593019886770620,74952280828346465277451545812645059041440154]
Q=[76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090]
for i in range(2902021510595963727029):
    result = curve.multPoint(i,P)
    if result[0]==Q[0] and result[1]==Q[1]:
        print (i)
        break

这是解决这个问题的正确方法吗？

4

2 回答 2

4

这不是一个好方法，因为您正在尝试执行 2902021510595963727029 操作。即使你每秒能做十亿次操作，也需要九万两千年才能完成。

您基本上是在试图破坏 ECDSA 的安全性。如果您想出一种方法来做到这一点，那么就可以在给定相应公钥的情况下找出一个 ECDSA 私钥。这将是密码学的一个突破，你会出名。有很多聪明人在你之前就考虑过这个问题，但没有找到解决方案。

您试图解决的问题称为离散对数问题。

于 2015-05-15T00:26:49.503 回答
0

该曲线容易受到 MOV 攻击和类似的旧 FR 攻击，因此我们可以使用 Weil 或 Tate 配对（分别）。

q = 134747661567386867366256408824228742802669457
Zq = Zmod(q)
E = EllipticCurve(Zq, [0,0,0,-1,0])
P = E(18185174461194872234733581786593019886770620, 74952280828346465277451545812645059041440154)
Q = E(76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090)
n = P.order()
k = GF(n)(q).multiplicative_order()
R = E.random_element()
w1 = P.tate_pairing(R, n, k)
w2 = Q.tate_pairing(R, n, k)
print w1, w2

在w2=w1^k的情况下，我们需要解决整数 mod p 环中的离散对数问题。这可能需要相当长的时间，但考虑到较小的模量，它仍然是可行的。

PS：这是eltrai的答案。

于 2015-05-18T20:16:10.350 回答