椭圆曲线暴力破解

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

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

Answer 1

这不是一个好方法，因为您正在尝试执行 2902021510595963727029 操作。即使您设法每秒执行十亿次操作，也需要 92 thousand years 才能完成。

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

您要解决的问题称为 discrete logarithm 问题。

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

with w2=w1^k 我们需要解决整数环 mod p 中的离散对数问题。这可能需要一段时间，但考虑到小 modulus.

仍然可行

PS: 这是eltrai answer.

椭圆曲线暴力破解

Elliptic curve brute forcing

python

brute-force

elliptic-curve

ecdsa