Question

1. In a RSA cryptosystem, a participant A uses two prime numbers p = 13 and q = 17 to generate her public and private keys. If the public key of A is 35, then the private key of A is 11.

2. Alice wants to encrypt a message to Bob by using the RSA algorithm and using keys in (A)

The plaintext = “HI”.

Answer: _______________

Answer 1

A.

Given p = 13 and q = 17
Compute totient Φ(n) = (p-1)*(q-1) = (13-1)*(17-1) = 12*16 = 192

Let the private key is d.
Given public key e = 35.

From RSA cryptosystem we know that d*e mod  Φ(n) ≡ 1
Let's check this for d = 11.
11*35 = 385 = 1 + 2*192 = 1 + 2*Φ(n)
Hence, d = 11 is valid private key.

B.

Let's encrypt the text = HI

n = p*q = 13*17 = 221
By RSA encrypted message c = m^e mod n
Where m is plaintext. Here m = HI.

We have to encode the plaintext into a numerical value we can do this using alphabet to number mapping i.e (A = 1, B = 2, ... Z = 26) and then add these numbers.
In our case message, 'HI' numerical value is 8(H = 8) + 9(I = 9) = 17.

Hence we have to encrypt m = 17
c = 17^35 mod 221 = 153 (calculate using calculator)

Therefore encrypted message is c sent by Alice is = 153.

Let's verify at Bob's end

m = c^d mod n

m = 153^11 mod 221 = 17
Now decoding m = 17 into text we get plaintext = HI