【文章內(nèi)容簡介】 同，則驗(yàn)證成功，可以確認(rèn)消息的完整性及簽名確實(shí)為簽名者的；否則，驗(yàn)證失敗，確認(rèn)簽名被冒充或是被篡改。 D E D E MD5 算法的介紹 MD5 消息摘要算法 (RFC 1321)是由 Rivest(公開密鑰密碼 RSA 算法的設(shè)計(jì)者之一 )所設(shè)計(jì)的單 向散列函數(shù)， MD5 不基于任何假設(shè)和密碼體制，它采用了直接構(gòu)造的辦法，速度很快，非常實(shí)用。 MD5 算法的 典型應(yīng)用是對(duì)一段信息（ message）產(chǎn)生 信息摘 要 (MD),以防止被篡改。比如，在 unix 下有很多軟件在下載的時(shí)候都有一個(gè)文件名相同，文件擴(kuò)展名為 .md5 的文件，在這個(gè)文件中通常只有一行文本，大致結(jié)構(gòu)如： md5 () = 0ca175b9c0f726a831d895e269332461 這就是 文件的數(shù)字簽名。 md5 將整個(gè)文件當(dāng)作一個(gè)大文本信息，通過其不可逆的字符串變換算法，產(chǎn)生了這個(gè)唯一的 md5信息摘要。如果在以后傳播這個(gè)文件的過程中，無論文件的內(nèi)容發(fā)生了任何形式的改變（包括人為修改或者下 載過程中線路不穩(wěn)定引起的傳輸錯(cuò)誤等），只要你對(duì)這個(gè)文件重新計(jì)算 md5 時(shí)就會(huì)發(fā)現(xiàn)信息摘要不相同，由此可以確定你得到的只是一個(gè)不正確的文件。如果再有一個(gè)第三方的認(rèn)證機(jī)構(gòu)，用 md5 還可以防止文件作者的 抵賴 ，這就是所謂的數(shù)字簽名應(yīng)用。 md5 還廣泛用于加密和解密技術(shù)上。比如在 unix系統(tǒng)中用戶的密碼就是以 md5（或其它類似的算法）經(jīng)加密后存儲(chǔ)在文件系統(tǒng)中。當(dāng)用戶登錄的時(shí)候，系統(tǒng)把用戶輸入的密碼計(jì)算成 md5 值，然后再去和保存在文件系統(tǒng)中的 md5 值進(jìn)行比較，進(jìn)而確定輸入的密碼是否正確。通過這樣的步驟，系統(tǒng)在并不知道用 戶密碼的明碼的情況下就可以確定用戶登錄系統(tǒng)的合法性。這不但可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道，而且還在一定程度上增加了密碼被破解的難度。 MD5 算法以任意長度的消息作為輸入，產(chǎn)生一個(gè) 128 比特消息散列值（或稱消息摘要）作為輸出。具體的算法步驟如下： 步驟 1：附加填充比特，對(duì)消息進(jìn)行填充，使消息的長度（比特?cái)?shù)）與 448模 512 同余，即恰好為一個(gè)比 512 比特的倍數(shù)僅小 64位的數(shù)。 步驟 2：附加消息長度值，將用 64 比特表示的初始消息（填充前）的長度（比特?cái)?shù)）附加在步驟 1的結(jié)果后。 步驟 3：初始化 MD 緩存， MD5 算法使用了一個(gè) 4個(gè)字（ 128 比特， MD4 中每個(gè)字 32 比特）的緩存來計(jì)算消息摘要，它們主要用來存放 MD5 的中間及最終結(jié)果。緩存可以看成是 4 個(gè) 32 比特的寄存器（ A， B， C， D）。 步驟 4：以 512 比特（ 16 個(gè)字）分組處理消息，這一步是 MD5 算法的主循環(huán)，以 512 比特作為分組，在后面有詳細(xì)的介紹。 3 RSA數(shù)字簽名的設(shè)計(jì)與實(shí)現(xiàn) RSA 數(shù)字簽名的總體設(shè)計(jì) RSA 數(shù)字簽名所需實(shí)現(xiàn)的功能 在本軟件中需要實(shí)現(xiàn)的功能有以下幾個(gè)： （ 1）生成 RSA密鑰：公鑰 ke=（ e,n），私鑰 kd=(d,n)； （ 2）利用 MD5算法計(jì)算出消息摘要 MD； （ 3）數(shù)字簽名的實(shí)現(xiàn)：用私鑰 d對(duì)消息摘要進(jìn)行加密計(jì)算（ RSA算法中的加密方法）； （ 4）驗(yàn)證數(shù)字簽名：用公鑰 e對(duì)數(shù)字簽名進(jìn)行解密計(jì)算（ RSA算法中的解密方法） ，得到的解密結(jié)果與 (2)步計(jì)算出的消息摘要比較，如果兩個(gè)消息摘要一樣則簽名成功。 本軟件的總體要求和設(shè)計(jì) 本軟件的總體要求有： 1）按要求生成非對(duì)稱密鑰 —— 公鑰和私鑰； 2）按任意寫入的的消息字符串 (明文信息 )生成所需要的消息摘要 MD； 3）在本設(shè)計(jì)中用產(chǎn)生的私鑰 d根據(jù) RSA算法的加密原理 對(duì)所生成的消息摘要進(jìn)行加密運(yùn)算，得到數(shù)字簽名； 4）在本設(shè)計(jì)中用產(chǎn)生的公鑰 e根據(jù) RSA算法的解密原理對(duì)所加密的消息摘要即數(shù)字簽名進(jìn)行解密運(yùn)算，得到對(duì)應(yīng)的消息摘要（在本設(shè)計(jì)中標(biāo)示的為解密信息），比較兩個(gè)消息摘要，驗(yàn)證數(shù)字簽名者的身份的真實(shí)與否； 5） 提示信息完整、操作舒適、圖形界面雅觀。 本軟件的總體設(shè)計(jì)都是基于 C++的開發(fā)環(huán)境，采用的是 Microsoft Visual c++ 。 各部分的設(shè)計(jì)實(shí)現(xiàn) 密鑰產(chǎn)生的實(shí)現(xiàn) 在密鑰的產(chǎn)生部分中起決定性作用的是素?cái)?shù)的選擇， 對(duì)隨機(jī)數(shù)作 素性檢測(cè)，若通過則為素?cái)?shù)；否則增加一個(gè)步長后再做素性檢測(cè)，直到找出素?cái)?shù)。素性檢測(cè)采用 Fermat測(cè)試。這個(gè)算法的理論依據(jù)是費(fèi)爾馬小定理：如果 m是一個(gè)素?cái)?shù)，且 a不是 m的倍數(shù)，那么根據(jù)費(fèi)爾馬小定理有： a m1=1 ( mod m)。 實(shí)際應(yīng)用時(shí)： a m1 = 1 ( mod m)? a m = a ( mod m) ?a= a m ( mod m)， 因此對(duì)于整數(shù) m，只需計(jì)算 a m ( mod m)，再將結(jié)果與 a比較，如果兩者相同，則 m為素?cái)?shù)。選取 a=2，則 a一定不會(huì)是任何素?cái)?shù)的倍數(shù)。根據(jù)所選的素?cái)?shù)的不同產(chǎn) 生不同的密鑰。 密鑰的理論產(chǎn)生模塊流程圖如圖 31所示： 圖 31 密鑰產(chǎn)生 密鑰產(chǎn)生的部分代碼實(shí)現(xiàn)： CString str。 //第一步 產(chǎn)生任意素?cái)?shù) GeneratePrimeNumbers()。 //第二步 計(jì)算 n=p*q m_n = m_Prime1 * m_Prime2。 //第三步 0=(p1)(q1) m_Undef = (m_Prime11) * (m_Prime21)。 //第四步 選擇 39。e39。 SelectE()。 //第五步 計(jì)算 D CalculateD()。 //顯示公鑰和私鑰 //(1) 公鑰 KU={e,n} ({%d, %d},m_e,m_n)。 (str)。 //(2) 私鑰 KU={d,n} ({%d, %d},m_d,m_n)。 (str)。 // 選擇一個(gè) 39。e39。 使 39。e39。與 m_Undef互素 產(chǎn)生任意素?cái)?shù) p 和 q 計(jì)算 n=p*q 計(jì)算 ou_la=(p1)(q1) 選擇 e 作為公鑰 計(jì)算 d 作為私鑰 //選擇 e的函數(shù) 的實(shí)現(xiàn) SelectE() { CString str。 for(float i=2。i100000。i++) { if(IsRelativePrime((float)m_Undef,(float)i)) { m_e=(long)i。 return。 } } } //互為素?cái)?shù)的函數(shù)的實(shí)現(xiàn) IsRelativePrime(float X,float Y) { float R。 //輸入 : X,Y if(XY)//如果 X較小則交換兩個(gè)值 { X=X+Y。 Y=XY。 X=XY。 } //在這時(shí) X總是比 Y大 for(。) { if(Y==0) break。 R=fmod(X,Y)。 X=Y。 Y=R。 } if(X != 1) return false。 else return true。//互素 } // 計(jì)算 D的函數(shù)的實(shí)現(xiàn) CalculateD() { float d。 long d_dash。 CString str。 for(float k=1。k100000。k++) { d=(m_Undef*k+1)/m_e。 d_dash = (long)((m_Undef*k+1)/m_e)。 if(d == d_dash) { m_d=d。 return。 } } } //產(chǎn)生素?cái)?shù)的函數(shù)的實(shí)現(xiàn) GeneratePrimeNumbers() { CString str。 UpdateData(TRUE)。 //通過以下兩個(gè)函數(shù)可獲得兩個(gè)大素?cái)?shù) ， 但增加了計(jì)算復(fù)雜性 ， 為了方便 ，直接給定素?cái)?shù) // m_Prime1 = FindPrime(1)。 // m_Prime2 = FindPrime(m_Prime1)。 m_Prime1=47。 m_Prime2=71。 } 產(chǎn)生消息摘要的設(shè)計(jì)實(shí)現(xiàn) 計(jì)算消息摘要的理論實(shí)現(xiàn)流程圖如圖 32所示： 圖 32 消息摘要計(jì)算流程 在以上流程圖中其中循環(huán)處理塊是最重要的一步，也是 MD5的核心算法，在這一步中包括了： （ 1）把四個(gè)連接變量復(fù)制到了四個(gè)變量 a,b,c,d中，使 a=A， b =B， c =C，d=D；其中 a,b,c,d組合成 128位的寄存器，且在 實(shí)際算法運(yùn)算中保存中間結(jié)果和最終結(jié)果； （ 2）將當(dāng)前的 512位塊分解為 16個(gè)子塊，每個(gè)子塊為 32位； （ 3）要循環(huán)四輪，每一輪處理一個(gè)塊中的 16個(gè)子塊，四輪的第一步進(jìn)行不同的處理，其他的相同：每一輪有 16個(gè)輸入子塊 M[0]， M[1]， ???? ..M[15]，或表示為 M[i]，其中 i為 015； t是常量數(shù)組，包含 64個(gè)元素，每個(gè)元素為 32位，數(shù)組 t表示為 t[1]， t[2]， ??? t[64]，或 t[k]， k為 164； MD5的循環(huán)四輪操作過程用下式表示： a=b+((a+proccessP(b,c,d)+M[i]+T[k])s) (s表示循環(huán)左移 s位 ) 產(chǎn)生消息摘要的主要代碼如下： int i。int Index。 //初始化 MD5所需常量 Init()。 初始化 MD5 所需的常量 計(jì)算所需的追加長度 對(duì)原始信息進(jìn)行補(bǔ)位 將輸入分成 512 位的塊 循環(huán)處理塊 得到消息摘要 //計(jì)算追加長度 Append(())。 //對(duì)原始信息進(jìn)行補(bǔ)位 for( i=0。im_AppendByte。i++) { if(i==0) WriteMessage+=(unsigned char)0x80。 else WriteMessage+=(unsigned char)0x0。 } //將原始信息長度附加在補(bǔ)位后 的數(shù)據(jù)后面 for( i=0。i8。i++) WriteMessage+=m_MsgLen[i]。 //位塊數(shù)組 unsigned char x[64]={0}。 //循環(huán) ， 將原始信息以 64字節(jié)為一組拆分進(jìn)行處理 for( i=0,Index=1。i()。i++) { x[++Index]=WriteMessage[i]。 if(Index==63) { Index=1。 //將 64字節(jié)位轉(zhuǎn)換為 16個(gè)字節(jié) Transform(x)。 } } //將寄存器 ABCD的最終值轉(zhuǎn)換為 16進(jìn)制返回給用戶 return ToHex(UpperCase)。 數(shù)字簽名的設(shè)計(jì)實(shí)現(xiàn) 數(shù)字簽名的理論實(shí)現(xiàn)流程圖如圖 33所示 ， 數(shù)字簽名，就是通過在數(shù)據(jù)單元上附加數(shù)據(jù)，或?qū)?shù)據(jù)單元進(jìn)行加密變換，從而使接收者可以確認(rèn)數(shù)據(jù)來源和完整性。數(shù)字簽名是防止他人對(duì)傳輸?shù)奈募M(jìn)行破壞，以及確定發(fā)信人的身份的手段。數(shù)字簽名中的加密算法就是應(yīng)用的 RSA加密原理，而它的驗(yàn)證算法 則是應(yīng)用的 RSA解密原理。 圖 33 數(shù)字簽名的實(shí)現(xiàn)流程 RSA 的加密、解密過程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。為了減小中間結(jié)果和提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性，本設(shè)計(jì)采用了快速指數(shù)算法。它的運(yùn)算過程為（假如要算 a^m mod n）： 1）將 m表示為二進(jìn)制的形式； 2）初始化 c=0， d=1， c 在這里表示指數(shù)的部分結(jié)果，它的終值即為指數(shù) m，d是中間結(jié)果，它 的終值即為所求結(jié)果； 3）從二進(jìn)制數(shù)的最高位到最低位開始對(duì)每一位都用公式 1 進(jìn)行運(yùn)算，得到的 d 為該步的結(jié)果，公式 1： c=2*c。d=fmod(d*d,n)。 4）若二進(jìn)制數(shù)是 1,則在上面的運(yùn)算后繼續(xù)以下運(yùn)算： c=c+1。d=fmod(d*a,n)。得到的結(jié)果 d 才為該步的最終結(jié)果。 數(shù)字簽名主要實(shí)現(xiàn)過程的代碼如下： //消息摘要， 8 位為一組 一個(gè)字符一組 char message[200]。 //從文本框中得到消息摘要 (message,200)。 len=strlen(message)。 開始 得到數(shù)字簽名 得到消息摘要 MD 用私鑰 d 加密 MD 結(jié)束 char showstr[1000]=。 int NO_BITS=32。 double c=0,d=1。 char bits[100]。 double n=(double)m_n。 unsigned char ch。 double data。//19。 long i,k=NO_BITS。 int sizeof_d=sizeof(double)。 //將十進(jìn)制數(shù)私鑰 d轉(zhuǎn)換為二進(jìn)制 D_to_B(m_d,32,bits)。 //得 到合適的字節(jié)