Dark mode
Elliptic Curve Cryptography
0322
Introduction
The purpose of this post is to introduce Elliptic Curve Cryptography (ECC) as a primer for use it's use in Web3.
Motivation
Symmetric key encryption is a type of cryptosystem that uses the same cryptographic keys for both encryption of plaintext and the decryption of ciphertext. As such, the key represents a shared secret between two or more people that can be used for private communication.
Encryption cipher_text = τ(plain_text, secret_key) Decryption plain_text = τ(cipher_text, secret_key) Where τ(x,y) is the function used for encryption and decryption
One of the main drawbacks of symmetrickey encryption is that all parties are required to know the key. This creates a sort of catch22 paradox where users need to privately communicate a key to use for private communication. At some point in time messages would need to be sent over unencrypted channels. This creates what is know as the key distribution problem.
This problem was solved in 1976 with the publication of the DiffieHellman key exchange algorithm. This algorithm is based on two related pieces of information a public key, which can be revealed publicly and sent over unencrypted channels, and a private key, which must be kept secret. With this, Alice can now safely send her public key over unencrypted channels to Bob who can use Alice's public key to encrypt some data. This cipher text can only be decrypted by the holder of the private key; Alice. This type of cryptosystem is known as publickey cryptography or asymmetric cryptography.
The basis of publickey cryptography relies a set of algorithms which are easy to compute in one direction but extremely computationally difficult to reverse. These types of functions are known as trapdoor functions.
# This should be easy to compute public_key = f(private_key) # This should be extremely difficult to compute private_key = g(public_key) where g(x) is the inverse function of f(x)
Elliptic Curve Cryptography is one type of publickey cryptography system that is widely used in both the Bitcoin and Ethereum protocols. However, before looking at Elliptic Curve Cryptography it will be helpful to briefly look at another publickey cryptosystem called RSA.
RSA
In their publication, Diffie and Hellman did not formally specify a oneway function that could be used in their key exchange algorithm. After a series of attempts, one year later Ron Rivest, Adi Shamir, and Leonard Adleman proposed a suitable oneway function based on prime factorisation.
Prime factorisation is simply a way of expressing a number as a product of its prime factors. This is a suitable oneway function as given two prime numbers it is straightforward to calculate their product. However, given only the product it is computationally hard to find that products prime factors.
One of the reasons prime numbers are so fundamental in cryptography is because when you multiply two together, the result is a number that can only be broken down into those primes (and itself and 1).
Here is a working example of the RSA algorithm:
 Choose two random prime numbers
p
andq
. Typically these two numbers will be very large and chosen at random. These are kept secret.
p = 3, q = 11
 Compute
n = p * q
.n
is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
n = 3 * 11 = 33
 Compute
φ(n) = (p  1) * (q  1)
.φ(n)
is kept secret.
φ(n) = (3  1) * (11  1) = 2 * 10 = 20
 Select an
e
such that1 < e < φ(n)
ande
andφ(n)
are coprime.e
becomes the public key.
e = 7
Two integers a and b are coprime if the only positive integer that divides both of them is 1.
 Compute d such that
(d * e) % φ(n) = 1
.d
becomes the private key.
d = 3 as (3 * 7) % 20 = 1
 Set the public key and modulus
public_key = (e, n) => (7, 33)
 Set the private key and modulus
private_key = (d, n) => (3, 33)
This is simplified and using much smaller numbers compared to secure systems. The maths required is based on Modular arithmetic, Euler's theorem, Extended Euclidean algorithm and Euler's totient function.
Encryption and decryption using the public and private keys is defined as follows:
Encryption
cipher_text = (plain_text ^ public_key) mod n
Decryption
decrypted_cipher_text = (cipher_text ^ private_key) mod n
We can now test that the public and private keys we generated work by encrypting and decrypting some plaintext:
 Choose plaintext to encrypt
plain_text = 2
 Encrypt the plaintext with the public key
cipher_text = (2 ^ 7) % 33 = 29
 Decrypt the cipher text with the private key
decrypted_cipher_text = (29 ^ 3) % 33 = 2
 Ensure the original plaintext matches the decrypted cipher text
