# Public-Key Cryptography

## Modular Arithmetic

Both RSA and Diffie-Hellman - the most widely-used public-key algorithms - are based on number theory and use modular arithmetic - modular addition, multiplication, and exponentiation. Before we dive into the details of the algorithms themselves, let’s review the basics of modular arithmetic.

Given a modulus M, x + y mod M is equal to the remainder of (x + y) / M. For example, 2 + 8 mod 10 = 0, because 10 / 10 divides evenly whereas 3 + 8 mod 10 = 1 because 11 / 10 yields a remainder of 1.

In modular addition, a number k has an inverse k' such that k + k’ mod M = 0. For example, for M = 10 and k = 2, k’ = 8 because 2 + 8 mod 10 = 0. Every number has an inverse under modular addition.

The presence of an additive inverse means that modular addition is reversible. That is, given c = a + b mod M, a = c + b' mod M and b = c + a' mod M . This reversibility is very convenient for encryption because we want the decryption process ideally to be the reverse of the encryption process.

Suppose we have plaintext p = 3, key k = 2 and encryption algorithm p + k mod 10. Thus, ciphertext c = 3 + 2 mod 10 = 5 mod 10 = 5. We can decrypt c using the inverse of k: k’. Since k' = 8, c + k’ mod 10 = 5 + 8 mod 10 = 13 mod 10 = 3 = p.

In modular addition, a number k has an inverse k' such that k + k' mod M = 0. In this case, M = 20 and k = 8. Therefore, k' = 12 because 8 + 12 mod 20 = 0.

## Modular Multiplication

Given a modulus M, x * y mod M is equal to the remainder of (x * y) / M. For example, 5 * 8 mod 10 = 0, because 40 / 10 divides evenly whereas 4 * 8 mod 10 = 2 because 32 / 10 yields a remainder of 2.

In modular multiplication, a number k , has an inverse k' such that k * k’ mod M = 1. For example, for M = 10 and k = 3, k’ = 7 because 3 * 7 mod 10 = 21 mod 10 = 1.

Not all numbers have multiplicative inverses for a given M. For M = 10, for example, 2, 5, 6, and 8 do not have multiplicative inverses.

## Modular Multiplication Quiz Solution

In modular multiplication, a number k has an inverse k' such that k * k' mod M = 1. In this case, M = 17 and k = 3. Therefore, k' = 6 because 3 * 6 mod 17 = 18 mod 17 = 1.

## Totient Function

Given a modulus M, only the numbers that are relatively prime to M have multiplicative inverses in mod M.

Two numbers x and y are relatively prime to one another if they share no common factor other than 1. For example, 3 and 10 are relatively prime, whereas 2 and 10 - which share 2 as a common factor - are not.

Given n, we can calculate how many integers are relatively prime to n using the totient function φ(n). If n is prime, φ(n) = n - 1, because every number smaller than n is relatively prime to n because n itself is prime. If n = p * q and p and q are prime, then φ(n) = (p - 1) * (q - 1). If n = p * q and p and q are relatively prime, φ(n) = φ(p) * φ(q).

## Totient Quiz Solution

If n = p * q and p and q are prime, then φ(n) = (p - 1) * (q - 1). For n = 21, p = 3 and q = 7, φ(n) = (3 - 1) * (7 - 1) = 2 * 6 = 12.

## Modular Exponentiation

In modular exponentiation, x^y mod n = x^(y mod φ(n)) mod n. If y = 1 mod φ(n), then x^y mod n = x mod n.

## Modular Exponentiation Quiz Solution

We know that x^y mod n = x^(y mod φ(n)) mod n. For x = 7, y = 27 and n = 30, 7^27 mod 30 = 7^(27 mod φ(30)) mod 30. We can calculate φ(30) as follows: φ(30) = φ(3) * φ(10) = φ(3) * φ(2) * φ(5) = 2 * 1 * 4 = 8. Thus, 7^27 mod 30 = 7^(27 mod 8) mod 30. If we divide 27 by 8, we are left with a remainder of 3, so 7^27 mod 30 = 7^3 mod 30. 7^3 = 343, which yields a remainder of 13 when divided by 30.

RSA - named after its three creators - is the most widely used public-key algorithm. RSA supports both public-key encryption and digital signature.

RSA bases the strength of its security on the hypothesis that factoring a massive number into two primes is computationally infeasible problem to solve on a reasonable timescale using modern computers.

RSA supports variable key lengths, and in practice, most people use a 1024-, 2048-, or 4096-bit key. The plaintext block size can also be variable, but the value of the block - represented as a binary integer - must be smaller than the value of the key. The length of the ciphertext block is the same is the key length.

Here is a summary of RSA, including the key generation, encryption, and decryption steps.

The first step is key generation. First, we select two primes p and q that are at least 512 bits in size. Next, we compute n = p * q, and φ(n) = (p - 1) * (q - 1). Then, we select an integer e that is smaller than φ(n) and relatively prime to φ(n). Finally, we calculate d: the multiplicative inverse of e, mod φ(n).

