In your favorite language (preferable in Python) create the following functions:

1. MRT => Use Miller-Rabin Primality Test to choose a prime number with s=512 bits and

check the primality test.

Project 3 on RSA:

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

II.

III.

a. Choose two primes p and q of s bits using MRT where p is not equal to q.

b. Calculate n = p * q, and (n) = (p − 1) * (q − 1)

c.

Chose randomly e from the set of {1,..., (n)-1} and check using EA if

gcd(e, (n)) = 1 if not chosen again until it fulfills the condition.

d. Calculate d = e¹ mod (n) using EEA. Note that d should be at least 0.3 * s

bits

e. Output k pub= (n, e) and k

Pr

(d)

Pub

RSA Encryption with input k (n, e) and random plaintext x and output should be

ciphertext y, evaluate exponentiation using the function powmod_sm

RSA Decryption with input kp = (d) 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.

=

=

Please write your report and include a snapshot of output with you source code.