Public-key cryptography

• 1. Introduction

  ›

  Public-key cryptography solves a problem that stumped every spy, diplomat, and merchant for thousands of years: how do you share a secret with someone you have never met, over a channel your enemy is watching? Before the mid-1970s, every cryptographic system on earth depended on both parties already sharing a key. Getting that key from one person to another without interception was a puzzle with no clean answer. The more people involved, the worse it got. If messages had to be secure from every other user in a network, a completely separate key was needed for every possible pair of participants. The logistics alone could strangle a communications system. Then, within a few years in the 1970s, a series of breakthroughs changed everything. Mathematicians on both sides of the Atlantic, some working in total secrecy, others publishing openly in academic journals, found a way to let two strangers agree on a shared secret in full view of an eavesdropper. The trick rested on a class of mathematical problems called one-way functions: operations that are easy to perform in one direction and nearly impossible to reverse. The story of how that idea emerged, who got credit, and how it now underpins nearly every secure connection on the internet is stranger than most people realize.

• 2. The Key Exchange Problem

  ›

  A face-to-face meeting, a trusted courier, a printed codebook handed over in secret: these were the tools of secure communication for most of human history. Every cipher system before the mid-1970s used what is now called symmetric key cryptography, where the same key both locks and unlocks a message. Both the sender and the receiver had to hold copies of that identical key, which meant the key itself had to travel somehow. The requirement was never trivial. Across a large network, the burden grew exponentially: a separate key for every pair of participants, each one requiring its own secure handoff. When those channels were not available, when keys needed to change frequently as good cryptographic practice demands, the system strained under its own weight. Public-key cryptography cuts through that tangle by splitting the key in two. One half, the public key, can travel freely and be shared with anyone. The other half, the private key, never moves. A message locked with the public key can only be opened by the matching private key, which only the intended recipient holds. The sender and recipient need never have exchanged anything secret beforehand.

• 3. The Classified Discovery

  ›

  In 1970, James H. Ellis, a British cryptographer at the UK Government Communications Headquarters, known as GCHQ, conceived of what he called "non-secret encryption." He could see that such a thing ought to be possible. He could not see how to build it. Three years later, his colleague Clifford Cocks found the implementation. Cocks devised what would eventually be recognized as the RSA encryption algorithm, giving the concept its first practical form. Then in 1974, another GCHQ mathematician named Malcolm J. Williamson independently developed the method now known as Diffie-Hellman key exchange. The scheme was passed to the United States National Security Agency as well. Both organizations had a military focus, and computing power was limited. The potential of these discoveries went largely unrealized inside the classified world. None of it became public knowledge until the British government declassified the research in 1997. By that point, the outside world had already reinvented the same ideas and built an entire industry on top of them.

• 4. Going Public

  ›

  In 1876, in his book The Principles of Science, the mathematician William Stanley Jevons posed a question to his readers: could they identify two numbers that, multiplied together, produce 8,616,460,799? He was confident they could not. Jevons was describing, without naming it, the factorization problem that would later become load-bearing in public-key cryptography. In July 1996, mathematician Solomon W. Golomb observed that Jevons had anticipated a key feature of the RSA algorithm, though he had not invented public-key cryptography itself. The formal public discovery came in 1976, when Whitfield Diffie and Martin Hellman, influenced by Ralph Merkle's earlier work on key distribution, published a method of public key agreement. Their approach used exponentiation in a finite field and became known as Diffie-Hellman key exchange. It was the first published practical method for establishing a shared secret over an authenticated channel without any prior shared secret. Merkle's own technique, later called Merkle's Puzzles, had actually been invented in 1974 but was not published until 1978. Then in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman, all then at MIT, independently generalized Cocks's earlier classified work. They published their algorithm in Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American. The algorithm took its name from their initials: RSA.

