Proof of Congruence

To prove that

(n_b)^a mod p = (n_a)^b mod p

Properties of congruence

a ≡ b mod m ⇒ b ≡ a mod b -------- 1

a ≡ b mod m ⇒ aⁿ ≡ bⁿ mod b -------- 2

Given

n_a ≡ g^a mod p -------- 3
n_b ≡ g^b mod p -------- 4

Applying 1 to 3 and 4

g^a ≡ n_a mod p -------- 5

g^b ≡ n_b mod p -------- 6

Applying 2 to 5 and 6

(g^a)^b ≡ (n_a)^b mod p -------- 7

(g^b)^a ≡ (n_b)^a mod p -------- 8

Applying rule of powers to 7 and 8

(g^a)^b = g^ab

(g^b)^a = g^ba

g^ab = g^ba

∴ (n_b)^a mod p = (n_a)^b mod p

Back to « Diffie-Hellman Key Exchange

⇑ Up to top of page

John McSweeney