RSA with 3e≡1 (mod p−1) and 5e≡1 (mod q−1)

Question

Consider RSA with $p$ and $q$ large distinct secret safe primes in interval $\bigl(2^{(n-1)/2},\,2^{n/2}\bigr)$, and private key $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ computed as $$\begin{align} N&=p\;\!q\\ d_p&=3\\ d_q&=5\\ u&=p-1\\ v&=(q-1)/2\\ d&=u\;\!\left((d_q-d_p)\;\!(u^{-1}\bmod v)\bmod v\right)+d_p\\ e&=d^{-1}\bmod(u\;\!v)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$$

For usual RSA key size (e.g. $n=2048$) and classical computers, does knowledge of the public key $(N,e)$ allow to factor $N$, or otherwise break the RSA assumption that given $x^e\bmod N$, finding $x$ is hard for integer $x$ drawn uniformly at random in the interval $[0,N)$ ?

---

If not, this variant of RSA is attractive because the low $d_p$ and $d_q$ allows to perform the RSA private-key operation using the CRT-based method with only 7 multiplications and 6 modular reductions with ⌈n/2⌉-bit parameters. This would have practical applications for parties with low computing power (e.g. an RFID chip): combined with standard RSA for the more powerful party's public key, that would allow mutual public-key authentication with record-low computing effort by the less powerful party.

The keys are conforming to PKCS#1 and compatible with many existing implementations. The public keys are only remarkable for their high $e$, thus public-key certificates are readily obtainable from the many vendors that allow $e$ in RSA public key certification requests to be up to n-2.

When using the standard RSAES-OAEP for encryption and RSASSA-PSS for signature, it appears that the basic fault injection attack in one of the two exponentiations modulo $p$ or $q$ is not to fear.

---

If this is unsafe [update: it is!], can we save most of the idea, e.g. with $e=d^{-1}\bmod(u\;\!v)+u\;\!v$, or (at the expense of PKCS#1 conformance) to $e=d^{-1}\bmod(u\;\!v)+n\;\!u\;\!v$, or/and by making $d_p$ and $d_q$ secret but still small (and distinct)?

Credit: that later variant was considered by Michael J. Wiener in Cryptanalysis of Short RSA Secret Exponent (published in IEEE Transactions in Information Theory, Vol. 36, N° 3, May 1990), with security stated as an open problem.

---

_{I hereby put in the public domain whatever novelty there is in the present post, and grant every legal entity a free, worldwide, perpetual, nonexclusive license to use such novelty.}

Answer 1

This is a very bad idea.

Given a ciphertext-plaintext pair $c,m$ I compute $\mathrm{GCD}(c^3-m, N)=p$.

Keeping small but secret $d_p$ and $d_q$, they'd still need to be too large to exhaust over. For 128-bits of security then, you'd probably want $d_p$ and $d_q$ of 128-bits. This does offer some savings over vanilla CRT, but perhaps not enough.