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

Question

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?

Answer 1

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.