RSA

From Computer Science
Revision as of 22:46, 16 February 2023 by Jkinne (talk | contribs)
Jump to: navigation, search

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.