# Introduction to Public Key Cryptography II

## Diffie-Hellman Key Exchange

This mechanism is one of the earliest approaches in public-key cryptography. Its primary objective is to address the key distribution problem. While it is not an encryption algorithm, it serves as a key exchange protocol that employs clever mathematical principles to securely establish a shared key between two parties.

### How DH works:

Assume we have 2 parties, Alice and Bob

1. **Parameter Agreement**:

Alice and Bob agree on two public parameters, ggg and PPP, over an insecure channel.

* g: A generator (usually a small integer).
* P: A large prime number.

2. **Secret Value Generation**:

Alice generates a secret value $$\alpha$$, and uses it to derive A, where $$A \equiv g^{\alpha} \pmod P$$

Bob generates a secret value $$\beta$$, and uses it to derive B, where $$B \equiv g^{\beta} \pmod P$$

5. **Exchnage**

Alice and Bob exchange A and B over the insecure channel.

6. **Shared Secret Computation**:

Alice computes the shared secret by computing $$S \equiv B^{\alpha} \pmod P$$

Bob computes the shared secret by computing $$S \equiv A^{\beta} \pmod P$$

Let's breakdown the math:

$$S \equiv A^{\beta}  \equiv g ^{\alpha^{\beta}} \equiv g^{\alpha\times \beta} \pmod P$$ # Bob Side

$$S \equiv B^{\alpha}  \equiv g ^{\beta^{\alpha}} \equiv g^{\beta \times \alpha} \pmod P$$ # Alice Side

## Diffie-Hellman Security (Discrete Logarithm Problem)

The **Discrete Logarithm Problem (DLP)** is a foundational mathematical challenge in the field of cryptography. Its significance lies in its use for ensuring the security of key exchange protocols, digital signatures, and other cryptographic primitives.

### **What Is the Discrete Logarithm Problem?**

The problem is defined as follows:\
Given three numbers g, P, and A, where $$A = g^a \mod P$$, find the exponent a. This is the discrete logarithm of A to the base g, modulo P. Symbolically:

$$a = \log\_g A \mod P$$

Unlike logarithms in real numbers, finding a in modular arithmetic is computationally hard when P is large, even though the forward operation $$A = g^a \mod P$$ is straightforward. This one-way property is what makes the DLP crucial for cryptographic security.

{% hint style="info" %}
Learn more about DH by playing with <https://cryptohack.org/challenges/diffie-hellman/>
{% endhint %}