This post is from my series of short essays on cybersecurity.

In previous post Cryptography – The game of confusion and diffusion I mentioned the challenges with symmetric key cryptography : distributing keys on a secure channel, managing number of keys for each pair of participants, and most importantly symmetric key cryptography can’t provide protection against cheating since both participants hold the same key. Public key cryptography (also called asymmetric key cryptography) beautifully addresses the problem of message authenticity and integrity.  

The basis of asymmetric key cryptography is a key-pair. Data encrypted using one key can be  decrypted by only corresponding other key in the pair. Owner of the key-pair keeps the secret private key and makes the corresponding public key available to anyone. The following picture below illustrates the flow where Bob not only decrypts the message but is also sure that the sender of the message is Alice.

So what brings the confidence in security of asymmetric key cryptography? How are we sure that someone knowing the public key can’t determine the corresponding private key? How do we know that each key pair is unique? The answer is reliance on hard computational problems. Hard computational problems are mathematical problems that are simple to describe but no known algorithm exists to find a solution in a reasonable time. In this post I will discuss three well known mathematical problems used in asymmetric key cryptography – integer factoring (RSA encryption algorithm), discrete logarithms (DLs) in finite fields (Diffie-Hellman key exchange and DSA algorithms), and DLs over elliptic curve (elliptic curve Diffie-Hellman, ECDSA algorithms). These problems with small numbers are solvable by brute force or basic algorithms. But computational requirements grow as we take these problems to large numbers; there is no efficient algorithm discovered on this planet till date to solve them in a reasonable time window.

Integer factoring and RSA – The factoring problem consists of finding the prime number p and q given a large number N, N = p * q. The security of RSA algorithm comes from the fact that factoring is hard; An adversary cannot factor the public modulus N contained in the public RSA key into its prime factors p and q to compute the private key. 

How using the large number keys hardened the security posture? Proof is actually in heuristic complexity estimates. For example a 1024-bit number will have two prime factors of about 500 bits each and will take 2⁷⁰ basic operations where a 2048-bit number will have prime factors of approximately 1000 bits each and take 2⁹⁰ basic operations that are a million times more. NIST 800-57 – Recommendation for Key Management: Application-Specific Key Management Guidance recommends using 2048 bit size keys for all key types using RSA algorithm.

Discrete Logarithm and Diffie-Hellman – In the Discrete Logarithm Problem (DLP), given g and p public integers and some input y = g^x mod p, problem is to find the discrete logarithm (DL) x,  where p is a prime number. The DLP is called discrete because we are dealing with integers (no continuous real numbers), and a logarithm because we are looking for logarithm of y in base g. The security of many cryptographic schemes relies on the computational hardness of the DLP. Most popular is Diffie-Hellman key exchange that is “based on” the DLP in the sense that if an adversary can compute the DL of one of the publicly transmitted key exchange values, they can use the value to easily compute the shared secret. NIST 800 – 57 Part 3 recommends using 2048-bit size keys for key establishment protocols with Diffie-Hellman.  

Elliptic Curve DLs – The newest addition in asymmetric key cryptography in 1985 is DLP on an elliptic curve (ECDLP). The theory and hardness of this mathematical problem is more complicated to explain compared to integer refactoring and discrete logarithm. Certain properties make it good for cryptography. First property is horizontal symmetry: any point on the curve can be reflected over the x axis and remain the same curve. Second important property is that  any non-vertical line will intersect the curve in at most three places. An example graph looks a bit like the Lululemon logo tipped on its side.

My favorite read to get the quick primer on elliptic curve cryptography (ECC) is in Nick Sulivan’s blog post A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography. If you are looking for a quick overview of ECC, it is my recommended reading. 

My favorite read to get the quick primer on elliptic curve cryptography (ECC) is in Nick Sulivan’s blog post A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography. If you are looking for a quick overview of ECC, it is my recommended reading. 

More than 40 years later we still don’t know any efficient algorithm to prime factor a large number or solve discrete logarithms. These problems are NP (nondeterministic polynomial) time problems. NP problems are the problems for which a solution can be verified efficiently even though the solution is hard to find. For example it takes a lot of computation to identify the prime factor of 101369, but if someone tells you that 607 and 167 are factors of 101369 you can quickly verify it. All the public key cryptography deployed today relies on either factoring (RSA), discrete logarithm (Diffie-Hallman) or Elliptic Curve (ECDSA).This short essay is only an introduction, if you are interested in exploring in depth there are several good introductory cryptography books. Here are two of my recommendations: Serious Cryptography – by Jean-Philippe Aumasson or  Cryptography made simple by Nigel Smart.

Today public key cryptography is the backbone of all secure communications over the internet with applications spread from digital signature, identifying user and devices, smart card authentication, to modern blockchain applications. Hard mathematical problems discussed in this essay provide algorithmic protection. But several additional factors need to be considered in security assessment like how the secrecy of the private key is maintained, if the correct random number generation algorithm is used to generate keys that are not predictable, how identity proofing is done before associating it with the key pair. I will discuss more details on key generation and key management and popular internet protocols that use public key cryptography in future posts.