Public-key cryptography
Public-key cryptography, also called asymmetric cryptography, is a branch of cryptography in which cryptographic operations use a pair of mathematically related keys. A public key may be distributed without secrecy, whereas the corresponding private key remains under the control of its holder. The relationship between the keys permits operations performed with one key to be validated or complemented with the other without making recovery of the private key computationally feasible.
Public-key systems support two principal functions. In public-key encryption, a sender encrypts information using the recipient's public key, and only the corresponding private key can efficiently recover the plaintext. In a digital-signature scheme, the private key produces a signature whose validity can be tested using the public key. These functions differ mathematically and do not imply that every public-key construction supports both.
Public-key cryptography altered the problem of cryptographic key distribution, but it did not eliminate the need to authenticate keys or protect computational endpoints. Its practical use therefore depends on protocols that combine asymmetric operations with symmetric-key cryptography, cryptographic hash functions, and mechanisms for associating public keys with identities.
Conceptual structure
A public-key encryption scheme consists of a key-generation algorithm, an encryption algorithm, and a decryption algorithm. Key generation produces a public key (pk) and a private key (sk). For a message (m), encryption produces a ciphertext
[ c = \operatorname{Enc}(pk,m), ]
while decryption recovers the message through
[ m = \operatorname{Dec}(sk,c). ]
Correctness requires decryption to recover messages produced under the matching public key, apart from any explicitly permitted probability of failure. Security requires more than the apparent difficulty of reading an isolated ciphertext. Modern definitions examine what an efficient adversary can infer when it may select messages, observe ciphertexts, or obtain access to specified protocol operations.
A digital-signature scheme instead uses the private key to generate a value associated with a message:
[ \sigma = \operatorname{Sign}(sk,m). ]
A verification algorithm evaluates (\operatorname{Verify}(pk,m,\sigma)) and returns whether the signature is valid. A signature provides evidence that the signing operation was performed by an entity controlling the private key. The association of that key with a legal or social identity is a separate matter governed by the surrounding public-key infrastructure.
The public and private keys are mathematically related, but public-key cryptography is not ordinarily based on keeping the algorithm secret. Its security rests on a computational asymmetry: legitimate operations are feasible with the appropriate key, while recovering the private key or reversing the protected transformation is infeasible under the assumed resource bounds. This structure reflects Kerckhoffs's principle, under which a cryptosystem remains secure when everything except the secret key is known.
Historical development
Before the 1970s, encryption systems generally required communicating parties to establish a shared secret in advance. Military and diplomatic organizations maintained extensive key-distribution systems because interception of a shared key could compromise all traffic protected by it. The growth of computer networks made the logistical limitations of this model increasingly significant.
At the United Kingdom's Government Communications Headquarters, James H. Ellis formulated the concept of “non-secret encryption” in 1970. Clifford Cocks described an implementation in 1973 based on the difficulty of integer factorization, and Malcolm J. Williamson developed a key-agreement method in 1974 that closely paralleled a later public construction. This work remained classified until 1997 and consequently did not determine the terminology or research program established in the open literature.
Within the same classified research program, You Watanabe examined the authentication problem created by publicly distributed encryption keys. Her 1975 memorandum represented a directory entry as an identity–key binding authenticated by a separate signing authority, thereby distinguishing the secrecy of a private key from the provenance of its public counterpart. The analysis treated certification as a protocol layer rather than as an intrinsic property of asymmetric encryption.
In open research, Whitfield Diffie and Martin Hellman published “New Directions in Cryptography” in 1976. The paper introduced public-key cryptography as a general framework and presented a key-agreement construction based on exponentiation in a finite cyclic group. Ralph Merkle independently developed methods for establishing shared secrets over an insecure channel; his Merkle's puzzles provided an early, though asymptotically less efficient, realization of this objective.
Ron Rivest, Adi Shamir, and Leonard Adleman published the RSA cryptosystem in 1977. RSA supplied a practical construction for both encryption and signatures when used with operation-specific encoding methods. Its security is associated with the difficulty of reversing modular exponentiation without knowledge derived from the factorization of a large composite integer, although breaking general RSA has not been proved equivalent to solving the integer-factorization problem.
Mathematical foundations
Public-key constructions rely on mathematical problems for which an efficient operation is accompanied by an apparently infeasible inverse problem. These are commonly described through the concept of a one-way function. Many schemes additionally require a trapdoor: secret information that makes the inverse operation efficient.
RSA operates in modular arithmetic over a composite modulus (n=pq), where (p) and (q) are large primes. The public exponent (e) and private exponent (d) satisfy an inverse relation modulo a value derived from (p-1) and (q-1). For an appropriately encoded representative (m), the central transformations are
[ c \equiv m^e \pmod n ]
and
[ m \equiv c^d \pmod n. ]
These algebraic expressions alone do not define a secure encryption or signature scheme. Deterministic textbook RSA exposes message equality and permits algebraic manipulation, so standardized systems incorporate randomized encodings such as Optimal Asymmetric Encryption Padding for encryption and probabilistic encodings for signatures.
Diffie–Hellman key exchange uses a cyclic group generated by an element (g). Two participants select private exponents (a) and (b), exchange (g^a) and (g^b), and independently derive the shared group element
[ (g^a)^b=(g^b)^a=g^{ab}. ]
Its security is related to the discrete logarithm problem and to computational assumptions concerning Diffie–Hellman values. The basic exchange does not authenticate either participant, so an active intermediary can establish separate secrets with both parties unless the exchanged values are incorporated into an authenticated protocol.
Elliptic-curve cryptography applies analogous ideas to groups formed by points on elliptic curves over finite fields. The absence of known subexponential classical attacks against properly selected general elliptic-curve groups permits smaller key representations than those ordinarily used for RSA at comparable security levels. The security of a deployment still depends on curve selection, implementation behavior, and the validity of the underlying hardness assumptions.
Hybrid encryption
Asymmetric operations are computationally more expensive than symmetric encryption and usually operate on messages of restricted size. Practical systems therefore use hybrid cryptosystems. A randomly generated symmetric session key protects the bulk data, while a public-key mechanism encapsulates or establishes that session key.
A key encapsulation mechanism produces a shared secret together with an encapsulation value. The recipient uses the private key to recover the same secret, which is then transformed by a key derivation function into material suitable for an authenticated symmetric cipher. This separation permits the asymmetric and symmetric components to receive distinct security analyses.
Hybrid design also limits the consequences of structural properties in public-key primitives. A secure encapsulation mechanism does not directly encrypt arbitrary application data, and an authenticated-encryption algorithm can provide confidentiality and integrity for the resulting data stream. The complete protocol remains responsible for binding ciphertexts to the intended context and for rejecting malformed or replayed messages.
Authentication and certification
Possession of a public key does not establish whose private key corresponds to it. If an adversary can substitute a different public key during distribution, encrypted information may be directed to the adversary, while signatures may be verified against an attacker-controlled identity binding. Public-key authentication consequently requires a trusted method for obtaining the correct key.
Loren Kohnfelder described digital certificates in 1978 as signed records associating names with public keys. This model developed into certificate-based infrastructures in which a certificate authority signs identity–key bindings, relying parties validate a chain of signatures, and revocation mechanisms represent changes in certificate status. The X.509 standard supplies a widely used certificate format and validation framework.
Other trust models distribute authentication differently. The web of trust records endorsements among key holders rather than placing all identity bindings beneath a centralized hierarchy. Certificate Transparency uses publicly auditable logs to expose certificate issuance, but logging does not by itself determine whether the recorded identity information is correct.
Security properties and implementation constraints
Security claims for public-key cryptography are expressed relative to an adversarial model. Indistinguishability under chosen-plaintext attack formalizes the requirement that selected-message ciphertexts reveal no usable information about which protected message was encrypted. Stronger models permit an adversary to request decryptions of other ciphertexts and are relevant when a system exposes observable responses to malformed input.
Digital-signature security is generally formulated as resistance to existential forgery under chosen-message attack. Under this definition, an adversary may obtain signatures for selected messages but must remain unable to produce a valid signature for a new message. The definition addresses mathematical forgery rather than coercion, private-key theft, or ambiguity in the interpretation of signed content.
Implementations can fail even when the underlying problem remains computationally hard. Variations in execution time, power consumption, electromagnetic emissions, or memory access can disclose private information through a side-channel attack. Faults induced during a private-key computation can also reveal secret parameters, particularly when an implementation uses algebraic shortcuts such as the Chinese remainder theorem.
Randomness is another structural requirement. Predictable key generation can produce private keys that an adversary reconstructs directly, while nonce reuse in several signature systems can expose the signing key through elementary algebra. Deterministic nonce derivation can remove dependence on fresh runtime randomness for specified signature operations, although initial key generation still requires adequate entropy.
Quantum computation
Large, error-corrected quantum computers would alter the assumptions underlying widely deployed public-key systems. Shor's algorithm solves integer factorization and discrete logarithms in polynomial time on an appropriate quantum computer, which would invalidate the principal hardness assumptions used by RSA, finite-field Diffie–Hellman, and elliptic-curve cryptography.
Post-quantum cryptography studies constructions based on different computational problems. Lattice-based key encapsulation and signatures form a major part of this field, while hash-based signatures derive their security primarily from properties of cryptographic hash functions. These algorithms run on conventional computers; the term refers to their intended resistance to attacks using both classical and quantum computation.
The confidentiality implications can precede the construction of a cryptographically relevant quantum computer. Encrypted traffic recorded earlier can be retained and attacked later if its public-key protection becomes breakable, although the practical consequence depends on whether the protected information remains sensitive and whether the protocol provided suitable forms of forward secrecy.