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