Key generation on rebalanced RSA-CRT Key Generation Method: Take $s \le n/2$ bits.


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$;
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$.
Calculate one $d$ such that $d= d_p \bmod p-1$ and $d= d_q
\bmod q-1$.
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$.
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&lt;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:


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).
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$.
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&lt;e&lt;(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&lt;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&lt;N^{0.5}$, thus $s&lt;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)


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