The RSA Algorithm

Get access to whole semester resourcesSemester Pass

Chapter Thirty-Five

Syllabus topic Module 1, "Public-Key Cryptography and RSA: The RSA Algorithm"

Pages 208 to 214 of 678

In one line

Pick two large primes, multiply them, choose a public exponent, and invert it modulo the totient. Encryption is raising to the public exponent modulo the product; decryption is raising to the private one.

In the wording a student can write in an examination: the RSA algorithm, published by Ron Rivest, Adi Shamir and Leonard Adleman in 1978, is a block cipher in which plaintext and ciphertext are integers between 0 and n - 1 for some modulus n. Key generation: choose two distinct large primes p and q; compute n = pq and phi(n) = (p - 1)(q - 1); select e with 1 < e < phi(n) and gcd(e, phi(n)) = 1; compute d as the inverse of e modulo phi(n). The public key is the pair {e, n} and the private key is {d, n}. Then

C = M to the power e mod n

M = C to the power d mod n

Key generation, step by step

Step 1: choose p and q. Two distinct primes, each about half the length of the intended modulus. For a 2,048-bit key that is two 1,024-bit primes, found by the method of the primality chapter: pick a random odd number of the right size and test it until one is prime.

Step 2: compute n and phi(n). n is pq, and phi(n) is (p - 1)(q - 1).

Step 3: choose e. Any value with 1 < e < phi(n) and gcd(e, phi(n)) equal to 1. In practice e is almost always 65537, for two reasons: it is prime, so the gcd condition is satisfied unless phi(n) happens to be a multiple of it; and in binary it is 10000000000000001, only two one bits, so the public operation is cheap.

Step 4: compute d. The inverse of e modulo phi(n), by the extended Euclidean algorithm of the arithmetic chapter.

Step 5: publish {e, n} and keep {d, n}, and destroy nothing of p and q that you need. A real implementation keeps p, q, and a few derived values, because decryption through the Chinese Remainder Theorem needs them.

And throw away nothing else that matters, but do throw away phi(n) from anywhere public. Anybody who learns phi(n) can compute d from e at once, so phi(n) is as secret as p and q.

The algorithm, run

# RSA, end to end, on numbers a student can check, and then on a real key size.

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

def modinv(a, m):
    g, x, _ = egcd(a % m, m)
    return None if g != 1 else x % m

def keygen(p, q, e):
    n, phi = p * q, (p - 1) * (q - 1)
    g, _, _ = egcd(e, phi)
    if g != 1:
        raise ValueError("e = %d shares a factor with phi(n) = %d" % (e, phi))
    return {"p": p, "q": q, "n": n, "phi": phi, "e": e, "d": modinv(e, phi)}

k = keygen(17, 11, 7)
print("the standard worked example")
print("   p = %d, q = %d" % (k["p"], k["q"]))
print("   n = p * q            = %d" % k["n"])
print("   phi(n) = (p-1)(q-1)  = %d" % k["phi"])
print("   e chosen coprime to phi(n) = %d" % k["e"])
print("   d = inverse of e mod phi(n) = %d, and e*d mod phi(n) = %d"
      % (k["d"], k["e"] * k["d"] % k["phi"]))
print("   public key  {e, n} = {%d, %d}" % (k["e"], k["n"]))
print("   private key {d, n} = {%d, %d}" % (k["d"], k["n"]))
print()

M = 88
C = pow(M, k["e"], k["n"])
print("encrypt M = %d:" % M)
print("   C = M to the power e mod n = %d to the power %d mod %d = %d"
      % (M, k["e"], k["n"], C))
print("decrypt:")
print("   M = C to the power d mod n = %d to the power %d mod %d = %d"
      % (C, k["d"], k["n"], pow(C, k["d"], k["n"])))
print()

