Hello everyone! Welcome to the new post of my blog. In this one, I'll try to cover the secp256k1 elliptic curve and key-generation process based on it. In the upcoming parts, we will discuss; signature generation & verification on secp256k1 and account (address) generation using secp256k1.

Elliptic Curves, Revisited
1. What was an elliptic curve, again?
What is secp256k1?
1. Parameters & Curve
2. Why is it important?
Key-Pair Generation w/ secp256k1
1. Key-Pairs
  1. Private Key
  2. Public Key
2. How to generate a key-pair?
  1. Generating a Private Key
  2. Deriving the Public Key
Conclusion

Elliptic Curves, Revisited

What was an elliptic curve, again?

Let $p$ be a prime number and let $\mathbb{F}_p$ denote the field of integers modulo $p$. An elliptic curve $E$ over $\mathbb{F}_p$ is defined by an equation of the form

$$y^2 = x^3 + ax + b,$$

where $a,b \in \mathbb{F}_p$ satisfy $4a^3+ 27b^2 \neq 0 \ (mod \ p) $ . A pair $(x, y)$ is a point on the curve if it satisfies the equation where $x,y \in \mathbb{F}_p$. The point at infinity, denoted by $\infty$ is also said to be on the curve. The set of all points on $E$ is denoted by $E(\mathbb{F}_p)$.

For example, if $E$ is an elliptic curve over $\mathbb{F}_7$ with equation

$$y^2 = x^3 + 2x + 4,$$

then the points on $E$ are

$$E(\mathbb{F}_7) = \{ \infty, (0,2), (0,5), (1,0), (2,3), (2,4), (3,3), (3,4), (6,1), (6,6) \}.$$

Notice that, with the point addition rule, the set of points $E(\mathbb{F}_p)$ forms a group with $\infty$ serving as the identity element. We call such groups elliptic curve groups.

What is secp256k1?

Parameters & Curve

In order to specify a particular elliptic curve, we need to mention a couple of parameters (domain parameters). Let us see what we have for secp256k1:

$a = 0$,
$b = 7,$
$p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1,$
$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337,$
$G_x = 55066263022277343669578718895168534326250603453777594175500187360389116729240,$
$G_y = 32670510020758816978083085130507043184471273380659243275938904335757337482424,$

where $a$ and $b$ are the multiples in the curve equation, $p$ is the order of the finite field which the curve is based on, $n$ is the order of the elliptic curve group, and finally $G$ is the base point or generator point of the curve with $G_x$ as the x-component and $G_y$ as the y-component.

Notice that all these numbers are quite large and this is the thing making the system so secure.

So our curve equation is as follows:

$$y^2 = x^3 + 7.$$

Notice that neither $G_x$, nor $G_y$ is greater than or equal to $p$.

Why is it important?

The elliptic curve secp256k1 has become a cornerstone in the world of cryptocurrencies, especially for Bitcoin and Ethereum. Its popularity comes from the curve's robust security, which is enhanced by its large prime order, and its operational efficiency. These features make it exceptionally suitable for creating cryptographic keys in decentralized systems.

The curve's parameters are specifically chosen to ensure fast cryptographic processes, which in turn, make transactions not only secure but also swift. This blend of security, effectiveness, and speed is crucial for maintaining the trust and reliability of transactions on the Bitcoin network, significantly contributing to the development and success of blockchain technology.

Key-Pair Generation w/ secp256k1

Key-Pairs

A key-pair consists of two keys:

private key and
public key.

Private Key

It is used for signing and, as the name suggests, kept secret. The signer uses their private key to sign the message. The strength of the system lies in the fact that, although the public key is known to all, it is computationally infeasible to derive the private key from it.

Public Key

It is available to everyone and used for signature verification. It's like a digital address shared openly for others to verify signatures if they are actually created by the party that claims the ownership of the signature.

How to generate a key-pair?

Generating a Private Key

A private key in elliptic curve cryptography is a randomly selected integer $d$ from the range $[1, n-1]$, where $n$ is the order of the curve.

Let's try it:

