Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?

Question

Alice is going to use some existing RSA scheme (employing industry-standard signature or/and encryption with proper padding), which she can't change, or influence beyond her choice of key. In this scheme, all public modulus $n$ are exactly $b$ bits with $b$ even (e.g. $b=4096$); and any odd public exponent $e$ with $3\le e<e_\mathtt{lim}$ is allowed, for some $e_\mathtt{lim}$ at least $n$ (this is common; e.g. PKCS#1v2.1 uses $e_\mathtt{lim}=n$).

Contrary to standard practice, Alice would like her RSA key to have a public exponent $e$ crafted to slow down use by other parties (say, she wants to better resist some denial of service attack starting with sending her an RSA-encrypted message); but she would like to keep her own actions fast when performing a computation normally involving her public key (that includes Alice checking a signature she just generated using the CRT, as customary to guard against the mother of many fault injection attacks).

Towards these goals, Alice can generate her key as follows:

1. she secretly chooses a random odd $f$ with $3\le f<2^{b/2}$;
2. she secretly chooses random primes $p$ and $q$ with $2^{(b-1)/2}<p<q<2^{b/2}$, $\mathtt{GCD}(p-1, f)=1$ and $\mathtt{GCD}(q-1, f)=1$;
3. she computes $n=p·q$;
4. she computes $e=f+(p-1)·(q-1)$;
5. she computes $d=f^{-1}\bmod{\mathtt{LCM}(p-1,q-1)}$, or/and $dP=f^{-1}\bmod{(p-1)}$, $dQ=f^{-1}\bmod{(q-1)}$, $qInv=q^{-1}\bmod p$.

Alice's public key is $(n, e)$, made public, and her private key is $(n, d, p, q, dP, dQ, qInv)$. These are usable as customary in RSA. In particular, the construction yields $2^{b-1}<e<n<2^b$ with $e$ and $n$ odd, and thus meets the conditions required for $(n, e)$ to be acceptable in the scheme.

For a user of Alice's private key other than Alice, computing $x^e\bmod n$ for arbitrary $x$ requires over $b$ modular multiplications (more like $3·b/2$ with basic binary exponentiation), rather than $17$ modular multiplications for the customary public exponent of $2^{16}+1$. Thus Alice's goal of making use of her public key slow is largely met.

Notice that $\forall x\in\mathbb Z$, $x^e\equiv x^f\pmod n$ (proof sketch: the equality holds $\pmod p$ using Fermat's little theorem; same $\pmod q$; thus the equality holds $\bmod(p·q)$ as well). Therefore, Alice can use $f$ instead of $e$ when she wants to perform the transformation $x\mapsto y=x^e\bmod n$. Because $f$ is at most $b/2$-bit when $e$ is $b$-bit, this gives Alice a performance advantage of about a factor of $2$.

Question is, does Alice's choice of key create a risk, compared to established practice? And how can we keep (or make) that safe, and maximize the cost of computing $x^e\bmod n$ directly, and Alice's advantage over that?

Update: In particular, how much can we safely reduce the interval for $f$ at step 1? Can we make the binary expression of $f$ sparse to further speed its use by Alice? Can we increase the cost of using the public $e$? How can we use freedom given by $e_\mathtt{lim}$ when that's more than $n$? Notice each of these could improve Alice's advantage.

Update: By using a CRT form of her public key $(n, f, p, q, fP, fQ, qInv)$ with $fP=f\bmod{(p-1)}$ and $fQ=f\bmod{(q-1)}$, Alice gains an extra advantage by a factor of about $2$ (and more should we increase the number of prime factors of $n$).

Update: As pointed in the first comment, Alice must keep $f$ secret as well as $d, p, q, dP, dQ, qInv$, since knowledge of $f$ combined with $e$ reveals $(p-1)·(q-1)=e-f$, wich combined with $n$ is known to allow efficient factorization of $n$. In particular, Alice should be wary of side channel attacks such as these when computing $x^f\bmod n$, which are not to fear when computing the same value as $x^e\bmod n$ (at least when $x$ is public).

_{Note: AFAIK this is new, and hereby put in the public domain.}

Answer 1

I can't see any problems, if you use it as specified (with the performance advantage of a factor of 2).

If you start to narrow the interval too much, you're going to get into trouble. For instance, one factoring method is to compute $c=b^e \pmod n$ for some known base $b$; then try to compute the discrete logarithm of $c$ to base $b$. We know $c=b^f \pmod n$, so if $f$ comes from a small range, so we can use some algorithm for computing the discrete logarithm when the exponent is known to come from a small range (e.g., baby-step giant-step or Pollard's rho). This will reveal $f$, if $f$ comes from too small of an interval. For instance, if you pick $f$ from the range $3 \le f \le 2^{80}$, these algorithms will be able to find $f$. Once $f$ is known, $n$ can be factored, as $e-f$ reveals $(p-1)(q-1)$ which can be used to extract a factor of $n$.