print("every message from 0 to n-1 encrypts and decrypts back:")
bad = [m for m in range(k["n"]) if pow(pow(m, k["e"], k["n"]), k["d"], k["n"]) != m]
print("   messages that fail:", len(bad), "of", k["n"])
print("   including the ones NOT coprime to n, which Euler's theorem alone")
print("   does not cover:", [m for m in (11, 17, 22, 34) if m < k["n"]],
      "all recover:", all(pow(pow(m, k["e"], k["n"]), k["d"], k["n"]) == m
                          for m in (11, 17, 22, 34)))
print()

print("a second example a calculator can follow: p = 61, q = 53, e = 17")
k2 = keygen(61, 53, 17)
print("   n = %d, phi(n) = %d, d = %d" % (k2["n"], k2["phi"], k2["d"]))
for m in (65, 1, 2, 3228):
    c = pow(m, k2["e"], k2["n"])
    print("   M = %4d -> C = %4d -> back to %4d" % (m, c, pow(c, k2["d"], k2["n"])))
print()

print("decryption through the Chinese Remainder Theorem, which is how it is")
print("really done, and why the private key stores p and q:")
def crt_decrypt(c, key):
    p, q, d = key["p"], key["q"], key["d"]
    m1 = pow(c % p, d % (p - 1), p)
    m2 = pow(c % q, d % (q - 1), q)
    h = (modinv(q, p) * (m1 - m2)) % p
    return m2 + h * q
print("   C = %d, straight     -> %d" % (C, pow(C, k["d"], k["n"])))
print("   C = %d, through CRT  -> %d" % (C, crt_decrypt(C, k)))
print("   the two agree:", pow(C, k["d"], k["n"]) == crt_decrypt(C, k))
print("   the CRT form works modulo p and q, which are half the size of n, so")
print("   each exponentiation is about eight times cheaper and there are two:")
print("   about a fourfold saving overall.")
print()

