Score:1

RSA factorization knowing the form of p and q

lk flag

I'm wondering if knowing the form of both factors (p and q) of a RSA modulus N is a significant help for factoring or not.

For instance: p of the form 4k+3, so (p-3)%4 = 0 and q of the form 4k+7, so (q-7)%4 = 0

poncho avatar
my flag
Note that the forms '4k+3' and '4k+7' are precisely the same...
Score:4
ng flag

If $k$ is the same in the two forms, that is $n=(4k+3)(4k+7)$, factorization is trivial: $p=\lceil\sqrt n\,\rceil-2$, $q=p+4$.

Assuming the two $k$ are independent from now on: note that for odd primes $p$ of a given size, the quantity $p\bmod4$ is about evenly split in $\{1,3\}$. Thus the known form gives one bit worth of information about $p$. We get that same bit of information about $q$, but observing $n\equiv1\pmod4$ already allowed to deduce it from $p\equiv3\pmod4$. Hence the known form gives only 1 bit of information towards helping factor $n$: for a given $n$ it can at best half the work. Also about one $n$ out of four in a normal RSA modulus has this form, thus if the problem was easy for these $n$, RSA would be insecure.

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.