I essentially have the same exact question as this one: Diffie Hellman Problem, which unfortunately doesn't have any good answers that clear up my confusion. There is one answer that is highly technical and that I don't understand. The comments seem to be on the right track, but I don't follow.
What I do understand is the following:
- Alice and Bob agree on two public numbers, $g$ and $n$.
- Alice chooses a private number, $a$, such that $1 <= a <= n$.
- Bob chooses a private number, $b$, such that $1 <= b <= n$.
- Alice computes $g^a (\text{mod n})$ and sends the result to Bob.
- Bob computes $g^b (\text{mod n})$ and sends the result to Alice.
- Upon receiving $g^a(\text{mod n})$ from Alice, Bob performs: $(g^a)^b (\text{mod n})$.
- Upon receiving $g^b(\text{mod n})$ from Bob, Alice performs: $(g^b)^a (\text{mod n})$.
- These are identical, and the result is used as the key for their communication.
Everything makes sense for me up until step 6. Bob received $g^a (\text{mod n})$ from Alice, so how can he perform $(g^a)^b$ if he does not know the value of $a$? Similarly, Alice received $g^b (\text{mod n})$ from Bob, so how can she perform $(g^b)^a$ if she doesn't know the value of $b$?
Said differently, Bob needs to calculate this:
$$ (g^a \text{mod n})^b (\text{mod n}) $$
What property of modular arithmetic allows him to simplify it to the following?
$$ g^{ab} (\text{mod n}) $$