The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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
asked in Computer Networks by Veteran (52k points)
edited by | 2.1k views
Here while we encrypt the messge, we have to do with the public key, and decryption is done using private key, but here they are encrypting with private key and decryption is done with public key, which has to be reverse.
recheck they are doing it correct
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

+19 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 φ(n) = φ(p)φ(q) = (p − 1)(q − 1)
  • This is more clearly stated as: solve for d given de ≡ 1 (mod φ(n))

So, B is answer.

answered by Veteran (61.4k points)
edited by
If in exam one gets confused then use some common sense like this-

(e,n) Public key
d is private key or (d,n) is private key

Now encryption should be allowed to anyone, Therefore to encrypt protocol must use public key only.
Hence, $M' = M^e \text{ mod n}$
d is private key and this should not be calculated using public componentent i.e. $\text{(e, n)}$
Hence, $d⋅e ≡ 1 \text{(mod φ(n))}$
i know that  (d*e)mod z=1. confused...

1 = d*e (mod φ(n) )   and   d*e = 1 (mod φ(n) )   these two are same..?

So here, M' is the plain text ,right? Because M' is generated by using private key on M.

And M is generated by using public key so it must be cipher text?
M' is cipher-text and M is plain-text.

(e,n) is public keys available to public to encrypt

$M' = (M)^e mod n$

and for decryption the receiver uses his/her private key

$M = (M')^d mod n$
It is confusing because RSA cryptosystem is also used in digital signatures.

Given (e,n) public key and (d,n) private key

What is happening in (I) is the sender is signing the message with his own private key and the receiver is verifying the signature using the sender's public key.

So, they have combined the idea of RSA and digital signatures.
+5 votes
ans b)
answered by Loyal (5.2k points)
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.

answered by Active (1.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,122 answers
71,040 users