密碼的加密與解密

密碼的加密與解密（一）引言（二）置換密碼（三）仿射變換密碼（四）Hill密碼（五）公開(kāi)密鑰系統(tǒng)（一）引言隨著社會(huì)的信息化，通信技術(shù)迅速發(fā)展，信息高速公路的建立，使網(wǎng)絡(luò)安全問(wèn)題受到重視。當(dāng)網(wǎng)絡(luò)中從計(jì)算機(jī)到計(jì)算機(jī)傳輸?shù)呢?cái)務(wù)報(bào)告、醫(yī)療記錄以及其他敏感的信息很容易被截取破譯時(shí)，有關(guān)信息安全以及保障隱私權(quán)的擔(dān)心也就與日俱增。信息的發(fā)送方為了保護(hù)自己的信息不被敵方輕易破解，通常會(huì)先將信息進(jìn)行加密，形成一堆普通人無(wú)法看懂的亂碼，然后再發(fā)送出去；而接收方接到加密信息后，則對(duì)其進(jìn)行解密，還原出原始信息，從而既完成信息的傳遞，又達(dá)到保密的目的。 事實(shí)上，密碼作為軍事和政治斗爭(zhēng)中的一種技術(shù)，古已有之，自從人類(lèi)有了戰(zhàn)爭(zhēng)，也就產(chǎn)生了密碼。如何使敵人無(wú)法破譯密文而又能使盟友容易譯出密文，一直是外交官和軍事首腦關(guān)心的重要問(wèn)題。近三四十年來(lái)，隨著計(jì)算機(jī)科學(xué)的蓬勃發(fā)展，數(shù)據(jù)安全作為一個(gè)新的分支已活躍在計(jì)算機(jī)科學(xué)領(lǐng)域，各種加密方法如雨后春筍般的出現(xiàn)，20世紀(jì)70年代后半期出現(xiàn)的數(shù)據(jù)加密標(biāo)準(zhǔn)和公開(kāi)密鑰系統(tǒng)就是其中兩種重要的加密方法。密碼學(xué)涉及的數(shù)學(xué)理論數(shù)論信息論概率統(tǒng)計(jì)代數(shù)幾何中的橢圓曲線明文加密密鑰加密密文公共信道解密原始明文破譯密碼解密密鑰如果甲方要通過(guò)公共信道向乙方傳送信息（message），為了保護(hù)信息不被第三方竊取和篡改，在發(fā)送信息之前需要把它變成秘密的形式，將要傳送的原始信息稱(chēng)為明文（plaintext），而將在公共信道中傳遞的明文的秘密形式成為密文（ciphertext）。用某種方法把明文變成密文的過(guò)程稱(chēng)為加密（encryption），利用密碼把密文還原為明文的過(guò)程稱(chēng)為解密（decryption），密碼中的關(guān)鍵信息稱(chēng)為密鑰。顯然，密鑰在保密通信中占有極其重要的地位，通常由通信雙方秘密商定。初等數(shù)論基礎(chǔ)知識(shí)性質(zhì)1：同余是一種等價(jià)關(guān)系，即性質(zhì)2同余式可以相加，即若有則性質(zhì)3

同余式可以相乘，即若（1）成立，則（1）性質(zhì)4

同余式等價(jià)于特別的，當(dāng)（2）(mod7)a123456a-1145236例a15711a-1(mod12)15711a123456789101112(mod13)a-1179108112534612定義2

同余式(二)置換密碼

將每個(gè)字母由某個(gè)其他的字母來(lái)替換，替換的規(guī)律可以是隨機(jī)的，也可以是系統(tǒng)的，總共有26！種可能的密碼。

古羅馬偉大的軍事家和政治家凱撒大帝在公元前50世紀(jì)使用的凱撒密碼就是一個(gè)典型的系統(tǒng)置換密碼。

