I had just finished reading this interesting article, “The Original OTP: Inside the Only Encryption Proven to Be Unbreakable” by Israel Ulelu, and one of the challenges he mentioned at the end of the article begs the question, “How do you securely transmit a secret over a channel?”, knowing well this channel could be public. The Original OTP: Inside the Only Encryption Proven to Be Unbreakable Israel Ulelu In today’s age, and the rapid evolution of technology with multiple abstraction layers, it is not surprising that a lot of practices and concepts are being forgotten or ignored in order to complement the newer technologies. The forgotten arts of technology, as I call them, comprise a host of primitive approaches, technologies, concepts, and even tools that have been put aside to favour some other. The Diffie-Hellman Key Exchange, an almost forgotten art, is a method for two parties to securely establish a shared secret key over a public channel without having to meet or exchange the key directly. Diffie-Hellman Key Exchange A common analogy is, “imagine trying to whisper a secret in a crowded room where everybody can hear you. It would be impossible to agree on a secret that only the two of you know”. That’s what Diffie-Hellman solves. This is an algorithm about establishing a shared secret between two parties while communicating over an insecure channel. This revolutionary algorithm was proposed by Whitfield Diffie and Martin Hellman in 1976, enabling two entities to agree upon a secret key without prior arrangements, even in the presence of potential eavesdroppers. Diffie-Hellman offers a powerful solution to secure key exchange, which has always been challenging and prone to alteration, thus ensuring confidentiality and integrity in information. How does Diffie-Hellman Key Exchange work? The Diffie-Hellman Algorithm is primarily based on two mathematical principles, modular exponentiation and discrete logarithm. Two parties agree on two positive numbers p and g, such that p is a prime number and g is a generator of p, and then private and public keys, and secrets are generated and computed off these. p g p g p On an operational level Setting up Parameters: Setting up Parameters: Alice and Bob must agree upon two numbers; A large prime number p and a generator g of p, which is a primitive root of p, can be publicly shared/exchanged. p p generator g g p p p p Generating Private Keys: Generating Private Keys: Alice and Bob then proceed to generate private/personal keys, say PrivK_A and PrivK_B, which are usually positive whole numbers, smaller than the prime number p. Neither party divulges their private keys to anyone, and they are kept as secrets. PrivK_A PrivK_B PrivK_B p p Computing Public Keys: Computing Public Keys: Next, Alice and Bob compute public keys PubK_A and PubK_B based on their private keys according to the following formulas: PubK_A PubK_A PubK_B PubK_B Alice’s public key => PubK_A = (g ^ PrivK_A) mod p PubK_A PubK_A = (g ^ PrivK_A PrivK_A ) mod p Bob’s public key => PubK_B = (g ^ PrivK_B) mod p PubK_B PubK_B = (g ^ PrivK_B PrivK_B ) mod p The two parties then exchange their public keys, in, of course, a channel that might contain hackers and eavesdroppers. Generating the Shared Secret Key: Generating the Shared Secret Key: Both Alice and Bob then proceed to generate a secret s with the formulae: s Secret s = (PubK_B ^ PrivK_A) mod p. Alice uses Bob's public key. “ Secret s = (PubK_B ^ PrivK_A) mod p Secret s = (PubK_A ^ PrivK_B) mod p. Bob uses Alice’s public key. “ Secret s = (PubK_A ^ PrivK_B) mod p The value of Secret s turns out to be the same according to either of the above two formulas. However, the private/personal keys PrivK_A and PrivK_B, which are critical in the calculation of s, haven't been transmitted over a public medium. s s PrivK_A PrivK_B s Alice and Bob will end up with the same secret s, which can then be used for encryption and decryption using any symmetric-key encryption algorithm. s Numerical representation of the Diffie-Hellman key exchange: For the sake of this article, we will use small numbers (real implementations use massive primes) Public parameters setup: Prime p = 23, Generator g = 5 Public parameters setup: • Alice’s private key: PrivK_A = 6 PrivK_A • Bob’s private key: PrivK_B = 15 PrivK_B Public Keys generation: Public Keys generation: • Alice’s public key: PubK_A = (g ^ PrivK_A) mod p = 5^6 mod 23 = 15625 mod 23 = 8 PubK_A PubK_A = (g ^ PrivK_A PrivK_A ) mod p 5^6 mod 23 15625 mod 23 = 8 • Bob’s public key: PubK_B = (g ^ PrivK_B) mod p = 5^15 mod 23 = 19 PubK_B PubK_B = (g ^ PrivK_B PrivK_B ) mod p 5^15 mod 23 = 19 Shared secret generation: Shared secret generation: The public keys are then exchanged, Alice gets Bob’s public key ( 19 ), while Bob receives Alice’s public key ( 8 ) They both generate the secret: Alice’s attempt: Bob’s public key to the power of Alice’s private key modulo p. p 19^6 mod 23 = 2 19^6 mod 23 = 2 Bob’s attempt: Alice’s public key to the power of Bob’s private key modulo p. p 8^15 mod 23 = 2 8^15 mod 23 = 2 Go Code Implementation package main import ( "crypto/rand" "fmt" "math/big" ) func generatePrime() *big.Int { prime, _ := rand.Prime(rand.Reader, 256) // Generating a 256-bit prime number return prime } func generatePrivateKey(prime *big.Int) *big.Int { privateKey, _ := rand.Int(rand.Reader, prime) return privateKey } func calculatePublicKey(prime, privateKey, base *big.Int) *big.Int { publicKey := new(big.Int).Exp(base, privateKey, prime) return publicKey } func calculateSharedSecret(prime, privateKey, publicKey *big.Int) *big.Int { sharedSecret := new(big.Int).Exp(publicKey, privateKey, prime) return sharedSecret } func main() { // Alice and Bob agree on a natural number p a generating element g // Which is known to everyone p := generatePrime() g := big.NewInt(2) // g is a primitive root modulo p (generator) // Alice and Bob generate their private keys // PrivK = random number between 1 and p-1 PrivK_A := generatePrivateKey(p) PrivK_B := generatePrivateKey(p) // Alice and Bob calculate their public keys // PubK = g^PrivK mod p PubK_A := calculatePublicKey(p, PrivK_A, g) PubK_B := calculatePublicKey(p, PrivK_B, g) // Now Alice and Bob exchange their public keys // and calculate the shared secret // shared_secret = PrivK^PubK mod p secret_A := calculateSharedSecret(p, PrivK_A, PubK_B) secret_B := calculateSharedSecret(p, PrivK_B, PubK_A) // If the shared secrets match, then Alice and Bob have // successfully established a shared secret if secret_A.Cmp(secret_B) == 0 { fmt.Printf("Shared secret: %s\n", secret_A.Text(16)) } else { fmt.Println("Shared secret mismatch") } } package main import ( "crypto/rand" "fmt" "math/big" ) func generatePrime() *big.Int { prime, _ := rand.Prime(rand.Reader, 256) // Generating a 256-bit prime number return prime } func generatePrivateKey(prime *big.Int) *big.Int { privateKey, _ := rand.Int(rand.Reader, prime) return privateKey } func calculatePublicKey(prime, privateKey, base *big.Int) *big.Int { publicKey := new(big.Int).Exp(base, privateKey, prime) return publicKey } func calculateSharedSecret(prime, privateKey, publicKey *big.Int) *big.Int { sharedSecret := new(big.Int).Exp(publicKey, privateKey, prime) return sharedSecret } func main() { // Alice and Bob agree on a natural number p a generating element g // Which is known to everyone p := generatePrime() g := big.NewInt(2) // g is a primitive root modulo p (generator) // Alice and Bob generate their private keys // PrivK = random number between 1 and p-1 PrivK_A := generatePrivateKey(p) PrivK_B := generatePrivateKey(p) // Alice and Bob calculate their public keys // PubK = g^PrivK mod p PubK_A := calculatePublicKey(p, PrivK_A, g) PubK_B := calculatePublicKey(p, PrivK_B, g) // Now Alice and Bob exchange their public keys // and calculate the shared secret // shared_secret = PrivK^PubK mod p secret_A := calculateSharedSecret(p, PrivK_A, PubK_B) secret_B := calculateSharedSecret(p, PrivK_B, PubK_A) // If the shared secrets match, then Alice and Bob have // successfully established a shared secret if secret_A.Cmp(secret_B) == 0 { fmt.Printf("Shared secret: %s\n", secret_A.Text(16)) } else { fmt.Println("Shared secret mismatch") } } Why It’s Secure An eavesdropper knows p, g, PubK_A, and PubK_B, but computing the shared secret requires knowing either PrivK_A or PrivK_B. The difficulty of deriving PrivK_A from (g ^ PrivK_A) mod p is called the discrete logarithm problem, which is computationally infeasible for large numbers. p g PubK_A PubK_B PrivK_A PrivK_B PrivK_A (g ^ PrivK_A PrivK_A ) mod p Over the years, researchers have identified potential vulnerabilities in Diffie–Hellman, particularly concerning the size of the prime modulus and the risk of precomputation attacks. Mitigating these challenges often involves using larger prime moduli or transitioning to elliptic curve cryptography. Real-World Usage In practice, Diffie-Hellman uses: • Prime numbers that are 2048-4096 bits long 2048-4096 • Variants like Elliptic Curve Diffie-Hellman (ECDH) for better efficiency • Additional authentication mechanisms to prevent man-in-the-middle attacks Diffie-Hellman Key Exchange forms the basis for establishing forward secrecy in common protocols like HTTPs Transport Layer Security (TLS) and is used in public key encryption schemes, password-authenticated key agreement, and more.
