淺談如何利用ＲＳＡ算法進行數字簽名

摘要：文章介紹了RSA算法的基本原理，提出了RSA算法中數據分塊的基本方法，分析了RSA數字簽名算法的基本理念，給出了運用RSA算法進行數字簽名的步驟以及進行驗證的步驟。

關鍵詞：RSA；數字簽名

中圖分類號：TP309文獻標識碼：A文章編號：1009-3044(2008)15-21048-02

Discussed Shallowly how to Carry on Digital Signature Using the RSA Algorithm

LI Chun-mei

(Anhui Xinhua University，Hefei 230088，China)

Abstract:The article introduced the RSA algorithm's basic principle， proposed in the RSA algorithm the data piecemeal's essential method， has analyzed the RSA digital signature algorithm basic idea， gave has carried on digital signature using the RSA algorithm the step as well as carries on confirmation the step.

Key words:RSA;Digital signature

1 引言

數字簽名是目前電子商務、電子政務中應用最普遍、技術最成熟的、可操作性最強的一種電子簽名方法。它采用了規范化的程序和科學化的方法，用于鑒定簽名人的身份以及對一項電子數據內容的認可。它通過將原始信息進行散列函數（哈希函數，Hash Function）運算，并將得到的結果使用密鑰進行加密，從而得到數字簽名值。其依據是在使用安全的哈希函數(單向哈希函數)的情形下，要想從已知的哈希函數結果中推導出原信息來，實際上是不可能的，因此，數字簽名可以在更少且可預見的數據量上進行運算，生成數字簽名，卻保持與原信息內容之間的高度相關，有效的保證了其完整性、真實性和不可抵賴性的特點。

基于公鑰密碼體制和私鑰密碼體制都可以獲得數字簽名，目前主要是基于公鑰密碼體制的數字簽名，包括普通數字簽名和特殊數字簽名。普通數字簽名算法有RSA、ElGamal、Fiat-Shamir、Guillou-Quisquarter、Schnorr、Ong-Schnorr-Shamir數字簽名算法、Des/DSA，橢圓曲線數字簽名算法和有限自動機數字簽名算法等。特殊數字簽名有盲簽名、代理簽名、群簽名、不可否認簽名、公平盲簽名、門限簽名、具有消息恢復功能的簽名等，它與具體應用環境密切相關。其中RSA算法是一種公認十分安全的算法，而且是目前網絡上進行保密通信和數字簽名的最有效的安全算法。

2 RSA簽名算法的確定

RSA算法所根據的原理是：根據數論，尋求兩個大素數比較簡單，而將它們的乘積分解開則及其困難。在這一體制中，密鑰分為兩種：加密密鑰PK={e，n}和解密密鑰SK={d，n}。

其中的加密密鑰PK是公開的，使得其他人可以使用，而對解密密鑰中的d則保密。這里，n為兩個大素數p和q的乘積（素數p和q一般為100位以上的十進制數），e和d滿足一定的關系，在已知e和n的情況下不能求出d。

下面是密鑰產生的過程：

(1)計算n。秘密選擇兩個大素數p和q，計算出n=p*q。n成為RSA算法的模。

(2)計算Φ(n)。再計算出n的歐拉函數Φ(n)=(p-1)(q-1)，Φ(n)定義為不超過n并于n互素的數的個數。

(3)選擇e。從[0，Φ(n)-1]中選擇一個與Φ(n)互素的數e作為公開的加密指數。

(4)計算d。計算出滿足下式的d：e*d=1 mod Φ(n)，d作為解密指數。

(5)得出所需要的公開密鑰和秘密密鑰：

公開密鑰（即加密密鑰）PK={e，n}

秘密密鑰（即解密密鑰）SK={d，n}

RSA的加解密算法是一樣的，公式如下：Y=Xa mod n（公式一）

當進行加密操作時，令a=e，則Y是X加密后的密文。當進行解密操作時，令a=d，則Y是將X解密后的原文。則該算法也可標識為：

Y=PowerMod(X，a，n) （公式二）

其中：X待操作的對象，a為運算指數，n為模，Y為操作結果，PowerMod則為Xa mod n。

由此，可得到RSA加密和解密的算法如下：

加密算法EPK(X)=PowerMod(X，e，n) PK={e，n} （公式三）

解密算法DSK(X)=PowerMod(X，d，n) SK={d，n}（公式四）

其中：DSK(EPK(X))=X （公式五）