use num_bigint::BigInt;
use rand::thread_rng;

// Order of the curve in hexadecimal form
const N: &str = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141";

fn generate_private_key() -> BigInt {
    let n = BigInt::parse_bytes(N.as_bytes(), 16).unwrap();
    let mut rng = thread_rng();
    // Generate a random BigInt within the range [1, n-1]
    let private_key = rng.gen_bigint_range(&BigInt::one(), &n);
    private_key
}

This short code snippet basically does:

import some external libraries to use BigInt format and choose a randomly selected integer,
declare a variable called N with the hexadecimal form of $N$,
initialize a function called generate_private_key(),
declare a variable called n and initializes it with the result of parsing the hexadecimal form of $N$,
generate a random integer within the range $[1, n-1]$ and assign it to the variable called private_key.
finally return private_key.

Deriving the Public Key

The public key $Q$ is derived from the private key $d$ by multiplying it with the base point $G$ of the curve:

$$Q = d \cdot G.$$

Hence, public key $Q$ is essentially a point on the curve.

use num_bigint::BigInt;

mod utils;

use utils::Point;
use utils::scalar_multiplication;

// Other domain parameters in hexadecimal form
const P: &str = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F";
const G_X: &str = "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798";
const G_Y: &str = "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8";

fn derive_public_key(private_key: &BigInt) -> (BigInt, BigInt) {
    let modulus = BigInt::parse_bytes(P.as_bytes(), 16).unwrap();
    let a = BigInt::from(0); // secp256k1's 'a' parameter is 0
    let g = Point {
        x: BigInt::parse_bytes(G_X.as_bytes(), 16).unwrap(),
        y: BigInt::parse_bytes(G_Y.as_bytes(), 16).unwrap(),
    };
    let public_key = scalar_multiplication(&g, private_key, &a, &modulus);
    (public_key.x, public_key.y)
}

This code basically does:

import an external library to use BigInt format,
import a struct called Point ,
declare the domain parameters as variables in their hexadecimal forms,
initialize a function called derive_public_key taking private key as an input,
declare a variable called modulus and initializes with the result of parsing the hexadecimal form of $p$.
declare variables for $a$ and the base point $G$,
perform the scalar multiplication $d \cdot G$ and assign it to the variable called public_key,
finally return the point public_key.

Let us build the main() function before running the code:

fn main() {
    let private_key = generate_private_key();
    println!("Private Key: {}", private_key);

    let public_key = derive_public_key(&private_key);
    println!("Public Key: ({}, {})", public_key.0, public_key.1);

    let ethereum_address = convert_to_ethereum_address(&public_key);
    println!("Ethereum Address: {}", ethereum_address);
}

Time to build and run:

cargo build
cargo run

Output:

Private Key: 41831991390653552422840364716923515177067311217271364429731967099160830113867
Public Key: (16443841179803354550922733760429663760404329023875294123053636149554388604922, 86388970361949805853944014893086285981774181298492291090513927212929981949880)
Ethereum Address: 0x101e2b2e11d2c62f9adcb129de37b2bb36982671

We have successfully generated our key pair and displayed it, along with an Ethereum address as an additional version.

I needed to code some extra utility functions to build this project:

convert_to_ethereum_address(),
add_points(),
double_point(),
scalar_multiplication(),
mod_inverse().

You can find the complete code in this GitHub repository.

Image Reference: I created it on imgflip.com.

Conclusion

In this first part of our exploration into the secp256k1 elliptic curve, we've laid the foundational knowledge necessary to understand the basics of elliptic curves and the specifics of secp256k1, including its significance in the world of cryptocurrency. We've also walked through the process of generating a key pair, which is crucial for ensuring secure digital transactions. As we've seen, the combination of a carefully selected private key and its corresponding public key forms the backbone of cryptographic security in blockchain technologies.

In the next parts of this series, we will delve deeper into the processes of signature generation and verification, as well as the intricacies of generating an account (address) using secp256k1.

Stay tuned as we continue to unravel the complexities of cryptographic protocols and their pivotal role in securing digital assets.

Furkan's Blog