Difference between revisions of "RSA"
(Created page with "Given primes p and q # Confirm p and q are prime using Fermat's little theorem prime test. ## Show the steps of how this is done using fast modular exponentiation. # Let n =...") |
|||
| Line 12: | Line 12: | ||
Take a given ciphertext c and computer c**d mod n to decrypt the message. | 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. | ||
Revision as of 22:46, 16 February 2023
Given primes p and q
- Confirm p and q are prime using Fermat's little theorem prime test.
- Show the steps of how this is done using fast modular exponentiation.
- Let n = p*q and totient = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1).
- Show the steps of computing gcd(p-1, q-1) using the Euclidean algorithm.
- Find the smallest e > 1 such that gcd(e, totient) = 1.
- Let d be the inverse of e mod totient.
- Show the steps of computing d using the extended Euclidean algorithm.
- Your public key: n, e
- 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.
