Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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? $\;$ – Ricky Demer 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.