3.4 數字簽名
在通信網絡安全中的密鑰分配、認證以及電子商務系統中，信息除了需要保證機密性以外，還需要滿足完整性、可認證性、不可否認性以及匿名性等基本安全要求。數字簽名作為這些基本安全要求的實現手段之一，在現代密碼學中具有重要的意義。本節將首先闡述數字簽名的基本概念，然后介紹ElGamal、RSA和DSS等常用的數字簽名算法。
3.4.1 基本概念
數字簽名（又稱公鑰數字簽名）類似于寫在紙上的普通物理簽名，但使用了公鑰加密領域的技術進行實現。簽名信息是采用一套規則和一系列參數通過某種運算得到的，通過它可以鑒別認證簽名者的身份并驗證電子文檔或數據的完整性。一套數字簽名機制通常需要定義兩種互補的運算，一種用于簽名，另一種用于驗證。
隨著計算機和通信網絡的發展，人們希望通過電子設備實現快速、遠距離的交易，由于在傳輸過程中存在不安全因素，數字簽名方法便應運而生，并開始廣泛應用于商業通信系統，如電子郵件、電子商務和電子政務等。
數字簽名與手寫簽名有相似之處，它們都需要滿足下列條件：接收方能夠確認或證實發送方的簽名，但不能偽造；發送方發出帶有簽名的內容給接收方后，就不能再否認它所簽發的內容；接收方對已收到的簽名內容不能否認，即需要有收報認證；必要時，第三方可以確認收發雙方之間的簽名內容，但不能偽造這些內容。
同時，數字簽名與手寫簽名也有許多不同之處。首先，在數字簽名中，簽名同消息是分開的，需要一種方法將簽名與消息綁定在一起，而在手寫簽名中，簽名被認為是被簽名消息的一部分；其次，在簽名驗證的方法上，數字簽名利用一種公開的方法對簽名進行驗證，任何人都可以對簽名進行驗證，而手寫簽名是由經驗豐富的接收者通過與以往的簽名進行比對來驗證；而且，數字簽名和所簽名的消息能夠在通信網絡中傳輸，而手寫簽名只能使用傳統的安全方式進行傳輸；最后，對于手寫簽名的復制比較困難，而對數字簽名的復制則非常容易。因此，在數字簽名方案的設計中要預防簽名的重用。
為了滿足在網絡環境中身份認證、數據完整性和不可否認性等安全需求，數字簽名必須具有以下幾個重要特性。
1）可信性。即簽名的接收方可以方便并有效地通過一個專門的驗證算法來驗證真偽。
2）不可偽造性。即除了合法的簽名者之外，任何人都無法偽造出這一簽名。
3）不可復制性。即對于某一條消息的簽名，任何一方都不能將此簽名用作對另一條消息的簽名。
4）不可抵賴性。即簽名一旦生成并被發送出去，簽名的生成者不能否認自己的簽名，因為接收方可以向別人出示簽名來證明消息的來源。
5）不可修改性。即簽名一旦完成，則對被簽名消息的任何修改都能夠被輕易發現。
通常，根據接收方驗證簽名的方式不同，可以將數字簽名分成兩大類——真數字簽名和仲裁數字簽名。真數字簽名就是簽名的接收方在收到簽名之后能夠獨立地驗證簽名的真偽而不必借助于其他任何人；仲裁數字簽名則是指接收方不能獨立完成簽名的驗證，而是需要與一個可信的第三方（即仲裁者）合作來完成驗證。
根據數字簽名實現方法的不同，又可以將數字簽名分為采用對稱加密算法的數字簽名和采用公鑰加密算法的數字簽名。采用對稱加密算法的數字簽名技術需要簽名的生成方和驗證方都持有相同的（或者是可以互相推導的）簽名密鑰來完成簽名生成和驗證的過程。這種方式容易導致所持有的密鑰外泄，并存在偽造的可能，因此其安全性并不高。而采用公鑰加密算法的數字簽名由于任何人都無法從公鑰推導出私鑰，因此密鑰外泄的可能性要低很多。當然，這類數字簽名技術的運行速度要比采用對稱加密算法的數字簽名慢得多。
圖3-8展示了一個采用公鑰加密算法的數字簽名算法的原理示意圖。
圖3-8 數字簽名原理示意圖
由圖3-8可知，采用公鑰加密算法的數字簽名的具體運行過程如下。
1）發送端首先對所要發送的消息數據采用Hash函數進行運算并獲得其消息摘要，然后使用私鑰對這段摘要進行加密，將加密結果作為數字簽名附在所要發送的消息數據之后一同發出。
2）接收端通過一個可信的第三方——證書機構（Certification Authority，CA）獲得發送端的公鑰，對接收到的數字簽名進行解密，得到摘要1。
3）接收端采用相同的Hash函數計算并獲得消息數據的摘要2，然后將摘要1與摘要2進行比較，以判斷數字簽名是否有效。
3.4.2 常用數字簽名技術
目前，數字簽名主要采用的是公鑰密碼算法，其中比較典型的有兩個：RSA簽名算法和ElGamal簽名算法。RSA簽名算法提出的時間比較早，其建立的基礎同RSA加密算法一樣，兩者都是基于大數分解難題。1985年，ElGamal簽名算法方案被提出，該方案的改進版已經被NIST采納為數字簽名算法（Digital Signature Algorithm，DSA），用于數字簽名標準（Digital Signature Standard，DSS）中。DSA的安全性建立在離散對數求解困難的基礎上，并使用了安全Hash算法SHA，其安全性與RSA算法基本相當。
本節將介紹RSA數字簽名方案、ElGamal數字簽名方案和DSS數字簽名標準。
1. RSA數字簽名方案
數字簽名方案通常由簽名算法和驗證算法兩部分組成。其中，簽名算法可以是保密的，也可以是公開的，而驗證算法則必須是公開的，并且驗證者可以通過這個公開的驗證算法來直接判斷出簽名的真偽。
RSA數字簽名方案在其運行過程中采用了前面介紹過的RSA公鑰加密算法，但在簽名方案中其使用方式有所不同。在作為加密算法使用時，發送方使用接收方的公鑰對信息進行加密，接收方利用自己的私鑰來解密信息；而在簽名方案中，發送方使用自己的私鑰對信息進行加密，接收方使用發送方的公鑰來解密信息進行驗證。其具體過程如下。
（1）算法描述
1）初始化。任意選取兩個大素數p和q，計算乘積n=pq以及歐拉函數值?（n）=（p-1）（q-1）；再隨機選取一個整數e，滿足1＜e＜?（n），而且e與?（n）互素；然后計算整數d，使得ed≡1mod?（n）。最后，公開n，e的值作為公鑰，而p、q和d保密。
2）簽名過程。設需要簽名的消息為x（x∈Zn），選擇一個安全的Hash函數，發送方的私鑰為d，計算
SigK≡h（x）dmodn
則SigK即為對消息x的簽名。
3）驗證過程。設接收方收到的簽名消息為y，利用發送方的公鑰e對簽名進行驗證
VerK（x，y）=TRUE?h（x）modn≡yemodn，其中x，y∈Zn
若VerK（x，y）=TRUE，則簽名有效；否則簽名無效。
（2）正確性證明
由ed≡1mod?（n）可得
ed=k?（n）+1，k∈Zn
于是，根據簽名和驗證算法可以得到
yemodn=（SigK）emodn=h（x）edmodn=h（x）kφ（n）+1modn=h（x）modn
由此，即可證明簽名方案的正確性。
2. ElGamal數字簽名方案
ElGamal加密方案能夠使用用戶的公鑰進行加密，并利用用戶的私鑰進行解密。而El-Gamal數字簽名方案，則是使用私鑰進行加密，而用公鑰進行解密。
先來看一下ElGamal方案中使用的數論原理。對于素數q和
，則有
a，a2，…，aq-1
取模（modq）后各不相同。如果a是q的本原元，則進一步有
1）對于任意整數m，am≡1（modq）當且僅當m≡0（modq-1）。
2）對于任意整數i、j，ai≡aj（modq）當且僅當i≡j（modq-1）。
同ElGamal加密方案一樣，ElGamal數字簽名方案的基本元素是素數q和a，其中a是q的原元。用戶A通過如下步驟產生公鑰和私鑰。
1）生成隨機整數XA，使得1＜XA＜q-1。
2）計算YA=aXAmodq。
3）則A的私鑰是XA；A的公鑰是{q，a，YA}。
為了對消息M進行簽名，用戶A首先計算M的Hash值m=H（M），這里m是滿足0≤m≤q-1的整數。然后A通過如下步驟產生數字簽名。
1）選擇隨機整數K，滿足1≤K≤q-1以及gcd（K，q-1）=1，即K與q-1互素。
2）計算S1=aKmodq。
3）計算K-1 mod（q-1），即計算K模q-1的逆。
4）計算S2=K-1（m-XAS1）mod（q-1）。
5）簽名包括（S1 ，S2 ）對。
任意用戶B都能通過如下步驟驗證簽名。
1）計算V1=ammodq。
2）計算V2=（YA）S1（S1）S2 modq。
如果V1=V2 ，則說明簽名合法。
3. DSS數字簽名標準
DSS是一種數字簽名方案，它是在由ElGamal基于離散對數問題提出的一個既可用于加密又可用于數字簽名的密碼算法的基礎上改進而來的，已經被NIST采納。該方案本身是一個非確定性的算法，這也意味著對于任何給定的消息將有許多合法的簽名。DSS數字簽名的具體過程如下。
（1）算法描述
1）初始化。選取兩個大素數p和q，滿足p-1能夠被q整除；選取一個整數h，計算g=h（p-1）/q modp，滿足h∈Zp?，且h（p-1）/q modp＞1；再隨機選取一個正整數x（0＜x＜q）作為私鑰，并計算y=gxmodp，將（p，q，g，y）作為公鑰；選擇單向Hash函數H（x），DSS標準中規定為SHA-1算法。
2）簽名過程。假設待簽名的消息為M（M∈Z?p），簽名者選擇隨機數k（0＜k＜q），計算
r=（gkmodp）modq
s=k-1 [H（M）+xr] modq
則（r，s）即為對消息M的簽名。
3）驗證過程。接收方收到消息M和簽名值（r，s）后，進行以下步驟
w=s-1 modq
u=[H（M）w] modq
t=（rw）modq
v=[（guyt）modp] modq
當v=r時，說明簽名有效。
（2）正確性證明
根據簽名和驗證算法可以得到
v =[（guyt）modp] modq=[（gH（ M） wyrw）modp] modq=[（gH（ M） wgxrw）modp] modq
=[（g[H（M）+xr]w）modp] modq=（gskwmodp）modq=（gkmodp）modq=r
由此，可以證明簽名方案的正確性。