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



Recovering $\Phi(n)$ from a multiple?
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.


