2
$\begingroup$

Given $k\phi(p)$, is it hard to recover $p$? Here, $p$ is a large prime, $\phi(\cdot)$ is Euler's totient function and $k$ is an unknown integer.

Or what's the complexity to recover $p$ from $k \phi(p)$.

$\endgroup$
  • $\begingroup$ Is this RSA related? Is $k$ the $k$ in $e*d_p = 1 + k(p-1)$ as in the CRT version of RSA ? $\endgroup$ – Ruggero May 8 '15 at 8:07
  • $\begingroup$ Yes. something like this. $\endgroup$ – Paradox May 8 '15 at 13:19
  • $\begingroup$ My answer assumed that the attack has no other information on either $k$ or $\phi(p)$; if he knows (for example) $pq$ and $k\phi(p)$, it's easy to recover $p$. $\endgroup$ – poncho May 8 '15 at 16:06
4
$\begingroup$

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?" It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of possibilities; we will consider it success if that attacker can create such a list with the correct value on it somewhere.

The answer would depend on how big $k$ (and $p-1$) is (and, how big the product is). If either is small (say, no more than 100 or 200 bits), or alternately smooth (that is, consists of prime factors that are small), then ECM would be able to pull out $k$ (or $p-1$), giving the attacker a good guess. In addition, if both have large factors, but the product is sufficiently small, then NFS would be able to factor the product. However, if both have large primes as factors, then it is unlikely to be feasible to recover $p$.

However, the above assumes that the attacker has no further information about either $p$ or $k$; if he (for example) also knows the value $pq$ (for a large prime $q$), then it is easy for him to derive $p$; he selects a random value $a$, and computes $gcd( pq, a^{k\phi(p)}-1 \bmod pq )$; with high probability, that's $p$ (assuming $k$ is unrelated to $q$; if the value of $k$ is (say) a multiple of $q-1$, then there are other ways to recover $p$ and $q$.

$\endgroup$
  • $\begingroup$ So based on your answer, my understanding is if both k and p-1 have large prime factors, then it is hard to recover p (e.g. it is safe) . Otherwise, the attacker can generate a list with the correct value on it somewhere. Thus the attacker can have a good guess of the value of p. Then is it possible to derive the probability that the attacker can recover p? For example, given that k and (p-1) have m and n prime factors, then derive the probability of recovering p in terms of m and n. $\endgroup$ – Paradox May 8 '15 at 3:09
  • $\begingroup$ No. ${}{}{}{}\;$ $\endgroup$ – user991 May 8 '15 at 4:34
2
$\begingroup$

If you know a multiple of $p$ and $k$ is smaller than $\sqrt(p)$ than you can use a different approach than the one by poncho.

Note: knowing a multiple of $p$ is the typical case of RSA where you know the modulus $N$ made by $p\times q$, so if your question refers to RSA you are left only with the constrain on the size of $k$.

The method you can use is an adaptation of Coppersmith's Method devised by Alexander May in New Partial Key Exposure Attacks on RSA but better described in Theorem 10 of his PhD thesis.

May's theorem states:

Let $N = pq$ with $p > q$. Furthermore, let $k$ be an (unknown) integer that is not a multiple of $q$. Suppose we know an approximation $\widetilde{kp}$ of $kp$ with $|kp-\widetilde{kp}| \leq 2N^\frac14$. Then we can find the factorization of $N$ in time polynomial in $\log N$

Note that you have $\widetilde{kp} = k(p-1) = kp -k$ which is an approximation of $kp$ with error equal to $k$. Therefore as long as $k \leq 2N^\frac14$ you can find $p$ in polynomial time following May's theorem.

A practical note: while the bound on $k$ translates into "the bitsize of $k$ should at maximum equal to half of the bitsize of $p$", in practice it is much better to have the bitsize of $k$ smaller than that bound by 10 to 30 bits (depending on modulus size) to be able to compute the LLL basis reduction in reasonable time (seconds compared to days).

If the unknown $k$ in your question refers to the CRT-RSA equation: $ed_p = 1 \mod(p-1) = 1 +k(p-1)$ than you can upper bound $k$ with $e$ whose size is known.

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