安全聊天系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 第31頁 共32頁安全聊天系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)學(xué)生姓名：xxx 指導(dǎo)老師：xxx摘 要 隨著計(jì)算機(jī)的不斷普及和互聯(lián)網(wǎng)技術(shù)在全球領(lǐng)域的高速發(fā)展。越來越多的人使用到了聊天程序。聊天程序給人們帶來通信便利的同時(shí)也存在著一些安全隱患，傳統(tǒng)的聊天程序以明文方式傳送聊天內(nèi)容，這樣就給一些用心不良的人大開方便之門。本系統(tǒng)正是基于以上原因而設(shè)計(jì)的加密聊天程序。聊天程序采用服務(wù)器/客戶端模式。在Linux環(huán)境下采用socket套接口編程，服務(wù)器程序以創(chuàng)建線程池的方式為每一個(gè)客戶服務(wù)。聊天內(nèi)容由服務(wù)器轉(zhuǎn)發(fā)。在聊天程序中加入了對(duì)稱加密算法DES和非對(duì)稱加密算法RSA。其基本實(shí)現(xiàn)是由服務(wù)器端生成RSA的公鑰和私鑰，由客戶端生成DES對(duì)稱密鑰，服務(wù)器端傳送公鑰至客戶端加密DES密鑰之后回傳服務(wù)器，服務(wù)器再用本地的私鑰解密獲得DES密鑰。此后雙方的通信由DES密鑰加密后傳送，這樣既能高效的加密明文又能在信道上安全的傳送密鑰使得密鑰間的共享成為現(xiàn)實(shí)。關(guān)鍵詞 對(duì)稱加密算法；非對(duì)稱加密算法；聊天系統(tǒng) The Design and implementation of safe chat system Abstract Along with Computer becoming more and more popular and Internet technology developing rapidly, a lot of People began to use the IM(chat program). Chat program brings people more convenience, but at the same time, security problem existed. The traditional chat program sends the message by plain text, which open the door for the bad man. This encrypted chat system is right based on the point. The system is in C/S architecture using socket based on Linux. The server program serves each client in the way of establishing thread and is responsible to transfer message. The DES algorithm and RSA algorithm are used to encrypt in this program. The basic principle is that the server generates RSA public key and private key and client generates DES symmetrical secret key. Firstly, the server sends the public key to client, and then client sends it back after encrypting DES secret key. Secondly, the Server uses local private key to decode to obtain the DES private key. After then, the message is sent after encrypted by DES secret key. So the plain text can be encrypted effectively and sent in channel in security.Key words symmetry encrypting program; unsymmetrical encrypting program;chat system1 引言1.1 課題背景自從TCP/IP協(xié)議族成為計(jì)算機(jī)通信的主要網(wǎng)絡(luò)協(xié)議，基于該協(xié)議族開發(fā)的網(wǎng)絡(luò)應(yīng)用程序數(shù)不勝數(shù)。聊天程序便是其中之一。聊天程序使人們可以通過互聯(lián)網(wǎng)及時(shí)傳送消息，讓遠(yuǎn)在千里之外的人們暢所欲言。傳統(tǒng)的聊天程序在給人們帶來方便的同時(shí)也逐漸暴露出一些安全隱患。前不久網(wǎng)上登出了這樣一則新聞：上海某銀行的白領(lǐng)麗人，因?yàn)榱奶斐绦蚴鼙O(jiān)控被同事知道了個(gè)人隱私，被迫辭去了月薪三萬余元的工作。于是聊天程序的安全性受到了人們的廣泛關(guān)注。1.2 國內(nèi)外研究現(xiàn)狀從國內(nèi)外對(duì)聊天程序的加密情況看，大多數(shù)處理方式是在現(xiàn)有的聊天程序基礎(chǔ)之上添加相應(yīng)的加密插件來實(shí)現(xiàn)加密。比較典型的例子是Linux平臺(tái)下的多集成聊天程序Gaim，其中集成了ICQ、MSN、QQ等現(xiàn)今主流國內(nèi)外聊天程序。普遍的聊天程序沒有經(jīng)過加密而直接傳輸聊天明文。Gaim通過添加插件程序?qū)ξ醇用艿牧奶斐绦蜻M(jìn)行加密傳輸，通信雙方需要只要同時(shí)安裝加密插件就可以順利的對(duì)聊天內(nèi)容進(jìn)行加密解密。這其中存在一個(gè)現(xiàn)而易見的問題：要是一方加入了加密插件而另一方卻沒有相應(yīng)的解密程序顯然雙方不能正確通信。1.3 本課題研究的意義聊天程序是否加密關(guān)系著用戶的切身利用。為了保衛(wèi)公民隱私權(quán)不受到網(wǎng)絡(luò)黑客的不法侵犯，開發(fā)加密傳輸信息的聊天程序有著重大意義。聊天程序的加密特性對(duì)用戶應(yīng)該是透明的。正如前面分析，如果以安裝插件的方式加密聊天程序很可能造成通信雙方加密不一致的情況。因此將加密算法內(nèi)嵌入聊天程序可以保證通信雙方均能正常通信。傳統(tǒng)的對(duì)稱加密算法如DES雖然可以快速的加密和解密明文，然而其密鑰難以分配和管理。如果讓通信雙方相互約定密鑰顯然是不合適的，因此最好的方式是由一方產(chǎn)生密鑰然后傳送給另一方。基于公鑰的非對(duì)稱加密體制的引入正是用于解決對(duì)稱加密算法在密鑰管理上的不足，但是非對(duì)稱加密算法如RSA存在運(yùn)算強(qiáng)度過大、費(fèi)時(shí)較長等問題。如果直接用于加密聊天程序，其生成密鑰和加密解密所需時(shí)間是人們?cè)谕ㄐ胚^程中所不能容忍的，采取將兩種加密算法相結(jié)合的方式可以很好的解決以上問題，從而達(dá)到安全快速的加密數(shù)據(jù)。2所采用技術(shù)的先進(jìn)性分析2.1 DES算法DES是Data Encryption Standard（數(shù)據(jù)加密標(biāo)準(zhǔn)）的縮寫。它是由IBM公司研制的一種加密算法，美國國家標(biāo)準(zhǔn)局于1977年公布把它作為非機(jī)要部門使用的數(shù)據(jù)加密標(biāo)準(zhǔn)，二十年來，它一直活躍在國際保密通信的舞臺(tái)上，扮演了十分重要的角色。DES是一個(gè)分組加密算法，它以64位為分組對(duì)數(shù)據(jù)加密。同時(shí)DES也是一個(gè)對(duì)稱算法：加密和解密用的是同一個(gè)算法。它的密鑰長度是56位（因?yàn)槊總€(gè)第8位都用作奇偶校驗(yàn)），密鑰也可以是任意的56位數(shù)，而且可以任意時(shí)候改變。其中有極少量的數(shù)被認(rèn)為是弱密鑰，但是很容易避開它們。所以保密性依賴于密鑰。2.2 RSA算法1978年，美國麻省理工學(xué)院（MIT）的研究小組成員Ronald L Rivest、Adi Shamir、 Leonard Adleman提出了一種基于公開密鑰密碼體制的優(yōu)秀加密算法RSA算法。RSA的取名就是來自這三位發(fā)明者姓氏的第一個(gè)字母。該算法以其較高的保密強(qiáng)度逐漸成為一種廣為接受的公鑰密碼體制算法。RSA算法是一種分組密碼體制算法，它的保密強(qiáng)度是建立在具有大素?cái)?shù)因子的合數(shù)，其因子分解NP（Nondeterministic Polynomial）完全問題這一數(shù)學(xué)難題的基礎(chǔ)上的，因此RSA算法具有很強(qiáng)的保密性。RSA算法研制的最初目標(biāo)是解決DES算法秘密密鑰利用公開信道傳輸分發(fā)困難的難題，而實(shí)際結(jié)果不但很好地解決了這個(gè)難題；還可利用RSA來完成對(duì)消息的數(shù)字簽名以防對(duì)消息的抵賴；同時(shí)還可以利用數(shù)字簽名發(fā)現(xiàn)攻擊者對(duì)消息的非法篡改，以保護(hù)數(shù)據(jù)信息的完整性。RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA得到了世界上的最廣泛的應(yīng)用，并于1992年ISO國際標(biāo)準(zhǔn)化組織在其頒發(fā)的國際標(biāo)準(zhǔn)X.509中，將RSA算法正式納入國際標(biāo)準(zhǔn)。2.3 線程池在傳統(tǒng)的UNIX模型中，當(dāng)一個(gè)進(jìn)程需要另一個(gè)實(shí)體來完成某事時(shí)，它就fork一個(gè)子進(jìn)程并讓子進(jìn)程去執(zhí)行處理。Unix上的大多數(shù)網(wǎng)絡(luò)服務(wù)器程序就是這么編寫的，父進(jìn)程accept一個(gè)連接，fork一個(gè)子進(jìn)程，該子進(jìn)程處理與該連接對(duì)端的客戶之間的通信。盡管這種范式多少年來一直良好地服務(wù)著，fork調(diào)用卻存在一些問題：1 fork是昂貴的。fork要把父進(jìn)程的內(nèi)存映象拷貝到子進(jìn)程，并在子進(jìn)程中復(fù)制所有描述字，如此等等。2 fork返回之后父進(jìn)程之間信息的傳遞需要進(jìn)程間通信（IPC）機(jī)制。調(diào)用fork之前父進(jìn)程向尚存在的子進(jìn)程傳遞信息相當(dāng)容易。因?yàn)樽舆M(jìn)程將從父進(jìn)程數(shù)據(jù)空間及所有描述字的一個(gè)拷貝開始運(yùn)行。然而從子進(jìn)程往父進(jìn)程返回信息卻比較費(fèi)力。線程有助于解決這兩個(gè)問題。線程有時(shí)稱為輕權(quán)進(jìn)程（lightweight process），因?yàn)榫€程比進(jìn)程“權(quán)重輕些”。也就是說，線程的創(chuàng)建可能比進(jìn)程的創(chuàng)建快10100倍。線程池是指在服務(wù)器啟動(dòng)階段預(yù)先創(chuàng)建一系列線程阻塞于accept調(diào)用，每個(gè)客戶由當(dāng)前可用線程池中的某個(gè)（閑置）線程處理。這種處理方式比通常的客戶連接到來時(shí)臨時(shí)創(chuàng)建線程為其服務(wù)要快得多?？梢垣@得很好的性能加速。 3系統(tǒng)需求分析3.1聊天程序功能分析1 注冊(cè)功能通常聊天程序需要用戶名和密碼才能使用，所以需要實(shí)現(xiàn)web注冊(cè)功能，這樣用戶可以很方便的通過web網(wǎng)站注冊(cè)自己的用戶名并取得密碼，還可以在服務(wù)器上存儲(chǔ)個(gè)人相關(guān)信息以便他人查看。2 登陸功能用戶在聊天之前需要輸入用戶名和密碼進(jìn)行登陸以便獲取自身相關(guān)信息和好友相關(guān)信息，故登陸過程中服務(wù)器需對(duì)用戶名和密碼進(jìn)行必要的核對(duì)。3 聊天功能這是聊天程序的主要功能。用戶之間的相互通信必須及時(shí)快速的由服務(wù)器轉(zhuǎn)發(fā)。3.2 加密算法由于是加密聊天程序，故對(duì)聊天明文的加密算法應(yīng)選取加密速度相對(duì)較快的對(duì)稱加密算法（如：DES），又由于DES的加密密鑰是不能公開的秘密密鑰，故對(duì)DES的密鑰應(yīng)加密傳送，所以應(yīng)采用非對(duì)稱的公鑰加密算法（如RSA）用以分發(fā)DES密鑰。DES加密算法：作為對(duì)稱加密算法中的DES加密算法由于其加密過程是固定不變的，故應(yīng)考慮其密鑰的生成。由于弱密鑰存在的可能性，還應(yīng)該考慮如何避免生成弱密鑰。因?yàn)椴罘址治龇ǖ奶岢隹梢钥焖俚钠平馍儆?6輪迭代的DES算法，故應(yīng)保證其迭代次數(shù)至少為16輪。RSA加密算法：由于RSA是基于大素?cái)?shù)因子分解這一數(shù)學(xué)難題提出的，故RSA中公鑰和私鑰的產(chǎn)生應(yīng)重點(diǎn)考慮。又由于RSA的運(yùn)算強(qiáng)度較大，故還應(yīng)考慮如何加速其運(yùn)算速度。4 系統(tǒng)總體設(shè)計(jì)和模塊劃分4.1 系統(tǒng)總體設(shè)計(jì)圖4.1系統(tǒng)設(shè)計(jì)如圖4.1所示，本系統(tǒng)采用C/S模式。1 用戶通過web應(yīng)用程序注冊(cè)帳號(hào)，然后用注冊(cè)的帳號(hào)登陸聊天程序服務(wù)器。2 客戶端產(chǎn)生生成DES密鑰，服務(wù)器端在啟動(dòng)時(shí)初始化產(chǎn)生RSA公鑰和私鑰。當(dāng)客戶端向服務(wù)器發(fā)起連接時(shí)，服務(wù)器送出RSA公鑰，客戶端用取得的公鑰加密產(chǎn)生的DES私鑰回傳服務(wù)器。3 最后服務(wù)器與客戶端雙方的通信均由DES加密算法加密通信明文。4.2 模塊劃分4.2.1 DES算法模塊1 加密算法3個(gè)主要步驟第一步，初始置換IP圖4.2 初始置換表IP圖4.2為初始置換表IP,64bit輸入明文經(jīng)過該表完成初始置換。第二步，16輪迭代圖4.3 16輪迭代圖4.3為DES16輪迭代，將經(jīng)過初始置換的數(shù)據(jù)分成Li和Ri兩部分。將Ri直接交換為Li+1，Li與Ri經(jīng)過f函數(shù)處理后的數(shù)據(jù)相異或得Ri+1，最后一輪不做交換。第三步，逆置換圖4.4 逆置換表（IP-1）圖4.4為逆置換表(IP-1)，經(jīng)過16輪迭代后通過該表置換得到輸出的密文。2 子密鑰的產(chǎn)生圖4.5 生成子密鑰圖4.5為子密鑰生成過程，將64bit初始密鑰經(jīng)過PC-1表置換為56bit輸入，分為Ci, Di兩組分別進(jìn)行LS循環(huán)左移，再經(jīng)過PC-2表壓縮為48bit子密鑰。如此循環(huán)16輪生成16組子密鑰。4.2.2 RSA算法模塊1 大數(shù)的運(yùn)算加法運(yùn)算：設(shè)定相應(yīng)的進(jìn)位變量c，按位相加，如ri = ai + bi + c，當(dāng)ai + bi + c > m (m為權(quán)值)，c送1，ri = (ai + bi + c) mod m， 否則c送0。減法運(yùn)算：設(shè)定相應(yīng)的借位變量c，按位相減，如ri = ai bi + c，當(dāng)ai < bi時(shí)，c送m (m為權(quán)值)，還要將ai高一位減1，如過高位連續(xù)為0則依次置m 1，一直到第一個(gè)非0位并將其減1，否則c送0。乘法運(yùn)算：設(shè)定相應(yīng)的進(jìn)位變量c，和一個(gè)取當(dāng)前結(jié)果位值變量d，雙重循環(huán)。外層循環(huán)依次取運(yùn)算數(shù)A的相應(yīng)位，內(nèi)層循環(huán)依次取B的相應(yīng)位。r(i + j) = d + ai * bj + c，當(dāng)d + ai * bi + c > m (m位權(quán)值)，c送ri/m (m為權(quán)值)，d為從對(duì)應(yīng)的內(nèi)外循環(huán)位之和(i + j)對(duì)應(yīng)的結(jié)果位上取得的值。r(i + j)暫時(shí)存入對(duì)應(yīng)的結(jié)果位。除法運(yùn)算：假設(shè)A為被除數(shù)，B為除數(shù)。當(dāng)A > B，將B擴(kuò)大到A相同位數(shù)，循環(huán)做A = A Bk (擴(kuò)充后的B)，商位qi = qi + 1，最后A為余數(shù)。取余運(yùn)算：依除法運(yùn)算輸出余數(shù)A。乘方運(yùn)算：與乘法運(yùn)算一樣設(shè)有進(jìn)位變量c和取當(dāng)前結(jié)果位值變量d。依然分內(nèi)外兩層循環(huán)。外層循環(huán)中d = r (2 * i)，r(2 * i) = d + ai * ai，在此僅計(jì)算相同位ai的乘積存入結(jié)果位r(2 * i)中。內(nèi)層循環(huán)d = r (i + j)，r(i + j) = d + 2 * ai * aj + c，這里由于乘數(shù)A和被乘數(shù)B相等，故可以采用2 * ai * aj，這種方式提前運(yùn)算對(duì)應(yīng)位?？梢钥闯鲞@種預(yù)處理方式加快了運(yùn)算速度。模冪運(yùn)算：將模冪運(yùn)算轉(zhuǎn)化為乘模運(yùn)算。定理：(a * b) mod n = (a mod n) * (b mod n) mod n。計(jì)算Am mod n：令c = 1，如果m = m % 2 = 0 循環(huán)計(jì)算 A = (A * A) mod n 否則 m = m 1，c = (A * c) mod n。最后輸出c。2 選取P，Q先以生成隨機(jī)數(shù)的方式生成隨機(jī)奇數(shù)A、B。再讓A、B依次通過Miller-Rabin素性測試。Miller-Rabin素性測試：先計(jì)算出m、j，使得n-1=m*2j，其中m是正奇數(shù)，j是非負(fù)整數(shù)，隨機(jī)取一個(gè)b，2<=b，計(jì)算v=bm mod n，如果v=1，通過測試，返回。令i=1，循環(huán)以后步驟，如果v=n-1，通過測試，返回。如果i=j，非素?cái)?shù)，結(jié)束。v=v2 mod n，i=i+1。3 歐幾里德算法求a，b最大公因數(shù)和逆元定理：gcd (a, b) = gcd (b, a mod b) (設(shè)a > b)r = a mod b, a = b，b = r 循環(huán)以上三步直到r = 0， 則a為所求最小公因數(shù)。r = a mod b => x * a + y * b = r。 x稱為a的逆元。在每步循環(huán)過程中將前一步中的r代入下一步中合并后可求得逆元x。4.2.3 DES和RSA安全性討論1 弱密鑰所謂的弱密鑰是指在所有可能的密鑰中，有某幾個(gè)特別的密鑰，會(huì)降低DES的安全性，所以使用者一定要避免使用這幾個(gè)弱密鑰。而弱密鑰產(chǎn)生的原因是由于子密鑰產(chǎn)生過程的設(shè)計(jì)不當(dāng)所導(dǎo)致的。由子密鑰產(chǎn)生的過程來看，假設(shè)有某個(gè)初始密鑰經(jīng)過密鑰初始置換表置換，使得寄存器C0與D0的內(nèi)容成為全是“0”或全是“1”的數(shù)據(jù)。如此一來，不管以后的每一輪中之循環(huán)左移函數(shù)是如何地變化，Ci與Di的內(nèi)容并不會(huì)有所改變的。換句話說，這樣的初始密鑰，將會(huì)產(chǎn)生16個(gè)一摸一樣的子密鑰。如此一來將大大地降低DES的安全性。弱密鑰有另外一個(gè)特性對(duì)弱密鑰而言，其加密與解密的過程是完全一樣的。我們知道DES的加密與解密過程中，唯一的不同在于子密鑰的使用順序是相反的。然而對(duì)弱密鑰而言，因?yàn)槠渌苌?6個(gè)子密鑰是完全相同的，故子密鑰之間也就毫無順序之分了。2 半弱密鑰除了上述的弱密鑰之外，還有另外一種稱之為半弱密鑰的初始密鑰。其特性是此類初始密鑰所產(chǎn)生的子密鑰，只有兩種可能。而每一種可能的子密鑰，剛好各出現(xiàn)8次。假設(shè)現(xiàn)在有兩個(gè)位串：A01010101，與B10101010，那么無論如何對(duì)A做循環(huán)左移動(dòng)作，其結(jié)果不是A就是B。當(dāng)然對(duì)B做循環(huán)左移動(dòng)作也會(huì)得到一樣的結(jié)果。如果對(duì)某個(gè)弱密鑰而言，它滿足以下兩個(gè)條件，那么它就屬于以上所謂的半弱密鑰了。（1）子密鑰排列中的C（或D）寄存器只含有0101，0101或1010，,1010這兩種形式的數(shù)據(jù)。（2）另一個(gè)寄存器D（或C）含有0000，0000，1111，1111，0101，0101或1010，1010任何一種形式的數(shù)據(jù)。3 差分分析法差分分析法基本上是屬于選擇明文攻擊法。但在某些特定的情形下，也可用于已知明文攻擊。這個(gè)方法簡單地說，就是分析特殊明文配對(duì)（Plaintext Pair）的差值相對(duì)應(yīng)的密文配對(duì)（Ciphertext Pair）的差值所產(chǎn)生的影響。這里所謂的差值是指兩個(gè)明文（或密文）之間做異或（XOR）所得到的值。這個(gè)做法的主要概念在于差值的運(yùn)算會(huì)使得DES變得簡單許多。我們知道DES可看做一部非常復(fù)雜的非線性機(jī)器，即使知道某一明文對(duì)應(yīng)的密文，若無法得知密鑰，也很難去推導(dǎo)出這一部機(jī)內(nèi)部的數(shù)據(jù)流。當(dāng)在差值的概念下，就有機(jī)可趁了。對(duì)DES中的某個(gè)差值而言，最多的可以有2的64次方個(gè)明文（或密文）配對(duì)與之對(duì)應(yīng)。差分密碼分析法所在乎的是差值本身，而非其所對(duì)應(yīng)的明文（或密文）配對(duì)。而某些特殊的差分密碼分析法就是選取許多擁有相同特征值的明文配對(duì)，加密后得到相對(duì)應(yīng)的密文配對(duì)，再借著特征值與這些密文配對(duì)推導(dǎo)出一些可能的密鑰，并附與可能的概率，最后再選出最有可能者。B. RSA安全性討論不可使用公共的模N在某些情況下，我們假設(shè)有一密鑰產(chǎn)生中心（Key Generation Center, KGC）,利用RSA系統(tǒng)產(chǎn)生一公共模N = pq。此中心接著產(chǎn)生許多對(duì)的加密與解密密鑰ei，di，并將解密密鑰di秘密傳送給使用者i，且公布ei為使用者i的公開密鑰。此系統(tǒng)的優(yōu)點(diǎn)為密鑰管理非常簡單，因?yàn)橄到y(tǒng)中使用公共的模（N），不會(huì)有Reblocking問題產(chǎn)生，且可節(jié)省公開密鑰的存儲(chǔ)空間。不過，RSA系統(tǒng)使用公共的模，卻可能招致下列三個(gè)主要的問題，使得此系統(tǒng)并不安全。1 若相同的明文m分送給兩個(gè)不同的使用者，則此系統(tǒng)可能變得不安全設(shè)預(yù)將明文m加密后分送給使用者i及j，則其密文分別為Ci = mei mod N及Cj = mej mod N。若使用者i與j的公開密鑰ei與ej互素，則由歐幾里德算法可求得兩整數(shù)r及s使得rei + sej = 1。很明顯地，r或s一定有一個(gè)為負(fù)數(shù)，即r = -|r|。若Ci與N互素（若不是的互，則我們可利用最大公因子方法求出p或q，盡而分解N），則Ci的乘法逆元Ci-1存在，并可被輕易求出。由下式我們可以容易求出明文m：(Ci-1)|r|(Cj)s = (mei)-|r|(mej)s = m(rej + sej) = m mod N因此，若有相同的明文分送給兩個(gè)不同的使用者，且此二使用者的公開密鑰為互素，則此系統(tǒng)并不安全。2 擁有一對(duì)的加密/解密密鑰就能因子分解NDelaurentis提出一種概率算法，使得擁有一對(duì)加/解密密鑰的人就能因子分解N。其基本概念為找出一整數(shù)b使得(1) b2 = 1 mod N(2) b != +- 1 mod N(3) 1 < b < N由基本數(shù)論知，若N = pq，滿足上述條件的b共有兩個(gè)。若能找出任一個(gè)，則我們即可將N因子分解。因?yàn)閎2 -1 = 0 mod N， 則(b + 1)(b - 1) = 0 mod N， 所以(b + 1)(b -1) = kN = kqp， 其中k為整數(shù)。由于1 < b < N，所以不等式0 < b 1 < b + 1 < N = qp成立。因此p及q不能同時(shí)整除b 1或b + 1，也即b 1與N必有一公因子p或q。利用歐幾里德算法，求GCD(b 1, N)，即可求得p或q，因此可以將N因子分解。3 擁有一對(duì)加/解密密鑰能在不必分解N情況下，求出另一對(duì)加解密密鑰。設(shè)已擁有一對(duì)加/解密密鑰e及d，則已給出一加密密鑰e1(GCD(e1, f(N) = 1)，即可在不需因子分解N情況下，求出其解密密鑰d1，滿足e1d1 = 1 mod f(N)。（1） 利用歐幾里德算法求出e1與ed 1的最大公因子g。（2） 求出(ed - 1) / g = f。（3） 利用歐幾里德算法，求出兩整數(shù)r1及d1，使得r1f + d1e1 = 1。由于g整除ed 1，因此f必為整數(shù)，且f必為f(N)的整數(shù)倍，這是由于f(N)整除ed 1，且g與f(N)互素。當(dāng)f求出后，第（3）步中，我們求出d1即滿足d1e1 = 1 mod f(N)。因?yàn)閒為f(N)的整數(shù)倍。4.2.4 聊天程序模塊1、數(shù)據(jù)庫設(shè)計(jì)用戶信息表User_Infor （存儲(chǔ)注冊(cè)用戶的信息）CREATE TABLE User_Info(user_id INTEGER AUTO_INCREMENT PRIMARY KEY,user_name VARCHAR (50) NOT NULL,user_passwd VARCHAR (10) NOT NULL,user_sex VARCHAR (10),user_age INTEGER,user_address VARCHAR (100),INDEX (user_name) ENGINE = InnoDB; #指定存儲(chǔ)引擎好友關(guān)系表Friend_Index (記錄用戶添加的好友)CREATE TABLE User_Online(user_id INTEGER PRIMARY KEY,ip_address VARCHAR (100) NOT NULL,conn_socket INTEGER NOT NULL,FOREIGN KEY (user_id) REFERENCES User_Info (user_id) ENGINE = InnoDB;在線用戶記錄表User_Online (記錄已登陸的在線用戶和與服務(wù)器建立的套接口)CREATE TABLE User_Online(user_id INTEGER PRIMARY KEY,conn_socket INTEGER NOT NULL,des_key VARCHAR (30) NOT NULL,FOREIGN KEY (user_id) REFERENCES User_Info (user_id) ENGINE = InnoDB;消息記錄表Messages (緩存發(fā)給離線用戶的消息)CREATE TABLE Messages(message_id INTEGER AUTO_INCREMENT PRIMARY KEY,from_id INTEGER NOT NULL,to_id INTEGER NOT NULL,body TEXT NOT NULL,date_posted TIMESTAMP NOT NULL,INDEX (to_id),FOREIGN KEY (from_id) REFERENCES User_Info (user_id),FOREIGN KEY (to_id) REFERENCES User_Info (user_id) ENGINE = InnoDB;2、Web注冊(cè)頁面模塊用戶管理：用于管理用戶的注冊(cè)和登陸。添加好友：查詢數(shù)據(jù)庫中注冊(cè)用戶，選擇要添加的好友插入數(shù)據(jù)庫。3、聊天程序服務(wù)器端初始化套接口，初始化RSA算法生成公鑰和私鑰 > 創(chuàng)建線程池等待連接 > 送出RSA公鑰 > 接收DES密鑰 > 驗(yàn)證登陸信息 > 服務(wù)登陸客戶負(fù)責(zé)消息轉(zhuǎn)發(fā)。4、聊天程序客戶端初始化套接口，生成DES密鑰，向服務(wù)器發(fā)起連接 > 取得RSA公鑰加密DES密鑰后回傳服務(wù)器 > 發(fā)送登陸信息 > 接收好友信息 > 創(chuàng)建發(fā)送消息線程和接收消息線程與好友通信。5系統(tǒng)實(shí)現(xiàn)5.1 DES核心代碼l DES類聲明class DESpublic :DES (unsigned long long); /構(gòu)造函數(shù)僅傳入密鑰void encrypting (unsigned long long &); /加密函數(shù)void decrypting (unsigned long long &); /解密函數(shù)private :/明文處理=bitset<64> IP_permute (unsigned long long); /初始置換unsigned long long IP_1_permute (bitset<64>); /逆置換/加密過程=bitset<48> E_permute (bitset<32>);/E盒子置換unsigned long long b1b6 (bitset<48>, int, int);unsigned long long b2b3b4b5 (bitset<48>, int, int, int, int);bitset<32> SBox_Process (bitset<48>); /S盒子置換void P_permute (bitset<32> &); /P置換bitset<32> f (bitset<32>, bitset<48>); /f函數(shù)/子密鑰生成=bitset<56> PC_1_permute (unsigned long long); /PC-1置換void LSi (bitset<28> &, int); /循環(huán)左移bitset<48> PC_2_permute (bitset<56>); /PC-2置換void create_k (unsigned long long);bitset<48> k16; /子密鑰數(shù)組;l 子密鑰生成void DES : create_k (unsigned long long key)bitset<56> CiDi (0);CiDi = PC_1_permute (key); /PC-1置換bitset<28> Ci (0), Di (0);for (int i = 0; i < 56; i+) /將經(jīng)過PC-1置換的數(shù)據(jù)分成左右28比特if (i < 28)Cii = CiDii;elseDii - 28 = CiDii;for (int i = 0; i < 16; i+) /16輪循環(huán)LSi (Ci, LSIi); /LS循環(huán)左移LSi (Di, LSIi); /LS循環(huán)左移for (int j = 0; j < 56; j+) /再將28比特?cái)?shù)據(jù)合為56比特?cái)?shù)據(jù)if (j < 28)CiDij = Cij;elseCiDij = Dij - 28;ki = PC_2_permute (CiDi); /存入子密鑰數(shù)組l 加密算法void DES : encrypting (unsigned long long &msg)bitset<64> ip (0);bitset<32> Li (0), Ri (0), buf (0);ip = IP_permute (msg); /IP初始置換for (int i = 0; i < 64; i+) /等分成左右32位數(shù)據(jù)if (i < 32)Lii = ipi;elseRii - 32 = ipi; for (int i = 0; i < 16; i+) /16輪迭代if (i != 15)buf = Li;Li = Ri; /Li = Ri-1Ri = f (Ri, ki); /f函數(shù)處理Ri-1Ri = buf; /Ri = f (Ri-1, ki) XOR Li-1else /最后不再互換buf = Ri;Ri = f (Ri, ki);Li = Ri;Ri = buf;for (int i = 0; i < 64; i+) /將兩部分32數(shù)據(jù)組合回64位數(shù)據(jù)if (i < 32)ipi = Lii;elseipi = Rii - 32;msg = IP_1_permute (ip); /IP-1 逆置換return; 5.2 RSA核心代碼l 大數(shù)類聲明class BigNumpublic :BigNum (char *a = NULL, unsigned long n = 0, Status s = 0);BigNum () ;BigNum absadd (BigNum, BigNum); /絕對(duì)值相加BigNum abssub (BigNum, BigNum); /絕對(duì)值相減BigNum operator + (BigNum); /加號(hào)重載BigNum operator - (BigNum); /減號(hào)重載BigNum operator * (BigNum); /乘號(hào)重載BigNum operator / (BigNum); /除號(hào)重載BigNum operator % (BigNum); /取余重載BigNum square (); /乘方運(yùn)算BigNum & operator <<= (unsigned long); /循環(huán)左移BigNum & operator >>= (unsigned long); /循環(huán)右移friend bool operator < (BigNum, BigNum); /<重載為友元friend bool operator > (BigNum, BigNum); />重載為友元friend bool operator >= (BigNum, BigNum); />=重載為友元friend bool operator = (BigNum, BigNum); /=重載為友元friend bool operator != (BigNum, BigNum); /!=重載為友元void print ();unsigned long getsize () return (size);char *getnum () return (num);private :char numMAXNUM;unsigned long size;Status symbol; /正數(shù)為1,零為0,負(fù)數(shù)為-1;l 模冪運(yùn)算BigNum modexp (BigNum x, BigNum r, BigNum p) /依據(jù)定理 （a * b）mod n = (a mod n) * (b mod n) mod nBigNum a, b, c ("1", 1, 1), one ("1", 1, 1), zero ("0", 1, 0), two ("2", 1, 1);a = x;b = r;while (b != zero)if (b % two = zero) /是否為偶數(shù)b = b / two; /降階a = a.square () % p; /乘方對(duì)p取余continue;b = b - one;c = (a * c) % p; /乘模運(yùn)算return (c);l 歐幾里德計(jì)算最大公因數(shù)和逆元BigNum RSA : gcd (BigNum &a, BigNum &b, BigNum x, BigNum y) /gcd (x, y) = gcd (y, x mod y), 對(duì)式子ax + by = r, /每一步迭代中ai = ai-2 q * ai-1, bi = bi-2 q *bi-1/其中q 為當(dāng)前這步的商BigNum zero ("0", 1, 0);BigNum q, r, ai_2 ("1", 1, 1), ai_1 ("0", 1, 0), bi_2 ("0", 1, 0), bi_1 ("1", 1, 1);if (x < y) /x、y互換BigNum c = y;y = x;x = c;r = y;while (x % r) != zero) /輾轉(zhuǎn)相除y = x;x = r;q = y / r;r = y % r;a = ai_2 - (q * ai_1); /迭代前兩步x，y逆元表達(dá)式系數(shù)b = bi_2 - (q * bi_1);ai_2 = ai_1;bi_2 = bi_1;ai_1 = a;bi_1 = b;return (r);l Miller-Rabin素性測試bool Prime_Num : Miller_Rabin (BigNum n, BigNum b) /令n 1 = 2lm，其中l(wèi)是非負(fù)整數(shù)，m是正奇數(shù)。 /若bm = 1 (mod n) 或 b(2j)m = (n - 1) mod n 0<=i <= j -1 /則稱n通過以b為基的Miller-Rabin測試BigNum m, j ("0", 1, 0), one ("1", 1, 1), two ("2", 1, 1), zero ("0", 1, 0);BigNum v;m = n - one;while (m % two) = zero) /將n-1處理為2的l次方乘以mm = m / two;j = j + one;if (b < two)cout << "ERROR b!" << endl;exit (0);v = modexp (b, m, n);if (v = one) /若b的m次方對(duì)n取余等于1通過測試return (true);BigNum i ("0", 1, 0);while (i < j)if (v = (n - one) /滿足b(2j)m = (n - 1) (mod n)，測試結(jié)束return (true);v = v.square () % n;i = i + one;return (false);5.3 Web注冊(cè)頁面核心代碼l 用戶管理<?phpclass UserManager /用戶管理類，用于管理用戶賬戶function _construct () public function isValidUserid ($in_userid) /驗(yàn)證用戶id的合法性if ($in_userid = or $in_userid < 0)return FALSE;return TRUE;public function isValidUserName ($in_user_name) /用正則表達(dá)式檢測輸入名字的合法性if ($in_user_name = or !ereg (":alnum:_-1,50", $in_user_name)return FALSE;elsereturn TRUE;public function isValidPassWord ($in_passwd) /檢測輸入密碼的合法性if ($in_passwd = or strlen ($in_passwd) < 4 or strlen ($in_passwd) > 10)echo "password len " . strlen ($in_passwd);return FALSE;elsereturn TRUE;public function createAccount ($in_uname, $in_pw, $in_sex, $in_age, $in_address) /創(chuàng)建賬戶，插入數(shù)據(jù)庫if (!$this->isValidUserName ($in_uname) /檢查用戶名是否正確,如果錯(cuò)誤給出相應(yīng)錯(cuò)誤提示echo <<<ERROR<p align = center><meta http-equiv = "refresh" content = "2; url = register.php">The user name is not right or the length is too long!The page will go back after 2 seconds.</p>ERROR;exit;if (!$this->isValidPassWord ($in_pw) /檢查密碼是否正確,如果錯(cuò)誤給出相應(yīng)錯(cuò)誤提示echo <<<ERROR<p align = center><meta http-equiv = "refresh" content = "2; url = register.php">The password is not right or the length is too long!The page will go back after 2 seconds.</p>ERROR;exit;$conn = $this->getConnection (); /創(chuàng)建到數(shù)據(jù)庫的連接$conn->autocommit (FALSE); /關(guān)閉自動(dòng)提交至數(shù)據(jù)庫為事務(wù)處理狀態(tài)$qstr = <<<EOQUERYINSERT INTO User_Info (user_name, user_passwd, user_sex, user_age, user_address)VALUES ($in_uname, $in_pw, $in_sex, $in_age, $in_address)EOQUERY;$result1 = $conn->query ($qstr); /執(zhí)行查詢語句if ($result1 = FALSE)$conn->rollback (); /出錯(cuò)后事務(wù)回滾echo "Insert User_Info false. message : ".$conn->error;exit;$user_id = $conn->insert_id;$result2 = $conn->commit (); /提交查詢if ($result2 = FALSE)echo "Commit Insert false. message : ".$conn->error;exit;$conn->close (); /關(guān)閉數(shù)據(jù)庫連接return $user_id; /返回用戶賬號(hào)public function userLogin ($user_id, $in_password) /處理用戶登錄$conn = $this->getConnection (); /連接數(shù)據(jù)庫$check = <<<CHECKSELECT user_name, user_id FROM User_Info WHERE user_id = $user_id AND user_passwd = $in_passwordCHECK;$result = $conn->query ($check); /執(zhí)行查詢語句if ($result = FALSE)echo select User_Info false! message: .$conn->error;exit;if ($row = $result->fetch_assoc () = NULL) /檢查登陸用戶信息是否正確,如果錯(cuò)誤返回FALSE$conn->close ();return FALSE;$conn->close ();return $row;private function getConnection () /連接數(shù)據(jù)庫$conn = new mysqli (localhost, andy, andy2000, FreeChat);if (mysqli_connect_errno () != 0)$errno = mysqli_connect_errno (); /獲取數(shù)據(jù)庫連接錯(cuò)誤號(hào)$errmsg = mysqli_connect_error (); /獲取數(shù)據(jù)庫連接錯(cuò)誤信息echo Connect database failed with: ($errno) $errmsg.;exit;return $conn;?>5.4服務(wù)器端核心代碼圖5.1 服務(wù)器完成初始化圖5.1為服務(wù)器初始化過程和為已登錄用戶服務(wù)的過程。服務(wù)器先生成RSA算法所需的公鑰和私鑰，當(dāng)連接到來時(shí)服務(wù)器送出RSA公鑰并等待用戶回傳DES密鑰。當(dāng)用戶傳回DES密鑰后，服務(wù)器用RSA私鑰解密得到DES密鑰。此后用戶登錄信息由此DES密鑰解密，用戶發(fā)送的消息由服務(wù)器轉(zhuǎn)發(fā)。l 線程函數(shù)，為登陸客戶服務(wù)void service (int connfd, RSA rsa)char bufMAXLINE;user_login *login;int n, check;unsigned long long key;publickey pk;pk.e = rsa.e;pk.n = rsa.n;send_rsa_publickey (connfd, pk); /發(fā)送RSA公鑰cout << "公鑰已送出!" << endl;cerr << "正在獲取des密鑰，請(qǐng)稍后." << ends;key = getdeskey (connfd, rsa); /獲取DES私鑰cout << "ok" << endl;if (key = 0)return;if (n = readn (connfd, (void *)buf, MAXLINE) < 0) /從套接口上讀取用戶登陸信息cout << "Read from socket connfd false! message: " << strerror (errno) << endl;exit (ERROR);else if (n = 0)cout << "The client close socket." << endl;return;login = (user_login *)buf;DES_Data *data = new DES_Data (void *)login->password, 16, key);bcopy (void *)data->Decrypting (), (void *)login->password, 11); /解密用戶登陸口令cout << "No." << login->user_id << "請(qǐng)求登錄." << endl;if (!(check = Attestation (connfd, login) /認(rèn)證用戶登陸消息cout << "Wrong user name or wrong password!" << endl;cout << "登錄失敗!" << endl;return;else