Applications to Cryptography

Applications to Cryptography

Abstract algebra underpins modern cryptography. Let's implement two foundational protocols using finite field arithmetic.

Diffie-Hellman Key Exchange

Two parties (Alice and Bob) agree on a public prime $p$ and primitive root $g$. Then:

1. Alice picks secret $a$, computes $A = g^a \bmod p$, sends $A$ to Bob
2. Bob picks secret $b$, computes $B = g^b \bmod p$, sends $B$ to Alice
3. Both compute the shared secret: $s = B^a \bmod p = A^b \bmod p = g^{ab} \bmod p$

An eavesdropper sees $g, p, A, B$ but computing $a$ from $A = g^a \bmod p$ requires solving the discrete logarithm — believed to be hard for large primes.

ElGamal Encryption

Built on top of Diffie-Hellman:

Key Generation: Choose prime $p$, generator $g$, secret key $x$. Public key is $h = g^x \bmod p$.

Encrypt message $m$ (where $1 \le m < p$):

1. Pick random $k$
2. $c_1 = g^k \bmod p$
3. $c_2 = (m \cdot h^k) \bmod p$
4. Ciphertext is $(c_1, c_2)$

Decrypt: $m = c_2 \cdot (c_1^x)^{-1} \bmod p = c_2 \cdot c_1^{p-1-x} \bmod p$

Modular Exponentiation

Both protocols rely on fast modular exponentiation:

def mod_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return result

Your Task

Implement diffie_hellman(g, p, a, b) returning the shared secret, and elgamal_encrypt(p, g, h, m, k) / elgamal_decrypt(p, x, c1, c2) for ElGamal encryption.