Information Security

Public-Key Cryptography

17 minute read

Notice a tyop typo? Please submit an issue or open a PR.

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 MM, x+y(modM)x + y \pmod M is equal to the remainder of (x+y)รทM(x + y) \div M. For example, 2+8(mod10)=02 + 8 \pmod{10} = 0, because 10รท1010 \div 10 divides evenly whereas 3+8(mod10)=13 + 8 \pmod {10} = 1 because 11รท1011 \div 10 yields a remainder of 11.

In modular addition, a number kk has an inverse kโ€ฒk' such that k+kโ€ฒ(modM)=0k + k' \pmod M = 0. For example, for M=10M = 10 and k=2k = 2, kโ€ฒ=8k' = 8 because 2+8(mod10)=02 + 8 \pmod{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(modM)c = a + b \pmod M, a=c+bโ€ฒ(modM)a = c + b' \pmod M and b=c+aโ€ฒ(modM)b = c + a' \pmod 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=3p = 3, key k=2k = 2 and encryption algorithm p+k(mod10)p + k \pmod{10}. Thus, ciphertext c=3+2(mod10)=5(mod10)=5c = 3 + 2 \pmod{10} = 5 \pmod{10} = 5. We can decrypt cc using the inverse of kk: kโ€ฒk'. Since kโ€ฒ=8k' = 8, c+kโ€ฒ(mod10)=5+8(mod10)=13(mod10)=3=pc + k' \pmod{10} = 5 + 8 \pmod{10} = 13 \pmod{10} = 3 = p.

Additive Inverse Quiz

Additive Inverse Quiz Solution

In modular addition, a number kk has an inverse kโ€ฒk' such that k+kโ€ฒ(modM)=0k + k' \pmod M = 0. In this case, M=20M = 20 and k=8k = 8. Therefore, kโ€ฒ=12k' = 12 because 8+12(mod20)=08 + 12 \pmod{20} = 0.

Modular Multiplication

Given a modulus MM, xโˆ—y(modM)x * y \pmod M is equal to the remainder of (xโˆ—y)รทM(x * y) \div M. For example, 5โˆ—8(mod10)=05 * 8 \pmod{10} = 0, because 40รท1040 \div 10 divides evenly whereas 4โˆ—8(mod10)=24 * 8 \pmod{10} = 2 because 32รท1032 \div 10 yields a remainder of 2.

In modular multiplication, a number kk , has an inverse kโ€ฒk' such that kโˆ—kโ€ฒ(modM)=1k * k' \pmod M = 1. For example, for M=10M = 10 and k=3k = 3, kโ€ฒ=7k' = 7 because 3โˆ—7(mod10)=21(mod10)=13 * 7 \pmod{10} = 21 \pmod{10} = 1.

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

Modular Multiplication Quiz

Modular Multiplication Quiz Solution

In modular multiplication, a number kk has an inverse kโ€ฒk' such that kโˆ—kโ€ฒ(modM)=1k * k' \pmod M = 1. In this case, M=17M = 17 and k=3k = 3. Therefore, kโ€ฒ=6k' = 6 because 3โˆ—6(mod17)=18(mod17)=13 * 6 \pmod{17} = 18 \pmod{17} = 1.

Totient Function

Given a modulus MM, only the numbers that are relatively prime to MM have multiplicative inverses in (modM)\pmod M.

Two numbers xx and yy 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 nn, we can calculate how many integers are relatively prime to nn using the totient function ฯ•(n)\phi(n). If nn is prime, ฯ•(n)=nโˆ’1\phi(n) = n - 1, because every number smaller than nn is relatively prime to nn because nn itself is prime. If n=pโˆ—qn = p * q and pp and qq are prime, then ฯ•(n)=(pโˆ’1)โˆ—(qโˆ’1)\phi(n) = (p - 1) * (q - 1). If n=pโˆ—qn = p * q and pp and qq are relatively prime, ฯ•(n)=ฯ•(p)โˆ—ฯ•(q)\phi(n) = \phi(p) * \phi(q).

Totient Quiz

Totient Quiz Solution

If n=pโˆ—qn = p * q and pp and qq are prime, then ฯ•(n)=(pโˆ’1)โˆ—(qโˆ’1)\phi(n) = (p - 1) * (q - 1). For n=21n = 21, p=3p = 3 and q=7q = 7, ฯ•(n)=(3โˆ’1)โˆ—(7โˆ’1)=2โˆ—6=12\phi(n) = (3 - 1) * (7 - 1) = 2 * 6 = 12.

Modular Exponentiation

In modular exponentiation, xy(modn)=xy(modฯ•(n))(modn)x^y \pmod n = x^{y \pmod{\phi(n)}} \pmod n. If y=1(modฯ•(n))y = 1 \pmod{\phi(n)}, then xy(modn)=x(modn)x^y \pmod n = x \pmod n.

Modular Exponentiation Quiz

Modular Exponentiation Quiz Solution

