0
$\begingroup$

Let $G$ be any group where group operations, as well as finding the inverse of an element, can be performed quickly, but the discrete log problem is difficult. Consider the following cryptosystem:

  1. Alice chooses an element $g ∈ G$, a message $m ∈ G$, and an integer $k_A$.
  2. Alice computes $s = mg^{k_A}$ and sends $s$ to Bob.
  3. Bob chooses an integer $k_B$, computes $t = sg^{k_B}$ , and sends Alice $t$.
  4. Alice computes $u = tg^{−k_A} = mg^{k_B}$ and sends $u$ to Bob.
  5. Bob computes $ug^{−k_B} = m$ and recovers the message.

Is this cryptosystem safe? I've noticed that Eve has $s$, $t$, and $u$
and that they are all divisible by m. Does this mean it's not safe? Or what am I missing?

Help is appreciated

$\endgroup$
1
  • $\begingroup$ This system in addition of being insecure as pointed by cpast, is rather strange. In fact it look like a PK cryptosystem but it is not one, by the simple reason that there are no construction based on a trapdoor one way function. to Break as cpast show it, it suffice also to listen the transaction and compute $u\times s\times t^{-1}=m$. Another observation, in a group structure, any element can be divided by any other one. $\endgroup$ Feb 11, 2015 at 15:58

1 Answer 1

4
$\begingroup$

This is extremely insecure. The discrete log is a red herring -- nowhere in the problem is the difficulty of discrete log relevant, because neither party ever uses their knowledge of their private exponent (computing $g^{-k}$ given $g^{k}$ does not require knowledge of $k$, so if inverses are fast to find, knowing one gives you the other quickly). That means we can ignore the exponentiation; all you have is Alice picking $a\in G$ and Bob picking $b\in G$, so $s=ma$, then $t=mab=sb$, then $u=ta^{-1}=mb$. Eve intercepts $s,t,u$, and computes $s^{-1}$, then $s^{-1}t=b$, then $b^{-1}$, then $ub^{-1}=m$. The issue isn't really that they're all divisible by $m$, it's that you rely on keeping $a$ and $b$ private but then send $s$ and $sb$ over a public channel (which means an attacker can easily recover $b$ and thus $m$).

In actual ElGamal, you actually use your private exponent. Instead of having to keep $g^{k_A}$ and $g^{k_B}$ secret, you rely on the fact that Alice (who knows $g^{k_B}$ and $k_A$) can compute $g^{k_Ak_B}$ while an attacker cannot. To use the security of discrete log, you have to do something that's easy for someone knowing the exponent but difficult for someone else; finding the inverse is not that something.

$\endgroup$

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.