[發明專利]基于RSA的電子簽名方案的長消息編碼的方法

無效

• 申請號: 01802931.0
• 申請日: 2001-09-26
• 公開（公告）號: CN1393081A
• 公開（公告）日: 2003-01-22
• 發明（設計）人: J·S·科倫;D·納卡徹
• 申請（專利權）人: 格姆普拉斯公司
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 中國專利代理(香港)有限公司
• 代理人: 楊凱,張志醒

本發明涉及基于RSA的電子簽名方案的長消息編碼的方法。

在保密密鑰密碼術的傳統模型中，希望通過非安全信道進行通信的兩個人必須首先對保密加密密鑰K達成協議。加密函數和解密函數采用相同的密鑰K。這種保密密鑰加密系統的缺點：在于所述系統在任何加密消息通過非安全信道發送之前，要求事先在兩個人之間通過安全信道就密鑰K進行通信。實際上，找到絕對安全通信信道一般都困難，尤其是在兩個人之間的距離隔得很遠的情況下。安全信道表示不可能知道或修改通過該信道的信息的信道。這樣的安全信道能由連接所述兩個人擁有的兩個終端的電纜來實現。

公共密鑰密碼術的概念由Whitfield?Diffie和Martin?Hellman于1976年發明。公共密鑰密碼術解決了通過非安全信道發送密鑰的問題。公共密鑰密碼術的原理包括利用一對密鑰：公共加密密鑰和專用解密密鑰。從計算的角度上看，從公共加密密鑰得到專用解密密鑰難以行得通。希望向用戶B傳送信息的用戶A使用用戶B的公共加密密鑰。只有用戶B擁有與其公共密鑰有關的專用密鑰。因此只有用戶B能夠解密發送給他的消息。

公共密鑰密碼術較之保密密鑰密碼術的另一個優點在于公共密鑰密碼術允許通過使用電子簽名的進行驗證。

發明RSA加密系統的Rivest、Shamir和Adleman于1977年開發了公共密鑰加密方案的第一實施例。RSA安全性基于對兩個素數的乘積的這樣一個大數進行因子分解的難度。其后，建議了許多公共密鑰加密系統，其安全性是基于以下各種計算問題(這里所列并非窮舉)：

-Merkle-Hellman“背包”：

這種加密系統基于子集的和的問題的難度；

-McEliece：

這種加密系統基于代數碼理論。它基于解碼線性碼的問題；

-E1Gamal：

這種加密系統基于有限域中離散對數的難度；

-橢圓曲線：

橢圓曲線加密系統構成對現行加密系統的修改，以便將之應用到橢圓曲線域。橢圓曲線加密系統的優點在于：與其它加密系統相比，它們需要較小的密鑰大小。

RSA加密系統是最廣泛使用的公共密鑰加密系統。它可用作加密方法或簽名方法。RSA加密系統用于智能卡，用于智能卡中的某些應用。RSA對智能卡的可能應用為：訪問數據庫，金融應用，諸如付費電視、加油或高速公路通行費支付的遠程支付應用。

RSA加密系統的原理如下。它可以被分成三個不同部分，即：

1)生成RSA密鑰對；

2)將明碼消息加密為加密消息，以及

3)將加密消息解密為明碼消息。

第一部分是生成RSA密鑰。根據以下5個步驟的方法，各個用戶建立RSA公共密鑰和相應的專用密鑰：

1)生成兩個相同長度的不同素數p和q；

2)計算n＝pq和φ＝(p-1)(q-1)

3)隨機選擇整數e，使得pgcd(e，φ)＝1，其中1＜e＜φ；

4)計算唯一的整數d，使得e^*d＝1mod(模)φ，其中1＜d＜φ；

5)公共密鑰為(n，e)；專用密鑰是d或(d，p，q)。

整數e和d分別被稱為加密指數和解密指數。整數n被稱為模數。

第二部分包括將表示為m的明碼消息通過算法加密為表示為c的加密消息，其中1＜m＜n，算法如下：

計算c＝m^e?mod?n。

第三部分包括通過一種算法、利用專用解密指數d解密所加密的消息。將表示為c的加密消息解密為表示為m的明碼消息的算法在下面給出，其中1＜c＜n：

計算m＝c^d?mod?n。

RSA系統也可用于生成電子簽名。基于RSA系統的電子簽名方案的原理一般可以被定義為三個部分：

-第一部分是利用之前描述的RSA系統的第一部分中所描述的方法生成RSA密鑰；

-第二部分是生成簽名。方法包括把要簽名的消息M作為輸入，利用函數μ對它應用編碼，以便得到字符串μ(M)，并應用上述RSA系統的第三部分的解密方法。因此只有擁有所述專用密鑰的用戶能夠生成簽名；

-第三部分是簽名的驗證。方法包括把要簽名的消息M以及要驗證的簽名s作為輸入，利用函數μ對消息M應用編碼，以便得到字符串μ(M)，對簽名s應用在RSA系統的第二部分中描述的加密方法，并驗證得到的結果等于μ(M)。在這種情況下，消息M的簽名s有效，反之則是錯誤的。