# why inverse in diffie-hellman protocol will not give same value?

Security of diffie hellman protocol is $K=g^{ab}$.if sender want to calculate value of $b$(given $a$) he can do $g^{{{ab}^b}^{-1}}$(where K=$g^{ab}$) which will give $g^{a}$ as we are cancelling value of $b$ by finding its inverse. but it is not cancelling the value of $b$ and not give the output $g^a$. can any one explain why, while in ElGamal decryption in same way give plain text ($m=c2 *g^{ab}^-1$)

-
g^{{ab}^b}^-1 $\:$ is not canceling the value of $b$. $\;\;\;\;$ – Ricky Demer Mar 6 '14 at 8:42
In case of ElGamal we decrypt the cipher text by inverting m=c*(g^ab)^-1 then why not in diffie-hellman – Aria Mar 6 '14 at 8:53
In Diffie-Hellman, we usually want to encrypt data that doesn't fit in a single group element. $\hspace{.86 in}$ – Ricky Demer Mar 6 '14 at 8:59
For more clarity could you update your question? Do you mean why $g^{a(bb^{-1})} !=g^a\bmod P$ or why $g^{(abb)^{-1}} !=g^a\bmod P$. – neverwalkaloner Mar 6 '14 at 11:15
Yes, like @neverwalkaloner mentioned, your exponentiation formula is not really clear. Please add some parentheses to make the order clear. – Paŭlo Ebermann Mar 6 '14 at 12:56

In DH if you want to compute $g^a$ from $K$ you have to know $b$ (which the legitimate receiver of $g^a$ clearly knowns, so this does not really make sence). This party can compute the inverse of $b$, namely $b^{-1}$, and then compute $g^a=K^{b^{-1}}$. Note that this is not the same as $(K^b)^{-1}=(g^{ab})^{-1}$ (as I will discuss below). But that is not related to the security of DH.

The security behind DH is the computational DH problem, i.e., an eavesdropper learning $g^a$ and $g^b$ cannot compute the shared secret $K=g^{ab}$. But clearly the two parties doing the exchange can, as they hold $b$ and $a$ respectively. So for instance the party holding $a$ and received $g^b$ can compute $(g^a)^b$. Both parties holding $K$ can then use this shared secret to derive some symmetric key for encryption of any messages they want to communicate.

Note that in ElGamal (which may be seen as a non-interactive DH using the public key as static DH key of the receiver) you have $(c_1,c_2)=(g^k,mg^{xk})$ as a ciphertext and $h=g^x$ as the public key and $x$ as the secret key. This means that you encrypt a message using the DH key. Then you decrypt as $m=c_2\cdot (c_1^x)^{-1}$. Note that $(c_1^x)^{-1}=(g^{xk})^{-1}$ which is the inverse of $g^{xk}$ and will cancel out in the decryption as $g^{xk} \cdot (g^{xk})^{-1}=1$.

Note that nobody would use ElGamal to directly encrypt messages, but one will use hybrid encryption, i.e., use ElGamal to encrypt a random symmetric key and use the symmetric key to encrypt the messages.

Why is it a different thing to compute either $(g^{ab})^{b^{-1}}$ or $((g^{ab})^b)^{-1}$? Well, I think your problem is that you should write the parenthesis as I have done it above, since these are two different things.

Now, $K^{b^{-1}}=(g^{ab})^{b^{-1}}=g^{abb^{-1}}$, i.e., here you exponentiate $K=g^{ab}$ with the element $b^{-1}$ (the invese of $b$) and since $bb^{-1}=1$ you obtain $g^{a}$. In the second case you have $(K^b)^{-1}=((g^{ab})^b)^{-1}=(g^{abb})^{-1}$, i.e., you exponentiate $K=g^{ab}$ with $b$ and then compute the inverse of the resulting element, which does not give you $g^a$ as a result, but $(g^{abb})^{-1}$ which is not equal to $g^a$.

For a concrete setting, if you work in the group ${\mathbb Z}_p^*$ with $p$ being prime and use a generator $g$ of ${\mathbb Z}_p^*$, then arithmetic is done modulo $p$. So inverses of elements, e.g. $(g^{ab})^{-1}$, are computed in ${\mathbb Z}_p^*$. But, be careful, operations on elements in the exponent of $g$ ($g$ generates the group of order $p-1$), e.g., computing $b^{-1}$ (if you want to compute $(g^{ab})^{b^{-1}}$) are done modulo $p-1$. This clearly requires that $b$ is co-prime to $p-1$, i.e., $\gcd(b,p-1)=1$, that the multiplicative inverse $b^{-1}$ of $b$ exists.

-
that what is my question why g^a!=(k^b)^-1 – Aria Mar 6 '14 at 9:01
I suppose you are not right. Look at my answer, I tried to explain why this is not correct. – neverwalkaloner Mar 6 '14 at 9:10
@Aria I clarified it a bit more. – DrLecter Mar 6 '14 at 9:19
in case of ElGamal $g^{x k}.g^{xk}^-1 = 1 why not in K^{b}^−1= g^{abb}^−1 – Aria Mar 6 '14 at 10:17 I do not see your point,$(K^b)^{-1}=(g^{abb})^{-1}$. But the thing is that$(g^{abb})^{-1}\neq g^a$. – DrLecter Mar 6 '14 at 10:23 All computations produced by modulo P, where P is prime number. From Euler theorem we know that$g^{P-1} = 1 \bmod P$. Hence,$g^P = g \bmod P$. We know that$b*b^{-1} = 1 \bmod P$So when you calculate$g^{bb^{-1}} \bmod P$you will receive$g^{nP+1} \bmod P =g^{n}*g \bmod P$. That is why$g^{(ab)b^{-1}} \bmod P$=$g^{a(bb^{-1})} \bmod P = g^{a(nP+1)} \bmod P =g^{an}*g^a \bmod P$and this is not equal to$g^a$. It does not work, because in the exponents null element will be not$(P)$, but$(P-1)$. So you need to calculate$b^{-1} mod (P-1)$not$b^{-1} mod (P)$. And in such case,$g^{a(bb^{-1})} = g^a \bmod P$. - last line is not clear how (g^ab)^b^-1 will be equal to g^an*g^a.. – Aria Mar 6 '14 at 9:39 @Aria, I added intermediate steps. Hope, now it is more clear. – neverwalkaloner Mar 6 '14 at 9:47 It is very confusing, how you use your modulo operator. It's better to apply mod at the end of your expression or equation. But anyway, there is a serious error in your calculation: If$g^{p-1} = 1$mod$p$for prime$p$, then you do not calculate inverse exponents$b,b^{-1}$modulo$p$. In the exponents, you have to use$\phi(n)=p-1$as modulus. Btw, DrLecters explanation is correct. – tylo Mar 6 '14 at 10:01 @tylo for example$P=29, g=3, a=2, b=5$.$g^a =9 \bmod 29$,$g^{ab} =5 \bmod 29$.$b^{-1} = 6 \bmod 29$. But$g^{abb^{-1}}=23 \bmod 29\$ If DrLecter is right and my answer is wrong, could you explain please, why last result is not equal to 9. Is something i messed or done wrong? – neverwalkaloner Mar 6 '14 at 10:22
@tylo, I understood, what did you talked about. Thank you. – neverwalkaloner Mar 6 '14 at 11:12