This is the first part of a series of articles explaining how cryptography in Ethereum works. The article does not assume any prior knowledge about cryptography and its mathematical foundations; it covers the absolute basics and delves into the details of how asymmetric encryption works.
Special thanks to Waylon Jepsen for the wonderfully pedantic and thoughtful feedback and guidance.
Cryptography is a branch of mathematics concerned with the secure transmission and protection of information. It is one of Ethereum’s technological pillars. It safeguards information by encoding it so that only the intended recipients can understand and process the information.
There are two different types of accounts in Ethereum: Externally Owned Accounts (EOAs) and contracts. EOAs have key pairs consisting of a private key and a public key. Private keys, along with digital signatures and Ethereum addresses, prove the ownership of the funds and assets in EOAs.
All user interaction with Ethereum is made possible using private keys. A private key uniquely determines an Ethereum address, which represents the intended recipient of a transaction. When you send a transaction on Ethereum, you need to digitally sign a message– this digital signature is also created using the private key. Anyone who has an account’s private key has full control of the funds and assets it holds. Keep your private key to yourself!
How is a public key derived from a private key? How do we prove ownership of an account without having to reveal our private key? How are digital signatures unique? Well, we need to start with the basics of cryptography to answer these questions. The topics we’ll cover are:
-
Cryptography basics and mathematical foundations,
-
Cryptographic hash functions and uses
-
Symmetric, Asymmetric cryptography
-
Elliptic curve cryptography, and
-
Digital Signatures: ECDSA.
Trigger warning: Math; it is optional and there is no test at the end. But give it a few minutes and you’ll understand everything better.
Cryptography Foundations
Trapdoor Functions
In mathematics, we have some functions that are easy to calculate but their inverses aren’t. For example, finding the product of two large prime numbers is straightforward. But given the product of two large primes, it is difficult to find its prime factors.
If you had some secret information, it’d be easy for you to invert some of these functions. Such functions are called trapdoor functions. For example, if you know one of the prime numbers in the previous example, it is trivial to find the other via simple division. Trapdoor functions are not used in cryptography to avoid loopholes in cryptographic protocols. If they were, secret information would be revealed.
An advanced category of mathematical functions based on elliptic curve arithmetic is used in cryptography. It is easy to find the product of two large prime numbers modulo a prime, but given the result, we can’t find the two prime factors. This is called the Discrete Logarithm Problem (DLP). DLP over certain groups has no trapdoors– this acts as a foundation for a large number of cryptographic protocols.
Modular Arithmetic
In mathematics, modular arithmetic is a system of integer arithmetic where numbers wrap around when they reach a certain value, called the modulus. The modulo operation returns the remainder when one number is divided by another. For example, 11 mod 3 evaluates to 2 because we get a quotient of 3 and a remainder of 2 when we divide 11 by 3.
For a positive integer n, two integers a and b are called congruent modulo n if a and b differ by a multiple of n. That is, for an integer k,
a − b = kn
Congruence modulo n is denoted as:
a ≡ b (mod n).
The parentheses here mean that (mod n) applies to the entire equation, and not just the right-hand side. This is different from the binary operation “a mod b”, which refers to the modulo operation and simply returns the remainder after a is divided by b.
a ≡ b (mod n) implies that a and b have the same remainder when they are divided by n. That is,
a = pn + r
b = qn + r
where r is the common remainder such that 0 ≤ r < n. For example,
38 ≡ 3 (mod 5) holds because 38 — 3 = 35, which is a multiple of 5. 38 and 3 also have the same remainder 3 when divided by 5.
The DLP can be stated as:
a, b and m are three integers. Find an integer k such that aᵏ ≡ b (mod m), where the greatest common divisor of a and m is 1.
Fields
A field is a set F with two binary operations on F called addition and multiplication, denoted using + and ⋅ respectively. These operations must satisfy the following properties, called the field axioms:
-
Associativity of Addition and Multiplication: a + (b + c) = (a + b) + c, and a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c.
-
Commutativity of Addition and Multiplication: a + b = b + a, and a ⋅ b = b ⋅ a.
-
Additive and Multiplicative Identity: there exist two different elements 0 and 1 in F such that a + 0 = a and a ⋅ 1 = a.
-
Additive Inverse: for every a in F, there exists an element -a ∈ F, called the additive inverse of a, such that a + (-a) = 0.
-
Multiplicative Inverse: For any a ∈ F such that a ≠ 0, there exists a⁻ ¹ ∈ F called the multiplicative inverse of a, such that a ⋅ a⁻ ¹ = 1.
-
Distributivity of Multiplication Over Addition: a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c).
In these axioms, a, b and c are arbitrary elements in the field F.
Cryptographic Hash Functions
Hash functions are used in computer programming to convert text (or other data) to integers. The process of calculating the value of a certain hash function is called hashing. Hashing usually maps distinct inputs to distinct outputs, but there might be collisions sometimes. Since hashing is irreversible by design, there are no quick algorithms for recovering the input message from its hash value.
In cryptography, hash functions convert arbitrary-sized input data (e.g. a message) to a fixed-size result (e.g. 256 bits). The result is called a hash value (hash code, message digest, or simply hash). Hash functions utilized in cryptography are called cryptographic hash functions. These are one-way hash functions that are infeasible to invert. The likelihood of finding a collision via brute force for a strong cryptographic hash function, like SHA-256, is extremely low. There are no known collisions for most modern strong cryptographic hash functions.
The ideal cryptographic hash function is:
-
Deterministic: Given a fixed input, the value of the output will never change.
-
Quick: Computing the hash for any message should be efficient (linear complexity).
-
Difficult to Decipher: A small change in the message will result in an extensive change in the hash value. Hence, we cannot derive any information about the original message from its hash value.
-
Irreversible: Deriving an input message from its hash should be computationally infeasible. This implies that using brute force (trial and error) is the best approach for doing so.
-
Collision Resistant: Finding two input messages with the same hash should be computationally difficult.
The Secure Hash Algorithms (SHA) are a family of cryptographic hash functions published by the National Institute of Standards and Technology. SHA-3 functions are deemed more secure than SHA-2 functions. The SHA-3 family of cryptographic hash algorithms, unlike SHA-2, is not prone to length extension attacks*.* In a length extension attack, a hacker can create a valid new hash by extending an existing one without knowing the original message or the private key used to create the hash.
The “Keccak” hashes family represents the SHA-3 hashes family and is based on the concept of “sponge construction”. Ethereum uses a variant of SHA-256 called Keccak-256.
SHA3–256('hello') = 3338be694f50c5f338814986cdf0686453a888b84f424d792af4b9202398f392
Keccak-256('hello') = 1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8
SHA3–512('hello') = 75d527c368f2efe848ecf6b073a36767800805e9eef2b1857d5f984f036eb6df891d75f72d9b154518c1cd58835286d1da9a38deba3de98b5a53e5ed78a84976
Random Number Generators
Randomness is crucial in cryptography. For example, we need a private key to access the assets in an Ethereum account. This private key should be randomly generated in a way that no one else can generate it. If a secure random number generator is used, the key will be unpredictable and the system will be secure. Hence, “secure random” simply just means “unpredictably random”.
In computer science, random numbers usually come from Pseudorandom Number Generators (PRNGs). The sequence of random numbers generated by a PRNG is deterministic and not truly random, as it is entirely determined by an initial value, called the PRNG’s seed. If a PRNG gets hacked, it will generate predictable random numbers. This allows hackers to reveal your private keys, sign malicious messages, and so on. Hence, it is essential to generate “truly random” numbers.
CSPRNG
Cryptographically Secure PRNGs (CSPRNGs) are used in cryptography to make the generated randomness unpredictable. By definition, CSPRNGs are pseudo-random number generators with properties that make them suitable for use in cryptography. They often combine entropy with PRNG and other approaches. To be a CSPRNG, a PRNG must meet two major requirements:
-
Satisfy the next-bit test: If someone knows all k bits from the start of the PRNGs, they wouldn’t be able to predict the bit k + 1 with reasonable computing resources.
-
Withstand the state compromise extensions: If an attacker guesses the internal state of the PRNG or it is revealed in some way, the attacker should be unable to reconstruct all previous random numbers before the revelation.
The operating system’s entropy is usually limited. Most cryptographic applications employ CSPRNGs, which “stretch” the OS’s available entropy into more bits needed for cryptographic purposes by using cryptographic hash functions while adhering to the CSPRNG criteria.
Most CSPRNGs use a combination of entropy from the operating system and a high-quality PRNG generator, and they frequently “reseed,” which means that when new entropy comes from the OS (for example, from user input, system interruptions, disc I/O, or hardware random generators), the underlying PRNG changes its internal state based on the new entropic bits. The CSPRNG is extremely difficult to predict and analyze due to its continual reseeding.
PoW Hash Functions
The majority of Proof of Work (PoW) algorithms generate a hash value greater than a certain threshold, known as mining difficulty. Blockchain PoW mining algorithms employ a special class of computationally and memory-intensive hash functions. Since hashes are random, miners calculate millions of distinct hashes to determine this hash value. For example, the PoW problem might be defined as:
find a number p, such that the hash(x + p) starts with 10 zero bits.
ASIC-resistance refers to a cryptocurrency’s protocol and mining algorithms being configured in such a way that employing ASICs for mining is either impossible or provides no substantial advantage over standard GPU mining. Blockchains that rely on other methods of reaching consensus (like PoS, dPoS, PoA) are ASIC-resistant by design. ASIC-resistance in PoW blockchains is determined by the implementation of the mining algorithm — Bitcoin is not ASIC-resistant, while Ethereum is. This is due to Ethereum’s adoption of the ETHash proof-of-hash function. It’s a memory-intensive hash function, meaning that it needs a lot of RAM to be calculated quickly, making it resistant to ASICs. This is how ETHash works:
-
A “seed” is computed for each block based on the entire chain until the current block.
-
From the seed, a 16 MB pseudorandom cache is computed.
-
From the cache, a 1 GB dataset is extracted to be used in mining.
-
Mining involves hashing together random slices of the dataset.
ASIC resistance is desirable– it increases a blockchain’s degree of decentralization and makes mining affordable for everyone. A small number of large players is bad, and a large number of small players is good.
Symmetric Cryptography
Symmetric encryption schemes use the same secret key (or password) to encrypt data and decrypt it back to its original form.
The figure here is simplified. Usually, the encryption scheme consists of:
-
Password to key derivation algorithm
-
Cipher algorithm
-
Cipher block mode algorithm
-
Message authentication code (MAC) algorithm.
The secret key used to cipher (encrypt) and decipher (decrypt) data is commonly 128, 192, or 256 bits in length and is sometimes referred to as an encryption key or a shared key because both the sending and receiving parties should know it. Most applications use a password-to-key-derivation scheme to extract a secret key from a certain password because users tend to remember passwords easier than binary data. A 256-bit secret key encoded as a hex string look like:
02c324648931b89e3e8a0fc42c96e8e3be2e42812986573a40d46563bceaf75110
Asymmetric Cryptography
Asymmetric cryptography or Public Key cryptography utilizes a pair of cryptographically related public and private keys to encrypt and decrypt data. If the data is encrypted using a private key, it can be decrypted using the corresponding public key and vice versa. As a result, someone can prove they own a certain private key while just revealing the public key that corresponds to it. RSA and ECC are two widely used public key cryptographic protocols.
The RSA public-key cryptosystem is based on the math of modular exponentiation (numbers raised to a power by modulus) and some additional assumptions, along with the computational difficulties of the integer factorization problem. Elliptic curve cryptography (ECC) is based on the algebraic structure of elliptic curves over finite fields and the complexity of the Elliptic Curve Discrete Logarithm Problem (ECDLP).
ECC is usually used in conjunction with the Elliptic Curve Digital Signature Algorithm (ECDSA). ECC uses smaller keys, ciphertexts and signatures than RSA, and is preferred for most applications. It has been proven mathematically that a 3072-bit RSA key has similar cryptographic strength to a 256-bit ECC key. ECC’s key generation is also significantly faster than RSA’s.
Blockchains like Bitcoin and Ethereum use ECC to secure transactions. It is worth noting that neither RSA nor ECC is quantum-safe, which means if someone has a powerful enough quantum computer, they’ll be able to derive the private key from a public key in a matter of seconds. While this is true, it is unlikely that there will be a powerful quantum computer anytime soon(next 5–10 years), and we have already constructed quantum resistance asymmetric cryptography like learning with errors.
Key Pairs
A pair of keys is used in public key cryptography — a public key and a private key. These keys are linked mathematically and are used together as a pair. A user controls their Ethereum account using the private key (like a password), while the public key is used to identify an account, similar to a bank account number. In ECC, the private key is used to calculate the public key, which is used to further derive an Ethereum address. In other cryptosystems (like RSA), the public key and private key are generated together but can’t be determined directly from each other.
A key pair is often generated at random in a secure environment (like a hardware wallet) and the public key is revealed, while the private key is secret and is securely stored in a crypto-wallet and is protected by a password or multi-factor authentication. Keep your private key safe, anon.
Randall Munroe shows the inner workings of the mind of a BAYC owner:
Elliptic Curve Cryptography
Elliptic curve cryptography (ECC) is a modern family of public-key cryptography systems, based on the algebraic structures of elliptic curves over finite fields and the complexity of the Elliptic Curve Discrete Logarithm Problem (ECDLP). ECC is the modern natural successor to RSA — it uses smaller keys and signatures than RSA for the same level of security, and provides fast operations (key generation, key agreement, signatures).
The DLP is based on the idea that it is difficult to factor a large integer composed of two large primes. This idea is then extended and modified for ECC protocols as — finding the discrete logarithm of a random elliptic curve element w.r.t. a publicly known base point is impossible. The difficulty of the problem is determined by the size of elliptic curve’s field.
Elliptic Curve Keys
ECC keys are integers in the range of the curve’s field size (typically 256-bit integers). Any number in this range is a valid ECC private key. Private key generation is as simple as securely generating a random number within a certain range.
In ECC, public keys are EC points, which are a pair of integer coordinates {x, y} on a curve. The EC points have special characteristics. They can be reduced to a single coordinate plus one parity bit (parity). This compressed public key is a 257-bit integer that corresponds to a 256-bit ECC private key. It is represented in the Ethereum format using 33 bytes (66 hex digits) and is optimized to exactly 257 bits.
Curves and key length
ECC algorithms can use different underlying elliptic curves. These curves that have been adopted in popular cryptography frameworks and security standards have:
-
a name : such as secp256k1, Curve25519
-
a field size: this determines the key length
-
security strength: usually fieldSize / 2 or less
-
performance : operations / sec
In most applications, the default ECC private key length is 256 bits.
Elliptic Curves
All elliptic curve algorithms use an underlying curve for calculations. They use public-private key pairs, where:
-
the private key is an integer, and
-
the public key is a point on the elliptic curve.
But first, what are elliptic curves?
In mathematics, elliptic curves are plane algebraic curves consisting of all points {x,y} described by the equation of a general cubic curve.
In cryptography, elliptic curves are used in a simplified form (Weierstrass form). For a field characteristic not equal to 2 or 3, the equation can be written as:
y² = x³ + ax + b
This equation when used with different values of a and b, gives us different curves. For instance, the secp256k1 curve used by Bitcoin and Ethereum uses a = 0 and b = 7 :
y² = x³ + 7
Elliptic Curves Over Finite Fields
Let p > 3 be a prime. An elliptic curve E defined over Fₚ is an equation y² = x³ + ax + b, where a, b ∈ Fₚ satisfies 4a³ + 27b² ≠ 0. We write E/Fₚ to denote the fact that E is defined over Fₚ. The condition 4a³ + 27b² ≠ 0 ensures that the equation x³ + ax + b does not have a double root. This is because the curve is required to be non-singular, which means that it has no cusps or self-intersections. This is needed to avoid certain degeneracies.
Elliptic curve cryptography makes use of elliptic curves in a finite field Fₚ , where p is a prime number greater than 3. The field is a p*p square matrix in which the points on the curve are limited to integer coordinates within the field only. This is done using the modulus operation to make the values wrap around when they reach the modulus p. All algebraic operations within the field result in another point in the field. The equation of an elliptic curve in a finite field Fₚ takes the modular form:
y² = x³ + ax + b (mod p)
The secp256k1 curve equation becomes: *y² = x³ + 7 *(mod p)
ECC uses points {x,y} in the Fₚ (x,y ∈ [0…p-1]). An elliptic curve over the finite field Fₚ consists of a set of integer coordinates {x,y} such that 0 ≤ x and y < p that stay on the elliptic curve y² = x³ + ax + b (mod p).
Point Arithmetic
When two EC points are added, the result is another point on the same EC. This operation is called EC point addition. When we add a point G to itself, we get
G + G = 2 ⋅ G
Doing this again, we get G + G + G = 3 ⋅ G
This is how EC point multiplication is defined.
When we multiply a point G on an EC with an int k, we get another point P on the same EC. This is a fast operation. P = k ⋅ G
Multiplying an EC point with 0 gives a special EC point called “point at infinity”.
Order and cofactor
The total number of points on an elliptic curve, including the point at infinity, is called its order. An elliptic curve over a finite field can form a finite cyclic algebraic group, which contains all of the curve’s points. In a cyclic group, when two EC points are added or an EC point is multiplied by an integer, the result is another EC point in the same cyclic group (and on the same curve). ECs can be divided into two categories based on their cyclic groupings:
-
Some curves form a single cyclic group that holds all their EC points,
-
While others form several non-overlapping cyclic subgroups, where each holds a subset of the curve’s EC points.
In the latter category, the points on the curve are divided into h cyclic subgroups or partitions, each of which has an order of r. The order of the whole group, n = h * r
The number of subgroups holding EC points is called the cofactor, h.
h = n / r, where
-
n is the degree of the curve — or the number of all points on the curve.
-
h is the curve cofactor — the number of non-overlapping subsets of points that contain all curve points together.
-
r is the order of the subgroups — the number of points in each subgroup, including the point at infinity for each subgroup.
The cofactor for the elliptic curve used by Ethereum (secp256k1) is 1.
Generator point
For elliptic curves over finite fields, the elliptic curve cryptosystems define a special pre-defined (constant) point called generator point or base point. This point can be used to generate any other point in its subgroup over the elliptic curve by multiplying G with some integer in the range [0…r], where r is the order of the cyclic subgroup.
The total number of private keys for this curve is determined by the order r of the subgroup (which may differ from the order of the curve) obtained from EC generator point G.
r = n / h
The elliptic curve domain parameters are chosen carefully to ensure the key space is large enough for certain cryptographic strength. EC subgroups usually have many generator points. Out of these, one is selected carefully, from which all points in the subgroup can be obtained. This point should also be suitable for performance optimization in computations. This generator point is called G.
Some points used as generators for the same curve will generate smaller subgroups than others. The smaller a subgroup, the weaker the security it provides — known as “small subgroup attacks”. This is also the reason why the subgroup order r is usually chosen as a prime number.
Private Key, Public Key and Generator Point
In ECC, when we multiply a fixed EC point G (the generator point) with a certain integer k (the private key), we obtain another EC point P (the public key). It is very fast to calculate P = k * G using well-known ECC multiplication algorithms. It will require just a few hundred basic EC operations for 256-bit curves.
Calculating k = P / G is extremely slow (infeasible for large values of k). This asymmetry — quick multiplication and really slow other operation — is the foundation of ECC’s security strength. This is also known as the ECDLP.
ECDLP
In computer science, the Elliptic Curve Discrete Logarithm Problem or ECDLP is defined as: Given an elliptic curve over a finite field Fₚ, a generator point G on the curve, and another point P on the curve, determine the integer k (if it exists) such that P * k = G.
Exponentiation of integers in group Zₚ (field of integers) is analogous to multiplying EC points in group Fₚ . ECDLP resembles the discrete logarithm problem in this manner. Many ECC algorithms rely on the ECDLP’s computational difficulties over a carefully chosen field Fₚ and elliptic curve, for which there are no efficient algorithms.
Curve Security Strength
The fastest known algorithm to solve ECDLP for the key size k requires √k steps. To achieve a k-bit security strength, at least a 2*k-bit curve is needed. Typically, 256-bit elliptic curves (where p is a 256-bit value) provide nearly 128-bit security strength.
In actuality, the strength is slightly lower because:
-
The order of the curve (n) is usually smaller than the size of the field (p).
-
The curve may have a cofactor (h) greater than 1.
-
The number of steps isn’t exactly √k but 0.886 * √k .
As a result, the secp256k1 curve offers 127.8-bit security.
Public Key Compression
Elliptic curves over a finite field Fₚ have at most 2 points for every x coordinate– odd y and even y (shown below for the secp256k1 curve). This property comes from the nature of the elliptic curve equation.
Due to this property, an elliptic curve point (and hence an ECC public key) P {x, y} can be compressed as C {x, odd/even). We erase the y coordinate from the elliptic curve point and represent it using a bit to denote an odd or even y. Since ECC public keys are just EC points, they can also be compressed in the same way.
To decompress a point, we first calculate the two possible y coordinates using the formulae:
-
y₁ = mod_sqrt(x³ + ax + b, p)
-
y₂ = p − mod_sqrt(x³ + ax + b, p)
The modular square root (mod_sqrt) can be calculated using the Tonelli–Shanks algorithm. We then take the odd or even value from the two, based on the additional parity bit in the compressed representation.
For example: For the elliptic curve y² ≡ x³ + 7 (mod 17), the point P {10, 15} on it can be compressed as C {10, odd}. To decompress the point, we first calculate the two possible y coordinates for x = 10 using the formulae above: y₁ = 2 and y₂= 15. We then choose the odd value: y = 15. Hence, the decompressed point is {10, 15}.
Domain Parameters
Elliptic curves used in ECC are described using a set of domain parameters, such as curve equation parameters, field parameters, and generator point coordinates. These parameters are defined for a set of named curves in cryptography standards like:
All communicating parties should agree on the EC domain parameters to use ECC. In ECC, elliptic curves over finite fields are used. The modulus p and order n are taken to be very large integers (Eg: 256 bit), and n is usually prime. The finite field of the curve has a size of p*p, and all EC points are also very large integers. For instance, the domain parameters for secp256k1 are:
-
p (modulus) = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
-
n (order; size; the count of all possible EC points) = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
-
a (the constant “a” in y² ≡ x³ + ax + b (mod p)) = 0x0000000000000000000000000000000000000000000000000000000000000000
-
b (the constant “b” in y² ≡ x³ + ax + b (mod p)) = 0x0000000000000000000000000000000000000000000000000000000000000007
-
g (the curve generator point G {x, y}) = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
-
h (cofactor, typically 1) = 1
Digital Signatures
Digital signatures are cryptographic tools that are used to sign messages and verify message signatures to validate the authenticity of a message. Digital signatures provide:
-
Message authenticity: proof that the message was created and signed by a specific sender (owner of a private key)
-
Message integrity: proof that a message was not altered after it was signed.
-
Non-repudiation: the signer cannot deny signing the message once the signature has been created.
Digital signature schemes make use of asymmetric cryptography. Digital signatures provide mathematical proof that a specific private (secret) key corresponding to a certain (non-secret) public key was used to sign the message.
Typically the input message is hashed and then the signature is calculated by the signing algorithm. Most signature algorithms perform some operations on the message hash and the private key in a manner that the result cannot be calculated without the private key. The result from message signing is called the digital signature.
The corresponding public key is used to verify digital signatures. The signed message is hashed, and the message hash and public key are used to perform some calculations. The outcome of this message verification is a boolean value (valid or invalid signature).
The most common digital signature schemes are based on the difficulty of the Discrete Logarithm Problem. These aren’t quantum-safe, which means a quantum computer might extract the private key from the signature. Quantum-safe signature schemes exist but aren’t frequently employed because of their limitations — lengthy keys and signatures, as well as sluggish performance.
The digital signature scheme used by Ethereum is ECDSA.
ECDSA
The Elliptic Curve Digital Signature Algorithm is a cryptographically secure digital signature scheme. It is based on the mathematics of cyclic groups of elliptic curves over finite fields and the ECDLP’s difficulty. ECDSA Sign and Verify make use of EC point multiplication.
ECDSA uses shorter keys and signatures than RSA to provide the same level of security– a 256-bit ECDSA signature has the same security strength as a 3072-bit RSA signature.
ECDSA Sign
The process of signing a message using ECDSA:
-
Calculate the message hash, using a cryptographic hash function (Keccak256 for Ethereum): h = hash(msg)
-
Securely generates a random number k in the range [1..n-1], where n is the group order.
In the case of deterministic-ECDSA, the value k is HMAC-derived from h + sk (see RFC 6979) -
Calculate the coordinates (x₁, y₁) for the random point *R using: ***
(x₁, y₁) = k × G -
Calculate r = x₁ mod n. If r = 0, go back to step 2.
-
Calculate the signature proof: s = k − 1 × (h + r × sk)(mod n)
The modular inverse k−1 (mod n) is an integer, such that
k × k − 1 ≡ 1 (mod n). If s = 0, go back to step 3. -
Return the signature {r, s}.
The signature {r, s} is a pair of integers, each in the range [1…n-1]. It comprises the proof s as well as an encoding of the random point R = k × G. This confirms that the signer is aware of the message h as well as the private key sk. The proof s can be verified using the corresponding pk.
ECDSA signatures are twice as long as the private key used during the signing process. For 256-bit elliptic curves like secpk256k1, an ECDSA signature is 512 bits long.
ECDSA Verify
To verify an ECDSA signature, we need to provide three inputs to the algorithm:
-
The signed message msg
-
The signature {r,s} — output of the ECDSA Sign algorithm.
-
The public key pk corresponds to the private key used to sign the message
The output of the ECDSA Verify algorithm is a boolean value: valid or invalid signature. This is how the algorithm works:
-
Verify that r and s are integers in the range [1, n-1]. If not, the signature is invalid.
-
Calculate the message hash, where the hashing algorithm is the one used during signature generation (Keccak256 for Ethereum): h = hash(msg)
-
Calculate the modular inverse of the signature proof: s₁ = s ⁻¹ (mod n)
-
Recover the random point used during the signing: R’ = (h × s1) × G + (r × s1) × pk
-
Take the x-coordinate from R’ : r’ = R’ . x
-
Check whether the signature is valid by comparing if r’ == r
The basic concept underlying signature verification is to recover the point R’ using the public key and compare it to the point R created at random during the signing procedure.
We now know about the state of cryptography in the current PoW Ethereum. But, what changes when we switch to PoS, and why?
Stay tuned for the second part of this series for the answer, coming soon.