Elliptic Curve Private Key Recovery
Given the public parameters of an elliptic curve, recover the poorly chosen private key
I've been trying to solve this challenge, and I know exactly what to do, its the Elliptic Curve discret logarithm problem (Q=kP, we got Q and P, must find k) , i've tried to solve it in Sage, no success!! I don't know if its realistic to recover the secret?? Does it need a specific kind of algorithm to solve it? I dont know like babystep Giant step or others? I need a little clue please!
@vigo85: The hint to keep in mind is
luckily, in this problem d was chosen to be a small value. Small in this context means small enough to find with a brute-force search. Good luck!
Hi, when should I use
p? I know that
b define the elliptic curve,
G is the generator point and
Q is the public key. But, when should I use
p? I'm now studying about arithmetic of elliptic curves, but I'm still lost in this
PS: Sorry if I made a mistake writing in english, is not my native language
EDIT: I think I found the answer to my own question here. But I'll wait for an answer anyway :)
All points on a curve over
F_p have coordinates
(x, y) such that
x, y <- F_p (excuse the formatting, we don't allow LaTeX in comments). So when you are doing point multiplication on a curve you have to operate within this field. I'd recommend not implementing point multiplication from scratch unless you really want to understand elliptic curve arithmetic. If your language has a package for ECDSA you should be able to leverage that package (I'd be happy to point you towards one if you let me know what language you're using). Otherwise, see here (chapter 3, page 75) for how to perform arithmetic on elliptic curves (or feel free to look at my python code for elliptic curve operations).
Guys, d being small enough, but who solved it, how long does it take to solve it on an i5 processor PC thx
@lattice01: On my laptop (i5 @1.4ghz) it takes a couple seconds to solve.