Hey folks,
I’m kinda new to the whole cryptography scene and have been exploring ECC. I managed to code BSGS and kangaroo in Rust without any issues. But using the k256 crate isn’t really giving me the performance boost I need when I compare it to keyhunt or cyclone.
From what I’ve seen, generating public keys (or the affine points on the secp256k1 curve, to be exact) takes way more resources than running sha256 or ripemd160.
I’m thinking I should focus on optimizing the main ECC operations. Here’s what I’ve gathered so far:
- Affine points are just the (X,Y) coordinates on the curve.
- Projective points (X,Y,Z=1) are easier to work with than affine points for addition/multiplication.
- If I use some batched inversion to flip affine points into projective ones, that should speed things up.
Still, even with all this, I’m only cranking out about 2MKeys/thread with k256, so even with 12 threads, I’m barely hitting 12MKeys/s. I’m wondering if there are other algorithms that could work better with k256 or if I need to switch to a different library to speed up point generation.
I’ve heard that a lot of C++ implementations are based on Jean-Luc Pons’ work, but it’s all a bit confusing to me. I see he precomputes G points from 0 to 255 (both + and -), but I’m not clear on the math behind it. It looks like it’s quicker since keyhunt, which uses his methods, does around 35MKeys/s with 12 threads and 5MKeys/s with just one (normal brute force).
Just a side note: when I say Mkeys/s, I’m talking about millions of points per second (not BSGS or anything) just trying to measure performance.
libsecp256k1 has the fastest code to compute a public key from a private key.
Avoid computing from private keys at all costs. Precompute any public keys you know are constant (or any deltas that you know are constant), and do pubA + pubB in affine instead. If you have a batch of (pubA, pubB) pairs, use a single field inverse. If you also know that you want to compute pubA - pubB (for example, if all keys of pubB are distanced in identical deltas from both sides), move to the middle of the batch and re-use the same resulted inverse at each step to do both pubA + pubB and pubA - pubB.
Dump JLP, it is slower than libsecp256k1. Use the fe_* and ge_* primitives to generate public keys and implement affine point addition (the lib does A + J because it specializes on k * G, not on P + Q). Affine + affine is faster than A + J if you batch it and if you actually need affine points, not Jacobian.
The secp256k1 API doesn't expose low-level methods, so the wrappers will not do it, most likely.
For maximum performance some functions need to be marked as exposed, to bypass some internal useless conversions, for example when converting from 64 bytes pubKey to 5x52 internal (most efficient) representation. Low-level primitives like field operations can be imported inline and specialized depending on the use-case.
But this requires the code to be written in C. Anything else will introduce slowdowns.