Join Log in
Score:1
Manc avatar Crypto

Factors calculation in RSA

in flag
Manc

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

90
1 + 3
rsa
fgrieu avatar
ng flag
fgrieu
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.
0
Reply
poncho avatar
my flag
poncho
@fgrieu: actually, it is usually a part of the RSA private key (swap which prime is called $p$ and which is called $q$)
0
Reply
Patriot avatar
cn flag
Patriot
@Manc You may want to consider voting up the answer that you accepted.
0
Reply
Score:1
poncho avatar Crypto
my flag
poncho

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

0 + 1
Manc avatar
in flag
Manc
Thanks a lot for your help!!❤
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.