What is Asymmetric Cryptography and How Does It Work?
We can roughly divide encryption algorithms into symmetric and asymmetric ones. Symmetric ones have a longer history. It can be said that they have over 2000 years of history and development. The concept of asymmetric or public-key cryptography, on the other hand, was developed in 1970s and first publicly published in 1977 by Whitfield Diffie and Martin Hellman, researchers at Stanford University.
The main difference between symmetric and asymmetric cryptography is that symmetric cryptography uses the same key for encryption and decryptions, while asymmetric cryptography uses two different, matched keys – a key pair with a public and a private key. Each individual in a communication network has their own key pair. The private pair is safely stored where only they can access it, while the public part is freely visible to all.
If person A wants to send a message to person B, they encrypt the message with person B’s public key. After that only person B can decrypt it using their well protected private key. Encryption can also work the other way around. Say person A wants to prove that they have indeed produced a certain document. They sign it with their own private key and publish it. After this anyone can take the document and try to verify the signature using person A’s public key. If verification is successful, it was indeed signed with person A’s private key – meaning that only person A could have signed it.
Advantages and disadvantages
One of the main advantages of asymmetric cryptography is its flexibility. The public-private key pairs enable us the use of digital certificates, PKI (Private Key Infrastructure) schemes, code signing, key exchange algorithms, authentication, and more. Additionally, compared to symmetric cryptography it enables bigger networks to communicate using a lower number of secret keys – key management becomes a lot easier.
On the other hand, key lengths of asymmetric keys are traditionally longer. For example, RSA, the most widely used asymmetric algorithms, usually uses keys of length 2048, or 4096 bits. The keys are getting longer as computing capacities are increasing in order to ensure a constant security level. This also causes slower encryption speed, which makes it not appropriate for encrypting large amounts of data.
Worth mentioning is also the fact that quantum computers will be able to completely break our presently used asymmetric algorithms. In the case of symmetric ones, they will just greatly reduce their level of security.
RSA and Elliptic Curves
RSA is the most well-known asymmetric cipher. It was developed by Ronald Rivest, Adi Shamir, and Leonard Adleman (hence RSA) and published in 1977. The underlying concept it relies on is the integer factorization problem. Say you have two prime number, p and q. Multiplying them into k=pq is easy. But say you know just the number k and the fact it is a multiplication of two primes. Finding these two primes k is composed out of seems easy for lower numbers. For example, 15 is obviously a multiplication of 3 and 5. But in general, integer factorization is an NP-hard problem - we do not know how to solve it in polynomial time. In practice this means it would take our computers millions of years to factorize a big enough integer.
So how to derive a public and private key for this scheme? Well, let k be the public key. Everyone can see it. The primes p and q, on the other hand, stay hidden and well protected as a private key.
One disadvantage of the RSA scheme are the long key lengths, which was one of the motivations for developing an alternative asymmetric scheme. In 1985 Neal Koblitz and Victor Miller independently co-discovered elliptic-curve cryptography. This family of codes are based on an entirely different NP-hard problem than RSA, the elliptic curve discrete logarithm problem. This time instead of private and public key parameters being primes and their multiplication, we have an elliptic curve, its base point, and others. The usual key length is 256bits.
Source: Nastja Cepak, PhD Cryptography, and CREAplus Cybersecurity Team.