應(yīng)用密碼學(xué)中的幾個(gè)重要算法(課程設(shè)計(jì)報(bào)告)

1、應(yīng)用密碼學(xué)中的幾個(gè)重要算法謝澤源 2013012613 信記1302密碼學(xué)（英語(yǔ)：cryptology）是研究如何隱密地傳遞信息的學(xué)科。密碼學(xué)的首要目的是隱藏信息的涵義，并不是隱藏信息的存在。如何將可理解的信息轉(zhuǎn)換成難以理解的信息，并且使得有秘密信息的人能夠逆向回復(fù)，但缺乏秘密信息的攔截者或竊聽(tīng)者則無(wú)法解讀。這是古典密碼學(xué)和部分現(xiàn)代密碼學(xué)的基本思想，例如：DES、AES。DES算法：DES是一種分組密碼協(xié)議，有兩個(gè)基本指導(dǎo)思想擴(kuò)散（Diffusion）和混亂（Confusion）,以保證密碼算法能滿足要求，所以DES的具體實(shí)現(xiàn)是依賴于多次迭代進(jìn)行乘積密碼加密變換。這個(gè)算法的核心是Feistel

2、密碼，由于其設(shè)計(jì)的巧妙，加密解密都用一個(gè)函數(shù)。它的算法是對(duì)稱的，既可用于加密又可用于解密。DES 使用一個(gè) 56 位的密鑰以及附加的 8 位奇偶校驗(yàn)位，產(chǎn)生最大 64 位的分組大小。這是一個(gè)迭代的分組密碼，使用稱為 Feistel 的技術(shù)，其中將加密的文本塊分成兩半。使用子密鑰對(duì)其中一半應(yīng)用循環(huán)功能，然后將輸出與另一半進(jìn)行“異或”運(yùn)算；接著交換這兩半，這一過(guò)程會(huì)繼續(xù)下去，但 最后一個(gè)循環(huán)不交換。DES 使用 16 個(gè)循環(huán)，使用異或，置換，代換，移位操作四種基本運(yùn)算。DES的流程基本是執(zhí)行16輪下面的運(yùn)算：1 初始變換Initial Permutation2 右邊32位f函數(shù)2.1 E置換2.2

3、 與輪密鑰XOR2.3 S盒替換2.4 P置換2.5 和左邊32位XOR3 左右交換，最終變換final permutation需要特別注意的是，最后一輪是不需要做左右交換這一部的。從具體實(shí)現(xiàn)看DES有幾個(gè)已知的方面存在脆弱性：1，加密協(xié)議半公開(kāi)化 2，密鑰太短 3，軟件的實(shí)現(xiàn)的性能較低。隨著計(jì)算機(jī)的處理能力的提高，只有56位密鑰的DES算法不再被認(rèn)為是安全性的，故現(xiàn)在一般的方案是三重DES，既3DES。AES 算法AES（The Advanced Encryption Standard）是一種非Feistel 的對(duì)稱分組密碼體制，和DES的基本指導(dǎo)思想一樣都是多次混淆，所不同的是非線性層的由

4、16個(gè)S盒進(jìn)行并置混淆。AES具有安全可靠、效率高等優(yōu)點(diǎn)。AES加密過(guò)程是在一個(gè)4×4的字節(jié)矩陣上運(yùn)作，這個(gè)矩陣又稱為“狀態(tài)（state）”，其初值就是一個(gè)明文區(qū)塊（矩陣中一個(gè)元素大小就是明文區(qū)塊中的一個(gè)Byte）。（Rijndael加密法因支持更大的區(qū)塊，其矩陣行數(shù)可視情況增加）加密時(shí)，各輪AES加密循環(huán)（除最后一輪外）均包含4個(gè)步驟： 1. AddRoundKey 矩陣中的每一個(gè)字節(jié)都與該次輪秘鑰（round key）做XOR運(yùn)算；每個(gè)子密鑰由密鑰生成方案產(chǎn)生。 2. SubBytes 通過(guò)個(gè)非線性的替換函數(shù)，用查找表的方式把每個(gè)字節(jié)替換成對(duì)應(yīng)的字節(jié)。 3. ShiftRows

