公鑰密碼的實(shí)現(xiàn)

1、計(jì)算機(jī)網(wǎng)絡(luò)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：公鑰密碼的實(shí)現(xiàn) 學(xué)生姓名： 專(zhuān) 業(yè)： 信息工程學(xué) 號(hào) ： 指導(dǎo)教師： 2010年 11月 16日一、公鑰密碼體制對(duì)信息發(fā)送與接收人的真實(shí)身份的驗(yàn)證、對(duì)所發(fā)出/接收信息在事后的不可抵賴(lài)以及保障數(shù)據(jù)的完整性是現(xiàn)代密碼學(xué)主題的另一方面。公開(kāi)密鑰密碼體制對(duì)這兩方面的問(wèn)題都給出了出色的解答，并正在繼續(xù)產(chǎn)生許多新的思想和方案。在公鑰體制中，加密密鑰不同于解密密鑰。人們將加密密鑰公之于眾，誰(shuí)都可以使用；而解密密鑰只有解密人自己知道。迄今為止的所有公鑰密碼體系中，RSA系統(tǒng)是最著名、使用最廣泛的一種。1976年提出公共密鑰密碼體制，其原理是加密密鑰和解密密鑰分離。這樣，一個(gè)

2、具體用戶(hù)就可以將自己設(shè)計(jì)的加密密鑰和算法公諸于眾，而只保密解密密鑰。任何人利用這個(gè)加密密鑰和算法向該用戶(hù)發(fā)送的加密信息，該用戶(hù)均可以將之還原。公共密鑰密碼的優(yōu)點(diǎn)是不需要經(jīng)安全渠道傳遞密鑰，大大簡(jiǎn)化了密鑰管理。它的算法有時(shí)也稱(chēng)為公開(kāi)密鑰算法或簡(jiǎn)稱(chēng)為公鑰算法。1978年提出公共密鑰密碼的具體實(shí)施方案，即RSA方案。1991年提出的DSA算法也是一種公共密鑰算法，在數(shù)字簽名方面有較大的應(yīng)用優(yōu)勢(shì)。二、公開(kāi)密鑰算法公開(kāi)密鑰算法是在1976年由當(dāng)時(shí)在美國(guó)斯坦福大學(xué)的迪菲（Diffie）和赫爾曼(Hellman)兩人首先發(fā)明的（論文"New Direction in Cryptography&qu

3、ot;）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同開(kāi)發(fā)的,分別取自三名數(shù)學(xué)家的名字的第一個(gè)字母來(lái)構(gòu)成的。1976年提出的公開(kāi)密鑰密碼體制思想不同于傳統(tǒng)的對(duì)稱(chēng)密鑰密碼體制，它要求密鑰成對(duì)出現(xiàn)，一個(gè)為加密密鑰(e)，另一個(gè)為解密密鑰(d)，且不可能從其中一個(gè)推導(dǎo)出另一個(gè)。自1976年以來(lái)，已經(jīng)提出了多種公開(kāi)密鑰密碼算法，其中許多是不安全的， 一些認(rèn)為是安全的算法又有許多是不實(shí)用的，它們要么是密鑰太大，要么密文擴(kuò)展十分嚴(yán)重。多數(shù)密碼算法的安全基礎(chǔ)是基于一些數(shù)學(xué)難題， 這些難題專(zhuān)家們認(rèn)為在短期內(nèi)不可能得到解

4、決。因?yàn)橐恍﹩?wèn)題(如因子分解問(wèn)題)至今已有數(shù)千年的歷史了。公鑰加密算法也稱(chēng)非對(duì)稱(chēng)密鑰算法，用兩對(duì)密鑰：一個(gè)公共密鑰和一個(gè)專(zhuān)用密鑰。用戶(hù)要保障專(zhuān)用密鑰的安全；公共密鑰則可以發(fā)布出去。公共密鑰與專(zhuān)用密鑰是有緊密關(guān)系的，用公共密鑰加密的信息只能用專(zhuān)用密鑰解密，反之亦然。由于公鑰算法不需要聯(lián)機(jī)密鑰服務(wù)器，密鑰分配協(xié)議簡(jiǎn)單，所以極大簡(jiǎn)化了密鑰管理。除加密功能外，公鑰系統(tǒng)還可以提供數(shù)字簽名。RSA公鑰加密算法中使用最廣的是RSA。RSA使用兩個(gè)密鑰，一個(gè)公共密鑰，一個(gè)專(zhuān)用密鑰。如用其中一個(gè)加密，則可用另一個(gè)解密，密鑰長(zhǎng)度從40到2048bit可變，加密時(shí)也把明文分成塊，塊的大小可變，但不能超過(guò)密鑰的長(zhǎng)度，

