05 安全性演算法

tags: Algorithm

這篇筆記是我參考【演算法圖鑑】和網路資源所製作。如果內容有誤，還請不吝賜教!

目錄

• 05 安全性演算法
  • 目錄
  • 05-0 傳輸數據時的問題
  • 05-1 雜湊函數 Hash Function
  • 05-2 加密 Encryption
    • 加密的基本原理
    • 共用金鑰系統 shared-key cryptosystem
    • 公開金鑰系統 public-key cryptosystem
    • 混成密碼系統 Hybrid Cryptosystem
    • 迪菲-赫爾曼金鑰交換 Diffle-Hellmen Key Exchange
  • 05-3 身分、訊息鑑別 Authentication
    • 鑑別的重要性
    • 訊息鑑別碼 Message Authentication Code (MAC)
    • 數位簽章 Digital Signature
    • 數位憑證 Digital Certificate

05-0 傳輸數據時的問題

• 竊聽 Eavesdrop
  資料可能被第三方讀取

• 竄改 Falsification
  資料被第三方擷取並竄改，或是通訊中發生不明原因而造成數據損毀，都稱為「竄改」。

• 電子欺騙 Spoofing
  傳輸訊息的兩端用戶其中一方有可能是偽裝的駭客，稱為電子欺騙。
  一般來說，電子欺騙可能有兩種情況：

(1) 接收端是駭客 - 最常見的事件就是騙取個資

(2) 發送端是駭客 - 常見的情形包括釣魚網站或是可能藏有病毒的不明檔案。

• 抵賴 Repudiation
  若訊息發送用戶不懷好意，在訊息送出後主張自己沒有送出該訊息，稱為抵賴。抵賴最大的問題在於網路上契約或商業交易不易成立，甚至會有詐騙的事件發生。

而對於這些問題，我們有以解決辦法：

問題	解決方法
竊聽	加密
竄改	訊息鑑別碼 v 數位簽章
電子欺騙	訊息鑑別碼 v 數位簽章
抵賴	數位簽章
以下將介紹各種安全性演算法

05-1 雜湊函數 Hash Function

雜湊函數在我先前的筆記(02-Data Structure)裡有提到，摘要如下：

Hash function is a function that turns given data into a fixed-length value, called "hash code".

Hash function has the following features:

1. Fixed Length of Hash Code - No matter how massive the given data is, the length of hash code is always fixed.
2. Same Data, Same Hash Code
3. Similar Data, Different Hash Code
4. Unidirectional - It's impossible to infer the original data from its hash code.
5. Hash Collision - Different data might have the same hash > > code, when this occurs, we call it "hash collision". However, > > chances of collision are extremely slim.

雜湊函數因為它的單向性、單一性及不可辨讀性，被廣泛地運用在加密及製作數位簽章上。而雜湊驗算法則又有許多種，常見的有MD5, SHA-1, SHA-2等。現在大多使用SHA-2，因為MD5和SHA-1都曾有被破解的事件，存在一定的風險。

註：
MD5 - Message Digest Algorithm 5
SHA - Securing Hash Algorithm

05-2 加密 Encryption

加密的基本原理

• 明文 - plain text, 可直接被解讀的訊息
  傳輸數據時若以明文直接傳輸，極有可能被第三方直接偷窺，因此數據傳輸時大多以密文的形式傳輸。
• 密文 - cipher text, 經加密後的訊息, 無法直接被電腦或人解讀

以下解釋了明文是如何被傳輸的。

加密(encryption)就是將明文和金鑰進行計算而產生密文
而解密(decryption)就是對密文和金鑰再進行運算還原成原本的訊息

加密的方式又可根據金鑰的性質分為兩種：對稱加密和非對稱加密。

對稱加密指的是雙方都使用相同的金鑰進行加密、解密，好處是運算速度非常快，但是它有一個致命的缺點 – 安全性的缺陷。非對稱加密則相反，雙方使用不同的金鑰進行加密、解密，它和對稱加密是互補的 – 一方的優點即是另一方的缺點。

	對稱性加密	非對稱加密
安全性
運算速度

現在來談談對稱性加密的大問題。

假設Alice要用這種演算法傳遞訊息給Bob，顯然如果雙方都知道金鑰的話，那是一件很美好的事。問題就在於多數時候雙方先前是沒有相互往來的，意即兩方都沒有共同金鑰。這種時候，我們有以下的解決辦法：

