up:: Foundations MOC
Key Pair
A key pair is the matched set of two keys, one public and one private, that a public-key (asymmetric) cryptographic algorithm uses, where the two keys are generated together and mathematically linked so that whatever one key does the other one reverses, yet the private key can’t be worked out from the public one by any efficient classical method. The private key stays secret with one owner, the public key is published for anyone to use, and that asymmetry is what lets strangers who share no prior secret still agree on encryption keys and prove each other’s identity. Every classical key pair in wide use today, RSA and the elliptic-curve pairs behind ECDH and ECDSA, rests on math that a quantum computer running Shor’s algorithm solves efficiently, so the machine can recover the private key from the public one and collapse the scheme.
The short version:
- A key pair is two mathematically linked keys, a public one shared openly and a private one kept secret, used by public-key cryptography.
- The keys are inverses of each other. What one does, the other undoes, so a message locked with the public key opens only with the private key, and a value stamped with the private key checks against the public key.
- The private key can’t be derived from the public key by any efficient classical method. That gap is the entire security of the system.
- Key pairs do two jobs: key establishment (KEMs and ECDH) and digital signatures.
- The quantum problem is the whole ballgame. Shor’s algorithm recovers the PRIVATE key from the PUBLIC one for RSA and elliptic-curve pairs, so the one secret the system depends on stops being secret.
Picture a padlock you can copy endlessly and a single key that opens it. You hand out open copies of the padlock to everyone, and anyone can snap one shut on a box and send it to you, but only your one physical key opens those boxes. The open padlock is the public key, the key in your pocket is the private key, and the reason the scheme is safe is that nobody can file a working key just from studying the padlock. A digital key pair is the mathematical version of that. The quantum problem is that Shor’s algorithm studies the padlock and cuts a perfect key from it.
What is a key pair?
A key pair is the two-key unit that public-key cryptography runs on: a private key and its matching public key, generated together as one linked pair. It belongs to asymmetric cryptography, the family named for using two different keys, and it stands in contrast to symmetric cryptography, where both sides share one identical secret key. The idea of splitting the key into a public half and a private half was introduced by Whitfield Diffie and Martin Hellman in 1976 and is what made secure communication between strangers possible in the first place.
The two keys have fixed, opposite roles:
- The private key is generated first and held by exactly one owner. It’s never shared, never published, and never transmitted. It’s the key that signs and the key that decrypts.
- The public key is derived from the private key and published as widely as you like, often bundled inside a certificate that ties it to an identity. It’s the key that verifies signatures and the key others encrypt to.
The link between them is deliberately one-directional. Computing the public key from the private key is easy, and computing the private key from the public key is meant to be so expensive that no attacker can afford it within the lifetime of the data. That one-way relationship is the source of all the security, and it’s exactly the relationship a quantum computer breaks.
Source: W. Diffie and M. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, 1976, IEEE 1055638.
NIST, “Recommendation for Key Management, Part 1 - General,” SP 800-57 Part 1 Rev. 5, May 2020, SP 800-57 Part 1.
How does a key pair actually work?
A key pair works because the two keys are inverse operations built on a hard math problem, so one key undoes the other while neither can be forged from what’s public. The pair gets created once, in a single step, and then the two keys go their separate ways:
- Generation. A key-generation algorithm produces the pair together from a hard problem. For RSA that problem is integer factorization, the difficulty of splitting a large number back into its two prime factors. For elliptic-curve pairs it’s the elliptic-curve discrete logarithm problem. The private key is the secret ingredient, and the public key is what you can safely publish about it.
- The public direction. Anyone can run the public key forward: encrypt a message so only the private-key holder can read it, or check a signature the private-key holder produced.
- The private direction. Only the owner can run the private key: decrypt what was sent to them, or sign something so the whole world can verify it came from them.
The keys are used in opposite directions for the two jobs, and mixing the directions up is a classic source of bugs:
- For confidentiality, a sender encrypts with the recipient’s public key, and only the recipient’s private key decrypts. The public key locks, the private key unlocks.
- For authenticity, a signer signs with their own private key, and anyone verifies with the signer’s public key. The private key stamps, the public key checks the stamp.
Everything holds together on one condition: the private key stays secret and the underlying hard problem stays hard. Break either and the pair is worthless, which is why quantum matters so much, because it breaks the second one for every classical key pair at once.
Source: NIST, “Recommendation for Key Management, Part 1 - General,” SP 800-57 Part 1 Rev. 5, May 2020, SP 800-57 Part 1.
What’s the difference between the public and private key?
The public key and the private key are two halves of the same pair with opposite handling and opposite jobs: the public key is shared with everyone and does the checking and locking, while the private key is guarded by one owner and does the signing and unlocking. The private key is the crown jewel, and the entire security model reduces to keeping it secret. NIST describes the public key as a key that “may be made public” and the private key as one that “shall be kept secret.”
| Public key | Private key | |
|---|---|---|
| Who holds it | Everyone, published openly (often inside a certificate) | Exactly one owner, never shared |
| What it does | Encrypts to the owner; verifies the owner’s signatures | Decrypts what’s sent to the owner; creates signatures |
| Direction | Locks (encrypt) and checks (verify) | Unlocks (decrypt) and stamps (sign) |
| What must stay secret | Nothing, it’s meant to be public | Everything, its secrecy is the whole security |
| If it’s exposed | No harm, that’s the design | Total compromise, the attacker becomes the owner |
| Quantum status | Already public, and that’s what Shor’s attacks | Recovered from the public key by Shor’s algorithm |
The asymmetry in that table is the point of the whole invention. Because the public key can be handed to anyone with no loss of security, two parties who have never met and share no secret can still set up an encrypted channel or verify each other, which is something symmetric cryptography can’t do on its own. The catch is that a quantum computer attacks the one thing the design deliberately leaves in the open.
Source: NIST, “Recommendation for Key Management, Part 1 - General,” SP 800-57 Part 1 Rev. 5, May 2020, SP 800-57 Part 1.
Where are key pairs used?
Key pairs are used for the two foundational jobs that symmetric cryptography can’t do by itself, agreeing on a secret with a stranger and proving identity to a stranger, which together underpin nearly every secure connection on the internet. Concretely, they carry two workloads:
- Key establishment. Two parties use a key pair to agree on a fresh shared secret over a channel anyone can watch, without ever sending the secret across it. The classical workhorse is ECDH, and the cleaner post-quantum interface is a key-encapsulation mechanism. That shared secret then keys fast symmetric encryption for the actual data, which is how a TLS session protects a web page.
- Digital signatures. A key pair proves who produced something and that it wasn’t altered. The signer signs with the private key and anyone verifies with the public key, which is what authenticates TLS certificates, code and firmware, and login tokens. The whole public-key infrastructure is a tree of key pairs, each Certificate Authority using its private key to vouch for the public keys beneath it.
Because a key pair sits at both the secrecy layer and the trust layer, it’s the single most load-bearing structure in classical cryptography, and it’s the exact structure the post-quantum transition has to rebuild.
How does the quantum threat attack a key pair?
A quantum computer attacks a key pair by recovering the private key directly from the public key, which is the one move the entire design assumes is impossible. A cryptographically relevant quantum computer running Shor’s algorithm efficiently solves both integer factorization and the discrete logarithm problem, and those are precisely the hard problems that link the private key to the public key in RSA and elliptic-curve pairs. Take the public key, which is already published, run Shor’s algorithm, and out comes the matching private key.
Three things make this severe:
- It targets the half that’s already public. An attacker doesn’t need to steal anything or break in. The public key is handed out by design, so the raw material for the attack is sitting in the open, waiting only on the machine.
- Bigger keys don’t save it. Enlarging an RSA or elliptic-curve key buys almost nothing against Shor’s algorithm, because its cost grows only slowly with key length. The fix is a different kind of key pair built on a different hard problem, not a longer version of the same one.
- The confidentiality damage can be retroactive. Traffic protected by a classical key exchange today can be recorded now and decrypted later once the machine exists, the harvest-now-decrypt-later problem, so the clock on some key pairs is already running.
This is why the post-quantum transition is fundamentally a key-pair replacement job. The symmetric keys and hashes carry forward with larger sizes, but every classical public/private pair has to be swapped for a post-quantum one, and because rebuilding PKI and trust stores takes years, Mosca’s theorem says that work has to start well before the machine arrives.
Source: P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Computing, 1997, quant-ph/9508027.
NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, NISTIR 8105.
Common misconceptions
- “The public and private key are interchangeable.” They have fixed, opposite roles. The private key signs and decrypts, the public key verifies and encrypts, and you can’t swap which one you guard. Only the private key is secret.
- “You can figure out the private key from the public key if you try hard enough.” Classically, no. The pair is built so that recovering the private key from the public key is infeasible. A quantum computer running Shor’s algorithm is exactly what changes that, and it’s the reason for the whole transition.
- “A key pair is just a longer password.” A password is one shared secret. A key pair is two mathematically linked keys with opposite jobs, and that split is what lets strangers who share nothing set up security between them.
- “Making the public key public is a risk.” Publishing the public key is the design, not a leak. It carries no secret, and handing it to the world is what makes public-key cryptography work.
- “A bigger key pair will survive quantum.” For RSA and elliptic-curve pairs, size buys almost nothing against Shor’s algorithm. Surviving quantum means moving to a post-quantum key pair built on a different hard problem.
- “Key pairs are only for encryption.” They do two separate jobs, key establishment and signatures, and in the post-quantum world those split into different standards, one for key exchange and one for signing.
Questions people ask
What’s the difference between a key pair and a shared key? A shared (symmetric) key is one identical secret both parties hold, used for fast bulk encryption. A key pair is two linked keys with opposite roles, a public one and a private one, used to set up trust and agree on a shared key in the first place. Real systems use a key pair to bootstrap, then hand off to a shared key for speed.
Which key do I keep secret, the public or the private one? The private key, always, and only the private key. The public key is meant to be published; its whole purpose is to be handed out. If your private key is exposed, an attacker can impersonate you and decrypt what was sent to you, so protecting it is the entire security of the pair.
Can the private key be recovered from the public key? Not by any efficient classical method, which is the assumption every classical key pair depends on. A quantum computer running Shor’s algorithm can recover it for RSA and elliptic-curve pairs, which is precisely why those algorithms have to be replaced.
Is a key pair the same thing as public-key cryptography? The key pair is the core structure, and public-key cryptography is the whole family of algorithms and protocols built on it. Every public-key operation, encrypting to someone, verifying a signature, agreeing a session key, uses a key pair underneath.
Do post-quantum algorithms still use key pairs? Yes. The post-quantum standards keep the public/private pair structure exactly, they just build the pair on a different hard problem that a quantum computer can’t solve, such as lattice math. The concept survives, the underlying math changes, and the new keys tend to be larger.
Why does a key pair have two keys instead of one? Because two linked keys solve a problem one key can’t: letting parties who share no prior secret still communicate securely. The public half can be handed to anyone with no loss of security, so a stranger can encrypt to you or verify you without ever needing your secret.
If a quantum computer breaks my key pair, is my old data exposed? For confidentiality it can be, if the traffic was recorded. Data protected by a classical key exchange today can be stored now and decrypted later once the machine exists, the harvest-now-decrypt-later problem. Signatures are a different, real-time forgery risk rather than a retroactive one.
Everything here is the map, given freely. When your team needs its own key pairs found, inventoried, and sequenced onto a post-quantum path, that’s the work I do. Request an alignment briefing.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.