plain_text (2) == decrypted_cipher_text (2)
This works with any encoded plaintext string
Now, if Alice and Bob need to privately communicate, Alice can send Bob her public key 7
and the modulus 33
. Bob can use these to encrypt some plain text 2
. The cipher text 29
can now be sent back to Alice who can decrypt it using her private key 3
.
As mentioned, the one way function in RSA comes from the fact that factorising n
(which is public) into its component primes (p
and q
) is computationally very difficult when sufficiently large and random prime values for p
and q
are selected.
However, in more recent years some algorithms have been created to handle the problem of prime factorisation and have been relatively successful in doing so.
Elliptic Curve Cryptography
Similarly, to RSA, Elliptic Curve Cryptography (ECC) is another publickey cryptosystem. ECC is based on the algebraic structure of elliptic curves over finite fields and uses a trapdoor oneway function based on the the discrete logarithm problem. ECC is seen as a suitable successor of RSA as ECC uses smaller keys than RSA with the same level of security and is faster at key generation, agreement, and signatures.
Elliptic Curves
An elliptic curve is a curve in mathematics which satisfies the equation
y^2 = x^3 + ax + b
ECC algorithms can use many different underlying elliptic curves. Different curves provide different levels of security, performance, and key lengths.
One of the most widely used elliptic curves is secp256k1
which has a key length of 256bits. This is the elliptic curve used in both Ethereum and Bitcoin and is defined as
y^2 = x^3 + 7
Where a = 0
and b = 7
A typical elliptic curve takes the following form
Elliptic Curves over Finite Fields
In order for the cryptography to work the elliptic curves used in ECC are set to be over a finite field p
where p
is prime and greater than 3.
A finite field is a field that contains a finite number of elements rather than being continuous over all real numbers. This means that the points on an elliptic curve over a finite field are limited to integer coordinates within the field and any algebraic operation will result in another point within the field.
An elliptic curve over a finite field can be defined as
y^2 ≡ x^3 + ax + b (mod p)
The mod p
indicates that this curve is over a finite field of prime order p
.
The secp256k1
curve can be defined over a finite field as
y^2 ≡ x^3 + 7 (mod p)
Elliptic Curves over Finite Fields Arithmetic
To calculate if a point (x,y)
belongs to an elliptic curve over a finite field we can check that
x^3 + ax + b  y^2 ≡ 0 (mod p)
If the result of the above operation is zero then that point lies on that elliptic curve, otherwise it does not.
When two points on an elliptic curve over a finite field are added together the result is another point on the elliptic curve.
T + Q = P
If both T
and Q
are both points on the same elliptic curve over a finite field, the result of the above operation will result in P
which will also lie on the same elliptic curve.
Similarly we can add a point to itself multiple times and the result will be another point on the same elliptic curve
T + T + T + T = F
We have now defined elliptic curve multiplication:
T * k = F
Meaning any point T
on an elliptic curve over a finite field can be multiplied by an integer k
and the result will be another point F
on the same elliptic curve.
With this arithmetic we can now create publicprivate keys using ECC.
ECC Keys
In ECC, private keys are simply random integers in the range of the order of the elliptic curve.
The order of the elliptic curve used in Bitcoin and Ethereum for instance is 2^256 (about 78 decimal digits). To create a private key, we randomly pick a 256bit number. One way this can be done is by taking an even larger string of random bits generated by a cryptographically secure source of randomness and hashing them using a 256bit hash algorithm such as SHA256.
It's interesting to note just how large the 2^256 key space is, especially considering this is the key space that all Ethereum and Bitcoin private keys are in. 2^256 is roughly equal to 10^77 in decimal. There is an estimated 10^80 atoms in the universe. This means there is almost enough private keys for every atom in the universe. Provided the private key you select is sufficiently random there is no way anyone else will also select that number as their private key.
The order of the elliptic curve used in Ethereum and Bitcoin is actually slightly less than 256bits but this is easy to account for when we generate the private key by checking it is within the allowable range.
In ECC, a public key is a (x,y)
point on an elliptic curve. This point is calculated using the private key (an integer) and a point G
on the elliptic curve.
public_key = private_key * G
Where G
is a constant known as the generator point and *
is the elliptic curve multiplication operator. We know from the above arithmetic that multiplying a point G
on an elliptic curve by an integer k
(the private key) will result in another point (the public key) that will lie on the same elliptic curve as G
.
This operation is a one way operation. It is trivial to calculate the public key knowing the private key but you cannot find the private key only knowing the public key. This reverse operation, which would be simple division with normal numbers, is known as finding the discrete logarithm in elliptic curve arithmetic. Calculating the private key when you only know the public key is as difficult as trying a brute force search of the entire key space for all possible values of the private key  needless to say this would take a very long time!
Elliptic Curve Diffie–Hellman Key Exchange
Going back to the initial problem with Alice and Bob, we can use Elliptic Curve Cryptography as an anonymous key agreement scheme. This is known as Elliptic Curve Diffie–Hellman Key Exchange (ECDH). ECDH allows Alice and Bob to generate a shared secret over an unencrypted channel provided both Alice and Bob have a public/private key pair generated from an elliptic curve. The idea is similar to RSA discussed above but it uses ECC multiplication rather than modular exponentiations. All that is required is that Alice and Bob agree on an elliptic curve to use and a generator point G
. All of which can be done in public.

Alice then randomly selects a private key:
alice_private

Alice creates her public key:
alice_public
alice_public = alice_private * G

Bob randomly selects a private key:
bob_private

Bob creates his public key:
bob_public
bob_public = bob_private * G

Alice and Bob can then share their public keys over an insecure channel.

Alice can now calculate their shared secret:
secret_key
secret_key = bob_public * alice_private
 Bob can now calculate their shared secret:
secret_key
secret_key = alice_public * bob_private
 Alice and Bob have now generated the same secret key without ever revealing their respective private keys.
The above key agreement relies on the fact that
(alice_private * G) * bob_private = (bob_private * G) * alice_private
Only the holders of the private keys corresponding to the two public keys that have been shared will be able to calculate the correct secret key. We have now solved the key distribution problem using Elliptic Curve Cryptography.
References
Note: these references exclude hyperlinks included throughout the document.