# GATE2009-46

3.4k 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
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:

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

edited
15
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$
1
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)

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.

edited

## Related questions

1
12.6k views
Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Let $I$ be the minimum number of ... wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time) $16ms$ $18ms$ $20ms$ $22ms$
Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). What is the minimum number of bits ... numbers distinctly? Assume that no time gap needs to be given between transmission of two frames. $I=2$ $I=3$ $I=4$ $I=5$
Let $G(x)$ be the generator polynomial used for CRC checking. What is the condition that should be satisfied by $G(x)$ to detect odd number of bits in error? $G(x)$ contains more than two terms $G(x)$ does not divide $1+x^k$, for any $k$ not exceeding the frame length $1+x$ is a factor of $G(x)$ $G(x)$ has an odd number of terms.
While opening a $TCP$ connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order $32$ bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter ... at which sequence numbers used for packets of a connection can increase? $0.015$/s $0.064$/s $0.135$/s $0.327$/s