A Primer on Asymmetric Cryptography

Cryptography is categorized based on the symmetry of the encryption key and encryption-decryption algorithms.

Symmetric cryptography algorithms use the same key for encryption and decryption, while asymmetric cryptography algorithms use different keys for encryption and decryption. Additionally, symmetric cryptography algorithms have the same encryption and decryption processes, except the decryption executes in the reverse order, while asymmetric cryptography uses the same steps for encryption and decryption. Another important difference is how the key is generated. In symmetric cryptography, the key is generated, usually by pseudorandom number generator (PRNG) or some similar mechanism, while in asymmetric cryptography key is computed.

The use of cryptography for commercial purposes became more necessary by the 1970s. Many banks and financial institutions started using Data Encryption Standard (DES) to encrypt the data. However, the million-dollar question was how to share the key with their other branches and offices. Banks actually sent keys in a safe; they actually had people flying around the country every day to just distribute the key [Singh, 2000]. But this wasn’t a manageable solution. Symmetric cryptography was secure, efficient, and useful, but it needed a proper key distribution mechanism. That’s when asymmetric cryptography was born.

Asymmetric cryptography has two keys: public key and private key. The public key, as the name implies, is available for public consumption and known to everyone. The private key, on the other hand, is private to the owner of the key. The sender uses the receiver’s public key to encrypt the message. Then the encrypted message can be shared over the unsecured network. Upon receiving the message, the receiver uses his own private key to decrypt the message.

The concept of public key cryptography was first proposed by Whitfield Diffie, Martin Hellman, and Ralph Merkle in 1976 [Diffie, 1976]. Since then, asymmetric, or public key encryption, played a prominent role in the way we communicate today. You may be wondering, if asymmetric cryptography is good, why not continue using asymmetric cryptography only? Why do we need centuries-old symmetric cryptography? The answer lies in the strengths and weaknesses of asymmetric cryptography, which we’ll discuss next.

Cryptography Is All About Keeping Secrets! Although the credit for discovering public key cryptography goes to Diffie, Hellman, and Merkle, British government documents released in the late 1990s revealed that the concept of public key cryptography was first discovered by James Ellis, Clifford Cocks, and Graham Williamson in the early 1970s at the UK’s Government Communications Headquarters (GCHQ). However, it was classified information at the time, and no patent was filed or research paper could be published. After all, cryptography is all about keeping secrets [Singh, 2000]!

Properties of Asymmetric Cryptography

Symmetric cryptography provides confidentiality to the data or message, but asymmetric cryptography has many other properties that are very useful. In this section, we’ll discuss strengths, weaknesses, and use cases of asymmetric cryptography.

Let’s start with the strengths of asymmetric cryptography, as follows:

• Key distribution: Key distribution is one of the major advantages of asymmetric cryptography. Key distribution and management can quickly become a nightmare in symmetric cryptography. This problem is solved with asymmetric cryptography by using two different keys for encryption and decryption.
• Confidentiality: Another advantage of asymmetric cryptography is confidentiality. Asymmetric cryptography provides a high level of security. Not to say that symmetric ciphers aren’t secure, but asymmetric encryption algorithms, such as RSA, are very difficult to crack (i.e., until you implement Shor’s quantum algorithm). In fact, it hasn’t been cracked yet! Apart from difficult math, in asymmetric cryptography, the user’s private key is never shared. (Compare that to symmetric cryptography in which the user has to share the key for decryption, creating the possibility of compromising the key.)
• Authenticity: Asymmetric cryptography can be used for digital signatures. The sender of the message can sign the message and then encrypt the signature with his private key. The recipient of the message can decrypt the signature. This provides authenticity to the message—the receiver can confirm that the message has really come from the said person.
• Nonrepudiation: Asymmetric cryptography is used to sign the message with a digital signature, so the sender can’t deny the fact. This provides a nonrepudiation property or advantage.

Asymmetric cryptography offers many advantages over symmetric cryptography, but it isn’t a magic wand to solve all our problems. Asymmetric cryptography has the following disadvantages:

