Elliptic Curve Private Key Recovery

Given the public parameters of an elliptic curve, recover the poorly chosen private key



vigo85

5 solved
Dec. 11, 2015, 9:25 a.m.

Hey there,

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!

Robert

Staff
Dec. 11, 2015, 2:28 p.m.

@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!

aaossa

30 solved
Dec. 24, 2015, 7:47 p.m.

Hi, when should I use p? I know that a and 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 :)

anton

Staff
Dec. 26, 2015, 8:50 a.m.

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).

lattice01

4 solved
May 8, 2016, 6:58 p.m.

Guys, d being small enough, but who solved it, how long does it take to solve it on an i5 processor PC thx

anton

Staff
May 8, 2016, 8:21 p.m.

@lattice01: On my laptop (i5 @1.4ghz) it takes a couple seconds to solve.