2
$\begingroup$

The PKC is in this way:

Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and sends the number $u = m^a\pmod p$ to Bob. Bob chooses a random exponent $b$ and sends $v = u ^ b = m^{ab}\pmod p$ back to Alice. Knowing the inverse of $a\pmod{p-1}$, Alice then computes $w = v ^ {a^{-1}} = m^{b}\pmod p$ and sends $w$ to Bob. Finally, Bob also computes $w ^ {b^{-1}} = m\pmod p$ and recovers the value of Alice's message.

I know a disadvantage of this PKC over ElGamal, that more times of data exchange is needed in order to send a single message. Are there any advantages of this cryptosystem over ElGamal? In particular, can Eve break it if she can solve the discrete logarithm problem? Can Eve break it if she can solve Diffie-Hellman problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ In the calculation for $w$, $u$ should be $v$. $\endgroup$
    – Aman Grewal
    May 20, 2020 at 11:55
  • $\begingroup$ @AmanGrewal I edited the question. Thank you very much. $\endgroup$
    – Kooranifar
    May 20, 2020 at 13:30

1 Answer 1

Reset to default
2
$\begingroup$

Can Eve break it if she can solve Diffie-Hellman problem?

Yes, at least, the computational Diffie-Hellman problem. This problem is "given the triplet $h, h^x, h^y$, recover $h^{xy}$"

Let us assume that Eve has an Oracle that solves this problem. Then, she sets $h=m^{ab}$, $h^x = m^b = (m^{ab})^{a^{-1}}$ and $h^y = m^a = (m^{ab})^{b^{-1}}$, and passes $h, h^x, h^y$ to her Oracle. The Oracle returns with $h^{xy} = (m^{ab})^{a^{-1}b^{-1}} = m$, problem solved.

And, if she can break the Discrete Log problem, she can solve the CDH problem, so this answers that question as well.

N.B. The protocol you listed is known as the "Shamir Three Pass Protocol", and is currently viewed more as a curiosity rather than something that solves some problem better than other solutions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot, I didn't expect that the protocol is that famous; great piece of info. $\endgroup$
    – Kooranifar
    May 25, 2020 at 12:32

Your Answer

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

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