《信息安全導(dǎo)論》課件2第9章

第9章密碼學(xué)與信息安全

9.1密碼學(xué)的基本概念

9.2對(duì)稱密碼體制

9.3公鑰密碼體制

思考題

實(shí)驗(yàn)9簡(jiǎn)單加解密算法的實(shí)現(xiàn)

內(nèi)容導(dǎo)讀

密碼學(xué)在信息安全領(lǐng)域作用巨大，其相關(guān)技術(shù)能夠直接用來(lái)實(shí)現(xiàn)保密性、數(shù)據(jù)完整性、可認(rèn)證性和不可否認(rèn)性服務(wù)。加密不僅可以保護(hù)存儲(chǔ)中的數(shù)據(jù)，也可以用來(lái)保護(hù)通信。敵手對(duì)加密體制的攻擊就是在不知道密鑰的情況下想法找出密文對(duì)應(yīng)的明文或密鑰。密碼體制可分為對(duì)稱體制和公鑰體制，公鑰體制能很容易實(shí)現(xiàn)不可否認(rèn)性服務(wù)。典型的對(duì)稱密碼算法有RC4、DES和AES等，公鑰密碼算法有RSA、ElGamal和ECC等。9.1密碼學(xué)的基本概念經(jīng)典的密碼學(xué)主要研究加密和解密理論，隨著密碼學(xué)研究領(lǐng)域的擴(kuò)展，要精確定義現(xiàn)代密碼學(xué)的研究范圍是非常困難的。目前人們一般認(rèn)為密碼學(xué)是研究基于困難問(wèn)題存在性的技術(shù)和應(yīng)用的科學(xué)，而一般教科書(shū)中討論的密碼學(xué)框架如圖9-1所示。圖9-1密碼學(xué)框架示意圖自從人類有了戰(zhàn)爭(zhēng)，就有了加密通信，因而也就有了密碼學(xué)。兩千多年前，愷撒大帝在戰(zhàn)爭(zhēng)中使用了字母變換密碼來(lái)傳遞信息，在第二次世界大戰(zhàn)中，中國(guó)專家池步洲(1908—2003)成功破譯日軍密碼，促使山本五十六被截殺。

1949年Shannon發(fā)表的論文“保密系統(tǒng)的通信原理”奠定了密碼學(xué)的數(shù)學(xué)理論基礎(chǔ)，1976年Diffie和Hellman的論文“密碼學(xué)的新方向”奠定了公鑰密碼學(xué)的基礎(chǔ)，1977年美國(guó)頒布了數(shù)據(jù)加密標(biāo)準(zhǔn)DES，2001年美國(guó)正式頒布AES為新的國(guó)家加密標(biāo)準(zhǔn)，近年來(lái)，量子密碼和DNA密碼的研究又把我們帶入了一個(gè)新的密碼時(shí)代。現(xiàn)代密碼學(xué)在信息安全中占有非常重要的地位，原因在于它能夠直接實(shí)現(xiàn)保密性、數(shù)據(jù)完整性、可認(rèn)證性和不可否認(rèn)性服務(wù)，如圖9-1所示。

