[上課筆記] 現代公開金鑰系統

－－－－複習－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

數位簽章程序(演算法)：
利用簽章者私key做簽署，及利用簽章者公key做驗證，使用的演算法有RSA簽章法、DSA/DSS簽章法。
key交換方式為利用演算法本身產生之數學方式來產製Session Key(Securt Key)(密key)或用接收者公key加密成密key(Preshare Key)傳給接收者模式。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
同餘算數(ppt 4-2-2、book4-10)：公key系統使用之數論

1.　mod("modulur")→中國餘數定理-韓信點兵
　 　X除3於1　　　→106 mod 3≡1
　 　X除5於1　　　→106 mod 5≡1
　 　X除7於1　　　→106 mod 7≡1
　 　X最少為106
反向函數　　　　　　　　　　　　　　　　　　　　　
　　同餘加法｛a的反向為b，則(a+b) mod N≡0
　　同餘乘法｛a的反向為b，則(a×b) mod N≡1
　　同餘指數｛a的反向為b，則(a×b) mod N≡1
反向函數演算法
N=10‧(a,b)
(4,10)(6,10)
同餘加法｛明文＋公key) mod N=密文 ex: (7+4) mod 10 ≡1
同餘加法｛密文＋私key) mod N=明文 ex: (7+4) mod 10 ≡7
(3,10)(7,10)
同餘乘法｛明文×公key) mod N=密文 ex: (8×3) mod 10 ≡4
同餘乘法｛密文×私key) mod N=明文 ex: (4×7) mod 10 ≡8
(7,10)(3,10)
同餘指數｛明文^[key1]) mod N=密文 ex: (8^7) mod 10 ≡2
同餘指數｛密文^[key2]) mod N=明文 ex: (2^3) mod 10 ≡8


------------------------------------------------------------------------------------
相關定理(ppt4-2-3)

(A) Fermat 定理 若 p 為質數，且 a 是無法讓 p 整除的正整數，則： a^(p-1) mod p ≡ 1、a與p-1為反向(乘法/指數)。


(B) Euler's Totient 函數 ，ψ(n) 是小於 n 但與 n 成為互質之正整數的數目，譬如ψ(10) = 4，則表示小於 10 且與 10 為互質的數字共計有 4 個。
如果 p 為質數的話，則：ψ(p) = p-1


(C) Euler 定理 ，如果 a 與 n 互質（gcd(a, n) = 1）的話，則： aψ(n) ≡ 1 mod n
意思表示：a 與 n 相互之間無法整除的話（互質），aψ(n) 除以 n，所得到的餘數為 1。






----------------------


實現 RSA 演算法 (ppt 4-4、book 4-27)




RSA鑰匙對產生演算法：

1. 選定兩亂數質數 p 與 q，並計算模數 n= p * q



2. 計算產生 Euler’s Totient 函數 ψ(n) =(p-1)*(q-1)



3. 選定 key1:e，需滿足 gcd(ψ(n), e)=1，e與ψ(n)互質



4. 尋找 key2:d，需滿足 e*d = 1 mod ψ(n)。



5. 實現 Mk mod n 運算



6. 配發鑰匙配對：公開鑰匙 = {key1:e, n}、私有鑰匙 = {key2:d, n}。

DH鑰匙交換法： (ppt4-5)

(產製雙方Session key而非純粹公/私key而已

1. A方選擇私key=Xa


2. B方選擇私key=Yb


3. 雙方均知公開參數 g,N


4. A方由g,N及Xa產生A方公key≡g^(Xa) mod N≡a


5. B方由g,N及Yb產生B方公key≡g^(Yb) mod N≡b


6. A傳a給B、B傳b給A


7. 公開性參數{a, g, N}公鑰、{b, g, N}公鑰


8. A方計算(由另方公key與已方私key產生)
   Session key=b^(Xa) mod N


9. B方計算(由另方公key與已方私key產生)
   Session key=a^(Yb) mod N


10. 未開性參數(未在網路上流傳)
    {Xa,g,N}私鑰、{Yb,g,N}私鑰、Session密鑰

(book 4-39)範例，網路上的SSL

----------------------------------------------------------
公開鑰匙分配(ppt 4-7、Book4-41)
密key系統如何分配密key：
－採取非網路方式傳送
－將公key系統保護密key在網路上傳送，但接收端之公key如何採信？

• 透過授權中心AC委託保管