電腦審計與安全期末報告 指導老師：徐立群教授 報告學生：陳淑娟、曾嬿蓉 Cryptography 電腦審計與安全期末報告 指導老師：徐立群教授 報告學生：陳淑娟、曾嬿蓉

報告大綱 導論 專有名詞解釋 密碼學的種類

導論 密碼學沿革 1900 B.C.:從埃及開始發展，埃及人使用非標準象形文字在泥土版雕刻，這是第一部將密碼學文書化 500B.C.:猶太人使用顛倒順序的字母替換加密法來寫聖經，稱為ATBASH 50B.C.:Julius Caesar使用簡單的替換法來加密 1412:Subhalasha共十四冊的阿拉伯百科全書裡介紹到替代和位置轉換加密法 1466:Leon Battista Alberti i因為他在多字母替換加密法的貢獻，被視為西方密碼學教父 1553:Giovanni Battista Porta介紹passpharss(密碼) as a key這個構想，這個多字母加密法也就是現代所稱的Vigene’re 1563:Giovanni Battista Porta 開始將加密法分成位置轉換法、替換法、記號替換法三類

導論（續） 1914~1917:在第一次世界大戰時，德國、英國和法國使用一系列的位置轉換法與替換法用來秘密通訊，也因此帶來了密碼學這門科學的誕生 1948:Claude Shannon 提議使用頻率與統計分析來破解替換加密法 1976:Whitefield Diffe and Martin Hellman介紹公開金鑰加密法的構想 1977:由Ronald Rivest, Adi Shamir, and Leonard Adleman這三人所發展出可行的公開金鑰加密法，RSA加密演算法因此誕生 1991:Phil Zimmermamn發表PGP( pretty Good Privacy) ，PGP是一個免費的軟體，後來成為全世界通用的公開加密系統 2000:Rijndael’s cipher被選為Advanced Encryption Standard

專有名詞解釋 密碼術(Cryptology) ：是一門包含關於密碼學(Cryptography)與密碼分析(或破密學)Cryptanalysis)領域的科學 密碼學(Cryptography) :是關於如何使訊息可以安全地被傳遞與接收的方法之相關知識，利用數學方法來對資料加密和解密的科學。密碼學讓你能夠儲存資訊，或透過並不安全的網路（例如網際網路）來傳遞訊息，而任何不該看到這個資訊的人都將無法讀取它。 密碼分析或破密學(Cryptanalysis) :相對於密碼學是保密資料的科學，密碼分析則是分析和破壞保密通訊的科學。古典密碼分析需要對分析推理、數學工具使用、板模尋找等興趣的結合，還需要耐心、決心、以及運氣。密碼分析家也被稱做攻擊客。