密碼學(xué)中最基本的概念是加密與解密。假如Alice要把消息m通過(guò)不安全的信道保密地傳給Bob，那么可按照?qǐng)D9-2方式進(jìn)行。圖9-2保密通信示意圖在圖9-2中，Alice要發(fā)送的消息m叫明文，明文被變換E轉(zhuǎn)化成的看似無(wú)意義的隨機(jī)消息C稱為密文，而這個(gè)變換E就叫加密。Bob通過(guò)變換D把C轉(zhuǎn)化為m的過(guò)程稱為解密。加密和解密都需要有Key的支持，這個(gè)Key稱為密鑰。如果加密方和解密方使用的是同樣的密鑰，相應(yīng)的變換稱為對(duì)稱密鑰加(解)密算法；否則稱為非對(duì)稱密鑰加(解)密算法或公開(kāi)密鑰加(解)密算法。所謂破解，即是敵手在不知道密鑰的情況下，把密文C還原成m或推導(dǎo)出解密密鑰。理想的安全密碼算法應(yīng)該能公開(kāi)其算法流程，不管敵手采用何種攻擊辦法，只要不告訴其密鑰，敵手就無(wú)法通過(guò)密文找出對(duì)應(yīng)明文或密鑰。也就是說(shuō)，敵手針對(duì)安全密碼算法的最好攻擊方式就是暴力攻擊(即搜索全部密鑰空間)。表9-1是敵手攻擊密碼系統(tǒng)時(shí)可能擁有資源的情況。表9-1攻擊類型與攻擊者擁護(hù)的資源情況理論上，只有一次一密(每個(gè)密碼只使用一次)的密碼系統(tǒng)才是不可破解的，沒(méi)有絕對(duì)安全的密碼算法。在實(shí)際應(yīng)用中，如果一個(gè)密碼算法用實(shí)際可得到的資源，在相對(duì)有限的時(shí)間內(nèi)不能破解，則稱該算法是計(jì)算上安全的。9.2對(duì)稱密碼體制9.2.1對(duì)稱密碼體制概述在對(duì)稱加密體制中，加密算法E和解密算法D使用相同的密鑰k如圖9-3所示。發(fā)送方Alice利用加密算法E和密鑰k將明文m加密成密文c，即c=E(k,m)。接收方Bob利用解密算法D和密鑰k將密文c解密成明文m，即m=D(k,c)。因此，在對(duì)稱加密體制中，對(duì)于明文m，有為了使用對(duì)稱加密體制，通信雙方應(yīng)提前商定一個(gè)會(huì)話密鑰和使用的具體算法，而后進(jìn)行秘密通信。圖9-3對(duì)稱密碼體制對(duì)稱密碼又分為流密碼和分組密碼兩大類。流密碼是按比特進(jìn)行加密，分組密碼是若干比特(定長(zhǎng))同時(shí)加密，其示意圖分別如圖9-4和圖9-5所示。圖9-4流密碼示意圖圖9-5分組密碼示意圖9.2.2典型算法介紹

1．維基尼亞密碼維基尼亞密碼是古典密碼的典型代表，這是一個(gè)多表替換密碼，其基本原理如圖9-6所示。圖中明文是“MESSAGEFROM…”，密鑰是“WHITE”，對(duì)應(yīng)的密碼文是“ILALECLNKS...”。有關(guān)該算法的具體實(shí)現(xiàn)可參見(jiàn)本章實(shí)驗(yàn)部分的有關(guān)內(nèi)容，請(qǐng)同學(xué)們寫(xiě)出加解密算法的具體數(shù)學(xué)表達(dá)式。圖9-6維基尼亞密碼示意圖古典密碼在歷史上發(fā)揮了巨大作用，香農(nóng)曾把古典密碼的編制思想概括為“混淆”和“擴(kuò)散”，這種思想對(duì)于現(xiàn)代密碼編制仍具有非常重要的指導(dǎo)意義。

2．RC4

RC4是美國(guó)麻省理工學(xué)院RonRivest于1987年設(shè)計(jì)的密鑰長(zhǎng)度可變的流密碼算法。MicrosoftWindows系統(tǒng)、安全套接層協(xié)議SSL和無(wú)線局域網(wǎng)通信協(xié)議WEP中均使用了該密碼算法。有關(guān)RC4算法的詳細(xì)內(nèi)容見(jiàn)本章實(shí)驗(yàn)。其他流密碼算法還有A5、Salsa20等。

3．?dāng)?shù)據(jù)加密標(biāo)準(zhǔn)DES數(shù)據(jù)加密標(biāo)準(zhǔn)(DataEncryptionStandard，DES)是最著名的分組加密算法之一。1977年的FIPSPUB46中給出了DES的完整描述。

DES的明文分組長(zhǎng)度n為64bit，密鑰為56bit，加密后產(chǎn)生64bit的密文分組。加密分為三個(gè)階段，首先是一個(gè)初始置換IP，用于重排64bit的明文分組；然后進(jìn)行相同功能的16輪變換，第16輪變換的輸出分左右兩半，并被交換次序；最后經(jīng)過(guò)一個(gè)逆置換，產(chǎn)生最終的64bit密文。DES加密算法的框圖如圖9-7所示。圖9-7DES加密算法框圖

DES的16輪加密變換中每一輪變換的結(jié)構(gòu)如圖9-8所示。圖9-8DES加密算法的輪結(jié)構(gòu)每一輪加密過(guò)程可用數(shù)學(xué)表達(dá)式表述為：Li?=?Ri-1，Ri?=?Li-1?

