Remember that the tests are called basic tests, because they only test basic functionality. Your code may be tested on reasonably more general inputs.
There are four test and a challenge,
number_thy_test
Complete the code in the MyMod class, and the code for the extended gcd. The extended gcd code is used to calculate inverses in modular number systems.
miller_rabin_test
Implement the Miller Rabin probabilistic primality testing algorithm. The function takes an integer and an iteration count. The output is phrased in terms of a found witness.
If no witness found, return False
If a witness is found, return the pair (witness_type, witness) where:
witness_type is "factor", if the witness is a non-trivial divisor of n
witness_type is "fermat", if the witness to the (n-1) power mod n is not 1
*** MILLER RABIN ALGORITHM ***
Given n and an iteration count,
First check for small primes.
Check of pure powers, and return "factor" and a non-trivial factor of n
For the iteration count:
Pick a random number w in range
Test for co-primality, and if fails return a factor of n
Square w successively for each factor of 2 in n-1
If during squaring non-negative one square root of 1 is found,
use it to factor n and return "factor" and a non-trivial factor of n
Finally take w to the remaining factor in p-1 and check the Fermat condition
If the Fermat condition fails, return the witness noted as "fermat"
Return False (failure to find a witness)
Complete the implementation of the RSA class, found in the template.
Note that the generate key operations also calculate and store the encryption and decryption exponents. The encryption exponent is the first integer equal to or larger than 3 that is relatively prime to phi(n), and the decryption exponent is the inverse mod phi(n) of the encryption exponent.
The default constructor goes ahead an calls the default key generation algorithm, using the given byte length. I have provided you with the random_prime function, that returns a random prime of the given byte length.
pollard_rho_test
Write the Pollard Rho algorithm. This algorithm can be used in challenge to crack a vulnerable RSA instance.
*** POLLARD RHO ALGORITHM ***
Given an n to factor
Choose a random starting points x and x_p, initially equal
Using the update function f(x)=x2+1, mod n:
Update x gets f(x) and x_p gets f(f(x))
Check the gcd between the difference x-x_p and n.
A non-trivial GCD is a factor of n. Return the factor
After about square root of n attempts, terminate having failed to find a factor of n
The Challenge
You are given the modulus and the exponent for a vulnerable RSA public key. Decode the ciphertext given.
author: burton rosenberg
created: 25 mar 2018
update: 29 mar 2018