The general method for constructing the parameters of the RSA cryptosystem can be described as follows:
- Select two primes p and q
- Let N = pq and determine ∅ (N) = (p - 1)(q - 1)
- Randomly choose e in the range 1 < e < ∅ N, such that gcd (e,N) = 1
- Determine d as the solution to ed ≡ 1 mod ∅ (N)
- Publish (e,N) as the public key
a. Show that a valid public key pair can still be constructed if we use only one prime
p, such that N =p and ∅ (N) = (p - 1).
b. If we use this "one-prime" RSA construction and publish the public key (e, N),why is it easy to recover the secret key d?
c. Let RSA(M) denote the encryption of the message M using the pair (e, N). Show that the RSA encryption function has the following property for any two messages M1 and M2
RSA (M1 × M2) = RSA(M1) × RSA (M2)
That is, the encryption of a product is equal to the product of the encryptions.
Tasks:
a. Show that "one-prime" construction produces a valid public key
b. Show the steps to recover d
c. Mathematical argument to show the property