基于Shamir的動態強前向安全簽名方案

摘要：目前基于Shamir的數字簽名方案多數仍需可信中心參與子秘密（秘密份額）的分發，缺乏成員對群管理的反向監督，缺少強前向安全性。在這些問題的前提下，提出一種無可信中心參與、多個成員可定期更新私鑰，同時解決了成員加入和退出問題的方案。該方案由產生簽名、私鑰更新、成員加入和退出三個部分構成，涉及的運算主要有拉格朗日插值計算，有較為良好的時間復雜度，實現了去可信中心化，并在保持公鑰不變的情況下定期更新成員私鑰，實現成員加入退出，進而保證消息的完整性及強前向安全性。

關鍵詞：Shamir；拉格朗日插值；秘密共享方案；強前向安全；門限簽名方案

中圖分類號：TP309.2文獻標志碼：A

文章編號：1001-3695（2023）05-037-1522-06

0引言

隨著互聯網技術的不斷發展，數據完整性需求也在不斷提升，促使了數字簽名的廣泛應用，然而攻擊手段也層出不窮，私鑰被竊取使得數字簽名被竄改、偽造，導致簽名失去真實性，造成了嚴重后果。1997年Anderson［1］第一次提出前向安全概念，定義了T時段的私鑰如果被竊取，攻擊者也無法對T時段之前的私鑰進行計算，其核心在于私鑰的更新，保證系統前向安全。2001年Burmester等人［2］提出了強前向安全性的定義，該定義包含前向安全性和后向安全性定義，并對前向安全方案提出了前向安全性和后向安全性［1］；定義了更新后的私鑰如果泄露，攻擊者也不能偽造T+1時段的簽名，保證后向安全性，提升了簽名效率及安全性，避免了每當密鑰泄露時重構方案系統。強前向安全性的提出對設計數字簽名方案的安全性具有重大意義，國內外學者針對強前向安全性的數字簽名做了大量的工作，在這些工作中，圍繞著設計簽名方案的后向安全、去可信中心、成員加入與退出三個特性來進行。文獻［3］采用單向散列鏈技術，基于ElGamal體制使方案滿足后向安全性；文獻［4］在密鑰演化中加入后向元素，使方案滿足后向安全性；文獻［5］基于Guillou-Quisquater簽名體制和Rabin密碼體制，使方案滿足后向安全性；文獻［6］提出了基于身份短簽名具有雙向安全性的方案，該方案算法簡單且使方案滿足了后向安全性；文獻［7］使用單向散列函數，加入了成員驗證，使方案滿足后向安全性、去可信中心；文獻［8］采用雙線性映射以及ECDLP問題，結合中國剩余定理和強RSA，使方案滿足后向安全性、成員加入與退出；文獻［9］采用中國剩余定理，基于離散數學難題提出動態數字簽名方案，使方案滿足后向安全性、去可信中心、成員加入與退出。

在前向安全性與后向安全性的基礎上實現去可信中心的核心思路是秘密共享，將每一位成員作為密鑰分發中心，而在目前的研究中，去可信中心的數字簽名方案可以使用Shamir秘密共享，本文將針對現有的基于Shamir簽名方案中是否滿足設計簽名方案的三個特性進行研究。文獻［10］提出一種基于門限的ECDSA的定期可更新的比特幣密鑰管理方案，使方案滿足后向安全性、去可信中心，但并沒有滿足成員的加入與退出。現階段存在的Shamir簽名方案多數用來對方案的密鑰分發起作用，缺少強前向安全性和成員的加入與退出。文獻［11］使用Shamir并結合環簽名、文獻［12］結合SM2與Shamir提出的圖像加密算法、文獻［13］提出一種基于橢圓曲線的Shamir門限簽名體制，它們都使用了Shamir門限的特性但并未實現強前向安全性，也沒有去可信中心和成員加入與退出。在基于Shamir秘密共享［14］的強前向安全性數字簽名研究中，缺少完全滿足三個簽名特性的簽名方案，為解決以上問題，使得基于Shamir秘密共享方案滿足強前向安全性的三個特性。本文對現階段Shamir門限簽名方案進行改進，提出一種基于Shamir的動態強前向安全性簽名方案，使其無須可信中心，保證公鑰不變的情況下，T時間段更新一次成員私鑰，并實現成員的加入與退出操作，避免了可信中心權威欺詐、保證了方案前向安全與后向安全。