Similarly, if you choose $f$ to have very low Hamming weight, I think you will again get into trouble. The baby-step giant-step and Pollard's rho algorithms can be adopted to solve the discrete log in cases where the exponent is konwn to have low Hamming weight, so the same method can be used.

For these reasons, I don't think you're going to be able to get a very large performance advantage.

And, I have to say that I would not bet much of my own money on the security of this scheme. I believe van Oorschot and Coppersmith have some results on factoring $n$ given partial knowledge of $d$ or $p$. The lesson I draw from those results is: when you start giving away partial information on RSA secrets, RSA can lose a lot of security. I don't know if that applies to your scheme, but I would be reluctant to use it in a high-stakes situation, and I would be especially reluctant to narrow the interval from which $f$ is chosen.

Answer 2

Here is my argument that the system as I proposed it is safe. I wish this could be made more rigorous.

For any RSA modulus $n=p⋅q$, it holds that $(p-1)⋅(q-1)=n+1-(p+q)$, thus $(p-1)⋅(q-1)=n+1-\sqrt{4⋅n+(q-p)^2}$, thus $$(n-2⋅\sqrt n+1)-{{(q-p)^2}\over{4⋅\sqrt n}}<(p-1)⋅(q-1)<(n-2⋅\sqrt n+1)$$ The customary $2^{(b-1)/2}<p<q<2^{b/2}$ implies ${{(q-p)^2}\over{4⋅\sqrt n}}<2^{b/2-5}$. Thus any adversary knows an interval of width less than $2^{b/2-5}$ in which $(p-1)⋅(q-1)$ lies.

With the proposed method, the adversary is given $(p-1)⋅(q-1)+f$ for an unknown randomly-chosen $f$ such that $3\le f<2^{b/2}$. That likely gives no additional information at all about $(p-1)⋅(q-1)$, and odds that it reveals the $k$ high bits of $(p-1)⋅(q-1)$ are less than $2^{-k-3}$.

That convinces me the proposed method does not allows easier factorization of $n$; and because $e$ and $f$ are exactly equivalent exponents, and publishing $f$ rather than $e=(p-1)·(q-1)+f$ would be safe, I fear no other danger.

---

The above computation suggests another, convincingly secure method to choose the key:

• choose random primes $p$ and $q$ with $2^{(b-1)/2}<p<q<2^{b/2}$;
• compute $n=p⋅q$;
• repeatedly select a random odd $e$ with $n-2⋅\sqrt n+4<e<n-2⋅\sqrt n+2^{32}$, until $\mathtt{GCD}(p-1, e)=1$ and $\mathtt{GCD}(q-1, e)=1$;
• publish the public key $(n,e)$;
• compute and use the private key $(n, d, p, q, dP, dQ, qInv)$ as customary;
• compute (and keep secret) the shortcut exponent $f=e-(p-1)⋅(q-1)$, which gives the same result as $e$, and is less than $2^{b/2-5}$, thus about 2 times more efficient.

