Is it hard to recover $p$ from $k \phi(p)$?

Question

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

Answer 1

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

Answer 2

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.