共用金鑰系統 shared-key cryptosystem

Alice在傳送訊息給Bob前，要先傳送金鑰給Bob，接著再傳送密文給Bob。

共用金鑰系統其實在兩千年前就已經存在，最著名的莫過於凱薩加密系統。現今常用的為AES加密演算法。

問題來了，在傳送金鑰的過程中，金鑰還是有可能被偷窺(金鑰傳送困難)，這不就又回到最一開始的問題了嗎？而且隨著傳輸的對象越多，管理金鑰的數量也會越來越多。這些都是共用金鑰系統最大的問題。

公開金鑰系統 public-key cryptosystem

公開金鑰系統彌補了共用金鑰系統的缺點，因為訊息只能用公鑰加密也只能用私鑰解密，即使公鑰和密文被偷窺，第三方也因為沒有解密的關鍵 – 私鑰而無法獲取原始明文，安全性相對提升。

以下將解釋這個加密演算法是如何運作的：

1. Bob先準備兩個金鑰 – 公鑰和私鑰，公鑰可公開到網路上，但私鑰必須被保管好而不能外流。接著將公鑰傳送給Alice。
2. Alice用Bob傳來的公鑰將訊息加密。
3. Alice將密文傳給Bob。
4. Bob用私鑰來解密，得到明文。

然而公鑰加密也有存在公鑰可信度的問題。換句話說，我們無法確定Alice是否不懷好意，又或者公鑰傳輸的過程，很有可能被第三者替換，這樣第三者便能取得訊息而雙方仍渾然不覺，稱為中間人攻擊。

以下將說明中間人攻擊的過程：

1. Eve製作了自己的公鑰Px和私鑰Sx。
2. Bob公開了他的公鑰P，但是在P傳到Alice之前，Eve攔截了這條通道，並將P改為Px。
3. Alice以為她收到的公鑰是Bob的，於是她用這隻公鑰Px加密訊息，並送出密文Tx。
4. Eve再度攔截，將密文用Sx解密取得明文。
5. Eve再用Bob公開的公鑰將原文加密成新密文T，再將T傳輸給Bob。
6. Bob收到密文T，用自己的私鑰S解密，但卻完全不知道Eve動過手腳…。

這個時候，解決方案便是數位憑證，之後的筆記將會介紹。

混成密碼系統 Hybrid Cryptosystem

混成密碼系統是共用金鑰和公共金鑰的加強版。將金鑰再進行一次公鑰加密，使得雙方能夠安全的傳遞共同金鑰。這個方法不只兼備了共用金鑰系統的快速，更解決了金鑰傳送困難的問題，一舉數得。

以下將說明混成密碼系統的運作過程：

1. Alice準備共同金鑰K，並將訊息用K加密成密文T。
2. Bob利用公鑰加密的方法，讓Alice取得Bob的公鑰P。
3. Alice用P將K加密並傳送給Bob。
4. Bob用私鑰S解密，如此一來兩人都有了金鑰K。
5. Alice傳送T給Bob，Bob就可以用K解密。

• SSL憑證
  混成密碼系統最被廣泛應用的地方，就是SSL安全憑證。我們每天用電腦或手機瀏覽網站時，和遠端伺服器幾乎都是以http(HyperText Transfer Protocal, 超文本傳輸協定)傳輸資料，而SSL憑證的目的是為了確保我們的裝置(client端)和伺服器(server端)皆是安全的。大部分的時候我們都會在網址看到https，那個s就代表這個網站有SSL憑證，是安全的。

迪菲-赫爾曼金鑰交換 Diffle-Hellmen Key Exchange

金鑰性質

迪菲-赫爾曼金鑰交換所交換的金鑰有一些特殊的運算性質：

1. 兩個金鑰可以透過一些運算合成一把新的金鑰。
2. 金鑰合成並無先後順序。
3. 合成的金鑰不能被分解、還原成原來的金鑰。

運作模式和安全性

現在來看看這種交換方式是如何運作的：

1. Alice跟Bob各自準備自己的私鑰A和B。
2. 再準備一隻公鑰P。
3. 兩人各自將私鑰和公鑰合成PA和PB。
4. 兩人互相交換新合成的金鑰。
5. 兩人各自將收到的金鑰和自己的私鑰再合成一次。
6. 這樣兩人都有共同金鑰PAB了。

