Skip to main content

Public-Key Cryptography - Asymmetric Encryption

About 2 min read

Public-key cryptography (asymmetric cryptography) is an encryption scheme that uses two different keys for encryption and decryption: a public key and a private key. The public key can be distributed to anyone, while the private key is held only by its owner. Data encrypted with the public key can be decrypted only with the corresponding private key, and a signature created with the private key can be verified with the public key. This asymmetry forms the foundation of secure communication on the internet and digital signatures.

Historical Background - A Revolution in Cryptography

In 1976, Whitfield Diffie and Martin Hellman introduced the concept of public-key cryptography in their paper "New Directions in Cryptography." Until then, encryption required the sender and receiver to share the same key in advance, and the secure delivery of keys was a challenge. The following year, in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman devised the RSA cipher, presenting a concrete public-key scheme. RSA bases its security on the mathematical property that factoring the product of large prime numbers is difficult. In 1985, Neal Koblitz and Victor Miller independently proposed elliptic-curve cryptography (ECC), achieving security equivalent to RSA with a shorter key length. The TLS 1.3 specification (RFC 8446) requires support for key exchange with the elliptic curve group secp256r1.

How It Works

Generate key pair
Send the public key to the other party
Encrypt with the public key
Decrypt with the private key

The core of public-key cryptography lies in the "one-way function." Multiplying large prime numbers together is easy, but finding the original primes from the product (factorization) is difficult. RSA exploits this property, while ECC exploits the difficulty of the discrete logarithm problem on elliptic curves. In both cases, with current computers and a sufficient key length, breaking them would take an enormous amount of time.

Comparison with Symmetric-Key Cryptography

AspectSymmetric-key (e.g., AES)Public-key (RSA / ECC)
Number of keysOne, shared by sender and receiverTwo: a public key and a private key
Processing speedFastSlow
Key distribution problemRequires a secure channelThe public key can be made public
Main usesEncrypting large amounts of dataKey exchange, signatures, authentication

In actual communication, a hybrid scheme combining both is used. In the TLS handshake, a shared key is first established through a key exchange that uses public-key cryptography, and subsequent data communication is carried out with fast symmetric-key cryptography. This mechanism achieves both secure key distribution and fast communication. Our article on the basics of encryption also explains this in detail.

Relationship with Digital Signatures

Public-key cryptography is used not only for encryption but also for digital signatures. In the case of signatures, the keys are used in the opposite direction from encryption. The sender signs the hash value of the data with their private key, and the receiver verifies it with the public key. This makes it possible to detect data tampering and verify the sender's identity at the same time. PKI (public-key infrastructure) is a mechanism that guarantees the validity of public keys through certificates, and it underpins the HTTPS communication of websites.

Why Key Lengths Cannot Be Compared Across Algorithms

Key length figures cannot be compared directly across different algorithms. The key length of RSA corresponds to the difficulty of factorization, while the key length of elliptic-curve cryptography corresponds to the difficulty of the discrete logarithm problem, and the key size required to reach the same level of security differs from one algorithm to another. Because elliptic-curve based schemes can achieve security equivalent to that of the older schemes with shorter keys, shortening a key does not mean weakening it. Shorter keys also reduce the volume of data and the amount of computation involved in signatures and key exchange, so processing can become lighter while the same level of security is maintained. Treating key length as a standalone metric overlooks these differences between algorithms and leads to judging the larger number as unconditionally safer. Evaluating the algorithm name and the key length as a pair is the starting point when reviewing key settings.

The Quantum Computer Threat and Post-Quantum Cryptography

Once quantum computers become practical, Shor's algorithm may efficiently solve the factorization and discrete logarithm problems that underpin the security of RSA and ECC. To prepare for this, in August 2024 NIST published three post-quantum cryptography standards (FIPS 203, 204, and 205): ML-KEM (lattice-based key encapsulation), ML-DSA (lattice-based digital signatures), and SLH-DSA (hash-based digital signatures). In September 2024, the Chrome team at Google announced that Chrome 131 would switch the hybrid key exchange for TLS connections from Kyber to ML-KEM. Our article on post-quantum cryptography and password security explains the future impact in detail.

Common Misconceptions

There is a misconception that "public-key cryptography is more secure than symmetric-key cryptography," but they offer different kinds of security. While AES-256 retains a degree of resistance even against quantum computers, RSA-2048 may be broken by them. Also, while it is true that "there is no problem in making a public key public," there is a risk of a man-in-the-middle attack unless the validity of the public key is verified.

Was this article helpful?

Related Terms