5、將矩陣中的每個(gè)橫列進(jìn)行循環(huán)式移位。 4. MixColumns 為了充分混合矩陣中各個(gè)直行的操作。這個(gè)步驟使用線性轉(zhuǎn)換來(lái)混合每列的四個(gè)字節(jié)。AddRoundKey步驟在AddRoundKey步驟中，將每個(gè)狀態(tài)中的字節(jié)與該回合密鑰做異或（）。AddRoundKey步驟，回合密鑰將會(huì)與原矩陣合并。在每次的加密循環(huán)中，都會(huì)由主密鑰產(chǎn)生一把回合密鑰（通過(guò)Rijndael密鑰生成方案產(chǎn)生），這把密鑰大小會(huì)跟原矩陣一樣，以與原矩陣中每個(gè)對(duì)應(yīng)的字節(jié)作異或（）加法。SubBytes步驟在SubBytes步驟中，矩陣中各字節(jié)被固定的8位查找表中對(duì)應(yīng)的特定字節(jié)所替換,S; bij = 

6、;S（aij）.在SubBytes步驟中，矩陣中的各字節(jié)通過(guò)一個(gè)8位的S-box進(jìn)行轉(zhuǎn)換。這個(gè)步驟提供了加密法非線性的變換能力。S-box與GF（28）上的乘法反元素有關(guān)，已知具有良好的非線性特性。為了避免簡(jiǎn)單代數(shù)性質(zhì)的攻擊，S-box結(jié)合了乘法反元素及一個(gè)可逆的仿射變換矩陣建構(gòu)而成。此外在建構(gòu)S-box時(shí)，刻意避開(kāi)了固定點(diǎn)與反固定點(diǎn)，即以S-box替換字節(jié)的結(jié)果會(huì)相當(dāng)于錯(cuò)排的結(jié)果。此條目有針對(duì)S-box的詳細(xì)描述：Rijndael S-boxShiftRows步驟在ShiftRows步驟中，矩陣中每一行的各個(gè)字節(jié)循環(huán)向左方位移。位移量則隨著行數(shù)遞增而遞增。ShiftRows描述矩陣的行操作。

7、在此步驟中，每一行都向左循環(huán)位移某個(gè)偏移量。在AES中（區(qū)塊大小128位），第一行維持不變，第二行里的每個(gè)字節(jié)都向左循環(huán)移動(dòng)一格。同理，第三行及第四行向左循環(huán)位移的偏移量就分別是2和3。128位和192比特的區(qū)塊在此步驟的循環(huán)位移的模式相同。經(jīng)過(guò)ShiftRows之后，矩陣中每一豎列，都是由輸入矩陣中的每個(gè)不同列中的元素組成。Rijndael算法的版本中，偏移量和AES有少許不同；對(duì)于長(zhǎng)度256比特的區(qū)塊，第一行仍然維持不變，第二行、第三行、第四行的偏移量分別是1字節(jié)、3字節(jié)、4位組。除此之外，ShiftRows操作步驟在Rijndael和AES中完全相同。MixColumns步驟在MixCo

8、lumns步驟中，每個(gè)直行都在modulo 之下，和一個(gè)固定多項(xiàng)式c(x)作乘法。在MixColumns步驟，每一列的四個(gè)字節(jié)通過(guò)線性變換互相結(jié)合。每一列的四個(gè)元素分別當(dāng)作的系數(shù)，合并即為GF（28）中的一個(gè)多項(xiàng)式，接著將此多項(xiàng)式和一個(gè)固定的多項(xiàng)式在modulo 下相乘。此步驟亦可視為Rijndael有限域之下的矩陣乘法。MixColumns函數(shù)接受4個(gè)字節(jié)的輸入，輸出4個(gè)字節(jié)，每一個(gè)輸入的字節(jié)都會(huì)對(duì)輸出的四個(gè)字節(jié)造成影響。因此ShiftRows和MixColumns兩步驟為這個(gè)密碼系統(tǒng)提供了擴(kuò)散性。大致說(shuō)來(lái)，AES 加密算法的核心有四個(gè)操作。AddRoundKey 使用從