The public key is {e, n}. The private key is {d, n}.

Suppose Bob wishes to send a message m to Alice that only she can read. Bob can encrypt m using Alice’s public key, {e, n} by computing m^e (mod n). On receipt of ciphertext C, Alice can use her private key, {d, n}, and compute C^d (mod n) to recover m.

RSA guarantees that only Alice can decrypt m because only she has the private key that pairs with the public key used to encrypt the message.

Digital signature creation and verification work in a similar fashion as encryption and decryption.

To create a signature s for a message m, Alice uses her private key, {d, n} to compute m^d mod n. Bob can verify Alice’s signature by using her public key, {e, n} to compute s^e mod n, which is equivalent to the original message m.

## Why Does RSA Work

Remember from the rules of modular exponentiation that, for a base x, a power y, a modulus n, x^y mod n = x^(y mod φ(n)) mod n. If y = 1 mod φ(n), then x^y mod n = x mod n.

Also recall that, for a given public key, {e, n} and its private key {d, n}, d * e = 1 mod φ(n). Thus, x^(e * d) mod n = x mod n.

To encrypt a message m, we compute c = m^e mod n. To decrypt c, we compute m = c^d mod n. We can substitute the first expression in for c in the second to get m = (m^e mod n)^d mod n. The right-hand side of the equation simplifies to m^(ed) mod n, which is equivalent to m mod n, which equals m since m < n.

Here is an example of RSA in action.

The key generation step proceeds as follows. First, we select two prime numbers, p = 17 and q = 11. From these values, we can compute n and φ(n), as p * q = 187 and (p - 1) * (q - 1) = 160, respectively. We select 7 as our public key e, as 7 and 160 are relatively prime. The private key is the multiplicative inverse of e, mod φ(n). The multiplicative inverse of 7 mod 160 is 23, which is our private key d.

To encrypt a plaintext m = 88, we compute ciphertext C = m^e mod n = 88^7 mod 187 = 11. To decrypt C, we perform C^d mod n = 11^23 mod 187 = 88, which returns m.

## RSA Quiz Solution

n = p * q = 11 * 3 = 33 and φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20. e and d must be multiplicative inverses mod φ(n), so for e = 7, d = 3, since 21 mod 20 = 1. Finally, public key {e, n} is equal to {7, 33}, and private key, {d, n} is equal to {3, 33}.

## RSA Encryption Quiz Solution

Encrypting message m involves computing m^e mod n, which is equivalent to 2^7 mod 33 = 128 mod 33 = 29. Decrypting ciphertext C involves computing C^d mod n, which is equivalent to 29^3 mod 33 = 24389 mod 33 = 3

## Why is RSA Secure?

RSA bases its security on the hypothesis that factoring a very large number - at least 512 bits, but often in the range of 1024-4096 bits - takes an inordinately long amount of time using modern computers.

If someone finds an efficient way to factor a large number into primes, then the security of RSA is effectively broken. Given public key, {e, n}, an efficient factorization of n into p and q allows an attacker to compute φ(n) and the multiplicative inverse of e, mod φ(n). This inverse is d, the private key.

An attacker can read confidential messages and forge digital signatures against any public key if they can compute a private key in a reasonable amount of time.

## Issues with Schoolbook RSA

One issue with RSA is that the algorithm is deterministic. For a given key, the same plaintext message always encrypts to the same ciphertext. Additionally, for specific plaintext values such as 0, 1, or -1, the ciphertext is always equivalent to the plaintext, regardless of the key used.

Another issue is that RSA is malleable. An attacker can induce predictable transformations in plaintext by modifying ciphertext in specific ways.

For example, suppose Bob sends Alice an encrypted message c = m^e mod n using Alice’s public key, {e, n}. The attacker intercepts c and performs the transformation c' = s^e * c. When Alice receives this ciphertext, the decrypted result is m' = s * m.

In practice, the standard is to prepend m with padding, a step which addresses the issues described above.

## RSA in Practice Quiz Solution

Always use standard libraries, as they have been reviewed and tested by experts in the field.

## Diffie and Hellman Key Exchange

In the Diffie-Hellman key exchange algorithm, there are two publicly known numbers q and α. q is a large prime number - at least 300 digits long - and α is a small primitive root of q.

Suppose two users A and B wish to exchange a key using Diffie-Hellman. A selects a random integer X_A < q and computes Y_A = α^X_A mod q. Likewise, B selects a random integer X_B < q and then computes Y_B = α^X_B mod q. Each side keeps its X_* value private and sends their Y_* value to the other side.

Upon receiving Y_B from B, A computes the key k = Y_B^X_A mod q. Similarly, B computes the key k = Y_A^X_B mod q upon receiving Y_A from A. The expressions used to compute k by each party are equivalent; that is, Y_B^X_A mod q = Y_A^X_B mod q. As a result of this exchange, both sides now share a secret encryption key.

