Cryptography筆記1 - 簡介與歷史

密碼學核心

1. 如何建立secret key: alice和bob要建立shared secret key，並且確認雙方的卻是alice和bob
2. 如何建立兩方安全通訊: 保持通訊內容完整性(不被竄改)以及隱密性(不被監聽)
3. digital signatures
4. anonymous communication: digital coins issues (double spending)
5. 匿名投票
6. 匿名拍賣
7. 委外encrypted computation
8. zero knowledge (proof of knowledge): bob只知道某個puzzle 題目(例如N = p*q，pq都是質數)，如果 alice能證明他知道pq (但是不揭露p q)，則信任可以建立

其中5和6基本上是一種 secure multi-party computation problem，主要目標就是不顯露每個人的投票意圖，但是只顯露投票結果，以下是一個常用的笨方法，就是一個"宣稱"保證自己安全公平的計票中心:

不過密碼學的理論證明，完全不需要計票中心的存在，能達成匿名投票，透過投票者間的秘密通訊就可以，例如以下示意圖:

第7點，目前甚至可以把你要做的內容加密，外包商可以在不知道內容的情況下，幫你做事(可能透過hash)，然後回傳加密過的答案給你，例如google search (沒聽過這樣的服務):

Symmetric Ciphers歷史

這是兩造都持有同一個secret key (所以叫symmetric) 來做加解密:

1. substitution cipher (古希臘時期，被破解) : E/D就是參照同一份簡單隨機的mapping table (這就是上圖中的key k)，例如以下:

如果此mapping table在每次加解密都是固定的，那就不能稱為一個cypher，因為等於沒有key，cypher定義key是隱密的，隨機的。

如何破解substitution cypher?
首先這個mapping table如果以英文字母來說，其sample space(正確應該叫key space)是 26!，因為a有26選擇，b有25選擇(被a選走一個)，c有24選擇(被ab選走兩個),...。

26! ~= 2^88，也就是要描述這個key 需要88 bits，這個key space大小並非不安全。

破解substitution cypher，透過找出英文字母中高頻率者，例如 "e"，根據統計占了英文文件的12.7%的出現機率，則如果統計一個加密過的cypher text，出現頻率最高的是"e"的機率也最大，可以假設是"e"來進行比對。利用統計頻率來解碼，大概以下兩種可能:

這是最糟的cypher，因為攻擊者只需要知道cypher text，就可破解!!


2. vigener cipher (文藝復興時期，被破解) :  這利用某個alphabet(例如英文)組成的key ，重複排列，然後與message做function mapping，例如f("C", "W") = ("C"+"W") % 26 = (3+23) % 26 = 0 = "Z"

解碼也是一樣，因為 c = (k + m)%26，c是 k+m / 26 的餘數，如果:
1. k+m < 26 ，則 c = k+m => m = c - k
2. k+m = 26，則 c = k+m => m = c - k
3. k+m > 26，則 c = k+m-26 => m = c - k + 26

以上三種cases涵蓋了所有可能，其中 第三式 c-k+26 涵蓋了1,2式，所以通式可以寫成:

m = if (c - k >= 0) c-k else c-k+26

怎麼破解呢?  這邊用到了一個假設（不知證實否）：既然"E"是最常出現的英文字母，則encrypted "E"也應該是最常出現的cypher text。

如果知道key的長度(e.g. |CRYPTO| = 6) ，先把cypher text 拆成6個一組，然後觀察每組的第一個字母組成的set 稱之為{c1}，找出出現頻率最高者，就可以假設他是encrypted "E"。例如{c1}中出現頻率最高的字元是"H"，則此時我們可以認為"H"是"E"的encryptio結果，則公式中m = "E"，c = "H"，則k就可以找出來了！換句話說，我們找出key的第一個字母了: k = c - m +26

"H" - "E" + 26 = "C"

利用上面的邏輯，執行6次可以把每個key character找出來。

但是如果一開始不知道key長度? 也沒關係，可以假設|key| = 1，然後找出key之後，試著把整篇message都解碼，看看有沒有意義，如果沒意義，那就嘗試|key| = 2，找出|key|=2時的key之後，來解碼message看有沒有意義，終究嘗試到有意義的解碼後的message時，就可以確認找到正確的key (此時key length已經不重要）。　

這是最糟的cypher，因為攻擊者只需要知道cypher text，就可破解!!

3. rotor machines cipher (19～20世紀，被破解) : 19世紀開始，利用複雜機械裝置的cipher開始流行起來，其中一個有名的稱為 the Hebern machine:

像打字機一樣的機器，中間的圓柱體就是藏有key的disc，當每次輸入一個message character m，則key disc轉動一個字母，這個key disc事實上就是一個動態的subistitution table，舉上圖左為例子：

按第一次"C"，則"C"被encypt成"T"，然後disc轉動一個字母，新的substitution table形成
按第二次"C"，則"C"被encypt成"S"，然後disc轉動一個字母，新的substitution table形成
按第三次"C"，則"C"被encypt成"K"，然後disc轉動一個字母，新的substitution table形成

最終發展出了複雜的Enigma (3~5 rotors):

不過.... 仍然逃不過文字頻率的邏輯攻擊，這是最糟的cypher，因為攻擊者只需要知道cypher text，就可破解!!

4. 進入數位時代　（１９７４）

IBM提出了DES，只有2^56 key space，一次可以encrypt 8 bytes，但是現在已經很容易被高速cpu brute force破解了，不應該再用！

之後會詳細提到AES。