2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ What are your thoughts? What efforts have you made? We expect you to make a serious effort to solve your own question before asking here. For instance, have you tried trying a few examples? Have you tried walking through the proof of correctness for RSA and seeing if it still holds if $p=q$? If your question is so short that it fits in a one-line title and you find that you don't have anything else to say in the body of the question, that should often be a warning sign. $\endgroup$ – D.W. Dec 18 '15 at 18:34
  • $\begingroup$ I did try to solve it! For a few cases, the public and the private key becomes the same, depending upon the choice of e. Rest I just think that it makes it easier to decrypt if the numbers are same. $\endgroup$ – Nilaxi Maken Dec 21 '15 at 19:10
13
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

In addition to SBareS's answer, let me mention that the formula $\varphi(pq) = (p-1)(q-1)$ only works if $p \neq q$: $\varphi(p^2) = p(p-1)$. Therefore if $p = q$ then decryption wouldn't be the inverse of encryption (unless you use the correct formula for $\varphi(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.