Factoring a Multiprime Modulus N with Random Bits

Abstract

In 2009, Heninger and Shacham presented an algorithm using the Hensel’s lemma for reconstructing the prime factors of the modulus $N = r_1r_2$. This algorithm computes the prime factors of N in polynomial time, with high probability, assuming that a fraction greater than or equal to 59 % random bits of its primes $r_1$ and $r_2$ is given. In this paper, we present the analysis of Hensel’s lemma for a multiprime modulus $N = \prod ^u_{i=1}r_i$ (for $u\ge 2$) and we generalise the Heninger and Shacham’s algorithm to determine the minimum fraction of random bits of its prime factors that is sufficient to factor N in polynomial time with high probability.

R.C. Villena—Supported by CAPES, Brazil.

1 Introduction

According to Skorobogatov [14], we know the recovery of information (bits) of the RAM can be done with a certain error due to the data remanent property of RAM and this error can be decreased by cooling techniques studied by Halderman [4]. This attack is known as cold boot attack [2] and it is able to make a copy of the DRAM used by the decryption process of an RSA cryptosystem with some private key identification techniques ([4, 11, 13]). Then, it may identify the set of correct bits of the secret key sk of the Basic RSA cryptosystem. ¹ Inspired by this attack the underlying ideas are used to identify and recover the secret key bits of a multiprime RSA cryptosystems ².

It’s widely known that the main drawback of Basic RSA cryptosystem is the relatively expensive encryption and decryption operations. It is relevant to mention there is an advantage to use more than two primes in the RSA modulus N. The decryption process is faster when it is done partially with respect to each prime modulus and then combine them using the Chinese Remainder Theorem (see [8, 12]). The more prime factors in the modulus N, the faster is the decryption process, providing a practical solution to the high cost of decryption. The advantages for performing these operations in parallel are that the number of bit operations is at most $\frac{3}{2u^3}n^3$ and the required space is only $\lg (r_i) = \frac{n}{u}$ where $n = \lg (N)$ (number of bits of modulus N) and u is the number of prime factors of N. The time and space used to perform the decryption process is lower for values u greater than 2 but the risk of the modulus N to be factored without extra information is increased [7].

As mentioned before, inspired by cold boot attacks, it was shown that if queries to an oracle for a relatively small number of bits of the secret key is given, it is possible to factor the Basic RSA modulus $N=pq$ in polynomial time with:

• $\frac{1}{4}n$ LSB (Least Significant Bits) or $\frac{1}{4}n$ MSB (Most Significant Bits) of p [3].

• a maximum of $\log \log (N)$ unknown blocks and $ln(2)\approx 0.70$ fraction of known bits of p [6].

• a fraction $\delta$ of random bits of p and q greater than or equal to $2-2^{\frac{1}{2}}\approx 0.59$ [5].

In comparison, for a multiprime modulus $N=r_1r_2...r_u$, $\frac{i}{i+1}\frac{n}{u}$ LSB or $\frac{i}{i+1}\frac{n}{u}$ MSB of $r_i$, for $1\le i \le u-1$ is required [7].

An example: to factor a 3-prime modulus N ($u=3$) the minimum requirement is:

• $\frac{n}{6}$ LSB or $\frac{n}{6}$ MSB of $r_1$, and $\frac{2n}{9}$ LSB or $\frac{2n}{9}$ MSB of $r_2$

• 0.38n fraction of bits of primes $r_1$ and $r_2$.

Hence more and more bits are required to factor a modulus N with u greater than 2.

The case that we analyzed is to factor a multiprime modulus N with a fraction $\delta$ of random bits of its primes, where $\delta$ was computed to factor N in polynomial time with high probability. Hence we show that a multiprime modulus N offers more security than a basic modulus N. Our main result is that:

• To factor the integer $N = \prod ^u_{i=1}r_i$ in polynomial time, using Hensel’s lemma, a fraction $\delta =2-2^{\frac{1}{u}}$ of random bits of its primes is sufficient.

