Home
5
Bash

Diffie Hellman in Bash: Complete Solution & Deep Dive Guide

man in black shirt using laptop computer and flat screen monitor

The Ultimate Guide to Diffie-Hellman Key Exchange in Bash

The Diffie-Hellman key exchange is a foundational cryptographic method allowing two parties, with no prior knowledge of each other, to jointly establish a shared secret key over an insecure channel. This guide explains how it works and demonstrates a complete implementation using a Bash script.

The Digital Handshake Problem: How to Share a Secret in Public

Imagine you and a friend are in a crowded room, needing to agree on a secret password. The problem is, anyone can hear you speak. You can't just shout the password across the room. You could write it down, lock it in a box, and send the box over, but your friend needs the key to open it. How do you get them the key without an eavesdropper intercepting it?

This is the classic key exchange problem that has plagued spies, generals, and now, internet protocols for centuries. In the digital world, every time you visit a secure website (HTTPS), send a private message, or connect to a VPN, your device performs a version of this digital handshake to establish a secure, encrypted session. It needs to agree on a secret key with a server without sending that key "in the clear" for attackers to see.

This is where the magic of the Diffie-Hellman key exchange comes in. It's a clever mathematical trick that allows two parties to create an identical shared secret without ever transmitting it directly. In this deep dive, we'll not only unravel the theory but also build a working implementation from scratch using the humble yet powerful Bash shell, a core module in the kodikra.com learning path.

What Is the Diffie-Hellman Key Exchange?

The Diffie-Hellman key exchange is not an encryption algorithm itself; it is a key agreement protocol. Its sole purpose is to generate a symmetric secret key that both parties can then use with a separate encryption algorithm (like AES) to secure their subsequent communications. It was one of the earliest practical examples of public-key cryptography, published by Whitfield Diffie and Martin Hellman in 1976.

The core idea relies on the mathematical difficulty of solving the discrete logarithm problem. In simple terms, it's easy to calculate exponents (like 5^3 = 125), but it's incredibly difficult to work backward and find the exponent if you only know the base and the result (finding x in 5^x = 125 is easy, but finding x in 5^x mod 23 = 8 is much, much harder for large numbers).

The most common analogy used to explain this is the paint mixing analogy:

  1. Public Color: Alice and Bob agree on a common, public color (e.g., yellow). This is analogous to the public prime numbers p and g.
  2. Private Colors: Alice chooses a secret color (e.g., red), and Bob chooses his own secret color (e.g., blue). These are their private keys, a and b.
  3. Mix and Share: Alice mixes her secret red with the public yellow to get orange. Bob mixes his secret blue with the public yellow to get green. They send these new mixed colors (orange and green) to each other over the public channel. These are their public keys, A and B.
  4. Create Shared Secret: Now, Alice takes Bob's mixed color (green) and adds her original secret color (red). Bob takes Alice's mixed color (orange) and adds his original secret color (blue).

The result? Both end up with the exact same final color (a muddy brown), which is their shared secret. An eavesdropper who only saw the public yellow and the mixed orange and green colors would find it practically impossible to separate the original secret colors to replicate the final mixture. This is the essence of Diffie-Hellman's security.

How Does the Math Behind Diffie-Hellman Work?

The security of the protocol is rooted in modular arithmetic. Let's break down the components and the step-by-step process. The entire exchange relies on two numbers that are public and agreed upon beforehand: a large prime number p and a primitive root modulo p, g.

The Key Components

  • p: A very large prime number. This is the modulus for all operations. It's public.
  • g: A primitive root modulo p (also called a generator). It's a number whose powers can generate many other numbers within the set modulo p. It's also public.
  • a: Alice's private key, a secret integer she chooses. It must be greater than 1 and less than p.
  • b: Bob's private key, a secret integer he chooses, also greater than 1 and less than p.
  • A: Alice's public key, which she calculates and sends to Bob.
  • B: Bob's public key, which he calculates and sends to Alice.
  • s: The final shared secret key, which both Alice and Bob calculate independently but arrive at the same value.

The Exchange Process Step-by-Step

