Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
1  
Wow, what a detailed answer. Thanks !! –  Robert777 Jan 20 at 10:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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