[發明專利]一種基于超對數難題的輕量級數字簽名方法

有效

• 申請號: 201110297654.1
• 申請日: 2011-10-08
• 公開（公告）號: CN102307102A
• 公開（公告）日: 2012-01-04
• 發明（設計）人: 蘇盛輝;呂述望;蔡吉人
• 申請（專利權）人: 蘇盛輝;呂述望;蔡吉人
• 主分類號: H04L9/32
• 分類號: H04L9/32;H04L9/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

(一)技術領域

公開密鑰數字簽名方法(簡稱數字簽名方法或數字簽名方案)屬于密碼技術和計算機技術領域，是電子金融安全、電子商務安全、電子政務安全、信息安全、身份認證和可信計算的核心技術之一。

(二)背景技術

數字簽名技術是密碼技術的擴展。密碼技術的發展經歷了古典密碼技術、對稱密碼技術和公鑰密碼技術三個階段。1976年，美國學者Diffie和Hellman提出公鑰密碼的思想，標志著公鑰密碼技術的來臨。目前，普遍使用的公鑰密碼技術有RSA和ElGamal等方案(參見《應用密碼學》，美國Bruce?Schneier著，吳世忠、祝世雄等譯，機械工業出版社，2000年1月，第334-342頁)，它們既可用于數據加密，也可用于數字簽名。為了縮短參數長度，ElGamal方案常在橢圓曲線上模擬實現，此時，它被稱為ECC方案。另外，我國學者陶仁驥教授曾提出了FAPKC1、FAPKC3方案(參見《計算機學報》，1985(n11)，pp.401-409)。另外，本發明作者之一蘇盛輝博士于2001年提出了REESSE1公鑰加密與數字簽名方案(參見《計算機工程與科學》，2003(n5)，pp.13-16)。

RSA和ElGamal等方案均是美國人發明的。它們的安全性分別基于大整數分解難題(IFP)和離散對數難題(DLP)，即在有限或有效的時間或空間內，對大整數進行因式分解或求離散對數幾乎是不可能的。這是一種漸近安全。隨著計算機運行速度的提高，它們的安全參數已變得越來越大，極大地增加了加解密系統和數字簽名系統的運行時間。特別是將來量子計算機的出現，使得大數因式分解和離散對數求解可以在多項式時間內實現，這對RSA、ElGamal和ECC體制構成了本質威脅。

同時，由于種種原因，FAPKC3和REESSE1公鑰體制在實踐中并沒有真正用起來。

(三)發明內容

數字簽名技術用于電子金融、電子商務和電子政務中主客體身份的認證、傳輸內容的不可抵賴性和傳輸內容的防修改性，不僅可以在網絡空間中使用，也可以在現實世界中使用。

本發明希望我們國家在輕量級公鑰數字簽名領域能夠擁有自己的核心技術，以確保國家的信息安全、經濟安全和主權安全，同時提高我國防范票據欺詐、證書欺詐、金融欺詐和商品欺詐的技術手段。

限于篇幅，本節內容略去了對有關性質和結論的證明，如果需要補上，我們將立即呈交。

在本文中，乘法運算“x×y”簡寫成“xy”，“％”代表模運算mod，“gcd(x，y)”代表最大公約數，“||x||”代表x％M的階，代表比特的求反，“←”表示變量的賦值，“≡”表示兩邊對模數求余相等，表示任意選取，“∈”表示左邊變量的值屬于某個區間或集合，“x|y”表示x整除y，表示x不能整除y，代表取x的上整數，lgx表示x對2求對數，hash(F)代表消息F的摘要，hash被稱為單向散列函數，從公開資料可以獲得。

3.1三個基本概念

令M為一正素數、n為一正整數。這里，M為模數，n為序列的長度。

3.1.1互素序列

定義1：假設A₁，...，A_n＞1是n個兩兩不同的整數，且滿足gcd(A_i，A_j)＝1或者gcd(A_i，A_j)＝H≠1，而有和則稱這些整數為一個互素序列，記為{A₁，...，A_n}，簡記為{A_i}。

性質1：如果從{A₁，...，A_n}中隨機選取m∈[1，n]個元素，構造一個子序列或子集{Ax₁，...，Ax_m}，那么，子集積

G=Πi=1mAxi=Ax1...Axm]]>