GATE CSE 2009 | Question: 46

Question

In the RSA public key cryptosystem, the private and public keys are $(e, n)$ and $(d, n)$ respectively, where $n=p \times q$ and $p$ and $q$ are large primes. Besides, $n$ is public and $p$ and $q$ are private. Let $M$ be an integer such that $0<M<n$ and $\phi(n) = (p-1)(q-1)$. Now consider the following equations. 

1. $M’ = M^e \text{ mod } n$
   $M = (M’)^d \text{ mod } n$

2. $ed  \equiv 1 \text{ mod } n$

3. $ed  \equiv 1 \text{ mod } \phi(n)$

4. $M’ = M^e \text{ mod } \phi(n)$
   $M = (M’)^d \text{ mod }\phi( n)$

Which of the above equations correctly represents RSA cryptosystem?

• A. I and II
• B. I and III
• C. II and IV
• D. III and IV

Comments

It is confusing because M-> ciphertext and M`->is plain text they reversed the symbol what we generally use , to confuse! :)

---

@Shiva is partially correct(but he pointed one imp. thing..):-

Actually, the Public Key Cryptography(i.e. RSA) has several applications

1.Encryption

2.Authentication

3.Key Exchange(i.e. Diffie-Hellman Key Exchange)

Here the given Question it is doing authentication by encrypting by sender's private key and decryption using sender's public key.

---

@Bikram Sir pls check

According to RSA applications it is generally used for

1)Encryption

2)Authentication

3)Key exchange

in this question e represents private key,d represents public key  and authentication has to be done .So if M is a msg then

Authentication by  Encryption ,using private key .So M'=M^e mod n

 Authentication by Decryption,using public key.So M= M' ^d mod n

http://searchsecurity.techtarget.com/definition/RSA
 

Answer 1

The basic principle behind RSA is the observation that it is practical to find three very large positive integers $e, d$ and $n$ such that with modular exponentiation for all $m:$

${\displaystyle (m^{e})^{d}\equiv m{\pmod {n}}}$ and that even knowing $e$ and $n$ or even m it can be extremely difficult to find $d.$

Additionally, for some operations it is convenient that the order of the two exponentiations can be changed and that this relation also implies: ${\displaystyle (m^{d})^{e}\equiv m{\pmod {n}}}$

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

• Choose two distinct prime numbers $p$ and $q.$
• Compute $n = pq.$
• Compute $\varphi (n)  = \varphi (p)\varphi (q) = (p − 1)(q − 1)$
• This is more clearly stated as: solve for $d$ given $d⋅e \equiv 1 (\mod \varphi (n))$

So, B is answer.

Comments

The basic principle behind RSA is the observation that it is practical to find three very large positive integers e, d and n such that with modular exponentiation for all m:

(me)d≡m(modn)

 and that even knowing e and n or even m it can be extremely difficult to find d.

Can anyone explain these lines?

---

@`JEET

Even knowing e,n it can be extremely difficult to find d.

This is true because to find d, we solve ed mod $\phi(n)$=1.

clearly d can be computed if we know e,$\phi(n)$.

but calculating $\phi(n)$ with n is computationally very difficult.

But how does receiver calculate it??

answer is receiver calculates it by $\phi(n)$=(p-1)(q-1).which is just a multiplication for him.

But others don't know p,q.So they can't calculate $\phi(n)$.

Hence they can't calculate  d.

---

Thanks.

Answer 2

They have reversed the sign.in general (e,n) is public key and (d,n) is private key for a sender so do not confuse with this.

Answer 3

If equation 2 is true i.e, ed mod n =1, then any one can calculate private key of receiver.

Hence any one can decrypt the message of sender.

Therefore equation 2 is false.

If equation 4 is true,  i.e $m=m^{e}$ mod $\phi(n)$ no one except the receiver can encrypt the message because calculating $\phi(n)$ without the prime numbers p,q which made n(i.e, n=p*q) is computationally very difficult .

Which is clearly not we want.

Hence equation 2,4 are false.

Hence option b is answer