For the slightly adventurous, choosing $p$ and $q$ with $k$ equal high-order bits allows to have $f<2^{b/2-2·k}$; AFAIK, that's safe for $k$ up to at least $80$ or $100$, perhaps even $k=b/10$ (or more if one foolishly assumed that the currently known Fermat-like-factoring attacks can't be improved, see this answer to a different question for links to some).

Answer 3

For random $f$ I don't see any risks (which doesn't mean that there aren't any), as $f$ hides the critical lower half of $\varphi = (p-1)(q-1)$ (the upper half is essential the same as $n$'s). Shorter $f$ don't feel good to me.

But if you choose $f$ sparse, then the attacker knows many bits of $\phi$ and can adapt the technique of the paper Correcting Errors in RSA Private Keys from the Crypto 2010:

Start with $\mathcal P_1 = \{1\}$ as set of possible solutions for $p \bmod 2^1$.

In a loop over $i = 2, 3, \dots$ extend the solutions in $\mathcal{P}_{i-1}$ by one bit in both possible ways to obtain double as many solutions $\mathcal{P}_i$ in each step. For each $p_i\in \mathcal{P}_i$ calculate possible approximations $q_i = n\cdot p_i^{-1} \bmod 2^i$ of $q$ and $f_i = e-(p_i-1)(q_i-1) \bmod 2^i$ of $f$. If $\mathcal{P}_i$ gets too big, discard all solutions $p_i$ whose corresponding $f_i$ have the highest Hamming weight. As $f$ is sparse, the correct $p_i$ has good chances for survival.

I do not know for which percentage of ones in the binary representation of $f$ this algorithm succeeds.

[see also the newer paper]

---

EDIT: After thinking a bit more about the problem, I started having doubts about the algorithm suggested by me. In the original from Crypto 2010 there are at least two equations that have to be fulfilled, and this redundancy makes it work. But there are some algorithms (I think D.W. refers to these in his/her answer) that have complexity about square root of brute force.

---

For the other problem of choosing $f$ small (e.g., 256 bit for a 2048-bit modulus) is not secure: From the equations $pq = n$ and $p+q = n-\varphi+1 \approx n-e$ one can simply solve the resulting quadratic equation (coming from $xq = n$ and $x + q = n-e$) to get a result for $x$ which differs from $p$ (rsp. q) by only about $2^{256+\epsilon}$ (with $\epsilon < 3$ in most cases). Knowing the upper half of the bits of $p$ (and therefore of $q$, as $q = n/p$) is enough to factor $n$ by a result from Don Coppersmith (Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, J. Crypt. 10(4), 233-60, 1997).

Answer 4

Yes, it's safe (for some definition of safe), but it will be very slow. The reason we typically use other ones is for speed. The usual exponents of 3, 5, 17, and 65537 all have the characteristic that they are primes with two one bits and other bits being zero. This means that the exponentiation will be reasonably fast.

A large random exponent would be safe, and arguably safer. I might not pick anything involving p and q, but from a strict mathematical aspect, you're just suggesting a large exponent.

Let's suppose you pick f to be any number that is b bits long. When you add it to (p-1)(q-1), you've essentially done a one-time pad encryption of that number, so why bother? Just use f.

If you pick it to be something like b/2 bits long, you're blurring (p-1)(q-1) by f, and one can find out f, then you leak (p-1)(q-1). Why do that? Why not just pick a random f? If you're concerned about leaking the state of your RNG, you can always whiten it with a PRF.

What problem are you trying to solve here? If you want a full-width exponent, do that. Generate one randomly. If you don't like your RNG to do it, then use an iterated hash or counter mode to get one. I can come up with several in my head that could work, but really, what's the problem you're trying to solve? Just to get a full-width exponent to slow things down? If that's it, then use a better generator. Here's one I throw out:

• Take your favorite hash function and generate H(p,q,pq)
• Split that hash into two, so you get a key and a counter.
• Use your favorite block cipher in counter mode to generate enough bits for your exponent.
• Make sure it meets proper form for an exponent, of course. Like being odd.

How's that?

Jon