Diffie Hellman (work out b)

Question

This is the question in full. Suppose that p − 1 = 2rs, where r and s are primes, both fairly close to p p/2 (but r doesn't equal s). Somehow Eve has found out the value of b mod r and mod s. Can she find out what b is? If so, how?

Answer 1

Yes, Eve can find $b$. Let's make sure we're on the same page, though, by clearly declaring the problem.

Alice and Bob have publicly declared the prime $p$ and a primitive element (generator) $g$ for the multiplicative group $\mathbb{Z}_p^*$. Alice chooses an integer power $a$ in secret, and Bob does the same choosing $b$. Alice computes $A= g^a \mod p$ and Bob computes $B= g^b \mod p$, and they both exchange the results of their computations (but not $a$ or $b$). Eve the eavesdropper sees all of their transmissions.

The point is that--by Euler's Theorem--their choices of exponents only matter mod $\varphi(p)$. But $\varphi(p)=p-1$, and your problem tells you something very strong about this. Eve knows $b \mod r$ and $b \mod s$, and $r$ and $s$ are distinct primes, so Eve can use any simple implementation of the Chinese Remainder Theorem and recover $b \mod 2rs$. Since this is also $b \mod p-1$, Eve has recovered $b$ and hence the secret key.

In this attack, she may not recover Bob's $b \in \mathbb{Z}$, but by my remarks above it doesn't matter. Getting $b$ right up to multiples of $p-1$ is good enough.