9、種子密鑰值中生成的輪密鑰代替 4 組字節(jié)。SubBytes 替換用一個(gè)代替表 替換單個(gè)字節(jié)。ShiftRows 通過(guò)旋轉(zhuǎn) 4字節(jié)行 的 4 組字節(jié)進(jìn)行序列置換。MixColumns 用域加和域乘的組合來(lái)替換字節(jié)。有限域GF(28)的加法和乘法正如你所看到的，AES 加密算法使用相當(dāng)簡(jiǎn)單明了的技術(shù)來(lái)代替和置換，除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基于數(shù)學(xué)（譯者注：近世代數(shù)）的域論。尤其是 AES 基于有限域GF(28)。GF(28)由一組從 0x00 到 0xff 的256個(gè)值組成，加上加法和乘法，因此是(28)。GF代表伽羅

10、瓦域，以發(fā)明這一理論的數(shù)學(xué)家的名字命名。GF(28) 的一個(gè)特性是一個(gè)加法或乘法的操作的結(jié)果必須是在0x00 . 0xff這組數(shù)中。雖然域論是相當(dāng)深?yuàn)W的，但GF(28)加法的最終結(jié)果卻很簡(jiǎn)單。GF(28) 加法就是異或（XOR）操作。在GF(28)中用0x01的乘法是特殊的；它相當(dāng)于普通算術(shù)中用1做乘法并且結(jié)果也同樣任何值乘0x01等于其自身?，F(xiàn)在讓我們看看用0x02做乘法。和加法的情況相同，理論是深?yuàn)W的，但最終結(jié)果十分簡(jiǎn)單。只要被乘的值小于0x80，這時(shí)乘法的結(jié)果就是該值左移1比特位。如果被乘的值大于或等于0x80，這時(shí)乘法的結(jié)果就是左移1比特位再用值0x1b異或。它防止了“域溢出”并保持乘

11、法的乘積在范圍以內(nèi)。一旦你在GF(28)中用0x02建立了加法和乘法，你就可以用任何常量去定義乘法。用0x03做乘法時(shí)，你可以將 0x03 分解為2的冪之和。為了用 0x03 乘以任意字節(jié)b， 因?yàn)?0x03 = 0x02 + 0x01，因此： b * 0x03 = b * (0x02 + 0x01) = (b * 0x02) + (b * 0x01)這是可以行得通的，因?yàn)槟阒廊绾斡?0x02 和 0x01 相乘和相加，用0x0d去乘以任意字節(jié)b可以這樣做：b * 0x0d = b * (0x08 + 0x04 + 0x01) = (b * 0x08) + (b * 0x04) +