Here is the flow of the entire key exchange, from setup to the final shared secret.

    ● Start: Agree on public p and g
    │
    ├───────── Alice's Side ──────────┬────────── Bob's Side ───────────┐
    │                                 │                                  │
    ▼                                 ▼                                  ▼
┌───────────────┐               ┌───────────────┐                  ┌───────────────┐
│ Chooses private │               │   (Public Channel)  │                  │ Chooses private │
│ key 'a'       │               │                     │                  │ key 'b'       │
└───────┬───────┘               └─────────────────────┘                  └───────┬───────┘
        │                                                                        │
        ▼                                                                        ▼
┌───────────────┐                                                        ┌───────────────┐
│ Calculates    │                                                        │ Calculates    │
│ A = g^a mod p │                                                        │ B = g^b mod p │
└───────┬───────┘                                                        └───────┬───────┘
        │                                                                        │
        └───────────── A ⟶ ───────────┬──────────── ⟵ B ──────────────┘
                                      │
                                      ▼
┌───────────────┐               ┌───────────────┐                  ┌───────────────┐
│ Receives B    │               │  (Eavesdropper │                  │ Receives A    │
│               │               │   sees A, B)    │                  │               │
└───────┬───────┘               └───────────────┘                  └───────┬───────┘
        │                                                                        │
        ▼                                                                        ▼
┌───────────────┐                                                        ┌───────────────┐
│ Calculates    │                                                        │ Calculates    │
│ s = B^a mod p │                                                        │ s = A^b mod p │
└───────┬───────┘                                                        └───────┬───────┘
        │                                                                        │
        └────────────────────────────┬───────────────────────────────────────────┘
                                     │
                                     ▼
                               ┌───────────┐
                               │  Shared   │
                               │ Secret 's'│
                               └───────────┘
                                     ● End
  1. Setup: Alice and Bob agree on the public values for p and g.
  2. Private Key Generation: Alice secretly chooses an integer a. Bob secretly chooses an integer b. These numbers never leave their respective machines.
  3. Public Key Calculation:
    • Alice calculates her public key A using the formula: A = g^a mod p
    • Bob calculates his public key B using the formula: B = g^b mod p
  4. Public Key Exchange: Alice sends her public key A to Bob, and Bob sends his public key B to Alice. An eavesdropper can see A and B, but this is not a problem.
  5. Shared Secret Calculation:
    • Alice takes Bob's public key B and uses her own private key a to calculate the secret: s = B^a mod p
    • Bob takes Alice's public key A and uses his own private key b to calculate the secret: s = A^b mod p

Because of the properties of modular exponentiation, both calculations yield the exact same result!
Alice's calculation: s = B^a mod p = (g^b mod p)^a mod p = g^(b*a) mod p
Bob's calculation: s = A^b mod p = (g^a mod p)^b mod p = g^(a*b) mod p
Since g^(b*a) mod p is the same as g^(a*b) mod p, they arrive at the identical shared secret s.

Where to Implement It: A Full Bash Script Solution

While languages like Python or Go have built-in libraries for handling large number arithmetic, Bash requires an external utility for this task. The most common and widely available tool is bc (Basic Calculator), which supports arbitrary-precision arithmetic.

This script, developed as part of the kodikra.com Bash curriculum, simulates the entire Diffie-Hellman exchange.

The Complete Bash Script

#!/bin/bash

# A script to demonstrate the Diffie-Hellman key exchange.
# This is for educational purposes only and is NOT cryptographically secure
# for real-world use due to the use of insecure random number generation
# and lack of proper validation.

# --- Function for Modular Exponentiation using bc ---
# Calculates (base^exponent) % modulus
# $1: base
# $2: exponent
# $3: modulus
mod_exp() {
    local base=$1
    local exp=$2
    local mod=$3
    # bc is a command-line calculator that can handle large numbers.
    # The 'A=B;if(A<0)A+=C;A' part handles potential negative results from bc's % operator.
    echo "ibase=10; obase=10; scale=0; val=($base^$exp)%$mod; if(val<0) val+=$mod; val" | bc
}