5、RSA算法把每一塊明文轉(zhuǎn)化為與密鑰長(zhǎng)度相同的密文塊。密鑰越長(zhǎng)，加密效果越好，但加密解密的開(kāi)銷(xiāo)也大，所以要在安全與性能之間折衷考慮，一般64位是較合適的。RSA的一個(gè)比較知名的應(yīng)用是SSL，在美國(guó)和加拿大SSL用128位RSA算法，由于出口限制，在其它地區(qū)（包括中國(guó)）通用的則是40位版本。RSA算法研制的最初理念與目標(biāo)是努力使互聯(lián)網(wǎng)安全可靠，旨在解決DES算法秘密密鑰的利用公開(kāi)信道傳輸分發(fā)的難題。而實(shí)際結(jié)果不但很好地解決了這個(gè)難題；還可利用RSA來(lái)完成對(duì)電文的數(shù)字簽名以抗對(duì)電文的否認(rèn)與抵賴(lài)；同時(shí)還可以利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對(duì)電文的非法篡改，以保護(hù)數(shù)據(jù)信息的完整性。三、密鑰的產(chǎn)生1. 選擇

6、兩個(gè)大素?cái)?shù)，p 和q ，計(jì)算出n=qp，n稱(chēng)為RSA算法的模數(shù)。p，q 必須保密，一般要求p，q為安全素?cái)?shù)，n的長(zhǎng)度大于1024bit ，這主要是因?yàn)镽SA算法的安全性依賴(lài)于因子分解大數(shù)問(wèn)題。2. 計(jì)算n的歐拉數(shù)(n)=(p-1)(q-1)(n)定義為不超過(guò)n并與n互質(zhì)的數(shù)的個(gè)數(shù)。3. 然后隨機(jī)選擇加密密鑰e，從0,(n)-1中選擇一個(gè)與(n)互質(zhì)的數(shù)e作為公開(kāi)的加密指數(shù)。4. 最后，利用Euclid 算法計(jì)算解密密鑰d, 滿(mǎn)足de1(mod (n)。其中n和d也要互質(zhì)。數(shù)e和n是公鑰，d是私鑰。兩個(gè)素?cái)?shù)p和q不再需要，應(yīng)該丟棄，不要讓任何人知道。5.得到所需要公開(kāi)密鑰和秘密密鑰：公開(kāi)密鑰（即

7、加密密鑰） PK=（e，n）秘密密鑰（即解密密鑰） SK=（d，n）四、RSA算法RSA算法非常簡(jiǎn)單，概述如下：找兩素?cái)?shù)p和q取n=p*q取t=(p-1)*(q-1)取任何一個(gè)數(shù)e,要求滿(mǎn)足e<t并且e與t互素（就是最大公因數(shù)為1）取d*e%t=1這樣最終得到三個(gè)數(shù)： n  d  e設(shè)消息為數(shù)M (M <n)設(shè)c=(M*d)%n就得到了加密后的消息c 設(shè)m=(c*e)%n則 m = M，從而完成對(duì)c的解密。注：*表示次方,上面兩式中的d和e可以互換。在對(duì)稱(chēng)加密中：n d兩個(gè)數(shù)構(gòu)成公鑰，可以告訴別人；n e兩個(gè)數(shù)構(gòu)成私鑰，e自己保留，不讓任何人知道。給別人發(fā)送的信

