1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ From that, we got : "GCD(e,phi(n)) = 65537" Could you give more details??? $\endgroup$ – Ievgeni Jul 17 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 Jul 17 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 Jul 17 at 20:26
  • $\begingroup$ Also such a small $p$ is a massive security risk, even for properly designed RSA. $\endgroup$ – kodlu Jul 17 at 23:31
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.