這里的X只是表示不大于n的整數。當X大于n時，就要將X分塊，使得每塊的長度一致且其值均不大于n，對于整數，顯然是無法分塊的，這就需要先對X進行編碼。編碼的基本要求是將X分塊，每塊是一個8位字節串EB，由塊標記BT，填充塊PS和數據D組成。

EB = 00 || BT || PS || 00 || D（等式一）

塊標記BT是一個標記字節，表示加密塊的結構。它有00，01，或02值。私鑰操作為00，或01；公鑰操作為02。填充串PS為k-3-||D||（D的字節長度）長的8位字節字符串。對于00型，填充串為00；對于01型，填充串為ff；對于02型，填充串為假散列生成的非0值。這使得加密塊EB的長度為k（模n的長度）。其中開始的00值字節保證了轉化成整數后的分塊小于模數n。

其中需要注意的地方如下：

對于00型（BT=00）來說，數據D必須以一個非0字節開始，或是必須知道長度，以便塊能被清楚的解析（EB中粗體部分）。對于01和02型來說，塊能被清楚的解析，這是因為填充塊PS不包含00值字節，它可以被一個00值字節從數據D分開。

01型被推薦為私鑰操作標志。

對于02類型來說，建議為每一個加密過程都獨立生成假散列字節，特別是如果相同的數據被輸入多于一個的加密過程。

對于01和02類型來說，填充串至少是8個字節長，為了防止攻擊者通過測試所有可能的加密塊來恢復數據。

上面的加密和解密算法適用的環境是他人通過PK將信息進行加密傳送給擁有SK者，擁有SK者在用SK進行解密，得到原始信息，這樣可防止其他人竊取信息。但是在數字簽名中卻不適用，因為數字簽名的過程正好相反，要求是擁有SK者先將信息進行加密，其他人在通過PK進行簽名驗證，那么該如何處理呢？

考慮這樣一個公式：EPK(DSK(X))=X（公式六）

這個公式看起來和上面的加密公式（公式五）很相似，只不過把加密和解密的過程換了個順序，但是滿足了數字簽名的要求，為什么呢？從公式二、公式三和公式四可知，E（加密）和D（解密）算法沒什么區別，只是參數不同而已，如果把參數互換一下，則可得到下面的公式：

加密算法ESK(X) =PowerMod(X，d，n) SK={d，n}（公式七）

解密算法DPK(X)=PowerMod(X，e，n) PK={e，n} （公式八）

其中：DPK(ESK(X))=X（公式九）

很顯然，公式九就是需要的數字簽名的算法。

3 數字簽名的流程

對于給定的原始數據，有時有可能比較大，而且RSA處理又是很慢，如果直接加密的話很是浪費時間，所以為了節省處理時間，在數字簽名時一般不通過直接加密原始數據而得到簽名值，而是先對原始數據進行散列化（單向散列），然后對散列的結果進行加密。這樣便得到了數字簽名的4個基本步驟：

3.1 第一步：消息散列

對于有效的散列算法，一般選擇MD2，MD4，MD5，SHA(SHA1)等算法，其中MD系列散列算法產生32字節的摘要信息，SHA系列算法產生40字節的摘要信息（散列的結果越長，越不容易被偽造）。可以任意選擇一種算法對消息M進行處理，進而得到M的散列信息MD，即消息散列。

3.2 第二步：數據編碼

如果直接對第一步得到的MD進行加密不就生成數字簽名信息了嗎？為什么還要有數據編碼的步驟呢？這個問題在第一步中就可以得到答案。

在第一步中提到有很多種散列算法都可以生成有效的摘要信息，這些算法生成的摘要信息均不包含散列算法信息，這就給接收者進行數字簽名驗證帶來了很大的麻煩，會因為無法得知發送方的散列方法而無法對接收到的數字簽名信息進行驗證，這時，就要求發送方在生成數據摘要時提供所使用的散列算法，以滿足接收者進行簽名驗證的需要。所以把散列算法和散列結果組合在一起，作為一個數據摘要完整的整體，這就是數據編碼過程所要完成的工作。

一般情況下，把消息散列MD和消息散列算法標識符組成下面所描述的ASN.1類型DigestInfo的值，此類型將通過BER編碼來生成一個8位字節串D，即原始數據。

DigestInfo ::= SEQUENCE {

digestAlgorithm DigestAlgorithmIdentifier，/* 散列函數標識編碼 */

digest Digest/*消息散列MD */

}

DigestAlgorithmIdentifier ::= AlgorithmIdentifier

Digest ::= OCTET STRING

類型DigestInfo的域有下列含義：

