Quiz Entry - updated: 2026.10.26
What exactly are the public and private keys in RSA, and what should happen to $p$ and $q$ after key generation?
Public key = $(N, e)$. Private key = $d$. The primes $p$ and $q$ are the trapdoor — some recommend destroying them after computing $d$, but keeping them is often preferred.
Public Key: $(N, e)$
- Published in a directory or certificate
- Anyone can use $(N, e)$ to encrypt a message for the key owner
- Anyone can use $(N, e)$ to verify a signature from the key owner
Private Key: $d$ (the secret exponent)
- Must be protected — stored in a tamper-proof smart card, encrypted with a symmetric key, etc.
- Used to decrypt messages
- Used to sign messages
- Important: For signing and encrypting, use two different key pairs!
What about $p$ and $q$?
- Some recommend destroying $p$ and $q$ after computing $d$, since they're no longer needed
- However, keeping $p, q$ allows for CRT optimization (Chinese Remainder Theorem) which makes decryption ~4x faster
- Keeping them is often preferred for exactly that reason; they're protected the same way $d$ is, so destroying them buys little
Go deeper:
RSA cryptosystem — keys (Wikipedia) — exactly what is public, what is secret, and why.
Chinese remainder theorem (Wikipedia) — the CRT trick that makes keeping $p, q$ worthwhile.