We know that xy(modn)=xy(modฯ•(n))(modn)x^y \pmod n = x^{y \pmod{\phi(n)}} \pmod n. For x=7x = 7, y=27y = 27 and n=30n = 30, 727(mod30)=727(modฯ•(30))(mod30)7^{27} \pmod{30} = 7^{27 \pmod{\phi(30)}} \pmod{30}. We can calculate ฯ•(30)\phi(30) as follows: ฯ•(30)=ฯ•(3)โˆ—ฯ•(10)=ฯ•(3)โˆ—ฯ•(2)โˆ—ฯ•(5)=2โˆ—1โˆ—4=8\phi(30) = \phi(3) * \phi(10) = \phi(3) * \phi(2) * \phi(5) = 2 * 1 * 4 = 8. Thus, 727(mod30)=727(mod8)(mod30)7^{27} \pmod{30} = 7^{27 \pmod 8} \pmod{30}. If we divide 27 by 8, we are left with a remainder of 3, so 727(mod30)=73(mod30)7^{27} \pmod{30} = 7^3 \pmod{30}. 73=3437^3 = 343, which yields a remainder of 13 when divided by 30.

RSA (Rivest, Shamir, Adleman)

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 pp and qq that are at least 512 bits in size. Next, we compute n=pโˆ—qn = p * q, and ฯ•(n)=(pโˆ’1)โˆ—(qโˆ’1)\phi(n) = (p - 1) * (q - 1). Then, we select an integer ee that is smaller than ฯ•(n)\phi(n) and relatively prime to ฯ•(n)\phi(n). Finally, we calculate dd: the multiplicative inverse of ee, (modฯ•(n))\pmod{\phi(n)}.

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

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

RSA guarantees that only Alice can decrypt mm 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 ss for a message mm, Alice uses her private key, d,n{d, n} to compute md(modn)m^d \pmod n. Bob can verify Alice's signature by using her public key, e,n{e, n} to compute se(modn)s^e \pmod n, which is equivalent to the original message mm.

Why Does RSA Work

Remember from the rules of modular exponentiation that, for a base xx, a power yy, a modulus nn, xy(modn)=xy(modฯ•(n))(modn)x^y \pmod n = x^{y \pmod{\phi(n)}} \pmod n. If y=1(modฯ•(n))y = 1 \pmod{\phi(n)}, then xy(modn)=x(modn)x^y \pmod n = x \pmod n.

Also recall that, for a given public key, e,n{e, n} and its private key d,n{d, n}, dโˆ—e=1(modฯ•(n))d * e = 1 \pmod{\phi(n)}. Thus, xeโˆ—d(modn)=x(modn)x^{e * d} \pmod n = x \pmod n.

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

Here is an example of RSA in action.

The key generation step proceeds as follows. First, we select two prime numbers, p=17p = 17 and q=11q = 11. From these values, we can compute nn and ฯ•(n)\phi(n), as pโˆ—q=187p * q = 187 and (pโˆ’1)โˆ—(qโˆ’1)=160(p - 1) * (q - 1) = 160, respectively. We select 7 as our public key ee, as 7 and 160 are relatively prime. The private key is the multiplicative inverse of ee, (modฯ•(n))\pmod{\phi(n)}. The multiplicative inverse of 7(mod160)7 \pmod{160} is 23, which is our private key dd.

To encrypt a plaintext m=88m = 88, we compute ciphertext C=me(modn)=887(mod187)=11C = m^e \pmod n = 88^7 \pmod{187} = 11. To decrypt CC, we perform Cd(modn)=1123(mod187)=88C^d \pmod n = 11^{23} \pmod{187} = 88, which returns mm.

RSA Quiz

RSA Quiz Solution

n=pโˆ—q=11โˆ—3=33n = p * q = 11 * 3 = 33 and ฯ•(n)=(pโˆ’1)โˆ—(qโˆ’1)=2โˆ—10=20\phi(n) = (p - 1) * (q - 1) = 2 * 10 = 20. ee and dd must be multiplicative inverses (modฯ•(n))\pmod{\phi(n)}, so for e=7e = 7, d=3d = 3, since 21(mod20)=121 \pmod{20} = 1. Finally, public key e,n{e, n} is equal to 7,33{7, 33}, and private key, d,n{d, n} is equal to 3,33{3, 33}.

RSA Encryption Quiz

RSA Encryption Quiz Solution