凱撒密碼就是把明文中的每個(gè)字母用按順序后移3位之后的字母來(lái)表示形成密文，即A→DB→E….W→ZX→AY→BZ→C這個(gè)密碼可以用數(shù)學(xué)模型描述：Step1：將26個(gè)字母與整數(shù)0~25建立一一對(duì)應(yīng)關(guān)系A(chǔ)BCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Step2:建立數(shù)學(xué)模型例：MATHEMATICALMODELING用凱撒密碼表示出來(lái)就是ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425PDWKHPDWLFDOPRGHOLQJ為了迷惑敵人，密文通常都寫(xiě)成5個(gè)字母一組的形式，PDWKHPDWLFDOPRGHOLQJ顯然在凱撒密碼中，整數(shù)3就是密鑰，如果要對(duì)一個(gè)用凱撒密碼加密的密文進(jìn)行解密，只要對(duì)p求解同余式稱(chēng)由下面公式給出的密碼為移位置換密碼對(duì)于移位置換密碼來(lái)說(shuō)，破譯的關(guān)鍵在于如何確定移位因子k的數(shù)值。如何確定移位因子k？方法一：窮舉法對(duì)k從1到m-1分別計(jì)算直到出現(xiàn)有明確意義的明文為止。缺點(diǎn)：這種方法僅對(duì)移位置換密碼有效，如果是隨機(jī)置換密碼，此方法就會(huì)失效，因?yàn)槊杜e次數(shù)將達(dá)到m!方法二：字母頻率法書(shū)面語(yǔ)言的一個(gè)重要特征是單個(gè)字母不是以同樣的頻率出現(xiàn)的。在英文常用文章中，平均說(shuō)來(lái)，字母“E”出現(xiàn)的頻率最高，可以占到所有字母的13%，其次是字母“T”，大致可占所有字母的10%左右，而字母“Z”出現(xiàn)的頻率遠(yuǎn)遠(yuǎn)小于1%。英文字母出現(xiàn)頻率分布表ABCDEFG0.08560.01390.02790.03780.13040.02890.0199HIJKLMN0.05280.06270.00130.00420.03390.02490.0707OPQRSTU0.07970.01990.00120.06770.00070.10450.0249VWXYZ0.00920.01490.00170.01990.0008例：已知下面的密文是用移位置換密碼編寫(xiě)的，試破譯該密文UQJFXJLTYTYMJBTWQIYWFIJHJSYJWYTFYYJSIYMJSLFYYMWJJURSJCYBJISJXIFD容易看出，其中出現(xiàn)頻率最高的字母是J，將其與字母“E”相對(duì)應(yīng)，這樣可求出k=5,于是破譯出相應(yīng)的有明確意義的明文為ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425PLEASEGOTOTHEWORLDTRADECENTERTOATTENDTHEMEETINGATTHREEPMNEXTWEDNESDAY即PLEASEGOTOTHEWORLDTRADECENTERTOATTENDTHEMEETINGATTHREEPMNEXTWEDNESDAY請(qǐng)?jiān)谙轮苋挛?點(diǎn)到世界貿(mào)易中心參加會(huì)議（三）仿射變換密碼數(shù)學(xué)模型其中自然數(shù)a必須與模m互素仿射變換的解密公式可以通過(guò)求解（1）得到（1）（2）式兩邊同時(shí)乘以a-1,即得（2）

在移位置換密碼下，明文中相鄰的字母對(duì)應(yīng)的密文字母也是相鄰的，而對(duì)于仿射變換密碼來(lái)說(shuō)，明文中相鄰的字母對(duì)應(yīng)的密文字母分別為D和E，但在仿射變換對(duì)應(yīng)的密文字母分別為F和I，它們之間有3個(gè)字母的間隔（a=3）例：假設(shè)下面的密文是使用仿射變換加密的，試破譯此段密文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHK

FSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS對(duì)于這個(gè)問(wèn)題，假設(shè)明文是由26個(gè)英文字母組成的，可取m=26,由于a與26互素，于是a的數(shù)值有12種可能取法35791113151719212325b有26種不同的取法，所以仿射變換總有種可能變化如果采用窮舉法破譯這段密碼，就要進(jìn)行312次嘗試。當(dāng)字符系統(tǒng)更為復(fù)雜時(shí)，如考慮標(biāo)點(diǎn)符號(hào)和數(shù)字等，需要枚舉的次數(shù)將會(huì)大為增加，因此采用其他更為有效的破譯方法是需要的。計(jì)算密文中各字母出現(xiàn)的頻率，F(xiàn)SFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHK

FSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS發(fā)現(xiàn)“F”出現(xiàn)12次，“R”出現(xiàn)11次，“S”出現(xiàn)9次，“K”出現(xiàn)8次，其他字母出現(xiàn)的次數(shù)較少，使用字母頻率法。假設(shè)1：密文中出現(xiàn)頻率最高的字母對(duì)應(yīng)于英文中最常見(jiàn)的字母，“F”對(duì)應(yīng)“E”，“R”對(duì)應(yīng)“T”，得到如下兩個(gè)同余式兩式相減，可得因?yàn)?5關(guān)于26的同余逆為7但是a=6與26不是互素的，無(wú)法對(duì)密文進(jìn)行解密假設(shè)2用“R”對(duì)應(yīng)“E”，“S”對(duì)應(yīng)“T”，得到另外兩個(gè)同余式（1）-（2）得得加密公式解密公式利用解密公式解密得到（1）（2）代入（1）得GTGAERCSGTKESREDGQETDICHHAEEDGTGXQJGTCKDGTAMHECTDJESMXXEEZGRGDDJWRKLGUGXDERTMMT這是一串沒(méi)有意義的文字，解密失敗假設(shè)3：令“R”對(duì)應(yīng)“E”，“K”對(duì)應(yīng)“T”，可得同余式(1)-(2)，得于是得到一個(gè)加密公式關(guān)于p求解這個(gè)方程就可以求得解密公式（1）（2）帶入（1）得最后利用解密公式得破譯后的明文為ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEIHTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON周四下午一個(gè)美國(guó)特工將在咖啡館與一位阿富汗間諜接頭（四）Hill密碼

前面介紹了如何破譯置換密碼，即使是在字母的置換是隨機(jī)的情況下，仍然可以利用字母出現(xiàn)的頻率，同時(shí)考慮字母組合出現(xiàn)的頻率進(jìn)行解密，從而達(dá)到破譯密碼的目的。究其原因，問(wèn)題出在明文中給定的字母在密文中總是用同一個(gè)字母來(lái)表示。這樣明文中文字的所有性質(zhì)都會(huì)在密文中體現(xiàn)出來(lái)，可以利用這些性質(zhì)對(duì)密文進(jìn)行解密。為了防止利用字母頻率解密，可以采用下面的加密方式，每次加密一組字母而不是加密單個(gè)字母。把n個(gè)明文字母組成一組，用n個(gè)密文字母來(lái)代替，這種加密方法稱(chēng)為Hilln密碼。Hill密碼是密文中字母出現(xiàn)的頻率變得不規(guī)則起來(lái)，也就是說(shuō)它將使明文中同一個(gè)字母在密文中大量的表示方式，從而徹底改變明文中的文字性質(zhì)。例：設(shè)明文為MEET，采用Hill2密碼對(duì)其進(jìn)行加密，即對(duì)每?jī)蓚€(gè)字母一組進(jìn)行加密。假設(shè)加密矩陣為求這段明文的Hill2密文將明文分為兩組MEET由此構(gòu)造出兩個(gè)二維列向量在上述兩個(gè)向量的左邊乘以矩陣A，得到兩個(gè)新的列向量再對(duì)這兩個(gè)列向量關(guān)于模26作余運(yùn)算，得于是對(duì)應(yīng)的密文為UUQR注意：明文中的一個(gè)字母“E”在密文中分別用兩個(gè)不同字母“U”和“Q”表示，而密文中的同一個(gè)字母“U”則對(duì)應(yīng)不同的明文字母“M”和“E”。由此明文中字母出現(xiàn)的頻率就被完全打亂了，從而使破譯變得困難起來(lái)Hilln密碼加密過(guò)程S1：選擇一個(gè)n階可逆整數(shù)方陣A作為加密矩陣，它是這個(gè)加密系統(tǒng)的密鑰S2:將明文字符按順序進(jìn)行分組，每n個(gè)字符一組，若最后一組不足n個(gè)字符，則補(bǔ)充一些沒(méi)有實(shí)際意義的虛設(shè)字符，使每一組都由n個(gè)字符組成S3：將每個(gè)明文字符對(duì)應(yīng)于一個(gè)整數(shù)，構(gòu)成一組n維列向量aS4：用加密矩陣A左乘每一個(gè)列向量a，得到新的n維列向量S5：對(duì)β的每個(gè)分量關(guān)