1
$\begingroup$

You are given $d\bmod(p-1)$ , $d\bmod(q-1)$ , $\operatorname{invert}(p,q)$ and $p\bmod2^{200}$, the public exponent is $e=65537$.

$\operatorname{invert}(p,q)$ is the answer of $ p*x \equiv 1 (mod\quad q)$

$d$ is the private exponent, the modulus is unknown.

Is there some way to calculate $p$, $q$?

$\endgroup$
3
  • $\begingroup$ The added information tells that $\operatorname{invert}(p,q)$ designates $p^{-1}\bmod q$. That's not $q_\text{inv}=q^{-1}\bmod p$ usually part of an RSA private key. $\endgroup$
    – fgrieu
    Jul 11, 2021 at 8:03
  • $\begingroup$ @fgrieu: actually, it is usually a part of the RSA private key (swap which prime is called $p$ and which is called $q$) $\endgroup$
    – poncho
    Jul 11, 2021 at 11:17
  • $\begingroup$ @Manc You may want to consider voting up the answer that you accepted. $\endgroup$
    – Patriot
    Jul 11, 2021 at 12:31

1 Answer 1

1
$\begingroup$

You are given $d \bmod(p−1)$.., the public exponent is $e=65537$. Is there some way to calculate $p$?

Well, we know that $d_p = d \bmod p-1$ and $e$ are related by $d_p \cdot e = 1 + kp$, for some integer $k$, and that $k < 65537$

So, do a partial factorization of $d_p \cdot e - 1$ into $a \cdot b$, where $a$ consists of factors below 65537 and $b$ has no such factors (which is quite easy). We know that $p = (a/c) b$, where $c$ is a factor of $a$; $a$ is relatively small, and so there are only a few such factors to consider. And because we know

$p \bmod 2^{200}$

It's easy to distinguish which one it is.

And, for the other half of the question:

Is there some what to calculate $q$

We can use the same trick, except using the known $p^{-1} \bmod q$ value as the distinguisher...

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your help!!❤ $\endgroup$
    – Manc
    Jul 11, 2021 at 11:54

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.