Public Key Crypto: The Secret GCHQ Origin

Public-key cryptography, the bedrock of secure online communication, wasn’t born from a single eureka moment but rather a slow, collaborative evolution across decades and continents.

Imagine Alice wants to send a secret message to Bob. In the old days, they’d need a shared secret key, a physical object they’d both possess. This key would be used to scramble (encrypt) the message, and only Bob, with his matching key, could unscramble (decrypt) it. The problem? How do they securely get that key to Bob in the first place? If an eavesdropper intercepts it, they can read all future messages.

This is where public-key cryptography (PKC) changes the game. Instead of one shared secret, each person has two keys: a public key and a private key. The public key can be freely distributed to anyone. It’s used to encrypt messages. The private key, however, must be kept absolutely secret. It’s the only key that can decrypt messages encrypted with the corresponding public key.

So, Alice wants to send a secret message to Bob. She gets Bob’s public key (which he’s freely shared everywhere). She uses Bob’s public key to encrypt her message. Now, only Bob, with his private key, can decrypt and read it. Even if someone intercepts the encrypted message and Bob’s public key, they can’t decrypt it without Bob’s private key.

This system, often called asymmetric cryptography, is what powers secure websites (HTTPS), encrypted email, and digital signatures.

The concept of "public-key cryptography" as we know it today is largely credited to Whitfield Diffie and Martin Hellman for their groundbreaking 1976 paper, "New Directions in Cryptography." They laid out the theoretical framework for key exchange and digital signatures using asymmetric principles.

Here’s a simplified look at how a Diffie-Hellman key exchange works (this is the exchange part, not the encryption itself):

1. Public Parameters: Alice and Bob agree on two public numbers: a prime number p and a generator g. These are like the shared secret for the exchange process.
2. Private Secrets: Alice chooses a secret number a, and Bob chooses a secret number b. These are their private keys.
3. Public Keys:
   • Alice computes A = g^a mod p and sends A to Bob.
   • Bob computes B = g^b mod p and sends B to Alice.
4. Shared Secret:
   • Alice receives B and computes s = B^a mod p.
   • Bob receives A and computes s = A^b mod p.

Because (g^b mod p)^a mod p is mathematically equivalent to (g^a mod p)^b mod p, both Alice and Bob end up with the same secret number s. An eavesdropper who sees p, g, A, and B cannot easily compute s because they don’t know a or b (this is related to the difficulty of the discrete logarithm problem). This shared secret s can then be used to derive a symmetric encryption key for actual message communication.

However, the idea of secret-key cryptography where one key encrypts and another decrypts had earlier, less public roots. In 1949, Claude Shannon, the father of information theory, hinted at the concept in his seminal paper "Communication Theory of Secrecy Systems," but he didn’t fully develop it or propose a practical implementation.

The real magic of PKC was then realized by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977. They developed the RSA algorithm, named after their initials. RSA was the first practical, widely usable public-key cryptosystem that could be implemented for both encryption and digital signatures.

Here’s a highly simplified RSA encryption example:

1. Key Generation:
   • Choose two large prime numbers, p and q.
   • Calculate n = p * q. This n is part of both the public and private keys.
   • Calculate phi(n) = (p-1)(q-1).
   • Choose an integer e such that 1 < e < phi(n) and e is coprime to phi(n). This e is the public exponent.
   • Calculate d such that d * e ≡ 1 (mod phi(n)). This d is the private exponent.
   • Public Key: (n, e)
   • Private Key: (n, d)
2. Encryption: To encrypt a message M (represented as a number), Alice uses Bob’s public key (n, e):
   • C = M^e mod n
3. Decryption: Bob receives ciphertext C and uses his private key (n, d):
   • M = C^d mod n

The security of RSA relies on the computational difficulty of factoring large numbers. It’s easy to multiply two large primes (p and q) to get n, but it’s extremely hard to find p and q if you only know n.

Interestingly, the core mathematical principles behind public-key cryptography were actually discovered much earlier in secret. James H. Ellis, a cryptographer at the UK’s Government Communications Headquarters (GCHQ), conceived of the idea of "non-secret encryption" in 1969. He proposed that a sender could encrypt a message with a key that was available to everyone, and only the intended recipient could decrypt it. However, he couldn’t find a mathematical method to implement it.

Ellis’s colleague, Clifford Cocks, then devised a concrete algorithm in 1973 that was essentially the RSA algorithm, but it remained classified for decades. It wasn’t until Diffie and Hellman published their work in 1976, and Rivest, Shamir, and Adleman independently developed RSA in 1977, that public-key cryptography became a public domain concept.

The most surprising thing is that the core mathematical breakthrough for what we now call RSA was achieved and kept secret by the British government years before it was independently rediscovered and published by others. They had the solution, but the secrecy prevented it from influencing the field until much later.

The next frontier in cryptography involves exploring post-quantum algorithms that are resistant to attacks from future quantum computers.