Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$.

This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ can exists with $m^e \equiv (m')^e \bmod N$.

However if we produce our $m$ like:
$$m = m_0^{e} \mod N$$
or more general
$$m = m_0^{e^{r_1}\cdot r_2} \mod N \tag{I}$$

We can always (except some special cases we ignore here) find a decryption exponent $d$ for $c \equiv m^e \mod N$
$$d \equiv e^i \equiv e^{\phi(\phi(N))-1} \mod \phi(N)$$
with
$$c^d \equiv (m^{e})^d \equiv m^{\displaystyle e^1\cdot e^{{\phi(\phi(N))-1}}} \equiv m^{\displaystyle e^{{\phi(\phi(N))}}} \equiv m \mod N$$

Of course this message $m$ could not transmit much of the target information. Some low bit information could be transmitted by generating random $m$ until the first bits carry the target info. Not efficient at all but that's not important here.

The question is would it be (much) easier for an adversary to find the decryption exponent $d$ for such $e$?

If $\gcd(e,\phi(N))\gg 1$ is known the factorization of $N$ can get much easier and with this break the security of RSA.

**Q1:** But what happen if $\gcd(e,\phi(N))\gg 1$ is **not** known? To ensure that we pick an $e$ which is hard to factorize.

Has an adversary still a big advantage of just knowing $\gcd \ne1$ ?

It could heavily depend on the chosen factors.

We assume here (target use case)
$$N = P \cdot Q$$
$$P = 2 \cdot p_s \cdot p_b +1$$
$$Q = 2 \cdot q_s \cdot q_b +1$$
$$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b$$
$$e = (2^2 \cdot p_b \cdot q_b) \cdot e_b > 2^{3000} \text{ (hard to factorize)}$$
$$\gcd(e,\phi(N))=2^2\cdot p_b \cdot q_b = 2^2\cdot (2\cdot 3\cdot b_0+1) \cdot (2\cdot 3\cdot q_0+1) = B$$
$$B > 2^{2000} \text{ (hard to factorize)}$$
$$\phi(\phi(N)) = 2^3 \cdot 3^2 \cdot \phi(p_s) \cdot \phi(q_s) \cdot (q_0\cdot b_0)$$
$$\phi(p_s) \cdot \phi(q_s) /4= S \approx 2^{200} \ll B$$
(in target use case $p_s,q_s$ have the form $p_s = 2\cdot p_1\cdot p_2 \cdot p_3+1$)

(all variable prime factors are unique)

$e$ need to be a square of a primitive root modulo $p_s$ and $q_s$.

With this we can produce $S$ different values with $m^{e^i} \bmod N$. Depending on starting $m$ we get 4 disjoint sets of that size (plus some smaller special cases we ignore here).

The additional factor $e_b$ is needed to hide the relation to $\phi(N)$ and $B$. With this $e\gg N$ here.

We assume the adversary does also know $S$ including it's prime factorization.

**Q2:** The use case related question also allows target values $n\ne m$ but generated like $(\text{I})$ (and known there is a solution):

Can the adversary find $i$ in $n\equiv m^{e^i} \bmod N$ with known $e,n,m,N,S$ faster than $O(p_s + q_s) \approx O(\sqrt{S})$?

This can be achieved by finding a solution for $j,k$ in $n^{\displaystyle p_s} \equiv (m^{\displaystyle {p_s}})^{e^j} \bmod N$ and $n^{\displaystyle q_s} \equiv (m^{\displaystyle {q_s}})^{e^k} \bmod N$ with step-by-step testing. Giant step can't be done as $\phi(N)$ is unknown and $e^{2^{50}}$ too big to compute without it. Or can it be done faster?

*(toy)-Example:*

Here $p_b,q_b < p_s,q_s$ are used. In target use case they will be $p_b,q_b \gg p_s,q_s$ (and all values much bigger)

$N=P\cdot Q = 6565236619157488809896588016937$

$P = 2 \cdot p_s \cdot p_b +1 = 2500987802965403$

$Q = 2 \cdot q_s \cdot q_b +1 = 2625057431856779$

$p_b = 2 \cdot 3 \cdot p_0 = 2 \cdot 3 \cdot 4547= 27283$

$p_s = 2 \cdot p_1 \cdot p_2 \cdot p_3 + 1 = 2 \cdot 2579\cdot 2963\cdot 2999 + 1=45834178847$

$q_b = 2 \cdot 3 \cdot q_0 = 2 \cdot 3 \cdot 4007= 24043$

$q_s = 2 \cdot q_1 \cdot q_2 \cdot q_3 + 1 = 2 \cdot 2819\cdot 3023\cdot 3203 + 1=54590887823$

$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b = 6565236619157483683851353194756$
$\phi(\phi(N))=2^5\cdot3^2 \cdot p_0\cdot p_1\cdot p_2 \cdot p_3\cdot q_0\cdot q_1\cdot q_2\cdot q_3$

$\phi(\phi(N)) = 3282361465954844745126356151456$

Exponents $e,d$ only have a single additional big factor to make factorizing hard.
$e = 3681846424601561452716738001396 = 2^2 \cdot p_b \cdot q_b \cdot 1403217197574083942221 $

$d = 1568810657844451193145575929268 = 2^2 \cdot p_b \cdot q_b \cdot 597901661545558066493 $

Here $B<S$ but in target use case $B \gg S$
$S = p_1\cdot p_2\cdot p_3\cdot q_1\cdot q_2\cdot q_3 = 625532128948867853353$

$B = 2^2 \cdot p_b \cdot q_b = 2^2 \cdot 27283 \cdot 24043=2623860676$

The adversary would know $N$,$e$,$S$ including the factorization of $S$. But he doesn't know the factorization of $N,e,B$.