Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$ so I can calculate $r\cdot s - 1 = k\cdot\phi(N)$.
Actually, we have $r \cdot s - 1 = a / b \cdot \lambda(N)$, where $\lambda(N) = \text{lcm}(p-1, q-1)$, and $b$ is likely to be small if $g$ was chosen randomly (example what can happen if $g$ is not chosen randomly, consider $g=h=r=s=1$).
With that, here is a randomized procedure that will find the factorization of $n$ with decent probability if $b$ is not too large:
Compute $z \cdot 2^{\ell}= r \cdot s - 1$ with $z$ odd
Select a random value $u$ and compute $v = u^z \bmod n$; if $v = 1$ or $v = n-1$, this iteration fails to find the factors; try again with another value of $u$
For $\ell$ times,
Compute $w = v^2 \bmod n$.
If $w = 1$, then this iteration succeeds, the factors are $\gcd( v-1, n)$ and $\gcd(v + 1, n)$
If $w = n-1$, then this iteration fails, try again with another value of $u$
Set $v := w$
If we went through $\ell$ loops without hitting 1 or $n-1$, this iteration fails to find the factors, try again with another value of $u$.