12、 (b * 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x01)在加解密算法中，AES MixColumns 例程的其它乘法遵循大體相同的模式，如下所示：b * 0x09 = b * (0x08 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x01) b * 0x0b = b * (0x08 + 0x02 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02) + (b * 0x01) b * 0x0e = b * (0x08 + 0x0

13、4 + 0x02) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x02)總之，在GF(28)中，加法是異或操作。其乘法將分解成加法和用0x02做的乘法，而用0x02做的乘法是一個(gè)有條件的左移1比特位。AES規(guī)范中包括大量 有關(guān)GF(28)操作的附加信息。在Java中的實(shí)現(xiàn)：/* * 解密AES加密過(guò)的字符串 * * param content * AES加密過(guò)過(guò)的內(nèi)容 * param password * 加密時(shí)的密碼 * return 明文 */ public static byte decrypt(byte content,

14、 String password) try KeyGenerator kgen = KeyGenerator.getInstance("AES");/ 創(chuàng)建AES的Key生產(chǎn)者 kgen.init(128, new SecureRandom(password.getBytes(); SecretKey secretKey = kgen.generateKey();/ 根據(jù)用戶密碼，生成一個(gè)密鑰 byte enCodeFormat = secretKey.getEncoded();/ 返回基本編碼格式的密鑰 SecretKeySpec key = new SecretKeyS

15、pec(enCodeFormat, "AES");/ 轉(zhuǎn)換為AES專用密鑰 Cipher cipher = Cipher.getInstance("AES");/ 創(chuàng)建密碼器 cipher.init(Cipher.DECRYPT_MODE, key);/ 初始化為解密模式的密碼器 byte result = cipher.doFinal(content); return result; / 明文 catch (NoSuchAlgorithmException e) e.printStackTrace(); catch (NoSuchPaddingExce

16、ption e) e.printStackTrace(); catch (InvalidKeyException e) e.printStackTrace(); catch (IllegalBlockSizeException e) e.printStackTrace(); catch (BadPaddingException e) e.printStackTrace(); return null; RSA算法類似DES，AES等算法中雙方都使用相同的密鑰進(jìn)行加密解密，我們把這種加解密都使用同一個(gè)密鑰的密碼體制稱為對(duì)稱密碼體制。使用相同的密鑰進(jìn)行加密解密，密鑰的傳輸是一個(gè)重要的問(wèn)題。所以，在公

17、開(kāi)的計(jì)算機(jī)網(wǎng)絡(luò)上安全地傳送和保管密鑰是一個(gè)嚴(yán)峻的問(wèn)題。于是，密碼學(xué)家們構(gòu)想了一個(gè)不一樣的的密碼體制來(lái)解決這一問(wèn)題-公鑰加密算法。公鑰加密算法也稱非對(duì)稱密鑰算法，用兩對(duì)密鑰：一個(gè)公共密鑰和一個(gè)專用密鑰。用戶要保障專用密鑰的安全；公共密鑰則可以發(fā)布出去。公共密鑰與專用密鑰是有緊密關(guān)系的，用公共密鑰加密的信息只能用專用密鑰解密，反之亦然。由于公鑰算法不需要聯(lián)機(jī)密鑰服務(wù)器，密鑰分配協(xié)議簡(jiǎn)單，所以極大簡(jiǎn)化了密鑰管理。除加密功能外，公鑰系統(tǒng)還可以提供數(shù)字簽名。 RSA是其中的一種有效實(shí)現(xiàn)。RSA的基本指導(dǎo)思想是設(shè)計(jì)有效的單向陷門函數(shù)，來(lái)使得正向加密計(jì)算容易、沒(méi)有密鑰下的反向計(jì)算幾乎不可能。RSA

18、的安全性是建立在大整數(shù)分解的困難性上的。公鑰與密鑰的產(chǎn)生假設(shè)Alice想要通過(guò)一個(gè)不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來(lái)產(chǎn)生一個(gè)公鑰和一個(gè)私鑰：隨意選擇兩個(gè)大的質(zhì)數(shù)p和q，p不等于q，計(jì)算N=pq。根據(jù)歐拉函數(shù)，求得r = (p-1)(q-1)選擇一個(gè)小于 r 的整數(shù) e，求得 e 關(guān)于模 r 的模反元素，命名為d。（模反元素存在，當(dāng)且僅當(dāng)e與r互質(zhì)）將 p 和 q 的記錄銷毀。(N,e)是公鑰，(N,d)是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來(lái)。加密消息假設(shè)Bob想給Alice送一個(gè)消

19、息m，他知道Alice產(chǎn)生的N和e。他使用起先與Alice約好的格式將m轉(zhuǎn)換為一個(gè)小于N的整數(shù)n，比如他可以將每一個(gè)字轉(zhuǎn)換為這個(gè)字的Unicode碼，然后將這些數(shù)字連在一起組成一個(gè)數(shù)字。假如他的信息非常長(zhǎng)的話，他可以將這個(gè)信息分為幾段，然后將每一段轉(zhuǎn)換為n。用下面這個(gè)公式他可以將n加密為c：ne  c (mod N)計(jì)算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。解密消息Alice得到Bob的消息c后就可以利用她的密鑰d來(lái)解碼。她可以用以下這個(gè)公式來(lái)將c轉(zhuǎn)換為n：cd  n (mod N)得到n后，她可以將原來(lái)的信息m重新復(fù)原。解碼的原理是：cd  n&

20、#160;e·d(mod N)以及ed  1 (mod p-1)和ed  1 (mod q-1)。由費(fèi)馬小定理可證明（因?yàn)閜和q是質(zhì)數(shù)）n e·d  n (mod p) 和 n e·d  n (mod q)這說(shuō)明（因?yàn)閜和q是不同的質(zhì)數(shù)，所以p和q互質(zhì)）n e·d  n (mod pq)簽名消息RSA也可以用來(lái)為一個(gè)消息署名。假如甲想給乙傳遞一個(gè)署名的消息的話，那么她可以為她的消息計(jì)算一個(gè)散列值(Message digest)，然后用她

21、的密鑰(private key)加密這個(gè)散列值并將這個(gè)“署名”加在消息的后面。這個(gè)消息只有用她的公鑰才能被解密。乙獲得這個(gè)消息后可以用甲的公鑰解密這個(gè)散列值，然后將這個(gè)數(shù)據(jù)與他自己為這個(gè)消息計(jì)算的散列值相比較。假如兩者相符的話，那么他就可以知道發(fā)信人持有甲的密鑰，以及這個(gè)消息在傳播路徑上沒(méi)有被篡改過(guò)。Java實(shí)現(xiàn)加密和解密的過(guò)程：public class RSA             /*    

22、0; *  加密、解密算法      * param key 公鑰或密鑰      * param message 數(shù)據(jù)      * return      */      public 

23、static long rsa(int baseNum, int key, long message)          if(baseNum < 1 | key < 1)              return

24、60;0L;                    /加密或者解密之后的數(shù)據(jù)          long rsaMessage = 0L;           

25、         /加密核心算法          rsaMessage = Math.round(Math.pow(message, key) % baseNum;          return rsaMessage;  &#

26、160;                           public static void main(String args)          /基數(shù)  

27、60;       int baseNum = 3 * 11;          /公鑰          int keyE = 3;         

28、0;/密鑰          int keyD = 7;          /未加密的數(shù)據(jù)          long msg = 24L;        &#

29、160; /加密后的數(shù)據(jù)          long encodeMsg = rsa(baseNum, keyE, msg);          /解密后的數(shù)據(jù)          long decodeMsg =

30、0;rsa(baseNum, keyD, encodeMsg);                    System.out.println("加密前：" + msg);          System.out.println("

31、加密后：" + encodeMsg);          System.out.println("解密后：" + decodeMsg);                  RSA加密算法的安全性當(dāng)p和q是一個(gè)大素?cái)?shù)的時(shí)候，從它們的積pq去分解因子p和

32、q，這是一個(gè)公認(rèn)的數(shù)學(xué)難題。然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。1994年彼得·秀爾（Peter Shor）證明一臺(tái)量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行因數(shù)分解。假如量子計(jì)算機(jī)有朝一日可以成為一種可行的技術(shù)的話，那么秀爾的算法可以淘汰RSA和相關(guān)的衍生算法。（即依賴于分解大整數(shù)困難性的加密算法）另外，假如N的長(zhǎng)度小于或等于256位，那么用一臺(tái)個(gè)人電腦在幾個(gè)小時(shí)內(nèi)就可以分解它的因子了。1999年，數(shù)百臺(tái)電腦合作分解了一個(gè)512位長(zhǎng)的N。1997年后開(kāi)發(fā)的系統(tǒng)，用戶應(yīng)使用1024位密鑰，證書認(rèn)證機(jī)構(gòu)應(yīng)用2048位或以上。RSA

33、加密算法的缺點(diǎn)雖然RSA加密算法作為目前最優(yōu)秀的公鑰方案之一，在發(fā)表三十多年的時(shí)間里，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受。但是，也不是說(shuō)RSA沒(méi)有任何缺點(diǎn)。由于沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度的等價(jià)性。所以，RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。在實(shí)踐上，RSA也有一些缺點(diǎn)：產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密；分組長(zhǎng)度太大，為保證安全性，n 至少也要 600 bits 以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，。SHA-1算法與其他算法不一樣的是，SHA-1設(shè)計(jì)的出發(fā)點(diǎn)是用于數(shù)字簽名，其本質(zhì)是一種散列函數(shù)（HASH）。哈希（Hash）是將目標(biāo)

34、文本轉(zhuǎn)換成具有相同長(zhǎng)度的、不可逆的雜湊字符串（或叫做消息摘要）由于哈希算法的定義域是一個(gè)無(wú)限集合，而值域是一個(gè)有限集合，將無(wú)限集合映射到有限集合，根據(jù)“鴿籠原理(Pigeonhole principle)”，每個(gè)哈希結(jié)果都存在無(wú)數(shù)個(gè)可能的目標(biāo)文本，因此哈希不是一一映射，是不可逆的。Java實(shí)現(xiàn)：import java.security.*; public class myDigest public static void main(String args) myDigest my=new myDigest(); my.testDigest(); public void testDigest() try String myinfo="我的測(cè)試信息" /java.security.MessageDigest alg=java.security.MessageDigest.getInstance("MD5"); java.security.MessageDigest alga=java.security.MessageDigest.getInstance("SHA-1"); alga.update(myinfo.getBytes(); byte digesta=