密碼學基礎

預備知識：
1. 在討論密碼學時，一般以柯克霍夫原則為前提：即使密碼系統的任何細節已為人悉知，只要密匙未洩漏，它也應是安全的。其他常見前提如下：( Image from Wiki )

2. 完善保密性：若暗文有完善保密性，那麼攻擊者不可能解讀明文中的任何一個片段。
3. 生日攻擊：根據生日悖論的發想，對 n-bit 的雜湊函數，嘗試約 2^( n / 2 ) 次便幾乎一定會產生碰撞，這個上界又稱為 Birthday Bound。進一步的，衝突攻擊雖然完全對破解密碼沒有幫助，卻可以幫助偽造電子簽名 ( Image from Wiki )。

( 若不了解 RSA 和電子簽名可先跳過 ) 大致如：假設利用雜湊 ( 如 MD5，為了效率 ) 對某個文件 A 轉換後，要求被攻擊者用 RSA 的私密鑰對其加密，驗證時檢測方利用被攻擊者的 RSA 的公共鑰解密，根據電子簽名的原理，以上程序完成後，若結果和文件 A 的雜湊值相符，便能證明被攻擊者同意文件 A 裡的內容。考慮一個攻擊者拿著一個無害的文件 X，和一個有害的文件 X'。現階段 hash( X ) 幾乎不可能等於 hash( X' )。但是，考慮對兩個文件都分別亂加空白，空行，污漬等等，產生大量的版本，假設各有 N 個版本 ( 而內容實質不變 )。很顯然可以用 O( N ) 的時間複雜度檢查所有版本裡是否有某個 X 和某個 X' 有相同的雜湊值，並檢測 N^2 組可能。此時若對象為 2^64 的雜湊函數，那麼僅僅需要各枚舉 2^32 個版本，就能以 O( 2^32 ) 的複雜度，期望上得到一組 X 和 X' 有相同的雜湊值。此時只要再請被攻擊者對該版本的無害文件 X 進行電子簽名操作，就能以它頂替有害文件 X' 的電子簽名，成功進行偽造。雖然 MD5 為 128 bit，但利用更好的搜索方式，依然可以實現 ( 也已被證實並實現 )。
4. 原像攻撃：
__第一原像攻擊 ( Preimage Resistance )：對 hash 函數的回傳值，攻擊者知道對應的參數
__第二原像攻擊 ( Second-preimage Resistance )：對參數 x1，攻擊者知道 x2，x2 ≠ x1 且 hash( x2 ) = hash( x1 )
5. 單向函數：一個理想的雜湊函數，應該要接近單向函數，也就是擁有參數很容易得到結果，但從結果得到參數必須是困難的。

對稱加密、私鑰加密、共享密鑰加密 ( Symmetric-key Algorithm ) :
概述：雙方預先決定好密碼，並以該組密碼對明文加密和解密。因此擁有密碼等價於擁有明文。
例：
__1. 歷史記載最古老的暗號，斯巴達的將軍將紙整齊地纏在棍子上做橫式書寫，需要有粗度相同的棍子才可解讀。
__2. DES
__3. WEP：由於鑰匙種子串流長度只有 24 bit，很容易暴力破解。除此之外，基於很容易產生密碼串流的碰撞，可以利用一些數學性質破解。這裡有大略的 WEP 的算法過程。

我的理解如下 ( Image from Wiki )：
根據生日攻擊，很快得到三個鑰匙種子 ( IV ) 相同的暗文 C1, C2, C3 後，兩兩成對異或後，便能得到 ( M1 XOR M2 ), ( M2 XOR M3 ), ( M3 XOR M1 )，有這三項便能求出這三個暗文分別對應的明文。
缺點：有幾個對象就必須具備幾組密碼; 預先決定密碼的過程可能被攔截，而交換密碼的過程亦希望能經過加密而產生矛盾
補充：
__1. 一般又可以分為以下兩種加密方法：
____a. 流加密 ( Stream Cipher )：將數據化為位元串流，密碼為相同或以上長度的位元串流，進行異或操作後為暗文。
____b. 分組密碼 ( Block Cipher )：將數據化為位元串流後，分塊分別進行異或操作後得到暗文。
__2. 訊息鑑別碼( Message authentication code MAC )：以防攻擊者進行中間人攻擊，任意竄改傳遞中的訊息，雙方可以事先約定一個以暗文和鑰匙為參數的某個函數，作為附加，稱為訊息鑑別碼。若解密後，前述的函數回傳值和訊息鑑別碼不一致，便可以確定訊息有被竄改。

公開金鑰加密、非對稱加密 ( Public-key Cryptography )
概述：為了閃避對稱加密的交換密碼產生的風險，不進行「鑰匙」的交換，而是接收者將「鎖」公開後，傳送者利用接收者公開的鎖對明文進行加密，此時只有擁有對應的「鑰匙」的接收者可以解讀明文。
例：
__1. RSA：考慮兩個極大的相異質數 P, Q。令 N = P * Q。收信者找一組適當的 a ( a 必須與 N 互質 ) 和 b ( 為 a 的模逆元 )，也就是使得 a * b = 1 ( mod N )，並公開 a 和 N，要求送信者將明文 T 變為暗文 T' = T^a ( mod N )，那麼 T'^b = T ( mod N )。在不知道 P 和 Q 的前提下，因為無法快速求得 phi 函數，所以也無法求得對應的私鑰 b。總結來說，攻擊者的唯一手段在質因數分解而求得 P, Q，但這個問題以目前數學界的發展來說認為是困難的。
__2. Diffie–Hellman key exchange：

