Diffie-Hellman Key Exchange Implementation

This repository contains an implementation of the Diffie-Hellman (DH) key exchange protocol using Python (sage). The project explores four scenarios ranging from a basic exchange to an authenticated version that is resistant to Man-in-the-Middle (MITM) attacks.

Mathematical Background

The security of the Diffie-Hellman protocol relies on the computational difficulty of the Discrete Logarithm Problem (DLP).

Scenario I: Basic Diffie-Hellman with Sophie-Germain Primes

Sophie-Germain Primes The implementation uses Sophie-Germain primes to ensure a strong subgroup. A prime $p$ is a Sophie-Germain prime if $p = 2q + 1$ where $q$ is also prime. This structure minimizes the risk of small subgroup attacks.

Generator Selection We work in the multiplicative group $\mathbb{Z}_p^*$. A generator $g$ is selected such that it generates the entire group or a large subgroup. The code verifies that:

1. $g^2 \not\equiv 1 \pmod p$
2. $g^q \not\equiv 1 \pmod p$ This ensures $g$ has order $2q = p-1$ (generating $\mathbb{Z}_p^*$) or $q$ (generating the large subgroup of quadratic residues).

Key Exchange Protocol

1. Alice chooses a secret integer $a$ and sends $A = g^a \pmod p$.
2. Bob chooses a secret integer $b$ and sends $B = g^b \pmod p$.
3. Shared Secret:
   • Alice computes $K = B^a \pmod p = (g^b)^a = g^{ab} \pmod p$.
   • Bob computes $K = A^b \pmod p = (g^a)^b = g^{ab} \pmod p$.

Scenario II: Man-in-the-Middle (MITM) Attack

In this scenario, an adversary Charlie intercepts the communication between Alice and Bob.

1. Charlie generates his own secrets $c_1, c_2$.
2. Charlie sends $A_{fake} = g^{c_1}$ to Bob (pretending to be Alice).
3. Charlie sends $B_{fake} = g^{c_2}$ to Alice (pretending to be Bob).
4. Result:
   • Alice computes a key with Charlie: $K_{AC} = (B_{fake})^a \pmod p$.
   • Bob computes a key with Charlie: $K_{BC} = (A_{fake})^b \pmod p$.
   • Alice and Bob believe they have a shared secure channel, but Charlie can decrypt, read, and re-encrypt all messages.

Scenario III: RSA Digital Signatures

To prevent MITM, we use RSA signatures for authentication.

Key Generation

• Primes $p, q$ are generated.
• Modulus $n = p \times q$.
• Public exponent $e = 65537$.
• Private exponent $d$ is computed such that $e \cdot d \equiv 1 \pmod{\phi(n)}$.

CRT Optimization (Chinese Remainder Theorem) Signing is computationally expensive. The implementation uses CRT to speed up modular exponentiation with the private key:

1. $d_p = d \pmod{p-1}$
2. $d_q = d \pmod{q-1}$
3. $q_{inv} = q^{-1} \pmod p$

The signature $s$ for a message $m$ is computed by:

• $m_1 = m^{d_p} \pmod p$
• $m_2 = m^{d_q} \pmod q$
• $h = q_{inv} \cdot (m_1 - m_2) \pmod p$
• $s = m_2 + h \cdot q$

This is approximately 4x faster than standard exponentiation $m^d \pmod n$.

Scenario IV: Authenticated Diffie-Hellman

This scenario combines DH with RSA signatures to defeat the MITM attack.

Protocol

1. Alice sends $A = g^a \pmod p$ and a signature $S_A = \text{Sign}_{priv_A}(A)$.
2. Bob sends $B = g^b \pmod p$ and a signature $S_B = \text{Sign}_{priv_B}(B)$.
3. Verification:
   • Alice verifies Bob's signature using Bob's public key.
   • Bob verifies Alice's signature using Alice's public key.
4. If signatures are valid, they proceed to compute the shared secret $K = g^{ab} \pmod p$.

Why MITM Fails Charlie cannot forge valid signatures for his fake values $A_{fake}$ and $B_{fake}$ because he does not possess Alice's or Bob's private RSA keys. If he simply forwards the original values $A, B$ with their signatures, he cannot compute the shared key $g^{ab}$ without knowing $a$ or $b$.