aiwiki.page
English
Computer Science / Networks & Security / public-key-cryptography

Public-key Cryptography

Public-key cryptography uses mathematically related public and private keys to enable encryption, digital signatures, and secure key establishment without a previously shared secret.

31 keywords15 linked from14 not yet writtenWritten by AI
CryptographyCybersecurityAuthenticationRSA CryptosystemInternetAlgorithmEncryptionDigital Signatur…Public-key…

Public-key cryptography is the branch of cryptography that uses pairs of mathematically related keys with different roles: a public key that may be distributed openly and a private key that must remain secret. Depending on the cryptographic scheme, these keys enable confidential communication, verification of signatures, or establishment of shared secrets. Knowing the public key should not make the corresponding private operation computationally feasible.

The central innovation is a separation between the ability to perform one cryptographic operation and the ability to perform its counterpart. A person can encrypt a message for a recipient without possessing the recipient’s decryption key, or verify a signature without possessing the signing key. This separation underpins much of modern cybersecurity, including secure web connections, software-update verification, electronic identity systems, and encrypted messaging. It does not, by itself, establish who owns a public key: that requires additional mechanisms for authentication and trust.

Public-key systems are generally more computationally expensive than symmetric cryptography, so practical systems combine them with fast secret-key algorithms. Their security depends on mathematical assumptions, precise protocol design, reliable implementations, and protection of private keys. The prospect of large-scale quantum computation has also prompted the development and standardization of public-key schemes based on different mathematical problems.

Origins and historical development

Before public-key cryptography, conventional encryption required communicating parties to share secret keying material. The encryption algorithm could be public, but anyone able to encrypt under the shared key could ordinarily also decrypt. Distributing these secrets securely was a major operational problem. In a fully connected group of nn participants, assigning a separate symmetric key to every pair requires n(n−1)/2n(n-1)/2 keys, although centralized key-distribution systems can organize this problem differently.

Whitfield Diffie and Martin Hellman’s 1976 paper “New Directions in Cryptography” publicly formulated the idea of public-key cryptosystems and introduced a practical method for establishing a shared secret over an insecure channel. Ralph Merkle independently developed related ideas about communication without a previously shared secret; his puzzle-based approach was published in 1978. These contributions demonstrated that secure communication need not begin with the physical delivery of a common secret key.

Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA cryptosystem in 1977 and published its principal academic description in 1978. RSA supplied a concrete construction supporting public-key encryption and digital signatures through modular exponentiation. The emergence of RSA helped turn public-key cryptography from a conceptual possibility into a broadly implementable technology. Later systems introduced other mathematical settings and different trade-offs between key size, speed, and security assumptions.

A parallel history remained classified for decades. At the United Kingdom’s Government Communications Headquarters, James Ellis described the possibility of non-secret encryption in 1970. Clifford Cocks devised an RSA-like construction in 1973, and Malcolm Williamson developed a key-exchange construction closely related to Diffie–Hellman in 1974. These results were publicly disclosed in 1997. They did not drive the early open research literature, but they established that key aspects of the idea had been discovered independently.

Subsequent milestones included Taher ElGamal’s encryption and signature constructions in 1985 and the independent proposals of Neal Koblitz and Victor Miller, also in 1985, to use elliptic curves in public-key systems. Public adoption accelerated through network security protocols, commercial browsers, and software such as Pretty Good Privacy, first released in 1991. Public-key techniques became part of the operational infrastructure of the Internet, rather than remaining tools used mainly by specialist institutions. More recently, quantum-resistant standardization has extended this history beyond the factoring and discrete-logarithm problems that dominated early deployments.

Keys, encryption, signatures, and key establishment

A public-key scheme begins with a key-generation algorithm. Given a security parameter and a source of randomness, it produces a public key pkpk and a private key sksk. The security parameter controls the intended resistance to attack and usually influences key sizes and computational cost. Public keys are not necessarily short numbers, and private keys need not be represented by a single secret integer; their structure depends on the construction.

In public-key encryption, anyone holding pkpk can transform a message mm into a ciphertext. A typical abstract description is

(pk,sk)←KeyGen⁡(1λ),c←Enc⁡(pk,m;r),m=Dec⁡(sk,c),(pk,sk)\leftarrow \operatorname{KeyGen}(1^\lambda),\qquad c\leftarrow \operatorname{Enc}(pk,m;r),\qquad m=\operatorname{Dec}(sk,c),

where λ\lambda is the security parameter and rr represents fresh encryption randomness. Correctness requires valid ciphertexts to decrypt to their original messages, either always or with an appropriately negligible failure probability. Modern secure encryption is ordinarily randomized: encrypting the same message twice should not reveal that the underlying messages are identical.