8、息使用e加密，只要?jiǎng)e人能用d解開(kāi)就證明信息是由你發(fā)送的，構(gòu)成了簽名機(jī)制。別人給你發(fā)送信息時(shí)使用d加密，這樣只有擁有e的你能夠?qū)ζ浣饷?。rsa的安全性在于對(duì)于一個(gè)大數(shù)n，沒(méi)有有效的方法能夠?qū)⑵浞纸鈴亩谝阎猲 d的情況下無(wú)法獲得e；同樣在已知n e的情況下無(wú)法求得d?；蛘哒f(shuō)，rsa的安全性在于對(duì)于一個(gè)大數(shù)n,沒(méi)有有效的辦法將其分解成p和q。五、設(shè)計(jì)分析 好我們所要達(dá)到的目標(biāo)是要確保除了在保密條件下，密鑰永不以明文的形式出現(xiàn)。假定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是多個(gè)終端連到一臺(tái)主機(jī)上，然后主機(jī)在與其他主機(jī)相連。如下圖所示：       

9、0;               KN1                 KN3                

10、0;                          KN4                       K

11、N2                                                 

12、0;    KN5                  為專(zhuān)用密碼裝置     一般情況下，當(dāng)用戶(hù)要在某一個(gè)通信信道上進(jìn)行通信時(shí)，要用初級(jí)密鑰KS對(duì)所要傳輸?shù)臄?shù)據(jù)進(jìn)行加密，并且連同KS一起傳送給接收方。如果KS被敵方所截獲，這不能保證數(shù)據(jù)的保密性。于是可以用該通道上的二級(jí)密鑰對(duì)KS進(jìn)行加密后再傳送，便可以保證數(shù)據(jù)的保密性。但是，二

13、級(jí)密鑰不能以明文的方式出現(xiàn)，否則同樣會(huì)被敵方所利用。     為了很好的解決這些問(wèn)題，我們對(duì)密鑰進(jìn)行如下分配：     1）終端   每一個(gè)終端配置唯一的一個(gè)二級(jí)通信密鑰KN(稱(chēng)其為終端的主要密鑰（KMT）),并由密鑰安裝人員裝入終端的專(zhuān)用密碼裝置，終端接收用戶(hù)自己提供的初級(jí)密碼。     2）主機(jī)   如果一個(gè)接有m個(gè)終端的主機(jī)與其余n個(gè)主機(jī)相連，那么它需要2n+m個(gè)二級(jí)密鑰，其中2n

14、個(gè)二級(jí)密鑰對(duì)其余n個(gè)主機(jī)的兩個(gè)通信方向進(jìn)行隔離保護(hù)，剩下的m個(gè)對(duì)終端通信進(jìn)行隔離保護(hù)。實(shí)行加密隔離的好處是即使某一密鑰被泄露二不會(huì)暴露其它密鑰，是損失降至最小。     為了對(duì)初級(jí)密鑰和二級(jí)密鑰的兩個(gè)傳輸方向之間進(jìn)行加密隔離，在主機(jī)中采用三個(gè)主機(jī)主密鑰：KM0,KM1,KM2。KM0用來(lái)加密保護(hù)主機(jī)中的初級(jí)密鑰，KM1和KM2分別用來(lái)加密通信的兩個(gè)方向上的二級(jí)密鑰。   其中KM1和KM2可以由KM0導(dǎo)出。例如，對(duì)KM0的某些位取反分別產(chǎn)生KM1和KM2，這樣在主機(jī)中只需將KM0以明文的形式保存到專(zhuān)用密碼裝置中。3

15、 密鑰數(shù)據(jù)庫(kù)（CKDB）CKDB用以存貯備足記住密鑰加密的二級(jí)密鑰。一種可行的CKDB的文件記錄格式如下：密鑰名通常使用密鑰的資源名命名，密鑰1字段放置KM1加密的密鑰，密鑰2字段放置KM2加密的密鑰，類(lèi)型1表示本主機(jī)上的終端上的主密鑰，類(lèi)型2表示與其他主機(jī)通信的二級(jí)密鑰。舉例如下：本地終端主密鑰：與其他主機(jī)通信的二級(jí)密鑰其中，E(K,M)表示用密鑰K加密信息M的結(jié)果。4.專(zhuān)用密碼裝置專(zhuān)用密碼裝置是一種專(zhuān)用的具有高安全性和可靠性的保密工具，它用硬件實(shí)現(xiàn)，由一個(gè)強(qiáng)的密碼算法、密鑰存貯器、數(shù)據(jù)存貯器以及控制器和接口電路組成，如下圖所示：    &#

