TESTBOOK

Question

using RSA algorithm Alice wishes to send a message m=439 to Bob. Alice choose a prime number p=31 and q=23,if he chooses a public key (223,713) what is the private key bob should choose?

A)367

B)413

C)218

D)240

Answer 1

The keys for the RSA algorithm are generated the following way:-

1. Choose two large and distinct prime numbers $p$ and $q$.
2. Take the product $n =p \times q$
3. Compute the number of integers less than n that are coprime with n (otherwise known as the totient):                           $\phi(n)=(p-1)\times (q-1)$
4. Choose an integer e such that $1< e< \phi(n)$ and $e$ and $\phi(n)$ are coprime (i.e. share no common factors other than 1)
5. Compute a value for d such that it satisfies the relation:  $(d \times e)\ \% \ \phi(n) = 1$
6. The public key is $(e,n)$
7. The private key is $(d,n)$
8. To encrypt m using the public key use the relation: $c = m^{e} \ \% \ n$
9. To decrypt c using the private key use the relation: $m = c^{d} \ \% \ n$

Given,

P=31 , Q=23 , e=223 , n=713 , m=439

$\phi(n)=(p-1)\times(q-1)$

$\phi(n)=30\times22$

$\phi(n)=660$

Now from step 5 Compute a value for d such that it satisfies the relation: $(d \times e)\ \% \ \phi(n) = 1$

it is satisfy when d=367

$(367 \times 223)\ \% \ 660 = 1$

Hence, Option(A)367 is the correct choice.

Algo. Reference :-https://www.cs.utexas.edu/~mitra/honors/security.html

Comments

@leenSharma

How to calculate d=367 ?????

---

It's an easy way for this question to put options and check.

or you can use extended Euclidean algorithm.

https://crypto.stackexchange.com/questions/5889/calculating-rsa-private-exponent-when-given-public-exponent-and-the-modulus-fact/5894

---

still 4 option checking takes time.

@leen is any shortcut process?

---

 srestha you can see given link to find d using extended Euclidean algorithm but I don't know any short method.

Answer 2

RSA Algorithm   http://courses.cs.vt.edu/~cs5204/fall00/protection/rsa.html 

Compute n = p * q = 31 * 23 =713

φ(n) = (p - 1) * (q - 1) = 30 * 22 =660

given public key is (e, n) = (223, 713)

encryption of m = 439 is      c = m^e mod n = 439 ²²³ mod 713 =284

decryption of c is                  m = c^d mod n = 284 ^d mod 713 =439     here d is public key

by checking option only 367 is satisfied