5,630 views

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

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

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))$

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)dm(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.

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.

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.