兩種分布式SM2/9 算法應用*

涂彬彬, 王現方, 張立廷

成都衛士通信息產業股份有限公司 摩石實驗室, 北京100070

1 介紹

2010 年, 國家密碼管理局發布了SM2 橢圓曲線公鑰密碼算法標準[1], 包括數字簽名算法、密鑰交換協議和公鑰加解密算法. 2016 年, 國家密碼管理局發布了SM9 標識密碼算法標準[2], 包括數字簽名算法、密鑰交換協議、密鑰封裝算法和加解密算法. 目前, SM2 和SM9 的數字簽名算法均已成為ISO/IEC 國際標準. 作為我國發布的首個公鑰密碼算法和標識密碼算法標準, SM2 和SM9 算法對我國商密領域各類信息系統的安全防護發揮了重要作用.

密鑰是密碼算法的核心信息, 其生成、分發、存儲、銷毀等機制需要專門設計和管理. SM2 算法[1,3]的私鑰完全由單個用戶掌握, 保障了簽名操作的不可否認性, 但同時面臨私鑰丟失、權限濫用或被攻擊者控制等安全風險. SM9 算法[2,4]的密鑰生成中心(Key Generation Center, KGC) 秘密保存系統主私鑰,用于生成所有用戶的標識私鑰, 在應用過程中同樣面臨單點故障的風險和問題, 難以滿足物聯網、云計算等應用場景對密碼系統的健壯性需求.

在SM2 算法應用方面, 林璟鏘等[5]針對兩方分布式應用場景, 設計了適用于云計算的SM2 協同簽名機制. 其基本思想是將SM2 私鑰分割成兩部分, 分別存儲于云端和終端, 簽名操作需要云端和終端協同完成, 從而避免了全部私鑰存儲于終端而導致的安全風險. 隨后, 針對不同的應用場景和需求, 涌現出多個此類SM2 簽名機制[6-16]. 2020 年, Yudi Zhang 等[17]提出了基于同態加密的SM2 協同簽名算法, 并給出了可證明安全保障. 然而, 此類機制要求全部參與方必須在線協同操作, 任何一方故障都會導致簽名失敗, 整個系統健壯性較弱; 在一些無可信中心的分布式場景中, 比如比特幣、以太坊等, 任何一方丟失私鑰都將導致簽名無法執行.

(n,t) 門限化分布式設計可有效避免該問題[18,19]. 簽名操作只需要任意t,t ＜n個參與方在線完成,部分參與方故障掉線不會影響系統的可用性; 對于部分參與方私鑰丟失, 任意t個參與方可為其恢復密鑰. 在該技術方向上, 尚銘等[19]首先提出了SM2 算法的分布式門限化設計, 基于聯合隨機秘密分享技術(Joint Random Secret Sharing, JRSS)[20,21]和秘密乘積、求逆、點乘分享技術, 設計了SM2 門限密碼算法, 可抵抗n/2 的竊聽攻擊和n/3 的中止攻擊(其中n為參與方總數). 但是該方案通信量較大, 且無法達到最優門限值. 在簽名階段, 該方案需要各個參與方兩兩通過安全信道進行交互, 每個參與方需要給其它參與方秘密傳輸信息; 對于門限值為t的門限簽名算法, 至少需要2t ?1 個參與方進行協同簽名. 而SM9 密鑰生成中心的分布式門限化設計更是鮮有成果.

SM2 簽名算法和SM9 密鑰生成的分布式設計的主要技術難點在于, 私鑰分割后如何安全有效地實現標準算法的既定功能. 在SM2 簽名算法分布式設計中, 難點集中在多個用戶協同計算私鑰的逆, 以及私鑰與隨機數的乘積; 在SM9 密鑰生成的分布式設計中, 難點集中在多個KGC 協同計算主私鑰的逆. 在該技術方向上, 尚銘等[19]根據秘密分享[21]思想所實現的安全多方計算方法[20,22], 在保證多個用戶安全協同計算乘積和求逆的前提下, 完成了多用戶協同簽名操作. 通過安全多方計算思想增強SM2 和SM9 密碼系統的健壯性已經成為業內共識, 但如何優化相關技術, 設計通信效率較高、門限值最優的分布式密碼方案, 提升SM2 和SM9 密碼系統的可用性, 仍然是密碼實踐中亟待探索解決的問題之一.

