# How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?

Here is some information we got :

We know the value of $$n$$, with size $$1043$$.

We know the value of $$p$$ (size $$20$$) and $$q$$ (size $$1023$$) as the factors.

$$e = 65537.$$

$$\varphi(n)$$ = $$(q-1)(p-1)$$

When I calculated $$\gcd$$ and $$\text{modinv}$$, I got :

$$\gcd(e,\varphi(n)) = 65537$$

$$modinv(e,\varphi(n)) = 1$$

So we can tell that they are not relatively prime.

So, how to compute the d, and get the value of m?

I'm not that good with math, so I cant understanding well the theory.

so can anyone please make an example implementation or write a clear formula?

• From that, we got : "GCD(e,phi(n)) = 65537" Could you give more details??? Jul 17, 2020 at 14:21
• so we calculate phi(n) from (p-1)*(q-1). e is 65537, when i calculated GCD(e,phi(n)) it returns 65537 Jul 17, 2020 at 14:50
• Welcome to crypto-SE. If $\gcd(e,\varphi(n))\ne1$, then $e^{-1}\bmod\varphi(n)$ is undefined. Thus some of the calculated stuff is wrong. Hint: use the given that $p$ has size 20 (I guess that's bits) to factor $n$.
– fgrieu
Jul 17, 2020 at 20:26
• Also such a small $p$ is a massive security risk, even for properly designed RSA. Jul 17, 2020 at 23:31

Well, if we assume that:

• $$e$$ is prime (65537 is)
• Only one of the primes minus one has $$e$$ as a factor; for example, $$p-1$$ is divisible by $$e$$, but $$q-1$$ is not. For this discussion, we'll assume that $$p$$ is the prime with $$p-1 \equiv 0 \bmod e$$ (which might happen to be the size 1023 factor for you)
• $$p-1$$ is not divisible by $$e^2$$
• That the ciphertext was actually generated by computing $$P^e \bmod n$$ for some plaintext value $$P$$.

Then, one way to derive the possible plaintexts is to compute:

$$C^d \cdot L^i \bmod n$$

where:

• $$C$$ is the ciphertext
• $$d = e^{-1} \bmod \lambda / e$$ . This is well defined, as $$\lambda/e$$ is an integer which is relatively prime to $$e$$.
• $$L = k^{\lambda/e} \bmod n$$, where $$k$$ is an integer such that $$L \ne 1$$ (and any such value $$L$$ works); most values of $$k$$ work
• $$\lambda = (p-1)(q-1)/\gcd(p-1, q-1)$$
• $$i$$ is any integer $$0 \le i < e$$

Now, if we iterate over the possible values of $$i$$, this will give $$e$$ possible values for the plaintext (unless $$C$$ happens to be a multiple of $$p$$). The original plaintext will be one of these values. All these values, when raised to the power $$e$$, will result in the ciphertext, hence we cannot distinguish from the ciphertext which one it is.

• How do things change if (p-1) is divisible by e^2 Oct 15, 2021 at 1:09
• @Michael: it gets ugly; considerably more analysis than I felt like doing would need to be applied to get an answer... Oct 17, 2021 at 2:29