認識密碼學 - 對稱式加密、非對稱式加密、數位簽章和憑證

在現在，密碼學已經非常深入我們的生活，在任何物聯網設備上，或是網際網路的溝通，都離不開密碼學，似乎憑證、簽章這些名詞從專業變成基本知識，因此這篇文章，來解釋這些名詞分別是什麼意思還有他們之間的關係，我把這篇文章分為以下幾個部分

• 對稱式加密(Symmetric-key algorithm)(又稱非公開密碼系統)
• 非對稱式加密(Asymmetric-key algorithm)(又稱公開密碼系統)
• 對稱式加密的金鑰分發(Key distribution)
• 數位簽章(Digital signature)
• 數位憑證(Digital certificate)

那開始吧!

對稱式加密(Symmetric-key algorithm)

重點: 加解密都是同一把鑰匙

我們先來看個例子，假如今天Alice要和Bob告白，她想傳一段Message "I LOVE U" 給Bob，加設她和Bob已經有一對一模一樣的金鑰(key = 2)，而且Bob知道Alice 會用哪種演算法來加密訊息，Bob拿到密文就能用相對應的"反運算"來解碼

對稱式加密衍生出來的加密機制，最著名的就是Feistel network，它是由德國物理學家兼密碼學家 Horst Feistel 在1970 年所提出的用於構造區塊加密法的對稱結構，基於此架構DES(Data Encryption Standard)也接著問世。

底下是Feistel network的概念圖，其實有點像是炒飯的感覺，重複翻炒

picture provided from https://en.wikipedia.org/wiki/Feistel_cipher

在DES和3DES後還有AES，AES常常應用在藍芽4.0或是TLS後面的訊息交換(session key)

非對稱式加密(Asymmetric-key algorithm)

重點: 加解密都是不同把鑰匙，公鑰(Public key)和私鑰(Private key)

在1976年，Diffie和Hellman先提出"公開密鑰系統"的概念，是基於數學的單向函數(One-way function)上，例如

$$y=f(x)$$

已知x可以求得y，但是已知y無法回推x，所以帶入密碼系統就是可以用私鑰可以算出公鑰，但是擁有公鑰無法回推私鑰的值

在1978年，Rivist, Shamir and Adleman三位學者提出了"RSA"演算法，實現了"公開密鑰系統"這個構想，RSA的基於大數的質因數分解，演算法大概如下

$$Select\quad  p,q, where\quad p\quad and\quad q\quad both\quad prime$$

$$calculate\quad   n = p*q$$

$$calculate\quad   \phi(n) = (p-1)*(q-1)$$

$$select\quad integer\quad e\quad and\quad d, where\quad e*d \quad mode \quad n =1$$

最後可求得公鑰 Public key = (e,n)；私鑰 Private key = (d,n)，那我們回到Alice和Bob的故事，假設今天對稱式加密的金鑰分發(Key distribution)，這時候Bob為了回應Alice的感情，就用Alice的公鑰加密了"5 2 0"這三個數字，他們加解密步驟如下(p=3,q=11)

非對稱式加密的演算法有非常多種，大家有興趣可以去查看看，那他帶來的應用最著名的應用有兩個

• 對稱式加密的密鑰分法
• 數位簽章

我們先來聊聊密鑰分發

對稱式加密的金鑰分發(Key distribution)

第一個故事我們提到，假設Alice和Bob用對稱式金鑰溝通的情況，那他們擁有的那對金鑰是怎麼祕密的教到他們彼此手中呢?

Merlke在1979年的時候提出了一個簡單交換金鑰的方式，我把他弄得更簡單一點，概念大概如下

1. Alice將他的公鑰傳給Bob
2. Bob產生一把隨機金鑰(session key)
3. Bob用Alice的公鑰加密了這把金鑰(session key)，回傳給Alice
4. Alice 用私鑰解密出這把金鑰(session key)，用此金鑰(session key)加密訊息給Bob

數位簽章(Digital signature)

大家有沒有想過，如果想要證明一個文件是自己所發，可信任且安全，該怎麼處理?

假設今天Alice和Bob要開始約會了，小明很想攪黃他們，所以他也用Alice的名字傳了一封訊息給Bob，這時候Bob就無法分辨哪個訊息是來自Alice，我想這時候Alice該有一個專屬的簽名檔了

在製作簽名檔之前，我們先了解什麼是雜湊函數(hash function)

雜湊函數(hash function)

定義：不同長度的訊息x經過雜湊函數會輸出固定長度的摘要(Digest) y

$$y = h(x)$$

特性:

1. 只存在唯一h(x)
2. y無法回推x的值
3. 不同x不會產生同樣的y，如果x1和x2不相等，則不存在h(x1)=h(2)

概念圖大概如下，

from https://en.wikipedia.org/wiki/Cryptographic_hash_function

應用：
雜湊函數的應用有很多，舉個簡單的例子，假如今天Alice傳了訊息給Bob，但是在過程中，受到一些原因封包受損，這樣Bob怎麼確認這個訊息沒有受損，是否完整?

其實只要Alice在他的訊息後面加上Digest，這樣Bob就可以輕易判斷訊息是否完整沒有受損，Bo收到訊息後，將Alice的訊息放入同樣的雜湊函數，再比對Alice算出來的Digest和他算出來的是否一樣

很多人會把雜湊函數和驗證碼(checksum)畫上等號，其實兩個概念上是相似的，但其實是不一樣的東西，恩...之後有空再聊

-----

回到數位簽章

這時候如果Alice在他的訊息後面加上專屬簽名，Bob就能判斷這是Alice所簽發的文件

他的製作方法如下

1. Alice 將訊息M經過雜湊函數得到Digest A (H(M))
2. Alice 用他的私鑰加密 H(M) 得到PA(H(M))，就是數位簽章
3. Bob收到訊息後
1. 將訊息M做雜湊求得 H(M)
2. 將數位簽章PA(H(M))用Alice的公鑰解密，取的H(M)'
4. Bob比對H(M)是否等於H(M)'

他們溝通簡化流程大概如下

這時候會不會有個疑惑，如果Alice的公鑰一開始就是假的呢?

中間人攻擊 Man-in-the-middle attack

對，小明還是不放棄，他改當中間人了，所有Bob和Alice中間的訊息，他都有機會去竄改或是監聽

這時候該怎麼辦? certificate authority (CA) 這個單位就問世了，他們專們簽發憑證，保證Bob不會拿到假的Alice的憑證

數位憑證(Digital certificate)

CA這個單位是專門簽發憑證，通常會是大公司或是政府單位可以當第三方憑證驗證單位，他的概念如下，

• Alice先將他的公鑰和基本資訊給CA，CA會加上CA的數位簽章(signed with CA's private key)，產生憑證給Alice
• Alice將憑證給Bob
• Bob拿CA的公鑰來驗證Alice的憑證是否由該CA簽發，是否合法-->如果合法，取得Alice 的公鑰

這大概就是憑證的概念，那這整個架構和溝通過程又被稱作為"公開金鑰基礎建設"（Public Key Infrastructure, PKI)

如果搞懂了以上的概念，可以看一下TLS，大概能更有體會