With this result, there is a need of $\delta \ge 2-2^{\frac{1}{3}} \approx 0.75$ fraction of random bits of prime factors to factor a 3-prime modulus N. Therefore 3-prime is better, adversarially, than $\delta \ge 2-2^{\frac{1}{2}}\approx 0.59$ for a basic modulus N.

Kogure et al. [9] proved a general theorem to factor a multi-power modulus $N=r_1^mr_2$ with random bits of its prime factors. The particular cases of Takagi’s variant of RSA [15] and Paillier Cryptosystem [10] are addressed. The bounds for expected values in our cryptanalysis are derived directly, without applying their theorem.

2 Algorithm to Factor a Multiprime Modulus N

We consider an equation of integer $N = \prod ^u_{i=1}r_i$ that can be expressed as a polynomial

$$\begin{aligned} f(x_1,x_2,...,x_u) = N - \mathop \prod \nolimits ^u_{i=1}x_i \end{aligned}$$

with solution (roots) $r=\langle r_1,r_2,...r_u\rangle$. We applied the idea in Heninger and Shacham’s algorithm, to rebuild the primes $r_i$ beginning with their LSB and MSB. In others words, we can lift all roots of the polynomial $f(x_1,x_2,...,x_u) \pmod { 2^{j+1}}$ from a root of the polynomial $f(x_1,x_2,...,x_u) \pmod {2^{j}}$. Applying this scheme, we can lift from one root of polynomial $f(x_1,x_2,...,x_u) \pmod 2$ to obtain all roots of $f(x_1,x_2,...,x_u) \pmod {2^{2}}$. Then, from these roots, lift all roots of $f(x_1,x_2,...,x_u) \pmod {2^{3}}$ and so on, up to all roots for $f(x_1,x_2,...,x_u) \pmod {2^{\frac{n}{u}}}$. One of these roots is the solution for $\langle r_1,r_2,..,r_u\rangle$, because we assume N is balanced³ hence the length of its primes is of $\frac{n}{u}$ bits.

$$\begin{aligned} \langle r_1,r_2,..,r_u\rangle \in \text { roots of } f(x_1,x_2,..,x_u)\pmod {2^{\frac{n}{u}}} \end{aligned}$$

To understand the relation between a root of $f(x_1,x_2,..,x_u)\pmod {2^j}$ and the roots of $f(x_1,x_2,..,x_u)\pmod {2^{j+1}}$ we introduce below the Hensel’s lemma for multivariate polynomials.

Lemma 1

(Multivariate Hensel’s Lemma [5]). Let $f(x_1,x_2,...,x_n)\in \mathbb {Z}[x_1,x_2,...,x_n]$ be a multivariate polynomial with integer coefficients. Let $\pi$ be a positive integer and $r = (r_1,r_2,...,r_n)\in \mathbb {Z}^n$ be a solution for $f(x_1,x_2,...,x_n)\equiv 0 \pmod {\pi ^j}$. Then r can be lifted to a root $r+b\pmod {\pi ^{j+1}}$, if $b = (b_1\pi ^j,b_2\pi ^j,...,b_n\pi ^j)$, $0\le b_i\le \pi -1$, satisfies

$$\begin{aligned} f(r+b) = f(r) + \sum ^n_{i=1}b_i\pi ^j f_{x_i}(r) \equiv 0 \pmod {\pi ^{j+1}} \end{aligned}$$

where $f_{x_i}$ is the partial derivative of $f$ with respect to $x_i$, or equivalently

$$\begin{aligned} \frac{f(r)}{\pi ^j} + \sum ^n_{i=1}b_if_{x_i}(r) \equiv 0 \pmod {\pi } \end{aligned}$$

Analyzing the polynomial $f(x_1,x_2,...,x_u) = N - \prod ^u_{i=1}x_i$ with the Hensel’s lemma we obtained the following results. Let $r = (r'_1,r'_2,...,r'_u)$ be a solution for $f(x_1,x_2,...,x_u)\equiv 0 \pmod {2^j}$ where a root for $f(x_1,x_2,...,x_u)\equiv 0 \pmod {2^{j+1}}$ is defined as $r = (r'_1+2^jb_1,r'_2+2^jb_2,...,r'_u+2^jb_u)$ where $b_i$ represents a bit $r_i[j]$ such that

