How can I break this encryption scheme?

Question

Let $p$ be a large public prime. Alice holds a private key $(e_1,d_1) \in Z_{p-1}^*$ such that $e_1 d_1 = 1 \mod {p-1}$. Bob also holds a different private key $(e_2,d_2)$ with the same property.

Let's say Alice wants to send a message $\large m \in Z_p^*$ to Bob:

$1.$ Alice computes and sends $\large m^{e_1} \mod p$ to Bob.
$2.$ Bob computes and sends $\large m^{e_1e_2} \mod p$ to Alice.
$3.$ Alice computes and sends $\large m^{e_1e_2d_1} = m^{e_2} \mod p $ to Bob.
$4.$ Bob decrypts by computing $\large m^{e_2d_2} = m \mod p$

Assuming Eve can read (but not modify) the messages exchanged between Alice and Bob, can she obtain any meaningful information about $\large m$ ? What happens if Alice and Bob use the same protocol to exchange multiple messages $\large m_1,m_2,...,m_t$ using the same private keys ?

Answer 1

This is the Shamir Three Pass protocol; it turns out the attacker can deduce some information about $m$; whether that information is meaningful depends on exactly what you are sensitive to.

Exactly what information is leaked turns out to depend on the factorization of $p-1$ (assuming, of course, that $p$ is large enough to make solving the discete problem infeasible); if $p-1$ has a factor $q$, the attacker can deduce the value of $m^{(p-1)/q}$ with $O(\sqrt{q})$ effort. If $p$ is a strong prime, that is, if $(p-1)/2$ is also prime, then the only thing that is leaked is the value of $m^{(p-1)/2}$, that is, whether $m$ is a quadratic residue modulo $p$.

As for sending multiple messages $m_1, m_2, ..., m_t$ using the same private keys, well, if the messages are independent, we can show that there cannot be a weakness that reveals even one of the messages (the proof goes as follows: if there were something where, given $t$ independent exchanges $m_1, m_2, ..., m_t$, it has a nontrivial probability of giving us $m_i$ for some $i$; then we can take a single exchange and blind it $t$ times to generate $t$ independent looking exchanges; if our multi-exchanged weakness revealed one of the blinded messages, we can translate that back to the original message). However, this proof technique relies on the messages being independent; if the messages had relationships between them, it is possible that the attacker could deduce that relationship (however, they still wouldn't be able to reconstruct the messages).