Key generation on rebalanced RSA-CRT

Question

Key Generation Method: Take $s \le n/2$ bits.

1. Generate two distinct random $n / 2$-bit prime numbers $p$ and $q$ with $\operatorname{gcd}(p-1, q-1)=2$ and calculate $N= p*q$;
2. Generate two $s$-bits random numbers $d_p$ and $d_q$,
   such that $\gcd(d_p, p-1)=1$, $\gcd(d_q, q-1)=1$
   and $d_p= d_q \bmod p-1$.
3. Calculate one $d$ such that $d= d_p \bmod p-1$ and $d= d_q \bmod q-1$.
4. Calculate $e=d^{-1} \bmod \varphi(N)$,
   Public key= $(N, e)$,
   Private key= $(p, q, d_p, d_q)$.

On the 3rd step of key generation, do I need to select between $d= d_p \bmod p-1$ and $d= d_q \bmod q-1$ or do I make the $d_p$ and $d_q$ to make same $d$ result?

It is okay to use small prime because I use $p = 41$ and $q = 59$ for study purposes.

Please help me to find the $d$.

Answer 1

The paper on which the question is based describes Rebalanced RSA-CRT with $d_p=d_q\bmod(p-1)$ as stated in the question's step 2, but is wrong in doing so. Notice that when $s<n/2$, that condition implies $d_p=d_q$, and that goes squarely against generate two $s$-bits random numbers $d_p$ and $d_q$ also in step 2 (further step 3 can become $d=d_p$, ans $d$ is $s$-bit only).

That's confirmed by looking at the paper's source: M. J. Wiener's Cryptanalysis of RSA with short secret exponents (IEEE ToIT, 1990), which section 8 open problems states [emphasis added]:

A useful technique for reducing the secret key exponentiation time is to take advantage of the knowledge of $p$ and $q$ (rather than just the product $pq$). Using this technique, two half-sized exponentiations are performed. The first exponentiation gives the result modulo $p$ using exponent $d_p=d\bmod(p-1)$, and the second gives the result modulo $q$ using exponent $d_q=d\bmod(q-1)$. These two results can be combined easily using the Chinese Remainder Theorem to obtain the final result modulo $pq$. One could reduce the secret key exponentiation time further by choosing $d$ so that $d_p$ and $d_q$ are short. An interesting open problem is whether there is an attack on RSA when $d_p$ and $d_q$ are short, but not equal.

Wiener clearly knew that short $d_p=d_q$ would be unsafe (his paper conclusively proves it when $s\le 0.125n$).

I thus suggest that the key generation procedure for Rebalanced RSA-CRT should be:

1. Generate two random $n/2$-bit primes $p$ and $q$ (that are nearly certainly distinct for sensible choice of $n$), optionally such that $\gcd(p-1,q-1)=2$ ;
   calculate $N=p\cdot q$ (which will be $n$-bit or one bit less).
2. Generate two $s$-bits random integers $d_p$ and $d_q$ (that are nearly certainly distinct for sensible choice of $s$), such that $\gcd(d_p, p-1)=1$ and $\gcd(d_q, q-1)=1$.
3. Calculate (using the CRT) one $e$ (possibly: the lowest) such that $e\equiv d_p^{-1}\pmod{p-1}$, $e\equiv d_q^{-1}\pmod{q-1}$, and $0<e<(p-1)(q-1)$.
   [or we could explicitly compute $d$ then deduce $e$ as in the question]
   Public key = $(N,e)$,
   Private key = $(p,q,d_p,d_q)$.

but I caution against using it:

• We know that it would be insecure to use $s<0.146n$, thanks to D. Boneh and G. Durfee's Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$ (first version in proceedings of Eurocrypt 1999)
• These authors caution the bound could further be improved to $d<N^{0.5}$, thus $s<0.25n$; so we should probably stick to prudently larger $s$, and a conservative Rebalanced RSA-CRT is thus bound to a speed improvement smaller than a factor of two.
• Further, when using RSA-CRT (rebalanced or not) to compute $x\to x^d\bmod N=y$ , it is customary and useful to check that $y^e\bmod N=x$ in order to guard against fault injection; in which case having a large $e$ (as in Rebalanced RSA-CRT) much more than offsets any speed gain achievable by lowering $d_p$ and $d_q$.

Example with $n=40$, $s=13$ (which are too small to be sensible choices)

1. $p=768941$, $q=825443$, $N=634716965863$
   
2. $d_p=4231$, $d_q=6779$
   
3. $d_p^{-1}\bmod(p-1)=634271$, $d_q^{-1}\bmod(q-1)=670801$
   $e=303057573891$.

Answer 2

Since in your construction, $\gcd(p-1,q-1) = 2$, one has $\lambda(N) = (p-1)(q-1)/2$. Private decryption key $d$ is defined modulo $\lambda(N)$. The condition $\gcd(p-1,q-1)=2$ implies that at least $(p-1)/2$ or $(q-1)/2$ is odd. In what follows, we assume without loss of generality that $(q-1)/2$ is odd.

From $d_p$ and $d_q$ do the following:

1. Define $q' := (q-1)/2$ and $d_{q'} := d_q \bmod q'$ [Remember that $q'$ is supposed to be odd; reverse $p$ and $q$ if not.]
2. Define $I_{q'} := 1/q' \bmod (p-1)$
3. Compute $d = d_{q'} + q'\left[I_{q'}(d_p - d_{q'}) \bmod (p-1)\right]$

The correctness follows by observing that the so-computed $d$ satisfies $d \equiv d_{q'} \pmod {q'}$ and $d \equiv d_p \pmod {(p-1)}$ since $q' \cdot I_{q'} \equiv 1 \pmod {(p-1)}$.

---

Example. With $p=41$ and $q = 59$, we have $q' = 29$ and $I_{q'} = 29^{-1} \bmod 40 = 29$. Hence, $d = d_{q'} + 29\left[29(d_p - d_{q'}) \bmod 40\right]$ where $d_{q'} = d_q \bmod 29$.

Answer 3

For RSA key generation, one usually first selects $e$ and generates primes $p$ and $q$ such that $\gcd(e,p-1)=\gcd(e,q-1) = 1$. The advantage of doing so is that one can use a small value for $e$. Common values for $e$ are $e = 3$, $e = 17$, or $e = 2^{16}+1$.

If you insist to first generate the decryption key then, upon generation of primes $p$ and $q$, you need to choose a random $n$-bit integer $d$ such that $\gcd(d, p-1) = \gcd(d,q-1) = 1$. Next, define $d_p := d \bmod (p-1)$ and $d_q := d \bmod (q-1)$.