Explain How Public-Key Encryption Works and Why It Is Secure

Explain the theory behind public-key (asymmetric) encryption. Cover what the two keys are and who holds each, which key encrypts and which decrypts when someone sends you a confidential message, and why knowing the public key does not let an attacker decrypt. The question came among rapid fundamentals questions at the start of a coding round, so aim for an answer that is correct and precise in a few minutes, with more depth ready if the interviewer probes. ```hint Two directions, one key pair The same key pair supports two different jobs: keeping a message secret and proving who produced it. Be explicit about which key is applied first in each. ``` ```hint Where the hardness lives Pick one scheme you can describe and name the computation that is easy with the private key and believed infeasible without it. ``` ### Clarifying Questions - Does the interviewer want the conceptual model only, or one concrete scheme, such as RSA, worked through? - Should digital signatures be covered alongside encryption, or only confidentiality? - Is there a system in mind, such as TLS between clients and a service, where the answer should show how the keys are used in practice? ### What a Strong Answer Covers - The key pair: what is public, what stays private, and the correct direction of encryption and decryption for confidentiality - The security argument: a one-way function with a trapdoor, illustrated with one concrete scheme, and why the private key cannot be derived from the public key - Signatures as the reverse use of the pair, and the difference between confidentiality, integrity and authenticity - Why real systems combine asymmetric and symmetric cryptography instead of encrypting bulk data with the public key - How a public key comes to be trusted, and what goes wrong without that trust ### Follow-up Questions - Work RSA through on small numbers: choose two primes, derive both keys, then encrypt and decrypt one message. - In a TLS handshake, where is public-key cryptography used, and what does using ephemeral keys add? - Why is encrypting directly with textbook RSA unsafe, and what does padding fix? - A server's private key has leaked. What can an attacker do with it, and what must happen next?