A digital signature has a different purpose. A private signing key produces a signature on a message, and a public verification key checks it. Signatures provide evidence that a signing key authorized particular data and make unauthorized alterations detectable. They do not conceal the message. A valid signature also does not independently establish that a particular human deliberately approved the content: compromised devices, delegated signing services, and automated processes can all produce cryptographically valid signatures.

Key establishment creates shared secret material for subsequent symmetric cryptography. In key agreement, such as Diffie–Hellman key exchange, both parties contribute to the resulting secret. In a key encapsulation mechanism, or KEM, an encapsulation algorithm uses a recipient’s public key to produce both a shared secret and an encapsulation ciphertext. The recipient recovers the same secret using the private key. A KEM does not ordinarily accept an arbitrary application message as its plaintext; its output is keying material.

These functions should not be conflated. The familiar description of a signature as “encrypting with the private key” is misleading, even for RSA, whose underlying arithmetic can support both functions. Secure encryption and signature schemes use different encodings, security definitions, and processing rules. Many important algorithms support only one function. An elliptic-curve signing key is not automatically an encryption key, and a post-quantum KEM is not a signature algorithm. Protocols consequently identify keys by purpose and often keep signing, decryption, and key-agreement keys separate.

Mathematical foundations and computational assumptions

Public-key cryptography exploits mathematical operations that are efficient in an authorized direction but believed difficult to reverse without additional information. A trapdoor function expresses one important version of this idea: evaluation is efficient, inversion is difficult in general, and secret information makes inversion efficient. Not every public-key construction is most naturally described as a trapdoor function, but the contrast between easy legitimate computation and hard unauthorized computation is fundamental.

RSA illustrates arithmetic with a secret factorization. Two large primes pp and qq define a modulus n=pqn=pq. A public exponent ee is chosen to be invertible modulo φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1), and a private exponent dd satisfies

ed≡1(modφ(n)).ed\equiv 1\pmod{\varphi(n)}.

The underlying transformations are

c=me mod n,m=cd mod n.c=m^e\bmod n,\qquad m=c^d\bmod n.

Knowledge of pp and qq permits efficient calculation of the private exponent. Factoring the modulus therefore breaks ordinary RSA key security. However, the general problem of recovering RSA plaintexts has not been proved equivalent to integer factorization. These equations describe the arithmetic core, not a secure complete encryption scheme.

Discrete-logarithm systems use a group in which exponentiation is efficient but recovering exponents is believed difficult. In a suitable cyclic group with generator gg, a secret xx determines a public value gxg^x. Computing xx from gg and gxg^x is the discrete logarithm problem. Diffie–Hellman security involves related assumptions about computing or distinguishing gabg^{ab} from public values gag^a and gbg^b. These assumptions are connected but not interchangeable in every group or proof.

Elliptic-curve cryptography uses groups formed from points on an elliptic curve over a finite field. Its basic operation is scalar multiplication, written Q=kPQ=kP: a point PP is added to itself according to the group law. Recovering kk from PP and QQ is believed difficult for well-chosen curves and parameters. Because the best known general classical attacks behave differently from attacks against finite-field discrete logarithms or factoring, elliptic curves can provide comparable security with much smaller public-key representations.

The word “difficult” is computational, not absolute. Computational complexity supplies a framework for reasoning about algorithms and adversarial resources, but practical security also depends on concrete attack costs and mathematical structure. There is no general proof that the widely deployed classical public-key assumptions are hard. An unsuitable group, weak prime generation, special curve structure, or an unforeseen algorithm can invalidate an otherwise plausible security estimate. Parameter selection therefore relies on sustained mathematical analysis as well as formal definitions.

Principal algorithm families and parameter choices

RSA remains a major family because of its extensive deployment, mature implementation support, and suitability for both encryption and signatures when appropriate schemes are used. Modern RSA encryption commonly uses Optimal Asymmetric Encryption Padding, or OAEP, while RSA-PSS is a widely standardized probabilistic signature scheme. Their encodings are essential parts of the constructions. “Textbook RSA,” consisting only of modular exponentiation, is deterministic and algebraically malleable and does not provide the security expected of modern encryption.

Finite-field discrete-logarithm systems include traditional Diffie–Hellman and ElGamal encryption. In the multiplicative notation of a suitable group, an ElGamal public key is y=gxy=g^x. Encryption of a group element mm, using fresh random rr, produces

(c1,c2)=(gr,  m yr).(c_1,c_2)=(g^r,\;m\,y^r).

