# Public Key Cryptography using Elliptic Curves

## Introduction
Up until now, we've dealt with the math portion of elliptic curves. Enough with the math, let's get into real-life use cases of public key cryptography using elliptic curves. All of this information will act as a basis for understanding public key cryptography used in Ethereum and Bitcoin. In this article, we will examine how Ethereum uses the secp256k1 elliptic curve to generate its pair of public and private keys, and why it is secure.

## Public Key Cryptography

The underlying computation behind private and public key generation is the equation that we've repeatedly seen throughout the previous articles: $X = x \cdot P$. Recall that $x \cdot P$ is scalar multiplication, which is relatively easy to compute. However, deriving $x$ while knowing $X$ and $P$ is computationally infeasible, as it involves the division $X/P$. This is called the discrete logarithm problem for elliptic curves and is the basis of public key cryptography that uses elliptic curves.

Specifically, Ethereum and Bitcoin use the elliptic curve **secp256k1** over a finite field, in which the equation is $y^2 = x^3+7 \pmod{p}$ and $p = 2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^6-2^4-1$. Note that because this is an elliptic curve defined over a finite field, all the points on the curve are integer points. Let's explore how a private-public key pair is generated on this curve.
### Private Key

As we've seen that it is extremely difficult to figure out $x$ given $X$, where $X = x \cdot P$, it is reasonable to define $x$ as the private key, where $X$ would be the public key.

A private key is simply a random 256-bit integer chosen between 1 and $n$, where $n$ is the
as the size of the secp256k1 curve is 256-bits. As the private key proves the ownership of a fund, it is crucial that this private key is produced with true randomness so that an attacker cannot predict or determine it. Once a random number is chosen, you want to check that it is in the valid range of the curve. For example, Ethereum feeds these numbers into a 256-bit hash algorithm such as Keccak-256 that will output a 256-bit private key. This private key is then represented as 64 hexadecimal digits, as such:

ea528c1fe54d658636c15b0b81a9d25698d3b051282f7ca5b4122729ef7dfb65

### Public Key
The public key is $X$, which is derived from multiplying the private key $x$ and a point $P$ on the secp256k1 curve. This output is a random integer point on the curve with $(x,y)$ coordinates. Point $P$ doesn't change all the time; it is a fixed point so that the output of your public key $X$ will always be the same by using your private key $x$. This is called the generator point.

The generator point $P = (x,y)$ for the secp256k1 curve is as follows:

x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

The computation of the public key $X$ is simply scalar multiplication: adding the generator point $P$ to itself $x$ times. As we've explored in our [previous article](https://hackmd.io/5qpUdZTsTxi0hSXvicMWvA), this computation is both fast and easy if we apply the double and add algorithm.

Ethereum has a particular format when expressing public keys. If you have a public key $X$ with each of its $(x,y)$ coordinates as 64 hexadecimal digits, the public key is formatted as such:

04 + x-coordinate (64 hex) + y-coordinate (64 hex)

04 is a prefix that represents uncompressed public keys, which Ethereum uses.

### Recap

Based on each of the methods of how private and public keys are generated, we can notice that while generating the public key $X$ is not demanding, deriving the private key $x$ from $X$ is hard because it requires modular inversion. In other words, it is computationally infeasible to derive a private key $x$ given a public key $X$. This guarantees security, as even if a malicious attacker were to know your public key, it would be extremely hard to extract your private key that gives access to all your funds.

To recap, these are the steps for generating a private and public key pair in a secp256k1 curve:

1. Generate a random 256-bit integer $x$
2. Given a generator point $P$, compute the public key $X = x \cdot P$ using scalar multiplication on elliptic curves

A nice example of how private and public keys are formatted can be found [here](https://www.oreilly.com/library/view/mastering-ethereum/9781491971932/ch04.html).

## Digital Signatures

The private key not only generates the public key, but also creates digital signatures and account addresses, which all come together to control the access of Ethereum's externally owned accounts (EOAs). Particularly, digital signatures sign messages to authenticate the owner of the contract, so that when Alice sends a transaction to Bob with her digital signature, Bob knows that this transaction is indeed sent from Alice.

More specifically, Alice would sign her message with her private key $x$ and Bob would validate the signature using Alice's public key $X$. To secure the integrity of the message, a hash function like SHA-256 is used to hash the message as such: `h = hash(message)`. We need to check that the bit length of the hash is equal to the bit length of the sizde of the curve, which is 256-bits. After this, the signing of the message is done with these steps:

1. Choose a random integer $k$ in the range of ${1, }

More specifically, the message that should be signed is Alice's transaction details. This is signed with a one-way hash function, which is later encrypted with Alice's private key. This encrypted hash is encrypted again with Bob's public key, producing a digital signature. Along with this signature, the hashing algorithm that Alice used to sign her message is also sent to Bob.

Bob_public_key(Alice_private_key(hash(message)))

Once this digital signature is sent, Bob needs to decrypt the message without knowing Alice's private key but also verify that the message was indeed sent from Alice. First, Bob is able to decrypt the digital signature with his public key, `Bob_public_key`. This ensures that Alice's transaction details can only be read by Bob. Then he is left with:

Alice_private_key(hash(message))

Bob is able to decrypt this part with Alice's public key, as it was shared during a key exchange between Bob and Alice. This then guarantees that the message was indeed sent from Alice. Finally, Bob is able to extract `hash(message)`. He checks that the message was not tampered in the delivery process by running the message through the same hashing algorithm that Alice used. If both messages match, then the transaction is valid.

Ultimately, digital signatures 1) authenticate Alice's transaction details by proving that Alice is indeed the sender of the message and 2) guarantee the integrity of the message so that only Bob is able to decrypt the message sent by Alice.

## Conclusion
Summing up, in this campaign, we started from basic elliptic curve arithmetic operations of point addition and point doubling to understanding how private and public keys are generated in blockchain ecosystems. We've also explored the discrete logarithm problem for elliptic curves and why they are so difficult to solve, which ultimately guarantees the security of Ethereum and Bitcoin's private-public key pairs.