Lab 14 : Plain RSA

In this lab, we will write a toy implementation the RSA algorithm. (Note that the goal is to learn the RSA algorithm, not to achieve security.)

0 Preliminaries

To run doctests, add the following to the bottom of your file:

if (__name__ == '__main__'):
  import doctest
  doctest.testmod(optionflags= doctest.NORMALIZE_WHITESPACE)

We will make use of the following library functions:

from random import randrange
from math import sqrt, ceil, gcd

We will also use following two functions which we have defined in previous labs (feel free to use your own definitions):

def sqr_and_mult_mod(x, e, n):
  """
  Computes x**e modulo n using the square-and-multiply algorithm.
  Assume e is a non-negative integer.

  >>> sqr_and_mult_mod(2, 5, 64)
  32
  >>> sqr_and_mult_mod(2, 6, 64)
  0

  """
  e = bin(e)[2:]
  result = 1
  for b in e:
      if b == '0':
          result = (result * result) % n
      else:
          result = (x * (result * result)) % n
  return result

def mult_inv(a, n):
  """
  Computes the multiplicative inverse of a modulo n using
  the Extended Euclidean algorithm.
  Assumes gcd(a, n) = 1.

  >>> mult_inv(5, 6)
  5
  >>> mult_inv(7, 26)
  15

  """
  q = [0,0]
  r = [n,a]
  x = [1,0]
  y = [0,1]

  while r[-1] > 0:
      q.append(r[-2] // r[-1])
      r.append(r[-2] % r[-1])
      x.append(x[-2] - x[-1] * q[-1])
      y.append(y[-2] - y[-1] * q[-1])

  return y[-2] % n

1 Random prime generation

Recall the steps in the RSA key generation algorithm:

1. Randomly choose two prime numbers p and q of “similar magnitude”. Set n equal to pq;
2. Compute \(\phi(n)\);
3. Randomly choose a number e greater than 1 which has a multiplicative inverse modulo \(\phi(n)\);
4. Compute the multiplicative inverse d of e modulo \(\phi(n)\).

Our strategy for randomly choosing a prime number in a given range will be to repeatedly randomly choose an odd number in that range until we have found one which is prime. So we will need to develop a function is_prime which determines whether or not a number is prime.

As it turns out, Fermat’s Little Theorem can also be used to test for primality. Recall that Fermat’s Little Theorem says that for all integers b, if n is a prime then the following congruence holds:

\[b^n \equiv b \pmod{n}\]

You might wonder whether the converse holds: that is, suppose that this congruence holds for all integers b; does that imply that n is prime? The answer is no; 561 is the first counterexample. However, composite n that do satisfy this congruence for all b are rare; they are known as the Carmichael numbers, and sometimes as “pseudoprimes” or “liars”. Satisfying the congruence of Fermat’s Little Theorem is one way of defining “probably prime” (although state-of-the-art implementations of RSA use more sophisticated definitions).

For our toy implementation, we will test for primality using the congruence in Fermat’s Little Theorem. Since our key length is relatively small, we can ensure that a “probably prime” n is actually prime by first checking whether it’s on a list of known Carmichael numbers bounded by the maximum key size.

Here are the Carmichael numbers less than \(2^{16}\):

carmichael = [561, 1105, 1729, 2465, 2821, 6601, 8911, 10585,
              15841, 29341, 41041, 46657, 52633, 62745, 63973]

Exercise 1 Write a function which randomly selects an odd number in a given range. Use randrange.

def random_odd(m, n):
  """
  Assumes m < n.

  """

Exercise 2 Write a function which tests a number less than \(2^{16}\) to see if it is prime. Your function must implement Fermat’s primality test. Use sqr_and_mult_mod and carmichael.

def is_prime(n):
  """
  Fermat's primality test for numbers <= 2**16

  >>> is_prime(2)
  True
  >>> is_prime(63863)
  True
  >>> is_prime(63864)
  False
  """

Exercise 3 Write a function random_prime which randomly generates a prime number greater than \(\sqrt{2}\cdot 2^{15}\) but less than \(2^{16}\). Use random_odd, is_prime, sqrt and ceil.

Challenge Rewrite is_prime and random_prime for an upper bound larger than \(2^{16}\). (You may find a longer list of Carmichael numbers online.) What can you say about the performance of random_prime as you scale up?

2 Key generation

Exercise 4 Write a function which generates a 32-bit RSA key pair. Use random_prime and mult_inv.

def gen_key_pair():
  """
  Returns ((n, e), (n, d)) where
    n is the modulus
    e is the public key exponent
    d is the private key exponent

  """

3 Encryption and decryption

Exercise 5 Write the encryption function for RSA. Use sqr_and_mult_mod.

def encrypt(m, pk):
  """
  Assumes m < pk[0].

  >>> encrypt(123456789, (1836553613, 2833740479))
  671336816

  """

Exercise 6 Write the decryption function for RSA. Use sqr_and_mult_mod.

def decrypt(m, sk):
  """
  >>> decrypt(671336816, (2833740479, 205383317))
  123456789

  """

Challenge Suppose you have the ciphertext 671336816 and the public key (1836553613, 2833740479) (from Exercise 5). How would you go about decrypting the message without the private key (assuming, of course, that you don’t already know the message)? Can you write a Python program to do it? Can you use Wolfram Alpha to do it?