# RSA key generation with large random numbers and no primality testing

Does the security of RSA rest entirely on the modulus having at least 2 large random primes?

Suppose you were to generate 2 random 1,000,000-bit numbers and just use the product of those as the modulus.

What are the odds that all the prime factors of the modulus be much smaller than 1,000,000 bits? And would that be sufficient to secure the scheme?

Keys, and cipher-texts would be large, also efficiency of encryption/decryption will suffer relative to real and probabilistic security level. But RSA key generation will be very cheap.

• You almost reinvented Mult-Prime-RSA Dec 15, 2023 at 9:30
• This idea was explored by Bogos, Boureanu, and Vaudenay a few years ago. It doesn't work directly for RSA, but they modify the Goldwasser-Micali scheme for this effect. The modulus size for 128-bit security becomes 66212 bits. Dec 16, 2023 at 5:44

There are two main issues with the proposal after we add that the two generated integers are odd1

• We can't compute the private key for a public key that we generate, for this requires the full factorization of the modulus. This is an issue in most practical applications: we can't decipher what's encrypted, or generate signatures that verify.
• As an aside, an RSA modulus $$n$$ must have no small prime factor $$r$$ such that $$r^2$$ divides $$n$$. One reason is that if it did, messages $$m$$ of the form $$m=k\,r$$ with integer $$k\in[1,n/r)$$ would not decipher correctly under textbook RSA; and there is probability near $$1/r$$ that a random $$m$$ is of this form, which is sizable for small $$r$$, and prevents using proper RSA with padding. That's fixable (since we can quite efficiently remove small factors from integers too large to factor entirely), but the cost of doing that with confidence is rather higher than generating primes of the same magnitude in the first place.

Update: When using textbook RSA encryption, the small factor issue is not only that a fraction of messages can't be decrypted. If an adversary manages to find a small factor $$r$$ from the public modulus $$n$$, they can find $$m\bmod r$$ from a ciphertext $$c=m^e\bmod n$$, by computing $$c^{\left(e^{-1}\bmod\left(r-1\right)\right)}\bmod r$$. That's a serious leak of information about $$m$$.

However, when we use proper RSA encryption or signature, what arguably matters is the two largest prime factors of the public modulus $$n$$. Probability that a random integer $$x$$ has it's large factor less than $$y$$ goes to $$\rho\left(\frac{\ln x}{\ln y}\right)$$ as the integers get large, where $$\rho$$ is the Dickman / de Bruijn function. Thus a 1,000,0000-bit random integer almost certainly has a factor at least 40,000-bit, with residual probability of the contrary $$\rho(25)<2^{-128.8}$$.

I conclude that if we published a public key made in the question's way, and received an RSASSA-PSS signature with 512-bit hash and MGF that verifies against it for message "I'm from the future where we have CRQC", we'd have to admit it, or that our key generator was hacked.

1 which is easy to ensure at generation, and customary because otherwise, in textbook RSA, the low-order bit of the message leaks as the low-order bit of the ciphertext.

• Can the RSA decryption failure be quantified? If you pick p and q that aren't prime and pretend that they are, will decryption fail every time or can it be something that is managed? The thing is, if it fails every time RSA encryption-decryption becomes a pair primality test, surely its not that easy?
– user113099
Dec 17, 2023 at 7:57
• @JamesArlington: I fail to immediately locate where we have a thorough discussion on that. In a nutshell, if $p$ is composite, each encryption/decryption of $m$ becomes a Fermat test of the primality of $p$ with witness $a=m\bmod p$. Thus vanishingly few plaintexts decrypt, except in the exceedingly rare case that the composite that slept thru is a Carmichael number, in which case RSA works but potentially succumbs overly easily to factorization of $n$. Notice that there are techniques to generate random and proven primes, if for some philosophical reason one does not want probable primes.
– fgrieu
Dec 17, 2023 at 10:05
• suppose we find a non-prime p,q that pass some number of Miller-Rabin tests, would the decryption failure probability be the same as a random p,q?
– user113099
Dec 17, 2023 at 18:02

An integer is not divisible by the prime $$p$$ with probability $$(1-p^{-1}).$$ Assuming your large number $$N$$ is chosen at random from numbers of the same bitlenth $$K$$ and assuming we want a number as strong as the current day RSA moduli (say 4096 bits), the probability that you get a number without a prime divisor less than say 250 bits (size of the largest RSA challenge which was factored) is approximately $$q(2^{250})=\prod_{p\leq 2^{250}}\left(1-\frac{1}{p}\right)$$ and Merten's third theorem states that $$q(x)=\prod_{p\leq x}\left(1-\frac{1}{p}\right)\sim \frac{e^{-\gamma}}{\ln x}.$$ where $$\gamma$$ is Euler–Mascheroni constant and plugging in, we get $$q(2^{2048})=\frac{e^{-\gamma}}{\ln (2048 \ln 2)}=\frac{e^{-0.577\cdots}}{\ln (0.69 \times 250 )}\approx\frac{0.56}{5.15}\approx 0.10$$

Below is for table of various bit sizes;

$$x$$ $$q(x)$$
$$2^{16}$$ 0.0506259257876265
$$2^{32}$$ 0.0253129628938132
$$2^{64}$$ 0.0126564814469066
$$2^{128}$$ 0.00632824072345331
$$2^{256}$$ 0.00316412036172665
$$2^{512}$$ 0.00158206018086333
$$2^{1024}$$ 0.000791030090431664
$$2^{2048}$$ 0.000395515045215832
$$2^{4096}$$ 0.000197757522607916
$$2^{8192}$$ 0.0000988787613039580
$$2^{16384}$$ 0.0000494393806519790
$$2^{32768}$$ 0.0000247196903259895

if I have computed correctly. This is way too small a probability to be assured of a safe RSA modulus! With the standard approach we do much better.

Even if this wasn't the case, generating such a large number as you want at random is computationally much more expensive since you need a set of good quality random or pseudorandom bits from a random number generator to generate such a large number.

Edit: As the other answer points out, the private key also cannot be determined without the full factorization of the modulus

• Shouldn't it be the probability that ALL prime divisors are less than 2048 bits for each chosen number? And generating pseudo-randomness is many orders of magnitude faster than primality testing.
– user113099
Dec 15, 2023 at 6:07
• It is enough for ONE too small divisor to ruin your approach Dec 15, 2023 at 6:26
• the second point is a bit academic Dec 15, 2023 at 6:26
• Do you have a reference that RSA is broken if any of the modulus divisors are known or weak? I was under the impression that you can pollute RSA with any number of primes you want as long as there are at least 2 large random primes.
– user113099
Dec 15, 2023 at 6:31
• @kodlu: on the other hand, the difficulty of breaking RSA with proper random padding (RSAES-OAEP with large random) arguably depends on the two highest factors of $n$. And the probability that a random 1,000,000-bit integer has no factor more than 40,000-bit is next to $\rho(25)<2^{-128.8}$, see Dickman / de Bruijn function.
– fgrieu
Dec 15, 2023 at 12:04