Discussion and implementation of RSA in Python

The Mathematics and Implementation of RSA - Conor Deegan


### Introduction

This post will not focus on the history of RSA or why it is used. There are plenty of resources available that explain this already - [see here](https://en.wikipedia.org/wiki/RSA_(cryptosystem)). Instead we will focus on some of the mathematics around how RSA is implemented, why it is secure, and how it can be implemented in Python.

### How it works

RSA is a [public-key cryptosystem]([https://en.wikipedia.org/wiki/Public-key_cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography)) based on exponentiation modulo a composite prime $n$ such that $n = p.q$, where $p$ and $q$ are large primes.

The protocol is as follows:

1. Bob selects two large primes $p$ and $q$ - these are kept private.
2. He computes the modulus $n = p.q$ - this is made public.
3. Bob selects a public key $e$ such that $e$ is coprime with $\Phi(n)$*. Where $\Phi(n)$ is computed with either the Totient function or the Carmichael function.
4. Bob computes a private key $d$ such that $e.d \equiv 1 \mod \Phi(n)$.

We will now look at each step in more detail.

* Note: two numbers, $a$ and $b$ are coprime if $gcd(a,b)=1$.

### Step 1 - Generating large primes

This first step in RSA is to generate sufficiently large primes, $p$ and $q$. In order for $n$ to be 2,048-bits, $p$ and $q$ must both be $\approx$ 1,024-bits each.

A common way to generate a large prime $p$ is as follows:

1. Create $\sigma$, a random $n$-bit number (e.g 1,024-bits). It should be the case that $\sigma$ is odd as no prime number, with the exception of 2, is even. Thus we select a decimal number in the range $2^{n-1} + 1$ up to $2^n -1$. We call $\sigma$ the prime candidate.
2. We can then perform a low-level [primality test](https://en.wikipedia.org/wiki/Primality_test#Simple_methods) by checking if $\sigma$ is divisible by any of the first $k$ prime numbers (this list of primes is precomputed). The value of $k$ should be as large as possible. If $\sigma$ is divisible by any of these pre-computed primes, the prime candidate is composite and we return to step 1.
3. Once we find a $\sigma$ that passes this low-level primality test, we can perform a high-level primality test known as the [Miller–Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test). In the case of testing for primality of extremely large numbers, such as those used in RSA, a deterministic method is not feasible in terms of compute power. Instead, the Miller–Rabin primality test uses a probabilistic approach. It tests a prime candidate ($\sigma$) for primality many times. Each time the test passes the candidate has a 75% chance of being prime. By performing many iterations, we can increase the probability that such a candidate is in fact prime. Enough tests should be performed such that the probability of the prime candidate being composite is less than $\frac{1}{2^{128}}$. If any of the iterations fail, we return to step 1.

With the above algorithm we can now generate $p$ and $q$ which are both 1,024-bit primes.

### Step 2 - Compute the modulus $n$

Once we have values for $p$ and $q$, it is trivial to compute $n = p.q$.

### Step 3 - Select a public key $e$

We must now select a public key $e$ such that $e$ is co-prime with $\Phi(n)$.

$\Phi(n)$ can be calculated using either [Euler’s Totient function]([https://en.wikipedia.org/wiki/Euler's_totient_function](https://en.wikipedia.org/wiki/Euler%27s_totient_function)) or the [Carmichael function]([https://en.wikipedia.org/wiki/Carmichael_function](https://en.wikipedia.org/wiki/Carmichael_function)).

- Using Euler’s Totient function $\Phi(n) = (p-1)(q-1)$
- Using the Carmichael function $\Phi(n) = lcm(p-1,q-1)$

Once $\Phi(n)$ is computed, a public key $e$ should be chosen such that $e$ and $\Phi(n)$ are co-prime. Although the value of $e$ can be any value provided $gcd(e,\Phi(n)) = 1$, typically $e$ is set to 65,537. 65,537 is a [Fermat Prime]([https://en.wikipedia.org/wiki/Fermat_number). This is useful as given it is prime, it is guaranteed to be co-prime with $\Phi(n)$ and it is also very easy to calculate modular exponents that are Fermat Numbers (as in the case of encryption in RSA).

### Step 4 - Compute a private key $d$

The private key $d$ is calculated such that $e.d \equiv 1 \mod \Phi(n)$. This is done by using the [Extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).

The Extended Euclidean algorithm calculates $x$ and $y$ such that $ax + by = gcd(a,b)$. A simple online calculator can be found [here](https://www.extendedeuclideanalgorithm.com/calculator.php).

We can now look at why this works. If we let $a = e$ and $b = \Phi(n)$ we can rewrite the above as:

$ex + \Phi(n)y = gcd(e,\Phi(n))$

We know that $e$ and $\Phi(n)$ are co-prime and thus $gcd(e,\Phi(n)) = 1$. Therefore we can rewrite this as:

$ex + \Phi(n)y = 1$

We then take this modulo $\Phi(n)$ to get:

$ex + \Phi(n)y \equiv 1 \mod \Phi(n)$

The value of $y$ does not matter as it will be eliminated modulo $\Phi(n)$. Thus we are left with:

$ex \equiv 1 \mod \Phi(n)$

Here $x$ is equal to our private key $d$.

We have now computed all the values required to use RSA for encryption and decryption.

### Encryption and Decryption

To encrypt data, the message is broken down into blocks such that each block is smaller than the modulus $n$. Note if $p$ and $q$ are both 1024-bit primes, $n$ will be 2048-bits. Meaning that each block must be shorter than 2048-bits to avoid data loss.

To encrypt data:

- Bob makes his public key $e$ and the modulus $n$ public.
- Alice encrypts plaintext $l$ such that $c = l^e \mod n$ where $c$ is the resulting ciphertext.

To decrypt data:

- Bob, the holder of the private key $d$, can now decrypt $c$ by $l = c^d \mod n$ where $l$ is the recovered plaintext.

Note: RSA is not typically used to encrypt large amounts of data. Instead it is used as part of a  [key exchange]([https://en.wikipedia.org/wiki/Key_exchange](https://en.wikipedia.org/wiki/Key_exchange)) protocol so that Alice and Bob can agree upon a shared secret for use with a symmetric cipher such as [AES]([https://en.wikipedia.org/wiki/Advanced_Encryption_Standard](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard)). This is because RSA is not as performant as some symmetric ciphers which leverage bitwise operations rather than more complex mathematical operations seen here.

### Security in RSA

Brute force approach:

Given $e$ and $n$ are public, if Eve was to know some ciphertext $c$, she could try all plaintext options $l$ until she finds an $l$ that satisfies $c = l^e \mod n$. However, this not feasible when $n$ is large.

Breaking the cipher:

If Eve was to learn any one of $p$, $q$, $\Phi(n)$, or $d$ she can fully break the cipher.

If she learns $p$ or $q$, it is trivial to calculate the other values given $n = p.q$ and $n$ is public. From here she can workout all remaining values.

If she learns $\Phi(n)$, she can solve for $p$ and $q$ given she knows the function $\Phi(n)$ and that $n = p.q$. This is a case of solving for two unknowns with two equations.

If she learns $d$, the private key, she can decrypt any chipertext easily.

If we assume that a brute force approach is not feasible and that all private values remain private, then the security of RSA relies on Eve being able to factorise $n$ into $p$ and $q$. This is known as prime factorisation.

### Prime factorisation

The best attack for Eve is to factor $n$ into $p$ and $q$. However, there is no efficient, [non-quantum](https://en.wikipedia.org/wiki/Quantum_computer) integer factorisation algorithm known when $p$ and $q$ are sufficiently large. Even the fastest prime factorisation algorithms on the fastest computers will take so much time to make the search impractical. However, knowing $p$ and $q$ makes computing $n = p.q$ trivial, this is the [one way function]([https://en.wikipedia.org/wiki/One-way_function](https://en.wikipedia.org/wiki/One-way_function)) used in RSA.

Some algorithms used for prime factorisation include [general number field sieve](https://en.wikipedia.org/wiki/General_number_field_sieve), [the quadratic sieve](https://en.wikipedia.org/wiki/Quadratic_sieve), [Fermat's factorization method](https://en.wikipedia.org/wiki/Fermat%27s_factorization_method), and [Pollard's rho algorithm](https://en.wikipedia.org/wiki/Pollard's_rho_algorithm). As it stands, for large RSA key sizes (in excess of 1024-bits) no efficient method for computing the factors is known.

Interestingly, a recent paper by Schnorr [6], controversially claimed that a new factoring method “destroys the RSA cryptosystem”. However, it has subsequently been shown not to be the case [7].

# RSA in Python

A complete implementation of RSA in Python can be found [here](https://github.com/conor-deegan/sandbox/tree/main/rsa-python). The code should be self explanatory given the information above. 

One interesting point that I have not discussed is how to compute $b = a^c$ efficiently if $c$ is large. One way to handle this is by using [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring). In the code you will notice on line 41 of `main.py` I compute the ciphertext by raising the plaintext to the power of $e$ directly. This is feasible given $e$ is relatively small. However, on line 45 of `main.py`, I compute the plaintext by using exponentiation by squaring instead as $d$ is too large to compute this directly. Python comes with a built in function to handle this - see [here](https://docs.python.org/2/library/functions.html#pow).

Besides encryption and decryption of data, RSA is also used for [digital signatures](https://en.wikipedia.org/wiki/Digital_signature). I have not gone into much detail about digital signatures as that is for a different post but I have included a full example in the code attached. You will notice that the only difference is that we use the keys in reverse order. I.e you sign a message with your private key and anyone who has a copy of your public key can verify it was you who signed it.

### References

1. [RSA - Wikipedia](https://en.wikipedia.org/wiki/RSA_(cryptosystem))

2. [RSA - calculator](https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html)

3. [RSA_ Problem](https://en.wikipedia.org/wiki/RSA_problem)

4. [https://coderoasis.com/implementing-rsa-from-scratch-in-python/](https://coderoasis.com/implementing-rsa-from-scratch-in-python/)

5. [Generating large primes](https://www.geeksforgeeks.org/how-to-generate-large-prime-numbers-for-rsa-algorithm)

6. [Fast Factoring Integers by SVP Algorithms - Claus Peter Schnorr](https://eprint.iacr.org/2021/232)

7. [No RSA is not broken](https://www.schneier.com/blog/archives/2021/03/no-rsa-is-not-broken.html)

*Note: these references exclude hyperlinks included throughout the document.*

*Disclaimer: Do not use this to secure any information. This code is purely to be used for educational purposes only.*

The Birthday Paradox

Discussion and demonstration of the Birthday Paradox

The Birthday Paradox - Conor Deegan


### Introduction

In probability theory, given a set of $n$ randomly chosen people, the birthday problem asks for the probability that at least two will share the same birthday. The birthday paradox is that, counterintuitively, in a group of only 23 people there is over a 50% chance that there is a shared birthday. This rises to almost 100% with just over 60 people.

It seems odd that only 23 people are needed in order to have a 50% chance of a shared birthday given 23 random birth dates is considerably lower than all of the possible birthdays people can have: 365. However, this is made more intuitive by considering that the comparisons of birthdays are made between every possible pair of individuals. I.e with 23 people, there are $(23 \times 22)/2 = 253$ pairs of birthdays to consider. This is well over half of the numbers of days in a year (182.5).

### Implications on cryptography

A [birthday attack](https://en.wikipedia.org/wiki/Birthday_attack) is a [cryptographic attack](https://en.wikipedia.org/wiki/Cryptanalysis) that exploits this paradox. Given the paradox, it is possible to find a [collision](https://en.wikipedia.org/wiki/Hash_collision) in a [hash function](https://conordeegan.dev/post/cryptographic-hash-functions) in $\approx \sqrt{2^d}$ or $\approx 2^{d/2}$ operations where $d$ is the length of the hash in bits - I will prove this shortly and also give a more exact equation. Some research indicates that quantum computers may perform birthday attacks, i.e find collisions, in $\approx \sqrt[3]{2^d}$ or $\approx 2^{d/3}$ operations [1].

A 128-bit hash would take $2^{128} \approx 3.40×10^{38}$ operations to brute force. It’s hard to grasp how massive this number is and its safe to say that brute forcing a 128-bit hash is still out of reach of modern computers. However, finding a hash collision in a 128-bit hash requires $2^{128/2} = 2^{64} \approx 1.84×10^{19}$ operations. A number quickly becoming within the reach of some modern computers.

I talk more about the problems of hash collisions [here](https://conordeegan.dev/post/cryptographic-hash-functions).

### Proof

For simplicity, the following proof will assume that the distribution of birthdays is uniform throughout the year. It will ignore leap years, twins, and seasonal and weekly variations in birth rates. To formalise this, it is assumed that there are 365 possible birthdays, and that each person’s birthday is equally likely to be on any of these days.

The goal is to compute $\gamma$, the probability that at least two people in a group of $n$ persons share the same birthday. However, it is simpler to calculate $\bar\gamma$, the probability that no two people in the room have the same birthday. Given $\gamma$ and $\bar\gamma$  are the only two possibilities and are also mutually exclusive, $\gamma = 1 - \bar\gamma$.

We can now calculate $\bar\gamma$ given $n$ = 23.

Assume the first person was born on any given date. Given this, the probability that the second person was not born on the same date as the first person can be computed as $1-1/{365}$. The probability that the third person was not born on the same days as either the first or the second person can be computed as $1-2/{365}$.

We can continue this for all 23 people:

$\bar\gamma = (1-\frac{1}{365})(1-\frac{2}{365})(1-\frac{3}{365})...(1-\frac{22}{365})$

$\bar\gamma = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \frac{362}{365} \times ... \times \frac{343}{365}$

$\bar\gamma = (\frac{1}{365})^{23} \times (365 \times 364 \times 363 \times ... \times 343) $

$\bar\gamma \approx 0.492703 $

Therefore, $\gamma \approx 1-0.492703 = 0.507297 $ i.e $50\%$.

### Generalising to $n$ number of people

We can generalise this to a group of $n$ people as follows:

$\bar\gamma = (1-\frac{1}{365})(1-\frac{2}{365})(1-\frac{3}{365})...(1-\frac{n-1}{365})$

$\bar\gamma  = \frac{356!}{365^n(365-n)!}$

The above shows that the $n^{th}$ birthday cannot be the same as any of the $n$ - $1$ preceding birthdays.

Therefore $\gamma = 1 - \frac{356!}{365^n(365-n)!}$

We can test this for $n = 23$:

$\gamma = 1 - \frac{356!}{365^{23}(365-23)!} \approx 0.507297$ - the same as above.

We can also test this for any value of $n$, e.g $n = 60$:

$\gamma = 1 - \frac{356!}{365^{60}(365-60)!} \approx 0.99412$

It's ineresting to see that with only 60 people in a group, it is *almost* guaranteed that there will be at least two people with the same birthday.

Using the Taylor series we can also approximate this above equation for $n$ number of people as:

$\bar\gamma \approx e^{- \frac{{(n-1)^n}}{2 \times 365}} \approx e^{- \frac{n^2}{2 \times 365}}$

### Generalising to `d-bit` hashes

Let’s now discuss how this translates to the cryptographic attack mentioned above. To do this, we need to replace birthdays for d-bit hashes by replacing $365$ in the above equation with $2^d$.

$\bar\gamma \approx e^{- \frac{n^2}{2 \times 2^d}}$

We can now solve for $n$ so that $\bar\gamma = \gamma = \frac{1}{2}$:

$n \approx \sqrt{2 \times \ln{2}} \times 2^{\frac{d}{2}} \approx 2^{\frac{d}{2}}$

We have now derived the equation known as the birthday bound for `d-bit` hashes. This equation tells us how many hashes are required ($n$) in order for a `d-bit` hash to have a 50% chance of a collision.

We can now compute this value for different `d-bit` hashes:

$d = 64$:

$n \approx \sqrt{2 \times \ln{2}} \times 2^{\frac{64}{2}} = 5056937541$

$d = 128$:

$n \approx \sqrt{2 \times \ln{2}} \times 2^{\frac{128}{2}} = 2.17×10^{19}$

$d = 256$:

$n \approx \sqrt{2 \times \ln{2}} \times 2^{\frac{256}{2}} = 4×10^{38}$

### Demonstration of this paradox in Python

Here's a Python program demonstrating the birthday paradox experimentally: [here](https://github.com/conor-deegan/sandbox/tree/main/birthday-paradox).

The attached Python program generates $n$ 16-bit hashes and checks for at least one collision.

For this, $n$ can equal $2^i$ where $i=2,3,4,…,16$.

Given that we are dealing with 16-bit hashes, due to the birthday paradox, we would expect a 50% chance of a collision when we generate $2^{16/2} = 2^8 = 256$ hashes.

The program runs 1,000 times for each value of $n$ in order to check if there is a trend in how many times at least one collision is found.  The program then plots the results along side the results calculated from the derived equation, subbing in the relevant value of $n$ each time:

$\gamma \approx 1 - e^{- \frac{n^2}{2 \times 2^{16}}}$

![Birthday-Paradox-Plot](https://conordeegan.dev/birthday-paradox-plot.png "Plot of Results")

From the above we can see that the empirical results match almost perfectly with the derived equation. Only 256 hashes are required in order to have a 50% chance of at least once collision in a 16-bit hash, which can take $2^{16}$ = 65,536 possible values.

### References

1. [Quantum Algorithm for the Collision Problem. Brassard et al 1997](https://arxiv.org/pdf/quant-ph/9705002.pdf)

2. [Birthday Attack](https://en.wikipedia.org/wiki/Birthday_attack)

3. [The Birthday Problem](https://en.wikipedia.org/wiki/Birthday_problem)

*Note: these references exclude hyperlinks included throughout the document.*

Feistel Network in Python

Discussion and implementation of a Feistel Network in Python

Feistel Network in Python - Conor Deegan


### Introduction

Feistel networks are a design scheme used to construct [block ciphers](https://en.wikipedia.org/wiki/Block_cipher). A lot of block ciphers use this scheme including [DES](https://en.wikipedia.org/wiki/Data_Encryption_Standard), [GOST](https://en.wikipedia.org/wiki/GOST_(block_cipher)), and [Blowfish](https://en.wikipedia.org/wiki/Blowfish_(cipher)). In block ciphers constructed using a Feistel network, encryption and decryption are very similar operations - the only difference is the order in which the sub-keys are used (more on that soon).

Named after [Horst Feistel](https://en.wikipedia.org/wiki/Horst_Feistel), Feistel networks were first used commercially in the [Lucifer cipher](https://en.wikipedia.org/wiki/Lucifer_(cipher)) designed by IBM in 1973. The Lucifer cipher would eventually set the basis for DES (with changes added by the NSA).

This article explains how a Feistel network works and implements one using Python. It goes without saying that this code should not be used to secure information of any kind. This is purely for learning and is not designed to be secure.

### Design

At its core, a Feistel network uses a round function to encrypt and decrypt data. The image below illustrates a single round of a Feistel network.

![Feistel-Network-Single-Round](https://conordeegan.dev/feistel-network-single-round.png "Single round of a Feistel Network [4]")

We can now step through the process of encryption using a Feistel Network. Let $F$ be the round function, $I_0$ be the first block of plaintext data, and $K_0, K_1,...,K_n$ be the sub-keys of $K$ for the rounds $0, 1,...,n$ respectively.

Before starting, $I_0$ is split into left and right halves such that $I_0 = (L_0 , R_0)$.

For each round $i = 0,1,2...,n$ compute:

> $L_{i+1} = R_i$

> $R_{i+1} = L_i \oplus F(R_i, K_i)$

The ciphertext becomes $(R_{n+1} , L_{n+1})$

Decryption of the ciphertext $(R_{n+1} , L_{n+1})$ is computed by reversing $i=n, n-1, ...,0$:

> $R_i = L_{i+1}$

> $L_i = R_{i+1} \oplus F(L_{i+1}, K_i)$

The plaintext becomes $(L_0 , R_0)$ - note this is what we stared with.

As can be seen above, a round function, $F$, takes a block of input data and a subkey and produces an output of the same size as the input data. During each round, the round function runs on the right half of the input data and its output is XORed with the left half of the input data. This is repeated a number of times and the final output is the encrypted or decrypted string.

The function $F$ is what differentiates block ciphers that are based on a Feistel network. For instance, the logic contained within $F$ will be different in DES, GOST, Blowfish, etc. It is also what provides the security of the cipher. In the Python implementation below, the function $F$ simply XORs the input data with the subkey.

As can be seen, both the encryption and decryption operations are very similar, requiring only that the order of the sub-keys used is reversed. This is shown clearly in the diagram below.

![Feistel-Network](https://conordeegan.dev/feistel-network.png "A Feistel Network with N rounds [3]")

### Python implementation

The full source code can be found [here](https://github.com/conor-deegan/sandbox/tree/main/feistel-network).

Although the code should be self-explanatory, I will briefly discuss the 3 most important functions; `encrypt`, `decrypt`, and `round`.

### The encrypt function:

Takes 2 inputs; a plaintext sting, and a secret.

The plaintext string is converted into binary:

```python
plaintext_bits = string_to_bits(plaintext)
```

This binary string is then split into blocks of 64 bits each. This is the block size for this Feistel network:

```python
plaintext_blocks = split_to_blocks(plaintext_bits, 64)
```

A `265-bit` key is then generated by hashing the secret provided using SHA-256:

```python
key = generate_key(secret)
```

8 x 32bit sub-keys are then generated by splitting the key into 8 blocks of 32bits each:

```python
sub_keys = split_to_blocks(key, 32)
```

Each block of plaintext is run through 8 rounds of the Feistel network. Once 8 rounds are completed, the resulting ciphertext block is stored.

```python
for plaintext_block in plaintext_blocks:
  for i in range(8):
	  plaintext_block = round(plaintext_block, sub_keys[i])
  ciphertext_blocks.append(str(plaintext_block[32:]) + str(plaintext_block[:32]))
```

Once all ciphertext blocks have been computed, the function returns the entire ciphertext in hexadecimal format:

```python
return bits_to_hex(''.join(ciphertext_blocks))
```

### The round function

The round function $F$ for this Feistel network simply XORs the sub-key with the right hand of the plaintext bits provided. The result of this is then XORed with the left hand bits. The halves are then swapped and returned.

```python
def round(bits, sub_key):
    left_bits = bits[:32]
    right_bits = bits[32:]
    f_out = xor(sub_key, right_bits)
    left_xor_f_out = xor(left_bits, f_out)
    return right_bits + left_xor_f_out
```

### The decrypt function:

The decryption function is almost identical to the encryption function. The only differences are that the ciphertext input to the function is a hexadecimal string and when performing the 8 rounds in order to decrypt the ciphertext, the sub-key order is reversed:

```python
for ciphertext_block in ciphertext_blocks:
  for i in range(ROUNDS, 0, -1):
      ciphertext_block = round(ciphertext_block, sub_keys[i - 1])
  plaintext_blocks.append(str(ciphertext_block[32:]) + str(ciphertext_block[:32]))
```

Finally, when the recovered plaintext bits are combined, they are split into blocks of 8bits (1 byte) each in order to recover the original ASCII character.


### References

1. [Feistel Cipher - Computerphile](https://www.youtube.com/watch?v=FGhj3CGxl8I)
2. [Feistel cipher - Wikipedia](https://en.wikipedia.org/wiki/Feistel_cipher)
3. Image source: By Feistel_cipher_diagram.svg: Amirkiderivative work: Amirki (talk) - Feistel_cipher_diagram.svg, CC BY-SA 3.0, [https://commons.wikimedia.org/w/index.php?curid=16419258](https://commons.wikimedia.org/w/index.php?curid=16419258)
4. Hernandez-Castro, J.C., Estevez-Tapiador, J.M., Ribagorda-Garnacho, A. and Ramos-Alvarez, B., 2006, July. Wheedham: An automatically designed block cipher by means of genetic programming. In *2006 IEEE International Conference on Evolutionary Computation*
 (pp. 192-199). IEEE.

*Note: these references exclude hyperlinks included throughout the document.*

*Disclaimer: Do not use this to secure any information. This code is purely to be used for educational purposes only.*

Elliptic Curve Cryptography

A practical introduction to Elliptic Curve Cryptography

Elliptic Curve Cryptography - Conor Deegan


### 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](https://en.wikipedia.org/wiki/Symmetric-key_algorithm) 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](https://en.wikipedia.org/wiki/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 symmetric-key encryption is that all parties are required to know the key. This creates a sort of catch-22 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](https://en.wikipedia.org/wiki/Key_distribution).

This problem was solved in 1976 with the publication of the [Diffie-Hellman key exchange algorithm](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange). 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 [public-key cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography) or asymmetric cryptography.

The basis of public-key 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](https://en.wikipedia.org/wiki/Trapdoor_function).

```
# 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 public-key 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 public-key cryptosystem called [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)).

## RSA

In their publication, Diffie and Hellman did not formally specify a one-way function that could be used in their key exchange algorithm. After a series of attempts, one year later [Ron Rivest](https://en.wikipedia.org/wiki/Ron_Rivest), [Adi Shamir](https://en.wikipedia.org/wiki/Adi_Shamir), and [Leonard Adleman](https://en.wikipedia.org/wiki/Leonard_Adleman)  proposed a suitable one-way 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 one-way function as given two prime numbers it is straightforward to calculate their product. However, given only the product it is [computationally hard](https://en.wikipedia.org/wiki/Computational_hardness_assumption) 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: 

1. Choose two random prime numbers `p` and `q`. Typically these two numbers will be very large and chosen at random. These are kept secret.

```
p = 3, q = 11
```

2. 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
```

3. Compute `φ(n) = (p - 1) * (q - 1)`. `φ(n)` is kept secret.

```
φ(n) = (3 - 1) * (11 - 1) = 2 * 10 = 20
```

4. Select an `e` such that `1 < e < φ(n)` and `e` 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.*

5. Compute d such that `(d * e) % φ(n) = 1`. `d` becomes the private key.

```
d = 3 as (3 * 7) % 20 = 1
```

6. Set the public key and modulus

```
public_key = (e, n) => (7, 33)
```

7. 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](https://en.wikipedia.org/wiki/Modular_arithmetic), [Euler's theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem), [Extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) and [Euler's totient function](https://en.wikipedia.org/wiki/Euler%27s_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:

1. Choose plaintext to encrypt

```
plain_text = 2
```

2. Encrypt the plaintext with the public key

```
cipher_text = (2 ^ 7) % 33 = 29
```

3. Decrypt the cipher text with the private key

```
decrypted_cipher_text = (29 ^ 3) % 33 = 2
```

4. 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](https://en.wikipedia.org/wiki/Quadratic_sieve) 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 public-key cryptosystem. ECC is based on the algebraic structure of elliptic curves over [finite fields](https://en.wikipedia.org/wiki/Finite_field) and uses a trapdoor one-way function based on the [the discrete logarithm problem](https://en.wikipedia.org/wiki/Discrete_logarithm). 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 256-bits. 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 Curve](https://conordeegan.dev/elliptic-curve.png)



### 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](https://en.wikipedia.org/wiki/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 public-private 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 256-bit 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](https://en.wikipedia.org/wiki/Cryptographically-secure_pseudorandom_number_generator#:~:text=A%20cryptographically%20secure%20pseudorandom%20number,suitable%20for%20use%20in%20cryptography.) and hashing them using a 256-bit hash algorithm such as [SHA-256](https://emn178.github.io/online-tools/sha256.html).

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 256-bits 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](https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman) (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.

1. Alice then randomly selects a private key: `alice_private`

2. Alice creates her public key: `alice_public`

```
alice_public = alice_private * G
```

3. Bob randomly selects a private key: `bob_private`

4. Bob creates his public key: `bob_public`

```
bob_public = bob_private * G
```

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

6. Alice can now calculate their shared secret: `secret_key`

```
secret_key = bob_public * alice_private
```

7. Bob can now calculate their shared secret: `secret_key`

```
secret_key = alice_public * bob_private
```

8. 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

1. [Mastering Ethereum by Andreas M. Antonopoulos, Gavin Wood](https://www.oreilly.com/library/view/mastering-ethereum/9781491971932/)

2. [Practical Cryptography for Developers by Svetlin Nakov](https://cryptobook.nakov.com/)

*Note: these references exclude hyperlinks included throughout the document.*


Cryptographic Hash Functions

An introduction to Cryptographic Hash Functions for use in Web3

Cryptographic Hash Functions - Conor Deegan


### Introduction

The purpose of this article is to introduce cryptographic hash functions.

Generally speaking a hash function is any function which can be used to map data of any size and type to a fixed sized integer. These values are then typically used as an index in a fixed size table called a hash table which can store and retrieve data in nearly constant time. Examples include dictionaries in Python, hashes in Ruby, and objects in Javascript. Hashes and hash tables used for this purpose are outside the scope of this article but can be read more about [here](https://en.wikipedia.org/wiki/Hash_function) and [here](https://en.wikipedia.org/wiki/Hash_table). 

The main concept for moving forward is that we can take any type of data of any length and use a hash function to map that data to a fixed sized integer.

An example of a hash function using a popular algorithm called [SHA-256](https://en.wikipedia.org/wiki/SHA-2) is shown below.

```
sha256('conor deegan') => 0x5682143fca595e8ff8f62f91aafbd3c43dfc20fa87d3a33e7bae49ed5236701a
```

The result of this hash function is a 256-bit integer.

### Cryptographic Hash Functions

A cryptographic hash function is similar to a regular hash function with some specific requirements.

*Note some of these requirements are also requirements for non-cryptographic hash functions.*

Although in-depth use cases of cryptographic hash functions are outside the scope of this post, in order to motivate some of these requirements it's important to outline a simplistic use case. 

Storing users passwords in plaintext can lead to massive security breaches if access to the database they are stored in becomes compromised. A hash of a users password should be stored instead. Authenticating a user remains trivial, simply hash the password presented by the user and compare the result with the stored hash in the database. If the hashes match we can be sure that the user has presented the correct password (for reasons we will discuss). If access to the database was to become compromised, leaking the hashed passwords is less of a concern than leaking a users plaintext password.

### One-way function

A cryptographic hash function should be a [one-way function](https://en.wikipedia.org/wiki/One-way_function). Meaning that once a message has been hashed it should be [computationally hard](https://en.wikipedia.org/wiki/Computational_hardness_assumption) to reverse the hash back to the original message.

I.e given a hash value `h`, it should be difficult to find any message `m` such that `h = hash(m)`.

Hash functions that lack this property are susceptible to what are known as [preimage attacks](https://en.wikipedia.org/wiki/Preimage_attack).

A preimage attack is an attack on a cryptographic hash function which tries to find a message for a given hash value (i.e reverse the one way function). As such, cryptographic hash functions should ensure that it is computationally infeasible to find any message given a hash output, or at least that the fastest way to calculate the message is with a brute force search of all possible inputs to see if they produce the correct hash. In terms of our simple example, this would mean that if Eve got her hands on a users password hash, in order for Eve to work out the users password she would be required to try all possible passwords to see if they produce the same hash value.

One important aspect of a hashing algorithm is the length of the hash it maps to. For instance, the SHA-256 hashing algorithm used above returned a 256-bit hash.   Knowing the length of the hash the function returns is important as it allows us to understand how difficult a brute force attack would be. For an `n-bit` hash the time complexity of a brute force search is `2^n`. This directly relates the security of a hashing algorithm with the length of the hash it produces.  As it stands, a value for `n` greater than or equal to 128-bits is considered secure in terms of a brute force attack - the assumption here that quantum computers are still a few decades away!

It's important to highlight that the resistance to a preimage attack on a well-designed cryptographic hash function assumes that the set of possible inputs is far too large to perform a brute force attack. This is not always the case and if an attacker knows that the given hash has been generated from a smaller subset of possible inputs a brute force search may be possible. Hacking password hashes is a good example of this as people tend to choose short predictable passwords making a brute force search feasible.

### Collision resistant

A cryptographic hash function should ensure that it is computationally infeasible to find two different messages that when hashed result in the same hash value.

I.e given a message `m1` it should be hard to find a different message `m2` such that the hash of `m1` and `m2` are the same provided `m1` ≠ `m2`.

However, given a hash function can take data of any size and produces a fixed sized integer, there are more possible inputs than outputs by definition. As per the [pigeonhole principle](https://en.wikipedia.org/wiki/Pigeonhole_principle), there must exist different input messages which result in the same hash - i.e there must be collisions. The hash function should make it very difficult to find these collisions.

An attack on a cryptographic hash function which tries to find two messages that result in the same hash is known as a second-preimage attack. In terms of our use case, if a cryptographic hash function was susceptible to a second-preimage attack it would mean that Eve could potentially find an entirely different password than the users password but would be granted access as both passwords result in the same hash.

The [birthday paradox](https://en.wikipedia.org/wiki/Birthday_paradox) places an upper bound on collision resistance of an `n-bit` hash as `root 2^n`, meaning that any method that makes it easier than this to find a collision deems that hash function as insecure. Some hash functions that were once thought to be collision resistant have now been broken. See [MD5](https://web.archive.org/web/20090521024709/http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf) and [SHA-1](https://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf).

### Avalanche Effect

A cryptographic hash function should ensure that a small change to a message (e.g flicking a single bit) changes the resulting hash so extensively (e.g. half the output bits flip) that the new hash value appears uncorrelated with the old hash value. This is know as [diffusion](https://en.wikipedia.org/wiki/Confusion_and_diffusion#Diffusion) first identified by [Claude Shannon](https://en.wikipedia.org/wiki/Claude_Elwood_Shannon). If a hash function has poor diffusion an attacker may be able to make predictions about a message given the hash.

Examples of the avalanche effect:

```
Hash 1:
sha256('conor deegan') => 0x5682143fca595e8ff8f62f91aafbd3c43dfc20fa87d3a33e7bae49ed5236701a

Hash 2:
sha256('conor deegam') => 0xf368271842971406f4379762bb4d3a0105010280ae0cc8ebe9bace7231315cae
```

By changing the final letter of the message from `n` to `m` the resulting hash is entirely different.

In terms of our use case, an example of two hashes generated from a hash function that does not implement the avalanche effect might look like this:

```
Hash of actual password
bad_hash_function('password') = 12345678

Hash of password guessed by Eve
bad_hash_function('Password') = 02345678
```

Eve would know that she is close to the correct password as the hashes are similar.

### Deterministic

A cryptographic hash function should be deterministic meaning that each time the same message is hashed it should produce the same result.

### Constant time

A [perfect hash function](https://en.wikipedia.org/wiki/Perfect_hash_function) can hash values in constant time. As such a cryptographic hash function should be quick to compute the hash value for any given message.

### Hash functions and Ethereum

Hash functions are used extensively in the Ethereum protocol. Some of the most common uses for hash functions in Ethereum include generation of Ethereum addresses from public keys, checking message integrity, detecting errors, proof of work, authentication, pseudorandom number generation, and digital signatures. Ethereum uses the `Keccak-256` cryptographic hash function.

### Keccak-256

`Keccak-256` was first developed and entered into a competition organised by the National Institute of Standards and Technology (NIST) set up to create a new hash standard, SHA-3. Ultimately `Keccak-256` won this competition and was due to be standardised as the FIPS-202 SHA-3 standard. However during the standardisation process NIST made some small adjustments to `Keccak-256` to "improve efficiency". Documents published by Edward Snowden implied that these adjustments were influenced by the NSA and included a change to intentionally weaken a part of the algorithm used to generate random numbers creating a backdoor in part of the function. As a result of this the Ethereum Foundation decided to implement the original `Keccak-256` algorithm rather then the modified standard `SHA-3`.

### References

1. [Mastering Ethereum by Andreas M. Antonopoulos, Gavin Wood](https://www.oreilly.com/library/view/mastering-ethereum/9781491971932/)

*Note: these references exclude hyperlinks included throughout the document.*

About

Posts

Work