Skip to main content
1 of 2
poncho
  • 150.7k
  • 11
  • 230
  • 369

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 plaintext is to compute:

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

where:

  • $C$ is the ciphertext
  • $d = e^{-1} \bmod \lambda / e$
  • $L = (1 + k\cdot q)^{\lambda/e} \bmod n$, where $k$ is an integer such that $L \ne 1$ (and any such value $L$ works)
  • $\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.

poncho
  • 150.7k
  • 11
  • 230
  • 369