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

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.

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.
• Beside, we can compute the necessary $(c,m)$ pair from the public key as $m=2$, $c=2^e\bmod N$. Adding multiples of $u\;\!v$ to $e$ is of essentially no help. I was not trusting that it could be safe for public $d_p$, $d_q$, but could not spot that attack immediately. It would still make a nice CTF. And Wiener's open problem of how big secret distinct $d_p$, $d_q$ need to be remains open. It seems to allow a factor of 8 saving compared to standard 2048-bit RSA, making it sort of competitive with standard ECC.
• My earlier comment about smooth $d_p$ and $d_q$ does not apply. I'm also not sure if Wiener's attack can be leveraged. It relies on a continued fraction approximation to $e/N$ with denominator divisible by $d$. In this case we seem to need a continued fraction for $e/p$ with denominator divisible by $d_p$, which I shouldn't be able to compute. Commented Feb 13 at 10:59