Skip to main content
3 of 3
deleted 855 characters in body

This key exchange is broken.

For this problem, let $\langle M_{0}\rangle$ denote the algebra generated by $M_{0}$.

Set $Z_{A}=X_{A}^{-1},Z_{B}=X_{B}^{-1}$. Then $M_{A}=P_{A}Z_{A},M_{B}=P_{B}Z_{B}$. In particular, $S_{B}=P_{B}Z_{B}P_{A}$.

A pseudo key is a matrix $Z_{B}^{p}$ such that $P_{B}Z_{B}^{p}\in\langle M_{0}\rangle$ and where $S_{B}=P_{B}Z_{B}^{p}P_{A}$. The affine space of all pseudo keys can be computed simply by solving a system of linear equations.

If $Z_{B}^{p}$ is a pseudo key, then $$M_{B}M_{A}=P_{B}Z_{B}P_{A}Z_{A}=S_{B}Z_{A}=P_{B}Z_{B}^{p}P_{A}Z_{A}=P_{B}Z_{B}^{p}S_{A},$$ so the secret key $M_{B}M_{A}$ is recoverable from a pseudo key $Z_{B}^{p}$ and the public information $S_{A}$.