in Computer Networks edited by
21 votes
21 votes

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?

  1. I and II
  2. I and III
  3. II and IV
  4. III and IV
in Computer Networks edited by


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



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



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


3 Answers

22 votes
22 votes
Best answer

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.

edited by


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:


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

Can anyone explain these lines?



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.

0 votes
0 votes

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

0 votes
0 votes

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

edited by

Related questions