Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)? 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&lt;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:


she secretly chooses a random odd $f$ with $3\le f&lt;2^{b/2}$; 
she secretly chooses random primes $p$ and $q$ with $2^{(b-1)/2}&lt;p&lt;q&lt;2^{b/2}$, $\mathtt{GCD}(p-1, f)=1$ and $\mathtt{GCD}(q-1, f)=1$;
she computes $n=p·q$;
she computes $e=f+(p-1)·(q-1)$;
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}&lt;e&lt;n&lt;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.
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.