EP20 - 你有聽過密碼學嗎？
Podcast 連結
本集內容大綱
前情提要
密碼學所討論的密碼和 EP3 - 設定密碼好複雜！中提到的用來驗證身份的密碼不同。
- 驗證身份的密碼：Password，使用者在登入時輸入已證明身份的密碼，安全性主要依賴密碼本身的長度和複雜度
- 密碼學所討論的密碼：Key 金鑰，用來加密和解密用的，長度通常較長，安全性除了依賴密碼的長度外，也大大取決於加密演算法。
密碼學
概念： 把一些資訊透過特定方式隱藏，讓這些資訊無法輕易的被外人解讀。
歷史：
- 500BC：斯巴達在打仗時不希望作戰計劃暴露給敵人，就在一條很長的紙上寫了一串字母，如果想讀取訊息，就要把紙條纏在一個特定大小的棍子上，才能拼出有意義的句子。 如下圖
Source: Wikipedia by Luringen licensed under CC BY-SA 3.0
- 490BC：古希臘人會將機密訊息刺在奴隸頭上，頭髮長出來時機密的訊息就會被蓋住，如果要看訊息再把奴隸的頭髮剃掉。
- 15 世紀：李奧納多•達文西的部分手稿就是利用鏡像文字左右相反的特性書寫，解讀時也就需要透過鏡子才能解讀。下圖為達文西的手稿
Source: Wikipedia by Luc Viatour licensed under Public Domain
- 現代：PTT 看到的藏頭詩
Source: PTT [Re: [求助]求高手藏頭詩 by wei998 (黑)](https://www.ptt.cc/bbs/Boy-Girl/M.1514541343.A.BE5.html)
這些依靠物理工具來達成的加密方法，雖然只能算是密碼學的皮毛，只是將資料很簡單的隱藏起來而已，並沒有將資料變得無法辨識，破解上並不需要花費太多力氣。
加密演算法
過一個金鑰和一些數學公式，讓原本的資料變得無法辨識，這樣即使資料被駭客取得了，也無法知道原本的內容是什麼，要復原的話就只能使用加密時使用的金鑰配合對應的數學公式解密。 元素：
- 明文：想保護而還沒加密的資料
- 密文：加密後無法辨識的資料
- 演算法：將資料加密或解密的方法
- 金鑰：與演算法配合，讓密文無法被他人解密的關鍵
混淆 Confusion ＆ 擴散 Diffusion
加密演算法主要會希望達到這兩個目的，做到這兩底才能確保密文在公開的情況下，攻擊者也無法知道我們使用的金鑰和明文。
- 混淆 Confusion：減少密文和金鑰間的關聯性，讓別人無法直接或間接地從密文中推敲出使用的金鑰、破解密文。
- 擴散 Diffusion：減少明文和密文間的關聯性，也就是說當明文中一個字母被更改，密文也應該要大幅度的改變，而不是也跟著只改變一個字母，才能避免攻擊者透過分析密文的變化進而找出規律推敲出明文。
替換式密碼 Substitution Cipher
加密演算法的兩種基礎加密方式的其中之一。
將明文中的每個字母替換成其他東西，讓明文看起來像是無意義的亂碼
-
Ａ換成Ｂ，Ｂ換成Ｃ ⋯ Ｚ換成Ａ（金鑰為 1）
- APPLE → BQQMF
-
Ａ換成Ｃ，Ｂ換成Ｄ ⋯ Ｚ換成Ｂ（金鑰為 2）
- APPLE → CRRNG
-
Ａ換成Ｚ，Ｂ換成Ａ ⋯ Ｚ換成Ｙ（金鑰為 25）
- APPLE → ZOOKD
豬圈密碼/共季會密碼 Pigpen Cipher
破解方式
分析每個字母出現的次數
在英文中，雖然有 26 個字母，但不是每個字母都會很平均的出現在句子和文章中，像母音的ＡＥＩＯＵ出現的機率就很高，相對的Ｘ、Ｚ等字母出現機率就很低。
出現的機率是最高的是Ｅ(13%)，遠高於平均的 3%。出現機率最低的則是Ｚ(0.074%)。 Wikipedia - Alphabet Frequency
透過這種特性，只要去統計加密後的密文中各個字母或符號出現的機率，再拿他去比對英文中各個字母出現的機率，就可以推敲出加密前的明文了。
換位式密碼 Transposition Cipher
加密演算法的兩種基礎加密方式的其中之二。
這個做法不會更改資料本身，但會依照規律改變資料的排列順序。
-
將奇數為字母拿到最前面，偶數為字母拿到後面
- HELLO → HLOEL （順序從 12345 → 13524）
-
用金鑰的字母順序作為每列換位的順序
進階的加密演算法
替換式密碼和換位密碼單獨來看都很基本，實際應用上在安全性也不是很足夠，但兩者都是密碼學上很重要的基礎，很多安全的加密演算法都是由不同種類的替換式密碼和換位密碼組合而成。
美國聯邦政府在 1976 年列為資料處理標準的加密演算法 DES（資料加密標準 Data Encryption Standard）就是結合了好幾種替換式密碼和換位密碼所組成的。
DES 中使用了一組 56 位元的金鑰將資料進行 16 輪的替換和換位來讓演算法夠安全。
DES 已經在 1997 年被破解了，現在取代 DES 的是進階加密標準 AES。
DES 的筆記會放在本篇文章的最後供大家參考。
加密演算法的安全性
考慮不同的情境
- 攻擊者只知道密文
- 攻擊者知道明文
- 攻擊者猜的到明文
- 攻擊者可以自由選擇明文
- 攻擊者可以自由選擇密文
如果攻擊者都已經知道明文了，加密方法安全性還需要考慮嗎？
加密演算法跟金鑰通常都不會只使用一次，當我們跟同一個對象在傳遞訊息時往往會重複使用同一組金鑰。 攻擊者知道明文的情況，可能就會發生在攻擊者獲取了對話中某些未加密的片段，如果攻擊者在這種情況下可以破解所使用的加密演算法和金鑰的話，就能破解過去和未來所傳遞的所有訊息。
所以最理想的情況是不管攻擊者知道多少訊息，只要不知道金鑰，都不能破解訊息，這樣才會認定這個加密方法是夠安全的。
抵禦暴力破解法
複習：什麼是暴力破解法？
以破解 DES 為例
DES 使用的是 56 位元的金鑰，每一位元可能是 1 或是 0 ，因此金鑰的可能性有 2 的 56 次方，也就是 7 千兆。
理論上如果我們使用一台蘋果的 Macbook Pro 來進行破解的話只要花 185 天就可以破解了，同時使用多台電腦或是用一些專門設計來破解用的電腦的話時間就會大幅縮短。 假設的條件和計算式：
- 假設在 500MHz 的情況下，每個時脈週期可以進行一次解密
- 確認一組金鑰所需要的時間：1/(500 x 10^6)秒
- Macbook Pro 處理器最高可達 4.5GHz
- 要確認 2^56 組密碼鎖需要花的時間：2^56/(4500 x 10^6)秒 = 185 天 (計算)
但如果是在相同的情況下要破解取代 DES，使用標準 256 位元金鑰的進階加密標準 AES 的話，需要的時間就會是 8x10^59 年（計算），簡單來說就是不可能被暴力破解。
在 DES 被發明的 1976 年，那時個人電腦還沒普及，每台電腦的效能也很差，因此在當時 DES 是一個安全的選擇，但拿到 44 年後的現在，因為科技的進步，電腦效能已經比以前好太多了，因此在現今科技底下 DES 是不夠安全的。
相同的道理也適用其他所有的加密演算法上，現在是安全的加密方法也會因為未來科技的進步，而變得能在短時間內被暴力破解法破解。
加密法是否被正確實踐
加密演算法安不安全還有一個很重要的點就是，我們是不是有正確的將他透過程式實現出來。
很多時候一個加密演算法本身以及他背後的數學原理是十分安全的，但程式設計師在將這個演算法轉換為軟體中可以運行的程式時會有邏輯上的瑕疵或是漏洞，導致這個加密方法無法被安全的實現。
我研究所時的密碼學教授就告訴我們永遠不要自己寫自己的加密演算法，因為自己寫的加密演算法一定都會多少有一點問題或是漏洞。
現在主流使用的加密演算法函式庫都是經過許多密碼學博士或是專家的測試和檢驗才確保安全的。
密碼學是一個很重要的工具，但密碼學也不是萬靈丹，在資安領域中除了有密碼學來幫我們加密資料以外也需要很多其他的工具的輔助。
加密解密小測驗
題目一： 找出下圖透過豬圈密碼所加密的訊息
題目二： 找出以下透過換位式密碼加密的訊息
金鑰：INFOSEC
密文：NRPPOCO NEICHCK
答案會在本文的最後
DES 資料加密標準 Data Encryption Standard 原理
加密解密小測驗 - 解答
題目一解答：Security is Important
題目二解答：Popcorn Chicken （PS. Popcorn Chicken 是鹽酥雞的英文）