古典密碼學(xué)介紹

古典密碼學(xué)介紹21世紀(jì)信息時(shí)代的大門已經(jīng)敞開，信息作為一種特殊的資源和財(cái)富，正引起人們的高度重視。同時(shí)研究如何隱密地傳遞信息的學(xué)科——密碼學(xué)也得到了良好的發(fā)展和改進(jìn)。在日常生活中，我們都或多或少的接觸或者使用過密碼。究竟何為古典密碼學(xué)呢？簡而言之，古典密碼學(xué)是密碼學(xué)發(fā)展的一個(gè)階段，是現(xiàn)代密碼學(xué)的淵源。它有著悠久的歷史。在計(jì)算機(jī)出現(xiàn)以前，密碼學(xué)之間的算法主要是通過字符間的替換和易位實(shí)現(xiàn)的，這些密碼體制則為古典密碼。因此，古典密碼大都比較簡單，可以通過手工或機(jī)械方式實(shí)現(xiàn)其加密、解密過程。古典密碼學(xué)一般有兩大基本方法。其一為代替密碼，即將明文中的字符替換為密文中的另一種字符，接收者只要對密文做反向替換就可以恢復(fù)出明文。代替的目的是制造混亂，使得確定消息和密鑰是怎樣轉(zhuǎn)換成密文的嘗試變得困難。具體的代替方案稱之為“密鑰”。如果26個(gè)英文字母仍用26個(gè)英文字母來代替的話，可能的密鑰有26！-1種。在使用代替密碼體制時(shí)，要求26個(gè)英文字母與模26的剩余類集合建立一一對應(yīng)關(guān)系（不區(qū)分大小寫）。當(dāng)K=3時(shí)，就是著名的Caesar密碼。代替密碼的實(shí)現(xiàn)方法分為單表代替密碼和多表代替密碼兩類。而單表代替密碼有兩種形式：1，使用密鑰的單表代替加密。這種密碼選用一個(gè)英文短語或字符串作為密鑰，去掉其中重復(fù)的字母得到一個(gè)無重復(fù)字母的字符串。，然后再將字母表中的其他字母依次寫與此字母串之后，就可構(gòu)造出一個(gè)字母代替表。這種單表代替泄露給破譯者的信息更少，而且密鑰可以隨時(shí)更改，增加了靈活性。2，仿射加密，其加密即為一個(gè)線性變換。值得一提的是，單表代替密碼的密鑰量很小，不能抵抗窮盡搜索攻擊。另外他沒有將明文字母出現(xiàn)的概率隱藏起來，很容易受到頻率分析的攻擊。因?yàn)槿绻艽a分析者知道明文的性質(zhì)，則分析者就能用該語言的規(guī)律進(jìn)行分析。相對于單表代替密碼而言，多表代替密碼將明文字符劃分為長度相同的消息單元，成為明文組，對字符快成組進(jìn)行代替，使用了多張字符代替表。同一個(gè)字符具有多種不同的密文，改變了單表代替密文的唯一性，從而使密碼分析更加困難。多字母代替的優(yōu)點(diǎn)是很容易將字母的自然頻度隱蔽或均勻化，從而有利于抗擊統(tǒng)計(jì)分析。其中比較典型的有Playfair密碼、Hill密碼和Vigenere密碼?？偠灾媸敲艽a學(xué)中有效的加密方法。但其仍然受到一定的破譯威脅,例如頻率分析（加密后保留了明文字母頻率特性）、重復(fù)結(jié)構(gòu)分析、考慮最可能出現(xiàn)的字母及單詞、明文已知并且易于識別等。另一種為置換密碼，又稱為易位密碼，即重新排列消息中的字母，以便打破密文的結(jié)構(gòu)特征，即它交換的不再是字符本身，而是字符被書寫的位置。它分為周期置換密碼和列置換密碼。周期置換密碼是講明文字符按一定長度n分組，把每組中的字符按1~n的一個(gè)置換重排位置次序來得到密文的一種加密方法。列置換的處理方法是：將明文按照一行寫在格紙上，然后再按列讀出結(jié)果。為了增加變換的復(fù)雜性，可以設(shè)定讀出列的不同次序（該次序即為算法的密鑰）。古典密碼體制分析常有三種方法。一為單表代換密碼分析。其中常用明文中各個(gè)字母出現(xiàn)的統(tǒng)計(jì)概率及字符出現(xiàn)頻率分類和字母組合概率進(jìn)行一定分析。二為多表代換密碼分析。其中主要應(yīng)用了卡西斯基測試法。該測試法的基本原理為：若用給定的K個(gè)密鑰表周期地對明文字母加密，則當(dāng)明文字母中有兩個(gè)相同的字母組在明文序列中間隔的字母數(shù)為K的整數(shù)倍時(shí)，這兩個(gè)明文字母組對應(yīng)的密文字母組必定相同。但反過來，若密文中出現(xiàn)兩個(gè)相同的字母組，他們所對應(yīng)的明文組不一定相同，但相同的可能性很大。如果我們將密文中相同的字母組找出來，并對其相同字母組綜合研究，找出它們的相同字母數(shù)的最大公因子，就有可能提取出有關(guān)密鑰字的長度K的信息。三為對Hill密碼的已知明文分析。其基本思想是：將d個(gè)連續(xù)的明文字母通過線性變換轉(zhuǎn)變?yōu)閐個(gè)密文字母，這種代替是有k個(gè)線性方程（變換矩陣）決定的，解密需要做逆變換即可，密鑰就是變換矩陣。Hill密碼能比較好的抵抗頻率法的分析，但不能抵抗已知明文攻擊。比較典型的古典密碼學(xué)有以下幾種：一是滾桶密碼。在古代為了確保他們的在古代為了確保他們的通信的機(jī)密，先是有意識的使用一些簡單的方法對信息來加密。如公元六年前的古希臘人通過使用一根叫scytale的棍子，將信息進(jìn)行加密。送信人先將一張羊皮條繞棍子螺旋形卷起來（如圖），然后把要寫的信息按某種順序?qū)懺谏厦?，接著打開羊皮條卷，通過其他渠道將信送給收信人。如果不知道棍子的寬度（這里作為密匙）就是不容易解密里面的內(nèi)容的，但是收信人可以根據(jù)事先和寫信人的約定，用同樣的scytale的棍子將書信解密。二是掩格密碼。16世紀(jì)米蘭的物理學(xué)和數(shù)學(xué)家Cardano發(fā)明的掩格密碼，可以事先設(shè)計(jì)好方格的開孔，將所要傳遞的信息和一些其他無關(guān)的符號組合成無效的信息，使截獲者難以分析出有效信息。三是棋盤密碼。我們可以建立一張表，使每一個(gè)字符對應(yīng)一數(shù)，是該字符所在行標(biāo)號，是列標(biāo)號。這樣將明文變成形式為一串?dāng)?shù)字密文。例如：明文battleonSunday密文121144443115034330434533141154（其中0表示空格）例如：如圖Polybius的棋盤密(B.C.200)也是一種在古希臘時(shí)已經(jīng)發(fā)展的比較完備加密的方法。希臘文字“”被加密為數(shù)字25424541443543四是Caesar密碼。據(jù)記載在羅馬帝國時(shí)期，凱撒大帝曾設(shè)計(jì)過一種簡單的移位密碼，用于戰(zhàn)時(shí)通信。這種加密方法就是將明文的字母按照字母順序，往后依次遞推相同的字母，就可以得到加密的密文，而解密的過程正好和加密的過程相反。其特點(diǎn)為：1.屬于單字母簡單替換密碼；2，已知解密和加密算法；3.明文語言集已知（用于英語）并且易于識別；4，結(jié)構(gòu)國語簡單，密碼分析員只使用很少的信息就可以預(yù)言加密的整個(gè)結(jié)構(gòu)。要指出的是，正是由于后三個(gè)特征，從而使得凱撒密碼很容易被蠻力攻擊方法分析。五是圓盤密碼。由于凱撒密碼加密的方法很容易被截獲者通過對密鑰賦值（1～25）的方法破解，人們有進(jìn)一步將其改善，只要將字母按照不同的順序進(jìn)行移動(dòng)就可以提高破解的難度，增加信息的保密程度。如15世紀(jì)佛羅倫薩人Alberti發(fā)明圓盤密碼就是這種典型的利用單表置換的方法加密的方法。如圖在兩個(gè)同心圓盤上，內(nèi)盤按不同（雜亂）的順序填好字母或數(shù)字，而外盤按照一定順序填好字母或數(shù)字，轉(zhuǎn)動(dòng)圓盤就可以找到字母的置換方法，很方便的進(jìn)行信息的加密與解密。凱撒密碼與圓盤密碼本質(zhì)都是一樣的，都屬于單表置換，即一個(gè)明文字母對應(yīng)的密文字母是確定的，截獲者可以分析對字母出現(xiàn)的頻率，對密碼體制進(jìn)行有效的攻擊。六是Vigenere密碼。為了提高密碼破譯的難度，人們發(fā)明一種多表置換的密碼，即一個(gè)明文字母可以表示為多個(gè)密文字母。多表密碼加密算法結(jié)果將使得對單表置換用的簡單頻率分析方法失效。其中，維吉尼亞密碼