# The flaw in what I consider as a flaw in Diffie-Hellman algorithm

I was going through the diffe-hellman algorithm in cryptography . So the algorithm apart the mathematicality it hinges on is as follows :

If $$p$$ is a prime number and $$g$$ is another integer and $$a$$ and $$b$$ are two integers then

($$g^a$$ $$mod p )^b$$ $$mod$$ $$p$$ = ($$g^b$$ $$mod p )^a$$ $$mod$$ $$p$$ ------$$A$$

I got the proof of it but before going through its proof I tried along the following lines :

let $$g^a$$ be $$k_1p$$ + $$r_1$$ where $$r_1$$ < $$p$$ and $$g^b$$ be $$k_2p$$ + $$r_2$$ where $$r_2$$ < $$p$$

so $$g^a$$ $$mod$$ $$p$$ = $$r_1^a$$ $$mod$$ $$p$$

and $$g^b$$ $$mod$$ $$p$$ = $$r_2^a$$ $$mod$$ $$p$$

Now similarly :

$$(g^a$$ $$mod$$ $$p$$)$$^b$$ $$mod p$$ is ($$r_1^a$$)$$^b$$)$$modp$$

and $$(g^b$$ $$mod$$ $$p$$)$$^a$$ $$mod p$$ is ($$r_2^a$$)$$^b$$)$$modp$$

If $$A$$ is true then that means ($$r_1^a$$)$$^b$$)$$modp$$ should be equal to ($$r_2^a$$)$$^b$$)$$modp$$ which of course is not true given the random choice of $$a$$ and $$b$$ .

I think I had made a mistake somewhere while moving along these lines . Where is it that I erred ?

As TonyK points out the mistake was the following :

$$g^a$$ $$mod$$ $$p$$ = $$r_1^a$$ $$mod$$ $$p$$

It should have been $$g^a$$ $$mod$$ $$p$$ = $$r_1$$ $$mod$$ $$p$$ .

So with this correction :

$$(g^a$$ $$mod$$ $$p$$)$$^b$$ $$mod p$$ is ($$r_1$$)$$^b$$)$$modp$$

and

$$(g^b$$ $$mod$$ $$p$$)$$^a$$ $$mod p$$ is ($$r_2$$)$$^a$$)$$modp$$ .

How to reason out ($$r_1$$)$$^b$$) being equal to ($$r_2$$)$$^a$$) ?

• Typesetting tip: use g \bmod p ($g \bmod p$) instead of g mod p ($g mod p$). – Rahul Jun 25 '19 at 6:25

Here is your (first) mistake:

so $$g^a \bmod p = r_1^a\bmod p$$

This should be

so $$g^a \bmod p = r_1\bmod p$$

• But in general , if $a$ $\congr$ $b mod p$ then $a$ can be expressed as $kp + b$ for some integer k , so $a^n$ is $(kp+b)^n$ which on expansion yields an expression which contains powers of $p$ in all terms + $b ^n$ , so $a^n$ - $b^n$ is divisible by $p$ . Isn't it so ? – Erwin Kairos Jun 25 '19 at 5:55
• Found the mistake ... Editing it – Erwin Kairos Jun 25 '19 at 6:00

How to reason out $$r_1^b$$ being equal to $$r_2^a$$ ?

Both are equal to $$g^{ab}\bmod p$$. Easy!

• Thanks a lot. Don't know what made me miss this – Erwin Kairos Jun 27 '19 at 2:30