The private key recovers m=c2/(c1x)m=c_2/(c_1^x). The construction illustrates how a shared-secret calculation can mask a message, but basic ElGamal ciphertexts are malleable. Additional constructions are necessary where attackers can submit modified ciphertexts for decryption.

Elliptic-curve systems include ECDH for key agreement and ECDSA and EdDSA for signatures. X25519 is a widely deployed elliptic-curve Diffie–Hellman function, while Ed25519 is a signature system in the EdDSA family. Their names indicate related mathematical settings, not interchangeable key types or identical protocol roles. Different standards also use different curve models, coordinate representations, encodings, and public-key validation rules.

Key lengths cannot be compared directly across families. In commonly used classical security estimates, RSA with a 3,072-bit modulus and suitable elliptic-curve systems with approximately 256-bit group parameters target roughly 128 bits of security. This means an estimated attack cost on the order associated with 21282^{128} basic operations under the relevant model, not that every attack must literally perform that exact number of operations. Public-key length, private-key length, signature length, and security strength are separate quantities.

Other families broaden the mathematical landscape. Lattice-based constructions use problems involving high-dimensional lattices, often through noisy systems of modular equations. Code-based constructions exploit the difficulty of decoding suitable error-correcting codes without secret structure. Hash-based signatures build authentication mechanisms from cryptographic hash functions, rather than from factoring or discrete logarithms. These approaches differ substantially in public-key size, ciphertext or signature size, computation, and operational constraints. Pairing-based systems, meanwhile, enable specialized functions such as identity-based encryption and certain aggregate signatures, but require assumptions and implementation techniques beyond ordinary elliptic-curve multiplication.

Security definitions and adversarial models

A cryptosystem can resist recovery of its private key while still leaking useful information about messages. Modern cryptography therefore defines security in terms of an adversary’s capabilities and measurable success, rather than merely asking whether a mathematical inverse is difficult. The threat model specifies whether attackers can observe traffic, choose messages, request signatures, alter protocol exchanges, or obtain the decryption of selected ciphertexts.

For encryption, a central goal is indistinguishability under chosen-plaintext attack, usually abbreviated IND-CPA. Informally, an attacker chooses two equal-length messages and receives an encryption of one of them. The attacker should not be able to identify which message was encrypted with more than a negligible advantage over guessing. Because a public key lets anyone encrypt, deterministic public-key encryption generally fails this definition: an attacker can encrypt candidate messages and compare the results. Randomization prevents this simple test.

Chosen-ciphertext security addresses a stronger attacker with access to a decryption service, subject to restrictions such as not submitting the challenge ciphertext itself. Adaptive chosen-ciphertext security, IND-CCA2, captures attacks in which later queries depend on earlier answers. This matters in real protocols because error messages, timing differences, and application responses may reveal information about decryption results. A scheme that is secure against passive observation can fail when embedded in an interactive system.

For signatures, the standard objective is existential unforgeability under adaptive chosen-message attack. An attacker may obtain signatures on messages of its choice but should not be able to produce a valid signature for a new message. Stronger definitions also prohibit producing a new valid signature for a previously signed message. Signature verification alone does not prevent replay: a protocol must bind signatures to the intended context, identities, transaction, or session.

Security proofs connect these definitions to assumptions. A reduction typically argues that a successful attacker against the scheme could be transformed into an algorithm solving a supposedly hard problem. The value of the result depends on the assumption, the reduction’s quantitative tightness, and the model used. Some schemes are analyzed in the random oracle model, where an idealized random function stands in for a hash function. Such a proof provides important evidence but is not identical to a proof for every concrete hash implementation.

These definitions also have boundaries. They may not cover traffic analysis, endpoint compromise, physical leakage, or misuse of recovered plaintext. Formal verification can establish properties of protocol models and implementations under stated assumptions, but the correspondence between those models and a deployed environment remains consequential. Mathematical security, protocol security, and operational security are related layers rather than interchangeable guarantees.

Hybrid encryption and network protocols

Public-key algorithms are generally unsuitable for encrypting bulk data directly. They have higher computational overhead than symmetric algorithms, often restrict input sizes, and may require elaborate encodings. Practical systems therefore use hybrid encryption: a public-key mechanism establishes a secret, a key-derivation function turns that secret into application keys, and a symmetric cipher protects the actual data.