16、160;         操作碼                 數(shù)據(jù)          輸出主密鑰采取物理的和邏輯的存取控制方法，確保只有授權(quán)的合法操作才能對(duì)專(zhuān)用密碼裝置進(jìn)行操作。專(zhuān)用密碼裝置的安全關(guān)系到整個(gè)密碼系統(tǒng)的安全，必須采取各種技

17、術(shù)的和行政的措施予以確保。專(zhuān)用的密碼裝置的基本功能是存貯密鑰、加解密數(shù)據(jù)和密鑰變換。用于終端和主機(jī)的專(zhuān)鑰寄存器。d.ENC:M->E(K,M)    加密數(shù)據(jù)此命令用工作密鑰寄存器中的初級(jí)密鑰K加密有數(shù)據(jù)輸入端輸入的數(shù)據(jù)，并將密文輸出。e.DEC:E(K,M)?M     解密數(shù)據(jù)此命令用工作密鑰寄存器中的初級(jí)密鑰K解密由數(shù)據(jù)輸入端輸入的密文，并將明文輸出。2） 主機(jī)專(zhuān)用密碼裝置的操作      主機(jī)專(zhuān)用密碼裝置的操作比終端的復(fù)雜

18、a.ECPH:E(KM0,K),M?E(K,M)     加密數(shù)據(jù)此操作的功能是，輸入初級(jí)密鑰的密文形式E(KM0,K)，解密出K,將K存入工作密鑰寄存器，再用K加密輸入的數(shù)據(jù)M，輸出密文 E(K,M).b.DCPH:E(KM0,K),E(K,M)?M    解密數(shù)據(jù)此操作的功能是，輸入E(KM0,K)，解密出K，將K存入工作密鑰寄存器，再用K解密輸入的密文E(K,M),輸出明文M.c.SMK:KM0      置入主密鑰此操作的功能是

19、由密鑰安裝人員手工置入主密鑰KM0.注意：此操作僅在特許狀態(tài)下才允許進(jìn)行，而且無(wú)逆操作。d.EMK:K?E(KM0,K)        加密初級(jí)密鑰此操作的功能使用主密鑰KM0加密初級(jí)密鑰K。本操作支持用戶(hù)自己提供的初級(jí)密鑰，而且無(wú)逆操作。e.RFMK:E(KM1,KN),E(KM0,K)?E(KN,K)     密鑰變換此操作的功能是把用KM0加密的初級(jí)密鑰K，轉(zhuǎn)換成用二級(jí)密鑰KN加密的形式。執(zhí)行過(guò)程為，輸入E(KM1,KN),用KM1解密得到KN，并將KN存入工

20、作密鑰寄存器，其中的KM1由KM0產(chǎn)生。再輸入E(KM0,K),用KM0解密得到K,并將K存入數(shù)據(jù)寄存器。最后用KN加密K,輸出E(KN,K).f.RTMK:E(KM2,KN),E(EN,K)?E(KM0,K)      密鑰變換此操作的功能是，把用KN加密的初級(jí)密鑰轉(zhuǎn)換成為用KM0加密的形式。此操作的執(zhí)行過(guò)程與RFMK類(lèi)似。1） 同一主機(jī)上的兩個(gè)終端的通信2） 不同主機(jī)上的兩個(gè)終端的通信下：a) A通過(guò)Ti1向主機(jī)I申請(qǐng)與B通信。b) 主機(jī)I響應(yīng)后，調(diào)用密鑰管理程序產(chǎn)生一個(gè)隨機(jī)數(shù)RN，并以此作