print("and a real key, generated here:")
import random
random.seed(5)
def is_prime(n):
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(r - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True

def prime(bits):
    while True:
        c = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime(c):
            return c

p, q = prime(512), prime(512)
key = keygen(p, q, 65537)
print("   p has %d bits, q has %d bits, n has %d bits"
      % (p.bit_length(), q.bit_length(), key["n"].bit_length()))
print("   e = %d, and d has %d bits" % (key["e"], key["d"].bit_length()))
msg = int.from_bytes(b"MU semester 5 marks", "big")
ct = pow(msg, key["e"], key["n"])
back = pow(ct, key["d"], key["n"])
print("   message as an integer has %d bits" % msg.bit_length())
print("   ciphertext has %d bits" % ct.bit_length())
print("   recovered:", back.to_bytes((back.bit_length() + 7) // 8, "big").decode())

The RSA Algorithm

the standard worked example
   p = 17, q = 11
   n = p * q            = 187
   phi(n) = (p-1)(q-1)  = 160
   e chosen coprime to phi(n) = 7
   d = inverse of e mod phi(n) = 23, and e*d mod phi(n) = 1
   public key  {e, n} = {7, 187}
   private key {d, n} = {23, 187}

encrypt M = 88:
   C = M to the power e mod n = 88 to the power 7 mod 187 = 11
decrypt:
   M = C to the power d mod n = 11 to the power 23 mod 187 = 88

every message from 0 to n-1 encrypts and decrypts back:
   messages that fail: 0 of 187
   including the ones NOT coprime to n, which Euler's theorem alone
   does not cover: [11, 17, 22, 34] all recover: True

a second example a calculator can follow: p = 61, q = 53, e = 17
   n = 3233, phi(n) = 3120, d = 2753
   M =   65 -> C = 2790 -> back to   65
   M =    1 -> C =    1 -> back to    1
   M =    2 -> C = 1752 -> back to    2
   M = 3228 -> C =  147 -> back to 3228

decryption through the Chinese Remainder Theorem, which is how it is
really done, and why the private key stores p and q:
   C = 11, straight     -> 88
   C = 11, through CRT  -> 88
   the two agree: True
   the CRT form works modulo p and q, which are half the size of n, so
   each exponentiation is about eight times cheaper and there are two:
   about a fourfold saving overall.

and a real key, generated here:
   p has 512 bits, q has 512 bits, n has 1024 bits
   e = 65537, and d has 1023 bits
   message as an integer has 151 bits
   ciphertext has 1023 bits
   recovered: MU semester 5 marks

The RSA Algorithm

Read six things out of that run.

The RSA Algorithm

The standard example checks out at every step. p of 17 and q of 11 give n of 187 and phi(n) of 160; e of 7 gives d of 23; and e d modulo phi(n) is 1, which the run prints rather than asserts. Encrypting 88 gives 11, and decrypting 11 gives 88 back.

All 187 messages recover, and the number that fail is 0. That is the completeness claim, tested exhaustively rather than argued.

The four messages that are not coprime to n recover too. 11, 17, 22 and 34 share a factor with 187, so Euler's theorem does not apply to them directly. They recover anyway, by the Chinese Remainder Theorem argument in the previous chapter, and the run confirms it.

The second example is the other one in circulation. p of 61, q of 53, e of 17 gives n of 3,233, phi(n) of 3,120 and d of 2,753, and the message 65 encrypts to 2,790. If you meet this example anywhere else, those are the numbers it should give.

Decryption through the Chinese Remainder Theorem agrees with the straight form. Both give 88. The CRT form works modulo p and modulo q, each about half the length of n, so each exponentiation is roughly eight times cheaper and there are two of them: about a fourfold saving. That is why a real private key file contains p and q and not only d.

And a real 1,024-bit key was generated and used. The sentence "MU semester 5 marks" became a 151-bit integer, encrypted to a 1,023-bit ciphertext, and came back. Everything in this chapter scales.

The RSA Algorithm

A worked example by hand, of the kind a paper sets

"In an RSA system, p = 3 and q = 11, e = 7. Find the private key and encrypt the message M = 5."

Step 1. n is 3 times 11, which is 33.

Step 2. phi(n) is 2 times 10, which is 20.

Step 3. Check e: gcd(7, 20). 20 divided by 7 is 2 remainder 6; 7 divided by 6 is 1 remainder 1; 6 divided by 1 is 6 remainder 0. The gcd is 1, so e of 7 is usable.

Step 4. Find d, the inverse of 7 modulo 20. Try the small multiples: 7 times 1 is 7; 7 times 2 is 14; 7 times 3 is 21, which is 1 modulo 20. So d is 3.

Step 5. The keys: public {7, 33}, private {3, 33}.

Step 6. Encrypt. C is 5 to the power 7 modulo 33. By square and multiply, 7 is 111 in binary: square 1 and multiply by 5 to get 5; square 5 to get 25 and multiply by 5 to get 125, which modulo 33 is 26 since 33 times 3 is 99; square 26 to get 676, which modulo 33 is 16 since 33 times 20 is 660, and multiply by 5 to get 80, which modulo 33 is 14.

Step 7. Check by decrypting. M is 14 to the power 3 modulo 33, which is 2,744 modulo 33. And 33 times 83 is 2,739, so the remainder is 5. Correct.

The step that carries the marks. Step 4 and step 7. Finding d by trying small multiples is perfectly acceptable when phi(n) is small, and always decrypt to check: it costs one line and catches every slip.

Distinctions that carry marks

	Public key	Private key
Is	`{e, n}`	`{d, n}`
Published	yes	never
Used to	encrypt to the owner, verify the owner's signature	decrypt, sign
Typical size of the exponent	17 bits, usually 65537	the full length of `n`
Cost of its operation	about 19 multiplications	about 3,041

	n	phi(n)	p and q
Public	yes	no	no
Needed to encrypt	yes	no	no
Needed to find `d`	no	yes	equivalent to `phi(n)`
Needed for fast decryption	yes	no	yes

	Straight decryption	Chinese Remainder Theorem decryption
Computes	`C` to the power `d` mod `n`	two exponentiations modulo `p` and `q`, then recombines
Needs	`d` and `n`	`p`, `q` and `d`
Cost	one full-size exponentiation	about a quarter of it
Used by	textbook descriptions	every real implementation

What beginners get wrong here

Computing d modulo n instead of modulo phi(n). d is the inverse of e modulo phi(n). It is the single commonest error in an RSA question.

The RSA Algorithm

Choosing e without checking the gcd. If gcd(e, phi(n)) is not 1 there is no d, and the whole key is void.

Letting M be greater than or equal to n. RSA encrypts an integer strictly less than n. A longer message is broken into blocks, each smaller than n.

Forgetting to check by decrypting. Every hand-worked RSA answer should end by recovering the plaintext.

Thinking p and q can be thrown away after key generation. They can, but then decryption is four times slower, which is why real key files keep them.

Choosing p and q close together. If they are near each other, n can be factored by trial around its square root. They should be of similar length and not of similar value.

Quick revision

RSA, Rivest, Shamir and Adleman, 1978. C = M to the power e mod n; M = C to the power d mod n.
Key generation: two distinct large primes p, q; n = pq; phi(n) = (p-1)(q-1); e with gcd(e, phi(n)) = 1; d the inverse of e modulo phi(n).
Public key {e, n}, private key {d, n}. e is almost always 65537, because it is prime and has only two one bits.
Standard example: p 17, q 11 gives n 187, phi 160, e 7, d 23; 88 encrypts to 11.
Second example: p 61, q 53, e 17 gives n 3,233, phi 3,120, d 2,753; 65 encrypts to 2,790.
All 187 messages recover, including the four not coprime to n.
CRT decryption works modulo p and q and is about four times faster, which is why a real private key stores p and q.
M must be less than n, and phi(n) is as secret as p and q.

Test yourself

1. Set out RSA key generation. Choose two distinct large primes p and q. Compute n as pq and phi(n) as (p - 1)(q - 1). Select e with 1 < e < phi(n) and gcd(e, phi(n)) equal to 1. Compute d as the multiplicative inverse of e modulo phi(n). The public key is {e, n} and the private key is {d, n}.

2. With p = 3, q = 11 and e = 7, find d and encrypt M = 5. n is 33 and phi(n) is 20. gcd(7, 20) is 1, so e is usable. The inverse of 7 modulo 20 is 3, since 21 is 1 modulo 20, so d is 3. Encrypting, 5 to the power 7 modulo 33 is 14. Checking, 14 cubed is 2,744, and 2,744 modulo 33 is 5.

The RSA Algorithm

3. With p = 61, q = 53 and e = 17, give n, phi(n) and d. n is 3,233; phi(n) is 60 times 52, which is 3,120; and d is 2,753, the inverse of 17 modulo 3,120.

4. Why is e almost always 65537? Because it is prime, so gcd(e, phi(n)) is 1 unless phi(n) is a multiple of it, which is easy to check and rare; and because in binary it is a one followed by fifteen zeros and a one, so square and multiply needs only two multiplications beyond the squarings, making the public operation very cheap.

5. Why must the message be less than n? Because RSA works on residues modulo n, so a message equal to or greater than n would be reduced modulo n and could not be distinguished from the smaller value congruent to it. Longer messages are split into blocks, each represented by an integer less than n.

6. What is Chinese Remainder Theorem decryption, and why does every real implementation use it? Instead of one exponentiation modulo n, it computes two, modulo p and modulo q, using d reduced modulo p - 1 and q - 1, and recombines the results. Since p and q are about half the length of n, each exponentiation costs roughly an eighth as much, so the total is about a quarter: a fourfold speed-up. It requires the private key to retain p and q.

7. Which of n, phi(n), p, q, e and d are public? Only n and e. d is the private exponent; p, q and phi(n) are all equivalent to one another in the sense that any of them yields d from e, so all three must be kept as secret as the private key itself.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.

Syllabus for Cyber and Information Security

Issue