6
$\begingroup$

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.

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Feb 12 at 9:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel S
    Feb 13 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.