I have this assignment in which I have to prove that Alice can recover the original plaintext that Bob sent using MQV. The way this goes is:

A trusted party chooses and publishes a (large) prime $p$, an elliptic curve $E$ over $F_p$, and a point $P \in E(F_p)$.

  • Then Alice chooses a secret multiplier $n_A$ and

  • calculates $Q_a = [n_A]P$. $Q_a$ is published.

  • Bob codes the plaintext in 2 integers, $m_1$ and $m_2$, and

  • generates a random integer $k$, which is the key.

  • He then calculates $R = [k]P$, computes $S =(x_s,y_s) = [k]Q_a$

    which makes $c_1 \equiv x_s m_1 \pmod{p}$ and $c_2 \equiv y_s m_2 \pmod{p}$.

  • He sends $(R, c_1, c_2)$ to Alice.

  • Finally, Alice computes

    $$T = (x_t , y_t ) = [n_A]R,$$ $$m_1 \equiv x_t^{−1}c_1 \pmod {p},$$

    and $$m'_2 = y_t^{−1} c_2 \pmod{p}$$

And I have to prove that $(m'_1, m'_2) = (m_1,m_2)$

Any help is appreciated!

New contributor
Afonso Pinto is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ Welcome to Cryptography.SE. You have dumped your HW, which is not readible. I've converted it to $\LaTeX$ MathJax. Check the edits and show your progress. HW questions are welcomed,however, we only provide some hints... $\endgroup$
    – kelalaka
    Jan 12 at 13:33
  • $\begingroup$ I don't see a hard question here other than the following the obvious. Note that $$[k]Q_a = k([n_a]Q_a) = [k n_A]Q$$ $\endgroup$
    – kelalaka
    Jan 12 at 13:57
  • $\begingroup$ Note that MQV is a key agreement scheme, therefore one must say that prove that Alice and Bob agreed on the same key! $\endgroup$
    – kelalaka
    Jan 12 at 14:18

Your Answer

Afonso Pinto is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.