In Python create the following functions:
1. MRT èUse Miller-Rabin Primality Test to choose prime number with s=512 bits and
check the primality test.
2. EA èUse Euclidean Algorithm to evaluate gcd
3. EEA èUse Extended Euclidean Algorithm to find modular inverse of the value
4. powmod_smè Square and multiply algorithm to evaluate exponentiation.
Now write the code for
I. RSA Key Generation (use above functions 1., 2., 3. ) should be
a. Choose two primes p and q of s bits using MRT where p is not equal to q.
b. Calculate = p ∗ , and phi() = (p − 1) ∗ ( − 1)
c. Chose randomly e from the set of {1,..., phi() − 1} and check using EA if
c(, phi()) = 1 if not chose again until it full fills the condition.
d. Calculate = 12 mo phi() using EEA. Note that should be at least 0.3 ∗
bits
e. Output :;< = (, ) and := = ()
II. RSA Encryption with input :;< = (, ) and random plaintext x and output should be
ciphertext y, evaluate exponentiation using the function powmod_sm
III. RSA Decryption with input := = () and ciphertext y and output should be plaintext x,
evaluate exponentiation using the function powmod_sm. Please make sure to check that you get the same plaintext value before the encryption.