Assignment #3: CRT, Totient Function, Inverses, and Applications (back to full lecture notes)

For this assignment, you will submit a single Python source file

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

    1. Define a Python function egcd() that takes two integer inputs x and y and returns a tuple of two integers (s,t) that satisfies the following property:
      • s * x + t * y == gcd(x,y)
    2. Define a Python function inverse() that takes two integer inputs x and m and returns the multiplicative inverse of x in Z/mZ if it exists, or returns None if it does not.
    1. Define a Python function CRT2() that takes two inputs, each of which is a pair of integers. Each of the two pairs of integers, call them (a,m) and (b,n), represents one of the equations in the system of equations below:
      a (mod m)
      b (mod n)
      You should assume m and n are coprime. The function should return a single integer x Z/(mn)Z that is the solution to the two equations above.
    2. Define a Python function CRTN() that takes one input, which is a list of pairs, each of which is of the form (a,m). Each of the pairs in the list represents a distinct equation in the system of equations below:
      a1 (mod m1)
      ak (mod mk)
      You should assume that for every i, j {1,...,k} where ij, mi and mj are coprime. The function should return a single integer x Z/(m1 ⋅ ... ⋅ mk)Z that is the solution to the system of equations above.
    1. Define a very efficient Python function pow2ModPrime() that takes four integer inputs x, y, z, and p. This function always assumes that p is prime (it need not return a correct output if p is not prime, and it should not check whether p is prime). The function should return the result of the computation:
      xyz mod p
      Your implementation may employ the built-in Python function pow(), which takes three inputs a, b, and m and returns ab mod m. However, your function must be able to handle very large inputs. For example:
         pow2ModPrime(3,3,1000000000000000000000,84199) # Should return 42526 quickly.
         pow(3,pow(3,1000000000000000000000),84199)     # Should be much slower than the above.
      Hint: consider the way Euler's theorem and the totient function φ are used in the RSA cryptographic protocol.
    2. Define a very efficient Python function diffPows() that takes three inputs: two integer inputs x and y and a list of distinct primes ps. Let P be the product of the primes in ps. The function should return an output equivalent to:
      (33x - 22y) mod P
      Your function must be able to handle very large inputs. For example:
         primes =[\
         # The code below should take at most a second or two to evaluate.
         diffPows(100000000000000000000, 100000000000000000000, primes)
         # The output of the above should be:
  1. In this problem you will implement the three component algorithms of the RSA cryptographic protocol described in lecture.
    1. Define a Python function generate() that takes a single integer input k and returns a tuple (n,e,d) corresponding to the public values n and e and private key d in the RSA cryptographic protocol. The output n must be the product of two distinct, randomly chosen k-digit primes.
      • You may import and use the Python random number generator (from random import random or from random import randint).
      • Your algorithm does not need to be efficient, but it should always be correct.
    2. Define a Python function encrypt() that takes two inputs: an integer m and a tuple (n,e). It should return a single integer: the ciphertext c.
    3. Define a Python function decrypt() that takes two inputs: an integer c representing the ciphertext and a pair of integers (n,d) representing the private key. It should decrypt c and return the original message m.