# --- Main script logic ---
main() {
    # Step 0: The prime numbers p and g are provided.
    # We expect them as command-line arguments.
    if [[ $# -ne 2 ]]; then
        echo "Usage: $0 <prime_p> <generator_g>"
        echo "Example: $0 23 5"
        exit 1
    fi

    local p=$1
    local g=$2

    echo "--- Public Parameters ---"
    echo "Prime (p): $p"
    echo "Generator (g): $g"
    echo ""

    # Step 1: Alice and Bob pick private keys 'a' and 'b'.
    # These must be greater than 1 and less than p.
    # NOTE: $RANDOM is NOT cryptographically secure. For a real application,
    # you would use a source like /dev/urandom.
    local a=$(( ($RANDOM % ($p - 2)) + 2 ))
    local b=$(( ($RANDOM % ($p - 2)) + 2 ))

    echo "--- Private Key Generation (Secret) ---"
    echo "Alice's private key (a): $a"
    echo "Bob's private key (b): $b"
    echo ""

    # Step 2: Alice and Bob calculate their public keys.
    # Alice's Public Key: A = g^a mod p
    # Bob's Public Key:   B = g^b mod p
    echo "--- Public Key Calculation & Exchange ---"
    local public_A=$(mod_exp "$g" "$a" "$p")
    local public_B=$(mod_exp "$g" "$b" "$p")

    echo "Alice calculates public key (A) and sends to Bob: $public_A"
    echo "Bob calculates public key (B) and sends to Alice: $public_B"
    echo ""

    # Step 3: Alice and Bob generate the shared secret.
    # Alice's calculation: s = B^a mod p
    # Bob's calculation:   s = A^b mod p
    echo "--- Shared Secret Calculation ---"
    local secret_s_alice=$(mod_exp "$public_B" "$a" "$p")
    local secret_s_bob=$(mod_exp "$public_A" "$b" "$p")

    echo "Alice calculates shared secret (s1): $secret_s_alice"
    echo "Bob calculates shared secret (s2): $secret_s_bob"
    echo ""

    # Step 4: Verification
    echo "--- Verification ---"
    if [[ "$secret_s_alice" -eq "$secret_s_bob" ]]; then
        echo "✅ Success! The shared secrets match."
        echo "Final Shared Secret: $secret_s_alice"
    else
        echo "❌ Error! The shared secrets DO NOT match."
    fi
}

# Execute the main function with all command-line arguments
main "$@"

How to Run the Script

1. Save the code above into a file named diffie_hellman.sh.
2. Make the script executable from your terminal:

chmod +x diffie_hellman.sh

3. Run the script, providing the public prime p and generator g as arguments. A classic example uses p=23 and g=5.

./diffie_hellman.sh 23 5

Expected Output

The output will show the entire process, and because the private keys a and b are generated randomly each time, the public keys and shared secret will be different on each run.

--- Public Parameters ---
Prime (p): 23
Generator (g): 5

--- Private Key Generation (Secret) ---
Alice's private key (a): 15
Bob's private key (b): 7

--- Public Key Calculation & Exchange ---
Alice calculates public key (A) and sends to Bob: 19
Bob calculates public key (B) and sends to Alice: 17

--- Shared Secret Calculation ---
Alice calculates shared secret (s1): 2
Bob calculates shared secret (s2): 2

--- Verification ---
✅ Success! The shared secrets match.
Final Shared Secret: 2

Code Walkthrough and Explanation

1. The mod_exp Function

This is the heart of the script. Bash's native arithmetic operators ($((...))) cannot handle the large numbers required for real cryptography. The bc command is a powerful tool that can.

echo "ibase=10; ... val=($base^$exp)%$mod; ... val" | bc

Let's break down this command:

  • echo "..." | bc: This pipes a string of commands into the bc interpreter.
  • ibase=10; obase=10;: Sets the input and output number base to 10 (decimal).
  • scale=0;: Ensures the output is an integer, with no decimal places.
  • val=($base^$exp)%$mod: This is the core mathematical operation. It calculates base to the power of exponent, and then finds the remainder when divided by modulus.
  • if(val<0) val+=$mod: A crucial fix. Some versions of bc can return a negative result for the modulo operator. In modular arithmetic, the result should always be positive. This line ensures that if the result is negative, we add the modulus to bring it back into the correct positive range.

This function elegantly encapsulates the complex math, allowing the main script to be clean and readable.

    ● Start Calculation: mod_exp(base, exp, mod)
    │
    ▼
  ┌───────────────────────────┐
  │ Construct `bc` command string │
  │ e.g., "(5^15)%23"           │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ Pipe string to `bc` process │
  │ `echo "..." | bc`         │
  └────────────┬──────────────┘
               │
               ▼
    ◆ `bc` computes result ◆
   ╱            ╲
 Negative       Positive
  │              │
  ▼              ▼
┌──────────┐   ┌────────────┐
│ Add modulus│   │ Use result │
│ to make it │   │ directly   │
│ positive   │   │            │
└─────┬────┘   └─────┬──────┘
      │              │
      └───────┬──────┘
              ▼
    ● Return final integer result

2. Main Script Logic

The main() function orchestrates the entire key exchange simulation.

  • Argument Handling: The script first checks if exactly two arguments (p and g) were provided. This is basic input validation and good scripting practice.
  • Private Key Generation: The line a=$(( ($RANDOM % ($p - 2)) + 2 )) generates a pseudo-random number. $RANDOM gives an integer between 0 and 32767. % ($p - 2) scales it to a range from 0 to p-3. Adding 2 shifts the range to 2 to p-1, satisfying the condition that the private key must be greater than 1 and less than p.
  • Calling mod_exp: The script then calls our helper function four times: twice to generate the public keys (A and B) and twice to generate the shared secrets from Alice's and Bob's perspectives.
  • Verification: The final if statement is the moment of truth. It compares the secret Alice calculated (secret_s_alice) with the one Bob calculated (secret_s_bob). If they match, the protocol was successful.

Security Considerations and Real-World Applications

Pros and Cons of Diffie-Hellman

Like any cryptographic protocol, Diffie-Hellman has its strengths and weaknesses, which are important to understand.

Pros (Advantages) Cons (Disadvantages)
Forward Secrecy: If a long-term key is compromised, past session keys remain secure. Each session generates a new, ephemeral key. Vulnerable to Man-in-the-Middle (MITM) Attacks: The basic protocol does not authenticate the parties. An attacker can sit between Alice and Bob and establish separate keys with each, relaying messages while decrypting them.
No Pre-Shared Secret Needed: The entire point is to establish a secret over an insecure channel, making it ideal for initial connections. Computationally Intensive: Modular exponentiation with very large numbers is resource-intensive compared to symmetric encryption.
Widely Studied and Trusted: The protocol has been analyzed by cryptographers for decades and its security is well-understood. Requires Careful Parameter Selection: The security relies on using a large enough prime (p) and a well-chosen generator (g) to prevent certain attacks.

The Man-in-the-Middle (MITM) Attack

The most significant vulnerability in the raw Diffie-Hellman exchange is the MITM attack. An attacker, Eve, can intercept the initial communication.

  1. Alice sends her public key A to Bob, but Eve intercepts it.
  2. Eve generates her own key pair (e, E) and sends her public key E to Bob, pretending it's from Alice.
  3. Bob sends his public key B to Alice, but Eve intercepts it.
  4. Eve sends her public key E to Alice, pretending it's from Bob.
Now, Alice and Eve share a secret key, and Bob and Eve share a different secret key. Eve can decrypt messages from Alice, re-encrypt them with Bob's key, and send them on. Both Alice and Bob think they have a secure channel, but Eve is reading everything. To prevent this, Diffie-Hellman is almost always used with an authentication mechanism, like digital signatures (e.g., RSA or ECDSA), to verify the identities of the participants.

Future-Proofing: Elliptic Curve Diffie-Hellman (ECDH)

As computing power increases, the size of the prime number p needed for classic Diffie-Hellman to remain secure must also increase. This leads to slower computations. The modern successor is Elliptic Curve Diffie-Hellman (ECDH).

ECDH applies the same principles but uses the mathematics of elliptic curves. It provides the same level of security with much smaller key sizes, making it faster and more efficient, especially for mobile and embedded devices. Today, ECDH is the standard for most TLS/SSL handshakes on the modern web. The underlying concept of exchanging public points and using a private scalar to derive a shared secret remains the same.

Frequently Asked Questions (FAQ)

Is Diffie-Hellman an encryption algorithm?

No, it is a key agreement protocol, not an encryption algorithm. Its only job is to help two parties securely establish a shared secret key. This shared key is then used by a separate symmetric encryption algorithm, like AES, to actually encrypt and decrypt the data being communicated.

Why are large prime numbers so important for security?

The security of Diffie-Hellman relies on the difficulty of the discrete logarithm problem. Solving this problem becomes exponentially harder as the size of the prime number p increases. If a small prime is used (like 23 in our example), an attacker could simply try all possible private keys (brute-force) to find the secret. For real-world security, primes of 2048 bits or more are standard.

What is a Man-in-the-Middle (MITM) attack on Diffie-Hellman?

A MITM attack occurs when an attacker secretly positions themselves between two communicating parties. The attacker intercepts the public keys being exchanged and substitutes their own. This allows the attacker to establish a separate secure session with each party, making both believe they are talking directly and securely to each other, while the attacker can read, modify, and relay all messages.

Can I use this Bash script for a real-world secure application?

Absolutely not. This script is purely for educational purposes to demonstrate the algorithm's logic. It has several critical security flaws for production use: 1) It uses $RANDOM, which is a predictable, non-cryptographically secure random number generator. 2) It lacks input validation for primality and generator quality. 3) It does not include any authentication, making it vulnerable to MITM attacks. Real-world implementations use highly vetted cryptographic libraries.

What is Elliptic Curve Diffie-Hellman (ECDH)?

ECDH is a modern variant of the Diffie-Hellman protocol that uses the algebraic structure of elliptic curves over finite fields. It provides equivalent security to classic Diffie-Hellman but with significantly smaller key sizes. This makes it much more efficient in terms of computation speed and bandwidth, which is why it's the preferred method in most modern applications like TLS 1.3.

How does bc handle the large number calculations that Bash can't?

bc is an "arbitrary-precision calculator language." Unlike Bash's fixed-size integer arithmetic (usually 64-bit), bc can handle numbers of virtually any size, limited only by the available system memory. It is specifically designed for high-precision scientific and mathematical calculations, making it the perfect command-line tool for demonstrating cryptographic algorithms that rely on very large numbers.

What exactly is a "primitive root modulo p"?

In simple terms, a number g is a primitive root modulo p if its powers (g^1 mod p, g^2 mod p, ..., g^(p-1) mod p) generate all the numbers from 1 to p-1 in some order. Using a generator ensures that the resulting public keys are well-distributed across the possible values, which is an important property for the security of the system.

Conclusion: From Theory to Practical Understanding

The Diffie-Hellman key exchange is a testament to the elegance and power of number theory in solving real-world security problems. By allowing two parties to derive a shared secret in plain sight, it laid the groundwork for the secure internet we use today. While the raw algorithm requires authentication to be truly secure, its core principle remains a cornerstone of modern cryptography.

By building a simulation in Bash, you move beyond abstract theory and gain a concrete understanding of the mechanics. You see how public and private components interact, how modular exponentiation works with large numbers via tools like bc, and how two independent calculations can magically arrive at the same secret result. This hands-on experience is invaluable for any developer or system administrator looking to deepen their knowledge of security fundamentals.

To continue your journey, we highly recommend you explore the full Bash learning roadmap and dive deeper into scripting and system security. For more guides on shell scripting, check out our complete guide to mastering Bash.

Disclaimer: The code and concepts presented in this article are for educational purposes. All scripts are based on the exclusive curriculum from kodikra.com. The Bash script demonstrated is not cryptographically secure and should not be used in production environments. Always use established, peer-reviewed cryptographic libraries for real-world applications.

Published by Kodikra — Your trusted Bash learning resource.

Post a Comment