1相關工作

1.1強前向安全性

強前向安全性包括了前向安全和后向安全，其思想核心在于密鑰的更新，如圖1所示。前向安全是密碼學中通信協議的安全屬性，在長期使用的主密鑰被攻擊者竊取后，無法計算出之前的會話密鑰，前向安全保護之前的通信（簽名）不會受密碼或密鑰在未來竊取偽造的威脅，保證上一時段簽名信息安全。后向安全性是指長期使用的主密鑰被攻擊者竊取后，無法計算出之后即將生成的密鑰，攻擊者不可偽造和推算下一時段的密鑰信息，即不能通過密鑰偽造簽名，保證下一時段的成員密鑰和簽名安全。

1.2數字簽名

消息的接收者根據簽名確認發送者的身份信息，該部分由兩種算法組成［9］。

a）簽名算法。由系統內部成員（簽名者）所擁有，簽名成員使用私鑰進行簽名，簽名密鑰和簽名算法保密，以防止攻擊者的惡意攻擊。該算法的主要作用在于對消息進行簽名（消息摘要的hash值）。

b）驗證算法。由驗證者驗證系統內部成員簽名的真偽，通過算法校驗消息的數字簽名，驗證者通過公鑰驗證數字簽名，以判斷簽名人員的身份信息。

系統中簽名公鑰公開，私鑰由內部成員秘密保存，驗證者收到消息的簽名后，利用公鑰對現階段數字簽名進行驗證。數字簽名有以下幾個特性：

a）鑒權性。公鑰加密系統允許任何人在發送信息時使用公鑰進行加密，接收信息時使用私鑰解密。當然，接收者不可能百分之百地確信發送者的真實身份，只能在密碼系統未被破譯的情況下才有理由確信。

b）完整性。傳輸數據的雙方都希望確認消息未在傳輸的過程中被修改。加密使得第三方想要讀取數據十分困難，然而第三方仍然能采取可行的方法在傳輸的過程中修改數據。不同的消息根據簽名算法生成不同的數字簽名，并且帶有操作者的身份信息。因此，簽名是不能夠被偽造的，同時也是不能否認的。

c）不可抵賴性。數字簽名中都帶有簽名者的身份信息，為防止所有后續的抵賴行為。

d）不可偽造性。數字簽名計算算法中，使用數學難題使得攻擊者竊取私鑰方式困難，很難偽造數字簽名。

本文方案涉及的運算主要有拉格朗日插值計算、hash運算、模冪運算、模加運算、模減運算、模乘運算，因模加運算、模減運算與其他相比計算量較小可忽略不計，所以不進行分析，計算復雜度相應的大小順序為Fgt;egt;ggt;mgt;h。

本文方案、文獻［10，12，13］中生成簽名、簽名驗證和密鑰更新的對比復雜度如表4所示。由表4可知，本文對基于Shamir秘密共享的數字簽名方案［10，12，13］進行時間復雜度對比，本文方案生成簽名、簽名驗證以及密鑰更新的時間復雜度低于文獻［10］，其方案在生成簽名和驗證簽名階段引入同態加密與同態解密在原有的計算基礎上增加了開銷；文獻［12］在計算過程中引入雜湊數，算法計算開銷較大且沒有實現密鑰更新、去可信中心的功能；文獻［13］在簽名生成階段計算開銷小于本文方案，但在簽名驗證的計算開銷高于本文方案，并且其方案中未保證數字簽名的強前向安全性。

綜合分析，本文方案所涉及的運算及安全性相較于其他幾個方案算法更簡單，計算開銷更小。

5仿真實驗

本文方案仿真實驗環境為：Windows1064位操作系統、IntelCoreTMi5-6300HQ處理器2.30GHz、內存8GB、PyCharm2021、Python3.8。與本文方案具有相同的強前向安全性Shamir簽名的文獻［10，12］進行產生簽名計算時間開銷的對比，結果如圖4所示。

由圖4可知，本文方案、文獻［10，12］的時間開銷與成員數n的增加成正相關的關系，因為成員的增加導致成員產生的部分簽名時間開銷增加，但本文方案的時間開銷小于文獻［10，12］，因為文獻［10］在產生簽名的過程中使用了同態加密與同態解密運算，文獻［12］使用雜湊數，兩者計算復雜度均高于本文方案。