2 本文工作

本文針對國密SM2 和SM9 算法的單點密碼運算容易導致系統健壯性不強的問題, 嘗試設計分布式門限化的SM2 簽名算法和SM9 密鑰生成算法.

首先, 我們研究多方安全計算技術, 調研了“乘積” 等基本運算的實現方法, 歸納其優缺點. 基于Shamir 秘密分享[21]的多方計算乘積[20,22], 各個參與方首先需要秘密協商隨機多項式, 再通過多項式相乘計算秘密乘積, 最后使用拉格朗日插值公式恢復秘密乘積. 該方法難以避免多項式次數的擴張, 在恢復秘密乘積時, 門限值無法達到最優. 而基于加法同態加密多方計算乘積[23,24], 各個參與方首先對秘密進行加密, 再利用加法同態運算和數乘運算計算乘積的密文, 最后使用解密運算獲得秘密分享的乘積結果. 該方法避免了多項式擴張, 對于門限值為t的秘密分享, 只需獲得t個份額即可恢復乘積結果, 可達到最優門限值. 在密文狀態下進行秘密乘積運算, 各個參與方可通過廣播信道向其他用戶傳輸信息, 產生的通信開銷較少. 但是該方法采用了同態加密技術, 計算復雜度略高.

其次, 我們歸納了三種安全多方計算方法, 分別是基于門限加法同態加密算法[23,24]、基于多個加法同態加密算法和基于單一加法同態加密算法的安全多方計算. 三種方法都可實現多個參與方的乘積和求逆運算, 適用于多數密碼算法的分布式設計. 在此類設計中, 首先將密碼算法拆解為乘積和求逆運算的組合, 再結合三種方法進行模塊化的分布式設計, 從而提升密碼系統的健壯性. 借助加法同態加密的優勢, 得到的門限化密碼方案可在廣播信道傳輸信息, 通信量較小; 同時在門限化密碼設計中有能力達到最優門限值. 在安全分析方面, 門限化密碼方案的安全性可歸約到密碼方案自身的安全性和三種安全多方計算方法的安全性. 此外, 針對基于多個同態加密算法的安全多方計算(第二種方法), 我們可以進一步提升方案健壯性. 具體地, 利用非交互零知識證明[25-27]對傳輸信息進行可驗證性擴展, 保證不按照正確協議運行的參與方能夠被及時發現.

然后, 我們基于上述三種安全多方計算方法, 設計了分布式門限化的SM2 簽名算法和SM9 密鑰生成算法, 并根據門限化SM2 和SM9 算法特點進行了優化, 在保證安全實現密碼算法功能性的同時, 算法更加高效實用.

SM2 簽名形式可拆分為私鑰sk 的求逆運算(1 + sk)?1, 以及求逆分享與隨機數的乘積運算(1 +sk)?1·(k ?r·sk). 根據上述三種方法, 參與方先進行求逆運算, 獲得(1+sk)?1的求逆分享, 再根據乘積運算, 計算簽名s= (1+sk)?1·(k ?r·sk) 的乘積分享. 各方通過公開s的乘積分享即可組合出簽名結果. 根據文獻[19] 對SM2 的簽名變形s=d·(k+r)?r, 其中d= (1+sk)?1, 可優化SM2 簽名算法,簽名過程只需要多方的乘積運算, 減少了協議運行的廣播輪數.

SM9 用戶標識私鑰可拆分為私鑰sk 的求逆運算(h+sk)?1, 以及求逆分享與私鑰的乘積運算[sk·(h+sk)?1]P1, 根據上述三種方法, 參與方先進行求逆運算, 獲得(h+sk)?1的求逆分享, 再根據乘積運算,多方計算sk·(h+sk)?1的乘積分享. 各方將乘積分享點乘P1,并秘密傳輸給用戶,用戶求和即可獲得標識私鑰. 根據橢圓曲線上倍點可疊加的性質,各方在計算獲得(h+sk)?1的求逆分享后,計算[(h+sk)?1]P1,并通過分別向用戶秘密傳輸私鑰與[(h+sk)?1]P1的乘積, 用戶求和即可獲得標識私鑰. 該優化方案所需的乘積運算量較小, 協議運行的廣播輪數較少.

