For more information about RSA and cryptology, see the FAQ (Fequently Asked Questions) www pages of RSA Labs.
In the RSA cryptosystem, each communicant selects the following public and private information. The private information consists of two large distinct prime integers p and q, and an integer d such that gcd(d,phi(n))=1, where phi(n)=(p-1)(q-1) is the so-called totient (or Euler phi function) of n. The public information consists of n = pq and an integer e such that ed = 1 mod phi(n). The public information is suitably disseminated--for example, using a PKI (Public-Key Infrastructure).
Messages are represented by integers in the set Z_n = {0, 1, 2, ... n-1}. (Long messages are broken down into sequences of such integers, where each message part is separately encrypted and suitably cryptographically "chained" to the other message parts.) Each message x \in Z_n is encrypted as follows to produce a ciphertext y:
y = E_(n,e)(x) = x^e mod n,
where x^e denotes exponentiation of x to the power e. If Alice is sending a message to Bob, then Alice encrypts using Bob's public parameters n and e. Note that exponentiation mod n can be efficiently carried out using the "repeated-squaring" algorithm, moding out by n at each step.
To decrypt the ciphertext y to yield the plaintext x, Bob computes:
x = D_(n,d) = y^d mod n,
using Bob's secret key d and Bob's public key n.
(a) Apply Extended Euclid's Algorithm (see Solution to HW4, Problem 5--Exercise 11 from Set 4.5) to compute all suitable e \in Z_phi(n), where n = pq. That is, solve the Diophantine equation
ed = 1 mod phi(n)
for e. How many solutions are there in Z_phi(n)? List all of these solutions in increasing order.
(b) Using the smallest suitable e, encrypt and decrypt each of the messages x = 0, 1, 7.