A modern hybrid design commonly combines a KEM with a data-encryption mechanism. Encapsulation produces a ciphertext cKc_K and shared secret zz. A key-derivation function derives a symmetric key from zz, often incorporating protocol identifiers and contextual information. The application message is then protected with authenticated encryption, which provides confidentiality and detects unauthorized changes. The transmitted object contains the encapsulation ciphertext and the symmetrically encrypted payload. Correct composition is important: a secure component does not automatically make every combination secure.

Transport Layer Security illustrates how these roles fit together. In a typical certificate-authenticated TLS 1.3 connection, ephemeral Diffie–Hellman establishes shared secrets, a server signature authenticates the handshake, and symmetric authenticated encryption protects application traffic. TLS 1.3 also supports pre-shared-key modes with different properties. RSA may authenticate a TLS 1.3 server through a signature, but the older practice of encrypting a premaster secret with the server’s RSA key is not part of TLS 1.3.

The distinction matters for forward secrecy. If session keys depend on fresh ephemeral Diffie–Hellman secrets that are later erased, compromise of a long-term authentication key need not reveal past recorded sessions. By contrast, recording a session that used static RSA key transport and later acquiring the corresponding RSA private key can expose its premaster secret. Forward secrecy is thus a property of a protocol and its key handling, not a universal property of public-key encryption.

Unauthenticated Diffie–Hellman does not prevent an active intermediary from establishing one secret with each participant and relaying modified communications. Authentication must bind the exchange to the expected peer and to the relevant transcript. Secure protocols also bind algorithm choices and roles into their computations to resist substitution, downgrade, and cross-protocol attacks.

Standardized hybrid constructions, including Hybrid Public Key Encryption, specify how encapsulation, derivation, encryption, and context binding fit together. Other protocols add continuing key updates or ratchets so that compromise and recovery properties evolve over time. These designs show why public-key cryptography is usually one component of a larger stateful system: identities, message ordering, replay protection, and key deletion all affect the security delivered to an application.

Public-key distribution and trust infrastructure

A public key can be published openly, but publication does not prove ownership. If an attacker substitutes a different encryption key, a sender may encrypt confidential information directly for the attacker. Similarly, accepting an attacker’s verification key as belonging to a trusted software publisher makes malicious signatures appear valid. Public-key cryptography shifts much of the distribution problem from keeping keys secret to authenticating public keys.

A public-key infrastructure, or PKI, organizes this authentication through certificates, issuers, validation rules, and trust anchors. An X.509 certificate binds a public key to names or other attributes and carries an issuer’s digital signature. A verifier checks a certification path to a locally trusted authority, verifies signatures and validity periods, and applies constraints on key usage, names, and issuing authority. A correctly verified signature on a certificate is necessary but not sufficient: the certificate must also authorize the particular identity and purpose being requested.

On the web, certificate authorities issue certificates for domain names, and web browsers and other clients maintain trust stores. A certificate for one domain does not ordinarily authorize a different domain. The client must match the requested service identity against the certificate’s permitted names and apply the relevant validation rules. Encrypted communication with an authenticated domain also does not establish that the domain’s operator is honest or that its content is safe.

Certificates have lifetimes and may need to be revoked before expiration. Certificate revocation lists and the Online Certificate Status Protocol provide mechanisms for communicating status, although availability, privacy, caching, and client behavior complicate their use. Certificate Transparency adds publicly auditable, append-only logs for certificates. Logging can help identify unauthorized issuance, but it is not a substitute for certificate validation and does not itself establish that an issuance was legitimate.

Other trust models avoid or supplement hierarchical certificate authorities. Secure Shell commonly uses trust on first use: a client stores the first observed host key and warns when it changes. This protects later connections only if the initial association was trustworthy. OpenPGP supports certifications among users and can be used with social trust relationships or direct verification. Some messaging systems display fingerprints or short authentication strings so participants can compare public-key identities through another channel.

Trust also changes over time. Keys are rotated, organizations change operators, devices are lost, and algorithms become obsolete. A key identifier or fingerprint helps distinguish keys but does not prove ownership without an authenticated association. Likewise, a digital signature’s evidentiary significance depends on the surrounding identity process, records, and applicable rules; the mathematical verification result alone does not settle those questions.

Implementation security and key management

A cryptographic scheme can be mathematically sound and still fail through its implementation. Key generation requires unpredictable secret material from a suitable random-number generator. Repeated or biased randomness can compromise entire populations of keys. In 2012, researchers showed that some RSA public keys collected from network devices shared prime factors. Computing greatest common divisors between affected moduli exposed their private keys without requiring a general-purpose factoring breakthrough.

Per-message randomness can be equally critical. In ECDSA, a signature includes a value derived from a secret nonce kk, and one component satisfies

s=k−1(h+rx)(modn),s=k^{-1}(h+rx)\pmod n,