F(Ri-1,Ki)。圖9-7和圖9-8中用到的初始置換IP、逆初始置換IP-1、擴(kuò)展運(yùn)算表E和置換運(yùn)算P分別見(jiàn)表9-2至表9-5，函數(shù)F(R，K)的計(jì)算過(guò)程如圖9-9所示。

表9-2初始置換IP表9-3逆初始置換IP-1

表9-4輪結(jié)構(gòu)中擴(kuò)展置換E

表9-5輪結(jié)構(gòu)中置換運(yùn)算圖9-9函數(shù)F(R，K)的計(jì)算過(guò)程在計(jì)算F(R，K)的過(guò)程中，要用到8個(gè)S盒。這8個(gè)S盒的具體定義見(jiàn)表9-6。表9-6DES的S盒對(duì)每個(gè)盒Si，其6bit輸入中，第1個(gè)和第6個(gè)比特形成一個(gè)2位二進(jìn)制數(shù)，用來(lái)選擇Si的4個(gè)代換中的一個(gè)。6bit輸入中，中間4位用來(lái)選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個(gè)數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。例如，S1的輸入為011001，行選為01(即第1行)，列選為1100(即第12列)，行列交叉位置的數(shù)為9，其4位二進(jìn)制表示為1001，所以S1的輸出為1001。

DES16輪迭代中，每一輪子密鑰Ki的長(zhǎng)度都是48bit。輸入的56bit密鑰首先經(jīng)過(guò)一個(gè)置換PC-1，然后將置換后的56bit分為各為28bit的左、右兩半，分別記為C0和D0。在第i輪分別對(duì)Ci-1和Di-1進(jìn)行左循環(huán)移位，所移位數(shù)由表給出。移位后的結(jié)果作為求下一輪子密鑰的輸入，同時(shí)也作為置換選擇PC-2的輸入。通過(guò)置換選擇2產(chǎn)生的48bit的Ki，即為本輪的子密鑰，作為函數(shù)F(Ri-1，Ki)的輸入。兩個(gè)置換PC-1和PC-2分別見(jiàn)表9-7和9-8，每一輪左循環(huán)移位數(shù)見(jiàn)表9-9。表9-7

PC-1表9-8

PC-2表9-9左循環(huán)移位數(shù)

DES的解密和加密使用同一算法，但子密鑰使用的順序相反。

DES已走到了它生命的盡頭，其56bit密鑰實(shí)在太小。2000年10月，美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所(NIST)選擇Rijndael密碼作為高級(jí)加密標(biāo)準(zhǔn)AES。Rijndael密碼是一種迭代型分

組密碼，由比利時(shí)密碼學(xué)家JoanDaemon和VincentRijmen設(shè)計(jì)，使用了有限域GF(28)上的算術(shù)運(yùn)算。數(shù)據(jù)分組長(zhǎng)度和密鑰長(zhǎng)度都可變，并可獨(dú)立指定為128bit、192bit或256bit比特，隨著分組長(zhǎng)度不同迭代次數(shù)也不同。Rijndael密碼可在很多處理器和專用硬件上高效地實(shí)現(xiàn)。對(duì)稱密碼具有加密速度快、密鑰短、易于硬件或其他機(jī)械裝置實(shí)現(xiàn)等優(yōu)點(diǎn)，但這種算法初始化比較困難，系統(tǒng)需要的密鑰量也很大。表9-10給出了一些歷史上著名的分組密碼算法，著名的電子郵件安全軟件PGP(PrettyGoodPrivacy)就采用了IDEA算法進(jìn)行數(shù)據(jù)加密。表9-10一些著名的分組密碼算法9.3公鑰密碼體制9.3.1公鑰密碼體制概述在公鑰密碼體制中，每一個(gè)用戶都擁有一對(duì)個(gè)人密鑰k=(pk,sk)，其中pk是公開(kāi)的，任何用戶都可以知道，sk是保密的，只有擁有者本人知道。假如Alice要把消息m保密地發(fā)送給Bob，則Alice利用Bob的公鑰pk加密明文m，得到密文c:=E(pk,m)，并把密文傳送給Bob。Bob得到Alice傳過(guò)來(lái)的c后，利用自己的私鑰sk解密密文c得到明文m=D(sk,c)，如圖9-10所示。圖9-10公鑰密碼工作原理圖

