簽名算法是指數字簽名的算法。數字簽名，就是只有信息的傳送者才能產生的別人無法偽造的一段數字串，這段數字串同時也是對信息的傳送者傳送信息真實性的一個有效證明。數字簽名是通過一個單向函式，對要傳送的信息進行處理得到的用以認證信息來源，並核實信息在傳送過程中是否發生變化的一個字母數字串。目前套用最為廣泛的三種簽名算法是：Rabin簽名、DSS簽名、RSA簽名。
基本介紹
- 中文名：簽名算法
- 外文名：signature algorithm
- 學科：計算機科學
- 類別：數字簽名
- 特徵：加密傳輸
- 主要方法：Rabin簽名、DSS簽名、RSA簽名。
基本概念,實現方法,相關步驟,算法比較,安全性,參數選擇,參數共享性,簽名速度,驗證速度,印記長度,印記的重複性,
基本概念
簽名算法是指數字簽名的算法。數字簽名（又稱公鑰數字簽名、電子簽章）是一種類似寫在紙上的普通的物理簽名，但是使用了公鑰加密領域的技術實現，用於鑑別數字信息的方法。一套數字簽名通常定義兩種互補的運算，一個用於簽名，另一個用於驗證。
數字簽名是通過一個單向函式，對要傳送的信息進行處理得到的用以認證信息來源，並核實信息在傳送過程中是否發生變化的一個字母數字串。數字簽名提供了對信息來源的確定並能檢測信息是否被篡改。數字簽名要實現的功能是我們平常的手寫簽名要實現功能的擴展。平常在書面檔案上籤名的主要作用有兩點，一是因為對自己的簽名本人難以否認，從而確定了檔案已被自己簽署這一事實；二是因為自己的簽名不易被別人模仿，從而確定了檔案是真的這一事實。採用數字簽名，也能完成這些功能：
（1）確認信息是由簽名者傳送的；
（2）確認信息自簽名後到收到為止，未被修改過。
數字簽名算法有映象式和印記式兩類。由於印記式的簽名速度和驗證速度比映象式快得多，因此印記式數字簽名算法更為實用。
實現方法
實現數字簽名有很多方法，目前數字簽名採用較多的是公鑰加密技術，同時套用最為廣泛的三種是：Hash簽名、DSA簽名、RSA簽名。
對稱密鑰密碼算法進行數字簽名
對稱密鑰密碼算法所用的加密密鑰和解密密鑰通常是相同的，即使不同也可以很容易地由其中的任意一個推導出另一個。在此算法中，加、解密雙方所用的密鑰都要保守秘密。
Lamport發明了稱為Lamport.Difle的對稱算法：利用一組長度是報文的比特數(n)兩倍的密鑰A，來產生對簽名的驗證信息，即隨機選擇2n個數B，由簽名密鑰對這2n個數B進行一次加密交換，得到另一組2n個數C。
傳送和接收的方式如下：
（1）傳送
傳送方從報文分組M的第一位開始，檢查M的第i位：
M的第i位為0時，取密鑰A的第i位；M的第i位為1時，取密鑰A的第i+1位。
直至報文全部檢查完畢，所選取的n個密鑰位形成了最後的簽名。
（2）接收
接受方對簽名進行驗證，從第一位開始依次檢查報文M：
M的第i位為0時，簽名中的第i組信息是密鑰A的第i位；M的第i位為1時，簽名中的第i組信息為密鑰A的第i+1位。
直至報文全部驗證完畢後，就得到了n個密鑰，由於接受方傳送驗證信息c，所以可以利用得到的n個密鑰檢驗驗證信息，從而確認報文是否是由傳送方所傳送。
Hash簽名
單向函式的概念是計算起來相對容易，但求逆卻非常困難。也就是說，已知X，我們很容易計算f(X)。但已知f(X)，卻難於計算出X。
單向Hash函式有很多名字：壓縮函式、縮短函式、訊息摘要、指紋等。單向Hash函式H(M)對一則任意長度的訊息進行處理，返回一個具有固定長度m的散列值h：
h=H(M)，其中h的長度為m=H(M)具有以下屬性：
（1）給定M，很容易計算出h，這表現了函式的快速性；
（2）給定h，很難計算出滿足H(M)=h的M，這表現了函式的單向性；
（3）給定M1，很難找到一則訊息M2，使得H(M1)=H(M2)；
（4）h=H(M)，h的每一比特都與M 的每一比特有關，並有高度敏感性。即每改變M的一比特，都將對h產生明顯影響；
（5）Hash函式除了信息M 自身之外，應該基於發信方的秘密信息對信息M進行確認；
（6）輸入數據M沒有長度限制；
（7）對輸入任何長度的M數據能夠生成該輸入報文固定長度的輸出。
相關步驟
RSA數字簽名算法
產生簽名與驗證參數：
Step1，簽名人A選擇兩個大素數p、q，計算n=pq及中Φ(n) = (P-1)(q-1)；
Step2，尋找e 、d 使滿足(eΦ(n))
1及ed l(mod Φ(n))；
Step3，公開驗證參數{n,e}，A 保存{ p, q,d , Φ(n)}作為秘密的簽名參數；
Step4，選用一通用的散列函式h(.)。
簽名算法：
Step1，A將需簽名的檔案m(含接收人、內容、簽名人、日期等)編碼後映射成h(m) ；
Step2，計算
Step3，將{m,
}傳送至檔案接收人B或仲裁人T(A、B、T的含義下同)。
驗證算法：
B(或T)檢驗
是否成立，若成立則接收此檔案及簽名，否則拒絕接收或宣布無效。
Rabin數字簽名算法
產生簽名與驗證參數：
Step1，簽名人A選擇兩個大素數p、q，計算n=pq；
Step2，公開驗證參數n，A 保存{ p, q}作為秘密的簽名參數；
Step3，選用一通用的散列函式h(.)。
簽名算法：
Step1，A 將需簽名的檔案m編碼後映射成h(m)；
Step2，計算
mod p，
mod q及印記
Step3，將{m, ，
}傳送至檔案接收人B或T。
驗證算法：
B或T檢驗
是否成立，若成立則接收此檔案及簽名，否則拒絕接收或宣布無效。
DSS數字簽名算法
產生簽名與驗證參數：
Step1，A 選擇一個大素數p，p-1應具有大素數因子q，選擇一個g使g的次數為q，再選擇一個計算
mod p；
Step2，公開驗證參數{p,q,g,y}，A 保存{ p, q}作為秘密的簽名參數；
Step3，選用一通用的散列函式h(.)。
簽名算法：
Step1，A 將需簽名的檔案m編碼後映射成h(m)，計算
使
Step2，計算
及s
(h(m)+xr) mod q；
Step3，將{m,r,s}傳送至檔案接收人B或T。
驗證算法：
Step1，B(或T)先計算u h(m)
mod q及v r mod q；
Step2，檢驗
是否成立，若成立則接收此檔案及簽名, 否則拒絕接收或宣布無效。
算法比較
下面是對三種簽名算法RSA、Rabin、DSS算法的比較。
安全性
由於求解mod n(n=np)的平方根問題以高機率等價於n的整數分解問題（Rabin定理），所以Rabin算法的安全性與RSA大體相當。DSS的安全性是建立在求離散對數問題上，至今雖未證明破解DS與求解q階乘法群的離散對數等價，但也未找到其他可繞開求離散對數的解法。整數分解與求離散對數的計算複雜度是近似的，因而上述三種簽名算法的安全性大體相當。
參數選擇
DSS算法參數的選擇比前兩種算法要容易。RSA算法出於安全性考慮，對參數p、q的選擇有一些較嚴格的要求，如
（k為較小自然數）應足夠大、gcd(p-1,q-1)應比較小、p
1和q 1都應至少含有一個充分大的素數因子等；Rabin算法對參數p、q的要求與RSA算法大體相同，但為了達到與RSA相當的安全性，其參數p、q應比RSA算法中稍大；DSS算法安全性的關鍵參數是q，可比前兩種算法中的n值略小，但應遠大於單獨的p和q。
參數共享性
RSA 算法和Rabin算法都無法共享參數；因為DSS算法可以對k有不同選擇，所以可以共享參數p、q、g，參數共享時至今尚未發現用戶之間可以互相傷害的途徑。
簽名速度
DSS算法簽名速度較慢。RSA算法和Rabin算法簽名時耗費時間的主要部分都是mod p、mod q的指數運算，這兩種算法簽名速度大體相同；DSS 算法簽名時mod p(p>q)的指數運算所耗費的時間要比前兩種算法長。
驗證速度
DSS算法驗證速度較慢。Rabin算法驗證時需進行一次mod n的平方運算，而RSA算法驗證時需進行一次mod n的e次指數運算，因此RSA算法比Rabin算法要稍慢；DSS算法驗證時需要進行2次mod p的指數運算，因此DSS算法驗證速度較前兩種算法慢,，而Rabin算法驗證速度最快。
印記長度
DSS算法簽名印記較長。RSA算法和Rabin算法的簽名印記都是一個mod n 數 ，只是Rabin算法多了1個很小的數
；DSS算法的簽名印記是兩個mod q數r 、s，比起前兩種算法的印記 要長一些。
印記的重複性
DSS算法簽名印記具有不重複特性。檔案m和h(m)完全相同，用DSS算法簽名時因每次可以選擇不同的k產生簽名印記，故DSS算法的簽名印記每次可以不同；RSA算法和Rabin算法無此特性，但可以對算法作適當改進，以增加1個隨機數加長傳送的數據為代價，使算法具有簽名印記不重複的特性。
