# Diffie and Hellman 公開金鑰交換協定
###### tags: `密碼學`

Alice 跟 Bob 要交換金鑰
1. 共同選定一個質數p 與 p的原根g
2. 個別選定一個密鑰 Ka與Kb
3. Alice 將 g^Ka mod p傳送給Bob
4. Bob 將 g^Kb mod p 傳送給Alice
5. Alice 將得到的公鑰與自己的私鑰做運算 (g^Kb mod p)^Ka mod p = g^KbKa mod p = sharedKey
6. Bob 將得到的公要與自己的私要做運算 (g^Ka mod p)^Kb mod p = g^KaKb mod p = sharedKey

為什麼要質數跟原根?
原根是產生特定有限場
質數是為了要產生唯一的乘法反元素

同餘加法
a+b mod c = [(a mod c)+(b mod c)] mod c

proof:
a = q1c+r1
b = q2c+r2
a+b mod c 
= q1c+r1+q2c+r2 mod c
= r1 + r2 mod c
= [(a mod c) + (b mod c)] mod c

同餘乘法
a*b mod c = (a mod c)(b mod c) mod c

proof:
a = q1c+r1
b = q2c+r2
a*b mod c 
= (q1c+r1)(q2c+r2) mod c
= (q1cq2c + q1cr2 + q2cr1 + r1r2) mod c
= (a mod c)(b mod c) mod c

同餘指數
a^b mod c = (a mod c)^b mod c

proof:
a = q1c+r1
b = q2c+r2
a^b mod c 
= (q1c+r1)^b mod c
= [C(b,0)q1c^b*r1^0 + ...... + C(b,b)q1c^0*r1^b] mod c # 二項式展開
= r1^b mod c
= (a mod c)^b mod c