Question

You and I want to communicate using RSA. I have found a “large” prime for us to use, n=33 (3*11).

a) Calculate the totient and come up with the smallest possible private key that will work. Justify that this private key is good (point out what has to be true).

b) Calculate the associated public key. Start at least by writing down what has to be true for a value to be the public key.

c) What are your public and private key pairs?

Answer 1

-----------------------------------------------------------------------------------

It is given that n = 33

Since, n = pq

p = 3, q = 11

-------------------------------------------

a)

Totient

We have to find the smallest possible private key d such that

where

Lets us find all possible values of e, such that 1 < e < 20 and for each e we will find corresponding d, then we will finally select d, e such that d is smallest

With  1 < e < 20, and gcd(e, 20) = 1 ,

The possible values for e are 3, 7, 9, 11, 13, 17, 19

We find d such that (de) mod 20 = 1

When e = 3, d = 7, since, 21 mod 20 = 1

When e = 7, d = 3, since, 21 mod 20 = 1

When e = 9, d = 9, since, 81 mod 20 = 1

When e = 11, d = 11, since, 121 mod 20 = 1

When e = 13, d = 17, since, 221 mod 20 = 1

When e = 17, d = 13, since, 221 mod 20 = 1

When e = 19, d = 19, since, 361 mod 20 = 1

Clearly when d = 3 is the smallest possible value for private key,

and e = 7 is the corresponding public key

-------------------------------------------

b)

When d = 3

Associated public key => e = 7

Public key e must satisfy

and   

When d = 3, e = 7, (de) mod 20 = 1

gcd(7, 20) = 1

-------------------------------------------

c)

Public key pair => (e, n) = (7, 33)

Private key pair => (d, n) = (3, 33)

----------------------------------------------

I hope this helps you,

Please rate this answer if it helped you,

Thanks for the opportunity