由於Eve只可能偷取P、PA或PB，又因為這種金鑰的特性，Eve不可能合成出PAB。因此這種演算法具有高度的安全性。

05-3 身分、訊息鑑別 Authentication

鑑別的重要性

傳輸訊息時可能發生好幾種狀況：

1. 即使是密文，在傳輸的過程中也會遭到惡意竄改，造成傳訊的兩方解讀有誤。這種狀況尤其在商業交易上是最不容許發生的。

2. 訊息傳輸的來源無法被確定。如果訊息是由駭客送出，那收到訊息的接收端怎麼確定這個訊息是從他信任的發送端送出呢?

以下將逐一介紹解決這些問題的演算法。

訊息鑑別碼 Message Authentication Code (MAC)

運作過程

1. Alice先將解密的金鑰
   $K_t$傳送給Bob(公開金鑰系統 或 迪菲-赫爾曼金鑰交換)。並將訊息用
   $K_t$加密。
2. Alice再準備另外一把產生MAC(訊息鑑別碼)的金鑰
   $K_m$，並再度用安全的方法傳送給Bob。
3. Alice將
   $K_m$和密文一起進行運算，得到MAC。

根據運算過程可將MAC的產生方式分成許多種，如HMAC，OMAC和CMAC。
現在普遍使用HMAC，它是利用hash function產生MAC。

4. Alice將密文和MAC傳送給Bob。
5. 和Alice一樣，Bob使用收到的
   $K_m$和密文一起進行相同運算得到新MAC。
6. Bob檢查新的MAC是否和Alice傳來的一樣，如果一樣則表示Alice傳來的密文沒有被竄改，並將密文用
   $K_t$解密。反之，Bob發出請求請Alice再傳一次直到正確為止。

MAC的安全性

如果這個時候第三方Eve想竄改任何訊息，訊息鑑別碼都能發揮作用，讓Bob能夠收到安全且正確的訊息。

1. 如果Eve竄改了密文，Bob便能在檢查的時候發現MAC和新的MAC不相符，並要求Alice再傳一次。
2. 如果Eve竄改了密文和鑑別碼，由於Eve並不擁有密鑰
   $K_m$，因此即使他變更了MAC和密文也無法使這兩者相對應。所以Bob還是能夠發現訊息被竄改，要求Alice再傳一次。

MAC的痛點

由於Alice和Bob手中都握有產生MAC的金鑰，雙方都能對訊息進行加密。然而這會產生一個問題。如果今天Alice或Bob不懷好意 (比方說Alice可以主張訊息是Bob捏造的，又或者Bob可以自行製作訊息然後說這是Alice傳來的)，這個時候因為MAC的來源沒辦法確定，造成抵賴的發生，這也是MAC無法解決的問題。

接下來將介紹解決抵賴的演算法 – 數位簽章。

數位簽章 Digital Signature

目的&優點

現實生活中的簽章目的是為了確認一個人的身分，數位簽章也一樣，目的是為了確認訊息是否真的由某人發送，解決了訊息來源的不確定性。

運作模式

數位簽章的運作模式大致如下：

1. Alice先準備兩把金鑰 – P(公鑰)和S(私鑰)。值得注意的是，訊息是用S加密，用P解密。
2. Alice先將訊息雜湊，得到hash value，並用S將hash value加密，產生的結果即是Alice的簽章 – Sign。
3. Alice公開自己的簽章Sign和P，提供給Bob甚至是其他人查證。
4. Alice將訊息用其他加密方式傳送給Bob。
5. Bob收到訊息後，開始查證是否為Alice傳送。查證方法如下：將訊息丟進相同的雜湊函數，得到新的hash value。接下來Bob用P解密Alice的簽章Sign，還原出Alice的hash value。如果兩人的雜湊值吻合，代表訊息就是Alice傳來的。

因為數位簽章是透過私鑰S加密形成，加上只有Alice擁有私鑰，因次這種演算法確保了製作出來的簽章具有唯一性，即簽章不能夠被偽造。

迷思澄清

Q1: 數位簽章跟公鑰加密系統都有用到公私鑰的概念吔，那到底差在哪呢?

先從運作方式切入，我們會發現這兩種演算法完全不同。
(假設發送訊息的是Alice，接收訊息的是Bob。)
(再假設公鑰是P，私鑰是S)

	加密	解密
