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