维吉尼亚加密法提出了自动金钥系统

1密碼學與網路安全第2章古典加密技術2對稱式加密SymmetricEncryption也稱為傳統加密、私密金鑰加密或單金鑰加密傳送端(加密)和接收端(解密)共用相同的金鑰所有古典加密演算法都是私密金鑰是1970年代公開金鑰加密發展出來之前的唯一加密方式而且是最常用的加密方式3基本術語明文plaintext－原始可理解的訊息或資料密文ciphertext－是由加密演算法根據明文和秘密金鑰所產生的輸出結果，內容是雜亂無章的訊息密碼cipher加密法encipher(encrypt)－將明文轉換成密文的演算法解密法decipher(decrypt)－將密文還原成明文的演算法金鑰key－用在加密演算法的資訊，而且只有傳送端和接收端知道密碼學cryptography－研究加密原則、方法的學科密碼解析cryptanalysis(codebreaking)－研究不需金鑰而能解密的學科密碼技術cryptology－研究密碼學和密碼解析的學科4對稱式加密模型5必要條件若要安全使用傳統加密法，有兩個必要的條件：強固的加密演算法只有傳送端與接收端能得知秘密金鑰以數學公式表示：Y=EK(X)X=DK(Y)我們不需要保護演算法，但我們需要保管好金鑰6密碼學Cryptography密碼學系統可以根據三種不同的觀點來描述：將明文轉為密文所用的運作方式替代／置換／重複的替代與置換substitution/transposition/product金鑰的使用數量單金鑰或私密金鑰／雙金鑰或公開金鑰處理明文的方式區塊加密／串流加密block/stream7密碼解析目的是還原金鑰，而非只還原訊息一般的方法：密碼解析攻擊cryptanalyticattack暴力破解法brute-forceattack8密碼解析攻擊僅知密文只知道演算法和密文(得知道明文是exe檔、或英文…)已知明文除密文外，尚有一或多組明文/密文組選定明文選取明文使用加密器獲得密文選定密文選取密文用解密器獲得明文選定內文選取明文或密文來加密或解密9密碼解析攻擊絕對安全unconditionalsecurity不論攻擊者取得多少密文，如果他無法從其中的資訊解出相對應的明文，我們就說這個加密機制是絕對安全。也就是說，不論攻擊者花多少時間都不可能破解密文，因為解開密文所需的資訊不在其中計算安全性computationalsecurity破解加密法所需的成本超過加密訊息本身的價值，或者破解加密法所需的時間超過訊息的有效壽命，加密法就視為計算安全性10暴力破解嘗試所有可能的金鑰平均來說，必須嘗試的金鑰數量，大約是可能的金鑰總數的一半下表列出不同的金鑰數量所需要的時間金鑰長度（位元）可能的金鑰總數每微秒加密一次所需的時間每微秒加密l06次所需的時間32232=4.3109231µs=35.8秒2.15毫秒56256=7.21016255µs=1142年10.01小時1282128=3.410382127µs=5.41024年5.41018年1682168=3.710502167µs=5.91036年5.91030年26字元（任意排列）26!=4102621026µs=6.41012年6.4106年11替代加密法以其它的字元或符號來替代將明文裡的字元如果將明文視為連續的字元，那麼替代就是將明文的字元樣式換成密文的字元樣式12凱撒加密法CaesarCipher目前所知道最早且最簡單的替代加密法羅馬的凱撒將軍（JuliusCaesar）所發明將每個字母用其後的第三個字母來替代例如:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB13凱撒加密法字元的順序可繞回頭：abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC為每個字母指定一個數值：abcdefghijklmnopqrstuvwxyz012345678910111213141516171819202122232425便能以下列方式表示這個演算法，也就是每個明文字元p會換成密文字元C：c=E(p)=(p+k)mod(26)p=D(c)=(c–k)mod(26)14凱撒加密法的密碼解析只有26種可能的加密方式對映至從A到Z的如果知道密文是由凱撒加密法產生，暴力法便很容易破解，因為：已知加密/解密演算法只要一一測試這26種對映方式已知明文所用的語言例如破解密文：GCUAVQDTGCM15單套字母加密法MonoalphabeticCipher不只字母移位，也任意排列字母每個明文字母對映到不同的隨機密文字母因此金鑰長達26個字母Plain：abcdefghijklmnopqrstuvwxyzcipher：DKVQFIBJWPESCXHTMYAUOLRGZN明文：ifwewishtoreplaceletters密文：WIRFRWAJUHYFTSDVFSFUUFYA16單套字母加密法的安全性總共有26!種可能的金鑰，也就是4x1026金鑰數量龐大，應該就很安全但是，錯！問題是在語言的特性17字元相對出現頻率不是所有字元的出現頻率都相同英文裡的字母E是最常用的字母，其次是T、R、N、I、O、A、S其他如Z、J、K、Q、X的使用頻率並不高各種語言皆有常用字、詞的頻率統計，有助於密碼解析18字元相對出現頻率19單套字母加密法的密碼解析重要概念–單套字母替代加密不會改變字元出現的頻率補救措施是讓一個字元有好幾種替代方式，亦即同音字如果按照字元出現頻率來決定其密文符號的多寡，就能完全消除單一字元的頻率資訊20密碼解析範例要破解的密文是：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ首先找出字元的相對出現頻率，並比較標準的英文字母頻率分佈推測密文裡的P和Z是e和t推測密文裡的ZW是th，因此ZWP是the繼續反覆試驗，最後可得：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow21普雷費爾Playfair加密法普雷費爾是最知名的多字元加密法這個方法將雙字元的明文視為單一元素，再將其轉成雙字元的密文這是由英國科學家惠斯頓CharlesWheatstone爵士於1854年發明，但是他以其朋友BaronPlayfair命名22普雷費爾金鑰矩陣普雷費爾演算法使用由關鍵字組成的5×5字元矩陣矩陣的建構方式1.先將關鍵字字元由左至右、由上至下填入矩陣，並刪除重複字元2.將26個字母剩餘的字元依序填入，而且將I跟J視為同一個字元例如以MONARCHY當作關鍵字MONARCHYBDEFGI/JKLPQSTUVWXZ23普雷費爾加密法的加密與解密一次針對明文的兩個字元來加密：1.若是相同字元的雙字元，就插入填充字元，例如x2.如果這兩個字元位於矩陣同一列，就把第一個字元當成最後一個字元的右邊字元（繞回頭），並用它們右邊的字元來替代它們eg.“arencryptsasRM3.如果這兩個字元位於矩陣同一行，就把第一個字元當成是最後一個字元的下方字元（繞回頭），並且用它們下方的字元來替代它們4.否則(即兩字不同行又不同列)，則每個字元都換成與它自己同一列、但與另一個字元同一行的字元eg.“hsencryptstoBP,and“eatoIMorJM24普雷費爾加密法的安全性安全性優於單套字母加密法因為有26個字母，但雙字元有26×26=676種組合，因此不易辨識雙字元再者，單一字元的相對出現頻率變化範圍比雙字元大很多，也讓雙字元頻率分析變得更加困難有很長一段時間此法廣被使用例如此法是英國陸軍一次世界大戰的標準系統，且直到二次世界大戰，美國陸軍與某些聯軍仍廣泛使用雖然普雷費爾加密法具備了相當程度的安全性，但還是很容易破解。因為它原封不動的留下很多明文語言的結構。基本上要破解普雷費爾加密法，只要幾百個密文字元就夠了25多套字母加密法PolyalphabeticCiphers改進單套字母加密，以多套字母加密替代而提高安全性以一組相關的單套字母作為替代的規則以金鑰決定在轉換時要使用哪種替代規則26維吉尼亞加密法VigenèreCipher最簡單的多套字母替代加密法以位移量0到25的26個凱撒加密法來組成相關的多套字母加密的替代規則維吉尼亞表(表2.3)有助於瞭解及使用這種方法28維吉尼亞加密法範例加密需要與訊息一樣長的金鑰金鑰通常是某個重複的關鍵字例如關鍵字是deceptive的以下加密範例：金鑰：deceptivedeceptivedeceptive明文：wearediscoveredsaveyourself密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ29維吉尼亞加密的安全性維吉尼亞加密法的強度在於一個明文字元可以對應到好幾個密文字元每個密文字元是由關鍵字裡的字母決定，因此能隱藏字元出現的頻率資訊維吉尼亞加密法並沒有隱藏所有的明文結構雖然優於普雷費爾加密法，但還是殘存著相當程度的頻率資訊30維吉尼亞加密的破解之道若使用單套字母加密法，密文的字元統計資訊會與明文趨於一致若懷疑使用的是維吉尼亞加密法，破解的過程會由如何求出關鍵字長度而定關鍵字長度：若兩個相同順序(sequence序列)的明文字串距離，剛好是關鍵字長度的整數倍，就會產生相同的密文字串破解這個加密法的重點在於，如果關鍵字長度是N，這個加密法實際上就是由N個單套字母加密法所組成31自動金鑰系統長度與訊息相同的關鍵字能消除關鍵字會定期出現的特性維吉尼亞加密法提出了自動金鑰系統這個系統會將明文接在關鍵字之後而形成金鑰例如關鍵字deceptive的範例：金鑰：deceptivewearediscoveredsav明文：wearediscoveredsaveyourself密文：ZICVTWQNGKZEIIGASXSTSLVVWLA但還是會因為金鑰與明文的字元頻率分佈相同，而能以統計的技巧破解32單次金鑰加密法One-TimePad使用與訊息等長的隨機金鑰，能不需重覆使用金鑰而達到相當程度的安全且這把金鑰用在加密、解密單一訊息之後，就丟棄不用因此每個新的訊息都需要與訊息等長的新金鑰此法所產生的隨機密文與原始明文並無統計的關聯性單次金鑰加密法的密文並無明文的任何訊息，因此無從破解問題：key的產生和安全的發送與保護33置換加密法TranspositionCiphers目前所提，都是將明文符號換成另一個密文符號另一種完全不同的對映方式，是以某種形式重新排列明文字元這種技巧稱為置換加密法34柵欄加密法RailFencecipher最簡單的置換加密方法將明文排成一連串的對角線形式，然後再一列一列讀出例如：明文：meetmeafterthetogaparty密文：mematrhtgpryetefeteoaat單純的置換加密方式很容易被識破因為密文和原始明文的字元頻率分佈都相同35列置換加密法RowTranspositionCiphers比較複雜的方法是將訊息一列一列排成矩形，再一行一行讀出來但還要交換行與行之間的順序「行的順序」就變成這個演算法的金鑰例如：金鑰：3421567明文：attackpostponeduntiltwoamxyz密文：TTNAAPTMTSUOAODWCOIXKNLYPETZ36回轉機RotorMachines回轉機是現代加密法出現之前，最常見的複雜加密方式