6結束語

本文在原有的Shamir門限秘密共享方案上進行修改，將成員動態可加入撤銷的思想加入方案中，現階段Shamir門限簽名方案多數沒有去可信中心、私鑰更新、成員加入和退出這幾個特點。本文將每個成員看做密鑰分發者，將自己所選擇的子秘密，通過自己選取的隨機參數分割給n個成員，并計算驗證參數，使得成員之間可以相互驗證廣播消息是否正確，由成員產生部分簽名合成簽名。現存多數方案仍需可信中心參與子秘密（秘密份額）的分發，缺乏成員對群管理的反向監督機制，管理中心很容易成為整個簽名系統的安全隱患。本文方案基于Shamir，實現了去可信中心化，并在保持公鑰不變的情況下定期更新成員私鑰，保證方案的前向安全和后向安全。

在接下來的研究中將進一步完善基于Shamir的私鑰更新模塊，實現方案運行更加便捷的成員部分私鑰更新，減少方案開銷的同時進一步提升效率。

參考文獻：

［1］AndersonR.Tworemarksonpublickeycryptology，UCAM-CL-TR-549［R］.

Cambridge：UniversityofCambridgeComputerLaboratory，2002.

［2］BurmesterM，ChrissikopoulosV，KotzanikolaouP，etal.Strongforwardsecurity［C］//ProcofIFIPInternationalInformationSecurityConfe-rence.Boston：Springer，2001：109-122.

［3］李順波，黃光球，彭家龍.一種前向安全數字簽名方案的分析及改進［J］.計算機技術與發展，2016，26（11）：93-96.（LiShunbo，HuangGuangqiu，PengJialong.Analysisandimprovementforadigitalsignatureschemeofforwardsecurity［J］.ComputerTechnologyandDevelopment，2016，26（11）：93-96.）

［4］LinDairui，WangCI，GuanDJ.Aforward-backwardsecuresignaturescheme［J］.JournalofQinghaiNormalUniversity，2016，26（1）：2319-2329.

［5］徐光寶，姜東煥，梁向前.一種強前向安全的數字簽名方案［J］.計算機工程，2013，39（9）：167-169.（XuGuangbao，JiangDonghuan，LiangXiangqian.Astrongforward-securedigitalsignaturescheme［J］.ComputerEngineering，2013，39（9）：167-169.）

［6］左黎明，胡凱雨，張夢麗，等.一種具有雙向安全性的基于身份的短簽名方案［J］.信息網絡安全，2018，211（7）：47-54.（ZuoLiming，HuKaiyu，ZhangMengli，etal.Ashortidentity-basedsignatureschemewithbilateralsecurity［J］.NetinfoSecurity，2018，211（7）：47-54.）

［7］廖小平，蔡光興.一種具有強前向安全性的數字簽名方案［J］.湖北工業大學學報，2011，26（2）：126-130.（LiaoXiaoping，CaiGuangxing.Astrongforwardsecurityofdigitalsignaturescheme［J］.JournalofHubeiUniversityofTechnology，2011，26（2）：126-130.）

