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$
$\endgroup$
2
-
$\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$– ThomasOct 9, 2014 at 7:48
-
$\begingroup$ I was speaking about factoring. $\endgroup$– Dingo13Oct 9, 2014 at 17:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Oct 9, 2014 at 9:02