I'm trying to reverse engineer a key exchange protocol which is based on the Diffie-Hellman key exchange scheme and faced with the following problem:

Let $g$ be the generator, $m$ the modulus.

Alice has a private key $a$ and computes her public key $A = g^a\pmod{m}$.
Bob has a private key $b$ and computes his public key $B = g^b\pmod{m}$.

During exchanges Bob generates password check signature:

• $C = f(A,B,password)$ where $f$ is cryptographic hash function.
• $D = f(m,g,password)$
• $X = \left(\left(D+A\right)\pmod{m}\right)^\left(C+b\right)\pmod{m}$

and then sends $f(X)$ to Alice.

Alice calculates $X$ on her side without $b$ and I can't figure out how.

Could somebody help me with the algorithm on Alice's side?

• Is my interpretation of "You don't know what $\hspace{.02 in}f$ is and hope that something about $\hspace{.02 in}f$ can be $\hspace{.9 in}$ worked out from the fact that Alice can calculate X" correct? $\;$ – user991 Jun 10 '13 at 8:24
• No, I know that $f$ is a cryptographic hash function e.g. sha1, and I'm sure that Alice can calculate X, but she doesn't know b and Bob doesn't send value of X he sends $f(X)$. I think $X = f_1(K,password)$ where K is the shared secret between Alice and Bob. They both know K and password, so there must be an expression equivalent to X on the Alice's side. – dr.g100k Jun 10 '13 at 12:36
• it maybe that: $X \equiv (DA)^{C+b} \pmod{m}$, then it can be rewritten $X \equiv g^{(d+a)(C+b)} \pmod{m}$, so Alice can get $X$ by this way $X \equiv (g^CB)^{d+a}\pmod{m}$ , you can check that – T.B Sep 3 '13 at 1:17