There may be errors and gaps in this post, so just use it for a broad understanding. Better resources, like the one linked above, are available if you're looking for a detailed description.
Prerequisites for Elliptic curves
Modular Arithmetic
Cryptography doesn't operate on real numbers or integers.
Computation is often performed modulo prime .
Set of integers modulo is
This just means that for any calculation, you take the normal result and take .
Imagine a clock with instead of . So anything that overflows wraps around.
Abelian Group
It is a set together with an operation . The operation combines two elements of the set, denoted for .
The operation must satisfy the following requirements:
Closure: For all , the result of the operation is also in .
Commutativity: For all we have .
Associativity: For all we have .
Identity element: There exists an element , called the identity element or neutral element, such that for all we have .
Inverse element: For every there exists an element such that , where is the identity element.
Examples of Abelian groups
and the standard addition operator
Closure: Addition of any two integers is always an integer.
Commutative: For any two integers .
Associativity: For any three integers .
Identity element: .
Inverse element: For any integer , is the inverse element.
, and addition modulo
Closure: .
Commutative: .
Associativity: For any three integers . This can be seen by simplifying both the sides as both of them are equivalent to .
Identity element: .
Inverse element: For any integer , is the inverse element.
Is an abelian group? Here is the normal multiplication operator.
There are non-abelian groups which have to satisfy all the above properties except commutativity.
Order of a group Number of elements in set is referred to as the order of that group.
Fields
Where in defining a group, we only need one set and one operator , finite fields requires one set and 2 operators . We call these operators addition and multiplication but they can be defined arbitrarily as long as all these properties are satisfied:
is an abelien group with some identity element . Let's call this identity element . This is just a notation and this need not be the literal integer .
The set (set except the element ) and the operator is an abelian group with an identity element denoted as .
This distribution law is satisfied: .
Examples of fields
The set of all real numbers and the usual addition () and multiplication operator () form a field.
form a finite field (field with finite elements).
Cyclic groups
Take any group with set with an operator and identify element .
Take any element , and consider the set: . If we use the shorthand and ( times), the set can be written as: . That's why this set is often referred to as the set of power of . These element are always in due to closure property. Hence, the set of powers of is a subset of .
This new set is also a group (you can go through the properties) and is called a subgroup of generated by . The order of the group element is defined to be the number of elements in the subgroup generated by .
If is finite, then this subgroup is also finite and hence should start repeating at some point. Why? Consider the sequence and so on. Since it's a finite sequence, at some point point it will see a duplicate element, after which the subsequent elements will all be duplicate.
There can be cases where this subgroup is exactly equal to , which means generates the entire group. When this happens, order of is the same as the order of the group . is now called a generator of the group , and is called a cyclic group. The cyclic group can be written as:
Exercise
Q1. Compute the inverse of when is a generator of the group .
A1. Since , is the inverse of .
Fact Group with a prime number order is always cyclic. That means the group is cyclic.
Finite field
From now on, we'll only consider a finite field defined as .
We want to implement addition, multiplication, subtraction and division on this finite field. We define addition as , multiplication as .
To do , we can rewrite it as . We can interpret as the additive inverse of . Hence, . Remember that is an abelian group.
To do , we can rewrite it as . Remember that is an abelian group. So, except for (on which division isn't defined anyways), we can find (called multiplicative inverse because we are considering the multiplication operator).
Fact ; called Fermat’s little theorem.
Elliptic Curves
Finally!
Elliptic curve defined over is an equation: where satisfy .
and has to be in , and any coordinate satisfying this equation belongs in .
We now define as an abelian group by adding the identity element (also called point at infinity). Remember that a group need not have only integers. Element can be anything as long as its properties are satisfied.
To define it as a group, we need to define . It's not the simple addition operator. We define this operator according to the Chord-and-tangent rule. I am not adding it here as it's not important for this high-level discussion, but you'll find plenty of resources online.
What you need to know is:
is the identity element. That means for any , .
Inverse of is . That means . Note that if satisfies the elliptic curve equation, does too. Also, notice that if is of the form , it is its own inverse.
We have well-defined formula to calculate and .
With this, becomes a finite and cyclic group. Let's denote the order of this group by .
Scalar multiplication
Scalar multiplication is multiplying any non-negative integer with a group element in . So ( times).
If is a generator of , you can derive all the group elements by going over different .
secp256k1 curve used in Ethereum
Ethereum uses an elliptic curve called secp256k1 defined over the finite field (for public key generation). It's equation is:
with .
Order of this elliptic curve group is 115792089237316195423570985008687907852837564279074904382605163141518161494337
A specific generator is picked : 55066263022277343669578718895168534326250603453777594175500187360389116729240 32670510020758816978083085130507043184471273380659243275938904335757337482424
This curve is used for key generation and signatures (for example, transaction signing) in Ethereum.
This is how it looks when defined over real numbers:
Image Not ShowingPossible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
There is no point in visualizing it over the field as there is no pattern there.
Private and public key generation for Ethereum
This is the process followed to generate keys for Ethereum:
Generate a random scalar value . This becomes your secret key.
becomes your public key.
Hash the public key using keccak256 and take the last 20 bytes. This is the your Ethereum EOA address.
Given the value , it is computationally hard to derive from it, so consider this impossible for randomly generated secret key. Otherwise, anyone would be able to derive your private key from your public key and this time Ethereum (and much more) will actually break.
This is called the elliptic curve discrete logarithm problem.
Cryptographic signature
Given a message and a private key (with corresponding public key ):
is a byte sequence called "signature".
returns true if the signature is correct, otherwise false.
It can be used for authentication.
Ethereum uses it for transaction authentication.
This can also be used in smart contracts. For example, ERC20 permits.
Specifically, ECDSA signature (a specific signature algorithm based on elliptic curves) is used by Ethereum for this purpose.
ECDSA signature
Heavily inspired from cryptobook.nakov.com. Signature algorithm takes a message and a secret key and produces signature which is a sequence of bytes.
Take a hash of your message . When you issue a transaction on Ethereum, it is the JSON with fields like "to", "value", "data" and so on. Ethereum uses keccak256 hash which outputs a 256 bit output .
Generate a random scalar value .
Calculate and take its coordinate. We denote it as .
Calculate .
is a value such that (you may know it as multiplicative inverse).
is your signature.
ECDSA verification
Verification algorithm takes the signature, message and a public key and verifies signature validity.
I'll defer the rest to this amazing post by Svetlin Nakov on cryptobook.
There is always more nuance to add and more details to cover, but I hope this gives you a good idea on what's going on behind the scene when you create a key pair in your Ethereum wallet.
For feedback and errors, please reach out on Twitter @blockdeveth!