公鑰密碼體制與對(duì)稱密碼體制的主要區(qū)別是前者的加密密鑰和解密密鑰是不同的。這個(gè)不同導(dǎo)致了：①在公鑰密碼系統(tǒng)中，密鑰維護(hù)總量大大減少；②在公鑰密碼系統(tǒng)中可以很容易實(shí)現(xiàn)抗否認(rèn)性。在公鑰體制中，用戶的公鑰pk和私鑰sk是緊密關(guān)聯(lián)的，否則加密后的數(shù)據(jù)是不可能解密的。但在安全的體制中，這種關(guān)聯(lián)也是敵手無(wú)法利用的，即想通過(guò)公鑰獲取私鑰或部分私鑰在計(jì)算上是不可行的。公鑰和私鑰的關(guān)聯(lián)性設(shè)計(jì)一般是建立在諸如大整數(shù)分解、離散對(duì)數(shù)求解、橢圓曲線上的離散對(duì)數(shù)求解等困難問(wèn)題上的，假如敵手能通過(guò)公鑰想辦法獲取私鑰信息，則敵手應(yīng)該能解決數(shù)千年沒(méi)解決的數(shù)學(xué)難題。9.3.2RSA公鑰密碼體制

RSA密碼體制是世界上應(yīng)用最為廣泛的公鑰密碼體制。RSA體制的安全性基于大整數(shù)分解的困難性，即已知兩個(gè)大素?cái)?shù)p和q，求n∶=?pq是容易的，而由n求p和q則是困難的。

RSA算法包括密鑰生成算法和加解密算法兩部分。密鑰生成算法如下：

(1)選擇不同的大素?cái)?shù)p和q，計(jì)算，。

(2)選擇e，滿足1<e<，且，(n,e)作為公鑰。

(3)通過(guò)計(jì)算d，且，(n,d)作為私鑰。

RSA加解密算法如下：

RSA加密：RSA解密：加密時(shí)首先對(duì)明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長(zhǎng)度小于?；诎踩紤]，目前RSA密碼體制使用的大素?cái)?shù)至少要在512bit以上。由于要進(jìn)行大數(shù)的計(jì)算，RSA運(yùn)算速度較慢，其軟件實(shí)現(xiàn)大概要比DES慢100倍。讀者可以對(duì)有關(guān)RSA算法的安全性作進(jìn)一步分析，也可參閱其他文獻(xiàn)。

除了RSA以外，著名的公鑰密碼算法還有Rabin算法(1979)、ElGamal算法(1985)、橢圓曲線算法ECC(1985)、基于格的NTRU算法(1996)和基于6次擴(kuò)域上的離散對(duì)數(shù)XTR算法(2000)等。思考題

(1)密碼學(xué)主要包含哪些內(nèi)容，密碼技術(shù)能提供哪些安全服務(wù)?

(2)古典密碼體制的主要思想是什么，如何理解密碼算法的安全性？

(3)簡(jiǎn)述DES加解密算法流程。(4)對(duì)稱密碼體制和公鑰密碼體制的主要區(qū)別是什么？(5)簡(jiǎn)述公鑰密碼算法的基本原理。(6)簡(jiǎn)述RSA算法及其安全性。實(shí)驗(yàn)9簡(jiǎn)單加解密算法的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?/p>

(1)掌握對(duì)稱加密算法的基本思想。

(2)深入理解Vigenere算法和RC4算法的算法流程。

(3)了解DES、AES等算法的加解密過(guò)程。二、實(shí)驗(yàn)準(zhǔn)備

(1)查閱有關(guān)資料，熟悉古典加密算法中單表代換與多表代換算法，掌握Vigenere算法。

(2)查閱有關(guān)資料，熟悉流密碼的基本思想，掌握RC4算法。

(3)查閱有關(guān)資料，熟悉DES和AES加解密程。三、實(shí)驗(yàn)內(nèi)容

(1)分析、調(diào)試運(yùn)行下面代碼，并寫(xiě)出代碼的算法流程圖。

#include<stdio.h>

#include<string>

voidmain()

