2.5k 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

edited | 2.5k views
+2
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.
0
recheck they are doing it correct
0
It is confusing because M-> ciphertext and M->is plain text they reversed the symbol what we generally use , to confuse! :)
+3

@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.

0

@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:

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

by Veteran (63k points)
edited
+14
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))}$
0
i know that  (d*e)mod z=1. confused...
+1

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

+3
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?
0
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$
0
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.
+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:

(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?

+1

@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.

+1
Thanks.
ans b)
by Loyal (5.2k points)

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. by Active (4.3k points)

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.