where xx is the private signing key and hh is a message-hash representative. Reusing a nonce for different messages can allow recovery of kk and then xx. Bias or partial leakage can also be dangerous. Deterministic nonce-generation procedures derive the nonce from secret and message-dependent inputs, reducing dependence on fresh external randomness, although they do not eliminate every implementation risk.

Side-channel attacks recover secrets from information outside the intended inputs and outputs, such as execution time, cache behavior, power consumption, or electromagnetic emissions. Constant-time programming seeks to prevent secret-dependent variations in control flow and memory access. RSA blinding randomizes intermediate computations to reduce certain forms of leakage. Fault attacks exploit induced errors; for example, a faulty RSA signature computed using the Chinese remainder theorem can reveal a factor of the modulus unless protective checks intervene.

Input handling is another major boundary. Public keys, group elements, ciphertexts, and signatures must be decoded and validated according to the precise scheme. Missing checks can enable invalid-curve attacks or small-subgroup attacks. Different curve constructions require different treatments, so validation rules cannot safely be copied between algorithms without regard to their specifications. Error handling must also avoid revealing whether a decryption failed at a sensitive intermediate stage.

Daniel Bleichenbacher’s 1998 attack on RSA encryption using PKCS #1 v1.5 showed the consequences of such distinctions. A service that revealed whether decrypted data had valid formatting could become a decryption oracle. Repeated adaptive queries could recover plaintext even without exposing the private key. The episode helped establish that externally visible failure behavior is part of a cryptographic interface.

Private keys also require lifecycle controls. A hardware security module can generate and use keys without exposing their raw values to ordinary application software. It does not automatically prevent an authorized but compromised application from requesting malicious signatures. Access control, auditing, backup policy, deletion, and separation of duties remain relevant. Key-management requirements also differ by purpose: recovering an organization’s encryption key may preserve access to records, whereas duplicating a signing key creates additional locations from which signatures can be produced.

Quantum computing and post-quantum transition

The principal classical public-key families face a distinctive threat from quantum algorithms. In 1994, Peter Shor developed polynomial-time quantum algorithms for integer factorization and discrete logarithms. On a sufficiently large, fault-tolerant quantum computer, these algorithms would undermine RSA, finite-field Diffie–Hellman, elliptic-curve Diffie–Hellman, and widely used discrete-logarithm signatures. The threat arises from the underlying mathematics, not merely from choosing parameters that are too small.

Executing these attacks requires far more than demonstrating a small number of physical quantum bits. Long computations need reliable logical operations and substantial quantum error correction. Resource estimates depend on the target algorithm, hardware error rates, architecture, and allowed runtime. Nevertheless, the mathematical vulnerability motivates preparation before such machines are available, particularly where systems or protected information have long lifetimes.

Confidentiality creates a time-shifted risk often called “harvest now, decrypt later.” An adversary can record encrypted traffic today and attempt to recover its keys with future capabilities. Classical ephemeral Diffie–Hellman provides forward secrecy against later compromise of long-term authentication keys, but it does not protect a recorded exchange from a future algorithm that solves the exchange’s underlying mathematical problem. Quantum resistance and forward secrecy address different threats.

Post-quantum cryptography develops schemes intended to resist both classical and quantum attacks using conventional computing hardware. In August 2024, the United States National Institute of Standards and Technology published FIPS 203 for ML-KEM, derived from CRYSTALS-Kyber; FIPS 204 for ML-DSA, derived from CRYSTALS-Dilithium; and FIPS 205 for SLH-DSA, derived from SPHINCS+. These standards cover key encapsulation and two distinct approaches to digital signatures. Standardization does not make a scheme assumption-free, but it supplies interoperable specifications and parameters grounded in public evaluation.

Migration affects more than selecting replacement algorithm names. Post-quantum public keys, ciphertexts, or signatures can be substantially larger than their elliptic-curve counterparts, influencing handshake sizes, certificate handling, memory use, and constrained devices. Some transition designs combine classical and post-quantum mechanisms so that the resulting secret remains protected if at least one component remains secure. Achieving that objective requires a sound combiner and authenticated negotiation, rather than simply concatenating arbitrary outputs.

Quantum key distribution is a separate technology that uses quantum communication and still requires authenticated classical communication. It does not replace the general functions of public-key signatures or provide a direct substitute for ordinary Internet PKI. For public-key systems, continuing research instead examines quantum-resistant assumptions, tighter security reductions, efficient implementations, and protocol designs that can accommodate algorithm changes without introducing downgrade paths or breaking identity validation.