• Slow speed: One of the major disadvantages of asymmetric cryptography is the slow speed of encryption and decryption. Asymmetric cryptography takes a significantly longer time to encrypt and decrypt the data. That alone is a good enough reason to continue using symmetric cryptography.
• Resource intensive: Asymmetric cryptography is heavily based on mathematics. The computations are large and involved. This takes a lot of computing resources. This is another big negative. Plus, because of the heavy resource consumption, it can’t be used with smaller devices or at least is difficult to use with smaller devices.
• Risk of being “locked out”: If the owner of the key loses the private key, then there is no way to recover from that. The data is lost. (Not that a symmetric key can’t be lost, but because they exist in a pair, in a worst case scenario, it can be “borrowed” from the receiver.)
• Trust in public key: As we learned previously, asymmetric cryptography has the advantage of two keys and the public key can be shared openly. However, how do we trust the public key? Is there a way to validate that the public key really belongs to a particular person, or that it hasn’t been tampered with? One solution is to use certificates. However, the certificate authority (CA) must be trustworthy and, more importantly, secure.
• Key length: The major reason for the strong security of asymmetric cryptography is its large key lengths. That makes it very difficult to crack. However, this is also a drawback because the longer keys can be difficult to manage and slow down the execution.

Thanks to the wide-ranging properties of asymmetric cryptography and considering its strengths and weaknesses, it has a variety of applications and uses. Some of the key use cases are as follows:

• Symmetric key sharing: Asymmetric cryptography is used to share (or send) the symmetric key securely—without flying people around the country. In fact, it turns out that the primary use of asymmetric cryptography is to send the symmetric encryption key over the unsecured network. The process is shown in the figure below and can be summarized in the following steps:

1. 1. Person A shares his public key with everyone—Person B gets this public key.
   2. Person B encrypts the message, the symmetric key, using person A’s public key, and sends the encrypted message, the symmetric key, back to person A.
   3. Person B decrypts the message using his private key and retrieves the symmetric key (the message). Now both parties have the shared key for symmetric encryption and decryption.
   4. From this point on, the data is encrypted and decrypted using symmetric encryption. The message or data could be encrypted and decrypted using Advanced Encryption Standard (AES) or the symmetric cipher of your choice.

• Digital signature: Asymmetric cryptography is used with digital signatures in signing messages. As discussed earlier, this provides authenticity and nonrepudiation to the messages. However, the role of the private key and the public key is (sort of) reversed. The digital signature is encrypted using the private key and decrypted or verified using the public key.
• Cryptocurrency: Cryptocurrencies, like Bitcoin, use asymmetric cryptography to authenticate and authorize transactions. In fact, asymmetric cryptography makes cryptocurrency dealing very secure. The cryptocurrency transaction isn’t complete until it’s verified by both keys. Moreover, it also provides nonrepudiation so there’s no denying the transaction later.
• PKI: Asymmetric cryptography is central to the public key infrastructure (PKI). PKI allows us, through the certificates, to trust public keys and communicate, transact, and browse securely over the internet.
• Security: This is an obvious use case—the main goal of any cryptosystem is to provide confidentiality and security. Asymmetric encryption provides a very high degree of security to the data.

Symmetric cryptography is divided into two types of ciphers based on how the encryption is performed—stream ciphers and block ciphers. Asymmetric cryptography, on the other hand, is classified into three types, based on the mathematical computation used in calculating the key. Each type of symmetric cipher has a wide range of options. There are many symmetric algorithms available for use depending on the application and use case. That certainly isn’t the case with asymmetric algorithms. The three major types of cryptography algorithms are as follows:

• Factorization algorithm: As the name indicates, this algorithm is based on factorizing a very large number. One of the most widely used algorithms, RSA, uses this mechanism to encrypt and decrypt the message. This method was first proposed in the mid-1970s [US patent 4,405,829, 1977]. The patent was filed in 1977 and granted in 1983. In 2000, the algorithm was released in the public domain.
• Discrete logarithms algorithm: This class of algorithms is based on discrete logarithm math problems. The discrete logarithm algorithm, which was also proposed in the mid-1970s, is also used in the Diffie-Hellman and Elgamal encryption algorithms [Diffie, 1976] [Elgamal, 1985].
• Elliptic curve algorithm: The elliptic curve forms the third type of asymmetric algorithm. In this type, the elliptic curve is used to derive the public and private keys. This class was proposed in the mid-1980s [Koblitz, 1987] [Miller, 1985].

Other asymmetric algorithms, such as lattice-based, McEliece, and so on are also very robust but were ahead of their time. These algorithms aren’t used currently; however, they are making their way back with the looming threat of quantum computers.

Introductory Mathematics

As mentioned earlier, asymmetric cryptography is heavily based on mathematics. It’s important that we have at least a high-level understanding of some of the mathematical concepts used in asymmetric cryptography. Asymmetric cryptography primarily uses modular arithmetic, Euclidean algorithm, Extended Euclidean algorithm, Euler’s (Phi) function, and primality theorems. All of these are part of number theory. Some concepts, such as elliptic curves, are explained with the algorithm and not discussed here.

What Is Number Theory?

Number theory is the mathematics or study of positive numbers—also known as integers, whole numbers, or real numbers—and the relationship between these numbers. It starts with basic operations like addition and subtraction and moves on to higher arithmetic, modular arithmetic, the Pythagorean theorem, and the list goes on and on. Cryptography relies on number theory because it works on a finite set of positive integers.

Euclidian Algorithm

The Euclidean algorithm is a factorizing algorithm that calculates the greatest common divisor (GCD) of two prime numbers. In other words, the Euclidean algorithm calculates the largest number that divides two integers without any remainder.

The Euclidean algorithm uses the simple technique of breaking down a large difficult problem into multiple small problems. It takes two very large numbers and solves recursively for the GCD. To do so, it subtracts the smaller number from the larger number and repeats the process of subtraction until the two numbers are equal, which is the GCD. For example:

gcd(21, 35) = (35 – 21, 21) = (14, 21)

gcd(21, 14) = (21 – 14, 14) = (7, 14)

gcd(14, 7) = (14 – 7, 7) = (7, 7)

The process of subtracting can take many steps when the numbers are large, or the difference is too big between them. One way to expedite the process is by dividing the numbers or using modular arithmetic. The process reaches the end or reveals the GCD when the remainder is zero. Mathematically, the process can be written as follows:

gcd(x,y) = (y, x mod y) when y ≠ 0

If y = 0, then gcd(x,y) = x

Let’s understand with an example of finding a GCD of 21 and 35:

gcd(21, 35) = (35, 21 mod 35) = (35, 21)

gcd(35, 21) = (21, 35 mod 21) = (21, 14)

gcd(21, 14) = (14, 21 mod 14) = (14, 7)

gcd(14, 7) = (7, 14 mod 7) = (7, 0)

Another approach to find the GCD is to use the division algorithm. The division algorithm is just a different way to express the factoring problem:

x = y × q + r

Here, x and y are two integers, q is a quotient, and r is a remainder. This is known as a division algorithm because it’s derived from the basic division problem:

x/y = q + r (writing it in the form of an equation: x = y × q + r)

Let’s understand with an example of finding a GCD of 21 and 35, assigning the larger number to y (35) and the smaller number to x (21):

y = x × q + r

35 = 21 × 1 + 14

21 = 14 × 1 + 7

14 = 7 × 2 + 0

All of these approaches are considered part of the Euclidean algorithm.

Extended Euclidean Algorithm

The Extended Euclidean algorithm is used to express the GCD as a linear combination of two numbers. The formula is as follows:

gcd(x, y) = ax + by

Let’s consider an example:

gcd(284, 774) = a × 284 + b × 774

First, let’s calculate the GCD using the division formula:

gcd(284, 774)

   y = x × q + r

   774 = 284 × 2 + 206 (i)

   284 = 206 × 1 + 78   (ii)

   206 = 78 × 2 + 50     (iii)

   78 = 50 × 1 + 28       (iv)

   50 = 28 × 1 + 22       (v)

   28 = 22 × 1 + 6         (vi)

   22 = 6 × 3 + 4           (vii)

   6 = 4 × 1 + 2             (viii) gcd(284, 774)

   4 = 2 × 2 + 0

Here, we’ve solved the left side of the equation using the division algorithm, where y = 774 and x = 284.

Now, solve the right side of the Extended Euclidean algorithm for (284, 774):

gcd(284,774) = a × 284 + b × 774

                       2 = a × 284 + b × 774

                       2 = 6 – 4 × 1                                            replacing 2 with (viii) above

                       2 = 6 – 1 × (22 – 6 × 3)                            replacing 4 with (vii) above

                       2 = 4 × 6 – 1 × 22

                       2 = 4 × (28 – 1 × 22) – 1 × 22                  replacing 6 with (vi) above

                       2 = 4 × 28 – 5 × 22

                       2 = 4 × 28 – 5 × (50 – 1 × 28                   replacing 22 with (v) above

                       2 = -5 × 50 + 9 × 28

                       2 = -5 × 50 + 9 × (78 – 1 × 50)                replacing 28 with (iv) above

                       2 = -14 × 50 + 9 × 78

                       2 = -14 × (206 – 78 × 2) + 9 × 78            replacing 50 with (iii) above

                       2 = -14 × 206 – 14 × (-78 × 2) + 9 ×78

                       2 = -14 × 206 + 37 × 78                          replacing 78 with (ii) above

                       2 = -14 × 206 + 37 × (284 – 1 × 206)

                       2 = -51× 206 + 37 × 284                         replacing 284 with (i) above

                       2 = -51 × (774 – 2 × 284) + 37 × 284

                       2 = (-51) × 774 + (39) × 284                    solved for gcd

gcd(x, y) = ax + by

gcd(284, 558) = a × 284 + b × 774 can be written as:

gcd(284, 558) = (39) × 284 + (-51) × 774

Here, we’ve solved the right side of the equation by substituting the left side with the GCD value calculated previously and keep going in the reverse order to solve for a and b.

We’ll use the Extended Euclidean algorithm in calculating the modular multiplicative inverse.

Modular Multiplicative Inverse

Before learning about the modular multiplicative inverse, we should recap the multiplicative inverse. The multiplicative inverse is the number that gives the product of 1 when multiplied by the original number. We can use modular arithmetic and the Extended Euclidean algorithm to calculate the multiplicative inverse of any number. The formula is as follows, where x is the number and i is the multiplicative inverse:

x × i = 1 mod m

xi mod m = 1

For example:

35i mod 8 = 1

Let’s find the multiplicative inverse of 35 with respect to mod 8:

gcd = (x, y) = gcd(35, 8) = gcd(8, 35)

                                   y = xq + r

                                   35 = 8 × 4 + 3

                                   8 = 3 × 2 + 2

                                   3 = 2 × 1 + 1 → The gcd

The GCD of these two numbers must be 1; otherwise, x doesn’t have a modular multiplicative inverse.

Now, let’s apply the Extended Euclidean algorithm to find the multiplicative inverse:

gcd(8, 35) = ax + by = a × 8 + b × 35

            1 = 3 – 2 × 1

            1 = 3 – 1 × (8 – 3 × 2) = -8 + 3 × 3

            1 = -8 + 3 × (35 – 8 × 4) = -8 × 13 + 3 × 35 = -104 + 105

Finally, substitute the values of x, m, and i in the modular multiplicative equation:

35i mod 8 =1

35 × 3 mod 8 =1

105 mod 8 = 1

The modular multiplicative inverse of 35 with respect to mod 8 is 3.

Chinese Remainder Theorem

The decryption process in RSA cryptography is made faster by using the Chinese remainder theorem. In a nutshell, the Chinese remainder theorem can be explained as if N = n1, n2, n3, where all n are coprimes, then we can calculate x mod N from x mod n1, x mod n2, and x mod n3. For example, if n₁, n₂, and n₃ are 3, 5, and 7, then N = 3 × 5 × 7 = 105.

The value of x mod N (i.e., x mod 105) can be calculated using x mod 3, x mod 5, and x mod 7.

It’s Prime Time! First, a quick refresher: a number is considered a prime number if it’s divided by 1 and itself—without any remainder. The rest of the numbers are known as composite numbers. The largest prime number has 24,682.048 digits [GIMPS, 2018]! The GCD of two prime numbers is always 1. If p and q are any prime numbers, then the GCD of p and q is always 1, as follows:

gcd(p,q) = 1 if p and q are prime numbers

However, the reverse isn’t true—meaning two numbers whose GCD is 1 don’t have to be prime numbers. And that leads us to the definition of coprime.

The numbers are said to be coprime when numbers don’t have any common factor between them other than 1. Needless to say, all prime numbers are coprime since 1 is the only common factor, however, the definition of coprime is applicable to composite numbers also. For example, 24 and 35 are coprime since the only common factor between them is 1; that is, GCD is 1. And, yes, you guessed it right—1 is coprime to every number!

There are mathematical ways to check if the number is a prime number; these methods or tests are called primality tests.

Euler’s Totient

Euler’s totient or Euler’s phi (ϕ) function is another very useful mathematical concept in asymmetric cryptography. Euler’s totient, ϕ(n), gives the number between 1 and n, which are coprime with n. For example:

ϕ(n) = ϕ(9) = {1,2,3,4,5,6,7,8,9} = {1,2,4,5,7,8} = 6, i.e., ϕ(9) = 6

In this example, n is 9. The function ϕ gives all the coprime numbers with 9. The example shows, there are six numbers—1,2,4,5,7,8—that are coprimes with 9.

However, Euler goes a step further and makes our lives easy by stating that, if p and q are prime numbers, then we can find n as follows: ϕ(n) = (p − 1)(q − 1).

Let’s consider an example where p = 3 and q = 3:

ϕ(n) = (p − 1)(q − 1)

        = (3 − 1)(3 − 1) = 2 × 2 = 4

In this example, we’re substituting the values of p and q to find the value of ϕ(n). This property of Euler’s function is also used in RSA key generation.

This can formerly be defined as, if p is a prime number, then gcd of (p,q) is 1 (see the box on prime numbers) and ϕ(p) = p − 1 as long as 0 < q < p.

Another useful property of Euler’s function is ϕ(p×q) = ϕ(p) × ϕ(q), where p and q are coprime.

The ϕ of a product is equal to the ϕ of two prime multipliers used in the product. For example:

ϕ(p) = ϕ(3) = 3 − 1 = 2. ϕ(q) = ϕ(5) = 5 − 1 = 4. ϕ(5) × ϕ(3) = 4 × 2 = 8

ϕ(p×q) = ϕ(15) = {1,2,4,7,8,11,13,14} = 8

Substitute the values of p and q. The example proves that the product of ϕ(p) and ϕ(q) gives the same result as ϕ(pq).

The last property of Euler states that if p is a prime number and k is greater than zero, then:

p^k = p^k – p^{(k – 1)}

For example, if p = 2 and k = 3, then

2³ = 2³ − 2^{(3 – 1)} = 8 – 4 = 4

Here, we’ve substituted the values of p and k in the preceding equation.

Is Modern Cryptography Still in 300 BC? Most of the mathematics used in asymmetric cryptography was first discovered/proposed a very long time ago. For example, modular arithmetic, Euclidean algorithm, prime numbers, and Euler’s function all were initially conceptualized around 300 BC. Just because the concept is around for so long, it doesn’t make it easy to solve! That’s why modern cryptography uses these concepts.

Editor’s note: This post has been adapted from a section of the book Modern Cryptography: The Practical Guide by Sandip Dholakia.