$$\begin{aligned} \left( N - \prod _{i=1}^ur'_i\right) [j]&\equiv \sum ^{u}_{i=1}r_i[j] \pmod {2}. \end{aligned}$$

(1)

It is an equation modulus 2. If all values $r_i[j]$ are considered as unknowns, it is an equation modulus $\pi =2$ with u variables. An equation with u variables has a total number of solutions equal to $\pi ^{u-1}=2^{u-1}$. In other words, we get a maximum of $2^{u-1}$ roots for $f(x_1,x_2,..,x_u)\pmod { 2^{j+1}}$ from a root of $f(x_1,x_2,..,x_u)\pmod { 2^{j}}$. Furthermore, if a fraction of random bits are known, this number of roots decreases, as we show below.

Let root[j] be a set of all possible roots of the polynomial $f(x_1,x_2,..,x_u)\pmod {2^{j+1}}$. root[0] is a set of single elements because the $r_i$’s are primes hence the single root of $f(x_1,x_2,..,x_u)\pmod 2$ is $\langle 1_1,1_2,..,1_u\rangle$. With the definition of root[j] we developed the following algorithm to factor a multiprime modulus N. In Algorithm 1 there are the following inputs: a big integer N, an integer u that is the number of prime factors of N. A fraction $\delta$ of random bits of the primes is known and given as $\tilde{r_1},\tilde{r_2}...\tilde{r_n}$

The algorithm begins with a set root[0] of single roots $\langle 1_1, 1_2,...,1_u\rangle$. (*) In Line 4 for each root $\langle r'_1, r'_2,...,r'_u\rangle \in root[j-1]$ we generate all permutations for bits $\langle r_1[j],r_2[j],...,r_u[j]\rangle$. The number of values of $r_i[j]$ is one only if this bit is known in $\tilde{r_i}$, otherwise there are two values, 0 or 1. Each result $\langle r_1[j], r_2[j],...,r_u[j]\rangle$ of this permutation is analyzed in Line 5 by the Hensel’s Eq. (1); it is added to the set root[j] if the equivalence is true. This procedure is done until the set $root[\frac{n}{u}]$ obtained contains the prime factors of N.

3 Behavior and Complexity of the Algorithm to Factor N

We developed a brute-force search algorithm lifting all possible roots for the polynomial $f(x_1,x_2,...,x_u)\pmod {2^{j}}$ for $1\le j\le \frac{n}{u}$. This behavior is shown in Fig. 1 where we can see the root $r=\langle r_1,r_2,...,r_u\rangle$ as a gray double circle. It was lifted in each level $j\in [1,\frac{n}{u}]$ from one root in root[0]. These roots are defined as good roots and are shown as no-color double circle. One good root in each level j always lifts the good root for the next level $j+1$. Each incorrect root is represented as a single line circle.

We know we have a number of $\frac{n}{u}+1$ good roots in all executions of Algorithm 1, but the behavior of the algorithm is determined by the number of the lifted incorrect roots. Therefore the analysis was done with respect to incorrect roots, and to do this analysis, we defined the following random variables:

• Let G be the random variable for the number of incorrect roots lifted from a good root.

• Let B be the random variable for the number of incorrect roots lifted from an incorrect root.

• Let $X_j$ be the random variable for the number of incorrect roots lifted at level j.

Fig. 1.

(Factoring N) Behavior of Algorithm 1 to factor N

3.1 Number of Incorrect Roots Lifted from a Good Root (G)

All cases that may occur are described in the following Table where we have one good root $\langle r'_1,r'_2,...,r'_u\rangle$ of $root[j-1]$ and let’s define h as the number of unknown bits in $\langle r_1[j], r_2[j],...,r_u[j]\rangle$.

Table 1. (Factoring N) Number of incorrect roots lifted from a good root.

There are h cases ($1\le h\le u$ in Eq. (1)). It is an equation modulus 2 with h variables where the number of solutions is $2^{h-1}$. Hence we get a total of $2^{h-1}$ roots for root[j]. In the case $h=0$ we obtain a single root and it is the good root of root[j] because it is built from the good root of $root[j-1]$ and all known bits are of the correct root. But we do not have the number of incorrect roots that were lifted. The number of incorrect roots lifted are in the third column of Table 1 and are the values of the second column decreased by 1 (because the good root in root[j] is always lifted by the good root in $root[j-1]$). Therefore we can define the expected value of G as follows:

$$\begin{aligned} \mathbb {E}[G]&= \sum _{h=1}^{u}(2^{h-1}-1)\left( {\begin{array}{c}u\\ h\end{array}}\right) (1-\delta )^{h}\delta ^{u-h} \end{aligned}$$

(2)

where the probability of occuring h unknown bits in a set of u bits is $\left( {\begin{array}{c}u\\ h\end{array}}\right) (1-\delta )^{h} \delta ^{u-h}$.

3.2 Number of Incorrect Roots Lifted from an Incorrect Root (B)

Before computing the number of incorrect roots lifted from an incorrect root let’s define $c_1$ as the computed value of

$$\begin{aligned} c_1 = \left( N - \mathop {\prod \limits _{i=1}^{u}}r'_i\right) [j] \end{aligned}$$

from the good root in $root[j-1]$. With this definition, we can observe two kinds of incorrect roots in $root[j-1]$: either the computed value of $\left( N - \prod _{i=1}^ur'_i\right) [j]$ is equal to $c_1$ or is different from $c_1$ (denoted by $\overline{c_1})$. Considering all this, we analyzed all cases for computing the number of incorrect roots lifted from an incorrect root in the next Table.

Table 2. (Factoring N) Number of incorrect roots lifted from an incorrect root.

The cases where $1\le h \le u$, the values $c_1$ and $\overline{c_1}$ are not important because in Hensel’s Eq. (1) there is a modular equation of h variables, and a total of $2^{h-1}$ incorrect roots. For the case of $c_1$, the incorrect root is going to act like a good root, hence for $h=0$ the incorrect root lifts an incorrect root. But in the case of $\overline{c_1}$ the incorrect root is dropped because we have a contradiction.

The computed value of $(N-\prod ^{u}_{i=1}r'_i)[j]$ in an incorrect root can be 0 or 1 with probability $\frac{1}{2}$. The probabilities are $P((N-\prod ^{u}_{i=1}r'_i)[j] = 1) = \frac{1}{2}$ and $P((N-\prod ^{u}_{i=1}r'_i)[j] = 0) = \frac{1}{2}$. In other words, the probabilities are the same because $c_1$ and $\overline{c_1}$ represent the value of one bit. Hence we have $P((N-\prod ^{u}_{i=1}r'_i)[j] = c_1)=\frac{1}{2}$ and $P(N-\prod ^{u}_{i=1}r'_i)[j] = \overline{c_1}) = \frac{1}{2}$.

Analyzing Table 2 and with the probabilities defined above, we can determine the expected value of B.

$$\begin{aligned} \mathbb {E}[B]&= \sum _{h=1}^{u}2^{h-1}\left( {\begin{array}{c}u\\ h\end{array}}\right) (1-\delta )^{h}\delta ^{u-h}\frac{1}{2}+\sum _{h=1}^{u}2^{h-1}\left( {\begin{array}{c}u\\ h\end{array}}\right) (1-\delta )^{h}\delta ^{u-h}\frac{1}{2} +\left( {\begin{array}{c}u\\ 0\end{array}}\right) (1-\delta )^{0}\delta ^{u-0}\frac{1}{2}\\ \nonumber&= \frac{(2-\delta )^{u}}{2} \end{aligned}$$

(3)

3.3 Number of Incorrect Roots Lifted at Level j ($X_j$)

The expected value of the discrete random variable $X_j$ is defined in the following recursion:

$$\begin{aligned} \mathbb {E}[X_j] = \mathbb {E}[X_{j-1}]\mathbb {E}[B]+\mathbb {E}[G] \end{aligned}$$

because the number of incorrect roots at level j is equal to the number of incorrect roots lifted from the incorrect roots at level $j-1$ plus the number of incorrect roots lifted from the only one good root at level $j-1$. And we have $\mathbb {E}[X_1] = \mathbb {E}[G]$ because at level 0 there is no incorrect root, hence we can compute the closed form as follows:

$$\begin{aligned} \mathbb {E}[X_j] = \mathbb {E}[G]\frac{1-\mathbb {E}[B]^j}{1-\mathbb {E}[B]}. \end{aligned}$$

(4)

3.4 Complexity of the Algorithm to Factor

The algorithm to factor N should run up to level $\frac{n}{u}$ and return the prime factors of N, thus the expected value of the number of incorrect roots analyzed by Algorithm 1 is defined as:

$$\begin{aligned} \mathbb {E}\left[ \sum ^{\frac{n}{u}}_{j=1} X_j\right]&= \sum ^{\frac{n}{u}}_{j=1}\mathbb {E}[X_j] \text {Property of expected value}\\&= \sum ^{\frac{n}{u}}_{j=1}\mathbb {E}[G]\frac{1-\mathbb {E}[B]^j}{1-\mathbb {E}[B]} \text {Definition (4)} \\&= \frac{\mathbb {E}[G]}{1-\mathbb {E}[B]}\sum ^{\frac{n}{u}}_{j=1}1+\frac{\mathbb {E}[G]}{\mathbb {E}[B]-1}\sum ^{\frac{n}{u}}_{j=1}\mathbb {E}[B]^j\\&= \frac{\mathbb {E}[G]}{1-\mathbb {E}[B]}\frac{n}{u} + \frac{\mathbb {E}[G]\mathbb {E}[B](\mathbb {E}[B]^{n/u}-1)}{(\mathbb {E}[B]-1)^2}. \end{aligned}$$

The equation above is exponential on n and on $\mathbb {E}[B]$ but it can be bounded as follows. For values of $\mathbb {E}[B]>1$ this function is actually exponential ($\lim _{n \rightarrow \infty }\mathbb {E}[B]^{n/u}=\infty$) but for values $\mathbb {E}[B]<1$ we get $\lim _{n\rightarrow \infty }\mathbb {E}[B]^{n/u}<1$. Therefore the expected number of analyzed incorrect roots is bounded by a linear equation on n for values $\mathbb {E}[B] <1$.

$$\begin{aligned} \mathbb {E}\left[ \sum ^{\frac{n}{u}}_{j=1} X_j\right] = \frac{\mathbb {E}[G]}{1-\mathbb {E}[B]}\frac{n}{u} + \frac{\mathbb {E}[B]\mathbb {E}[G](\mathbb {E}[B]^{n/u}-1)}{(\mathbb {E}[B]-1)^2}\le \frac{\mathbb {E}[G]}{1-\mathbb {E}[B]}\frac{n}{u} \text { for }\mathbb {E}[B] <1 \end{aligned}$$

In summary, we can factor the modulus $N = \prod ^u_{i=1}r_i$ in polynomial time, given a $\delta$ fraction of random bits of its prime factors greater than $2-2^{\frac{1}{u}}$ (by Definition (3) $\mathbb {E}[B] = \frac{(2-\delta )^u}{2}<1$) because the expected number of analyzed incorrect roots is O(n).

$$\begin{aligned} \mathbb {E}[B] = \frac{(2-\delta )^u}{2}&<1\\ (2-\delta )^u&<2\\ 2-\delta&<2^{\frac{1}{u}}\\ \delta&>2 - 2^{\frac{1}{u}} \end{aligned}$$

Some results from this analysis are, to factor in polynomial time an integer:

• $N = \prod ^2_{i=1}r_i$, $\delta \ge 0.59(2-2^{\frac{1}{2}} \approx 0.5858)$ fraction of the bits of its prime factors is needed.

• $N = \prod ^3_{i=1}r_i$, $\delta \ge 0.75(2-2^{\frac{1}{3}} \approx 0.7401)$ fraction of the bits of its prime factors is needed.

• $N = \prod ^4_{i=1}r_i$, $\delta \ge 0.82(2-2^{\frac{1}{4}} \approx 0.8108)$ fraction of the bits of its prime factors is needed.

4 Implementation and Performance

The algorithm to factor N was implemented in 300 lines of code using the program language C with the library Relic-toolkit [1] that is focused for the implementation of cryptosystems, and was executed on a processor Intel Core I3 2.4 Ghz with 3 Mb of cache and 4 Gb of DDR3 Memory.

The experiments were executed for integers N ($n = 2048$ bits) and they were the product of u primes, $2\le u \le 4$. For each value $\delta$ a total of 100 integers N were generated, and for each integer N 100 inputs with a fraction $\delta$ of bits of its primes were generated. The results of the total of 550000 experimental runs are shown in Tables 3, 4, 5 and Fig. 2.

Table 3. Results of total examined roots by the algorithm to factor $N = \prod ^2_{i=1} r_i$, 2048 bits.

Table 4. Results of total examined roots by the algorithm to factor $N = \prod ^3_{i=1} r_i$, 2048 bits.

Table 5. Results of total examined roots by the algorithm to factor $N = \prod ^4_{i=1} r_i$, 2048 bits.

With the results obtained by Heninger and Shacham in [5] we can say that the number of analyzed incorrect roots in an experiment has a low probability to surpass 1 million. In our experiments we did the same to avoid trashing, hence we canceled all experiments that surpassed one million analyzed incorrect roots.

In Tables 3, 4 and 5 we have in the second and third column the minimum and maximum analyzed incorrect roots, respectively. The fourth and sixth column contain the average number and the average time of analyzed incorrect roots in all experiments that did not surpassed one million of incorrect roots. The fifth column contains the number in all experiments that were canceled because it surpassed one million incorrect roots.

For all experiments, we obtained an average time less than 1 second to factor N. And only 305 experiments were canceled because they had over one million of analyzed incorrect roots. For the rest of experiments, the algorithm always returned the prime factors of N.

Figure 2 shows the average number of analyzed roots of our experiments to factor N with $n = 2048$ bits. We observe the exponential growth of $\mathbb {E}\left[ \sum ^{\frac{n}{u}}_{j=1} X_j\right]$ for values of $\delta$ lower than $2-2^{\frac{1}{u}}$ ($\mathbb {E}[B]>1$) for u in [2, 4].

Fig. 2.

(Factoring N) Average number of analyzed roots by the algorithm to factor $N = \prod ^u_{i=1} r_i$ where $2\le u\le 4$

5 Concluding Remarks

We designed an algorithm to factor a multiprime integer N based on Hensel’s lemma.

The statistical analysis shows that factoring a multiprime modulus N for u greater than 2 offers more security (adversarially thinking) than for $u=2$, assuming a fraction of random bits of its primes is given. Table 6 shows a comparison done for Basic, 2-power and 3 multiprime modulus N.

Table 6. Comparison of basic, 2-power and 3-primes modulus N.

Using a multi-power $N = r_1^mr_2$ allows a faster decryption process than using a basic $N = r_1^{1}r_2$. There is no advantage to factor a multi-power modulus N with random bits because for any value of $m\ge 1$ we always need a fraction $\delta \ge 0.59$ of random bits. Due to page number restrictions, our analysis and implementation results to factor a general multipower modulus $N=r_1^mr_2$ (for the cases even and odd m) with random bits of its prime factors are given in the extended version of this paper to be published elsewhere.

The advantages of using a multiprime modulus N are: the decryption is faster, and with respect to cold boot attacks, the attacker needs more than $2^{\frac{1}{u}} - 2^{\frac{1}{2}}$ fraction of random bits if a basic modulus N is used. Therefore if $u>2$, to factor N is harder but there is a limit for the value u. When u is large the modulus N can be factored without extra information using the algorithm called Number Field Sieve (NFS)⁴ or by an elliptic curve method (ECM)⁵.