# Digital Signatures
Digital signature algorithms allow us to verify the authenticity and integrity of digital documents. They have more advantages than physical signatures, such as being immutable and not easily forged like physical signatures which ensures it integrity.
There are various digital signature algorithms, including Elgamal, RSA, and ECDSA. We'll take a look at ECDSA (Elliptic Curve Digital Signature Algorithm) signatures, how they are generated and verified, and an application of ECDSA in Bitcoin cryptocurrency. After learning and implementing ECDSA, it should be easy to learn other algorithms and use them. [Each has its strengths and weaknesses](https://en.wikipedia.org/wiki/Digital_signature#Some_digital_signature_algorithms), you can explore them and use the one suitable for your application.
## ECDSA Signature
There are three steps involved in the process: key generation, signature generation, and signature verification.
### Key Generation
Key Generation involves the creation of an ECDSA keypair; one private key (a large integer) and one public key (an EC point). In this article we will be using Elliptic Curve $secp256k1$ key generation algorithm to generate this key pair.
There are some fundamental concepts that you need to understand before proceeding such as: Finite fields, Prime field of integers, Elliptic Curve, and how two points on the Elliptic Curve are doubled or added. A good resource is this article: [Elliptic Curves and the Discrete Log Problem](https://enigbe.medium.com/about-elliptic-curves-and-dlp-ed76c5e27497).
If you are already acquainted with these concepts you can move on.
The following steps are used in key generation:
1. Define the Elliptic curve parameters
- The elliptic curve $E$ is defined over a prime field of integers $\mathbb{Z}$ with the equation $y^2 = x^3 + ax + b$
- Select the $a$, $b$ and $p$, variables.
- The number $p$ is a prime number that defines the size of the finite field over which the Elliptic curve $E$ is defined.
- The coefficients $a$ and $b$ are integers within the field defining the shape of the Elliptic Curve $E$.
- $a$, $b$, and $p$ should be chosen such that the resulting Curve has good [cryptographic properties](https://en.wikipedia.org/wiki/Elliptic_curve).
2. Select a Generator point on the Curve, $A (x, y)$ (also known as a base point) is a point on the elliptic curve used to generate other points on the curve.
- Use $A, a , b, p$ to compute the cyclic prime order $q$, this simply means that starting from $A$, you can generate $q$ distinct points by repeatedly adding $A$ to itself. $(i.e., A, 2A, 3A,…, (q−1)A)$. When you reach $qA$, the process cycles back to the identity element (often called the point at infinity $O$). You identify when you reach the identity element when the sum of a point by itself is itself $O+O = O$. Note that $q$ is the cyclic prime order as it will be used heavily throughout this article.
- The generator point $A$ and the order $q$ must satisfy the elliptic curve equation $y^2 = x^3 + ax + b$.
3. Generate a public key $Kpub$
- Choose a random integer $d$ such that $0 < d < q$.
- Compute $B=d⋅A (x, y)$ using the Elliptic Curve point addition and point doubling formulas.
- The public key $Kpub$ is the set $(p, a, b, q, A, B)$.
$secp256k1$ is an example of Elliptic Curve graph parameters which define the $a, b$ and $p$ parameters as $(0, 7, 2^{256} - 2^{32} - 977)$
The resulting equation of $y^2 = x^3 + ax + b$ after substituting the coefficients $a$ and $b$ is; $y^2 = x^3 + 7$.
Over a very large integer $2^{256} - 2^{32} - 977$.
We will demonstrate how to generate a key pair of this form using the [low-level $secp256k1$](https://gist.github.com/ismaelsadeeq/2a4c6382c4b2f811c858ca5ca8f85923) field and group arithmetic implemented in Bitcoin core functional tests.
**Prerequisites**
* Python Environment: Ensure you have Python installed on your system.
Steps
1. Create a new directory:
- Download the [$secp256k1$.py](https://gist.github.com/ismaelsadeeq/2a4c6382c4b2f811c858ca5ca8f85923) file.
- Add this file to your new directory.
2. In the same directory, create a new Python file named `signatures.py`.
- Inside `signatures.py` import the $secp256k1$ library, random number generator library, hashing library and declare constants
```python
import hashlib
import random
import secp256k1
PRIME_FIELD = secp256k1.FE.SIZE
GENERATOR_POINT = secp256k1.G
CYCLIC_PRIME_ORDER = secp256k1.GE.ORDER
```
3. - Define a class which will generate key pair upon initialization.
- Add a method `get_pubkey` that returns the public key.
```python
def generate_random_number(begin, end):
return random.randrange(begin, end)
class KeyPair:
def __init__(self):
# Initialize the private key as a random number between 1 and the cyclic prime order
self.privkey = generate_random_number(1, CYCLIC_PRIME_ORDER)
# Compute the corresponding public key by multiplying the private key with the generator point
self.pubkey = self.privkey * GENERATOR_POINT
def get_pubkey(self):
return self.pubkey
```
Note: In actual projects, do not use pseudorandom number generators; use a [cryptographically secure random number generator](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator). This is important because pseudorandom number generators (PRNGs) like the python `random` library can produce predictable outputs if the initial seed value is known or can be guessed.
### ECDSA Signature Generation
After generating the key pair, we will now use the private key $d$, the Elliptic Curve generator point $A$, and the message we wish to sign to generate a signature through series of steps below.
1. **Compute Ephemeral Key $(K)$**: A randomly selected integer $K$ such that $0 < K < q$.
It is important that the ephemeral key is generated randomly within the cyclic prime order and used only once. Reusing this key can lead to [serious security vulnerabilities](https://crypto.stackexchange.com/questions/64167/ecdsa-with-common-nonce), allowing attackers to recover the private key and thereby forge signatures.
2. **Compute $R$**: $K * A$ using Elliptic Curve point addition and doubling formula.
After multiplying $K * A$, the result will be a point $R$ with coordinates $(x, y)$.
3. **Compute $r$**: $xR \bmod q$, where $xR$ refers to the $x$-coordinate of the point $R$.
4. **Compute $x$**: as the integer representation of the SHA-256 hash of the message.
We first have to convert the text representation of the message to bytes to ensure consistency and compatibility with the SHA-256 hash function. Then, we use the SHA-256 hash function to generate the hash of the byte representation of the message. The generated hash will always be the same, as SHA-256 is deterministic. Finally, we convert the hash to an integer number, which is necessary for subsequent summation with the private key $d$ in the next step.
5. **Compute $s$**: $\left( (x + d \cdot r) \cdot K^{-1} \right) \mod q$.
Substitute all the values into the expression above and compute the result to get the $s$ value of the $s$ component of the signature.
6. **Final Signature**: The final signature consists of the pair of integers $(r, s)$.
### Implementation
We will define some helper functions that will be used in the key generation code.
The `convert_to_bytes` function takes either an integer or a string and converts it to its equivalent byte representation in big-endian format.
```python
def convert_to_bytes(data):
if isinstance(data, int):
bits_per_byte = 8
num_bits = data.bit_length()
# Calculate the number of bytes needed to represent the integer
num_bytes = (num_bits + bits_per_byte - 1) // bits_per_byte
return data.to_bytes(num_bytes, byteorder='big')
elif isinstance(data, str):
return data.encode('utf-8') # Using UTF-8 encoding for consistency
raise TypeError(f"Unsupported type {type(data)}.")
```
`check_type` function checks whether the provided data is of the specified type. If the data is not of the expected type, it raises a `TypeError`.
```python
def check_type(data, type):
if not isinstance(data, type):
raise TypeError(f"data must be of type '{type}'")
```
`compute_sha256_hash` function takes a byte sequence as input and computes its SHA-256 hash. Before performing the hash computation, it verifies that the input is of type `bytes` using the `check_type` function.
```python
def compute_sha256_hash(data):
check_type(data, bytes)
# Compute the SHA-256 hash of some bytes of data
return hashlib.sha256(data).digest()
```
`convert_bytes_to_int` function converts a byte sequence into its equivalent integer representation using big-endian byte order. It also uses the `check_type` function to ensure the input is a byte sequence.
```python
def convert_bytes_to_int(data):
check_type(data, bytes)
# Convert some bytes to its integer representation using big-endian byte order
return int.from_bytes(data, 'big')
```
Next in the KeyPair class add the key generation code below
```python
class KeyPair:
...
def generate_signature(self, message):
check_type(message, bytes)
# Generate an ephemeral key, which is a random number between 1 and the cyclic prime order
ephemeral_key = generate_random_number(1, CYCLIC_PRIME_ORDER)
# Compute R by multiplying the ephemeral key with the generator point
R = ephemeral_key * GENERATOR_POINT
# Extract the x-coordinate of R and reduce it modulo the cyclic prime order
r = int(R.x) % CYCLIC_PRIME_ORDER
# Compute the SHA-256 hash of the message and convert it to an integer
message_hash = compute_sha256_hash(message)
message_hash_int = convert_bytes_to_int(message_hash)
# Calculate the signature's s component using the ECDSA formula
s = ((message_hash_int + (r * self.privkey)) * pow(ephemeral_key, -1, CYCLIC_PRIME_ORDER)) % CYCLIC_PRIME_ORDER
return r, s
```
### ECDSA Signature Verification
Anyone can verify the authenticity of a signature using the public key $B$, the signature $(r, s)$, and the message that was signed.
1. **Compute $x$**:
Calculate $x$ as the integer representation of the SHA-256 hash of the message, just as it was done in the signature generation process.
2. **Compute value $w$ = $s^{−1} \mod q$**:
$s^{−1}$ represents the modular multiplicative inverse of $s$ modulo $q$ .
3. **Compute value $u1$ = $(w * x) \mod q$**:
$u1$ is calculated by multiplying $w$ with the integer representation of the hash of the message, then taking the result modulo $q$.
4. **Compute value $u2$ = $(w * r) \mod q$**:
$u2$ is obtained by multiplying $w$ with $r$ (part of the signature), then taking the result modulo $q$.
5. **Compute point $P$ = $(u1 * A) + (u2 * B)$**:
Where $A$ is the generator point and $B$ is the public key point.
6. **Compute $xP$**:
Once we have the point $P$, we extract its $x$-coordinate $xP$. This value will be compared against the original signature component $r$.
7. **Verification**:
If $xP \mod q$ is the same as $r$, the signature is valid; otherwise, it is not.
Code Implementation
```python
def verify_ecdsa(signature, pubkey, message):
check_type(message, bytes)
r, s = signature
w = pow(s, -1, CYCLIC_PRIME_ORDER) % CYCLIC_PRIME_ORDER
message_hash = compute_sha256_hash(message)
message_hash_int = convert_bytes_to_int(message_hash)
u1 = (w * message_hash_int) % CYCLIC_PRIME_ORDER
u2 = (w * r) % CYCLIC_PRIME_ORDER
P = (u1 * GENERATOR_POINT) + (u2 * pubkey)
xP = int(P.x) % CYCLIC_PRIME_ORDER
return xP == (r % CYCLIC_PRIME_ORDER)
```
There exists a mathematical proof that shows that [$xP == r \mod q$](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Correctness_of_the_algorithm)
### Testing the signature generation and verification
We will be modifying the signature to test for malleability, invalidity, and at last a valid signature.
```python
def verification_test_ecdsa(signature, pubkey, message_bytes):
print("ECDSA signature verification")
r, s = signature
# Test 1: Modify r slightly
is_valid_modified_r = verify_ecdsa((r + 1, s), pubkey, message_bytes)
print(f"Modified r Signature valid: {is_valid_modified_r}")
# Test 2: Modify s slightly
is_valid_modified_s = verify_ecdsa((r, s + 1), pubkey, message_bytes)
print(f"Modified s Signature valid: {is_valid_modified_s}")
# Test 3: Use negative r
is_valid_neg_r = verify_ecdsa((-r % CYCLIC_PRIME_ORDER, s), pubkey, message_bytes)
print(f"Negative r Signature valid: {is_valid_neg_r}")
# Test 4: Use negative s
is_valid_neg_s = verify_ecdsa((r, -s % CYCLIC_PRIME_ORDER), pubkey, message_bytes)
print(f"Negative s Signature valid: {is_valid_neg_s}")
# Test 5: Actual signature
is_valid = verify_ecdsa(signature, pubkey, message_bytes)
print(f"Actual Signature is valid: {is_valid}")
if __name__ == "__main__":
# Initialize key pair and message
key1 = KeyPair()
message = "Hello World"
message_bytes = convert_to_bytes(message)
# ECDSA Signature Test
ecdsa_signature = key1.generate_signature(message_bytes)
verification_test_ecdsa(ecdsa_signature, key1.get_pubkey(), message_bytes)
```
An interesting use of ECDSA is in the Bitcoin cryptocurrency. In Bitcoin, values are locked in an unspent transaction output called UTXO.
A simple example of a UTXO `scriptPubKey` is the `Pay-to-Public-Key` (`P2PK`) output. In this output, values are locked in a ECDSA public key. When the owner wishes to spend the bitcoin, they must provide a signature created with the private key corresponding to the public key in the `scriptPubKey`, usually by signing the transaction data or part of the transaction data. By using the signature verification method described above, anyone can ensure the signature’s validity and confirm that the owner is indeed the one spending the value.
In a subsequent article, we will discuss Schnorr signatures, which offer several advantages over ECDSA.
Thanks for reading!
Sign in with Wallet
Connect another wallet