數位簽章	SA	PA
公鑰加密	PB	SB
完全相反的原因是因為這兩種演算法背後的意義截然不同。公鑰加密系統是為了安全、不被偷窺地傳輸訊息，而數位簽章則是向大眾證明訊息是由自己傳送的。兩種演算法的目的不同，自然就有許多差別。

(別把這兩種演算法搞混了!!!)

Q2: 為甚麼還要先將訊息經過雜湊，而不是直接將訊息用私鑰加密?

最主要是為了壓縮訊息，降低耗費時間。

公鑰加密運算量龐大，直接用訊息進行運算非常沒效率。雜湊函數這時也派上用場了。因為雜湊函數可以幫我們為一筆資料產生一獨有的「身分證」 – 雜湊值(忽略機率極低的雜湊碰撞!)，所以利用這個雜湊值產生簽章，就跟用原來的訊息一樣沒有差別。又因為相較於原本的訊息，雜湊值的資料量極小，因此對它進行公鑰加密速度便提升許多。

數位簽章的缺陷

數位簽章其實還存在著一個問題，那就是Alice有可能是不懷好意的Eve偽裝的。根本的問題在於公鑰本身並沒有任何證據證明公鑰製作者是安全的一方。因此接下來我們將介紹解決這個問題的演算法 – 數位憑證。

數位憑證 Digital Certificate

目的&優點

使用公鑰加密系統或數位簽章時，公鑰本身因缺乏認證機制而有可能被替換。而數位憑證的出現，則確保了公開金鑰的真實性。

運作過程

1. Alice想要傳送自己的公鑰P_A給Bob。為了證明P_A真的是Alice自己的，在此之前Alice要先向憑證機構(Certificate Authority, CA)申請憑證。
2. Alice將P_A和自己的電子郵件一起傳送給CA。
3. 憑證機構CA確認資料無誤後，再用自己的私鑰S_C將Alice的資料加密，產生簽章。
4. CA將這份簽章的電子檔傳送給Alice，而這份檔案就是Alice的數位憑證。
5. Alice將憑證傳送給Bob。
6. Bob收到後，利用CA公開的金鑰P_C解開憑證。解開後Bob會獲得Alice的email和P_A。
7. Bob確認電子郵件真的是Alice的，這樣代表那個憑證具有真實性，因此Bob可以信任Alice傳來的公鑰P_A。

利用這個機制，Bob不需要去相信第三方惡意傳送的假公鑰，因為那些公鑰並未擁有數位憑證。

迷思澄清

Q1: 假設有第三人Eve取得了Alice的憑證，並用CA的公鑰解開憑證竊取Alice的email，那這個時候Eve不就可以拿著Alice的電郵申請假憑證，然後傳送給Bob了嗎?

遇到這種情況，在憑證階段就能被發現。

首先，Eve根本就不能單靠Alice的email申請憑證，Eve如果沒有Alice的裝置，要申請憑證是不可能的。

就算Eve真的成功申請到假憑證，在Bob檢查信箱的階段就會被察覺。

Bob可以寄確認信給Alice，Alice本人可以親自回覆。多虧了現今電子郵件系統的防禦措施，如果Eve為了回覆確認信而嘗試登入Alice的信箱，系統會發一封簡訊到Alice的裝置確認是否讓外來裝置登入。

因此Eve不可能申請到假憑證，就算Eve擁有假憑證，但Bob終究能夠分辨而不會相信。

Q2: 因為公鑰本身不具備來源確定性，必須透過憑證機構CA做擔保。那如果Eve偽裝成CA，製作假憑證，該怎麼辦?該怎麼確定CA的公鑰是可信的?這樣不就又回到最初的問題了嗎?

事實上，這個憑證機構所製作的公鑰還有上層的機構給予憑證、做擔保。而上層的機構還有更上層的憑證機構做擔保…如此向上追溯，我們發現了最上層的機構 – 稱為「根憑證機構」(Root CA, RCA)，而這些機構不是政府機關就是大企業等深受社會信任的組織。而子機構的產生，也是先向這些大機構申請憑證，這些較大的組織便會替較小的組織的信用度做擔保，形成了層層下推的樹狀結構。

數位憑證的延伸應用

網站進行通訊時也會用到數位憑證。不同於個人的憑證是和電子信箱綁在一起，網站背後的伺服器則是用網域(Domain Name, 透過DNS的解析可和該網頁的IP位址相互對應)申請憑證，確保管理此網站資訊的組織及伺服器相符。