Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$?

share|improve this question
3  
No research effort whatsoever was made. Proper tagging is not enough! –  fgrieu Feb 26 at 7:43
    
No they are not, getting p,q from n is not trivial –  figlesquidge Feb 26 at 10:54

1 Answer 1

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)$.

share|improve this answer
1  
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 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 at 8:36
3  
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 at 9:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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