專有名詞解釋 密碼系統(Cryptosystems) :是利用人工或電腦來加密(encrypt)或使資料轉型，以便進行祕密傳輸與儲存，密碼系統亦用來將加密後的資料解密(decryption)或解碼；密碼系統有五大特性: 認證 (Authentication): 辨識身份 授權 (Authorization):存取控制Access Control,存 取權限Access Right 儲存與傳輸機密資料: 秘密通訊, 防止竊聽 存取密碼 (Password): 選擇好的密碼, 單次密碼系統 不可否認性 (Non-Repudiation): 證明資料來源 電子簽章 (Digital Signature) 完整性 (Integrity): 防止竄改 訊息文摘 (Message Digest

專有名詞解釋 Steganography:與密碼學有同樣的目的就是傳遞者可以秘密傳輸訊息給接收者；其與密碼學不同的地方在於它不使用數學演算法(algorithm)與金鑰(keys) ，其最終的目標是把訊息隱藏起來，使其他人不知道有此訊息的存在，其隱藏的方法包括使用看不見的連結、縮小、字母重新排列和選擇、數位簽章和浮水印。現代Steganographic 技術可以使訊息隱藏於電腦圖形和聲音檔案或將其訊息存放在不用的磁碟空間。例

Byte 1-red Byte 2-green Byte 3-blue Technical Details EX1. Aha!( 4*8=32 bits)隱藏在圖形中:改變一些像素 一個像素由紅、綠、藍共3*8=24位元組成 Aha! 隱藏後的結果 Byte 1-red Byte 2-green Byte 3-blue 01010110 01111011 00011110 01000001 01101000 01100001 00100001 Pixel Byte 1-red Byte 2-green Byte 3-blue 01010110 01111011 00011110 2 01010110 01111010 00011110 3 01010110 01111011 00011110 4 01010111 01111011 00011110 5 01010111 01111010 00011110 6 01010110 01111010 00011111 7 01010111 01111010 00011110 8 01010110 01111010 00011111 9 01010110 01111010 00011111 10 01010110 01111010 00011110 11 01010110 01111011 00011110

Technical Details EX2.浮水印 創作者先選定一具安全性的亂數產生器，並選擇一亂數作為亂數產生器的種子(seed)，將此種子帶入亂數產生器(pseudo random number generator)運算會得到一連串的亂數值（x, y, z），其中（x, y）代表所要藏入的像素座標位置，z是代表所要藏入在像素中的位置（由左至右為0、1、…、7），此外所選擇的種子必須保持妥善保存，不可洩漏。此外，若所計算出來的藏入座標點有重複的話，必須捨棄不用。 浮水印影像為一較小的影像，且為一黑白兩色的二元影像，故每個像素只需1 bits來表示即可。因此將浮水印影像的第一個像素藏到（x, y）座標像素的第z個位置中。 接下來要做失真補償，將此像素的z-1位置的bit改為1，z+1至最後位置的bit都改為0，然後計算此像素值p1並和將此像素z+1至最後位置的bit都改為1所得到的像素值p2做比較，若p與p1的誤差較p與p2的誤差要小，p則將替換為p1，否則將p替換為p2，其中p為原始的像素值。 重複步驟2、3，直至藏完所有浮水印影像為止。 當要驗證此作品確為其所創作，只需提出此亂數產生種子，透過亂數產生器產生一連串的亂數值（x, y, z）。 到所對應的像素和位元中取出浮水印的像素值，重組後若可回復一代表創作者的浮水印，則可證明此作品為此創作者所創作。

Technical Details EX2.浮水印 01234567 10101010 11101010 假設在影像中座標（4，7）的原始像素值為p=170（10101010）， 而浮水印第一個像素值為1，於是將原始像素值位置為1的bit由0改為1， 而藏入後的像素值為234 (11101010)。 接著計算p1＝192（11000000），p2＝127（01111111）， 我們可以發現p1與p的誤差較p2與p的誤差小， 我們變將位置（24、71）的像素值改為p1（192）。

Technical Details

專有名詞解釋 明文(Plaintext or cleartext):未曾被加密過的原始文件，使用者可以閱讀的文件 密文(Ciphertext):加密後所產生的無法讀解之加密文件，接受者必須利用解密演算法與金鑰解密成明文才能閱讀 加密演算法(Cipher or Cryptographic algorithm) :一個密碼演算法，或稱為密碼本，是一個用來處理加密和解密的數學函式。一個密碼演算法必須和一副金鑰(一個文字、數字、或詞組 ) 一起將明文加密。同樣的明文一旦使用了不同的金鑰，就會加密成不一樣的密文。加密過資料的安全完全依賴兩件事：密碼演算法的強度和金鑰的保密。 編碼(Code or Cord words)在加密之前，用一些替代性文字或其他字參雜在明文中。

專有名詞解釋 C v.s. k uryou are oic oh! I see i eye 密碼字母表(Cipher alphabet) :應用於替換(substitution)加密法上，為加密演算法中的每個字母、數字、記號提供交互查詢的功能。 異義同音字(Homophones) :在沒有改變明文內容意義的前提下，利用改變字母或字母重組來增加複雜度，例如 Null:通常是沒有什麼意義的，當我們不知道演算法與金鑰時，我們去除null來解碼，以增加解碼的複雜度 多字母系統(Polyalphabetic):比單一字母系統(monoalphabetic)還要安全 解碼(Decode or deciphered):接收者用正確的金鑰與已知的演算法解碼成明文 C v.s. k uryou are oic oh! I see i eye

專有名詞解釋 雜湊函數(Hash function):可以配對或轉化一組位元 為另一組位元（通常是較小的） 的單向演算法，使每 次均可得出該訊息的同一個雜湊函數，而且不可以經 由雜湊函數重整得出該訊息 。此外，兩個不同的訊 息不會得出相同的雜湊函數，用來確保訊息內容不會被改變。 對稱式加密法(Symmetric ciphers):以同一個key同時進行文件加密與解密的方法，也稱為秘密金鑰加密(private key encryption)或對稱加密(symmetric encryption)。 非對稱式加密法(Asymmetric ciphers):使用兩個 不同的keys分別用以加密和解密的加密法，但不能 根據用以加密的key計算出解密的key 。

密碼學的種類 多字母替換加密法(Polyalphabetic Substitution Ciphers) 位置轉換加密法(Transposition Ciphers) 雜湊函數(Hash Function) 加密演算法(Cyptographic Algorithms) 對稱式演算法(Symmetric or Private Key Cryptography) 非對稱式演算法(Asymmetric Cryptography or Public Key Cryptography) 混合式密碼系統(Hybrid Cryptosystems)

密碼學的種類 Caesar cipher 一個傳統密碼法的簡單例子是取代法密碼本。也就是透過取代法密碼本把一部份的資訊取代成另一些無意義的字串。這種方法常常透過把字母系統偏移數個字母加以施行。 密碼演算法就是「字母偏移」，而金鑰則是「字母偏移的距離」。 單一字母(monoalphabetic) v.s. 多字母替換法(polyalphabetic)

密碼學的種類 Caesar cipher 明文 A b c d e f g h I j k l m n o p q r s t u v w x y z 密文 Wd j n t r p v z u m e c y f s l g q x h a b I k o 明文: call home 密文: jwee vfct

Polyalphabetic Substitution Ciphers 增加解碼的複雜度與困難度 Enigma and Purple等著名的密碼系統在第二次世界大戰分別被德國和日本軍隊使用 Standard Vigenere Table Keyword: FORTUNEFORT(ROW) Plaintext: MEETMEATSIX(COLUMN)

Polyalphabetic Substitution Ciphers D E F G H I J K L M N O P Q R S T U V W X Y Z Polyalphabetic Substitution Ciphers 增加解碼的複雜度與困難度 Standard Vigenere Table Ciphertext: RSVMGREYGZQ

Transposition Ciphers 位置轉換加密法利用先前定義的演算法與金鑰將字母重組，使明文轉換成密文。 缺點:有心人士使用頻率分析(frequency analysis) 來解密 結果:現代人將polyalphabetic substitution and transposition混合使用 Plaintext: Call home Ciphertext:lacl eohm

Transposition Ciphers 單向雜湊函數(One Way Hash Functions) 雜湊演算法將任意長度的訊息對應到成固定長度的雜湊數值，產生訊息摘要(message digest)，以確認此訊息是沒有被更改的。 優點：不經由加密，只以雜湊函數來確認訊息的一致性與完整性 密碼認證系統(Password verification systems) 經由輸入的密碼對應到的雜湊值，來產生訊息摘要，此時系統會將此一新計算出來的雜湊值和先前儲存的雜湊值比對來確認使用者的身分。

Transposition Ciphers 訊息確認碼(MESSAGE AUTHENTICATION CODE，MAC):此類公開函數的輸入是一個訊息與一把秘密金鑰，而其輸出則是一個固定長度的確認器 使用秘密金鑰來產生固定大小的資料區段(MAC)，這段資料(MAC)會被加到訊息的後面一起傳給接收者 接收者會使用秘密金鑰來執行相同的運算來得到新的MAC，將此一新MAC與收到的MAC比對 MAC=Ck (M)

Cyptographic Algorithms-Symmetric or Private Key Cryptography 經由發送者透過某一種程序將明文亂序，此一程序稱之為金鑰；而接收者收到密文後，使用同一把金鑰解密還原明文， 稱之為對稱式密碼演算法，加解密速度快是其優點，其加密金鑰與解密金鑰為相同一把金鑰稱之。目前常見的演算法有RC2,DES,Triple-DES和AES等 亂數產生器PSEUDORANDOM NUMBER GENERATOR(PRNG):創作者先選定一具安全性的亂數產生器，並選擇一亂數作為亂數產生器的種子(seed)，將此種子帶入亂數產生器(pseudo random number generator)運算會得到一連串的亂數值 ，因此產生KEY，用來加密與解密。

Cyptographic Algorithms-Symmetric or Private Key Cryptography 對稱式區段加密法(Symmetric block chiphers) 將一小段明文視為整體，然後據此產生長度相同的密文區段，亦即針對n位元的明文區段來產生n位元的密文區段。基本上，一個區段的大小是8-16位元組 優點:安全性高 缺點:速度慢、可能會產生重複的密文 Electronic Code book( ECB) mode Cipher Block Chaining (CBC) mode Cipher feedback mode (CFB) and output feedback (OFB):使用修改過的XOR 函數 由於此明文區塊、金鑰值和先前明文內容產生的區塊之交互作用影響， 結果會使擁有相同區塊的明文有不同的加密方法而成為密文，使其安全性提高

Cyptographic Algorithms-Symmetric or Private Key Cryptography 對稱式區段加密法(Symmetric block chiphers) 可能的明文區段有2n種可用來加密，傳輸到接收方解密後只會產生一個版本的明文 EX. 可逆轉換 明文 密文 00 11 01 10 10 00 11 01 不可逆轉換 明文 密文 00 11 01 10 10 01 11 01 使解密後，產生不同版本的明文（2n!）

Cyptographic Algorithms-Symmetric or Private Key Cryptography 對稱式資料流加密法(Symmetric Stream Ciphers) 一次會加密數位資料的一個位元或位元組ex. Vigener加密法 故密文大小等於明文大小 其演算法會產生key stream(一連串的位元) 。為增加安全性，the keystream generation是獨立於明文與密文 A one-time pad cryptosystem:使用亂數產生器產生的位元再與明文混合，其產生的位元與明文結合的字串，使安全性提高 ex. Keystream 優點:速度快、不會產生重複的密文 缺點: 有心人士會分析位元隨機產生的頻率，將密文解密成為明文

Cyptographic Algorithms-Symmetric or Private Key Cryptography Table A-3 特性 區段 資料流 加密速度 較慢 較快 密碼行數 較少行數 較多行數 加密金鑰 可再使用 只能使用一次 相容性 有標準演算法：AES、DES、Triple DES、RC2、RC5、IDEA、Blowfish and Rijndael 沒有標準演算法：RC4

Cyptographic Algorithms-Asymmetric or Public Key Cryptography 最大特色是二把金鑰的概念，當加密使用其中一把金鑰，能解密就只有另一把方能解開。由於無法從其中一把金鑰逆推得只一把金鑰值， 故稱之為單向函數。 這個理論於1977年由Mr. Rivest, Shamir及Adleman三人所發表，主要是用以解決前面對稱式加密金鑰的傳遞問題。 公開金鑰密碼系統最大缺點即是其運算速度較慢，比對稱式密碼系統慢1000至1500倍，實務上，簽章時均以對該文件之”訊息摘要”(Message Digest) 加以簽章的方式來替代對整份文件簽章。常見的有DSA,RSA及目前最先進的ECC橢圓曲線密碼 。

Cyptographic Algorithms -Hybrid Crptosystems 結合了對稱式與非對稱式演算法的優點 速度快和安全性高 具有數位簽章的功能，即具有不可否認性的特性 先使用對稱式演算法將明文加密，再使用非對稱式公鑰將對稱式私鑰加密 接收者的私鑰-將session key解密，得到session key 接收者的公鑰-將session key加密 B A Session key-成為密文 Session key-解密成為明文 明文 明文 密文

Symmetric algorithms and Asymmetric Algorithms Table A-4 對稱式演算法 非對稱式演算法 DES、Triple DES、RC2、RC4、RC5、IDEA、Blowfish、Rijndael、AES RSA PGP

報告大綱： Popular Cryptographic Algorithms Protocols for Secure Communications Attacks on Cryptosystems

報告大綱： Popular Cryptographic Algorithms Data Encryption Standard (DES) Data Encryption Core Process Triple Data Encryption Standard (3DES) Advanced Encryption Standard (AES) RSA algorithm Public Key Infrastructure (PKI) Digital Signatures Digital Certificates Pretty Good Privacy (PGP)

Data Encryption Standard (DES) 最著名的保密密鑰或對稱密鑰加密演算法 DES (Data Encryption Standard)是根源於IBM’s Lucifer algorithm ，將key length128-bits修改成 56-bits，在70年代發展起來的 美國國家標準局於1973年和1974年向公眾發出了徵求加密算法的公告。加密算法要達到的以下四點： 提供高質量的數據保護，防止數據未經授權的洩露和未被察覺的修改 具有相當高的複雜性，使得破譯的開銷超過可能獲得的利益 密碼體制的安全性應該不依賴於算法的保密，其安全性僅以加密密鑰的保密為基礎實現 經濟，運行有效，並且適用於多種完全不同的應用。

Data Encryption Standard (DES) 於1976年11月被美國國家標準與技術中心(National Institute of Standards and Technology NIST)採納IBM公司設計的方案作為非機密數據的正式數據加密標準，DES隨後被美國國家標準局和美國國家標準協會(American National Standard Institute， ANSI) 承認。 現今，DES算法在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費站等領域被廣泛應用，以此來實現關鍵數據的保密，如信用卡持卡人的PIN的加密傳輸，IC卡與POS間的雙向認證、金融交易數據包的MAC校驗等，均用到DES算法。

Data Encryption Standard (DES) DES算法的入口參數有三個：Key、Data、Mode。 Key為8個字節共64位，是DES算法的工作密鑰； Data也為8個字節64位，是要被加密或被解密的數據； Mode為DES的工作方式，有兩種：加密或解密。 在通信網絡的兩端，雙方約定一致的Key，在通信的源點用Key對核心數據進行DES加密，然後以密碼形式在公共通信網（如電話網）中傳輸到通信網絡的終點，數據到達目的地後，用同樣的Key對密碼數據進行解密，便再現了明碼形式的核心數據。這樣，便保證了核心數據（如PIN、MAC等）在公共通信網中傳輸的安全性和可靠性。 通過定期在通信網絡的源端和目的端同時改用新的Key，便能更進一步提高數據的保密性

(DES) Enciphering computation 16次

IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 64 32 32 IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

(DES) cipher function 放大換位表 32 1 2 3 4 5 5 6 7 8 9 9 10 11 12 13 32 1 2 3 4 5 5 6 7 8 9 9 10 11 12 13 13 14 15 16 17 17 18 19 20 21 21 22 23 24 25 25 26 27 28 29 29 30 31 32 1 32 48 48 48 6 6 6 6 6 6 6 6 單純換位表 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 4 4 4 4 4 4 4 4 32 32

(DES) Key schedule calculation 去除parity bits(8、16、24…64），共8個基偶校驗位 64 56 Iteration Number Number of Left Shifts 循環左移位數 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1 PC-1選擇縮小換位表1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 56 28 28 48 56 PC-2選擇縮小換位表2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

Data Encryption Standard (DES) DES用軟體進行解碼需要用很長時間，而用硬體解碼速度非常快，但幸運的是當時大多數黑客並沒有足夠的設備製造出這種硬體設備。在1977年，人們估計要耗資兩千萬美元才能建成一個專門電腦用於DES的解密，而且需要12個小時的破解才能得到結果。所以，當時DES被認為是一種十分強壯的加密方法。 但是，當今的電腦速度越來越快了，製造一台這樣特殊的機器的花費已經降到了十萬美元左右，所以用它來保護十億美元的銀行間線纜時，就會仔細考慮了。另一個方面，如果只用它來保護一台伺服器，那DES還是一種好的辦法，因為駭客絕不會僅僅要入侵一個伺服器而花那多的錢破解DES密文。 By 1997 it was realized that a 56-bit key was insufficient to maintain an acceptable level of secure communications In 1998, using a specially designed computer, the Electronic frontier Founation broke DES in less than three days.

Alternative Modes of Using the DES. ECB (electronic code book) is a direct application of the DES algorithm to encrypt and decrypt data; CBC (cipher block chaining) is an enhanced mode of ECB which chains together blocks of cipher text; CFB (cipher feedback) uses previously generated cipher text as input to the DES to generate pseudorandom outputs which are combined with the plaintext to produce cipher, thereby chaining together the resulting cipher; OFB (output feedback) is identical to CFB except that the previous output of the DES is used as input in OFB while the previous cipher is used as input in CFB. OFB does not chain the cipher.

ECB electronic core book Mode Characteristic Advantage Disadvantage ECB electronic core book Message broken into independently encrypted blocks Useful when sending and encrypting a few blocks at a time Repetitions in plaintext can be reflected in cipher text CBC Cipher block chaining Message blocks linked during encryption More secure than ECB Initiation value must be known by both parties; errors can propagate through encryption CFB Cipher feedback Message treated as a stream of bits; result is fed back for the next encryption Very secure Errors can propagate through encryption; slower than ECB OFB Output feedback Message treated as a stream of bits; results of block cipher are added to message and then fed back for the next encryption Used when error feedback is problematic Less secure than CFB; sender and receiver must remain synchronized

3DES Triple DES encryption is the same as standard DES; however, it is repeated three times. Triple DES encryption can be employed using two or three keys, and a combination of encryption or decryption to obtain additional security. E[K1]E[K2]E[K1],E[K1]E[K2]E[K1],E[K1]D[K2]E[K1],E[K1]D[K2]E[K3] 3DES employs 48 rounds in its encryption computation, generating ciphers that are approximately stronger than standard DES while requiring only three times longer to process.

(AES) Rijndael 在AES ( Advanced Encryption Standard ) 的選拔中，逐步篩選出適合用來作為下一代加密演算法的標準。Rijndael在經過了一番時日的考驗之後，直至2000 Oct. 2，NIST宣布Rijndael脫穎而出為最佳AES。 2002 May 26,AES被商務部Secretary of Commerce核准為官方聯邦政府的標準。 網站： http://csrc.nist.gov/CryptoToolkit/aes/rijndael/ http://home.ecn.ab.ca/~jsavard/crypto/co040401.htm Rijndael是一個反覆運算的加密演算法，它允許可變動的資料區塊及金鑰的長度。資料區塊與金鑰長度的變動是各自獨立的。

RSA 西元1997，三位美國麻省理工學院學者李瓦士Rivest、夏米爾Shamir 、以及艾道曼Adleman率先公開RSA加密 演算法並取得專利權，目前有很多的數位消費性產品，例如視訊轉換器與智慧卡，都是利用了RSA加密來傳遞訊息，RSA就是分別取三位學者名字的開頭字母來命名的。 如果想和別人祕密通訊，你可以先選定兩個非常巨大的質數P1、P2作為私人鑰匙（(private key，解密用的），然後將 P1× P2 的乘積作為加密用的公開鑰匙 (public key)，鑰匙的長度約在 40 個位元到 1024 位元。你可以把公開鑰匙 (public key)公佈在名片上或在網路上。那麼，別人要傳一封密函給你，他必需要先得到你的公開鑰匙 (public key)，按照一個約定的方法將信件加密後送出。你在收到密函後，再用你的私人鑰匙(private key)就可以解出密函原文。 公鑰加密系統面臨的一項考驗就是它需要大量的處理資源，甚至Gigabit級的桌上型電腦亦無法有效解決。對於各種採用較慢處理器的嵌入式系統而言，問題就更為嚴重。

RSA Start Up: This need be done only once. Generate at random two prime numbers p and q of 100 digits or more. Calculate and Generate at random a number e < such that gcd (e, ) = 1. Calculate the multiplicative inverse, d, of e (mod ) using the Euclidean algorithm. Note: Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do – simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.

RSA 2. Publish: Make public the enciphering key, 3. Keep Secret: Conceal the deciphering key, 4. Enciphering: The enciphering transformation is, 5. Deciphering: The deciphering transformation is,

A simple example of RSA encryption Select primes p=11, q=3. = 11*3 = 33 = 10*2 = 20 Choose e=3 Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),and check gcd(e, q-1) = gcd(3, 2) = 1 therefore gcd(e, ) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1 Compute d such that e*d ≡ 1 (mod ) i.e. compute d = e^-1 mod = 3^-1 mod 20 i.e. find a value for d such that divides (ed-1) i.e. find d such that 20 divides 3d-1. Simple testing (d = 1, 2, ...) gives d = 7 Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.

A simple example of RSA encryption Public key = (n, e) = (33, 3) Private key = (n, d) = (33, 7). This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message m = 7, = 7^3 mod 33 = 343 mod 33 = 13. Hence the ciphertext C = 13. To check decryption we compute = 13^7 mod 33 = 7.

A simple example of RSA encryption Note : We don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that a = bc mod n = (b mod n)*(c mod n) mod n so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value. One way of calculating m' is as follows: = 13^7 mod 33 = 13^(3+3+1) mod 33 = 13^3*13^3*13 mod 33 = (13^3 mod 33)*(13^3 mod 33)*(13 mod 33) mod 33 = (2197 mod 33)*(2197 mod 33)*(13 mod 33) mod 33 = 19*19*13 mod 33 = 4693 mod 33 = 7

English Alphabet and Corresponding Numbers for Each Letter A=01;B=02;C=03;D=04;E=05;F=06;G=07;H=08;I=09;J=10;K=11;L=12;M=13;N=14;O=15;P=16;Q=17;R=18;S=19;T=20;U=21;V=22;W=23;X=24;Y=25;Z=26 Encryption & Decryption Plain Text value (Text)^E (Text)^EMOD N= Cipher T 20 8000 8000MOD33=14 Cipher (Cipher)^D (Cipher)^D MOD N=|Text| Plain Text 14 105413504 105413504MOD33=20

RSA The strength of this encryption algorithm relies on how difficult it is to factor P and Q from N. 為了檢測 RSA 技術的安全性，一家專門研究RSA 技術的公司 RSA Security 提出了 8 個巨大合成數讓數學家作質數分解。這些合成數都是由兩個巨大的質數相乘積，要分解它們並不一件簡易的事。 RSA-576總共有174位數。在2003年12月3日，一個德國機構成功的將RSA-576分解成並獲得RSA Security 所提供的獎金１００００美金。如果成功分解RSA-2048，就能得到RSA Security 所提供的獎金２０００００美金，所以多研習密碼學，或許這些獎金會落入你的口袋。 ｈttp://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

PKI Public Key Infrastructure is an integrated structure of software, encryption methodologies, protocols, legal agreements, and third-party services that enable users to securely communicate across the insecure Internet. Third-party services that enable users to securely communicate across the insecure Internet. Third-party suppliers integrate public key cryptography, digital certificates, and certification authority into an enterprise-wide solution to provide authenticates and secure communications between participants.

PKI PKI公鑰基礎設施是提供公鑰加密和數字簽名服務的系統或平臺 ，它由公開密鑰技術、數字證書、證書發放機構（CA）和關於公開密鑰的安全策略等基本成分共同組成的。是利用公鑰技術實現電子商務安全的一種體系，是一種基礎設施，網路通訊、網上交易是利用它來保證安全的。從某種意義上講，PKI包含了安全認證系統，即安全認證系統-CA/RA系統是PKI不可缺的組成部分。 A typical PKI solution protects the transmission and reception of secure information by integrating the following components: CA (Certificate authority) RA (registration authority) Certificate directories Management protocols Policies and procedures

CA (Certificate authority) CA issues, manages, authenticates, signs and revokes a digital certificate containing the user’s name, public key, and other identifying information. 所謂憑證機構（Certification Authority，CA）係指提供數位簽章製作及電子認證服務之機構。憑證機構必須依據電子簽章法之相關管理規定及標準，提供相關憑證服務：包括審驗憑證申請人身分、資格與屬性，發給申請人私密金鑰，並且簽發公開金鑰憑證，以供驗證其公開金鑰及私密金鑰之配對關係，證明身分及確保安全。簡單言之，憑證機構便是扮演網路環境中的「戶政事務所」角色，負責個人身分審核並發給身分證明。

RA (registration authority) RA operates under the trusted collaboration of the certificate authority and can be delegated day-to-day certification functions, such as verifying registration information about new registrants, generating end-user keys, revoking certificates, and validating that users possess a valid certificate. 使用者申請憑證前，須先經過嚴謹審核作業，有行使該憑證授權範圍內工作之權利，以確認憑證所表達之身份，CA才能簽發該憑證。然而就申請者申請憑證的用途方面，CA於查核身份上或因無查證能力；或因權責區分考量，會將身份登錄查核工作移轉至權責單位擔任，此即為Registration Authority﹙註冊管理中心﹚，例如：若憑證用途為商務交易，CA於身份查核上便無法得知使用者的信用狀況，因此可委任銀行擔任RA，申請者身份查核由RA負責，CA僅簽發憑證，進而達成CA與RA權責區分。 RA負責對申請者進行身份正確性查核與憑證用途範圍驗證，再交予CA簽署憑證。對於憑證持有人的憑證狀態改變時﹙例如：私密金鑰遺失、喪失資格、憑證效期展期等﹚，對憑證加以管理。合法的RA身份乃由CA查核。

others Certificate directories are central locations for certificate storage, providing a single access point for administration and distribution. Management protocols organize and manage the communications between CAs, RAs, and end users. Policies and procedures assist an organization in the application and management of certificates, formalization of the legal liabilities and limitations, and actual business practice use. Certificate revocation list (CRL) contains a signed time-stamped listing if all revoked certificates.

Digital Signatures Digital Signatures based on the Digital Signature Standard (DSS). The DSS approach uses a hash function to create a message digest, which is then input into the digital signature algorithm along with a random number to generate a digital signature. DSA, RSA, and ECDSA (Elliptic Curve Digital Signature Algorithm) are the three algorithm NIST has approved. 數位簽章可用來相較於您的親筆簽名。 它不像傳統的通訊方式，您的親筆簽名有可能會被竄改，數位簽章是無法偽造的。 那是因為該簽章是使用您獨有的私鑰所建立的，然後它可被您的收件人使用您的公鑰來做確認。 一個數位簽章也會標記一個文件的時間戳記； 基本上這代表您簽署該文件的時間也是該簽章的一部分。 所以當任何人試著要修改該文件時，數位簽章的驗證將會失敗。

Digital Signatures 數位簽章的作法是拿你的私鑰來進行加密，而非像加密資訊那樣使用別人的公鑰。如果這個資訊能夠被你的公鑰解密，那麼它顯然是出自你手中。

Digital Certificates Digital certificates are electronic documents issued by a reputable third party that certify the identity of a user and the proof of identification associated with the presentation of a public key. Digital certificates authenticate the company that provides the verification of the digital signature. 數位憑證是一筆具有類似實際憑證功能的資料。在數位憑證通常包括在一個人的公鑰當中以助於其他人能夠驗證這把金鑰是真的或有效的。通常數位憑證能夠阻止將某人的金鑰代換成另一個的不良意圖。 在憑證的時候，數位簽章的目的是要聲明這份憑證資訊已經被其他人或實體所驗證了。數位簽章並不能對整個憑證驗證其可信度；它只能擔保說，那些簽署的身份資訊確實是跟隨著或附著在那一把公鑰上。

Pretty Good Privacy (PGP) PGP （designed in 1990 by Phil Zimmermann）結合了傳統密碼法和公開金鑰密碼法的特色。是一種混合密碼系統。當使用者使用 PGP 來對純文字加密的時候， PGP 首先會壓縮這段純文字。資料壓縮能夠節省數據機傳輸時間和磁碟空間、強化密碼法的保密程度。大部分的密碼分析技術利用純文字理發現的板模來破解密碼本。壓縮可以減少純文字裡的板模，相對來說也就提高了對密碼分析的抵抗力。然後 PGP 會產生一個階段金鑰，以非常秘密而快速的傳統加密演算法來加密純文字，而產生出密文。當資料加密完成後，這把階段金鑰接著就會開始以收信者的公鑰被加密。這個被公鑰加密過的階段金鑰將會與密文一併交付給收信者。

Pretty Good Privacy (PGP) 解密的過程就是反向運作了。收信者的 PGP 會利用他的私鑰來還原那把暫時的階段金鑰，然後 PGP 再利用這把階段金鑰來將傳統加密過的密文解密。 兩種加密方法的結合匯聚了公開金鑰加密法的便利以及傳統加密法的迅速。傳統加密法大約比公鑰加密法要快上 1,000 倍；而公鑰加密法則解決了金鑰傳遞和資料傳輸的課題。雙管齊下，效率和金鑰傳遞兩者同時改善了，而且不會有任何安全上的犧牲。 The PGP security solution provides six services: authentication by digital signatures, message encryption, compression, e-mail compatibility, segmentation, and key management.

Conventional encryption PGP Routines Routine Algorithm Application Public key encryption RSA/SHA or DSS/SHA Digital signatures Conventional encryption 3DES,RSA, IDEA or CAST Message encryption File management ZIP Compression

authentication by digital signatures: SHA-1 is used to a hash a message into a 160-bit hash code encrypted with DSS or RSA with a sender’s private keyappended to the message The receiver uses the sender’s public key to decrypt and recover the hash code. Using the same encryption algorithm, the receiver then generates a new hash from the same message, which is the comparison of the two identical hash codes that authenticates the sender.

digital signatures of PGP 然後 PGP 使用這個摘要和私鑰以產生「簽章」。 PGP 把簽章和純文字一起傳遞。當收件者收到訊息後，就利用 PGP 重新計算摘要，然後驗證這個簽章。不論 PGP 有沒有對純文字加密，對純文字簽署都是很有用的。一旦採用了保密雜湊函式後，就沒有任何方法把某人的簽章從文件中截下、貼到另一份文件上，或改變任何被簽署過的訊息。任何在簽署過的文件上所動的細小手腳，都會導致數位簽章驗證的結果失敗。

message encryption: 3DES, IDEA, or CAST are all standard algorithms, may be used to encrypt the message contents with a unique, randomly generated 128-bit session key. The session key is encrypted by RSA, using the receiver’s public key, and then appended to the message. Compression: PGP uses the freeware ZIP algorithm to compress the message, after it has been digitally signed but before it is encrypted. Conclusion: Authentication and message encryption can be used together by first digitally signing the message with a sender’s private key, compressing the message with ZIP algorithm, encrypting the message with a unique session key, and then encrypting the session key with the intended recipient’s public key.

e-mail compatibility: Radix-64 conversion assures e-mial compatibility by maintaining the required 8-bit blocks of ASCII text. CRC (cyclic redundancy check) is attached to detect transmission errors. segmentation: With many Internet facilities imposing restrictions on maximum message size, PGP can automatically subdivide message into a manageable stream size. At the recipient end, PGP reassembles the segment’s blocks prior to decompression and decryption.

報告大綱 Protocols for Secure Communications S-HTTP and SSL Secure/Multipurpose Internet Mail Extension (S/MIME) Internet Protocol Security (IPSec)

SSL (Secure Sockets Layer) Nescape developed the SSL protocol, which uses public key encryption to secure the channel in Internet communication. SSL（Secure Socket Layer）一個由Netscape所發展出的TCP/IP加密方式，是全球電子銀行交易普遍採用、使用上較方便的加解密安全控管機制，可確保機密資料傳輸上的安全性 SSL provide two layers of protocol within the TCP framework: SSL Record Protocol: responsible for fragmentation, compression, encryption, and the attachment of a SSL header to the cleartext prior to transmission Standard HTTP: provide the internet communication services between client and host. the handshaking phase

S-HTTP (Secure Hypertext Transfer Protocol) S-HTTP is an extension of the Hypertext Transfer Protocol to provide for the encryption of individual messages between a client and server across the internet. SSL與S-HTTP的比較： SSL S-HTTP 主要功能是建立安全的連線 建立安全的資料傳送 在HTTP通訊協定階層上使用，也可用於Socket階層 只能用於HTTP通訊協定階層 具有保全所有使用Socket的Internet通訊協定的能力 不具有 包含了Client端與Server端間溝通加密演算、交換認證與加密金鑰資訊等訊息 S-HTTP可使瀏覽器與伺服器二者利用簽名、認證、與加密等方式來維護HTTP網路封包的安全 瀏覽器會將原來純文字HTTP使用的HTTP://URL形態，改為HTTPS://URL這種形態 目前已被SSL（Secure Socket Layer）所取代

Secure/Multipurpose internet mail extension (S/MIME) S/MIME is the second generation of enhancement to the internet e-mail format standard STMP/RFC 822. The MIME specification included five news message header fields, predefined content types, and conversion transfer encoding in order to resolve many of the problems with STMP like the inability to transmit executable files or binary object, and the limit to 7-bit ASCII. SMTP（Simple Mail Transfer Protocol）是網際網路上伺服器 之間互相交換信件時所用的通訊協定。SMTP尋找遞送郵件的路徑， 將信件送至指定位置。 MIME規格是定義電子郵件訊息該如何組織的一個業界標準格式，而S/MIME則是指安全多功能網際網路郵件延伸 (Secure/Multipurpose Internet Mail Extension) 的縮寫。這是網際網路上用來傳遞安全電子郵件的一個通訊協定標準。S/MIME標準與金鑰技術等建立網狀信任關係與層次認證機制， 建構端到端的安全電子郵件技術，保證郵件內容保密且不可否認 （Non-repudiation）。

Header Files Function MIME-version States conformity to RFCs 2045 and 2046 Content-ID Identifies MIME entities Content-type Describes data in the body object Content-description Text description of the body object Content-transfer-encoding Type of conversion used in message body Function Algorithm Hash code for digital signatures SHA-1 Digital signatures DSS Encryption session keys ElGamal (variant of Diffie-Hellman) Digital signatures and session keys RSA Message encryption 3DES, RC2

Internet protocol security (IPSec) IPSec is an open source protocol to secure communications across any IP-based network such as LANs, WANs, and the internet. The protocol is designed to protect data integrity, user confidentiality, and authenticity at the IP packet level. IP layer security is obtained by AH (application header) or an ESP (encapsulating security payload). 在TCP/IP通訊協定上IPSec是作業系統提供應用程式之間安全溝通的編碼加密服務，透過IPSec通訊協定,可確保你的資料具隱密性,完整性,可靠性,封包傳送時發生錯誤自動修正(anti-replay)等安全服務。

IPSec建立在以下連接方式： 1.提供(end-to-end)端點對端點編碼通訊方式,例:client-to-server,server-to-server和client-to-client等連接方式, 藉由以上通訊方式為兩端點建立安全通道,資料流通在安全通道上會加上一層加密功能,確保資料隱密性。 2.對於client-to-gateway端點對閘道,IPSec有提供的L2TP(Layer Two Tunneling Protocol) 壓縮編碼方式使得遠端存取資料能更安全。 3.對於gateway-to-gateway(閘道與閘道之間)的資料保密,也可透過L2TP/IPSec或純IPSec兩種編碼方式確保曝露在企業建立的私有廣域網路(WAN)及網際網路(Internet)資料流通的安全性。 IPSec不同於VPN(Virtual Private Network),IPSec是針對現有的IP通訊上加密編碼,而VPN在既有的連線上創造另一組虛擬IP作為溝通的通道且所使用的通訊協定也不同.提供功能更強大的資料保密通訊協定是IPSec主要扮演的角色.。

The authentication header protocol The authentication header protocol is designed to provide data integrity and authentication of IP packets. Next header: Identifies the next higher level protocol such as :TCP and ESP Payload length: Specifies the AH contents length Security parameters index: identifies the security association for this IP packet. Sequence number: Provides a monotonically increasing counter number for each packet sent Authentication data: A variable-length containing the ICV for this packet. Next header Payload length Reserved Security parameters index Sequence number Authentication data (variable length)

encapsulating security payload protocol The encapsulating security payload protocol provides confidentiality services for IP packets across insecure networks. ESP can also provide the authentication services of AH. Payload data: Contains the encrypted data of the IP packet Padding: Space for adding bytes if required by encryption algorithm Pad length: Specifies how much of the payload is padding Security parameters index Sequence number Payload data (variable length) Next header Payload length Reserved Authentication data (variable length)

Attacks on Cryptosystems Man in the middle (CH2) Correlation attacks Attempt to reduce statistical relationships concerning the structure of the key and the output of the cryptosystem. Dictionary attacks Require the attacker to use the target cryptosystem to encrypt every word in a given dictionary Timing attacks The attacker eavesdrops during a user’s session. Statistical analysis of the users’ typing patterns and interkeystroke timings can be used to discern sensitive session information.

部分資料資料來源集 國家標準與技術中心(The National Institute of Standards and Technology, NIST)，是美國商業部(Department of Commerce)的一個法定機構，也是美國國家標準機構(American National Standards Institute, ANSI)的一員。http://www.nist.gov/ NIST FOPS1801: http://www.itl.nist.gov/fipspubs/fip180-1.htm NIST http://www.itl.nist.gov/fipspubs/fip46-2.htm Rijndael (AES) http://fp.gladman.plus.com/cryptography_technology/rijndael/ Ronald L. Rivest http://theory.lcs.mit.edu/~rivest/ RSA Security co. http://www.rsasecurity.com/ PGP http://jedi.org/blog/archives/002592.html#p10

Thank you