# Diffie-Hellman (DH) Public Key Exchange

>This is a method to **securely generate and exchange key pairs** and is universally used not only in the field of cryptography but also computer science.

When we were discussed about symmetric encryption, we assume that 2 parties share a same secret key to do encryptions and decryptions.

In fact, DH allows these 2 parties to generate a **shared secret key** over an insecure channel, which can be used in a symmetric encryption and is also followed afterwards by [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)), the other way to exchange keys in asymmetric encryption.

## Math Explanation
DH key exchange protocol allows 2 party to share a secret key, but what do they do in the math?

There are 2 people, **Alice** and **Bob**, who want to exchange some msg by using the same secret to encrypt and decrypt.

In fact, the process is relatively quite simple:

Terms used below
- **g**: generator
- **p**: a prime
- **a**: the secret number held by Alice
- **b**: the secret number held by Bob

1. Set up a public numbers: $g$ & $p$.
2. Alice pick a secret number $a$ to generate $g^a (mod \ p)$, we would call it $pub_A$.
3. $pub_A$ can be public sent to the communication channel because the adversaries are not able to figure out what is $a$. (due to the [discrete log problem](https://www.doc.ic.ac.uk/~mrh/330tutor/ch06s02.html))
4. Then, Bob does the same calculation to generate $pub_B = g^b (mod \ p)$.
5. Now that Alice and Bob both knows the public information of each others. Alice and Bob are able to calculate a secret Key that only known by Alice and Bob:
$$
secretKey = g^{a} (mod \ p) * g^{b} (mod \ p) \equiv g^{ab} (mod \ p) \equiv g^{ba} (mod \ p)
$$
6. Afterward, Alic and Bob both get $secretKey$ to **encrypt their messages**, yet the adversaries on the communication channel can not build this key since they don't have $a$ or $b$.

> In 2006, Hellman shout out to Merkle (The one who invented [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree)) to help people recognize Merkle's equal contribution to the invention of public key cryptography by a new name: **Diffie-Hellman-Merkle Key Exchange**.

If you feel this one too hard, [here's](https://www.youtube.com/watch?v=NmM9HA2MQGI&list=PLzH6n4zXuckpoaxDKOOV26yhgoY2S-xYg&index=1) another version of explanation in colors

# Elliptic Curve (EC)

## Math
The formula of a Elliptic Curve is:

$$
y^2 = x^3 + ax + b
$$

If a,b (the parameters of EC) is on the real number $\mathbb{R}$, the curve would looks like:

*$y^2=x^3 + ax + b$ over $\mathbb{R}$

However, EC should be defined over many other types of finite fields to become more powerful in cryptography.

Therefore, just imagine this curve is now over a prime fields called $Z_p, p>3$. All pairs (x,y) filfulls: $y^2=x^3 + ax + b (mod \ p)$.

## The infinite $\theta$
And there's a imagination point called $\theta$, which represent infinity (where $a,b \in Z_n \land 4a^3 + 27b^2 \ne 0 (mod \ p)$). This identity point is additionally added to the group definition. And it has a trait:

In any group E, given point $P \in E: P + \theta = P = \theta + P$.


Another trait of EC is that it's symmetric along the x-axis. For each point $P=(x,y)$ the inverse of P is $-P=(x,-y)$

## Addition of points on EC

Generating points a EC is based on **Addition of a base point**.

However, this operation on EC is kind of tricky, which use a **geometric interpetation** to add 2 points.

Here's the example


e.g. $P (x_P, y_P) + Q (x_Q, y_Q) = R (x_R, y_R)$

2 case here:

1. if $P \ne Q$
- Draw a straight line throught P and Q
2. if $P = Q$
- Draw a tangent line

Then, just mirror the third intersection point on EC along the x -axis (as shown in the figure).

## Doubling Point
> In the aspect of math, here's what it actually do

$$
s =
\begin{equation}
\left\{
\begin{array}{**lr**}
\frac{y_2 - y_1}{x2 - x_1} (mod \ p), \ if \ P \ne Q \\
\frac{3x_1^2 + a}{2y_1} (mod \ p), \ if \ P = Q \\
\end{array}
\right.
\end{equation}
$$

if $P (x_1, y_1) + Q (x_2, y_2) = R (x_R, y_R)$

$$
x_r = \begin{equation}
\left\{
\begin{array}{**lr**}
s^2 -x_1 -x_2 (mod \ p) \ (addition) \\
s^2 -2x_1 (mod \ p) \ (doubl) \\
\end{array}
\right.
\end{equation}
$$

$$
y_R = s^2(x_1 - x_R) - y_1 (mod p)
$$

# EC Diffie-Hellman
ECDH protocol is another powerful tool commonly used in asymmetric cryptography.

Allow me to C&P the whole process in DH above:

There are still Alice and Bob wanted to send a share secret key with each other.

Terms used below
- **E**: Elliptic Curve over a prime field
- **G**: the primitive point of E
- **a**: the secret number held by Alice
- **b**: the secret number held by Bob

1. Set up $E$ and $G$.
2. Alice pick a secret number $a$ to generate $a * G$, we would call it $pub_A$.
3. $pub_A$ can be public sent to the communication channel because the adversaries are not able to figure out what is $a$.
4. Then, Bob can do the same calculation to generate $pub_B = b * G$.
5. Now that Alice and Bob both knows the public information of each others. Alice and Bob are able to calculate a public Key:
$$
pubKey = (a * G) * (b * G) = ab * G = (b * G) * (a * G)
$$
6. Afterward, Alic and Bob both get $pubKey$, yet the adversaries on the communication channel can not build this key since they don't have $a$ or $b$.

The protocol leverages the **ECDL problem** (shown below).

## EC Discrete Logarithm Problem
> Definition

Given a primitive element $P$ and another element $T$ on an EC named E.

The ECDLP is finding the integer $d$, where $1 \le d \le |E|$, s.t. $P + P + P + ... + P = dP = T.$

This makes EC a really powerful and more secure (compare to DL problem) tool on cryptography.

# ECDSA
> Refer to [DSA](https://en.wikipedia.org/wiki/Digital_Signature_Algorithm) if you have no idea what is it.

ECDSA is the native signature method used by Ethereum and is definitely worthy to drill it more in detail.

This algorithm uses ECDH to generate its public key pair.

## Step
There are a few step to generate a signature and verify a signature.
1. **Basic Setup**: to set up a EC curve to generate a private key and public key.
2. **Generate personally private key**
3. **Generate Signature**.
4. **Verify Signature**.

### Basic Setup
First of all, EC domain parameters need to set up.

$$
D = {q, FR, a, b, G, n, h}
$$

and here's how they are generated:

1. $n$ is the order of $G$
2. Select coefficients $a$ and $b$ from $F_q$ verifiable using a random method.
3. Compute the value of Number $N$.
4. Verify $N$ is divisible by the large prime number if not go to step 1.
5. Verify $N$ does not divisible by $qk -1$ for each $k$ where $k$ ranges from 1 to 20.
6. Verify $N$ is not equal to $q$ if not then go to step 1.
7. Select an arbitrary point $G’ \in Nq$ and set $G=(N/n)$. (Generator of EC curve)

> More detail can be seen [here](https://www.geeksforgeeks.org/blockchain-elliptic-curve-digital-signature-algorithm-ecdsa/)

### Generate Personal Private Key
The way to generate a private/ public key pair is as same as ECDH.

1. First, randomly choose a integer $d$ in the range of $[1, n-1]$
2. generate public key from the curve: $Q = dG$
3. private key: $d$; public key: Q

### Generate Signature
Alice wants to sign her message $m$ with ECDSA, and here's what signature does.

1. Select a random number $k$ from $[1, n-1]$
2. Calculate the point on curve $(x_1, y_1) = k*G$
3. Compute $r = x_1 (mod \ n)$. if $r=0$, get back to step 1.
4. Compute $k^{-1} (mod \ n)$, aka multiplicative inverse of $k (mod \ n)$
5. Compute $s = k^{-1} * (Hash(m) + d*r) (mod \ n)$. If $s=0$, get back to step 1.
6. The signature of $m$ is pair $(r, s)$

### Verification of sig(m)
Remember that $D$ is common parameters that everyone knows, and so does $Q$ (Alice's Public Key).

1. Check if $(r,s)$ both are between $[1, n-1]$. If not, then this sig is invalid.
2. Convert $m$ into integer $e$, $e = Hash(m)$
3. Compute the multiplicative inverse of $s (mod \ n)$: $w = s^{-1} (mod \ n)$.
4. Compute $u_1 = e*w$ (mod \ n), $u_2 = r*w (mod \ n)$
5. Compute EC point $X = u_1G + u_2Q$
$$
\begin{align}
X &= u_1G + u_2Q \\
&= e * w * G + r * w * Q \\
&= w * (eG + rQ) \\
&= \frac{eG + rQ}{k^{-1} * (Hash(m) + d*r)} \\
&= \frac{eG + d*rG}{k^{-1} * (e + d*r)} \\
&= \frac{G (e + d*r)}{k^{-1} * (e + d*r)} \\
&= kG
\end{align}
$$
- if $X = \theta$ (infinite point), then reject.
8. Else, extract x-coordinate from $X$ and reduce it mod n to get a new integer $v = X_x (mod \ n)$
9. The signature is valid iff $v=r$.

# EdDSA (Edwards-curve Digital Signature Algorithm)
Unlike Schnorr signatures, which may use a random value for generating the signature, EdDSA takes a deterministic approach. It hashes the private key and the message together to produce the randomness, ensuring repeatability.

Suppose we have a private key $d$ <=> public key $A$ and a message $m$. In EdDSA, we would compute:

- $h = Hash(d)$
- $r = Hash(h || m)$
- $R = r * G$

where $G$ is the base point on the curve and $R$ is another point on the curve.

Just like Schnorr, the signature in EdDSA is a pair $(R, s)$, where:

- $s_1 = (r + Hash(R || A || m) * d) mod q$

The verification checks:

1. $s_2 = Hash(R || A || m)$
2. Verifier needs to check if $v1 = v2$
- $v1 = s_1G$
- $v_2 = R + ds_2$
$$
\begin{align}
v_2 &= R + ds_2 \\
&= rG + d*Hash(R || A || m) \\
&= (r + d*Hash(R || A || m))G \\
&= s_1 G
\end{align}
$$

# Schnorr's Signature - a sig algo used in ZKP
Schnorr Signature Protocol is signature scheme invented by Claus Schnorr, which is widely known for its simplicity and efficiency, and **also can be used in ZKP.**

Just like other DSAs, Schnorr Signature Protocol has several steps:
1. **Setup**
2. **Generate Signature**
3. **Verify Signature**

## Setup

First, consider several parameters:
- **d**: the secret key ($0 < s < q$)
- **A**: the public key $A = dG$

> These parameters are required for Alice to create a sig for a message $m$.

## Generate Signature

1. Alice choose a random number $k$ s.t. $0 < k < q$ to generate $R=kG$
2. Compute $s = k - Hash(m || R) * d$
3. Compute $r = R_x (mod \ n)$

pair $(r,s)$ is the signature.

## Verify Signature

> Another person, Bob, want to verify if this Sig is from Alice, he can use $v, p, q, a$ to verifiy it.

Check if this $d * Hash(m || R) + sG = R = kG$ is true

## ZKP properties
- Completeness: If the statement is true, an honest verifier will be convinced by the honest prover.
- Soundness: If the statement is false, cheating prover have really some prob. to convince the honest verifier that it's true.
- ZK: for all verifiers, they do not gain any external infomation from this statement.

# References
- [Secret Key Exchange (Diffie-Hellman) - Computerphile](https://youtu.be/NmM9HA2MQGI?list=PLzH6n4zXuckpoaxDKOOV26yhgoY2S-xYg)
- [A (relatively easy to understand) primer on elliptic curve cryptography](https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/)
- [Schnorr Digital Signature - Geeksforgeeks](https://www.geeksforgeeks.org/schnorr-digital-signature/)