I have written an application to brute-force attack Bitcoin addresses for OpenCL. It implements a simple exhaustive search starting from public key G (private key 1) and point increment (addition of G) to get next key.
It works, but its performance is one order of magnitude slower than its CPU implementation using GMP (same point increment algorithm but with GMP routines instead of custom ones). On GMP implementation, hashing is the bottleneck. On OpenCL implementation, point increment is the bottleneck.
My point increment implementation uses modular multiplicative inverse via binary extended GCD (algorithm 14.61 of Handbook of Applied Cryptography). It is one order of magnitude slower than GMP implementation using mpz_invert()
.
What I need is an optimized point increment (point addition with G) optimized for curve secp256k1. This is an educational project, so my knowledge about the subject is limited. I don't know if there is a way to accomplish it without using modular multiplicative inverse or if there is a way to speed up this calculation for my particular application.
I saw and implementation (by Segher Boessenkool) using modular exponentiation with precomputed values, but there was no information on how to get those values for other curves. I failed to replicate GMP implementation. Its source code is huge and a mess of mixed optimized C and assembly code impossible to understand for me.
Requirements:
- A fast point addition by G implementation.
- Safety is irrelevant due to its use.
- If possible, optimized for curve secp256k1.
- If possible, precompute as much as possible.
Question:
How can I improve speed of elliptic curve point addition in my specific case?
Notes on comments:
- The search is sequential inside each OpenCL kernel, but parallel considering the whole program. My worksize is optimized experimentally, getting close to theoretical GPU FLOPS performing SHA-256 only, so the bottleneck is not in OpenCL usage, but algorithmic implementation of elliptic curve cryptography.
- The performance one order of magnitude smaller I am talking about is measured on CPU, not GPU. I get about 30 kKeys/s with my own modular multiplicative inverse and 200 kKeys/s (a laptop) with GMP. On GPU I get about 2 MKeys/s. Computing unoptimized SHA-256+RIPEMD-160 hash only, without point addition, I get about 1 GHashes/s (AMD Radeon RX 580).
- Main program computes an array of public keys using scalar multiplication. It can compute them pseudo-randomly or equally spaced. This array is feed to the OpenCL kernel, and each instance computes
RIPEMD160(SHA256(P)) == TARGET
,RIPEMD160(SHA256(P+G)) == TARGET
,RIPEMD160(SHA256(P+2G)) == TARGET
, ... For now, there is only a single target address. - OpenCL is not the issue here. Profiling on CPU reveals that 90% of the time is expend computing modular multiplicative inverse. Same algorithm with GMP
mpz_invert()
uses only 25% of the time to do same step, using the remaining time on hash computation.