Discrete Log Problem: Can we derive the Private Key?
Let's try to derive the private key from the given public key!
Many technologies like Tor, Bitcoin, and Email use Asymmetric Cryptography (also known as Public Key Cryptography) for secure data exchanges. If you are reading this blog, your browser has established a secure connection to hashnode's server using this cryptography. The fundamental step for such secure connections is the generation of a private and public key pair.
It is known that we cannot derive the private key for a given public key, but there is no mathematical proof to back this up. It is unwise to believe something blindly. So let us write some code to derive the private key from a public key to evaluate the difficulty of this process. Before diving into the code, we need to understand a few basic concepts used in asymmetric cryptography and elliptic curve cryptography.
Let's learn basic cryptography
Feel free to skip this section if you know the basics of asymmetric cryptography and elliptic curves.
Asymmetric Cryptography
It is a type of cryptography that is widely for secure data transfers. It is an excellent fit for vast and growing environments with frequent data exchanges (i.e., basically the internet). So we use it for email security, web security, etc. It has the following properties.
- Each user generates two keys: a public key and a private key.
- Public key is mathematically derived from the private key (both keys together are called the key pair).
- The public key is made available to anyone. The private key is kept secret.
- Both keys are used to perform operations like encryption and decryption.
Public and Private key
Although we use the term "keys" a lot, there are no physical keys involved here. Both public and private keys are enormous prime numbers. You can think of the public key as the username of your Twitter account and the private key as its password. Therefore, both of these together define your identity in the network.
I have mentioned before that your browser uses asymmetric encryption to connect to this blog's server. Let's try to find the public key used in this connection.
- Step 1: Click the lock button beside the URL of this page.
- Step 2: Choose the Certificate option and navigate to details.
- Step 3: Now, you can view hashnode's public key.
Elliptic Curve Cryptography
One of the popular methods used to generate the private and public key pair is to use Elliptic Curve Cryptography. We follow the steps shown below to generate a public key from a private key.
- Select an elliptic curve.
- Choose a random point on the curve (Let's say \( G \)).
- Add this point with itself a certain number of times (Let's say \( n \) times).
- Return the result (\( n*G \)).
\( G = \)Generator point, \( n = \) private key and \( n*G = \) public key. Now we have covered the required concepts. If you want to learn more about Elliptic Curve Cryptography then, check out this fantastic blog series by Andrea Corbellini.
How to derive the private key?
We want to derive the private key from a known public key. we can mathematically write this as given \( G \) and \( E \). Find the value of \( n \) in the equation \[ E = n*G \] where \( E = \) public key, \( n = \) private key, and \( G = \) generator point. This is called Elliptic Curve Discrete Logarithm Problem (ECDLP). This youtube playlist by Leandro Junes covers the topic of the Discrete Logarithm Problem in detail.
This problem doesn't seem that difficult, right? After all, we know both \( G \) and \( E \) and we just need to find the value of \( n \). We can store \( G \) in a variable (Let's say curr_key) and keep incrementing this curr_key by the value G until it equals E. Then, the number of increments performed should be equal to the private key. The python implementation of this idea is below.
def find_priv_key(G, pub_key):
priv_key = 0 # no of increments performed
curr_key = 0
while(curr_key != pub_key):
curr_key += G # point addition on elliptic curves
priv_key += 1
if(curr_key == pub_key):
return priv_key
return -1 # if no key exists
The time complexity of this algorithm is O(n) where n = size of the private key. So, did we derive the private key? Linear-time algorithms should be easy to compute, right? Great question! It will be easily computable if this was a leetcode problem, but that is not the case here. There are two mistakes in this approach.
Mistake 1: The range of \( n \) is \( 0 \leq n \leq 2^{256} \). This range is so large that even if you have Google's computation ability (i.e., ~ millions of GPUs) and start your calculation at the creation of our universe, you still won't be able to finish your calculation by today. I would highly recommend you to watch this video by 3Blue1Brown. It will give you a good visual representation for the massive size of \( 2^{256} \).
Mistake 2: The value of \( x * G \) starts to repeat after a certain \( x \). That is there can be \( x1 \) and \( x2 \) for which \( x1 * G = x2 * G \). This is because the addition that we perform here isn't a normal addition. It is a point addition on elliptic curves. You can relate this to the property of arithmetic modulo operation where \( 1\;mod\;5 = 6\;mod\;5 \). How exactly is this a problem? Can't we just store \( x1 \), \( x2 \) and later find out which of these two is the actual private key? If there are just two possible values (i.e, \( x1 \) and \( x2 \)) then we can use this approach. In reality, the private keys used are huge prime numbers so, we will encounter so many more \( x \) that it might not be feasible to store all of them.
How are key pairs generated?
We realized that the linear time solution for private key derivation is computationally infeasible. Doesn't this also make the public key generation in linear time impossible? Yes, It is not feasible to generate a public key in linear time. Then how is a public key generated?
The algorithm used to generate the public key executes in O(log n) instead of O(n), making this generation process feasible. There does not exist an algorithm to derive the private key in logarithmic time. Hence, making the derivation process infeasible. This O(log n) generation process makes use of binary expansion of \( n \) to calculate \( n*G \). You can find the implementation of this idea is below.
def generate_pub_key(G, n):
temp = G
pub_key = 0 # stores public key
while(n > 0): # loops over the bits of n
if(n&1): # add 2^(i) to answer if ith bit is 1
pub_key += temp
n = n >> 1 # equivalent to n = n/2
temp = 2*temp
return pub_key
Closing note
The final verdict is that it is infeasible to generate a private key given the public key. The security of many technologies relies on this property. I hope you won't find any clever algorithm to derive the private key from the public key.
If you want to explore similar topics, I recommend the Computerphile youtube channel. It has many interesting videos like Secret Key Exchange, SQL Injection Attack and Elliptic Curve Back Door. Also, please share your thoughts on this blog in the comment section below. It will help me make the next one better.
I started exploring this topic to understand the secp256k1 library. I am grateful to my mentor Jesse Posner for encouraging me to write a blog on this topic. I am also grateful to Adam Jonas, Adi Shankara, and Caralie Chrisco for providing me this opportunity to participate in the Summer of Bitcoin 2021.