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:
- 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<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)
- $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$.