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.

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

share|improve this question
    
g^{{ab}^b}^-1 $\:$ is not canceling the value of $b$. $\;\;\;\;$ –  Ricky Demer Mar 6 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 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 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 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 at 12:56
show 4 more comments

2 Answers 2

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.

share|improve this answer
    
that what is my question why g^a!=(k^b)^-1 –  Aria Mar 6 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 at 9:10
    
@Aria I clarified it a bit more. –  DrLecter Mar 6 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 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 at 10:23
show 1 more comment

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

share|improve this answer
    
last line is not clear how (g^ab)^b^-1 will be equal to g^an*g^a.. –  Aria Mar 6 at 9:39
    
@Aria, I added intermediate steps. Hope, now it is more clear. –  neverwalkaloner Mar 6 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 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 at 10:22
    
@tylo, I understood, what did you talked about. Thank you. –  neverwalkaloner Mar 6 at 11:12
show 1 more 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.