Encrypting message mm involves computing me(modn)m^e \pmod n, which is equivalent to 27(mod33)=128(mod33)=292^7 \pmod{33} = 128 \pmod{33} = 29. Decrypting ciphertext CC involves computing Cd(modn)C^d \pmod n, which is equivalent to 293(mod33)=24389(mod33)=329^3 \pmod{33} = 24389 \pmod{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{e, n}, an efficient factorization of nn into pp and qq allows an attacker to compute ฯ•(n)\phi(n) and the multiplicative inverse of ee, (modฯ•(n))\pmod{\phi(n)}. This inverse is dd, 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=me(modn)c = m^e \pmod n using Alice's public key, e,n{e, n}. The attacker intercepts cc and performs the transformation cโ€ฒ=seโˆ—cc' = s^e * c. When Alice receives this ciphertext, the decrypted result is mโ€ฒ=sโˆ—mm' = s * m.

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

RSA in Practice Quiz

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 qq and ฮฑ\alpha. qq is a large prime number - at least 300 digits long - and ฮฑ\alpha is a small primitive root of qq.

Suppose two users AA and BB wish to exchange a key using Diffie-Hellman. AA selects a random integer XA<qX_A < q and computes YA=ฮฑXA(modq)Y_A = \alpha^{X_A} \pmod q. Likewise, BB selects a random integer XB<qX_B < q and then computes YB=ฮฑXB(modq)Y_B = \alpha^{X_B} \pmod q. Each side keeps its Xโˆ—X_* value private and sends their Yโˆ—Y_* value to the other side.

Upon receiving YBY_B from BB, AA computes the key k=YBXA(modq)k = {Y_B}^{X_A} \pmod q. Similarly, BB computes the key k=YAXB(modq)k = {Y_A}^{X_B} \pmod q upon receiving YAY_A from AA. The expressions used to compute kk by each party are equivalent; that is, YBXA(modq)=YAXB(modq){Y_B}^{X_A} \pmod q = {Y_A}^{X_B} \pmod q. As a result of this exchange, both sides now share a secret encryption key.

The values of XAX_A and XBX_B are private while ฮฑ\alpha, qq, YAY_A, and YBY_B are public. If an attacker CC wants to compute the shared key, they must first compute either XBX_B or XAX_A. The attacker can compute XBX_B, for example, by computing dlog(ฮฑ,q)(YB)dlog(\alpha,q)(Y_B), where dlogdlog is the discrete logarithm. If CC can retrieve XBX_B, they can compute the shared key using YAY_A and qq.

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

Diffie-Hellman Example

Let's walk through the Diffie-Hellman key exchange using q=353q = 353 and ฮฑ=3\alpha = 3.

First, user AA selects a random number, XA<q=97X_A < q = 97, which they keep secret, and they compute YA=397(mod353)=40Y_A = 3^{97} \pmod{353} = 40. Similarly, user BB selects a random number XB<q=233X_B < q = 233, which they also keep secret, and they compute YB=3233(mod353)=248Y_B = 3^{233} \pmod{353} = 248. Next, AA sends 40 to BB and BB sends 248 to AA.

Upon receiving YAY_A, BB computes k=YAXB(mod353)=40233(mod353)=160k = {Y_A}^{X_B} \pmod{353} = 40^{233} \pmod{353} = 160. Similarly, AA computes k=YBXA(mod353)=24897(mod353)=160k = {Y_B}^{X_A} \pmod{353} = 248^{97} \pmod{353} = 160. Through this exchange, both AA and BB have computed the same secret value, which they can now use to encrypt their communications.

We assume that an attacker can access YAY_A, YBY_B, qq, and ฮฑ\alpha. Because the numbers in this example are quite small, an attacker can feasibly compute the discrete log to retrieve either XBX_B or XAX_A. However, as we said before, this computation becomes infeasible for the large values of qq used in practice.

Diffie-Hellman Quiz

Diffie-Hellman Quiz Solution

Alice sends ฮฑa(modq)\alpha^a \pmod q to Bob, which is equivalent to 56(mod23)=85^6 \pmod{23} = 8. Bob sends ฮฑb(modq)\alpha^b \pmod q to Alice, which is equivalent to 515(mod23)=195^{15} \pmod{23} = 19.

Diffie-Hellman Security

In Diffie-Hellman, neither party ever transmits the shared secret encryption key SS, nor the locally generated secrets XAX_A and XBX_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 YAY_A, YBY_B, qq, and ฮฑ\alpha, since these values are transmitted. The value of local secret XAX_A is equal to the discrete logarithm dlog(ฮฑ,q)(YA)dlog(\alpha,q)(Y_A). The security assumption in Diffie-Hellman is that finding the discrete logarithm is infeasible given a very large, prime qq.

Of course, if this conjecture is not valid, then an adversary knowing YAY_A, qq, and ฮฑ\alpha can easily compute XAX_A. With XAX_A in hand, they can compute SS and effectively eavesdrop on communication between AA and BB.

Diffie-Hellman Limitations

Suppose that Alice tells Bob to use Diffie-Hellman. The first thing that Bob has to do is compute YBY_B from his local secret XBX_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 YAY_A that Alice sends to Bob, and instead sends her own YXY_X to Bob, fooling Bob to accept this as YAY_A. Likewise, Trudy intercepts YBY_B that Bob sends to Alice and instead sends her own YXY_X to Alice, fooling Alice to believe that YXY_X is actually YBY_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 YAY_A when she sends it to Bob. Bob can verify that YAY_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

RSA, Diffie-Hellman Quiz Solution

OMSCS Notes is made with in NYC by Matt Schlenker.

Copyright ยฉ 2019-2021. All rights reserved.

privacy policy