December 15, 2019

Proof of Congruence

 

To prove that

(nb)a mod p = (na)b mod p

Properties of congruence

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

a ≡ b mod m ⇒ an ≡ bn mod b -------- 2

Given

na ≡ ga mod p -------- 3
nb ≡ gb mod p -------- 4

Applying 1 to 3 and 4

ga ≡ na mod p -------- 5

gb ≡ nb mod p -------- 6

Applying 2 to 5 and 6

(ga)b ≡ (na)b mod p -------- 7

(gb)a ≡ (nb)a mod p -------- 8

Applying rule of powers to 7 and 8

(ga)b = gab

(gb)a = gba

gab = gba

∴ (nb)a mod p = (na)b mod p

 

Back to « Diffie-Hellman Key Exchange

 

 

 

 

 

 

 

 

 

 

 

 

Up to top of page