# RSA public key security issue

The public key for RSA is $[e,n]$. Since $n = p * q$, are $p$ and $q$ already exposed because it takes no effort to figure out $p$ and $q$ from $n$?

-
No research effort whatsoever was made. Proper tagging is not enough! – fgrieu Feb 26 '14 at 7:43
No they are not, getting p,q from n is not trivial – figlesquidge Feb 26 '14 at 10:54

If I right understood your question, you think that from N it is easy to compute $p$ and $q$. But it is not true.
For computing $p$ and $q$ from $N$, you need to solve factorization problem. And this is very difficult. If $N$ small number, then you can use brute force. But when it comes to RSA, $N$ is a very big number. And it will take many hundreds years to compute $p$ and $q$ this way.
But you can use one of sub exponential algorithm, for example quadratic sieve. It is one of the fastest factorization algorithm right now. for big $N$ (1024 bits or more) this method is not practical. That is why, knowledge $N$ will not give you help to reveal $p$ and $q$.
But as soon as a practical method is found, RSA will be absolutely weak, because everyone would be capable to compute $\varphi(N)=(p-1)(q-1)$ and everyone would be capable to compute the secret exponent $d=e^{-1}\bmod\varphi(N)$.
Writing nice formulas is easy: $d=e^{-1}\bmod\varphi(N)$ is just $d=e^{-1}\bmod\varphi(N)$; an important point is that this $d$ will be a working private exponent; however it is not guaranteed to be the private exponent; there are several equally fine private exponents. – fgrieu Feb 26 '14 at 7:39
@fgrieu Thank you. It is really easy:) I didn`t get your remark about several exponents. Do you mean that every $d$ such as $ed=k\varphi(N)+1$ will be good private exponent? – neverwalkaloner Feb 26 '14 at 8:36
Yes, every $d$ such as $e⋅d=k⋅φ(N)+1$ will be good private exponent. And there typically are others. If $N=p⋅q$ with $p$ and $q$ large distinct primes, one can use $\operatorname{lcm}(p-1,q-1)$ which is also $\lambda(N)$, and is smaller than $φ(N)$. That's what the de-facto-standard definition of RSA does. It allows smaller $d$, that often are slightly more efficient. – fgrieu Feb 26 '14 at 9:34