2
$\begingroup$

Hello fellow experts here, in order to use RSA to encrypt and decrypt in a controlled environment, we will actually need to have a list of prime numbers to do so instead of using library generated RSA keys to encrypt and decrypt.

My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers. However this process is really performance taxing (by using BouncyCastle), I was wondering if there was really any faster and efficient method to generate an infinite amount of BigInteger prime numbers that can be used for RSA?

$\endgroup$
3
  • 4
    $\begingroup$ Random question on whether this is the correct problem: do you have to use RSA? Would ECC work better for you? $\endgroup$ – poncho May 16 '20 at 13:04
  • $\begingroup$ Currently I do know that ECC is the trend in cryptography right now, but I think that i should have minimal knowledge on non ECC algorithm before i can proceed to ECC, because RSA alone already give me tons of problems, IMOO , I think ECC would be the same too. If i don't have non ECC minimal knowledge, in the future i couldn't use hybrid controlled encryption. That's why i start with the one i knew the most RSA . $\endgroup$ – Hern May 16 '20 at 14:37
  • 1
    $\begingroup$ RSA key pair generation is one of the most inefficient and complex key generation methods though. EC key pair generation is much more efficient and much easier to understand. Of course, understanding ECC itself might be harder than understanding RSA. But if you're worried about the key pair generation efficiency, you'll probably end up using ECC/ECIES anyway. $\endgroup$ – Maarten Bodewes May 16 '20 at 15:56
5
$\begingroup$

We will actually need to have a list of prime numbers

That's dangerous, since that list must be kept secret, and primes that have been used removed to avoid reuse. There's almost always a better way, like generating the primes on demand. But let's ignore that.

My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers

If two large primes $p$ and $q$ thus obtained are used to form RSA moduli $N=p\,q$ , then that modulus $N$ will be factorable in a millisecond: compute $u=\left\lceil\sqrt N\,\right\rceil$, $v=\sqrt{u^2-N}$ (which critically will be a small integer), the factors are $u-v$ and $u+v$. That's a special case of Fermat's factorization method. This works because the two primes will be overly close¹, and illustrates a more general fact: we must generate two primes forming an RSA moduli in a way such that they bear no relationship known to an attacker².

Also, in most applications, we want that revealing the factorization of a number of $N_i$ does not help factoring any other $N_j$. For this reason, it's simplest/common/best to generate the primes independently. It remains important to generate them fast.

There are several ways to generate primes in a reasonable time. A simple one improves on the method above by avoiding not only the multiples of two, but the multiples of more small primes, so that fewer candidates will be tested before a prime is found. For example, when generating a prime with $b$ bits, we would expect to test about $b\ln(2)/2$ odd integers (that's $\approx355$ for $b=1024$), per the Prime Number Theorem. But if we manage to avoid those with no divisor among the first $127$ primes (that is, the primes to $709$), we improve this by a pleasant factor of $\displaystyle\prod_{3\le s\le709\\\,s\text{ prime}}\frac s{s-1}\ \approx5.9$.

The most usual methods towards that are

  • First testing a candidate odd prime $r$ with $\gcd(r,m)=1$, where $m$ is the product of a number of small odd primes; e.g. first up to $23$, or $29$ such that $m=3234846615$ barely fits 32-bit. In one swift test, that reduces the number of prime candidates by a factor of $\approx3.17$. But if the method to test primes already does something equivalent or better, this added filtering will actually harm!
  • Sieving, essentially building a sieve of Eratosthenes localized to an interval sieved. It's effective, and often practiced. But it's a tad difficult to code and optimize³; and the basic algorithm exhibits detectable bias⁴.

There are other techniques which generate provable primes, and I'm told they are competitive from a performance standpoint. See e.g. FIPS 186-4 B.3.2 for one.


I now describe an alternative to sieving, that also avoids testing candidates $r$ with a small prime factor $s$ (though to an appreciably lower bound than possible with sieving, as noted by poncho), without an explicit sieve array, and (discounting precomputations) with less work on modular reduction of a large value modulo a small prime $s$, which sometime gives a speed advantage.

In a nutshell, we'll use the Chinese Remainder Theorem to generate candidate primes $r$ with $r\bmod e$ drawn in $[2,e)$ and $r\bmod s$ drawn in $[1,s_i)$ for other small primes $s_i$.

  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v+1)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement for $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
    • Repeat⁵:
      • If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$):
        • Test if $r$ is prime⁶, using e.g. a small number of strong pseudoprime⁷ tests to random base, and if so:
          • Output $r$ and stop.
        • If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.

