1
$\begingroup$

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$.

$\endgroup$

1 Answer 1

1
$\begingroup$

One obvious factorization method be to do:

r := rand();
m_0 := r^e mod n
x := y := m_0
for (;;)
    x := x^2 * m_0 mod n
    y := y^2 * m_0 mod n
    y := y^2 * m_0 mod n
    if (gcd(x-y, n) != 1)
        gcd(x-y, n) is likely a nontrivial factor

It appears that the number of iterations used is likely to be related to the smaller of the largest prime factors $p_s - 1, q_s - 1$. Because you specified those to be small, this has a good chance to be practical.

$\endgroup$
2
  • $\begingroup$ thanks for the answer. Is it 'the smaller or the largest'? Not fully understood it yet but in some test it took $\min((p_s-1)/2,(q_s-1)/2)$ for-loops. So if the primes $p_s$ and $q_s$ have a similar size of $\approx 2^{100}$ each (and their prime factors $p_1,p_2,p_3,q_1,q_2,q_3$ a size of $\approx 2^{33}$) it would also take $\approx 2^{100}$ steps and with this $\approx O(\sqrt{S})$ as the alternative method described above. So with this it should be roundabout as secure as a 200-bit elliptic curve. Right? $\endgroup$
    – J. Doe
    Jun 3 at 1:17
  • $\begingroup$ Those techniques can be combined if (as assumed in the test case) $p_s$, $q_s$ are known by the adversary. If $m_0 = mod(m_0^{p_s}, n)$ is used the loop finish at the first iteration. So $\gcd( mod( m_0^{3}, N )-mod( m_0^{7}, N ) ) \ne 1$. To find the factor we just need to factorize $mod(mod( m_0^{3}, N )-mod( m_0^{7}, N ),N)$. This also works with other exponents. So it's very likely a easy to factorize solution can be found. $\endgroup$
    – J. Doe
    Jun 3 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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