__3. ELGamel Encryption：( Image from link left )

由於明文 A、對應的暗文 A'、明文 B、對應的暗文 B'，在這個算法中滿足 A' * B' = ( A * B )'，因此可以利用 ( A * B * 1 )' = A' * B' * 1' 來進行「再暗號」。在適當的時機使用有防追蹤的效果。
缺點：公開鍵演算法一般處理時間較長，因此企業間的大資料運輸仍以對稱加密為普遍; 如果實現方法不當，仍有「鎖」在一開始被調包的風險
補充：
__1. 電子簽名：公開鍵可以實現電子簽名，具體方法是將文件 T，以自己的私鑰 a 進行加密，將對應的公鑰 b 和 T^a 和希望簽名的文件 T 都交給檢測方檢查 ( T^a )^b 是否等於 T。但若只是如此，攻擊者可以產生一個隨意的文件 F，並宣稱所簽的文件為 G = F^b，雖然無法任意構造文件 F 的長相，卻已算成功竄改資料並騙過檢測方。這個問題很好解決，稱為 RSA-FDH 為了使攻擊者無法任意產生文件 F，考慮先將希望簽名的文件 T 進行 hash 後，將 hash 函數、T、hash( T )^a、b 都交給檢測方。如此一來，根據 hash 函數的理想單方向性，無法在不知道 a 的前提下構造任意一個 F 使得 ( hash( F )^a )^b = hash( F )。

其他：
1. 考慮一個很可能發生的情況，攻擊者在一次事件後知道暗文 A' 對應的明文為 A，在往後傳輸 A' 時便失去完善保密性。有一個很容易防止的方式，增加另一個變數。常用的方法有兩種：一種是每次傳輸時產生一個亂數 x，將 x 加入加密函數的參數中，便能使得同一個明文 A 產生不同的暗文 A'，而因為攻擊者始終沒有鑰匙，這個亂數 x 對攻擊者而言沒有意義，可以直接公開地交給接收者。另一種方法是雙方事先設定一個同步的計時器，每一次傳輸後改變計時器的值，而該值加入加密函數的參數中。
2. 考慮分享網路，要能限定分享的對象，以及有效率的增減分享對象。顯然開多個網路，每個都進行不同的加密，並將不同的密碼交給各位做管理則成本很大。因此考慮對每個人編號。假設有 N 個人，編號範圍 [ 1, N ] 且皆相異邊號，並產生大小為 N 的亂數數列 A，讓所有人都拿到自己編號以外對應的 A 值。此時，若要讓某些編號的人不能使用網路，就將他們的編號收集起來，做 XOR{ A[ x ], for each id = x is not welcomed }。但這個方法無法防止密碼共用的可能。這次考慮將三十分鐘定為一個時段，六十分鐘為一週期，並開兩條網路，兩個網路的前一個時段和後一個時段的密碼皆相異。假設有四個人，那麼，顯然有四種分配方式，而我們只給想給的人密碼，並使之皆相異。此時如果存在相同一組的密碼，就能鎖定共有密碼的犯人。注意到只要使一個週期的時段增加一個，就能增倍分配方式。缺點在於，仍然無法防止三人以上合夥的情形。
3. 考慮透過網路互動進行猜拳。如果先出，對方就可以直接應對，產生不公平問題。因此考慮先出，在向對方保證無法改變已出的拳式的前提下，等待對方出拳後，再讓對方知道自己所出的拳式。這個可以透過公開鍵實現。利用事先公開的公開鍵對拳式加密後，再用私鑰解密秀出拳式。我可以理解構造的困難性，但對相同的暗文的第二個私鑰對應的第二個拳式的不可能性保持懷疑。
4. 秘密分散：考慮一個鑰匙，公平的分給若干個人，使得每個人都無法直接得到鑰匙。簡單地實現方法為多項式的應用，假設為一元 k 次多項式，那麼令鑰匙為常數項，並尋找線上 k + 1 個座標分給 k + 1 個人。
5. 假設甲乙兩人分別有數字 X 和 Y。希望雙方能在不能知道對方的數字，且第三者不介入的前提下進行數字的大小關係比較。令 ( f, N ) 和 g 分別為乙的 RSA 公鑰和私鑰，並讓乙決定一個 R 為某個亂數不小於 Y。甲接著隨機取一個數字 t，並把 Z = t^f * A mod N 交給乙。乙接著公開一個 hash 函數，並交給甲所有 hash( Z / i ), for each 1 ≤ i ≤ B，以及 R - B 個亂數。假如果發現 hash( A ) 存在於乙交給他的數字裡，那麼極高機率 ( 也就是除非混肴 B 的大小所用的亂數恰好產生碰撞 ) 滿足 A ≤ B，否則一定 A > B。此為零知識對話證明的一種，若擔心碰撞的可能，可以重複做幾次直到該機率必須被忽視。另外，能不能防止甲或乙不老實回答的問題呢？
6. Steganography

參考資料：
1. 暗号攻撃法

______________________________________________