椭圆曲线穷举攻击

Question

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

因此，我使用了这个class。

然后：

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

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

- Chaker

---

请注意，在您的参数中，a=-1且b=0，因此椭圆曲线方程y^2 = x^3 + ax + b实际上变成了y^2 = x^3 -1*x。这不再是一个强椭圆曲线。祝您在CTF比赛中好运！ - Nils Pipenbrinck

Answer 1

这不是一个好的方法，因为你试图执行2902021510595963727029次操作。即使你每秒可以执行10亿次操作，也需要92000年才能完成。

你基本上在试图破解ECDSA的安全性。如果你找到了一种方法，那么就可以根据相应的公钥找出ECDSA私钥。这将是密码学领域的突破，你会成为名人。许多聪明的人之前都考虑过这个问题，但都未能找到解决方案。

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

- David Grayson

---

这是一个CTF挑战，所以它很可能是可以解决的。 - b0fh

如果他们故意选择了一个较小的“k”值，或者曲线参数选择不当，那么这个问题是可以解决的。如果这里没有人有任何想法，也许你应该在http://cryptography.stackexchange.com上询问。 - David Grayson

Answer 2

该曲线容易受到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，我们需要在模p的整数环中解决一个离散对数问题。这可能需要一些时间，但由于模数较小，仍然可行。

附注：这是eltrai的答案。

- Chaker