Lets prime factorize $30$:
$$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$
We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two primes. Why is this??
$\begingroup$
$\endgroup$
5
asked Mar 19, 2020 at 12:33
-
2$\begingroup$ Does this answer your question? Are there any standards of multi-prime RSA key generation? $\endgroup$– kelalakaMar 19, 2020 at 12:34
-
5$\begingroup$ Because RSA modulus are not just random big numbers: they are built by first sampling two primes, and then multiplying them together. $\endgroup$– Geoffroy CouteauMar 19, 2020 at 12:59
-
$\begingroup$ Thank you Geoffroy Couteau. Since primes are rather "unusual", especially the bigger the number, won't that leave a manageable (for a computer) amount of products to "choose" from. A hacker/decoder might have a library of prime products and will be able to look up the chosen number. $\endgroup$– Kristian Francisco Milla NielsMar 19, 2020 at 13:21
-
2$\begingroup$ @KristianFranciscoMillaNiels see this other question $\endgroup$– SEJPMMar 19, 2020 at 13:35
-
$\begingroup$ @KristianFranciscoMillaNiels Also see the GCD Them ALL $\endgroup$– kelalakaMar 19, 2020 at 14:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
By construction, RSA moduli are the product of two large primes.
-
1$\begingroup$ Or more. Depends on how the RSA moduli is generated. Muliprime RSA is a thing, we even have a multi-prime-rsa tag for it. In particular, there is provision for it in the private key format defined by PKCS#1v2.2. $\endgroup$– fgrieu ♦Apr 18, 2020 at 21:38
-
$\begingroup$ Three factors would be very useful if someone finds an ingenious method to factor products of two large primes which is useless for products of three large primes. Which is quite conceivable. $\endgroup$ Apr 19, 2020 at 9:23
-
$\begingroup$ @gnasher729: the reason usually driving the use of $f>2$ factors are (A) speed of the private key operation (using the CRT method) for a given public modulus size : when modular multiplication with $b$-bit arguments has cost proportional to $b^2$, the speedup is by a factor $f^2/4$, that is over a factor of two for $f=3$; and (B) allowing to work around a limitation on $b$ in the hardware doing fast modular arithmetic, which for a given public modulus size operates with arguments of size inversely proportional to $f$. $\endgroup$– fgrieu ♦Apr 19, 2020 at 12:20