3 安全多方計算的定義與模型

從1982 年姚期智先生在FOCS ’82 會議上提出并研究的“百萬富翁” 問題開始, 安全多方計算(Multi-party Computation, MPC) 技術[22,23,28-30]以其強大的功能性和豐富的應用性, 特別是在分布式密碼算法設計方面具有得天獨厚的優勢, 深得密碼學家的廣泛關注與研究. 安全多方計算可保證n個參與方集合A={A1,··· ,An}, 計算某個給定的n個輸入和n個輸出的功能函數f(x1,··· ,xn) =(y1,··· ,yn), 其中,n個輸入x1,··· ,xn分別由n個參與者A1,··· ,An秘密掌握, 在計算結束后,A1,··· ,An分別得到輸出y1,··· ,yn. 計算結束后每個誠實的參與方都能得到正確的輸出, 同時還可保證各個參與方輸入的保密性, 即每個參與方除了知道(xi,yi) 以及從中推導的信息外, 得不到其他的信息.

安全兩方計算(Two-party Computation, TPC) 是安全多方計算的特殊情況. 具體參與方只有兩個,雙方根據自己秘密掌握的信息x1和x2進行某個功能函數的運算f(x1,x2) = (y1,y2), 并且在計算結束后各方除了知道自己的輸入和輸出以及從中推導的信息外, 得不到其他的信息.

一般而言, 確定性功能函數可分解為基本的三種運算組件: 加法運算、乘法運算和求逆運算. 三種運算模型的安全兩方計算可簡單表示如下: 參與方A和B分別擁有s和r的分享(s1,r1) 和(s2,r2), 其中s=s1+s2,r=r1+r2.

· 加法運算:A和B通過加法運算協議分別獲得s+r的分享a1和a2, 使得a1+a2=s+r;

· 乘法運算:A和B通過乘法運算協議分別獲得s·r的分享m1和m2, 使得m1+m2=s·r;

· 求逆運算:A和B通過求逆運算協議分別獲得s?1的分享i1和i2, 使得i1+i2=s?1.

上述計算模型中, 最后組合計算結果的方法采用加法形式只是為了方便表示, 其它的安全組合方式計算最后結果也可行. 在加法運算中,A和B可通過本地計算a1=s1+r1和a2=s2+r2獲得各自的秘密分享, 該模型比較簡單, 以下省略. 求逆運算可看作乘法運算的推廣. 因此, 實現安全乘法運算是安全多方計算的關鍵.

本文歸納的安全多方計算協議采用的通信模型是同步的廣播信道[23]. 另外, 為了方便, 以下省略modp運算.

4 三種實現安全乘法運算的基本方法

本節歸納了三種安全乘法運算方法, 分別是基于門限加法同態加密的乘法運算、基于多個加法同態加密的乘法運算、基于單個加法同態加密的乘法運算. 根據具體協議設計, 我們對協議進行優化, 減少了協議運行的廣播輪數. 基于多個加法同態加密的乘法運算方法, 我們采用非交互零知識證明技術, 保證協議參與雙方傳輸的信息可被對方驗證. 我們在附錄A 中詳細地給出了三種安全乘法運算的安全性證明.

4.1 基于門限同態加密的乘法運算

基于(2,2)-門限加法同態加密[32,33]構造安全兩方計算的乘法運算(TPC-1-Multi)[23,24], 其中參與方數量n= 2, 門限值t= 2. 假設E() 和D() 分別表示門限同態加密算法的加密算法和解密算法. 門限加法同態加密算法滿足加法同態運算E(m1)⊕E(m2) =E(m1+m2), 數乘運算u ?E(m) =E(u·m),以及門限解密運算, 即參與方的解密分享數量達到門限值才可組合出明文. 具體協議如下:

·A計算E(s1) 并公布;B計算E(s2) 并公布;