［8］韋性佳，蘆殿軍.基于中國剩余定理的前向安全的聚合簽名方案［J］.計算機技術與發展，2021，31（4）：137-141.（WeiXingjia，LuDianjun.ForwardsecureaggregatedsignatureschemebasedonChineseremaindertheorem［J］.ComputerTechnologyandDeve-`lopment，2021，31（4）：137-141.）

［9］程亞歌，胡明生，公備，等.具有強前向安全性的動態門限簽名方案［J］.計算機工程與應用，2020，56（5）：125-134.（ChengYage，HuMingsheng，GongBei，etal.Dynamicthresholdsignatureschemewithstrongforwardsecurity［J］.ComputerEngineeringandApplications，2020，56（5）：125-134.）

［10］韓妍妍，徐鵬格，李兆斌，等.基于門限ECDSA的定期可更新的比特幣密鑰管理方案［J］.計算機應用與軟件，2021，38（9）：307-314，321.（HanYanyan，XuPengge，LiZhaobin，etal.AperiodicrenewingbitcoinkeymanagementschemebasedonthresholdECDSA［J］.ComputerApplicationsandSoftware，2021，38（9）：307-314，321.）

［11］高夢婕.基于區塊鏈的醫療健康數據共享機制研究［D］.南京：南京郵電大學，2020.（GaoMengjie.Researchonmedicalhealthdatasharingschemeusingblockchain［D］.Nanjing：NanjingUniversityofPostsamp;Telecommunications，2020.）

［12］譚亦夫，李子臣.基于Shamir門限秘密分享的圖像可視加密算法［J］.網絡與信息安全學報，2018，4（7）：69-76.（TanYifu，LiZichen.ImagevisualizationencryptionalgorithmbasedonShamirthresholdsecretkeysharing［J］.ChineseJournalofNetworkandInformationSecurity，2018，4（7）：69-76.）

［13］彭慶軍，李新平.一種基于橢圓曲線的Shamir門限簽名體制［J］.湖南理工學院學報：自然科學版，2008，21（2）：8-10.（PengQingjun，LiXinping.AShamirthresholdsignaturesystembasedonellipticcurve［J］.JournalofHunanInstituteofScienceamp;Techno-logy：NaturalSciences，2008，21（2）：8-10.）

［14］ShamirA.Howtoshareasecret［J］.CommunicationsoftheACM，1979，22（11）：612-613.

［15］林齊平.門限解密方案研究［J］.現代計算機（專業版），2008，291（9）：18-19.（LinQiping.Researchonthresholddecryptionscheme［J］.ModernComputer，2008，291（9）：18-19.）

［16］楊雪菲.數字簽名技術綜述［J］.電腦編程技巧與維護，2021，437（11）：7-9.（YangXuefei.Reviewoffiguresignaturetechnology［J］.ComputerProgrammingSkillsamp;Maintenance，2021，437（11）：7-9.）

［17］榮輝桂，莫進俠，常炳國，等.基于Shamir秘密共享的密鑰分發與恢復算法［J］.通信學報，2015，36（3）：64-73.（RongHuigui，MoJinxia，ChangBingguo，etal.KeydistributionandrecoveryalgorithmbasedonShamirsecretsharing［J］.JournalonCommunications，2015，36（3）：64-73.）

［18］林修慧，林昌露，黃可可，等.門限秘密分享中高效添加新參與者方案［J］.南京理工大學學報，2022，46（1）：98-103.（LinXiuhui，LinChanglu，HuangKeke，etal.Efficientschemeofregisteringnewparticipantinthethresholdsecretsharing［J］.JournalofNanjingUniversityofScienceamp;Technology，2022，46（1）：98-103.）

［19］田秀霞，張悅，顏赟成.秘密共享的發展與應用綜述［J］.上海電力大學學報，2022，38（1）：66-74，81.（TianXiuxia，ZhangYue，YanYuncheng.Areviewofthedevelopmentandapplicationofsecretsharing［J］.JournalofShanghaiUniversityofElectricPower，2022，38（1）：66-74，81.）

［20］黃曉暉，李俊峰，何云.一種基于群簽名密鑰協商算法的多方參與完整性驗證方案［J］.信息技術與信息化，2022，268（7）：102-105.（HuangXiaohui，LiJunfeng，HeYun.Amulti-partyparticipationintegrityverificationschemebasedongroupsigningkeynegotiationalgorithm［J］.InformationTechnologyamp;Informatization，2022，268（7）：102-105.）

［21］盧俊情.支持成員身份隱私的動態群簽名方案研究［D］.南京：南京信息工程大學，2022.（LuJunqing.Researchondynamicgroupsignatureschemesupportingmembershipprivacy［D］.Nanjing：NanjingUniversityofInformationScienceamp;Technology，2022.）

［22］張碩英.無證書群簽名方案及其應用研究［D］.煙臺：山東工商學院，2022.（ZhangShuoying.Researchoncertificatelessgroupsignatureschemeanditsapplication［D］.Yantai：ShandongTechnologyandBusinessUniversity，2022.）

［23］方圓.可否認的全動態群簽名方案［D］.重慶：重慶大學，2021.（FangYuan.Deniablefulldynamicgroupsignaturescheme［D］.Chongqing：ChongqingUniversity，2021.）

［24］范家幸.基于動態門限環簽名的分級匿名表決研究［D］.南京：南京郵電大學，2021.（FanJiaxing.Researchonhierarchicalanonymousvotingbasedondynamicthresholdringsignature［D］.Nanjing：NanjingUniversityofPostsamp;Telecommunications，2021.）