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 ?


1 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.