·A選擇隨機數u1, 計算E(r1(s1+s2)+u1) 并公布;B隨機選擇u2, 計算E(r2(s1+s2)+u2)并公布;

·A和B分別解密密文c=E(r1(s1+s2)+u1)⊕E(r2(s1+s2)+u2) =E(s·r+u1+u2), 并公布各自的解密分享DA(c) 和DB(c);

·A組合解密分享獲得明文s·r+u1+u2, 并計算乘積分享m1=s·r+u1+u2?u1=s·r+u2;B計算乘積分享m2=?u2.

第一輪廣播中, 雙方公布E(s1) 和E(s2) 在計算意義下不泄露秘密信息. 因此, 雙方可通過本地預存對方的密文E(s1) 和E(s2), 減少一輪廣播. 此外, 根據門限加密的性質,A和B可采用門限加密的組合算法計算s·r, 則A和B可不用選擇u1和u2, 在第二輪分別公布E(r1(s1+s2)) 和E(r2(s1+s2)), 然后各自計算密文c=E(s·r) 并計算解密分享DA(c) 和DB(c) 作為s·r的分享, 可減少一輪廣播. 采用非交互的門限加法同態加密算法[34]可保證最后組合乘積結果不需要參與方之間的交互. 根據協議優化過程, 各參與方對所有輸入信息進行密態操作, 門限加密方案的安全性可保證各個參與方輸入信息的安全性.

基于門限同態加密的乘法運算, 可通過增加一輪廣播, 擴展至求逆運算(TPC-1-Inv), 此處使用優化后的乘法運算協議, 使用組合算法作為計算乘積結果的方式, 具體協議如下:

4.2 基于多個同態加密的乘法運算

基于多個加法同態加密[34]構造安全兩方計算的乘法運算(TPC-2-Multi). 假設E1() 和E2() 表示分別使用A和B的公鑰進行加密,E1() 和E2() 滿足加法同態運算和數乘運算.

4.3 基于單個同態加密的乘法運算

基于單個加法同態加密[34]構造安全兩方計算的乘法運算(TPC-3-Multi). 假設E() 表示使用A的公鑰進行加密(E() 可以使用任何參與方的公鑰加密, 此處為方便選擇A).E() 滿足加法同態運算和數乘運算. 具體協議設計如下:

·A選擇隨機數u1, 計算E(s1),E(r1),E(u1) 并公布;

·B選擇隨機數u2,v2,w2,計算E((s1+s2)·v2),E(r·w2),E(u·v2·w2),其中r=r1+r2,u=u1+u2并公布;

·A解密并計算(s1+s2)·v2·r·w2·(u·v2·w2)?1=(s1+s2)·r·u?1并公布;

1923年7月，蔡元培偕夫人周養浩(1892—1975)和子女再度赴歐洲學習考察，先居住于比利時布魯塞爾，次年1月移居法國。1924年8月，蔡元培自法國赴荷蘭、瑞典參加一個關于哥倫布未發現新大陸之前美國民族問題的國際民族學會議，巧遇但采爾。此時，但采爾已從萊比錫大學博士畢業，在漢堡大學做教授。

·A計算分享m1=(s1+s2)·r·u?1·u1;B計算分享m2=(s1+s2)·r·u?1·u2.

根據上述協議, 參與雙方分別公布最后分享進行加法運算s·r= (s1+s2)·r·u?1·u1+(s1+s2)·r·u?1·u2, 則u1和u2信息公開, 但是并不影響雙方輸入信息(s1,r1) 和(s2,r2) 的安全性. 因此, 可優化協議如下: 在第一輪廣播中A只公布E(s1),E(r1), 在第二輪廣播中B選擇隨機數v2,w2, 計算E((s1+s2)·v2),E(r·w2), 則A和B可分別計算秘密分享m1=(s1+s2)·v2·r·w2和m2=(v2·w2)?1;如此, 雙方以乘法形式代替加法形式計算最終結果, 可減少一輪廣播.

基于單個同態加密的乘法運算, 可通過增加一步廣播, 擴展至求逆運算(TPC-3-Inv), 具體協議設計如下:

上述三種安全兩方計算TPC-1/2/3 適用于兩方模型. 我們根據TPC-1/2/3 的具體性質, 在附錄B中將TPC-1/2/3 擴展至多方模型MPC-1/2/3, 并基于(n,t)-門限秘密分享方案[21], 對MPC-1/2 進行門限化擴展.

三種多方安全計算MPC-1/2/3 可保證多個參與方在不泄漏各自隱私數據的情況下, 完成多個參與方隱私數據的加法運算、乘積運算和求逆運算. 基于多方安全計算技術, 我們分別設計了分布式SM2 簽名算法[1,3,19]和分布式SM9 密鑰生成算法[2,4], 并根據具體協議給出方案優化.

5 SM2 簽名的分布式設計

本節給出SM2 簽名算法的分布式設計. 分布式SM2 簽名算法的驗證算法與原SM2 的驗證算法一致.具體參數參考SM2 標準算法[1,3], 為了方便, 省略算法中的編碼部分. SM2 簽名算法如下: 設用戶的簽名私鑰為sk,待簽名消息為m,用戶簽名過程如下: 用戶選擇隨機數k,計算(x1,y1)=[k]G,r=H(m)+x1,計算簽名結果(r,s=(1+sk)?1·(k ?r·sk)), 其中G是SM2 算法橢圓曲線上的參數點, [k]G表示橢圓曲線上的倍點運算,H表示雜湊算法SM3[35].

5.1 方案設計

5.2 方案優化

上述優化方案滿足兩方到多方, 再到門限化的擴展.d·k的運算不涉及簽名消息, 參與方可以離線操作, 進一步提高了在線協同簽名的效率. 參與方通過離線預存簽名所需準備信息, 在線簽名時各參與方甚至不需要交互, 直接可生成各自簽名分享, 用戶本地對簽名分享進行疊加, 即可獲得最終簽名. 優化方案的安全性建立于MPC-1/2/3-Multi 和MPC-1/2/3-Inv 協議的計算安全, 安全性證明類似引理A.1, A.2,A.3, 敵手攻擊參與方獲得的信息可被模擬器模擬.

5.3 方案效率分析與對比

基于三種安全多方計算的擴展, 我們可對SM2 簽名算法進行了分布式門限化設計, 并根據具體的算法進行優化改進. 通過對固定信息預存, 改進組合秘密的運算形式, 減少各個參與方的廣播輪數, 減少協議運行的通信量. 此外, 我們對尚銘等人[19]的SM2 門限簽名算法進行分析, 按照用戶數量為n, 門限值為t, 安全參數為k, 進行分析和對比. 具體的分析表1所示.

表1 方案效率與對比Table 1 Efficiency and comparison

6 SM9 密管中心分布式設計

6.1 方案設計

上述分布式SM9 密鑰生成中心滿足多方模型和門限化的擴展, 滿足MPC-2 的可驗證性擴展. 安全性建立于MPC-1/2/3-Multi 和MPC-1/2/3-Inv 協議的計算安全. 此外, 參與方A和B分別只拿到部分的標識私鑰, 完整的標識私鑰只有用戶自己掌握.

6.2 方案優化

6.3 方案效率分析

基于三種安全多方計算的擴展, 我們以模塊化的形式設計了三種分布式門限化的SM9 密鑰生成算法,并根據具體的算法設計進行了方案的優化改進. 通過對固定信息預存, 改進組合秘密的運算形式, 減少各個參與方的廣播輪數, 減少協議運行的通信量. 其中KGC 數量為n, 門限值為t, 安全參數為k, 具體的分析表2所示.

表2 方案效率Table 2 Efficiency of proposed schemes

7 總結

為提升國密算法在實際業務系統的健壯性和可用性, 本文通過歸納三種多方乘法運算及其擴展, 給出了SM2 簽名算法和SM9 密鑰生成算法的分布式門限化設計, 在較低通信量的條件下達到最優門限值. 但由于引入了同態加密運算, 方案的計算復雜度略高, 仍有待優化. 此外, 探索新型安全多方計算技術, 以合適的通信、計算復雜度實現國密算法的分布式設計, 將是未來密碼應用研究的熱點問題之一.