patternModerate
What if p and q are not distinct in RSA Crypto System? What could go wrong?
Viewed 0 times
distinctwhatrsaaresystemcouldcryptowrongandnot
Problem
In RSA Crypto System we choose p and q such that they are distinct primes. Calculate n=pq and phi=(p-1)(q-1). Then e is chosen for public key (n,e) s.t. gcd(e,phi)=1
Solution
The security of RSA relies on the fact that the best known way to compute $\phi(n)$ is to prime factorize $n$. For $n=pq$, where $p$ and $q$ are large, distinct primes, this is very hard. If instead $n=p^2$, then one could quickly find $p$ by calculating a square root. Then one could calculate $\phi(p^2)=p^2-p$ and break the encryption completely.
Context
StackExchange Computer Science Q#50906, answer score: 13
Revisions (0)
No revisions yet.