# Prove that the message is recoverable in MQV

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.
• 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... Jan 12 at 13:33
• 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$$ Jan 12 at 13:57
• Note that MQV is a key agreement scheme, therefore one must say that prove that Alice and Bob agreed on the same key! Jan 12 at 14:18