The values of X_A and X_B are private while α, q, Y_A, and Y_B are public. If an attacker C wants to compute the shared key, they must first compute either X_B or X_A. The attacker can compute X_B, for example, by computing dlog(α,q)(Y_B), where dlog is the discrete logarithm. If C can retrieve X_B, they can compute the shared key using Y_A and q.

The security of Diffie-Hellman lies in the fact that it is infeasible to compute discrete logarithms for large primes such as q using modern computers.

## Diffie-Hellman Example

Let’s walk through the Diffie-Hellman key exchange using q = 353 and α = 3.

First, user A selects a random number, X_A < q = 97, which they keep secret, and they compute Y_A = 3^97 mod 353 = 40. Similarly, user B selects a random number X_B < q = 233, which they also keep secret, and they compute Y_B = 3^233 mod 353 = 248. Next, A sends 40 to B and B sends 248 to A.

Upon receiving Y_A, B computes k = Y_A^X_B mod 353 = 40^233 mod 353 = 160. Similarly, A computes k = Y_B^X_A mod 353 = 248^97 mod 353 = 160. Through this exchange, both A and B have computed the same secret value, which they can now use to encrypt their communications.

We assume that an attacker can access Y_A, Y_B, q, and α. Because the numbers in this example are quite small, an attacker can feasibly compute the discrete log to retrieve either X_B or X_A. However, as we said before, this computation becomes infeasible for the large values of q used in practice.

## Diffie-Hellman Quiz Solution

Alice sends α^a mod q to Bob, which is equivalent to 5^6 mod 23 = 8. Bob sends α^b mod q to Alice, which is equivalent to 5^15 mod 23 = 19.

## Diffie-Hellman Security

In Diffie-Hellman, neither party ever transmits the shared secret encryption key S, nor the locally generated secrets X_A and X_B. Since we assume that attackers can intercept any transmitted value, the lack of transmission of secret values adds to the security of the scheme.

We assume that an attacker can access Y_A, Y_B, q, and α, since these values are transmitted. The value of local secret X_A is equal to the discrete logarithm dlog(α,q)(Y_A). The security assumption in Diffie-Hellman is that finding the discrete logarithm is infeasible given a very large, prime q.

Of course, if this conjecture is not valid, then an adversary knowing Y_A, q, and α can easily compute X_A. With X_A in hand, they can compute S and effectively eavesdrop on communication between A and B.Let’s walk through the Diffie-Hellman key exchange using q = 353 and α = 3.

## Diffie-Hellman Limitations

Suppose that Alice tells Bob to use Diffie-Hellman. The first thing that Bob has to do is compute Y_B from his local secret X_B, and this computation involves a very CPU-intensive exponentiation calculation.

If Alice is a malicious attacker, and Bob is a server, then Alice can request multiple simultaneous Diffie-Hellman sessions with Bob. These requests would cause Bob to waste many CPU cycles on exponentiation, which can result in denial of service.

Additionally, the sole purpose of Diffie-Hellman is key exchange. Unlike RSA, it does not offer encryption and cannot produce digital signatures.

## Bucket Brigade Attack, Man in the Middle (MIM)

The biggest threat to the Diffie-Hellman key exchange is the bucket brigade attack, which is a type of man-in-the-middle attack.

In this attack, Trudy intercepts the message Y_A that Alice sends to Bob, and instead sends her own Y_X to Bob, fooling Bob to accept this as Y_A. Likewise, Trudy intercepts Y_B that Bob sends to Alice and instead sends her own Y_X to Alice, fooling Alice to believe that Y_X is actually Y_B.

The result is that the shared key that Alice computes is the shared key between Alice and Trudy. Similarly, the shared key that Bob computes is the shared key between him and Trudy. In other words, Trudy plays Bob to Alice and Alice to Bob.

This man-in-the-middle attack is possible because the Diffie-Hellman key exchange protocol does not authenticate Alice or Bob. There is no way for Alice to know that the message that she has received is from Bob, and vice versa.

There are several ways to fix this problem. For example, everyone can publish their public key to a trusted, public repository instead of sending it and risking interception and forgery.

Alternatively, if Alice has already published her RSA public key, she can sign Y_A when she sends it to Bob. Bob can verify that Y_A is really from Alice using her RSA public key.

## Other Public Key Algorithms

The Digital Signature Standard (DSS) is based on the secure hash function SHA-1. This algorithm is only used for digital signature, not encryption or key exchange.

While RSA is the most widely used public-key algorithm for encryption and digital signature, a competing system known as Elliptic-Curve Cryptography (ECC), has recently begun to challenge RSA. The main advantage of ECC over RSA is that it offers the same security with a far smaller bit size.

On the other hand, RSA has been subject to a lot of cryptanalysis work over the years. For ECC, the cryptanalysis work is still just beginning; therefore, we are not as confident in ECC as we are in RSA.

## RSA, Diffie-Hellman Quiz Solution

OMSCS Notes is made with in NYC by Matt Schlenker.