Andrew S. Tanenbaum Edition 5th Exercise 8 Question 17 (Page No. 873)

Question

Using the RSA public key cryptosystem, with a = 1, b = 2 . . . y = 25, z = 26.
(a) If p = 5 and q = 13, list five legal values for d.

(b) If p = 5, q = 31, and d = 37, find e.
(c) Using p = 3, q = 11, and d = 9, find e and encrypt ‘‘hello’’.

Answer 1

...........

Answer 2

a. p=5, q=13

    n=p*q=65

    $\Phi (n)$=(p-1)*(q-1)=48

    d(private key) should be chosen such that d and $\Phi (n)$ have no common factors(they are relatively prime)

    Possible choices for d=5,7,11,13,17

b. p=5, q=31 and d=37

    n=p*q=155

     $\Phi (n)$=(p-1)*(q-1)=120

     the following relation must hold

     e*d=1 MOD  $\Phi (n)$

     e*37=1 MOD 120

     e*37 could be 121, 241, 361, 481 and so on

     for here we obtain e=13

c.  p=3, q=11, d=9

     n=p*q=33

      $\Phi (n)$=(p-1)*(q-1)=20

      e*d=1 MOD  $\Phi (n)$

      e*9=1 MOD 20

      e=9

      for encryption $C=P^e MOD$ n

      hello=8, 5, 12, 12, 15

      h =>  $8^9 MOD$ 33=29

      e =>  $5^9 MOD$ 33=20

      l  =>  $12^9 MOD$ 33=12

      o =>  $15^9 MOD$ 33=3

Comments

I think there is some mistake in the question as for h we're getting  C=29