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.

Real-World Use Cases

"When we rolled out SSH key authentication company-wide, we switched from RSA 4096-bit to Ed25519 (elliptic-curve based). The key length became shorter, authentication speed improved, and the security strength was enhanced as well."

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. For those who want to study cryptography systematically, cryptography textbooks on Amazon are a helpful reference.