Diffie–Hellman key exchange and Discrete Log [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I have a general question, and for that I will give an example: assuming Alice and Bob chose the prime number 593 and a public g= 9 . Alice choose the number 530. Bob choose the number 147.

Alice computes: x= g^a mod p = 574 Bob computes: y = g^b mod p = 527 Their shared key is 156

Now Eve is trying to crack the key and find a. She has a cracking function, and she finds c such that: g^c mod p =x In our exmaple, c = 234, but this is not the original a that Alice chose, so she still didn't succeed. My question is: is there a way she finds out the original a of Alice, using this information- that Eve has c, g, p and x, and she knows that g^c mod p =x

(Maybe by inverse function, I don't know..) Thanks

Answer 1

Yes. If

g^a mod p = g^x mod p

Then

g^ab mod p = g^xb mod p

In particular

(g^b mod p)^a mod p= (g^b mod p)^x mod p

So you can, for all practical purposes, pretend that Alice's private key is x. This is why it is important for g to be a generator of the group, so that there are no such 'sibling' private keys.

She can't know the 'original' a, but she does know that it's in the (usually) small set of numbers that differ from x by multiples of o(g). Which one it is doesn't really matter.

In this particular case, what's happening is that g is of order 296 instead of 592. Because of this, the actual secret key Alice chose - 530, has a 'sibling':

c = 530 + 296 mod 592 = 234