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 the greatest challenge. The following year, in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman devised the RSA cipher, putting public-key cryptography into practical use. 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. In today's TLS 1.3, ECC is used as standard.

How It Works

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 extremely 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 astronomical amount of time.

Comparison with Symmetric-Key Cryptography

In actual communication, the mainstream approach is a hybrid scheme combining both. In the TLS handshake, a shared key is first exchanged securely using 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 2024 NIST officially announced ML-KEM (lattice-based key encapsulation) and ML-DSA (lattice-based digital signatures) as standards for post-quantum cryptography. Google Chrome has already enabled hybrid key exchange (traditional ECC + ML-KEM) by default for TLS connections. 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. That is precisely why verifying public keys with certificates is essential.