RSA

Given primes p and q

1. Confirm p and q are prime using Fermat's little theorem prime test.
   1. Show the steps of how this is done using fast modular exponentiation.
2. Let n = p*q and totient = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1).
   1. Show the steps of computing gcd(p-1, q-1) using the Euclidean algorithm.
3. Find the smallest e > 1 such that gcd(e, totient) = 1.
4. Let d be the inverse of e mod totient.
   1. Show the steps of computing d using the extended Euclidean algorithm.
5. Your public key: n, e
6. Your private key: n, d

Take a given ciphertext c and computer c**d mod n to decrypt the message. Note: you will receive a message from the instructor that is encrypted with your public key.

Given the instructor's public key, encrypt your response and include that in your submission of the assignment.

CyberChef things to use...

• To Char code, from char code.