Offensive Security Researcher & Quantum Cryptography Analyst

Linear Programming Algorithm: Working, Explanation, and Optimization Methods

Abdul Wahab Junaid
Linear programming algorithm and working of this algorithm

I find the Diffie-Hellman key exchange to be one of the most elegant ideas in all of cryptography, because it solves a problem that seems almost paradoxical at first glance: how can two people agree on a shared secret while communicating entirely over a channel that an eavesdropper can listen to completely? Diffie-Hellman is a method for two parties to establish a shared secret key over an insecure channel, without ever transmitting the key itself. Its importance is hard to overstate — it underlies the key exchange step in TLS/SSL (which secures most of the web), SSH, VPN protocols, and many other systems where I need two parties to establish secure, encrypted communication without having met beforehand to exchange secrets in person.

History and Background

I credit Whitfield Diffie and Martin Hellman with publishing this method in their landmark 1976 paper “New Directions in Cryptography,” which is widely regarded as the paper that founded public-key cryptography as a field. Ralph Merkle also contributed foundational ideas around the same time (Merkle’s puzzles), and the method is sometimes called Diffie-Hellman-Merkle key exchange in recognition of this. What I find historically fascinating is that classified work by British intelligence (GCHQ) — specifically by Malcolm Williamson — had actually developed equivalent ideas a few years earlier, around 1974, but this work remained secret until it was declassified in 1997, long after Diffie and Hellman’s public work had already transformed the field. Diffie and Hellman’s 1976 paper predates RSA (1977) and set the conceptual stage for the entire idea that cryptographic keys could be split into public and private components — even though, notably, the original Diffie-Hellman protocol itself is a key-exchange mechanism, not a full public-key encryption scheme.

Problem Statement

I use Diffie-Hellman to solve the key distribution problem: two parties, who have never met and share no prior secret, want to establish a shared secret key over a communication channel that a third party can freely observe (but not alter, in the basic version). Before public-key cryptography, secure communication required parties to have exchanged secret keys through some trusted, secure channel beforehand — which is impractical at internet scale. The problem Diffie-Hellman solves is enabling this shared secret to be derived even when every single message exchanged between the two parties is visible to an eavesdropper, relying on a mathematical asymmetry: certain operations are easy to compute in one direction but computationally infeasible to reverse.

Core Concepts

How It Works

I walk through the classic Diffie-Hellman exchange between two parties, whom I’ll call Alice and Bob:

  1. Alice and Bob publicly agree on a large prime $p$ and a generator $g$ (these values do not need to be secret).
  2. Alice privately chooses a random secret integer $a$ (her private key).
  3. Bob privately chooses a random secret integer $b$ (his private key).
  4. Alice computes her public key $A = g^a \bmod p$ and sends $A$ to Bob over the insecure channel.
  5. Bob computes his public key $B = g^b \bmod p$ and sends $B$ to Alice over the insecure channel.
  6. Alice computes the shared secret as $s = B^a \bmod p$.
  7. Bob computes the shared secret as $s = A^b \bmod p$.
  8. Because of the algebraic properties of modular exponentiation, both computations yield the same value $s = g^{ab} \bmod p$, which becomes their shared secret key, even though neither party ever transmitted $a$, $b$, or $s$ directly.

Working Principle

The internal logic rests entirely on a mathematical asymmetry: computing $g^x \bmod p$ given $g$, $x$, and $p$ (modular exponentiation) is computationally easy, even for very large numbers, using efficient algorithms like fast exponentiation. But going the other direction — given $g$, $p$, and $g^x \bmod p$, finding $x$ — is believed to be computationally infeasible for well-chosen large primes, and this is known as the discrete logarithm problem. An eavesdropper watching the exchange sees $p$, $g$, $A=g^a \bmod p$, and $B=g^b \bmod p$, but to compute the shared secret $g^{ab} \bmod p$, they would need to solve the discrete logarithm problem to recover $a$ or $b$ from the intercepted public values — and no efficient classical algorithm is known for this problem when the parameters are large enough (this specific difficulty, of computing $g^{ab}$ from $g^a$ and $g^b$ without knowing $a$ or $b$, is called the Computational Diffie-Hellman problem, and it’s believed to be as hard as the discrete logarithm problem itself).

Mathematical Foundation

Given a publicly agreed prime $p$ and generator $g$, the exchange proceeds as follows.

Alice’s public key:

$$ A = g^a \bmod p $$

Bob’s public key:

$$ B = g^b \bmod p $$

Alice computes the shared secret:

$$ s = B^a \bmod p = (g^b)^a \bmod p = g^{ba} \bmod p $$

Bob computes the shared secret:

$$ s = A^b \bmod p = (g^a)^b \bmod p = g^{ab} \bmod p $$

Since exponentiation is commutative ($g^{ab} = g^{ba}$), both parties arrive at the identical value:

$$ s = g^{ab} \bmod p $$

The security of the scheme rests on the assumed computational hardness of the discrete logarithm problem: given $p$, $g$, and $A = g^a \bmod p$, finding $a$ requires (for classical computers, with well-chosen parameters) time exponential (or at least sub-exponential, using the best known algorithms like the General Number Field Sieve for discrete logs) in the bit-length of $p$.

Diagrams

