一種基於超對數難題的輕量級數字籤名方法
2023-05-01 03:47:21 1
專利名稱：一種基於超對數難題的輕量級數字籤名方法
技術領域：
公開密鑰數字籤名方法(簡稱數字籤名方法或數字籤名方案)屬於密碼技術和計算機技術領域，是電子金融安全、電子商務安全、電子政務安全、信息安全、身份認證和可信計算的核心技術之一。
背景技術：
數字籤名技術是密碼技術的擴展。密碼技術的發展經歷了古典密碼技術、對稱密碼技術和公鑰密碼技術三個階段。1976年，美國學者Diffie和Hellman提出公鑰密碼的思想，標誌著公鑰密碼技術的來臨。目前，普遍使用的公鑰密碼技術有RSA和ElGamal等方案 (參見《應用密碼學》，美國Bruce khneier著，吳世忠、祝世雄等譯，機械工業出版社，2000 年1月，第334-342頁)，它們既可用於數據加密，也可用於數字籤名。為了縮短參數長度， ElGamal方案常在橢圓曲線上模擬實現，此時，它被稱為ECC方案。另外，我國學者陶仁驥教授曾提出了 FAPKCl、FAPKC3方案(參見《計算機學報》，1985 (nil), pp. 401-409)。另外，本發明作者之一蘇盛輝博士於2001年提出了 REESSE1公鑰加密與數字籤名方案(參見《計算機工程與科學》，2003 (n5)，pp. 13-16)。RSA和EWamal等方案均是美國人發明的。它們的安全性分別基於大整數分解難題(IFP)和離散對數難題(DLP)，即在有限或有效的時間或空間內，對大整數進行因式分解或求離散對數幾乎是不可能的。這是一種漸近安全。隨著計算機運行速度的提高，它們的安全參數已變得越來越大，極大地增加了加解密系統和數字籤名系統的運行時間。特別是將來量子計算機的出現，使得大數因式分解和離散對數求解可以在多項式時間內實現，這對RSA、ElGamal和ECC體制構成了本質威脅。同時，由於種種原因，FAPKC3和REESSE1公鑰體制在實踐中並沒有真正用起來。
發明內容
數字籤名技術用於電子金融、電子商務和電子政務中主客體身份的認證、傳輸內容的不可抵賴性和傳輸內容的防修改性，不僅可以在網絡空間中使用，也可以在現實世界中使用。本發明希望我們國家在輕量級公鑰數字籤名領域能夠擁有自己的核心技術，以確保國家的信息安全、經濟安全和主權安全，同時提高我國防範票據欺詐、證書欺詐、金融欺詐和商品欺詐的技術手段。限於篇幅，本節內容略去了對有關性質和結論的證明，如果需要補上，我們將立即呈交。在本文中，乘法運算「χ X y」簡寫成「xy 」，「 %，，代表模運算mod，「gcd (X，y)，，代表最大公約數，「 11X11，，代表M的階，％，，代表比特的求反，「一」表示變量的賦值，「E」表示兩邊對模數求餘相等，「V」表示任意選取，「 e，，表示左邊變量的值屬於某個區間或集合， 「χ I y」表示χ整除ι, 「χ t/』表示χ不能整除ι,「χ 代表取χ的上整數，Igx表示χ對2求對數，hash(F)代表消息F的摘要，hash被稱為單向散列函數，從公開資料可以獲得。3. 1三個基本概念令M為一正素數、l、n為一正整數。這裡，M為模數，η為序列的長度。3. 1.1互素序列定義1 假設A1,. . .，Αη > 1是η個兩兩不同的整數，且V為、Aj {i力)滿足gccKA^ Aj) = 1 或者 gcd (Ai5Aj) =H^ 1,而 VA:本 U j e [1, 」]有/ H) \ ▲和(々 / H) \ ▲，則稱這些
整數為一個互素序列，記為{A1; . . .，AJ，簡記為{AJ。性質1:如果從{A1;...，An}中隨機選取me [1，η]個元素，構造一個子序列或子集{ΑΧι，...，Α、}，那麼，子集積G = Π 二 A= Α·.· Α 被唯一地確定，即從G到{AXl，... , AxJ的映射是一對一的。證明略。3. 1.2槓桿函數定義2 對於素域Gffl (M)上的公鑰數字籤名體制，密鑰變換式中的參數1 (i)被稱為槓桿函數，如果它具有下列特性①1(.)是一個單射函數，其定義域為[l，n]，值域Ω為(1，Μ)的子集，這裡η<Μ;②i和1 (i)之間的映射被隨機確定，且不存在任何顯性的從1 (.)到公鑰的映射；③當試圖從公鑰提取私鑰時，任何敵手不得不考慮Ω中元素的所有排列；④當解密或數字籤名時，私鑰擁有者只需考慮Ω中元素的累加和。顯然，{l(i)}是在「公開」一端計算量大，在「私有」一端計算量小，它正好起到了 「槓桿」的作用。性質2(1(.)的不確定性)令/(Oe Λ C{1, ...,j0},Ci^Aiff1(i)(%M) (i = 1,..., η)，則W e(l』 場和Vx、少、ζ e [1, /7]附帶 ζ 乒 x、y，有①當ι (χ) +ι (y) = ι (ζ)時，有Φ)+ww+iiy)+_丨 * m + \m (% 場；②當1 (χ) +1 (y)興1 (ζ)時，總存在Cx = A' xff' (x\Cy = A' yff' (!°和(；三六'zff' (z)(% M)滿足+m ^ m (%碭且A' z彡P，這裡P是互素序列中被允許的最大素數。證明略。3. 1. 3超對數難題定義3:已知ye [1，M_1]，求χ <M滿足同餘方程y Ε χχ(% Μ)被稱為超對數難題(Transcendental Logarithm Problem, TLP)。性質3 =TLP在計算難度上至少等價於同一素域中的DLP。證明見 Asymptotic Granularity Reduction and Its Application 一文 (Theoretical Computer Science, vol. 412(39), Sep. 2011, pp.5374-5386. Shenghui Su, Shuwang Lii, and Xiubin Fan)。3. 2本發明的技術方案注意在本文中，序列{A1; A2, .... , AJ有時簡寫成{AJ，序列IC1, C2, ... , Cj有時簡寫成{CJ，槓桿函數{1(1),1(2),...,1 (η)}有時簡寫成{1⑴}。本發明是一種基於超對數難題的輕量級公鑰數字籤名方法，簡稱JUNA輕量級數字籤名方法。輕量級數字籤名方法具有模數長度較短、計算量較少、運算速度較快、但安全性仍滿足應用需求等特點。根據該方法，可製造密鑰生成晶片、數字籤名晶片和身份驗證晶片，或開發密鑰生成軟體、數字籤名軟體和身份驗證軟體等。因此，本發明是一種生產數字籤名產品所必須遵循的基本原理與技術方案，而不是物理產品本身。本技術方案，由密鑰生成、數字籤名和身份驗證等三部分組成。3. 2. 1數字籤名與身份驗證操作本文中，把待籤名的文件或數據叫消息，把籤名輸出叫名鑑。假設用戶V欲通過網絡向用戶U發送一個自己籤名的消息，並由U驗證被籤名的消息。V與U欲實現這麼一個籤名與驗證構思，其過程如下密鑰生成首先，用戶V去第三方權威機構，即CA證書中心(Certificate Authentication)領取由密鑰生成部件輸出的一對私鑰(Private Key)與公鑰(Public Key)，私鑰必須由V自己保管，不得外洩；公鑰則允許以公鑰證書的形式向外界公開發放， 以便於驗證名鑑時使用。數字籤名操作用戶V在數字籤名部件上用自己的私鑰對消息進行籤名，得到名鑑，並將名鑑附在消息之後發送給用戶U。身份驗證操作用戶U從CA認證中心獲得用戶V的公鑰證書，在身份驗證部件上用V的公鑰對名鑑進行驗證，以確定它是否為V的名鑑。3. 2. 2輕量級密鑰生成部分在本方法中，
權利要求
1. 一種基於超對數難題的輕量級數字籤名方法，由密鑰生成、數字籤名和身份驗證三個部分組成，第一部分用來生成發送方的一對私鑰和公鑰，第二部分供發送方使用自己的私鑰對消息進行籤名，第三部分供接收方使用發送方的公鑰來驗證名鑑，假設T、￡)、d是兩兩互素的整數、hash是一單向散列函數，其特徵在於 密鑰生成部分採用了下列步驟1)隨機產生互素序列{A1;. . .，AJ且每個Ai < P2)找到一個素數M滿足想Γ|Μ, gcd(r, Ml Τ)3)隨機選擇S—1彡5為小整數且gcdCS—1,M)=\, 隨機選擇W，δ使得gcd(<5，Μ) = 1且· = ΒΤ4)隨機選取1 (1)，· · ·，1 (n) e Ω 且▽"_/，有 1 (i)興 1 (j)5)計算《—妒"+ 1)r % Μ, β— 5W"T % M，h 、 、H)為私鑰，({CJ、a、β)為公鑰，η、S、Τ、M 共用； 數字籤名部分採用了下列步驟發送方以自己的私鑰({AJ、{l(i)}、W、δ、￡)、d、η)作為籤名密鑰，針對消息F做(1)令H— hash (F)，其二進位形式是bp · · bn(2)置次—δΣ^Α )% Μ, Go <- (Π^.^ΓΥ % M(3)選擇<5e (1，詢使得(S7)丨財時t (WQ) % Μ, 其中，β S α{Βδ~χ) + WHd'1 (% Μ).(4)計算i <- (Q(0hyYsG0-\ —￡<- SaD % Μ, ξ<τ- (SQ)"'1-'(NW)' % M(5)任選re[1，cf216]使得+ {r+Wn-')US) % M,其中，(6)若^擬爐⑵—+^^+爐「穴「^^/^駭轉至(5)最後，得到名鑑⑴、U)，其可附在消息F後面發送給接收方； 身份驗證部分採用了下列步驟接收方以發送方的公鑰(ICJ、α、β)作為驗證密鑰，針對消息F和名鑑(Q、U)做①令H— hash (F)，其二進位形式是bp . . bn②計算GeFHL1C/'% M③計算{aQ-xfmaQn% Μ, Y^- {GQirx)USTp(Q"'X + US)H+H「 % M④若XE Y，則籤名者身份正確且F未被修改， 否則，籤名者身份無效或者F在傳輸已被修改。
全文摘要
一種基於超對數難題的輕量級數字籤名方法，屬於密碼技術和計算機技術領域；包括密鑰生成、數字籤名和身份驗證三個部分；其發送方用戶擁有兩個密鑰，即一個私鑰和一個公鑰，且從公鑰不能推導出私鑰；發送方的私鑰用於生成消息的名鑑，發送方的公鑰用於接收方驗證相應消息的名鑑；該方法能有效抵禦現有分析手段的攻擊，具有模長小於96比特、計算速度快、技術可公開等特點，可用於手機、計算機和通信網絡中任何消息的籤名與驗證，也可用於電子金融、電子商務、電子政務中的身份認證與內容確認，還可用於票據、證書和高檔商品的防偽。
文檔編號H04L9/30GK102307102SQ20111029765
公開日2012年1月4日 申請日期2011年10月8日 優先權日2011年10月8日
發明者呂述望, 蘇盛輝, 蔡吉人 申請人:呂述望, 蘇盛輝, 蔡吉人