The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

In RSA Algorithm, we have public key(e,n) and private key(d,n).

**Sender side** we encrypt **plain text P as an integer between 0 and n-1** as follows:

$P^{e}modn$

and send it.

**At receiver side**, we do the following:

$(P^{e}modn)^{d}modn = P^{ed}modn$

$P^{ed}modn= P$

But according to Euler's Theorem:

The following equation holds if 'a' and 'n' are coprimes:

$a^{\phi (n)t+1)}modn= a$

So, what I am confused about is that while encrypting the message P we are taking it as as integer between 0 and n-1. So, the P may not be coprime to n. Then how does the algorithm work?

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,720 questions

52,821 answers

183,476 comments

68,569 users