digestAlgorithm表示用于散列的算法（以及相關參數）。它標識了所選的散列算法：MD2、MD4、MD5或SHA等。作為參考，以下是部分相關的對象標識符：

md2 OBJECT IDENTIFIER ::={ iso(1) member-body(2) US(840) rsadsi(113549)digestAlgorithm(2) 2 }

md4 OBJECT IDENTIFIER ::={ iso(1) member-body(2) US(840) rsadsi(113549)digestAlgorithm(2) 4 }

md5 OBJECT IDENTIFIER ::={ iso(1) member-body(2) US(840) rsadsi(113549)digestAlgorithm(2) 5 }

sha-1 OBJECT IDENTIFIER ::= {iso(1) identified-organization(3) oiw(14) secsig(3) algorithm(2) 26}

對這些對象標識符來說，散列算法的參數域是空（散列函數除消息M外無其他參數）。

digest是消息散列過程的結果，例如消息散列MD。

具體編碼方法可參考ASN.1相關標準。

3.3 第三步：RSA私鑰加密

為了安全起見，數字簽名所使用的RSA的密鑰長度（n的長度）最少選擇1024位（轉換成二進制為128個字節），長度遠遠大于MD編碼后的字符串D。D被簽名者采用公式七進行加密，生成一個8位字節串ED，其塊標記為01（見1節）。

3.4 第四步：字節串到位串的轉換

第三步中加密的結果ED是一個8位字節串，而簽名值是個位串，簽名驗證時是一位一位進行驗證的，所以要將ED轉換成一個位串S，即簽名值 。具體來說，ED的第一個字節的第一位成為S的第一個數據位，以此類推，直到ED的最后一個字節的最后一位，它將變成S的最后一個數據位。實際上就是取ED的二進制編碼。

注意：簽名S的位長度是8的倍數（是字節串的二進制表示）。

4 數字簽名的驗證

驗證過程同樣包括四個步驟：位串到字節串的轉換，RSA公鑰解密，BER數據解碼得到解密后的散列值，最后與原始數據散列值進行比較，若每一位都相同則驗證通過，否則驗證失敗。

4.1 位串到字節串的轉換

簽名S被轉換成字節串ED，即被加密的數據。具體來說，假設S的位長度是8的倍數，S的第一位將變成字節串的第一個字節的第一位，以此類推，直到簽名的最后一位變成字節串的最后一個字節的最后一位。如果簽名的位長度不是8的倍數，則是錯誤。

4.2 RSA解密

采用公式八使用簽名者的公鑰對被加密數據ED進行解密，得到字節串EB，然后根據等式一進行解析，得出塊標記BT，填充塊PS和原始數據D。如果有下列情況發生，則為錯誤：

BT標記不是01（私鑰加密，BT應該為01）。

填充塊PS少于8字節，或是和塊標記BT不匹配。

4.3 數據解碼

將原始數據D是DigestInfo 類型的ASN.1編碼結構，將D進行BER解碼，得到分成消息散列MD和消息散列算法標識符。消息散列算法標識符決定了下一步所選的消息散列算法。如果消息散列算法標識符不是MD2，MD4，MD5或SHA(SHA1)消息散列算法，則為錯誤。

4.4 消息散列和比較

使用所選的消息散列算法對收到的消息M進行散列，得到字節串MD’。如果MD`和MD完全相同，則表示驗證成功，否則為失敗。

5 結束語

在實際應用中，進行數字簽名的RSA中的模n一般都要求1024位或2048位，這在常用的編程軟件中都是很難處理的。因為在常用的編程軟件中整數最大只支持到64位，也就是說n≤2^64，遠遠滿足不了要。但是，如果把大數換算成其他x進制的數（比如2^16進制、2^30進制等），用長度為x的無符號長整型數組來存儲每一“位”x進制的數，這樣每一“位”x進制的數就可以表示0～2^x之間的整數，保證2個x進制的數進行任何運算都不會出現溢出，處理好這個x進制數的相關運算（加、減、乘、除、冪等）后就可以自己編寫滿足數字簽名要求的RSA算法了。

參考文獻：

[1] 謝希仁.計算機網絡教程[M].北京:人民郵電出版社，2004.

[2] RFC2313-1998 PKCS #1:RSA Encryption Version 1.5[S].

[3] GBT 16262.1-2006 抽象語法記法(ASN.1)基本記法規范[S].

[4] GBT 16263.2-2006 ASN.1編碼規則第1部分，基本編碼規則(BER)、正則編碼規則(CER)和非典型編碼規則(DER)規范[S].