21、為受KM0I保密的會(huì)話(huà)密鑰，RN=E(KM0i,KS).調(diào)用RFMK操作將RN轉(zhuǎn)變?yōu)橛蒏MTi1加密KS的形式。      RFMK:E(KM1I,KMTi1),RN?E(KMTi1,KS)并將E(KMTi1,KS)發(fā)給A.調(diào)用RFMK操作將RN轉(zhuǎn)變?yōu)橛蒏nij加密KS的形式。  RFMK:E(KM1I,Knij),RN?E(Knij,KS)并將E(KNij,KS)發(fā)給主機(jī)j.c) 主機(jī)j收到E(KNij,KS)后，調(diào)用RTMK操作將E(KNij,KS)轉(zhuǎn)變?yōu)镋(KM0j,KS):  

22、      RTMK:E(KM2j,Knij), E(KNij,KS)?E(KM0j,KS)     調(diào)用RFMK操作將E(KM0j,KS)轉(zhuǎn)變?yōu)镋(KMTj2,KS):        RFMK:E(KM1j,KMTj2), E(KM0j,KS)?E(KMj2,KS)并將E(KMj2,KS)發(fā)送給Tj2的B.d) A和B已共享會(huì)話(huà)密鑰KS，他們可進(jìn)行保密通信。于是，A利用KS加

23、密會(huì)話(huà)數(shù)據(jù)M并發(fā)給B               ENC:M?E(KS,M)e) B收到后進(jìn)行解密：DEC:E(KS,M)?M六、公鑰密碼的實(shí)現(xiàn)（一）找兩個(gè)素?cái)?shù)：p=47q=59這樣n=p*q=2773t=(p-1)*(q-1)=2668取e=63，滿(mǎn)足e<t并且e和t互素用perl簡(jiǎn)單窮舉可以獲得滿(mǎn)主 e*d%t =1的數(shù)d：C:Temp>perl -e "foreach $i (1.9999) print($i

24、),last if $i*63%2668=1 "847即d847最終我們獲得關(guān)鍵的n=2773d=847e=63取消息M=244我們看看加密：c=M*d%n = 244*847%2773用perl的大數(shù)計(jì)算來(lái)算一下：C:Temp>perl -Mbigint -e "print 244*847%2773"465即用d對(duì)M加密后獲得加密信息c465解密：我們可以用e來(lái)對(duì)加密后的c進(jìn)行解密，還原M：m=c*e%n=465*63%2773 ：C:Temp>perl -Mbigint -e "print 465*63%2773"244即用e對(duì)

25、c解密后獲得m=244 , 該值和原始信息M相等。（二）、字符串加密把上面的過(guò)程集成一下我們就能實(shí)現(xiàn)一個(gè)對(duì)字符串加密解密的示例了。每次取字符串中的一個(gè)字符的ascii值作為M進(jìn)行計(jì)算，其輸出為加密后16進(jìn)制的數(shù)的字符串形式，按3字節(jié)表示，如01F代碼如下：#!/usr/bin/perl -w#RSA 計(jì)算過(guò)程學(xué)習(xí)程序編寫(xiě)的測(cè)試程序#watercloud 2003-8-12#use strict;use Math:BigInt;my %RSA_CORE = (n=>2773,e=>63,d=>847); #p=47,q=59my $N=new Math:BigInt($RSA_

26、COREn);my $E=new Math:BigInt($RSA_COREe);my $D=new Math:BigInt($RSA_COREd);print "N=$N D=$D E=$En"sub RSA_ENCRYPT     my $r_mess = shift _;    my ($c,$i,$M,$C,$cmess);    for($i=0;$i < length($r_mess);$i+)       

27、     $c=ord(substr($r_mess,$i,1);        $M=Math:BigInt->new($c);        $C=$M->copy(); $C->bmodpow($D,$N);        $c=sprintf "%03X",$C;   &#

28、160;    $cmess.=$c;        return $cmess;sub RSA_DECRYPT     my $r_mess = shift _;    my ($c,$i,$M,$C,$dmess);    for($i=0;$i < length($r_mess);$i+=3)            $c=substr($r_mess,$i,3);        $c=hex($c);        $M=Math:BigInt->n