The Locks Of The Internet: What Public-Key Cryptography Does

Every time you open a banking app, connect to a work VPN or install a software update, your device runs a quick conversation with a computer it has never met. Within a fraction of a second the two sides agree on a secret key, and your device checks that the other side really is who it claims to be. Public-key cryptography is the tool that makes that possible.

This article explains what public-key cryptography does, the two mathematical problems it rests on, and where it sits inside everyday systems. That background matters because these are exactly the parts of today’s security that a large quantum computer would break, while other parts would survive.

Two Problems Public-Key Cryptography Solves

Ordinary encryption uses one shared secret key to encrypt and decrypt data. It is fast and strong, but it has an obvious gap: two parties who have never met need some safe way to agree on that key first. Public-key cryptography fills the gap by giving each party a pair of keys. One is public and can be shared with anyone. The other is private and never leaves its owner.

A helpful picture is a padlock. You can hand out open padlocks to the whole world, and anyone can snap one shut on a box addressed to you, but only you hold the key that opens it. That covers the first job, key establishment: agreeing on a fresh secret over an open network.

The second job is the digital signature. Think of a wax seal that only you can press but that anyone can inspect. A signature made with a private key can be checked by anyone who holds the matching public key, which proves who produced a message or a file and that nobody changed it afterwards. Linking a public key to a real organisation in the first place depends on a certificate from an authority your device already trusts.

The Maths Underneath

Public-key schemes depend on calculations that are easy to perform in one direction and extremely hard to reverse. Two families of problems carry almost all of today’s traffic.

• Factoring. Multiplying two large prime numbers takes a computer no time at all. Recovering those primes from the product is believed to be infeasible for numbers of the size used in practice. RSA is built on this.
• Discrete logarithms. Repeatedly combining a number with itself in a special mathematical group is easy, but working out how many times it was combined is hard. Diffie-Hellman key exchange relies on this, and so do the elliptic curve versions: elliptic curve Diffie-Hellman (ECDH) for key agreement and ECDSA and EdDSA for signatures.

In the mid-1990s the mathematician Peter Shor showed that a quantum computer could solve both problems efficiently, in what computer scientists call polynomial time.¹ The next article explains what that means in practice.

Where You Rely On It

NIST, the US standards body, lists the public-key algorithms it plans to retire because of this threat. For signatures they are RSA, ECDSA and EdDSA. For key establishment they are finite field Diffie-Hellman, ECDH and RSA key transport.² Those names turn up in almost every secure system.

NIST’s draft transition guidance walks through the places they appear: network protocols such as TLS (the padlock in your browser), Secure Shell (SSH) and IPsec virtual private networks, email signing and encryption with S/MIME, code and firmware signing, user and machine authentication, and the public key infrastructure (PKI) that issues and checks digital certificates.² In a typical connection using TLS 1.3, the current version of the web’s main security protocol, the two sides agree keys with Diffie-Hellman over finite fields or elliptic curves, and the server proves its identity with an RSA, ECDSA or EdDSA signature backed by its certificate. TLS 1.3 then protects each message with an authenticated cipher such as AES-GCM, which both hides the data and detects tampering.³

The pattern in the table is the key idea of this whole topic group. Public-key cryptography does the introductions and the identity checks. Symmetric cryptography, such as AES, does the bulk work of keeping data secret once the introductions are done. NIST states that its symmetric standards are far less exposed to known quantum attacks and that it does not expect to move away from them as part of this transition.²

How The Pieces Stack Up

It helps to see public-key cryptography as one layer in a stack. An application rarely calls RSA directly. It uses a protocol such as TLS, which uses a cryptographic library, which may in turn use a hardware security module to hold private keys. Certificates issued by a PKI tie it all to real identities.

NIST points out that every one of those layers needs work for the transition: protocols must support new algorithms, libraries and hardware modules must implement them, and PKI must be able to issue and sign certificates with them.² That is why replacing a few algorithms turns into a multi-year programme, a theme the Preparing For Migration group covers in depth.

Why This Matters For The Rest Of The Series

Once you know which job each algorithm does, the quantum threat becomes easier to reason about. Key establishment protects secrecy, so it is exposed to attackers who record traffic today and break it later. Signatures protect identity and integrity, so the danger there is forgery once a capable quantum computer actually runs. The two risks have different timelines, and the harvest now, decrypt later article looks at the first in detail.