Recovering $\Phi(n)$ from a multiple?

Question

I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn't recall the reason for, nor original source of.

Given an unfactored $n=pq$, computing $\phi(n)$ is as hard as finding $p,q$; this is the key idea of various "RSA-like" cryptosystems. One presented had a step in which for a secret $k$ and a random $t$, $k-t\phi(n)$ is transmitted. The claim was then that this process should only be applied once, as if an attacker sees $k-t\phi(n)$ and $k-u\phi(n)$ then they can recover $(t-u)\phi(n)$, and it's alleged that this makes it easier to compute $\phi(n)$.

So my question is, why is it easier to compute $\phi(n)$ given a random multiple of it, assuming we're at "cryptographic size"? (that is, $p,q$ sufficiently large that it's not feasible to try and factor $n$ and $\phi(n)$)

Answer 1

While I cannot immediately see an easy way to find Φ(n) from (t-u)Φ(n), assuming t-u is also of "cryptographic size" of course, an attacker will probably not have to.

Depending on how RSA-like the cryptosystem is, knowing a multiple of Φ(n) might well be enough to decrypt. After all, given the public exponent e, the private key in RSA is only an integer d with the property that ed = 1 mod Φ(n). Knowing (t-u)Φ(n) will allow the attacker to find an integer d satisfying ed = 1 mod (t-u)Φ(n) as long as gcd(t-u,e)=1. This d will also satisfy ed = 1 mod Φ(n), so it will work as a private key.

Answer 2

If you know an even $m$ such that $a^m \equiv 1 \mod n, (a,n)=1$, e.g. a multiple of $\phi(n)$ then there is a standard probabilistic algorithm to factor $n=pq$. Write $m = 2^rs$ with $s$ odd. Pick a random $a$ and compute $a^s, a^{2s}, a^{4s},\ldots$. If $a^s \ne 1 \mod n$, then at some point in the calculation, you find $b \ne 1 \mod n$ with $b^2 \equiv 1 \mod n$. If $b \ne -1 \mod n$, then, as $b^2-1=(b-1)(b+1) \mod n$, you factor $n$ by computing $(b-1,n)$. This will succeed with probability $> 1/2$, so if it fails, pick another $a$. By picking enough $a$'s, you make the probability of success as close to $1$ as you like.

Answer 3

I also don't see how to recover Φ(n) from (t-u)Φ(n). However, if you do the step in question a third time with the same k and a random v, then you can compute (t-u)Φ(n) and (t-v)Φ(n), and taking a gcd will very likely give you Φ(n) or a small multiple thereof.