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?

  • $\begingroup$ From that, we got : "GCD(e,phi(n)) = 65537" Could you give more details??? $\endgroup$
    – Ievgeni
    Commented Jul 17, 2020 at 14:21
  • $\begingroup$ so we calculate phi(n) from (p-1)*(q-1). e is 65537, when i calculated GCD(e,phi(n)) it returns 65537 $\endgroup$
    – user81147
    Commented Jul 17, 2020 at 14:50
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Commented Jul 17, 2020 at 20:26
  • $\begingroup$ Also such a small $p$ is a massive security risk, even for properly designed RSA. $\endgroup$
    – kodlu
    Commented Jul 17, 2020 at 23:31

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


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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