# 密碼學講義
###### tags: `小社講義`
你問我為何講義看起來比簡報隨便？
你問我為何課堂更有趣、收穫更多？
那你就專心聽課啊
講義只是給你複習用的
講師做這個很累誒
[\簡報傳送門/](https://slides.com/repkironca/minimal)
by. Repkironca
---
## 前言
### 密碼學簡介
密碼學，聽起來很酷對吧，你是否曾經認為，只要上完這門課，自己也能成為天才駭客？
痾，那你可能會感到有點失望，我既不會教你怎麼駭進祖克柏的帳號，也不可能跟你講駭客技巧，阿蘇不會，而且我也不願被炎上。
言歸正傳，密碼學這門學問，主要核心都是圍繞在＂如何建立起安全的通訊＂上面，為什麼會突然這麼說呢？實際上，我們每天在傳遞訊息或傳輸資料時，都有可能遭到攻擊，而密碼學的作用就是免於我們受到這些攻擊的干擾。
具體來說，最常見的攻擊可能包含以下幾項：
- 竊聽，Eavesdrop
字面上的意思。當A、B(By the way，密碼學上常常這兩人命名為Alice與Bob，有夠沒創意)在建立起通訊時，有一第三者C，在雙方皆不知情的情況下成功攔截到他們的通訊內容。當然，如果這只是你一般在與朋友的對話，似乎沒什麼差。不過當這些資料轉變成你的信用卡密碼、學期成績、轉帳資料等等，聽起來就沒那麼妙了，對吧？
- 竄改，Falsification
同樣不難理解。繼剛剛的竊聽，如果駭客不只攔截你們的通訊紀錄，還順便幫忙竄改了A到B的訊息，此時就能稱為Falsification了。透過這個攻擊，你完全無法保證所說出的東西是按照自己的意思，你甚至不會知道自己的訊息已經被編輯過了。可惜的是，當你的損友把你的對話紀錄截圖傳給自己，而後斷章取義，臭到全台灣電資社團都知道，可能無法被稱為竄改。對，我**絕對不是**在說我朋友：）
- 電子欺騙，Spoofing
電子欺騙的精確定義是，駭客偽裝成某一IP，並以這個IP的身分收發訊息。與前者的細微差距在，駭客在做竄改時不見得會偽裝成特定IP。如果今天駭客的能力無法破解密文，但他透過某種方式修改密文再傳出去，就可以被定義為竄改了。而電子欺騙一般是在已經破解密文的情況下，再以原加密法來偽裝自己是原發信者，輸出完全不同之內容。同時電子欺騙的定義相對更廣，就算今天A根本沒發訊息，還刻連攔截都沒有攔截，直接冒用A身分來傳訊息給B，同樣處此範圍。甚至連＂駭客偽裝成自己為收訊者，宣稱自己有收到訊息，但實際上訊息未成功傳達＂也算是電子欺騙。簡單來說，只要有**冒充自己是IP**的情況，就可被成功定義。順帶一提，若你的損友趁你不注意時拿走你手機，然後亂發訊息給別人，這個也是電子欺騙喔，同樣我絕對不是在說我朋友：）
- 抵賴，Repudiation
從字面上似乎有點難理解。網路傳遞訊息與現實不同，我們不見得能確認螢幕前的人是本人，或傳遞過來的訊息是他原本的意思。而抵賴就是針對這部分做的攻擊，假設A傳遞了一訊息給B，且B已讀了就不當一回事。之後A收回訊息，並宣稱該訊息不是出自自己，就算是抵賴。所以密碼學可能無法讓各位再繼續用＂假告白真試探，而後再宣稱被盜帳＂這種爛招數了。
### 密碼學三大分類
根據用途的不同，在密碼學上，我們會將東西分成 **編碼、雜湊、加密** 三個類別。別擔心，這些我今天全部都會講，現在只是給你個觀念而已。
- 編碼
簡單來說， 日常中你聽到的那些ASCII、base_64，甚至是感覺酷酷的摩斯密碼，全部都會被歸類在編碼。首先我想先幫各位建立一個觀念：**編碼不是密碼的一種**。如果下次你朋友拿著明顯是編碼的東西，告訴你他學會了新的密碼，知道要如何拿知識狠狠甩他巴掌了吧。所謂編碼，一般是為了資料傳輸方便而創的東西，即原本資料太難表達或太大，所以用了一個新的方法表示它。舉ASCII來說，它把英文字元及一些符號轉成用數字的方法表達，讓我們可以更輕鬆地在程式中用上。編碼有個特色是，你只要會 Google ，就絕對可以破譯它，因為編碼的邏輯很簡單：一個字元對一個東西。所以破解編碼真的沒什麼了不起的，頂多就證明你是會按鍵盤的好棒棒人類而已。
Btw，這是ASCII表，類似這種概念
- 雜湊
aka 哈希碼（拜託不要這樣叫，我寧願你講英文，這樣超蠢）、單向散列函數、Hash，也有人會叫它**Hash function**。簡單來說這就是一種很酷的函式，利用取模之類，沒辦法從答案反推的方式，經過一連串運算，把輸入的文字轉成亂碼。這個亂碼符合幾個特色，首先此函式無論輸入，輸出的亂碼長度都是絕對固定的。舉個例子好了，下面是**SHA-512**（之後會介紹，總之就是一種Hash）的轉換結果
```
123 ->
3c9909afec25354d551dae21590bb26e38d53f2173b8d
3dc3eee4c047e7ab1c1eb8b85103e3be7ba613b31bb5c
9c36214dc9f14a42fd7a2fdb84856bca5c44c2
ckefgisc ->
dea3738b43d02259b021d6eea3938f8c71af99011a871
667b5ada3e545f639ec5548951a4ba7f4d71b6fe431a3
24c1bda477f73c5910fb5b6ec76f454b128489
Gawr Gura ->
cb735fe78384b65a8a5a40425d21b6ade24d87a8614a9f
3530e1db62e6890c466cdd0b83541b0e2fc3cd5aebe001
5d1e74fa9324df17dbb5684dc7406e7b8424
有沒有執秘剝削密碼學講師的卦 ->
17cf86b7750744f604ce62948dc0cfae7b3261408be6715
e19b824611ee34d6e66f4f8ca2a6ce9aebe578a953ee250
01a2d6f4525232c9cb5624bcd2941b9a35
```
如各位所見，不管我input什麼，output都不一樣，且長度不會改變。同時，如果出現兩個不同的 output，則能夠保證進來的兩個 input 絕對不同。最後就是，雜湊與其它兩者不同，它是不可逆的，甚至連暴力破解都無法。你無法從hash轉回去原文，當然如果你有本事把所有input都試完一遍就另當別論了，不過我可以再換一套hash function：）。各位可以先猜猜看這些性質有什麼用途，稍後解密。
- 加密
老實說這才是今天的主軸w，而且我認為只有加密夠格被稱為密碼。加密與編碼最大的差異在，**加密絕對存在金鑰**。什麼是金鑰呢？金鑰通常是配合加密演算法，用於把密文翻譯回去明文的關鍵，可能是一個數字、一個字串，形式不限。一旦少了它，密文將無法被解密（暴力破解或其他奇怪方法例外）。有發現什麼關鍵嗎？**今天就算我知道你加密演算法在幹嘛，如果我沒有金鑰，還是什麼都做不了**。這就是加密的關鍵，就算駭客從中途攔截到密文，或得知了你們使用什麼加密演算法，只要演算法、金鑰、密文其中一個東西欠缺，駭客也只能乾瞪眼。
### Kerckhoffs's principle
Claude Shannon，不要問我他是誰，曾經說過一句看起來很帥的話
> The enemy knows the system
雀食，敵人永遠會知道你的加密系統及方法。還記得我剛提到的加密特性嗎？一套好的資訊安全演算法，是不該被這點影響的。另外一個人，Bruce Schneier也曾說過類似的話
> 任何以隱藏設計作為防護的保安系統必然會失敗
意思大概是，如果一套演算法要成立的運行，是隱藏本身的設計方式，那它必定會失敗。應該要做到沒有密鑰，就極難被破解的狀態。而這也是Kerckhoffs's principle，中文翻譯成柯克霍夫原則，的精隨：**並非密碼學演算法都必須公開，但是要確保即使公開，也不會傷害其安全性**。當作附錄，這邊是它的原文定義
```
The concept that a Cryptographic system shouldbe designed to be secure,
even if all its details,except for the key, are publicly known.
```
---
### [小補充，密碼學的特性，我在課堂中可能不會提到](https://isp.nuu.edu.tw/p/405-1074-1269,c82.php)
~~雖然我不是數學家，但這隻鯊魚很可愛對吧，這就是為何它出現在這裡~~
---
## 古典密碼
接下來會從古典密碼開始介紹，所謂古典密碼，是指~~上古時期~~電腦還沒被發明以前，前人使用過的加密技術。基於戰爭因素，人類從很久以前就有了加密訊息的需求，而加密演算法的複雜度也逐漸複雜，在沒有任何現代科技的輔助下，老實說能想到這些，真的頗值得敬佩的。而這些演算法也是現代密碼學的前身，經由加密與破譯兩者之間的鬥智，孕育出今日保護資訊安全的種種。
### 凱薩密碼
首先第一個要介紹的是凱薩密碼。沒錯，就是各位在歷史課本看到，羅馬共和時期，被暗殺的那個凱薩大帝，~~希望各位除了地獄梗外，也能記得他在密碼學做出的貢獻~~
凱薩大帝曾說過這一段話：
```
如果需要保密，信中便用暗號，也即是改變字母順序，使局外人無法組成一個單詞。
如果想要讀懂和理解它們的意思，得用第4個字母置換第一個字母，即以D代A，余此類推。
```
聽起來很簡單對吧？事實上他的確不複雜，但也因為這個原因，凱薩密碼可以很隨便地被破解。不過當時的識字人口本來就不多，也沒有加密訊息的概念，對世界各語系亦沒有完整的認識，看到凱薩密碼大概也只會覺得是某個鳥國家的語言罷了，所以尚行得通。
如果你發現自己看不懂凱薩在講什麼，我在這邊簡單解釋一下：
凱薩密碼使用字母偏移替換的方式，來把明文轉為密文，而金鑰即為字母偏移量。直接看例子或許會更好理解，假設偏移量為 3，則所有字母 A 都會被從 A 往後數的第 3 個字母，aka **D** 取代，如下表：
同時字母間會形成一個循環，所以 X 會被 A 取代，Y 會被 B 取代，依此類推。假設你是數學狂熱分子，或許你會更喜歡下面這個簡潔的式子。
> 替代字母 = (原字母 + 偏移量) % 26
那麼，凱薩密碼有資格被稱為加密嗎？
答案是，**當然可以，雖然看起來很廢，但它符合所有加密的構成條件**。
為何會說看起來很廢呢？我們可以假設兩個狀況，來討論可以怎麼破解凱薩密碼：
> A. 我知道這是一個替換式密碼，不過我不知道這是凱薩加密
> B. 我已經知道這是凱薩密碼了，不過我不知道偏移量是多少
針對 A. 情況，由於凱薩密碼是一字對一字的加密方式，並沒有改變原文的長度或語法結構，所以其實滿明顯的。或使用等等會提到的頻率分析，也能馬上發現眼前的是凱薩加密。
接著是 B. 情況，首先我們要先了解一點很顯然的性質：**偏移量 = 1** 與**偏移量 = 27**，兩者是一模一樣的東西。亦即，實際上能用的偏移量只有 26 個，直接丟到電腦上暴力破解，不消幾秒鐘明文就會被篩選出來了。
假設你覺得暴力破解不夠帥，也能試試頻率分析。在一段有意義的英文長文中，某幾個特定的字或詞，被證實出現的頻率特別高。舉例來說，最常出現的字母是 e ，第二常出現的是 t ，第三常出現的是 a。而對於雙單詞組合，最常出現為 th，三單辭組合則由 the 獲得冠軍。
經由這點，我們可以直接觀察密文中，出現頻率最高的那個字，並直接推測它是 e，此時偏移量也出來了。如果你認為這樣過於草率，也能多做個幾組，反正單詞組合出現的頻率隨便 Google 都找得到。
By the way，[ZJ_b248](https://zerojudge.tw/ShowProblem?problemid=b428)，就是一題有關凱薩加密的題目，有空可以去寫寫看：）
AC後你大概就更能領悟，為何凱薩是個超級容易爛掉的加密方式了。
### 維吉尼亞密碼
下一個介紹的是維吉尼亞密碼，說實話它就是改編自凱薩密碼，稍微變複雜一點點而已，其基本邏輯都相同。凱薩密碼是把每個字母的字母序，加上偏移量後再模 26 對吧？而維吉尼亞密碼改變的只有**偏移量是固定數字**這點罷了。
具體來說，維吉尼亞密碼的金鑰會是一串小於或等於明文長度的字串。如果小於明文長度，那它就會不斷複製自己直至補足。For example，若明文有 20 個字母，金鑰選用"INCODE"這個字，就會變成 INCODEINCODEINCODEIN。
加密時，只要把明文與補完後的金鑰對齊，並按照此式計算就可以了
> 替代字母 = (原字母 + 對應字母 - 1) % 26
如果你覺得上面的敘述有點難理解，也可以用另一套邏輯思考：維吉尼亞密碼把凱薩密碼的 26 種偏移量都窮舉出來並且列表：
而每次要加密時，只要抓明文字母與對應字母出來對照表格，就能得出替代字母了
上圖即為 **明文D × 密鑰N** 或 **明文N × 密鑰D**的結果
還是覺得很抽象嗎？那直接上例子吧 :partying_face:
拿第一個字母來說明好了，如果用的是第一組邏輯，那麼
> (7 **[G]** + 23 **[W]** - 1) % 26 = 29 % 26 = 3 **[C]**
~~我希望你們沒有邊算邊唱字母歌~~，因為這樣真的很麻煩，而且阿蘇自己就是在唱字母歌的其中一個，所以我強烈推薦第二種邏輯。直接對照表格就結束了，簡單俐落，不是嗎？
然而，維吉尼亞密碼仍然很容易被破解。你可能會發現，因為這次的偏移量不再是一個固定的數字，因此頻率分析已經不能用了。但實際上還是可以喔：），先做個假設吧，令我們已經知道金鑰的長度 n，可以如何破解它呢？
既然金鑰是不斷複製自己產生的，代表第 a 個字母與第 a + n 個字母，是被同一個字母加密的，建立在這個前提之下，我們只要以間隔 n 來做頻率分析，就可以還原出金鑰了。
```
舉例來說，金鑰長度是 5，密文長度為 1000，則可以先分析第 1、6、11、16...996 個字母中，
哪個單字母出現的頻率最高，並定義其為 e（詳見前文的**頻率分析**那邊），假設是 f 好了。
則明文的 e，在經過第一個金鑰字母的加密後會變成 f，最後反推出金鑰第一位是 b。
```
> 然後呢？你的假設要怎麼成立，阿蘇又在唬爛我了嗎
關於這點，目前有三種可行的辦法：
**1. 通靈**
對，不要懷疑，真的是通靈。所謂知己知彼，百戰百勝。如果加密者的金鑰是選用有意義的字串，則極可能被認識的人直接猜出來。不過這方法沒什麼太大的可靠性，看看就好，我們還是進入比較有科學根據的方法吧。
**2. 暴力破解**
簡單，而且有用。~~事實上去年暑訓在教這邊時，也是直接教我們窮舉~~。最原始的做法是從長度 = 1 開始，一路去嘗試頻率分析、回推金鑰、破譯，再觀察出來的結果是否有意義，如果沒有則常代入下一個長度。
另外有個方法是利用英文語系的性質，會比人工觀察文字是否具有意義來得快。*"在任何一段有意義的英文長文中，隨機抓取兩個字母，他們相同的機率會是 0.068。＂* 同樣是從長度 = 1開始，以間隔 = n 的方式將密文分組，並且在裡面隨機抓取兩字母，觀察他們是否相同。重複以上動作多次（放心，這種東西交給電腦作花不了多少時間）後，相同機率最接近 0.068 者即為金鑰長度。
**3. 卡西斯基試驗，Kasiski Test**
[截圖自此](https://www.youtube.com/watch?v=asRbswE2hFY)
上圖是一個維吉尼亞密碼的長文，如果仔細觀察，會發現`ZVRAO`和`MBDBMVS`這兩個單詞組合在密文中多次重複出現，如圖中的紫色與綠色標示。
在一個有意義和主題的文章中，除了前文頻率分析中提到的外，肯定會有一些和主題相關的字詞是被多次提到的。舉例來說，如果這是一篇關於告白的密文，`feel`、`love`等字可能就會一直用到; 如果這是一篇關於空襲的密文，則可能會是`enemy`、`plane`等。而在金鑰長度不夠的情況下，就很容易發生，相同單字被相同金鑰片段加密的情況，進而導致各位所看到，特定單詞組合不斷在密文中出現的情況。
卡西斯基試驗在做的事，其實就是統整出這些字的間隔。拿這個例子來說，大概會長這樣子：
單詞組合|index(取首字的位置)|間隔
-|-|-
ZVRAO|102、134、390、402、426|32、256、12、24
MBDBMVS|143、155、307、411、439|12、152、104、28
根據這些字的間格，金鑰長度必定會是這堆數字的公因數。分別列出這些間隔的正因數（顯然金鑰長度是自然數，所以負因數可以直接忽略）：
數字|因數
-|-
32|**1**、**2**、**4**、8、16、32
256|**1**、**2**、**4**、8、16、32、46、128、256
12|**1**、**2**、3、**4**、6、12
24|**1**、**2**、**4**、6、12、24
12|**1**、**2**、3、**4**、6、12
152|**1**、**2**、**4**、8、19、38、76、152
104|**1**、**2**、**4**、8、13、26、52、104
28|**1**、**2**、**4**、7、14、28
最後得出金鑰長度是 1（等同於凱薩密碼）、2、4 其中一個，再直接拿這三個數字代入嘗試就可以了，相對暴力破解，效率會高上許多
> 我如果把金鑰長度設超級長，是不是就不會被破解了
ㄟ，雀食。事實上，在現代密碼學中，的確有個類似的想法，被稱為**一次性密碼本**。這個晚一點就會提到了，敬請期待。
### 恩尼格瑪密碼
這個密碼還是用歷史故事的方式來呈現，效果大概會好很多，所以...
> Story Time！！！
時光回溯到 1918 年 2 月 23 日，當時正值第一次世界大戰末期，德國科學家 **亞瑟 · 謝爾比烏斯** （Arthur Scherbius）創造出了新的一套加密方式：利用一台含有輪盤的機器，來創造替代式密碼，而這便是今日的恩尼格瑪機之雛形。
他興奮地向德國軍方推薦自己的加密方式，希望能取代原本危險的通訊管道，然而德國根本沒鳥他。回想一下歷史課本，德國當時忙著空襲牆頭草義大利，愉快得要命，才懶得鳥這個不知道哪裡出來的菜逼八。
然而，由於對加密系統的輕視，德國在幾個月後於一戰戰場不斷失利，甚至因此發生著名的 **齊默爾曼電報事件**。簡單來說，就是德國想號召位居美國南方的墨西哥，一同去扁美國，而他們寄給墨西哥的電報外洩，並被協約國破解。平常打打周邊小國也就算了，偏偏同盟國對美國的野心外洩，惹到最強滿血野怪的下場就是美國加入戰場。1918 年 11 月 11 日，同盟國被打爛，投降。
凡爾賽條約簽訂後，德國始終無法理解，為何戰況會突然急轉直下，原本占優勢的自己，最終落敗的原因。一直到 1923 年，尚未成為英國首相的邱吉爾在書中提到，協約國早已破解了德國的密碼，這是他們一戰能成功的關鍵之一。此時德國才如夢初醒，發現自己是小丑，自嗨過程被敵人看光光，趕緊回去把當年的亞瑟挖回來，請教他密碼機的詳細。
不問還好，一問不得了。德國人發現這個男人簡直是天才，再加上亞瑟在被塑膠的期間，又不斷改進自己的機器，現在幾乎可說是天衣無縫。德國軍方下令大量生產此一密碼機，並成為之後的標準訊息加密方式。
故事先暫停到這裡，我們來了解一下恩尼格瑪機的運作方式吧，否則也是白講。如圖，這是一台恩尼格瑪機，雖然出自遊戲畫面，但非常寫實。
每台恩尼格瑪機扣掉本體，還有 **4 個輪盤插槽、數個輪盤、6 條連結線**作為配件。基本上使用方式就是把明文（或密文）的字母用鍵盤輸入，接著放內部的電路去跑，最後前方螢幕前亮起的字母便是密文（或解碼出的明文）了。內部電路大概是這種概念：
接收到鍵盤訊號後，先經過 4 層輪盤，再經過連結線區，最後跑到燈泡。而此種加密方式的密鑰就是機器的初始設置方式。更具體來說，分為**輪盤要用哪幾個、輪盤的初始狀態、連結線插的方式**三個。
先從輪盤開始說好了，每打一個字，最右邊的輪盤就會移動一格，以改變內部電路跑的方式。每當最右邊的輪盤跑完一輪，第三個輪盤就會移動一格 ; 每當第三個輪盤跑完一輪，第二個輪盤就會移動一格，依此類推。不同的輪盤或不同的位置對電路的改變均有差異，因此只要輪盤選錯、放錯位置、甚至是輪盤初始的格子沒對好，都會嚴重影響密文，早就極大的變化性。
然而這樣還不夠，設計者嫌僅僅如此過於無聊，所以又多增加了連結線的設計：如圖，再設置時會根據密鑰，把連結線接到指定位置。
連結線會交換兩邊的輸出結果，例如原本 A 對應 L、B 對應 Q，一旦 A、B 被接上連結線，就會變成 A 對應 Q、B 對應 L的狀態。這使得暴力破解幾乎變成天方夜譚，也確實讓後面的國家十分頭痛。
介紹差不多先到這邊，讓我們回到故事本身。1926 年 2 月，英、法、美等國突然偵測到德國開始發出一大堆意義不明的訊號，實際上，這便是他們剛學會的恩尼格瑪密碼。幾國本來想嘗試破解，但經過努力無果後就直接放棄了：他們認為德國在凡爾賽條約的牽制下，也搞不出什麼事來，還是不要浪費金錢力氣去管這個比較好。
這時候波蘭頭就痛了，它夾在德、蘇兩個大國之間，只要有人開戰就絕對成為第一受害者。此時剛被擊退的蘇聯正在重振旗鼓，準備重新擴張領地，德國感覺也想做什麼壞事，雖然德蘇兩國簽署了和平協議，實際上卻暗潮洶湧，隨時有撕票打起來的可能。在西方的鄰居又整天傳一堆看不懂的話，要他們如何不緊張？
於是被嚇爛的他們決定自立自強，請來了波蘭總參謀部第二局（但我比較喜歡叫總參二局，比較帥），來處理密碼破譯的事情。自此以來，波蘭放出大量間諜進入德國，並召集全國的數學家、密碼學家等菁英齊聚一堂。
前幾個月沒有什麼進展，不過他們在後期截獲了一台商用恩尼格瑪機，仔細研究後才搞懂其中構造。雖然無法得出密鑰，但至少他們得知了暴力破解無用，並製造出第一台能模擬恩尼格瑪機的機器，＂炸彈＂（BOMBA）。
搞定了模擬器，那要如何解決密鑰問題？
事情是這樣的，謹慎的德國人，因為害怕密文會被敵人破解，所以在每次發報前，規定要所有傳訊兵在信件最前方隨機想幾個字母，已混淆視聽。同時為了分辨正文，又規定隨機想個字母要連續打兩次再進入正文。
聽起來就會出事，實際上也真的出事了。聰明反被聰明誤的他們，因為觸犯了密碼學最大的忌諱，aka **重複**，信件的金鑰被推出來，並且整封被破解。波蘭就一直用這種方法持續破解德國的信件，儘管他們每天都會更換金鑰，所以破解速度非常不穩定。
6 年後，德國人或許點了通靈技能，或聽到了風聲，突然覺得本來的加密方式可能有點危險，決定對原有系統進行強化。然而他們甚至連加密邏輯都沒改，直接用著同一台機器，增加了輪盤與連結線的數量，順便廢除原有**隨機字母打前面**的規定。這下波蘭人可頭痛了，簡單幾個步驟就幫該系統增加巨額可能性。
在波蘭人想到怎麼破解新版機器前，他們的預言就成真了。1939 年 9 月 1 日，瘋狗納粹德國入侵波蘭，夢魘成真。原本的那批數學家趕緊逃到法國尋求庇護，並與終於意識到危機的當地政府合作，繼續密碼破譯的工作。然而，與各位歷史課上到的相同，1940 年 6 月 22 日，納粹德國攻進巴黎，法國投降。這群可憐的數學家又流亡至英國。幸好最後英國沒被打下來，他們同樣與當地政府合作，在一處名為**布來切利莊園**的地方落腳。幾年內，更多人才也陸續湧入，加入該莊園與該組織一同嘗試破解恩尼格瑪密碼。
此時，逆轉局勢的那個男人就出現了。他被後世稱為計算機科學與人工智慧之父（或被政府迫害的同性戀），Alan Turing，艾倫圖靈。
他加入莊園後，先是與夥伴共同製造出了 **BOMBE**
對，看這沒創意的命名大概也知道是什麼用途了，BOMBA 的進化版w
有了能更快速模擬恩尼格瑪機，排出所有組合的機器後，圖靈開始尋找恩尼格瑪密碼能夠被攻破的漏洞。雖然前面我用過這句了，但還是再次強調，知己知彼百戰百勝。圖靈發現德國發出來的信件有一個特定格式，例如會先在信件的開頭標註今日天氣，或信件的結尾絕對是 **Heil Hitler** 等。利用著這點，往後德軍的密文都被他破解成功。而最後結果各位應該也清楚，利用著情報優勢，軸心國的戰況被逆轉，慘敗協約國。
同時，圖靈製造的 BOMBA，也被視為歷史上第一台電子計算機與人工智慧。歷史自此刻起，加密逐漸趨向於使用計算機，計算機的構造也日漸複雜，最終成為了目前的樣子。古典密碼大概就介紹到這邊，之後的課程會著墨在現代密碼學，也就是使用點子計算機進行加密的部份。
---
## 很廢的計算機概論
既然講到計算機加密，不先來一些計算機概論似乎說不過去。理論上，幾天前的硬體課程應該會包含一些，所以我這裡只會教等等用得到的東西，各位可以當成補充就好了。
### 進位制
各位或許時有耳聞，但老實說日常生活中，除非你也是電資圈怪人，否則接觸到這塊的機率不高。我這次會細講的部份有**十進位制、二進位制、十六進位制**三種。另外也有**八進位制**等制度存在，基本上邏輯都換湯不換藥，雖然我不會細講，但各位應該能自行延伸。
#### 十進位制
各位最習慣的那套進位制度。從小我們在書寫時，應該都是遵循著
```
0、1、2、3、4、5、6、7、8、9
10、11、12...
```
的邏輯對吧。分析一下它的特色：
- 使用的符號有 0、1、2、3、4、5、6、7、8、9，共 10 個
- 當我們想要表達＂9 + 1＂時，就會進位
- 每一個位數都代表 10 的指數次方倍，e.g. 百位數代表 10<sup>2</sup>
如果你覺得我在講廢話，代表你目前還是清醒的 XD。不過可以先記住這三個特色，之後所有的進位制度，改變的都只有這三條的一些細微地方而已。
#### 二進位制
最常，或著說一定，會用在計算機科學的進位制度。外行人對電資圈的刻板印象，往往是```整天看著一堆 0 跟 1，嘗試解讀他們```。例如下面這張圖：
雖然聽起來很瞎，而且實際上我們也看不懂 0-1 字串，不過這也間接說明了二進制在這個圈子的地位。
還記得我剛剛說的三個特色嗎？他們也同樣能拿來解釋二進制：
- 使用的符號只有 0、1，共 2 個
- 當我們想要表達＂1 + 1＂時，就會進位
- 每一個位數都代表 2 的指數次方倍，e.g. 第三位代表 2<sup>2</sup>
舉體來說，如果我們想要使用二進位來數數，應該會長這樣
二進位|1|10|11|100|101|110|111|1000|1001|1010
-|-|-|-|-|-|-|-|-|-|-
十進位|1|2|3|4|5|6|7|8|9|10
#### 十六進位
其實按照前面的邏輯，各位應該能直接猜出這套制度要怎麼使用了，頂多就是想不透要用什麼數字來表達 10 ～ 15 罷了。總之老樣子，先把那三個特色搬出來講吧
- 使用的符號有 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F 共 16 個
- 當我們想要表達＂F + 1＂時，就會進位
- 每一個位數都代表 16 的指數次方倍，e.g. 第三位代表 16<sup>2</sup>
這邊要顛覆的觀念是，在此系統中，A ~ F 也被拿來表達數字了。所以如果我們要用 16 進位來數數，應該會長這樣
十六進位|1|2|3|4|5|6|7|8|9|A
-|-|-|-|-|-|-|-|-|-|-
十進位|1|2|3|4|5|6|7|8|9|10
十六進位|B|C|D|E|F|10|11|12|13
-|-|-|-|-|-|-|-|-|-
十進位|11|12|13|14|15|16|17|18|19|
#### 雜談
基本上觀念就這樣了，各位可以嘗試代入幾個數字去嘗試轉換，等熟了以後甚至能嘗試用 C++ 或 Python 刻出來，順便練習語法。
這邊附上一個小觀念，可以方便各位把任何進位制的數字轉成十進位。其原文是這樣的：
> 如果要把 n 進制的數字轉成十進制
> 當第 a 位的數字為 x 時
> 它在十進制的值會是 a * n<sup> a-1</sup>
其實也就是前面提到的第三個特色：在第一位時，其值為 n<sup> 0</sup>，第二位為n<sup> 1</sup>，再下去是n<sup>2</sup>，依此類推。
btw, 我還真的找到一題關於這方面的實作，[Zero Judge 的 a034](https://zerojudge.tw/ShowProblem?problemid=a034)，有空可以上去看看。如果對 AC 扣有興趣可以去我簡報翻，不過那有用到一些演算法，你們可以不用寫到那麼難沒關係，這只是語法題，還是可以 AC 的。
### bit
下一個會提到的東西是＂bit＂，中文是位元，雖然我仍然喜歡用英文稱呼其就是。位元是電腦的儲存單位中，單位最小的一個，每個 bit 可以儲存一個 0 或 1（現在知道為何二進制很重要了吧）。而由 n 個 bit 合成的組合，恰好會有 2<sup> n</sup>不同的可能排列。
另外，扣掉 bit 外，也順便介紹一下其他電腦的容量單位。
名稱|換算
-|-
Bit|X
Byte|1 Byte = 8 Bit
KiB|1 KiB = 1024 Byte
MiB|1 MiB = 1024 KiB
GiB|1 GiB = 1024 MiB
TiB|1 TiB = 1024 GiB
PiB|1 PiB = 1024 TiB
EiB|1 EiB = 1024 PiB
ZiB|1 ZiB = 1024 EiB
嗯，下面全部都是以 1024 為單位。雖然這個是最精準的換算，但那個數字實在太醜了，並不好運算，所以在生活中，我們往往會希望它是以 1000 為單位。各位常聽到的```KB```、```MB```等，就是用 1000 來換算的，使用上也比較方便，惟要注意不可以加上中間的那個```i```，才能區分這是估算值或實際值。
### XOR
接下來要介紹的是 XOR。首先為了避免各位忘記之前之前別堂課教過的性質，我於此再重申一次。對於任何一個 boolean，我們可以（也習慣）使用 **0** 來代替 false，使用 **1** 來代替 true。
那也簡單複習兼帶過一下 and 與 or 兩個邏輯閘，如下圖：
> **這是 and，符號為 &**
&|0|1
-|-|-
0|0|0
1|0|1
> **這是 or，符號為 |**
｜|0|1|
-|-|-
0|0|1
1|1|1
只要用 boolean 的角度來思考，以上兩個閘並不難理解，接著進入真正的主題 -- **XOR**。
XOR 的中文是 **邏輯互斥或**，但我並不覺得中文會讓其比較好理解，所以參考即可。同時它的符號為 ⊕，不要問我怎麼打出來，我也是用複製的。總之先來觀察看看它的表格吧：
⊕|0|1
-|-|-
0|0|1
1|1|0
用最白話的方式來講，定義 ⊕ 為 **這兩個數字是否不一樣**，不要把它想太複雜。
而 XOR 的概念經常被用在密碼學中。除了其 0、1 的分布在 4 種可能中是平均的，也因為其具有以下性質。在閱讀的時候可以親手算算看，證明我沒在唬爛你：
- 交換率
```A ⊕ B = B ⊕ A```
對，應該沒什麼需要多補充的
- 結合率
```(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)```
同上，這邊也很好理解
- 與自己 XOR 時會變成一坨 0
```A ⊕ A = 00000...```
因為對上自己，那不是 0 對 0 就是 1 對 1 嘛，而這兩者都會得 0，是故
- 與一坨 0 做 ⊕ 後，什麼也不會改變
```A ⊕ 00000... = A```
無論原文是 0 或 1，對到 0 都恰好會得到自己本身
---
雖然目前聽起來很雜，不過上面這幾個性質，在我晚點講到 **One Time Pad** 時會再次用到。然後我到時候一定會叫你回來挖這段，所以不如現在就先記住：）
## 編碼
> 如果每個 bit 只能儲存二進位數字，那電腦豈不是只能儲存數字，文字要怎麼辦？
如果你還記得我前文提過的**編碼**，有提過這是為了資料傳輸方便而創，而所謂方便就是用在這邊。用最白話來說，編碼就是把賦予字符自己的編號，以讓電腦能夠儲存，或讓我們能夠更快速簡短地傳遞資訊。
### ASCII
這個你們應該很熟 XD。全名 **A**merican **S**tandard **C**ode for **I**nformation **I**nterchange，如果你和我一樣喜歡講一堆沒人聽得懂的鬼話，可以稍微記一下。ASCII 收錄了大小寫英文字母、數字、常用符號，以及古老電腦需要的一些指令，本身無法被看到。具體來說，ASCII 中包含 95 個真的能顯示的字元（空白字元也算），與 33 個無法顯示的指令。這邊針對**無法顯示的指令**做一些舉例，例如編號 9 的字元是鍵盤上的 ```Tab``` 鍵，或編號 127 是鍵盤的 ```Delete```鍵。以下是 ASCII 表：
上面的 Dec 表示十進制，Hx 表示十六進制，Oct 表示八進制。
同時可以發現，能顯示的字元分布在 32 ～ 126 間，其他都是無法顯示的字元。
### Unicode
OK，下一個問題
> 解決了英文與數字的顯示，中文或其他奇怪語言要怎麼辦，他們沒人權嗎？
當然有，這就是 Unicode 存在的意義。Unicode 被翻譯成**萬國碼**，如其名，它的存在使命就是為了把世界上所有的字元系統化，給他們屬於自己的編號。同時 Unicode 是個很通用的編碼系統，除了始終居於常用程式語言排行榜前排的那個傢伙，Java 語言會吃 Unicode 外，如果你有嘗試更改 Windows（其他我沒用，所以也不知道QAQ）的語言，也會看到這個詞。
Unicode 有屬於自己的統一格式，非常容易辨識。每個 Unicode 都會以 **U+** 開頭，後面接一串十六進位數字，代表字元的編碼，例如 **U+A2F9**、**U+A51C** 等。
Unicode 一開始推出的版本被稱為 **UCS-2**，值域從 **U+0000 ～ U+FFFF**。4 個 16 進位的數字，共會有 16<sup>4</sup> = 65536 種組合，而 65536 = 2<sup>16</sup>，故一個 UCS-2 的 Unicode 會占用 2 Bytes，也就是 16 bits。
雖然 65536 個字元已經可以表達一堆東西，所以後來 UCS-2 又被開發出了擴充集，稱為 UCS-4，值域從 **U+00000000 ～ U+7FFFFFFF**，後面的值域只是單純沒有東西可以填入，所以暫時為空白罷了。8 個 16 進位的數字共會有 16<sup> 8</sup> = 2147483648 = 2 <sup>32</sup>種組合，不難看出它占用的空間會是 4 Bytes。
UCS-4 已經包含目前所有你想得到的字元了，從中文到日文漢字、從象形文字到馬雅文字，實際上世界上的字元數量可能沒有你想像中的多w。
By the way，由於 UCS-4 所佔的容量過大，明明只是要輸入一個簡單的英文也要占用 32 bits，後來發展出了一套輔助 Unicode 的系統，名為 UTF-8，有興趣的可以再去看看，這邊就不多做贅述了。
### base 64
下一個是 base-64，它與前文所述的較不同，是為了方便傳輸資料，而非用於儲存資料。當我們要傳遞一堆字串的編碼，aka 一坨二進制數字時，就能用 base-64 來簡化。
之所以被稱為 **64**，是因為此邊碼都是以 6 bits，共 64 種組合為單位。具體運作步驟如下：
1. 把原字串的邊碼化成二進制並連接（見上圖 **bit狀態** 那欄）
2. 承上，如果原字母的數量並非 3 的倍數，補上 **與下個 3 倍數的差距** 個，長度為 8 的 0 字串。（上圖 **bit狀態** 那欄中，＂(空)＂即是補位下去的）
3. 以 6 個 bit 為單位，進行重新分組（見上圖 **索引值** 那欄）
4. 把每組的值拿去對照 base-64 表，轉成編碼。值得注意的是，如果該組的 索引值是0，且全部的 bit 都是來自於補位，則該組會轉成等號（=），而非 A。
> 註：不同地區的 base-64 表可能有些微差異，主要差別在 62 與 63 那兩格，會使用什麼字元補
而事實上，不一定要是 ASCII 才能進行 base-64 編碼，只要是任何能轉成二進制的編碼，都可以使用。最常見的例子是 Youtube 連結，最後面的那串即是 base-64。拿各位最熟悉的那個連結來舉例好了：
> https://www.youtube.com/watch?v=dQw4w9WgXcQ
懂的都懂，甚至看連結就知道裡面是什麼了。而在 **watch?v=** 後面那串，全部都是 base-64。
順帶一提，下面這個網址也能證明 Youtube 連結的格式，會在 watch?v= 後面接 11 個 base-64 編碼。而且其影片內容也是關於這個，講得滿有趣的，無聊也能去翻翻看
> https://www.youtube.com/watch?v=j--cLVoyurM
## Shared-key Cryptosystem，對稱式加密
講完前情提要，現在終於可以正式進入計算機加密的世界了。首先要介紹的加密種類是 **對稱式加密**，又被稱為 **共用金鑰密碼系統**，它並非特定加密系統的名稱，而是一個分類、一個總稱。
順帶一提，我之後講的所有加密，都要先把明文化成編碼。如果你開心，也能在加密後再次利用密文重新編碼。只是正如我前面所說的，編碼本身不具任何安全性，僅是為了方便傳遞、儲存罷了。
### 這是什麼鳥東西
我們假設有兩個人，台灣獼猴與花心鬼，前者要傳遞訊息給後者（他們的圖片自己去挖我簡報），並且使用對稱式加密，則流程應該如下：
```
1. 台灣獼猴與花心鬼先溝通好一把金鑰，雙方都知道且不可外流
2. 台灣獼猴使用該金鑰加密自己的訊息後傳給花心鬼
3. 花心鬼再使用同一把金鑰進行解密
```
簡單來說，對稱式加密最大的特色是，加密與解密皆使用同一把金鑰，一但金鑰外流整則訊息就會被破解。我們至今學到的所有古典密碼，包含凱薩、維吉尼亞、恩尼格碼，全都屬於這種方式。
對稱式加密主要的優點為其速度快，因為加解密使用的金鑰不變，所以對金鑰的需求量較小（可以跟後文的非對稱式加密比較）。缺點則是安全性相對較低，在兩人溝通金鑰的同時，如果不多加注意很容易被竊取，會直接造成日後所有加密失效。
### One Time Pad
希望你還記得我在講 XOR 時，提到的這個名詞。如果我預言成功，你已經忘記 XOR 的那堆性質，那你可以先暫停閱讀，乖乖回到那段去複習了 XD。總之，結合 XOR 的性質後，可以再推出下面這條公式
> A ⊕ B ⊕ A = (A ⊕ A) ⊕ B = null ⊕ B = B
當 XOR 算式中出現兩次同樣東西時，可以直接把他們一起劃掉，會等同於什麼都沒做。所以如果真的有人如此天真單純，使用同一串金鑰來做超過一次的 XOR 以進行加密，你大概就能想像他有多小丑了。
言歸正傳，One Time Pad 中文為 **一次性密碼本**，是一種簡單、暴力，但被證實安全的加密演算法。它簡單到我甚至能用一句話就解釋完，聽好囉，短到你會懷疑人生。One Time Pad 實際上在做的只有：
> 拿一串跟明文一樣長的 01 字串對明文 XOR
啊？簡潔到你難以相信？那我可以再傳一次
> **拿一串跟明文一樣長的 01 字串對明文 XOR！！！**
嗯，他的實作簡單到我也不清楚要怎麼說明，金鑰就是那個 01 字串。不然直接進入 Q&A 好了，你們可能會比較想提問（X
- > Q：為什麼金鑰一定要跟明文一樣長？
A：如果金鑰長度小於明文，那就只是變種的維吉尼亞。還記得我怎麼破解它的嗎？這會使此演算法不安全。而且如果遇到一長串 null，金鑰會直接被印出來
- > Q：一次性密碼本的優缺點？
A：優點部分，由於所有明文產生出相同密文的機率都相同，aka 在不知道金鑰的情況下，同一篇密文可以同時對應到無限多篇明文，故此演算法是被證實安全的，完全無法被破解。至於缺點，除了密鑰長到哭以外，它不能預防竄改。就算駭客不知道金鑰，還是能在不被發現的前提更改內容
- > Q：為何叫＂一次性＂密碼本？
A：此演算法的金鑰，只能被使用一次，且通常是隨機產生。如果重複使用，駭客只需把兩份密文 XOR，此時金鑰的保護已消失，就可以透過分析還原出原文了。
### 串流加密 vs 區塊加密
實際上，加密其實分成兩種：**串流加密**與**區塊加密**。所有我之前教的東西，都屬於串流加密。所謂**串流加密**，是指一次吃一個 bit 進來，再針對它進行加密，吐出由該 bit + 金鑰創造出來的密文。至於**區塊加密**，則是一次吃整陀 bit 進去，把這堆 bit 視為一個整體，再輸出由該區塊與金鑰創造出來的密文，通常會用於已知訊息長度的狀況。
### DES
**首先我要先強調，這個結構還滿複雜的，請注意自己的大腦**
DES，又稱為**資料加密標準**，是 1970 年代，美國國家標準局所提出的區塊加密方法。在我們深入了解其運作方法之前，必須先介紹**費斯妥網路**這個酷酷的東西。
#### 費斯妥網路
DES 整體都是以這個它為架構，一次費斯妥網路的簡圖如下：
搭配圖比較好講：）
> 1. 首先，DES 的每個區塊是 64 bits，它會先擷取目前要加密的區塊
> 2. 接著，把該區塊平分成左右兩塊，我先稱其 L<sub>0</sub> 與 R<sub>0</sub>
> 3. 直接把 R<sub>0</sub> 搬運去下一次網路的左半區塊，也就是 L<sub>1</sub>
> 4. 拿 R<sub>0</sub> 去經過一個特定的 function 運算，出來的結果再跟 L<sub>0</sub> 做 XOR，最終獲得下一次的右半區塊 R<sub>1</sub>
> 5. 現在我們有 L<sub>1</sub> 跟 R<sub>1</sub> 了，重複步驟 (1) ～ (4)，共要進行 16 次
了解它的結構後，再把那個**特定的 function**抓出來講會比較順。雖然實際上我也沒要說多細啦（X
#### 加密 function
首先，DES 的金鑰是一個 64 bits 的字串，但實際上會用到的只有 56 bits，剩下 8 bits 會被拿來做 [奇偶校驗](https://zh.wikipedia.org/zh-tw/%E5%A5%87%E5%81%B6%E6%A0%A1%E9%AA%8C%E4%BD%8D) ，有興趣的自己點連結去看，這邊不多做贅述。
首先 function 會先獲取金鑰，暫時稱其為 **K<sub>n</sub>**，把它> 平分成兩個部分，分別拿去做**Shift**。做完後將兩者合併，目前的這 56 bits 將做為下一次加密的金鑰，也就是 **K<sub>n+1</sub>**。
> 紀錄完後，再把這 56 bits 拿去做 **Compress**，壓縮成 48 bits，以方便等等使用，我先將這 48 bits 稱為 **K**。
> 處理完金鑰，接下來就是加密的部分了。如果你還記得剛剛的結構圖，現在它吃進來的應該是 **R<sub>n</sub>**，大小恰好為 32 bits。首先做的第一件事，是會把這 32 bits 拿去做 **Expand**，擴張成 48 bits，這樣等等才能跟大小同樣為 48 bits **K** 配合。
> 接下來才是關鍵。取做完 **Expand** 的 48 bits，加上剛剛的 **K**，兩者一同經過 **S-box**。出來後將變回 32 bits，最後再將這 32 bits，經過 **P-box** 的修飾後就完成了。
好，如果你剛剛的三個區塊看得很懵，絕對是正常現象。**Shift、Compress、Expand、
S-box、P-box**，怎麼瞬間一堆專有名詞？
在我跟你講答案前，我想先再次重申**Kerckhoffs's principle**，希望你們還記得它。任何一個設計良好的演算法，就算整套系統被外流，只要沒有金鑰都不會被破解。是的，沒錯，這正是我要丟包你們的宣言w，可以注意到，剛剛那整套落落長的系統，有用到金鑰的也就 **S-box** 一環。而其他所有東西都是固定的，不受到金鑰影響，本身也不具任何安全性，我在這邊詳細解釋只會讓本來就頭昏眼花的你們更混亂而已。是故，這些完全固定的過程，就放給你們自己 Google 了，~~一來講師的負擔較少~~，二來這些真的很好找，三來 Google 絕對能說的比我詳細，甚至能告訴你為什麼，但我今天沒時間解釋這些。
我就只挑 **S-box** 詳細說明了。實際上，**S-box** 只是我針對這步驟的簡稱，雖然我前面的圖示只有畫一個，但這個流程其實會分為 8 個部分，每個部分都會經過自己專屬的 **S-box**。而每個 **S-box** 都固定會吃 6 bits 進來，吐出 4 bits 出去。（合理吧，進入這個階段前有 48 bits，分給 8 個 **S-box** 剛好每人得 6 bits。而最後吐出 32 bits，則是因為每個 box 的 output 為 4 bits，4 * 8 = 32。）
說了那麼多，**S-box**究竟要怎麼對這 6 bits 動手腳呢？實際上還滿鳥的，就只是對照表格而已。真的，你沒聽錯，拿第一個 **S-box** 來舉例好了，它長這樣：
針對輸入進來的 6 bits，首先我們會把它的首尾取出來，假設進來的是 **110101** 好了，那就會取出 11。接下來根據首尾的值（用二進位來看），來決定等等表格要對到哪一個橫列。剛剛的例子，因為 11 = 3，所以就會對到＂3＂那一列。
接下來再利用剩下的中間四位之值，來決定要對照表格中的哪一個直行。同樣拿剛剛來說，中間剩下 1101，而 1101 = 10，因此會對到＂10＂那一列。最後出來的結果是＂03＂，再轉回二進位，output 為 0011。
#### 雜談
就算到了現代，有著各種技術的輔助，還是找不出一個辦法，能用暴力以外的方法，破解 **S-box** 提供的保護。這就是此演算法厲害的地方，明明盒昕就超級簡單直觀，但就是找不出漏洞
可惜的是，由於金鑰實際上只有 56 bits，而 2<sup> 56</sup> = 72057594037927940，對電腦來說太容易暴力破解了。2008 年時，有人締造出在一天內暴力破解 DES 的紀錄，這也證明了此演算法不再安全。
不過這個想法還是不錯的。為了解決金鑰太短的問題，DES 日後又出現了 3-DES、AES（Advanced Encryption Standard，進階加密標準）等變體，有興趣的人不妨自己去了解看看吧
## Asymmetric cryptography，非對稱式加密
介紹完對稱式，相信你們會接著好奇非對稱性加密在幹嘛吧
~~希望你們不只有＂大腦死機＂的感受，如果累了可以先休息一下等等再回來繼續閱讀~~
非對稱式加密，又稱公開金鑰密碼系統，同樣是一個總稱，而非單指特定一個演算法。
**要把金鑰給公開？** 這怎麼聽都讓人匪夷所思，我懂。其實與先前介紹的不同，這邊的金鑰共有兩個：其一是可以公開，被自由傳遞使用的，被稱為**公開金鑰**或**公鑰** ; 相對會有一個絕對不能外流，只有自己一個人能知道的金鑰，被稱為**私密金鑰**或**私鑰**。
### 所以，這到底是什麼鳥東西
假設有兩個人 -- 台灣獼猴與花心鬼，然後台灣獼猴又又又要傳送訊息給花心鬼了。如果使用非對稱式加密，則大致步驟如下：
> 1.接收訊息者，在這裡是花心鬼，先打造屬於自己的**私鑰**，以及能夠外流的**公鑰**
> 2. 把**公鑰**傳給台灣獼猴，台灣獼猴使用**公鑰**加密自己的訊息
> 3. 密文傳給花心鬼，花心鬼再用**私鑰**來解密
到這邊，可以發現這套系統與對稱式的差異極大。首先是方向性，在非對稱式加密中，一＂套＂金鑰只能供一個方向的訊息傳遞使用，是單向的：假設花心鬼要回送訊息給台灣獼猴，則台灣獼猴要再打造一對屬於它自己的金鑰。
這麼做有什麼好處呢？由於我前面是說，公鑰可以自由地被傳遞使用，所以就能實現多對一的通訊。只要把公鑰放出去，所有人都能透過那份公鑰安全地傳送訊息給自己。
另外就是安全性問題，因為私鑰從頭到到尾都無須傳送給任何人，駭客根本就沒有攔截的餘地，整體安全性相較對稱式加密而研安全非常多。
而此類演算法最大的缺點，除了運算速度真的很慢外，大概就是對金鑰的需求了。每次要開通一個新的傳遞方向，就需要多打出兩把金鑰，在多人互相傳遞訊息的情況下，其實還滿惱人的。
### RSA
接下來要介紹的是 RSA 加密演算法，這是一個被證實安全，而且廣用的區塊加密。由於此演算法牽扯到數論，礙於課程難度與常度的限制，我恐怕難以向各位解釋**這為什麼不會爛掉**，頂多只能證明**ㄟ這真的是好的**給各位看而已。
如果你真的超級好奇，可以先去把基礎數論翻一下。這邊會牽扯到的應該只有歐拉定理、模反元素。或著你可以去問 @Aaw，超級強學長。總之我先帶過 RSA 的步驟吧
> 1. 選擇兩個超級大的質數 p、q，大概落在 10<sup> 20</sup>左右，並相乘兩者得 N，N 即是公鑰的一部分
> 2. 計算出 r = (p - 1) (q - 1)
> 3. 找出一個與 r 互質的正整數 e，e 也是公鑰的一部分
> 4. 找出 e 在模 r 下模反元素 d，用白話文說就是，找出一個數字 d，
> 使得(e * d) % r = 1，此即為私鑰
> 5. 加密：使用公鑰 N 與 e，讀入區段後，令其中一個區段的值為 m，計算
> m<sup> e</sup> % N，產生出來的數字就是密文
>6. 解密：計算 密文<sup> d</sup> % N，即可回推出明文
聽起來不難，但感覺很莫名其妙對吧？如果你有打算要繼續往電資圈走，之後絕對會接觸到數論的，等讀完再回頭看應該會明朗很多
那為何 RSA 是安全的呢？事實上，如果要破解 RSA 加密，則一定要或得最一開始訂的那兩個 p、q。換句話說，不把 N 給質因數分解是做不到的。這也是為何一開始會要使用者訂兩個超級大的質數，因為對 p * q 做質因數分解，就一般電腦而言是非常困難，幾乎不可能的。我們先不要討論量子電腦，~~那傢伙會毀了密碼學世界~~
順帶一提，我的簡報中有附上關於 RSA 的扣（其實是 Aaw 寫的），可以讓你們自己測試或玩玩看，至少體驗 RSA 的過程是真的能用，並非我在唬爛。
## 密鑰交換
既然之前有提到，＂非對稱式加密因為沒有傳送私鑰的過程，所以相對安全＂。那究竟要如何做到對稱式加密裡的第一步，**建立一個雙方都知道的金鑰**呢？難不成真的要用心電感應？
如果真的有心電感應，那的確會成為效率最快的辦法。切回現實的話，我們要怎麼在確保安全的前提下，把金鑰傳送給對方？可能會有人覺得
> 為什麼不用加密演算法來加密金鑰就好
痾，這想法還不錯，但會進入 while(1)。如果要使用加密演算法來加密金鑰，那勢必會需要另一組金鑰，來確保此加密演算法是安全的。這樣問題又回歸原始，我們要怎麼傳送這個金鑰？所以此方法顯然是不可行的...？
### Diffie-Hellman key exchange
其實真的有專門為交換金鑰而設計的演算法，名為 Diffie-Hellman key exchange，aka
迪菲-赫爾曼金鑰交換。這個演算法不需要其他金鑰保護，所以並不算是一種加密。同時它也有牽扯到數論，就是剛剛 RSA 的那坨東西，所以我等等同樣會跳過一些東西，敬請見諒。
```
我們先定義一個 function M，假設此 function 能夠吃進兩把金鑰 A、B，
並將他們兩個金鑰合併，輸出合併後的金鑰 A-B
同時，合併後的金鑰具以下性質：
－即便得到了 A、A-B，也無法從 A-B 中單獨將 B 提取出來
－順序不會影響合成的金鑰，即 A-B = B-A
－把同樣兩把金鑰合成會得出新的金鑰，即 A != A-A
```
定義完 function 後，以下為迪菲-赫爾曼金鑰交換的過程，同樣請到台灣獼猴與花心鬼登場：
> 1.先建立一把公鑰 **P**，這把公鑰台灣獼猴跟花心鬼都知道，不用擔心安全性，直接傳就好了
> 2. 台灣獼猴跟花心鬼各自製作一把只有自己知道的私鑰 **A、B**
> 3. 兩者都利用 function M 來合併公鑰與自己的私鑰，製作出 **P-A、P-B**，並傳給對方
> 4.再拿收到的合併金鑰與自己的私鑰結合，製作出 **P-A-B**，這個就是最後能使用的金鑰
讓我們看看為何這是安全的：從頭到尾被傳送出去的資訊只有，**P**、**P-A**、**P-B** 三個，而駭客無法使用這三個元素拼湊出 **P-A-B**，所以他根本就沒有得知真正金鑰的機會
- 混成加密系統
公鑰跟私鑰...不覺得這兩個詞很熟悉嗎？剛剛的迪菲-赫爾曼金鑰交換，似乎有點像非對稱式加密？有沒有一種方法，能結合對稱式與非對稱式，擷取雙方優點使用？
誒，還真的有，而且這東西超級簡單。既沒有數論，也沒有煩躁的邏輯閘。它被稱為混成加密系統，單純到我直接上步驟，你們大概就能看懂了，請花心鬼跟台灣獼猴死者蘇生：
> 1. 花心鬼製作公鑰與私鑰，把公鑰傳給台灣獼猴
> 2. 台灣獼猴利用該公鑰，來加密**對稱性的金鑰**
> 3. 台灣獼猴把**加密後的對稱性金鑰**傳給花心鬼
> 4. 花心鬼拿私鑰解密**對稱性金鑰**
對，真的就只有這樣。簡單來說就是它拿非對稱式加密系統，來加密對稱式加密系統的金鑰，且日後都使用該金鑰來進行對話。~~現在知道為何我前面，＂所以此方法顯然是不可行的＂後面要加問號了吧~~。並非此想法不能用，只是用的方法錯誤罷了。
## 應用
最後要說的就是密碼學本身的應用了。前面扯了很多有的沒的東西，那密碼學除了加密、解密資料外，還能有什麼其他用途？
### Hash
你們有發現一件事嗎，我在剛開始敘述＂密碼學三大分類＂時，明明就分成了三類，但到現在整份講義快結束了，還是有一個分類沒被我講到 XD。Here it is，台錢拖了那麼久只單純因為我把它歸類在應用。
希望你們還記得它在幹嘛，因為我不打算重講一次：）
#### 雜湊碰撞
之前講義中有這句話，其中伏筆實際上滿深的
> 如果出現兩個不同的 output，則能夠保證進來的兩個 input 絕對不同
不過，既然都可以被稱為**函式**了，應該是要反過來，一個 y 只能對應到一個 x，這樣的敘述看起來不怎麼符合函式性質。
事實上，Hash Function 真的不符合。當＂一個 output 對應到不只一個 input＂這種狀況出現時，被稱為**雜湊碰撞**。
或用另一種方式來說，兩個不同的輸入，還是有極低機率會出現相同的輸出。至於那個機率有多低，就要視使用哪一種 function 而定了。以下列舉出幾種常見的 Hash Function，以及他們發生雜湊碰撞的機率。
> MD5 -> 1.47 * 10<sup> -29</sup>
> SHA-1 -> 1.00 * 10<sup> -45</sup>
> SHA-256 -> 4.30 * 10<sup> -60</sup>
雜湊碰撞其實算是一種漏洞，因此發生雜湊碰撞的機率越低，代表此 Function 的**抗碰撞性**越高，安全性也會跟著上升。
#### 常見 Hash Function 介紹
名稱|安全性|輸出大小|說明
-|-|-|-
**MD5**|低|126 bits|非常古老的一個系統，目前的抗碰撞性已被攻破，不再具備保護力
**SHA - 1**|低|160 bits|SHA 家族中的初代，改編自 MD5，兼容性極高。但原因 MD5 容易被攻擊的結構依然存在，所以近幾年已被暴力破解，變得很不安全，不建議使用
**SHA - 2**|中|不一定|改編自 SHA - 1，增加了其安全性，但 MD 結構仍然沒有被更動，頂多只能說**目前尚未被破解**，未來被破解的機率其實滿高的。它擁有許多變體，以其輸出大小來命名，例如 SHA - 256 就是其中一個分支，輸出大小為 256 bits
**RIPEMD - 160**|中|160 bits|由歐盟所提出，被比特幣所採用。但這個 function 並不算很安全，比特幣會採用它，只是因為它是所有目前尚未被攻破的選項中，輸出長度相對短的一個
**SHA - 3**|高|不一定|為了解決 MD 結構所延伸出的問題，翻新整個結構，是目前 SHA 家族中安全性最高的一個。同時與其它不同，此家族支援無上限的 input 長度，不會再受到限制
#### Hash Function 可以拿來幹嘛
- 預防軟體被竄改
由於 Hash Function 擁有，＂只要任何一個 bit 被修改，輸出結果就會大幅改變＂的性質。只要把整套軟體都拿去做 Hash，這樣在軟體遭到修改時，即便只是一個非常細微的地方，也能馬上被偵測到。
- 儲存密碼
> 你該不會天真地以為，你在各網頁的密碼，都是用明文儲存吧
曾經有人說過，密碼用明文儲存，跟裸奔的概念相差不遠。實際上，使用者的所有密碼在網頁後台，都是以 Hash 的方式儲存，一來防止網頁的 Manager 對使用者的帳號進行盜取，二來如果網頁後台真的被攻破，則使用者的密碼是安全的。
有趣的一點是，在儲存密碼時，通常會在使用者的密碼後面加上 **salt**，我也不知道那中文是什麼，但翻譯大概不是**加鹽**。**salt** 是一串隨機數據，作用是為了把每個使用者的密碼，特別是超級爛的密碼，獨立出來存成不同 Hash。畢竟各位也知道，不管再怎麼宣導，12345678 這種垃圾密碼還是有一大堆。
### 訊息鑑別碼
一開始曾經說過，在資訊傳遞上，可能會遭遇 **竊聽、竄改、電子欺騙、抵賴** 四種攻擊。**竊聽**的部分我們已經透過加密來防禦了，那其它的呢？
現在要講的訊息鑑別碼，就是為了預防**竄改**而誕生的。概念大概就是在傳送密文時，透過一把新的金鑰 **P<sub>T</sub>**，以及密文本身，產生出一個 **tag**，與密文一併傳過去。訊息接收方在收到密文時，會先再次拿 **P<sub>T</sub>** 與密文去嘗試產生 tag，驗證自己產出的 tag 是否與收到的吻合。
由於 tag 是從利用密文得來的，所以一旦密文遭到竄改，產生出來的 **tag** 就會改變，此時訊息接收方就能發現，收到的訊息是經過竄改的。
到這邊可能又會誕生出一個問題：
> 駭客在竄改訊息的同時，順便把 tag 也改一改不就好了
This is why 我有強調，要拿一把**新的金鑰**來產生 tag，當駭客在沒有金鑰的前提下，即便他想連帶竄改 tag，也無法創造出合理的結果。tag 的生成要素有密文跟金鑰，缺一不可，單單擁有竄改過的密文是做不了任何事的。
### 數位簽章
解決完竄改後，接著我們來看**抵賴**。想要解決**抵賴**的關鍵在於，要想辦法創造出一套制度，能夠保證此訊息是由某人發出的。由於這個概念與現實中的簽章類似，因此此制度被稱為**數位簽章**。
如果要把**數位簽章**說得簡單一點，它其實是反過來的非對稱式加密而已：使用私鑰加密，使用公鑰解密。
一般來說，訊息傳送方會先把明文轉成 hash，接著拿自己的私鑰對該 hash 做加密。收到訊息者只要先用解密訊息的金鑰取出明文後丟進 hash function，再拿用於數位簽章的公鑰去解密收到的加密 hash，並確認兩者是否相同即可。或許這聽起來有點玄，但是真實存在且能使用。不過我還是稍微放了一點 Q&A 進來，首次聽到這個東西，內心產生一堆疑問是正常的
- > Q：為什麼一串加密過的密文，可以當成簽名用？
A：由於公鑰與私鑰是成對的，如果一個人發出來的密文，有辦法被公鑰解密，則代表該訊息絕對是由本人發出。同時因為私鑰只有自己知道，能防止抵賴的發生
- > Q：如果是用公開金鑰解密，那數位簽章不就沒機密性了？
A：確實，不過我現在又不是要加密訊息，機密性並不怎麼重要。使用數位簽章的目的一直就不是為了保護訊息，當然還是要用安全的算法來加密明文，數位簽章僅能保證其完整性與防止抵賴。
- > Q：數位簽章不是很容易被駭客任意複製嗎？
A：首先，簽名本來就是簽給別人看的，複製數位簽章沒有意義。同時針對不同消息，給出的數位簽章也會不同，所以不用擔心濫用的問題
### 數位憑證
最後就是電子欺騙了。由於電子欺騙的性質是無中生有，駭客可以直接連同整套數位簽章、訊息鑑別碼都使用偽造的，反正他自己就是站在訊息發送方的角度。而**數位憑證**正是拿來解決此問題的。
**數位憑證**的做法，就是請第三方幫你背書，確定訊息發送方是本人而已。專門在做這門事的公司，被稱為 Certificate Authority，簡寫為 CA。
具體做法是，數位憑證的申請人，會將足以證明個人身分的資訊、自己的數位簽章、數位簽章的公鑰丟給 CA。而 CA 在驗證通過後，會頒布數位憑證給申請人，內含申請人的數位簽名、公鑰，以及**CA方自己的數位簽名**，以證明此消息是經過第三方驗證，值得信賴的。
好耶，我感受到又又又又又有人要提問了
> 倘若連 CA 都是駭客偽裝的？
不得不說，能想出這問題的人，腦洞真的滿大的。不過業界的確有防範這種事情：一般剛成立的 CA，會去找更老牌的 CA 來為自己背書，證明自己是合法的公司，並非由駭客或有心人士假扮，最後形成下圖一般的樹狀圖：
至於位於樹狀圖頂端的那間 CA...就真的找不到辦法驗證了。換言之，對世界上任何一家 CA 的信賴，都是源自於頂端那家母公司，而且是單純人與人間的信任而以，沒有任何人能背書。好消息是至今這套系統都是好的，頂層 CA 並沒有背叛世界對其的信賴。
## source
石田寶輝, & 宮崎修一. (2017). 演算法圖鑑 (謝孫源, Ed.; 陳彩華, Trans.). 城邦文化. https://webpac.tphcc.gov.tw/webpac/content.cfm?mid=788600&m=ss
Chou, A. (2018). 應用密碼學入門. https://hitcon.org/2018/CMT/slide-files/d1_s2_r4.pdf
Starpt. (2021). 密碼學基本概念. HackMD. https://hackmd.io/@DIuvbu1vRU2C5FwWIMzZ_w/ByUf1sdRr#%E5%AF%86%E7%A2%BC%E5%AD%B8%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5
舒靜雯. (2021, May 13). 密碼學簡介. https://drive.google.com/drive/folders/1tk3exZ-RkdDTHtlcalBrMGf16xdgp8NC?usp=sharing
Gibson, T. (2020, April 1). Kasiski Test. YouTube. https://www.youtube.com/watch?v=asRbswE2hFY
梗你看電影 X. (2022, January 16). 【H&M 365 EP. 16】齊默爾曼電報 - 咦？皇帝隨便說說的話，你外交部長竟然當真？ /《金牌特務：金士曼起源》The King’s Man, 2022 | PODCAST.YouTube. https://www.youtube.com/watch?v=tR-DH9cIz64
森纳映画. (2022, July 1). 【不止遊戲】二戰德軍號稱「謎」的密碼機，究竟是如何使用的？. YouTube.
https://www.youtube.com/watch?v=kE3Xb-XH8NU
Unknown. (2022, June 13). Unicode. Wikipedia. https://zh.wikipedia.org/wiki/Unicode#%E7%BC%96%E7%A0%81%E6%96%B9%E5%BC%8F
Shin-ming , C. (2016, August 9). 2-9 資料加密標準(DES). Youtube.
https://www.youtube.com/watch?v=WnsgWK0DOOM
洪âng春男chhun-lâm. (2020, May 18). RSA公開金鑰的加密與解密方法. YouTube.
https://www.youtube.com/watch?v=YZ8iMkxmGkI
Sign in with Wallet
Connect another wallet