sequenceDiagram
    participant Alice
    participant Eavesdropper
    participant Bob
    Note over Alice,Bob: Publicly agree on prime p and generator g
    Alice->>Alice: choose private key a
    Bob->>Bob: choose private key b
    Alice->>Eavesdropper: send A = g^a mod p
    Eavesdropper->>Bob: A = g^a mod p (visible, unmodified)
    Bob->>Eavesdropper: send B = g^b mod p
    Eavesdropper->>Alice: B = g^b mod p (visible, unmodified)
    Alice->>Alice: compute s = B^a mod p
    Bob->>Bob: compute s = A^b mod p
    Note over Alice,Bob: Both now share the same secret s = g^(ab) mod p

Pseudocode

function DiffieHellman():
    // Publicly agreed values
    p = large_prime()
    g = primitive_root_mod(p)

    // Alice's side
    a = random_private_key(1, p-2)
    A = mod_exp(g, a, p)
    send(A) to Bob

    // Bob's side
    b = random_private_key(1, p-2)
    B = mod_exp(g, b, p)
    send(B) to Alice

    // Shared secret computation
    alice_secret = mod_exp(B, a, p)
    bob_secret = mod_exp(A, b, p)

    assert alice_secret == bob_secret
    return alice_secret   // == g^(ab) mod p

Step-by-Step Example

I will use small numbers here purely for illustration; real-world use requires primes hundreds or thousands of bits long.

Time Complexity

Each party performs one modular exponentiation to compute their public key, and one more to compute the shared secret. Using fast (repeated squaring) exponentiation, computing $g^x \bmod p$ takes $O(\log x)$ multiplications, and each modular multiplication of $k$-bit numbers costs $O(k^2)$ using schoolbook multiplication (or faster with more advanced multiplication algorithms). So each exponentiation costs roughly $O(k^3)$ for $k$-bit numbers using simple methods, or better with optimized big-integer arithmetic. Since each party only performs a small, constant number of exponentiations (typically two), the overall computational cost of the protocol itself is efficient and practical even for the large key sizes (2048+ bits) used in real deployments.

Space Complexity

Each party needs to store the public parameters $p$ and $g$, their own private key, the other party’s public key, and the resulting shared secret — all of which are single integers of size $O(k)$ bits, where $k$ is the chosen security parameter (key length). So the space complexity is $O(k)$, extremely modest even for cryptographically strong key sizes, since I’m only ever storing a handful of large integers, not arrays or matrices that scale with input size.

Correctness Analysis

I verify correctness algebraically: both parties compute $g^{ab} \bmod p$, just by different paths — Alice computes $(g^b)^a \bmod p$ and Bob computes $(g^a)^b \bmod p$ — and because exponentiation is commutative under modular arithmetic (a property inherited directly from the fact that ordinary integer exponentiation satisfies $(g^b)^a = (g^a)^b = g^{ab}$, and this equality is preserved when reducing modulo $p$), both parties are mathematically guaranteed to arrive at an identical value, with no possibility of divergence given correct implementation. Security correctness (as opposed to functional correctness) is a separate matter and rests on an unproven but widely believed computational assumption: that the discrete logarithm problem (and the related Computational and Decisional Diffie-Hellman problems) is hard for classical computers given large enough parameters. I should note that this assumption does not hold against a sufficiently large quantum computer, since Shor’s algorithm can solve discrete logarithms efficiently on such a machine — this is why post-quantum key exchange methods are an active area of research and eventual replacement for classical Diffie-Hellman in security-critical, long-lived systems.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Educational implementation using small numbers.
// Real-world use requires big-integer arithmetic libraries and
// cryptographically secure random number generation with large primes.

// Fast modular exponentiation: computes (base^exp) mod mod
long long mod_exp(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1)                 // if exponent is odd
            result = (result * base) % mod;
        exp = exp >> 1;                   // divide exponent by 2
        base = (base * base) % mod;       // square the base
    }
    return result;
}

int main() {
    srand((unsigned) time(NULL));

    // Step 1: publicly agreed parameters (small values for demonstration only)
    long long p = 23;   // prime modulus
    long long g = 5;    // generator (primitive root mod p)

    printf("Public parameters: p = %lld, g = %lld\n", p, g);

    // Step 2: Alice picks a private key and computes her public key
    long long a = 2 + rand() % (int)(p - 3);  // private key in [2, p-2]
    long long A = mod_exp(g, a, p);
    printf("Alice's private key a = %lld, public key A = %lld\n", a, A);

    // Step 3: Bob picks a private key and computes his public key
    long long b = 2 + rand() % (int)(p - 3);
    long long B = mod_exp(g, b, p);
    printf("Bob's private key b = %lld, public key B = %lld\n", b, B);

    // Step 4: exchange A and B over the (insecure) channel, then compute shared secret
    long long alice_secret = mod_exp(B, a, p);
    long long bob_secret = mod_exp(A, b, p);

    printf("Alice computes shared secret: %lld\n", alice_secret);
    printf("Bob computes shared secret:   %lld\n", bob_secret);

    if (alice_secret == bob_secret)
        printf("Success: both parties derived the same shared secret.\n");
    else
        printf("Error: shared secrets do not match.\n");

    return 0;
}

Sample Input and Output

With $p=23$, $g=5$, and randomly chosen private keys, a typical run produces output like:

Public parameters: p = 23, g = 5
Alice's private key a = 6, public key A = 8
Bob's private key b = 15, public key B = 19
Alice computes shared secret: 2
Bob computes shared secret:   2
Success: both parties derived the same shared secret.

This matches my hand-worked example earlier, confirming both parties independently arrive at the shared secret value of 2.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version