Let suppose that the sizes of factors $p$ and $q$ are $b$ bits. We construct two RSA numbers $n$, $n'$ of same sizes. Can we say that the duration to break these two numbers is two times the duration to break one number?

  • $\begingroup$ You will have to define "break" and "RSA moduli" - do you mean "factor" and do "RSA moduli" need to resist factorization, or do you mean any semiprime? $\endgroup$
    – Thomas
    Oct 9 '14 at 7:48
  • $\begingroup$ I was speaking about factoring. $\endgroup$
    – Dingo13
    Oct 9 '14 at 17:35

For $n$ and $n'$ RSA moduli of a size of practical interest (1024-bit and more) and correctly generated, we can say that the expected computing effort to factor both $n$ and $n'$ by any practical method that we know (including the best, which is GNFS) is about twice that to factor $n$.

How that translates to time is context-dependent. In particular, the time it takes to design and build the tools (hardware and software) that factor $n$ needs not be spent again when factoring $n'$. And for an adversary with large resources, it might be possible to run the two computing efforts on duplicated hardware (especially the matrix step), so that the wall clock time to factor both $n$ and $n'$ might be significantly less than twice that to factor $n$, even when discounting design and build time.


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.