The Key Exchange (Diffie-Hellman-Merkle Key Exchange)

Having a better understanding of modulus and the one-way function provides us the basis for our key exchange. Think of this like Alice and Bob trying to create a secret handshake without ever meeting in person, while others are watching them. Here’s how it works:

1. Alice and Bob start by agreeing on two public numbers that everyone can see:
   • A prime number [latex]p[/latex]
   • A base number [latex]g[/latex] (called a generator)
2. Then, they each choose their own secret number:
   • Alice picks number [latex]a[/latex]
   • Bob picks number [latex]b[/latex]
   • They never tell anyone these numbers!
3. They each do a calculation and share the result:
   • Alice calculates [latex]A=g^{a} \bmod p[/latex] and sends [latex]A[/latex] to Bob
   • Bob calculates [latex]B=g^{b} \bmod p[/latex] and sends [latex]B[/latex] to Alice
4. Finally, they each do one more calculation:
   • Alice takes Bob’s number and calculates [latex]B^{a} \bmod p[/latex]
   • Bob takes Alice’s number and calculates [latex]A^{b} \bmod p[/latex]

The modular exponent power rule tells us [latex]\left(g^{a} \bmod p\right)^{b} \bmod p=\left(g^{b} \bmod p\right)^{a} \bmod p[/latex]. This means they both end up with the same secret number, even though they never shared their secret numbers with each other!  

Let’s see this with real numbers.

RSA

RSA is one of the most widely used methods in modern cryptography. It uses a public-private key system where anyone can encrypt a message using your public key, but only you can decrypt it with your private key. This is similar to having a special lock where copies of the public key can be freely distributed – anyone can use it to secure a message, but only the holder of the private key can unlock and read those messages.

The security of RSA relies on a fundamental principle in mathematics: the difficulty of factoring large numbers into their prime components. For example, while it’s straightforward to multiply [latex]53[/latex] times [latex]59[/latex] to get [latex]3127[/latex], finding the original prime factors of [latex]12,317[/latex] is considerably more challenging. This difficulty increases exponentially when working with prime numbers that are hundreds of digits long, making it computationally infeasible to break the encryption.

Here’s how RSA encryption works:

1. Key Generation
   • Select two distinct prime numbers
   • Calculate their product [latex]n[/latex], which becomes part of the public key
   • Generate the encryption key [latex]e[/latex] and decryption key [latex]d[/latex]
   • Publish [latex]n[/latex] and [latex]e[/latex] as your public key, keep [latex]d[/latex] private
2. Message Encryption
   • The sender uses your public key to encrypt their message
   • Using the formula: [latex]\text{encrypted} = \text{message}^e \bmod n[/latex]
   • This creates a secure encrypted message
3. Message Decryption
   • You decrypt the message using your private key [latex]d[/latex]
   • Using the formula: [latex]\text{message} = \text{encrypted}^d \bmod n[/latex]
   • This recovers the original message

The strength of RSA lies in its mathematical foundation: even with knowledge of the encrypted message and public key, determining the original message is computationally infeasible without access to the private key. This makes RSA a cornerstone of modern secure communications.