Caution: It is critical to use an unpredictable randomness source, and that all quantities manipulated remain secret.


¹ The primes will be close if they have been chosen incrementally.

² Other kinds of harmful relations between primes could be: they are generated by testing integers of the form $2\,k\,a+b$ for public $a$ and random secret $b$. That could extend to random secret $a$, if there are several $N_i$.

³ Competing computational bottlenecks are the final primality test (the more small primes are sieved, the less such tests there are), and computing the offset in the sieve (which requires computing the remainder of a large value modulo each of the small primes).

⁴ If we select the smallest prime in the sieved region, it will have a gap with the previous prime larger than expected for a random prime. Selecting a uniformly random prime in the sieved region mostly fixes that, but still the selected prime will tend to have less neighboring primes than expected for a random prime. These biases are detectable when examining the primes generated, but are not a security concern in RSA.

⁵ With $(r\bmod e)\in[2,e)$, $(r\bmod2)=1$, and $(r\bmod s_j)\in[1,s_j)$ for $0\le j<i$. The product of these distinct coprime moduli is $m$. Prime candidate $r\in[k_\min\,m,k_\max\,m)$ changes by multiples of $m$, among $t$ possible candidates. $t>2^{39.9}$, which makes it beyond reasonable doubt that there's a prime among the candidates, given the upper bound for $r_\max$. The order in which we scan them is random and secret among $>2^{39.9}$ possibilities, conjecturally defeating statistical tests of non uniformity.

⁶ This is very likely, to the point of making the contrary hard to test.

⁷ In an RSA context, it is considered acceptable to restrict to primes $r\equiv3\pmod 4$. This simplifies the strong pseudoprime test to an Euler test (or otherwise said, makes the straightforward Euler test more robust). This can be obtained by $r\gets ((1-v)\,e\bmod4)\,e+v+2$ rather than $r\gets ((v+1)\bmod 2)\,e+v+2$, and $m\gets4\,e$ rather than $m\gets2\,e$ (the later occurs in two steps).

$\endgroup$
13
  • $\begingroup$ "This works because the two primes will be overly close, and illustrates a more general fact: we must generate two primes forming an RSA moduli in a way such that they bear no relationship known to an attacker." Sorry for asking but the relationship u meant here can you explain in a simple example and theory? $\endgroup$ – Hern May 16 '20 at 12:20
  • $\begingroup$ "A simple one improve on the method above by avoiding not only the multiples of two, but the multiples of more small primes, so that fewer candidates will be tested before a prime is found." I have question here, those small primes(In programming), are they BigInteger or just regular integer ? $\endgroup$ – Hern May 16 '20 at 12:31
  • $\begingroup$ "For example, when generating a prime with b=1024 bits, we would expect to test about bln(2)/2≈355 odd integers." I have questions here, the variable b is it the modulus bit count or the prime number bit count ? Does the formula "bln(2)/2≈x" applies to other big large prime numbers too or just for 1024 bits? $\endgroup$ – Hern May 16 '20 at 12:35
  • $\begingroup$ In my example, the "small primes" are noted $s$, and will comfortably fit a normal integer (even a 15-bit one like in portable C); $v$ will also. All other quantities (except perhaps $e$) are "big integers". In "a prime with b=1024 bits", we are generating 1024-bit primes for 2048-bit RSA modulus, which is considered the standard minimum nowadays. $\endgroup$ – fgrieu May 16 '20 at 14:02
  • 2
    $\begingroup$ @kelalaka: oddly nontrivial question (actually, we're talking about performance, so subtle points really aren't that odd); calculating $bignum \bmod small$ can be done quite efficiently if $small$ fits in a single word, while $\gcd( product, candidate )$ would require multiprecision ops if $product$ doesn't; it might make sense to go through your small primes in batches (where each product fits within a word); of course, not all bignum libraries support this optimization... $\endgroup$ – poncho May 16 '20 at 14:16

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.