Finding missing bits mathematicaly in a DLP situation
I suppose (for simplicity but it can be generalized I think) that the missings bits of $r$ and $s$ are the least significant bits. So, we have:
$$
\begin{array}{lll}
r = r_12^u + r_0&amp;\text{with}&amp;g^r \equiv h \pmod N \\
s = s_12^v + s_0&amp;\text{with}&amp;h^s \equiv g \pmod N,
\end{array}
$$
with $r_0 &lt; 2^u$ and $s_0 &lt; 2^v$ unknown.

Using the relation between $g$ and $h$, we can get the following relation:
$$
h^{rs-1} = 1 \mod N.
$$
The order of the multiplicative group $\mathbb Z/N\mathbb Z$ is $\varphi(N)$. Given the factorization of $N$, as in your example, this value is known and there exists $k\in\mathbb Z$ such that:
$$
rs - 1 = k \varphi(N).
$$
Let's call $x$ and $y$ the unknown part of $r$ and $s$ and we look at the precedent equation mod $\varphi(N)$ to get rid of $k$ and we have an equation in two variables:
$$
(r_12^u +x)(s_12^v + y) - 1\equiv 0 \mod \varphi(N).
$$
If the size of the unknwown part of $r$ and $s$ are not too big, then the Coppersmith technique in two variables (using lattice) may be used to recover those part. Lot of information here.