{inti,j,m,n,cmd;intlength_keyword,length_plaintext;charkeyword[21],plain_text[401];charvigenere_table[26][26];memset(keyword,0,21);memset(plain_text,0,401);printf("VigenereTable:\n");printf("\n");for(i=0;i<=25;i++){printf("%c",'a'+i);}printf("\n\n");for(i=0;i<=25;i++){printf("%c",'a'+i);for(j=0;j<=25;j++){

vigenere_table[i][j]='a'+(i+j)%26;

printf("%c",vigenere_table[i][j]);

}

printf("\n");}printf("\n");for(i=0;i<=25;i++){printf("%c",'a'+i);}while(1){printf("\n\n***********************************\n");printf("cmd\"1\"toenterencryptprocess.\n");printf("cmd\"2\"toenterdecryptprocess.\n");printf("cmd\"0\"toquit.\n");

printf("***********************************\n");scanf("%d",&cmd);

getchar();switch(cmd){{case1:printf("Pleaseenteryoukeyword(*onlylowercase&<=20acceptable*):\n"); gets(keyword);length_keyword=strlen(keyword);printf("Keyword:\n");puts(keyword);

printf("\n");printf("Num:\n");

printf("%d\n",length_keyword);printf("Pleaseenteryouplaintext(*onlylowercase&<=400acceptable*):\n");gets(plain_text);length_plaintext=strlen(plain_text);printf("Cryptographis:\n");/*加密算法*/for(j=0;j<length_plaintext;j++){m=keyword[j%length_keyword]-'a';n=plain_text[j]-'a';printf("%c",vigenere_table[m][n]);}printf("\n");break;case2:printf("Pleaseenteryoukey(*onlylowercase&<=20acceptable*):\n");gets(keyword);length_keyword=strlen(keyword);printf("Key:\n");

puts(keyword);printf("\n");printf("nNum:\n");

printf("%d\n",length_keyword);printf("Pleaseenteryoucryptograph(*onlylowercase&<=400acceptable*):\n");gets(plain_text);//這里plain_text數(shù)組保存的是密文

length_plaintext=strlen(plain_text);printf("Plaintextis:\n");/*解密算法*/

for(i=0;i<length_plaintext;i++){intcryptograph_index=plain_text[i]-'a'; introw_index=keyword[i%length_keyword]-'a'; intindex=(cryptograph_index-row_index+26)%26; printf("%c",vigenere_table[0][index]);}printf("\n");break;

case0:exit(0);default:printf("命令無(wú)效,請(qǐng)重新輸入!");break;}}}

(2)分析、調(diào)試運(yùn)行下面代碼，并寫(xiě)出代碼的算法流程圖。

#include<stdio.h>

#include<string>

voiddecrypt(charcipher[]); //解密過(guò)程函數(shù)，根據(jù)輸入密鑰再一次生成密鑰流

voidmain()

{printf("**************************RC4加解密程**************************\n");

charchoose1,choose2;

do

{ints[256],t[256];chark[256]; //用戶輸入的密鑰/charplaintext[1024],ciphertext[1024];printf("輸入密鑰:\n");gets(k);for(inti=0;i<256;i++) //給字節(jié)狀態(tài)矢量和可變長(zhǎng)的密鑰數(shù)組賦值/{s[i]=i;

t[i]=k[i%strlen(k)];}intj=0;for(i=0;i<256;i++) //使用可變長(zhǎng)的密鑰數(shù)組初始化字節(jié)狀態(tài)矢量數(shù)組s/{inttemp;j=(j+s[i]+t[i])%256;temp=s[i];s[i]=s[j];s[j]=temp;}printf("\n輸入要加密的字符串:\n");gets(plaintext);intm,n,key[256],q;m=n=0;printf("\n得到密文：\n");for(i=0;i<strlen(plaintext);i++) //由字節(jié)狀態(tài)矢量數(shù)組變換生成密鑰流并對(duì)明

//文字符進(jìn)行加密{inttemp;m=(m+1)%256;n=(n+s[n])%256;temp=s[m];s[m]=s[n];s[n]=temp;q=(s[m]+s[n])%256;key[i]=s[q];ciphertext[i]=plaintext[i]^key[i];printf("%c",ciphertext[i]);}ciphertext[i]='\0';//解密printf("\n是否對(duì)上面的密文進(jìn)行解密？(y/n)\n");scanf("%c",&choose2);getchar();while(choose2=='y'||choose2=='Y'){decrypt(ciphertext); //解密過(guò)程函數(shù)choose2='n';}printf("\n是否希望繼續(xù)使用程序？(y/n)\n");scanf("%c",&choose1);getchar();}while(choose1=='y'||choose1=='Y');printf(