Can I derive the private key from the public key?

Can I derive the private key from the public key?

I received an email from someone and was asked how they could find a private key from an elliptic curve public key. On the one hand there would be deep ethical questions to answer, but I didn’t probe the reason why they wanted to do this. My answer was … “You might be lucky and find the key, but even if you used all the computers in the world to try and find the key, it will still take you billions and billions of years with current computing power.

Why? Because we use a 256-bit random number for our elliptic curve private key. The chances of you finding that key with your first guess will be:

1 in 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936 (2²⁵⁶)

That is approximately:

1 in 150,000 billion billion billion billion billion billion billion billion

I thus have a worry that there’s a bit of misunderstanding of the core principles involved in key generation, and the easy of cracking hashed passwords somewhat crosses over into the generation of encryption keys.

Elliptic Curve Crypto

So what protects your privacy and security probably more than anything else on the Internet? That will be Elliptic Curve , and especially:

y² = x³+ax+b

where 4a³+27b² ≠ 0 (and which is need to avoid singular points). The most popular curve is a Secp256k1 (or Curve 25519), and is defined with a=0 and b=7:

y² = x³+7 [Link]

In this, with ECC (Elliptic Curve Cryptography), we take a random number (n), and a point on the elliptic curve (G), and then multiply them together to produce P:

P = n G

G will be an (x,y) point on the curve that both Bob and Alice will agree to. n will then be Bob’s private key, and P will be his public key. The challenge is that if n is a 256-bit random value, it will be extremely difficult to find the value, even though we know G and P.

So let’s look at a bit of Python code in getting an elliptic curve setup:

In this case we see that _a is 0 and _b is 7 (y² = x³+7), and that we have a _Gx and a _Gy value. We also have _p which is a prime number in which all the operations are conducted with a (mod _p) function. In Python we could create two key pairs (one for Alice and one for Bob) with:

And where we generate a random 256-bit value for a, and then find the public key (A) by multiply it with G. This will give us a point on the elliptic curve. Note that all of the operations are undertaken with (mod _p), and where the mod operator is the remainder of an integer division.

Analysing the keys

When we generate our key pair with Openssl, we see a 256-bit private key (and made from 32 bytes), along with a 65 bytes of a public key. The 04 at the start of the public key is an identifier. There are two 256-bit points which define the public key (and each are 32 bytes long):

In this case the private key is:

and the public key:

The elliptic curve parameters that are shared can be viewed with:

Notice that the values here for the Prime, A, B and Generator and the same as the values for _p, _a, _b, _Gx and _Gx from the Python snippet above, and will are likely to be the same for any applications of this curve standard. If you are interested, some standards for curve parameters are defined here.

Bitcoin addresses and signing

Elliptic Curve is seen all over the Internet, smarts cards and in IoT applications. You can also see it with blockchain, where it is used as a standard method to sign transactions. With this Bob has a wallet, and which contains his public and private key. The private key is used to sign his transactions, and the public key will provide that he was the one that signed it. We also generate Bob’s ID from the key pair.

With this, Bob initially create a number 256-bit value, and this will be his private key. The key is converted into a Base-58 form (and which gets rid of difficult characters such as ‘O’, and ‘l’ [here]). This is his WiF (Wallet Interchange Format) private key. He should not reveal this to anyone, and, if possible should not store it on-line. Next he will produce his 512-bit public key (as seen above). After this it is then hashed with SHA-256 and RIPEM-160 to produce a public key hash value. This is then converted, using Base-58, into Bob’s Bitcoin ID:

And example of this is:

And so, it we want to send bitcoins to Bob, all we need to do is to get his address, and then sign a transaction with our private key.

Conclusions

And so I repeat … with current computer technology, it will take you billions and billions of years to find a key derived from an elliptic curve public key. Of course, when quantum computers come along, that won’t hold any more.