my helper file for this lab.

it includes some data for this lab as well as functions to convert strings to integers and back, and determine the "block length" of strings you can use when working with a modulus n.

task 1: write a function modexp(a,b,n), which a positive integer n and non-negative integers a, b, computes fast modular exponentiation of a^b mod n via repeated squaring. (by a^b i mean exponentation, not bitwise as this would mean in python.) you may use the binrep function you wrote for lab 5. test your function on a few small cases, then test modexp(3,4567890,10000) and compare the time taken with the straightforward python code 3**4567890 % 10000. (recall the use of timeit from lab 5 for timing code.)

task 2: using your modexp function, verify my rsa digital signature sig2 (no hashing) of my message m2 with my public key from the my helper file. question: can you figure out why i might have chosen e in my public key to bet 65537 = 2^16 + 1? is there any security issue with different people using this value for e?

task 3: write a function is_prime(p) that, given a positive integer p, returns True if p is prime and False otherwise. you should check divisibility by numbers up to the square root of p. (you do not need to check divisibility by all numbers up to the square root of p, and i encourage you to implement simple speed-ups using this idea.) you can compute the floating point square root of p in python by first calling from math import sqrt, and then sqrt(p). test your function on all integers p between 1 and 50 by printing all numbers in this range for which your function returns True.

task 4: write a function is_pseudoprime(p) that runs the following probabilistic primality test. first, check that p is not divisible by any number 1 < d < min(p,100). (for efficiency, if you wish, you can precompute a table of primes < 100, and test for divisibility by these). then, if p > 100, check that p satisfies the expectation from fermat's little theorem with a=2, i.e., that 2^(p-1) = 1 mod p. (this means that p is a fermat pseudoprime for the base 2) return True if p passes both of these tests and False otherwise. determine how many numbers p up to 2^20 such that p passes your pseudoprime test but is not actually prime. how does this compare with the number of pseudoprimes (or if you prefer primes) up to 2^20? also, compare the time taken to run is_prime(p) for all p to 2^20 versus is_pseudoprime(p).

task 5: write a function pseudoprime(k) that finds a random pseudoprime of at least k digits. you can generate a random integer between a and b (inclusive) with the code function randint(a,b) after calling from random import randint. suggestion: generate a random number, test it for being a pseudoprime, and if it fails, increment by 1 (or maybe 2) and try again. test your function several times for k=2.

task 6: write a function rsakeygen(p,q) which returns a triple (n,e,d) consisting of n=pq and a random pair (d,e) of integers such that de = 1 mod phi(n). you should use your modinv function from lab 5 to do this efficiently. test your function a few times on pairs of small primes (p,q).

task 7: generate random pseudoprimes p, q which are each about 10-15 digits long. (note: it's better not to pick p, q too close as there are factoring methods that can exploit this, so it's better choose them to have not exactly the same number of digits.) use the previous function to make a public rsa key (n,e) and private rsa key d. encrypt the message m = "Psst! I know a secret about coronavirus." with the public key and then decrypt it with the private key. note that you will need to break your message into blocks, which you can either do "by hand" or you can automate with auxiliary functions.

lab 6 homework (hw 10): complete the above tasks (due mon apr 6)