# 密碼學基礎 ## 目的 密碼，在傳遞訊息中扮演重要的角色，如何能夠安全的傳遞訊息且不被破解。密碼的目的在於加密明文，以密文方式傳遞到接收端，且能夠被接收端解密，得到明文。從以前的古羅馬時期發展的凱薩密碼，到替換式密碼，到了現代的對稱加密、非對稱加密以及串流加密...，都為了發展更加安全的通訊方式付出了相當大的貢獻。 ## 基本概念 * 明文:欲傳達之訊息，不論是文字、圖片還是影片... * 密文:加密後之訊息 * 金鑰:為解開密文而附上的解密訊息 * 解密:解密方必須知道密鑰及解密方法，經由解密後，才能得出正常的可閱讀訊息 * 加密演算法:通常演算法可分為:對稱加密和非對稱加密。 對稱加密: 加、解密時使用同樣的金鑰。 非對稱加密: 加、解密時使用不同的金鑰 ## 密碼技術 * 單向雜湊函數: 注意安全性的的軟體發布時，會一併提供該軟體的**雜湊值**，以免被惡意的竄改，此雜湊值即由**單向雜湊函數**計算，即可確保訊息的**完整性**而非機密性。 * 訊息認證碼: 如果要確認訊息是否來自正確的對象，可以使訊息驗證碼的技術來認證。 * 數位簽章: 可以防止假冒、竄改或者是**否認**等威脅技術，就稱作數位簽章。類似於現實生活中的印章或簽名，是相當重要的技術。 * 虛擬亂數產生器: 是一種產生虛擬亂數的演算法。亂數擔任**產生金鑰**的重要工作。 # 古典密碼學 古典密碼學，最經典的取代加密，將明文經過換字表或者移位方式加密後成為密文，最後一樣透過一樣得方式解密出明文，概念十分簡單，但是卻有許多種變形。 ## 凱薩加密 凱薩密碼，是一種最簡單又廣為人知的加密演算法。明文中所有的字母都在字母表上向後(或向前)按照一定數目進行偏移後就可以產生出密文。當偏移量是左移6的時候（解密時的密鑰就是6）： | 原文 | a | b | c | d | e | f | g | h | i | j | |: :|: :|: :|: :|: :|: :|: :|: :|: :| | | | 使用加密金鑰+6後 | g | h | i | j | k | l | m | n | o | p | 使用時，加密者只需要查找每個字母所在的位置，再依循著加密表反向操作，即可還原出密文。 ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int key; string s; while(true){ cout<<"Enter the Messenge: "; cin>>s; cout<<"Enter the KEY:"; cin>>key; for(int i=0;i<s[i];i++){ s[i] += key; } cout<<"The cyphertext is :"<<s<<endl<<endl; } } ``` ## 維吉尼亞密碼 維吉尼亞密碼是基於凱薩加密，他把凱薩加密所有位移建表，  必須有明文與密鑰，密鑰長度必須小於等於明文長度 若密鑰小於密文長度，則將密鑰重複至等於明文長 然後一一對應，若用數學表示即為以下。 加密：將明文和金鑰之對應字母表上的數字進行相加減後同餘 $C_i\equiv P_i+K_i mod\ 26$ 解密：將密文和金鑰相減加後同餘 $P_i\equiv C_i-K_imod\ 26$ Message = VigenereCipher ExtenedKey= codecodecodeco ## 仿射密碼 仿射密碼是一種替換密碼， 乘上某個數再模運算 $E(x)=(ax+b)mod \ m$ (a,m互質) $D(x)= a^{-1} (x-b)mod \ m$ ## 換位加密 先將欲加密之訊息進行如下排列，之後再依照金鑰左右排列3後，便可依欲輸出之 方法進行輸出，本範例所使用的為簡易的行換位法。 換位加密範例: zoe have a pen and a apple | 1 | 2 | 3 | 4 | 5 | | | | | | | | z | a | p | n | p | | o | v | e | d | p | | e | e | n | a | l | | h | a | a | a | e | 進行加密之金鑰：１３２５４ 加密後排序如下表： | 1 | 3 | 2 | 5 | 4 | | | | | | | | z | p | a | p | n | | o | e | v | p | d | | e | n | e | l | a | | h | a | a | e | a | 接著使用橫排輸出即可得到密文 * 密文：zpapn oevpd enele haaea * 金鑰：１３２５４ ## 多圖替換(Playfair cipher) * 生成表: 選取一個字串為密鑰，將重複的字元去除，逐個加入5X5的矩陣，在將剩下的字母加入矩陣(會缺一個，所以可以把不常用的去除例如:Q，或者把I,J視為一樣) * 加密 : 將明文切成兩個兩個一組，每組的明文以m1,m2表示，密文以c1,c2表示，套用以下規則即可生成密文 * 規則: 1. 兩個字元在同列不同行，密文各為字元右邊的字元(若字元在最右即取最左的) 2. 兩個字元在同行不同列，密文各為字元下邊的字元(若字元在最下即取最上的) 3. 兩個字元不同行不同列，密文為這兩個字元圍成矩形的頂點(第一個密文和第一個明文同列) 4. 兩個字元在同行又同列(m1=m2)，密文會將其分成兩組，並分別在後方加上一個X充當空字元加密 取*CYSHSCIENCEONE*為密鑰，對應矩陣為下列 >C Y S H I >E N O A B >D F G K L >M P Q R T >U V W X Z 將*FIGHTFORGSAT* 拆成 >FI GH TF OR GS AT 對應後產生的密碼為 >LY KS PL AQ QO BR ## 卡爾達諾漏格法密碼    # 對稱式密碼 ## 加密演算法 ### 加密原則 * confusion混淆 混淆，是讓密文跟密鑰間的關係模糊，目的是讓監聽者即使獲得密文也無法推測出密鑰。使用非線性的替換會有不錯的混淆效果。 * diffusion擴散 擴散，就是讓明文盡量被多個加密操作影響，目的是為了要隱藏明文的統計性。最理想是讓密文的每一位都受到明文中的每一位的影響。 ### DES #### 何謂DES 1976年被 `美國聯邦政府的國家標準局`確定為`聯邦資料處理標準`（FIPS），隨後在國際上廣泛流傳開來。它基於使用56位金鑰的對稱演算法。 這個演算法因為包含一些機密設計元素，相對短的金鑰長度以及懷疑內含美國國家安全局（NSA）的後門而在開始時有爭議，DES因此受到了強烈的學院派式的審查，並以此推動了現代的塊密碼及其密碼分析的發展。 #### 加密方式 <!--**費斯妥結構**  **費斯妥函數f**  --> * 每一次加密64位元的資料，用56位元的金鑰。 * 經過16回合的加密，並且每一個回合用56位元產生出48位元的子金鑰對64位元資料加密 一回合的加密流程: 1. 一回合的輸入分成**左**、**右**兩部分 2. 右半部直接輸出為**右** 3. 將右帶入回合函數$f$ 4. 回合函數$f$使用右及子金鑰計算出隨機的位元串 5. 將得到的位元串與左進行XOR運算後，得到的結果成為加密後的左 ### AES #### 何謂AES? 進階加密標準（英語：Advanced Encryption Standard，縮寫：AES），在密碼學中又稱Rijndael加密法，是美國聯邦政府採用的一種區塊加密標準。這個標準用來替代原先的DES，已經被多方分析且廣為全世界所使用。 ### Rijndael加密 * 運用SPN框架 1. SubBytes - Rijmdael輸入區塊是128位元(16位元組)，把一位元組的值當作索引，從擁有256個數值得S盒中獲得一個值。 2. ShiftRows - 以4個位元組，為單位劃分的列往左而右位移的混和處理。 3. MixColumns - 對4位元組的值進行位元運算，在轉換為另一個4位元組 4. AddRoundKey - 最後再將MixColumns的輸出與此回合的金鑰作XOR運算。 5. 重複1 ~ 4步驟，並做10~14次 ## 區塊加密模式 ### ECB模式 * 全名: Electric CodeBook * 方式: 將明文區塊加密，直接變成密文區塊 * 優點: 簡單、快速、可以進行同步處理 * 缺點: 容易遭受重送攻擊、重覆部分容易辨識   ### CBC模式 * 全名: Cipher Block Chaining * 方式: 把前面一個密碼與明文區塊進行XOR運算再加密 * 優點: 相同明文，會因為前一個的密文不同造就出不同的密文 * 缺點: 一個密文錯誤會導致兩個明文解析錯誤   ### CFB模式 * 全名: Cipher FeedBack * 方式: 類似 CBC，但前一個密文的結果只影響一部分的加密關係，然後將前一段密文狀態加密金鑰，再對明文加密。 * 優點: 可以解密任意密文區塊、支援自動同步 * 缺點: 位元錯誤過多的情況下，不宜使用   ### OFB模式 * 全名: Output-FeedBack * 方式: 類似於 CFB，將前一段的加密金鑰拿回來加密，不依賴接收的密文狀態。 * 優點: 只需要加密器，加密做兩次相當於解密、位元錯誤下支持的能力好 * 缺點: 如果翻轉密文區塊的位元，明文區塊將出現位元反轉   ### CTR模式 * 全名: CounTeR * 方式: 類似於OFB，直接利用計數器作為加密金鑰。 * 優點: 可以進行同步處理 * 缺點: 如果翻轉密文區塊的位元，明文區塊將出現位元反轉   # 公開金鑰密碼系統 公開金鑰密碼系統，分成兩個金鑰，一把負責加密，一把負責解密，兩把成對。 收件者只需要解密金鑰，寄件者只需要加密金鑰。 只要保管好解密金鑰，即使加密金鑰被竊聽也沒關係，就要講到金鑰配送。 ## 金鑰配送 假設寄件者Alice收件者Bob竊聽者Eve密文$x$，Alice要把$x$安全的傳給Bob，Eve會想辦法竊聽。 1. Bob製作使用工具製作出一對鑰匙，加密鑰匙$c$和解密鑰匙$d$，且保管好解密鑰匙。 2. Bob將$c$用任何方式傳送給B，Alice和Eve都得到$c$。 3. Alice使用$c$將x加密，並且傳送給Bob，Eve竊聽到也無法解密。 4. Bob收到加密後的用$d$解密得到$x$ ## RSA ### 產生公私鑰 1. 隨機選擇兩個足夠大質數$p,q,p!=q，N=pq$ 2. 使用歐拉函數$r=\varphi(n)=\varphi(p)\varphi(q)=(p-1)(q-1)$ 3. 選擇一個比$r$小的整數$e$，且$r$跟$e$互質。 4. 求$e$對$r$的逆模元，$ed\equiv 1(mod N)$，為$d$。 公鑰為$(N,e)$,私鑰為$(N,d)$。 ### 加密 RSA的加密方式使用模運算產生密文$c$，他要傳送的訊息為$m$。 首先要將$m$轉換成比$N$小的非負整數$n$。 $c=n^e(mod N)$ 這時候就可以把$c$傳送給B了 ### 解密 B得到c之後就可以用以下方式將密文解密 $n\equiv c^d(mod N)$ RSA程式碼演示(C++) ```cpp= #include<iostream> #include<math.h> #include<string.h> #include<stdlib.h> using namespace std; long int p, q, n, t, flag, e[100], d[100], temp[100], j, m[100], en[100], i; char msg[100]; int prime(long int); void ce(); long int cd(long int); void encrypt(); void decrypt(); // 判斷是否為質數 int prime(long int pr) { int i; j = sqrt(pr); for (i = 2; i <= j; i++) { if (pr % i == 0) return 0; } return 1; } int main() { cout << "\nEnter First PRIME Number: "; cin >> p; flag = prime(p); if (flag == 0) { cout << "\nWrong Input\n"; exit(1); } cout << "\nEnter ANOTHER PRIME Number:"; cin >> q; flag = prime(q); if (flag == 0 || p == q) { cout << "\nWrong Input\n"; exit(1); } cout << "\nEnter Message\n"; fflush(stdin); cin >> msg; for (i = 0; msg[i] != NULL; i++) m[i] = msg[i]; n = p * q; t = (p - 1) * (q - 1); ce(); cout << "\nPossible value of e and d are\n"; for (i = 0; i < j - 1; i++) cout << e[i] << "\t" << d[i] << "\n"; encrypt(); decrypt(); return 0; } //判斷 void ce() { int k = 0; for (i = 2; i < t; i++) { if (t % i == 0) continue; flag = prime(i); if (flag == 1 && i != p && i != q) { e[k] = i; flag = cd(e[k]); if (flag > 0) d[k++] = flag; if (k == 99) break; } } } long int cd(long int x) { long int k = 1; while (true){ k = k + t; if (k % x == 0) return (k/x); } } //加密，設第一組密碼為金鑰 void encrypt() { long int pt, ct, key = e[0], k, len; i = 0; len = strlen(msg); while (i != len) { pt = m[i]; pt = pt - 96; k = 1; for (j = 0; j < key; j++) { k = k * pt; k = k % n; } temp[i] = k; ct = k + 96; en[i] = ct; i++; } en[i] = -1; cout << "\nThe ENCRYPTED Message is\n"; for (i = 0; en[i] != -1; i++) printf("%c", en[i]); } // 解密，設第一組密碼為金鑰 void decrypt() { long int pt, ct, key = d[0], k; i = 0; while (en[i] != -1) { ct = temp[i]; k = 1; for (j = 0; j < key; j++) { k = k * ct; k = k % n; } pt = k + 96; m[i] = pt; i++; } m[i] = -1; cout << "\nThe DECRYPTED Message is\n"; for (i = 0; m[i] != -1; i++) printf("%c", m[i]); } ``` ## 對RSA攻擊 只要質數夠小或者挑得不好 可以直接用線上的質數庫分解或者使用秀爾演算法暴力拆質數 再用上面的公式帶入就可以直接得到密文。 ### 暴力解 只要N足夠小就可以直接暴力破解。 可以直接透過線上質數庫或者秀爾演算法，暴力拆解質數就可以解開。 ### 中間人攻擊 在Alice跟Bob要公開金鑰的時候，Mallory就開始竊聽了， 他知道有這個訊息，當Bob傳送公開金鑰Mallory就攔截，並把它的公開金鑰存下來， 接著把自己的公開金鑰傳送給Alice， Alice就用Mallory的公開金鑰加密訊息後再傳送給Bob，Mallory攔截訊息解開訊息後，再用Bob的公開金鑰加密傳回去給Bob，也可以在這中間修改訊息 ## ElGamal ### 產生公開金鑰 1. Alice 利用1生成元$g$產生一個$q$階循環群$G$的有效描述。($G$必須滿足一定的安全性質) 2. Alice 從${1,2,...,q-1}$中隨機選一個數$x$ 3. Alice 計算$h:=g^x$ 4. Alice 公開$h$以及$G,q,g$的描述，作為期公鑰，並保留$x$作為私鑰。 ### 加密 使用Alice的公鑰$(G,q,g,h)$向加密一條訊息$m$: 1. Bob 從{1,....,q-1)挑選隨機一數$y$，然後計算$c1:=g^y$ 2. Bob 計算出共享秘密$s:=h^y$ 3. Bob 把他要發算的秘密訊息$m$映射為$G$上的一個元素$m'$ 4. Bob 計算$c2:=m'*s$ 5. Bob 將密文$(c1,c2)$發送給Alice ### 解密 1. Alice計算出共享秘密$s:=c1^x$ 2. 計算$m':=c2*s^{-1}$，並將其映射回明文$m$，就可以得到原文 ## ECC ### 簡介 在相同的安全強度下，ECC的密碼學金鑰長度可遠較其他，公開金鑰密碼系統(如RSA)小且處理速度較快，意即ECC 每個金鑰位元所能提供的安全性遠超過其他公開金鑰密碼系統，這使得ECC非常適合利用於如智慧卡或手機無線行動裝置等記憶體有限的環境中 ### 橢圓曲線(質數體) 一般來說，橢圓曲線可以用下列方程式表示，a,b,c,d為係數 $E:y^2=ax^3+bx^2+cx+d$（$a≠0，ax^3+bx^2+cx+d=0$沒有重根） 下圖為$E:y^2=x^3-2x+4$:  #### 加法 過曲線上的兩點P、Q畫一條直線，找到直線與橢圓曲線的交點 -R 交點關於x軸對稱位置的點，定義為P Q，即為加法。如下圖所示：PQ = R  #### 乘法定義(兩倍運算) 上述方法無法解釋P P，即兩點重合的情況。因此在這種情況下，將橢圓曲線在 P 點的切線，與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為P P，即2P，即為二倍運算  #### 無窮遠點 如果將A與-A相加，過A與-A的直線平行於y軸，可以認為直線與橢圓曲線相交於無窮遠點。  ### 有限域 (伽羅瓦域)和離散對數 橢圓曲線是連續的，容易被推算，因此，並不適合用於加密； 所以，我們必須把橢圓曲線變成離散的點 把橢圓曲線定義在有限域上，這時就會用到以質數為模的整數域 GF( p ) 有限域GF( p )指給定某個質數p，由0、1、2……p-1共p個元素組成的整數集合中定義的加減乘除運算。 假設，橢圓曲線為$y^2=x^3+x+1$，其在GF(23)的有限域上，寫作: $y^2 ≡ x^3+x+1(mod 23)$ 此時，橢圓曲現已不再是連續曲線，是分散的各個點，如: (0,1)、(0,22)、(1,7)、(1,16)... ### ECC的運作 設定一個有限域Fp，曲線在E^23^(1,1)有一點P， 如果橢圓曲線上的P點存在一個正整數n使得$nP=O∞$，則將n稱作P的階 若n不存在，則P是無限階  選定n後即可 計算出可得27P = -P 所以P的階為28 這些點促成了一個循環，稱作為循環阿貝爾群，其中生成原為P，階數為29 從中挑選一個基點，開始計算，考慮K=kG，其中K、G為橢圓曲線Fp(a,b)上的一點，k為小於n的整數。 則給定k和G，根據加法法則，計算K很容易。 但反過來，給定K和G，求k就非常困難，其中k、K分別為私鑰、公鑰。 ## PGP PGP使用非對稱加密 每個使用者都有一對公鑰和私鑰 把資料用公鑰加密過後，只能用相對的私鑰解密 用私鑰加密後，可以用公鑰解密驗證 但是在PGP的加密，他是使用一把對稱的鑰匙加密資料，再用非對稱加密加密鑰匙 解密使先用私鑰解開對稱金鑰，再用金鑰解開資料  # 單向雜湊函數 ## 何謂單向雜湊函數? 單向湊雜函數是當輸入一個字串或是一個檔案時，在經過單向雜湊後，便會形成一行短碼，但從檔案轉成湊雜後的碼很簡單，從湊雜碼分析原始檔案卻是幾乎不可能發生的，也是因此造就了其不可逆性。 ### 運作 **欲加密之明文A → 使用雜湊函數 → 得出雜湊碼B** 其運作方式如下: **(1)** 雜湊函數必須對任意長度的訊息輸入，產生固定長度的雜湊值輸出。 **(2)** 如果給予雜湊值 A，在計算上是無法找出原訊息 B，使其符合 A =hash(B)，此特性稱之為『單向雜湊』 **(3)** A檔案之雜湊值並不會與其他檔案雜湊值相等，若相等那兩者皆必為相等 ### 目的 約略10-20年前，單向雜湊函數是用來確保加密資料是否有被修改過的確定方法。從網路上下載檔案時，大多網站皆會附上一雜湊碼，下載後，便能透過其網站提供函數之相似性進而推出檔案是否有遭到竄改。此函數之優點便是若有稍做修改，雜湊出的函數便會與原函數相差甚遠 * 如加密訊息為**1234** 得到的函數便是 **ff0eb2864feb22354747f8c85d42ccb5** * 但若將訊息修改為**1235**後 函數便會變成 **9996535e07258a7bbfd8b132435c5962** ## 應用 * 訊息認證碼 * 數位簽章 * 虛擬 * 產生器 * 動態密碼 --> ## 具體範例 ### MD5 MD5為輸入不定長度之文字或數字等，以128-bits的演算法進行輸出，輸出位數為32位元的十六進位碼。 ### SHA-1 對於長度小於2^64位的消息，SHA-1會產生一個160位的訊息摘要。當接收到訊息時，這個訊息摘要可以驗證是否有被竄改。 #### SHA-1 不安全 SHA-1已被Google的團隊找到碰撞的例子。  ### SHA-256，SHA-384 以及 SHA-512 為SHA變體，這三個函式訊息對應到更長的訊息摘要。以它們的摘要長度（以位元計算）皆為加在原名來作命名來提高安全性。 ### 暴力攻擊法 當欲破解此檔案或是更動此檔案時，必須要尋找與此檔案同樣之密碼，因此須製造一意義相似的檔案，並嘗試謀和，找到相同加密碼的檔案並交換，因此，必須對原始數據進行搜索，直到找到答案為止 ### 生日攻擊法 因兩個不同的原函數值在進行加密的時候，可能會得出相同之加密值，因此，生日攻擊法的可能性就產生了。在加密過後，若加密值共有N個，只要$1.2\sqrt{2}$便有**50%** 的機率可以碰撞。 ### 兩者差異 暴力攻擊法和生日攻擊法的差異便是**弱碰撞性**及**強碰撞性**，暴力攻擊法因為從原始數據發出搜尋，因此可能性是無限大，所以要找到正確的加密碼根本是大海撈針，但是生日攻擊法只要確認加密碼的值域，便可以確認值域進行搜索，得到加密碼。 # 訊息認證碼(MAC) ## 何謂訊息認證碼? 在密碼學中，訊息鑑別碼，是經過特定演算法後產生的一小段資訊，檢查某段訊息的完整性，以及作身分驗證。它可以用來檢查在訊息傳遞過程中，其內容是否被更改過，不管更改的原因是來自意外或是蓄意攻擊。同時可以作為訊息來源的身分驗證，確認訊息的來源。 ## 使用方式 1. 寄件者Alice與收件者Bob要先共用一把金鑰 2. Alice根據匯款通知計算MAC值(使用共用金鑰) 3. Alice傳送匯款通知及MAC值給Bob 4. Bob把計算出來的MAC值與Alice銀行寄來的MAC值做比對 ## 運用 ### SWIFT SWIFT是Society for Worldwide Interbank Financial Telecommunication(環球銀行金融電信協)的簡稱，是一個國際合作組織，營運著世界級的金融報文網路，銀行和其他金融機構通過該組織提供的安全、標準化的和可信的通道與同業交換報文，從而完成金融交易。 ### IPsec IPsec是在網際網路的通訊協定IP(Internet Protocol)中，加上安全性功能。IPsec為了進行通訊內容的完整性，而使用了訊息認證碼。 ### SSL/TLS SSL/TLS是我們在網站上進行線上購物時，使用的通訊協定。SSL/TLS一樣使用了訊息驗證馬來進行通訊內容 ## 建立訊息驗證碼 ### 單向雜湊建立HMAC 1. 填補金鑰 1. 金鑰比單向雜湊函數區塊短: 補0 2. 過長: 將金鑰進行雜湊把該雜湊值當作HMAC的金鑰 2. 填補後的金鑰與ipad進行XOR運算 ipad是指，重複00110110位元串(十六進位是36)，直到與區塊長度相同 經過XOR的值成為依附金鑰的位元串。 3. 將依附金鑰的訊息串加到訊息開頭 4. 將3.的結果輸入雜湊函數取取得雜湊值 5. 填補後的金鑰與opad進行XOR運算 opad是指，重複00110110位元串(十六進位是5c)，直到與區塊長度相同 經過XOR的值成為依附金鑰的位元串，暫稱opadkey。 6. opadkey與雜湊值結合 7. 將6.結果再度輸入雜湊函數，計算MAC值 ### 區塊加密法建立 把區塊加密法的金鑰當作訊息認證碼的共同金鑰來使用，並利用CBC模式讓整個訊息加密。需先固定初始化向量(IV)。由於不需要解密，所以只留下最終區塊，其他都捨棄不用。最終區塊就是MAC值，因為CBC模式的最終區塊會受到整個訊息及金鑰影響，所以能當作訊息認證碼。 ## 重送攻擊 假設Alice 想向Bob證明自己的身分。 Bob 要求她的密碼作為身分證明，愛麗絲應盡全力提供（可能是在經過諸如雜湊函式的轉換之後）； 與此同時，Eve竊聽了對話並保留了密碼（或雜湊）。交換結束後，Eve連接到Bob。當被要求提供身分證明時，Eve傳送從Bob接受的最後一個對談中讀取的Alice的密碼（或雜湊），從而授予Eve存取權限。 # 數位簽章 ## 簡介 數位簽章是公開鑰匙系統，傳送具備**完整性**及**不可否認性**。 功能與訊息驗證碼的功能相似，數位簽章應用在『陌生環境』之下與『陌生人』之間的通訊，除了期望能表明自己的身份之外，並且可以保證所攜帶的訊息確實是自己所傳送的。 ## 產生 ### RSA 利用 RSA 公開鑰匙系統製作出來的數位簽章機制，就稱為『RSA 數位簽章』 #### RSA 簽章演算法  * 傳送訊息：$M$ * 雜湊演算法：$H$ * 加密演算法：$E_K[M]=M^dmod \ n$ * 解密演算法：$D_K[C] = C^e^ mod n * 傳送端計算雜湊碼：H(M) * 數位簽章：Sig(M) = $E_{K_R}[H(M)]=(H(M))^dmod\ n$ * 接收訊息：M’ * 接收端計算雜湊碼：H(M’) * 驗證簽章：Ver(Sig(M)) = D~KU~[E~KR~[H(M)]] = (Sig(M))^e^ mod n = H(M) * 若H(M)與H(M')的值相同代表驗證成功，反之即是 #### 安全性 數位簽章的安全性考量，與訊息確認碼（MAC）一樣，必須考慮到破解鑰匙的暴力攻擊法、以及偽造訊息的生日攻擊法。對於數位簽章有一個更重要的特點，它的訊息主要以**明文方式**傳送，而且簽署後的簽章碼（Sig(M)）必須保持一段長時間的使用（一般都是一年）；在這一段時間內，破解者可以利用已知的明文來測試各種可能發生的鑰匙（暴力攻擊法），並比對現有的簽章碼。 #### 防範 * 執行數位簽章與文件加密的鑰匙，不可以使用同一對公鑰與私鑰配對。 * 執行數位簽章時，必須針對文件的雜湊值加密，而不可以直接對文件明文加密。 * 不可以對亂數做數位簽章。 * 不同鑰匙配對之間不可以有相同的模數（n）。 * 必須將明文填補（亂數或 0）到與模數（n）相同長度之後，再執行數位簽章。 ## 產生 ### DSS 『數位簽章標準』（Digital Signature Standard, DSS）是美國 NIST（National Institute Standard and Technique）於1994 年所制定的數位簽章標準，此標準制定了『數位簽章演算法』（Digital Signature Algorithm, DSA） #### DSA 演算法  #### DSA 安全性考量 DSA 演算法是 ElGamal[59] 編碼系統的修正版，因為 ElGamal 是採用極複雜之離散對數的計算方法，時至今日尚未發現較有效的方法，因此唯有仰賴老方法：暴力攻擊法與生日攻擊法。 # 數位憑證 『數位憑證』就是讓個人（或組織單位）在網路的虛擬環境下，可以表示個人身分的依據。當個人需要在網路上進行任何交易，只需秀出個人的數位憑證，足以表明自己的身份；至於此數位憑證是真是假？如警察人員一樣，可向有關單位詢問是否有發出此數位憑證 ## 數位憑證種類 * 憑證授權(CA)中心憑證 雖然 CA 中心負責發行憑證給使用者，但 CA 中心也需要另一個較高權威單位授權給它，足以表示其信用度 * 伺服器憑證 伺服器需要向CA中心申請憑證，以確定自己真正的身份。目前網路上，從事於電子商務的伺服器，大多需要申請 SSL 數位憑證，以確定伺服器本身的名稱及公鑰。 * 個人憑證 由自然人或法人向 CA 中心所申請的憑證，這種憑證大多祇能使用於某一特殊用途，並無法廣泛使用。 ## 憑證儲存 * 隨身碟： 其功能大都與磁碟片相同，只是具有更大的儲存空間。目前電腦大多配備有 USB 介面，不需特殊軟體，便可以讀取隨身碟上的資料，雖然方便但他的安全性是可慮的。 * IC 卡： 卡片上的 IC（Integrated Circuit）可包含著 CPU及相關記憶體單元。基本上，IC 卡就具有簡單電腦系統的功能，不但有獨立的處理單元、作業系統（COS）、輸入/輸出介面，它與讀取設備（讀卡機）之間可從於較嚴謹的通訊協定，來管理並認證對方身份的工作，因此他的安全性可以說是最高的，也是目前最普遍採用的儲存元件。 # 金鑰 ## 何謂金鑰? 金鑰，是一種訊息，這個訊息可以用來加密解密訊息。 在密碼學演算法中，加密與解密的金鑰可以一樣也可以不一樣，取決於你的演算法不同。 ## 管理金鑰 要管理金鑰，就等於各種操作。 * 生成密鑰 * 更新密鑰 * 保存密鑰 * 作廢密鑰 * 配送密鑰 ## Diffie-Hellman金鑰交換 上面講到的配送密鑰，就要講到一種安全協定-**Diffie-Hellman金鑰交換(D-H)**。 ### 如何實現 Alice想要傳送訊息給Bob且Eve想要竊聽 1. Alice和Bob互相約定好質數$p$和原根$g$，並公開出去所以Eve知道了。 2. Alice挑選一個整數$a$ 3. Alice計算出$A=g^a mod p$並公開出去給Bob，Eve也知道 4. Bob也挑一個數字$b$ 5. Bob計算出$B=g^b mod p$並公開給Alice，Eve也知道 6. Alice計算出$s=B^a mod p$ 7. Bob也計算出$s=A^b mod p$ ### 安全性 只要數字選擇合適，這個協定是安全的。 因為如果Eve順利竊聽到的話，他要破解，可能需要進行求解$g^{ab}$，但又因為目前沒有足夠快的離散對數演算法，故這個協定被認為是安全的 # 亂數 ## 什麼是亂數 亂數是指在一個範圍內提供一個，具有隨機性(平均分布、獨立性)和不可預測性的數。 ## 應用 亂數是資安中很重要的一項工具 * 產生鑰匙：傳送方選一個亂數當鑰匙，再加密傳給對方。 * 演算法：有些演算法需要亂數來增加神秘性。(ex:RSA、Diffie-Hellman) * 計算器：某些通訊協定（ex:IPSec）會擇一亂數計數器做為序號，用來辨識防禦重複攻擊。 * 確認：如雙方需要確認持有的鑰匙是否相同時，一方會選用一個亂數加密後，傳送給對方。對方解密後，再將亂數加密，加密後回傳給發送者。 ## 特性 - 統計學偽隨機性:看起來很亂，而且取樣極大的時候，分布是平均的。但產生的過程有規則，因此只要取得夠多樣本，就有機會推算下一個亂數為何。 - 密碼學安全偽隨機性:當有一部分的樣本與演算法時，依然無法推測下一個亂數為何。 - 真隨機性，隨機樣本無法重現，是完全不可預測的亂數。 ## 生成亂數方法 ### 線性同餘法 同餘可以產生**偽隨機數**的方法。 因為它可以透過輸出演算得知所以他是偽隨機數生成器。 * 周期為$M$ * $B,M$互質 * $M$的所有質因數都可以整除$A-1$ * 如果$M$是4的倍數$A-1$也要是 * $A,B,N~0~$都比$M$小 * $A,B$必須要是正整數 $N_{j+1}\equiv(A*N_j+B)mod M$ ### DES 亂數產生 利用線性同餘法產生亂數後，再加密(ex:DES or AES)，處理出來再將原來亂數的格式再打亂一次 雙方都使用同樣的演算法，那就可以產生同樣的演算結果，也可以用這個方法來驗證。  ### ANSI 亂數產生 * 輸入參數：使用兩個輸入參數。一者為隨時變動的日期與時間，並以 64 位元來表示。第二次以後的計算，也會製造另一個亂數種子（Seed），做為下一次計算的初始值； * 加密鑰匙：本演算法係採用 Triple-DES 加密法，鑰匙長度為 112（=56 × 2）。此鑰匙確保安全，只能使用於虛擬亂數產生上。 * 亂數輸出：亂數輸出也是 64 個位元；另外輸出一個 64 位元的種子（Seed），作為下一次計算虛擬亂數的參數。  ### PRNG PRNG 是偽亂數產生器，又稱為確定性隨機比特生成器(DRBG) 是一種生成序列的方法，雖然要產生接近真隨機數續列的可以使用TRNG完成 符合統計學偽隨機性 他不是真隨機亂數，因為序列的產生取決於初始值 但是透過嚴謹的數學分析可以使他接近真亂數序列 但基於速度跟可再現的特性，所以實踐上也是很重要的 M19937 mmersenne twister ### 線性遞歸的生成器 PRNG的標準演算法由線性同餘法(LCG)構成 雖然說LCG的算法不夠好是確定的 但是也沒有更好的算法 #### 可能產生的問題 * 較弱的初始值 * 序列分布不均 * 連續值 #### 應用 * 模擬 * 遊戲的過程生成 * 密碼學 ### CSPRNG CSPRNG 是密碼學安全偽亂數生成器 承接了上面的PRNG，為了適合用在密碼學加密 符合統計學偽隨機性、密碼學安全偽隨機性 CSPRNG用來搭建其他更複雜的密碼學應用(Ex:CSPRNG和XOR建構出串流加密的方法) 抑或是以下的PHP的隨機數函式就是使用CSPRNG ```php= random_bytes() random_int() ``` ### TRNG 一種通過物理方式產生亂數的方法 符合統計學偽隨機性、密碼學安全偽隨機性、真隨機性 這樣的裝置通常是基於一些能隨機的**噪聲**訊號的微觀現象，(ex:熱力學噪聲、光電效應和量子現象) 這些物理過程理論是完全不可預測的，並且已經得到了實驗的證實。 硬體亂數生成器通常由換能器、放大器和類比數位轉換器組成。 其中換能器用來將物理過程中的某些效果轉換為電訊號，放大器及其電路用來將隨機擾動的振幅放大 而類比數位轉換器則用來將輸出變成數字，通常是二進位的零和一。 通過重複採樣這些隨機的訊號，一系列的亂數得以生成。 ### 量子亂數產生 我們可以用量子的機率性來產生隨機亂數 假設我們要產生範圍0~7之間的亂數 代表我們需要三個位元的隨機數 所以我們每次將一個qubit丟進去H-gate然後去測量 可以產生50%-50%的1或0 做三次就可以產生0~7之間的亂數 # SSL/TLS SSL/TLS是世界上最常用的秘密通訊方法。透過網頁伺服器被廣泛使用，一般而言，在網路上傳遞訊息時，總會需要將自己的訊息進行加密，以防止訊息遭人竄改或是洩漏，因此在用戶與用戶之間的訊息，就必須用SSL及TLS來做加密，其原理如下。 1. Alice和Bob在有SSL/TLS的保密網站(https://)下進行傳訊 2. 兩方用戶的訊息在從此網站傳訊的期間，執行HTTP，進而達到加密的效果 但在傳訊的時候，同時也需要確認對方用戶的訊息是否真的由對方用戶所傳出，因此在加密訊息的後面，還會加上用戶的憑證 ## SSL/TLS密碼技術漏洞以及攻擊 ### SSL3.0降級漏洞與POODLE攻擊 在SSL3.0的CBC模式之下進行加密，可以修改資料而不用驗證，導致攻擊者可以隨意竄改內文。POODLE攻擊就是在此模式進行攔截資料，進而得到許多安全性資料。而攻擊者甚至還有可能將TLS強制轉換成SSL3.0模式，再套用上方的方式進行攻擊。 ### SSL只保護了傳遞中的資訊 若是用戶在傳遞訊息的前後，在編譯訊息過程中遭人看見，那SSL/TLS便無法保證此訊息是否會被竄改與否，因為SSL/TLS只能確保傳遞過程中的訊息不被盜用。 # 密碼學應用 ## 比特幣 ## 拜占庭將軍問題 簡單來說，拜占庭帝國正在打仗這個帝國擁有需多軍隊，一些將軍都帶領著各自的軍隊 在這裡決策只有進攻與撤退兩種做法，為了贏得戰爭，必須使所有軍隊一起進攻一起撤退，則投票時採用過半數的決策 假設有七支軍隊， 其中有一位將軍是叛徒(簡稱C)， 有三位將軍決定進攻(簡稱A)， 有三位將軍決定撤退(簡稱B)， 這下行動的關鍵票就落在這位叛徒C的手中， C就跟A說我決定進攻，卻也跟B說我要撤退 所以A會進攻B會撤退，那麼這場戰爭必輸 把這個問題轉換到資訊領域上 假設所有電腦分布在世界各地上，稱為分布式結點 如果有少數電腦產生故障、藏有駭客，如何保持一致性與正確性 所以我們只要保證多數的電腦都可以做出一致與正確的決定就可以了 **將軍副官模型** 在這裡忠誠跟叛徒是兩件事 有可能忠誠但是他是叛徒 - 忠誠的副官 忠誠的副官遵守將軍的指令一起進攻一起撤退 這就保持了一致性 - 忠誠的將軍 那麼所有忠誠的副官都會執行這個指令 這裡提出了一個小結論 m:惡意的個數，n:所有的個數 當**n>3m**的時候，這個問題有解， 因為所有人都會互相交換、驗證。 ### 何謂比特幣? 比特幣是一個全球通用貨幣，且不再由特定人群或是專業網站來管理，而是全體公民皆可使用，為"去中心化"性質，比特幣目前已成為較為知名的加密貨幣。 ### P2P網路 P2P網路英文全名是Peer to Peer，跟傳統的Client-Server不同的是 傳統的方法是所有用戶端都跟伺服器拿資料， P2P是用戶端跟用戶端提取資料，這樣就可以避免伺服器掛掉導致無法連線 雖然我們可以說「比特幣是一種貨幣」，其實，「比特幣是在P2P網路上進行交易的系統」  #### 優點 * 減少server負擔:這樣主server可以把上傳的工作分給其他Client * 分享檔案快速:下載一個檔案是把很多檔案切分成好幾份，同時從很多台電腦存取 #### 缺點 * 安全性:當你下載檔案的時候你是Client也是Server所以你的Port是開的，容易被攻擊。 * 容易癱瘓網路:如果再學校網路或者內網使用P2P很可能會癱瘓掉學校的網路 #### 實現方式 交易的本質就是**A給B一塊錢，B少了一塊，A多了一塊** 所以比特幣就是在每次交易的時候向所有人公開這個消息， 收到這個消息就把它記錄下來 等於是一個大家都擁有的超大帳本 只要大多數人的帳本都一樣這筆就成立 所以如何安全的驗證這些資料就需要**區塊鏈技術** ### 區塊鏈 區塊鏈是用密碼學串接來保護文字紀錄 每個區塊分成head和body **head存以下資料:** - 版本號 - 上一塊的哈希值 - 時間 - merkle root哈希值 - 難度 - 隨機數 把以上數據丟到SHA256**兩次**後就可以得出這塊的哈希值 **body存交易資料** #### 哈希值 比特幣的數學原理也是根本就是哈希 比特幣採用SHA256實現加密的關鍵 因為使用哈希，所以有不可竄改性，可以方便的檢視與驗證交易資料 修改頭會更改到哈希值 修改交易資料會修改到merkle root的哈希值 所以每個區塊只要修改了一些哈希值就會產生變化，且碰撞機率很小  區塊鏈由綠色塊開始，主鏈黑色，紫色是孤兒塊 之後會講這條鏈是怎麼決定他的走向的 #### 難度與目標值 我們可以把哈希值上的每一個位都看成隨機的 如果要找到第n位前都是0的哈希值機率是$1/16^n$ 所以0越多難度則越大 如果我要找開頭第一位0的數即要找一個比10000.....(16進64位)還小的數，這個數就是目標值(Target)，礦工的目標就是要找到比Target小的值 Target值透過函式決定，藉由全網算力將區塊運算時間控制在10分鐘左右 隨著速度的加快，所以系統每2016個區塊就會根據前2016個區塊所用的時間進行調整，獎勵也會隨著區塊減少，每21萬個獎勵就會減半 ### 挖礦原理 挖礦，是在虛擬貨幣中，透過提供算利來獲取虛擬貨幣回報的一種行為，本質上就是解一個足夠難的數學題，執行這個行為的稱為礦工。 上述提到難度與Tatget，還有一個隨機值(Nonce) 礦工的工作就是，將前面的東西保留，並且加上隨機值(從0開始)進行雙重哈希 當得到的哈希值比Target小的時候，該礦工就可以得到該塊的記帳權，且其他都正確，就可以把這個區塊加入主鍊，並獲得獎勵。 每個人前面的MerkleRoot是不同的，因為你提取獎勵必須自己加上去，所以包含自己的地址不同，所以MerkleRoot每個礦工都不同，隨機值也不同 所以算力越大搶到的概率越大。 ### 51%攻擊 有個問題: 如果每個人的同時找到了Nonce值，那麼會是誰搶到呢? 答案是: 分別開一條支鏈，所有礦工都可以選擇要接在哪一條上，越長的支鏈，就可以合併到主鍊中，另一條則被捨棄 這樣又有一個問題: 被捨棄的那條支鏈中的礦工不想放棄獎勵，怎麼辦? 答案是: 一直算下去直到他的支鏈超過另一條支鏈並成為主鍊 所以這就是51%攻擊 理論上，你只要擁有全網51%的算力，你就可以掌握主鍊的記帳權，那麼無論你是不是主鍊，你新開的支鍊也會成為主鍊，擁有全部的獎勵。 雖然在已經成熟的貨幣且足夠龐大的貨幣上是不可能發生的。 但在山寨幣或者還未成熟的貨幣具有相對低的保護區塊鍊的能力 就容易受到51%攻擊。 例如Monacoin，Bitcoin Gold和ZenCash就曾經受到51%攻擊 # 資源 https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html https://academy.binance.com/ https://www.youtube.com/watch?v=ZAn453E1H2g https://www.youtube.com/watch?v=bBC-nXj3Ng4 tg.pe/xBWe