Question

Discrete Structures problem

Suppose we use p = 7 and q = 5 to generate keys for RSA. a) What is n ? b) What is on)? c) One choice of e is 5. What are the other choices for e? d) Explain how you got your answer for part c. e) For the choice of e = 5 what is d? Show work. f) Using the public key (n, e), what is the message 3 encrypted as? Show work as if not using a calculator. g) Show that your result for part f decrypts back to 3, using the private key (n. d). Show work as if not using a calculator. h) Suppose you know only the public key (n.) and want to figure out the private key. Explain how you can do it in the case of our value for n. Why doesn't this work for very large values of n?

Answer 1

a)

n= p*q

n=7*5 = 35

b)

Phi(n) = (p-1)(q-1)

Phi(n) = (7-1)(5-1)

Phi(n)=6*4 = 24

c) public key that is e should be coprime to phi(n) and should be less than phi(n).

Choice are 5,7,11,13,17,19,23

d) as explained in above part, (e,phi(n)) should be coprime and e<phi(n).

e) if e= 5, then to calculate d, we need to satisfy following equation.

=> (e*d) mod phi(n) = 1

=> ( 5*d) mod 24 = 1

Substitute d = 5, then above equation is satisfied.

So, d is 5

f) m = 3 (plain text)

To encrypt

m^e mod n

3^5 mod 35

243 mod 35 = 33

33 is cipher text.

g)

decryption

c^d mod n

33^5 mod 35 = 3

So, we got plain text back.