4
$\begingroup$

I want my application to generate an EC key pair.

The first four bytes of the sha256 hash of the public key should contain a known IP address.

As hashes are one-way functions, I need to brute force this by generating four billion keys.

Is this possible, in under an hour, on a laptop?

Openssl is not the way to do this - generating just a thousand keys takes few seconds. Four billion would take six months at 4s/thousand.

#!/bin/bash
time for a in {0..999} ; do
  openssl ecparam -genkey -name secp256k1 -noout -out key.priv.pem
done

Is openssl doing something which is unnecessary in making keys just to check the hash?

$\endgroup$
  • $\begingroup$ 1) This is probably feasible, but you need specialized code for that. Such code would speed up key generation about 200x. 2) Since your curve is Secp256k1, the bitcoin curve, you should seach the bitcoin forums for tools that find "vanity addresses". 3) The expectation value is 4 billion, not 2 billion. $\endgroup$ – CodesInChaos Oct 16 '15 at 14:05
  • $\begingroup$ Yes, you're right about the expectation value. I will edit. $\endgroup$ – Thomas Von Panom Oct 16 '15 at 14:41
  • $\begingroup$ @fgrieu I don't follow. The OP has no guarantee that a hit will be among the first 4 billion hits, so you get an independent chance of 1 / (4 billion) for each attempt, which follows an exponential distribution with expectancy value 4 billion. $\endgroup$ – CodesInChaos Oct 16 '15 at 14:42
  • $\begingroup$ Vanitygen seems to be able to generate and hash between 1 and 60 million keys per second, depending on available hardware. So it'll take a few hours hour with CPU only and a few minutes with a fancy GPU. $\endgroup$ – CodesInChaos Oct 16 '15 at 14:46
  • $\begingroup$ @CodesInChaos Bitcoin addresses are not (just) SHA-256 hashes, so for the actual question a vanity address generator could require some modification. Of course, if the purpose really is to generate a Bitcoin address... $\endgroup$ – otus Oct 16 '15 at 15:55
4
$\begingroup$

The very fastest elliptic curve algorithms can generate a key-pair in about 40k cycles on a modern CPU. A high end laptop has four cores running at about 3 GHz, so it can generate about 300k key-pairs per second, or a billion per hour. (The cost of SHA-256 is negligible in comparison.)

However, secp256k1 is nowhere near the fastest curve. It takes 10 times as long to generate a key-pair with many algorithms, according to the above link, so it would likely take tens of hours at least to iterate the search space. A more mainstream laptop and you may be looking at several days.

So if you just brute force generate key-pairs looking for a matching one, you can't get it done in an hour even with a much better implementation (unless you get lucky).

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ If you generate many keys at once, of which you only use one, this will reduce the cost a hundredfold or so. Instead of using a scalar multiplication, you can simply use point addition and the field inversion for point compression can be amortized. $\endgroup$ – CodesInChaos Oct 16 '15 at 14:33
  • $\begingroup$ @CodesInChaos, I'll edit to make it clear this answer only covers the brute force method. (I don't have data on cost of point addition anyway.) $\endgroup$ – otus Oct 16 '15 at 14:57
  • $\begingroup$ @CodesInChaos could you add a link to an explanation of how this might be done using Bouncy Castle and/or Java's BigInteger class? $\endgroup$ – Thomas Von Panom Nov 2 '15 at 8:45
1
$\begingroup$

This may not be exactly what you are looking for, however with small modifications it may give you the results you seek.

Look at Vanitygen, which uses the GPU and on most modern cards can generate roughly 50M keys per second.

For the record - on my laptop GPU it does about 5M keys/sec.

| improve this answer | |
$\endgroup$
1
$\begingroup$

It is possible to generate about 30 Mkeys/s on a notebook with Xeon E3 (4 cores, only CPU, no GPU).

I mean: 30 million uncompressed public keys, or 60 million (if you accept both uncompressed and compressed format) keys in 1 second.

If you exploit then the symmetrie of the secp256k1 curve, you can double this number for free (120 million public keys in 1 second). If you use endomorphism too, you could get over 220 million of public keys in 1 second. Only via CPU.

So generating one billion public keys takes about 5 seconds (or 10 if you look only at compressed keys). Then you have to perform the sha256 operations (much slower on a CPU)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.