• 5. How It Actually Works

  ›

  RSA's security rests on the extreme difficulty of factoring the product of two very large prime numbers. Multiplying those primes together is fast. Running the calculation in reverse, starting from the large product and recovering the original primes, is a problem for which no known efficient general technique exists. That asymmetry, easy in one direction and hard in the other, is what makes the whole system viable. Digital signatures use a related mechanism. A sender applies a private key to a message to produce a signature. Anyone holding the matching public key can verify that the signature is genuine, but a forger who lacks the private key cannot produce any message-and-signature pair that will pass the check. The practical example the source offers involves a software publisher: install the public key on users' computers, then distribute updates signed with the private key. Any computer receiving an update can confirm it is genuine by checking the signature, as long as the private key has not been exposed. Public-key encryption works in the other direction. A journalist might publish a public key so that sources can send encrypted messages. The journalist is the only person who can decrypt them, because only the journalist holds the private key. Crucially, public-key encryption does not conceal metadata: who sent a message, when, or how long it is can all remain visible even when the content is hidden.

• 6. Hybrid Systems and Real-World Use

  ›

  Asymmetric key algorithms carry a practical cost: they are nearly always far more computationally intensive than their symmetric counterparts. Running an entire encrypted connection through RSA or a similar system would be slow. The solution used in practice is the hybrid cryptosystem. A public-key algorithm handles the initial handshake, encrypting and exchanging a symmetric key. Once both parties hold that shared symmetric key, they switch to the faster symmetric method for the remainder of the session. PGP, SSH, and the entire SSL/TLS family of protocols all work this way. TLS, which secures most web browser connections today, underpins HTTPS across the internet. S/MIME and OpenPGP secure email. SSH secures remote server access. Bitcoin relies on asymmetric key techniques for signing transactions. The list of protocols using asymmetric keys includes IPsec, ZRTP for secure voice calls, and Off-the-Record Messaging. National cryptography standards have also emerged in this space: China developed SM2 and SM9, Russia adopted GOST R 34.10-2012, South Korea uses EC-KCDSA, and Ukraine maintains DSTU 4145.

• 7. Threats and Weak Points

  ›

  The most direct threat to any public-key system is exposure of the private key. Once an attacker holds it, all past and future communications protected by that key are compromised. Recent TLS schemes address this through forward secrecy, which generates a fresh ephemeral set of keys for each session so that capturing one key does not unlock earlier conversations. A subtler threat is the man-in-the-middle attack. If an attacker can intercept the exchange of public keys and substitute their own, they can sit silently between two parties, decrypting traffic from one side and re-encrypting it for the other. Neither party suspects anything is wrong, which can produce the maddening situation where both users blame each other. Man-in-the-middle attacks become straightforward when the attacker controls the communications infrastructure, such as in the case of a hypothetical malicious employee at an internet service provider. The solution most widely adopted is the Public Key Infrastructure, or PKI: a hierarchy of certificate authorities that vouch for the legitimacy of public keys by issuing digital certificates. Web browsers carry a built-in list of trusted certificate authorities for exactly this purpose. The weakness is that the entire system rests on trusting those authorities. An attacker who compromised a certificate authority's servers and obtained its store of keys could spoof, forge, and decrypt transactions without limit. Research on Uruguay's implementation of PKI under Law 18.600 found that when private key custody is delegated to third-party Trust Service Providers, the core principle of private-key secrecy is weakened and exposure to man-in-the-middle attacks increases.

• 8. Quantum Computing and What Comes Next

  ›

  Most public-key systems in use today are vulnerable, in theory, to quantum computing. The mathematical problems that make RSA and related algorithms hard to crack, large-number factorization in particular, yield to quantum algorithms far more readily than to classical ones. This vulnerability is not yet practical: sufficiently powerful quantum computers do not yet exist. But the research community is treating the threat as a planning horizon, and new quantum-resistant schemes are actively being developed. The "knapsack packing" algorithm, once considered promising, illustrates how quickly the field can shift: a new attack rendered it insecure, and it is now listed among notable but broken asymmetric key algorithms. Claude Shannon, who coined the term "work factor" to describe the computation required to crack a cipher by brute force, established the conceptual framework for evaluating these risks. Longer keys raise the work factor and push brute-force attacks further out of reach, but some algorithms have inherently low work factors that longer keys cannot fix. Metadata remains a parallel vulnerability that no purely cryptographic fix resolves. An experimental messaging system that encrypts headers as well as message bodies has been demonstrated, reducing the information available to a third party to little more than the inbox server and the timestamp. Scaling that approach would make social network modelling from intercepted traffic far more challenging, but the technology remains in an experimental phase.