群論應(yīng)用舉例

組合群論在密碼學(xué)和電子商務(wù)的安全性中的應(yīng)用目錄第一章密碼學(xué)和電子商務(wù)的安全性………………1第一節(jié)密碼學(xué)概述………………1第二節(jié)電子支付系統(tǒng)的安全性…………………4第二章組合群論和密碼學(xué)…………4第一節(jié)基礎(chǔ)知識和背景…………4第二節(jié)密碼體制和密鑰交換協(xié)議………………7TOC\o"1-5"\h\z\o"CurrentDocument"[Wag84]公鑰密碼體制 72.2.2[Anshel93]密碼體制 9\o"CurrentDocument"2.2.3[Anshel-Anshel-Goldfeld]密鑰交換協(xié)議 9\o"CurrentDocument"2.2.4[Ko-Lee-Cheon]密鑰交換協(xié)議和密碼體制 11第三章組合群論在電子支票的多簽名體制中的應(yīng)用……………14第一節(jié)三方密鑰交換協(xié)議……14第二節(jié)基于辮群的多簽名體制方案…………15多簽名介紹……………163.2.2基于單向環(huán)同態(tài)的多簽名體制 173.2.3基于辮群的多簽名體制 18第一章密碼學(xué)和電子商務(wù)的安全性第一節(jié)密碼學(xué)概述信息安全是密碼學(xué)的基本要求，為了要達(dá)到這一點(diǎn)，密碼學(xué)始終涉及兩個(gè)方面的斗爭。其中一方（發(fā)送者）是設(shè)法對消息進(jìn)行加密，使得只能是具有特殊權(quán)利的人（接受者）才能夠接受和閱讀信息。而另一方則是盡力設(shè)法截獲信息，破譯密文，或者用修改以后的假信息欺騙接收者。在本文中，我們主要討論的是前一方，即考慮用何種方法能夠?qū)ο⑦M(jìn)行安全、有效且快捷的加密，保證消息的傳送。待加密的消息被稱作明文（plaintext），用某種方法偽裝消息并隱藏它的內(nèi)容的方法稱作加密（encryption），被加密以后的消息稱為密文，而把密文轉(zhuǎn)變成明文的過程稱為解密。加密體制中的加密運(yùn)算是由一個(gè)算法類組成，這些算法類的不同運(yùn)算可用不同的參數(shù)表示，不同的參數(shù)分別代表不同的算法，被稱作密鑰，密鑰空間是所有密鑰的集合。密碼體制一般是指密鑰空間與相應(yīng)的加密運(yùn)算結(jié)構(gòu)，同時(shí)還包括了明文和密文的結(jié)構(gòu)特征。在密碼體制的設(shè)計(jì)和評價(jià)中要考慮到以下一些基本原則：（1） 不可破原則，指該密碼體制在理論上或?qū)嶋H上是不可破解的。（2） 部分信息丟失不會(huì)影響整個(gè)系統(tǒng)的安全性。即硬件設(shè)備、加密算法或全部密文與部分明文這些信息的丟失不會(huì)危及整個(gè)系統(tǒng)的安全。（3） 與計(jì)算機(jī)、通信系統(tǒng)匹配原則。要求密碼系統(tǒng)不是獨(dú)立存在的，而可以在計(jì)算機(jī)或通信系統(tǒng)中使用。密碼體制發(fā)展到現(xiàn)在，已經(jīng)有了很多種不同的類型。但是從密碼體制所使用算法的分類上說，可以分為兩種。一種是利用了對稱算法，又稱作傳統(tǒng)密碼算法；另一種則是利用了公開密鑰算法。對稱算法是指加密密鑰和解密密鑰能夠互相推算出來，公開了一個(gè)也就相當(dāng)于公開另一方。因此對稱算法的密鑰只能由發(fā)送者和接收者兩方知道，他們必須事先商定好密鑰，這一點(diǎn)就涉及了密鑰交換協(xié)議。公開密鑰算法是指公開了加密算法E以后不會(huì)泄露解密算法D，因此和KK對稱算法相比，任何人都可以通過公開渠道(網(wǎng)絡(luò)或密鑰管理中心)已知他人的加密密鑰，把明文加密以后傳送給接收者，而只有擁有解密密鑰D的人才能夠K對密文解密。這在密鑰管理和消息的傳送方面更具有優(yōu)勢。另外，公開密鑰算法還可以運(yùn)用在數(shù)字簽名中。在目前應(yīng)用于實(shí)際生活比較廣泛的公鑰加密算法包含有RSA密碼體制和橢圓曲線密碼體制。RSA密碼體制：1979年，ShamirRivest和Adelman提出了第一個(gè)也是應(yīng)用最廣的公鑰密碼體制，即RSA體制。經(jīng)過20多年的密碼分析和攻擊，迄今為止，RSA被證明仍是安全的。設(shè)n=pq,p和q是兩個(gè)大素?cái)?shù)，a和b是兩個(gè)整數(shù)，定義密鑰空間為｛(n,p,q,a,b):n=pq,ab三1(mod申(n))｝。把n，b作為公開密鑰，而p，q，a，申(n)，作為秘密密鑰。整個(gè)加密算法就是y=E(x)=xbmodn，而解密算法K是D(y)=yamodn，由Euler定理知道，x=D(y)成立，上述解密的方法正確。KK由于RSA加密算法是指數(shù)運(yùn)算，因此當(dāng)密鑰越大時(shí)，計(jì)算速度越慢。RSA算法比通常的DES算法慢了1500倍。并且RSA的計(jì)算量很大，為了要達(dá)到較高的安全程度，RSA的密鑰位數(shù)比其它的密碼體制大的多，現(xiàn)在一般需要1024位的密鑰。所以一般對速度要求較高的數(shù)字簽名或智能卡中的身份驗(yàn)證不太使用RSA密碼體制，而采用其它較快的算法。橢圓曲線密碼系統(tǒng)就是其中的一種。橢圓曲線密碼系統(tǒng)：橢圓曲線密碼體制和RSA體制比較起來，所需要的密鑰量小，安全程度高，比如RSA密碼體制需要1024-bit的密鑰才能達(dá)到的安全程度，利用橢圓曲線只需要160比特位的密鑰就能夠保證同樣的安全(文獻(xiàn)⑨)，密鑰長度的減少同時(shí)帶來了計(jì)算速度的提高。即使是在剩余類環(huán)Z運(yùn)用離散對數(shù)而構(gòu)造的加密P系統(tǒng)的安全程度也要低于橢圓曲線，因此橢圓曲線系統(tǒng)不愧為一個(gè)性質(zhì)較好的密碼系統(tǒng)。橢圓曲線第一次運(yùn)用于公鑰密碼算法是在1985年NealKoblitz和V.S.Miller提出來的。他們并沒有提出新的算法，只是把橢圓曲線運(yùn)用到已存在的公鑰密碼算法中，比如說ElGamal加密算法。利用ElGamal思想構(gòu)造的橢圓曲線密碼體制如下顯示：首先是產(chǎn)生密鑰階段。Bob從Z中隨機(jī)選取充分大的整數(shù)k，隨后計(jì)算nB出橢圓曲線上的點(diǎn)P=kQ(Q是橢圓曲線上的適當(dāng)?shù)囊稽c(diǎn))，將k保密，作為秘BB密密鑰，并將P公開，作為公鑰。加密方法如下：如果Alice想把消息M(同樣是橢圓曲線上的一點(diǎn))發(fā)送給Bob，就從Z中隨機(jī)選擇整數(shù)lgZ后，計(jì)算出S=IQ和S=M+IP的值，加nn12密以后的信息就是橢圓曲線上兩點(diǎn)(S,S)。12解密：Bob收到加密信息(S,S)后，通過密鑰k就可以計(jì)算M=S-kS12B2B1得到消息M。縱觀上面提出的兩個(gè)公鑰密碼體制，再加上其它的密碼系統(tǒng)，在加密的時(shí)候都采用了單向函數(shù)的思想。單向函數(shù)是指函數(shù)f滿足從x計(jì)算f(x)容易，但從f(x)計(jì)算x有可能不可行。單向函數(shù)的構(gòu)造依賴于計(jì)算復(fù)雜度理論，即利用一些困難問題。上述兩個(gè)系統(tǒng)的安全性都依賴于一些數(shù)論中的基本困難問題。比如說RSA體制利用了把大整數(shù)n分解為兩個(gè)大素?cái)?shù)的難度，而橢圓曲線是利用了求解離散對數(shù)問題的困難程度，(即根據(jù)P=kQ和Q求解Z中整數(shù)k)。這些BnB密碼體制都是很成功的，在實(shí)際中也有了進(jìn)一步的應(yīng)用。對于本文來說，我們的主要目的是把組合群論的思想引進(jìn)到密碼學(xué)中，所以利用了組合群論中的一些困難問題，如字問題，共軛問題等等，由此構(gòu)造出新的密碼體制。協(xié)議(protocol)是指一系列的步驟，它包括兩方或者多方，設(shè)計(jì)它的目的是要完成一項(xiàng)任務(wù)。密鑰交換協(xié)議(keyexchangeprotoco1)是指兩人或多人之間通過一個(gè)協(xié)議取得密鑰并用于進(jìn)一步的加密算法中的方法。在實(shí)際的密碼世界中密鑰交換其實(shí)是很重要的一個(gè)環(huán)節(jié)。比如說利用對稱加密算法，如果雙方?jīng)]有約定好密鑰，就必須再進(jìn)行密鑰交換。但是如何使得密鑰到達(dá)接收者和發(fā)送者手里是件很復(fù)雜的事情。最早利用公鑰密碼思想提出的密鑰交換協(xié)議有Difffie-Hellman算法。新的密鑰交換協(xié)議有利用組合群論中的辮群B構(gòu)造的兩個(gè)n協(xié)議，Anshel-Anshel-Goldfeld協(xié)議和Ko-Lee-Cheon協(xié)議。第二節(jié)電子支付系統(tǒng)的安全性電子商務(wù)作為新興事務(wù)，已經(jīng)隨著計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的成熟得到了飛速發(fā)展，而且使得商家的整體經(jīng)營方式都有了變化。電子商務(wù)是以數(shù)字化的電子方式，以網(wǎng)絡(luò)為媒體進(jìn)行的商業(yè)數(shù)據(jù)交換或其他商業(yè)活動(dòng)。電子商務(wù)的一個(gè)重要組成部分就是電子支付系統(tǒng)。電子支付是指交易的各方是通過電子手段，比如說銀行的電子存款系統(tǒng)和電子清算系統(tǒng)來記錄和轉(zhuǎn)移資金的方式。一個(gè)安全、可靠的電子支付系統(tǒng)是電子商務(wù)的交易活動(dòng)能夠正常進(jìn)行的保證。目前INTERNET上的電子支付系統(tǒng)主要有四種:信用卡、IC卡、電子現(xiàn)金(e-Cash)和電子支票(e-Check)。一般來說，電子支付系統(tǒng)必須滿足以下的安全性要求，包括有消息的保密性、能夠確認(rèn)雙方都具有合法的交易身份的能力、保證交易完畢以后的信息是無法修改的和交易以后各方對業(yè)務(wù)的不可否認(rèn)性。作為電子支付系統(tǒng)的不同代表，電子現(xiàn)金和電子支票雖然有一定的共性，但在安全性要求和性質(zhì)方面有著各自獨(dú)特的特點(diǎn)。電子支票和紙張支票轉(zhuǎn)移支付的原理類似，是利用數(shù)字傳遞將錢款從一個(gè)賬戶轉(zhuǎn)移到另一個(gè)賬戶的電子付款方式。在電子支票實(shí)現(xiàn)的過程中，它的安全性問題是，如何保證銀行、用戶、商場對電子支票進(jìn)行簽名的有效性。由于轉(zhuǎn)賬在銀行、用戶和商場三方進(jìn)行，在每一次交易完成以后都必須對消息簽名，用來保證交易信息的真實(shí)、完整和不可否認(rèn)。所以在交易過程中將會(huì)涉及到數(shù)字多簽名。在本文中，我們最后討論了一種利用辮群構(gòu)造的多簽名體制，可以把上述多簽名運(yùn)用到電子支票轉(zhuǎn)賬系統(tǒng)中去。電子現(xiàn)金是一種以數(shù)據(jù)形式流行的貨幣，因此和支票相比，電子現(xiàn)金更強(qiáng)調(diào)滿足隱私性和可分割性，另外，雖然要保證用戶的隱私權(quán)，電子現(xiàn)金出于安全性的考慮，還需要滿足電子現(xiàn)金的不可偽造性和不可重用性。如果同一份電子現(xiàn)金被使用兩次，使用者的身份就可以被發(fā)現(xiàn)。關(guān)于電子現(xiàn)金，現(xiàn)在最主要討論的是它的可分性的實(shí)現(xiàn)。第二章組合群論和密碼學(xué)第一節(jié)基礎(chǔ)知識和背景自從1984年N.R.Wager和M.R.Magyarik在①中提出了第一個(gè)用組合群論的理論構(gòu)造公鑰密碼體制的方法以來，在密碼學(xué)家們的共同努力下，利用組合群論的理論已經(jīng)提出多個(gè)公鑰密碼體制和密鑰交換協(xié)議。由于組合群論中的數(shù)學(xué)工具和以前數(shù)論中的內(nèi)容截然不同，有必要對組合群論中的一些定義和定理加以說明，從而可運(yùn)用到密碼學(xué)中去，得到不同的加密算法。群G稱作是有限生成的(第二章組合群論和密碼學(xué)第一節(jié)基礎(chǔ)知識和背景自從1984年N.R.Wager和M.R.Magyarik在①中提出了第一個(gè)用組合群論的理論構(gòu)造公鑰密碼體制的方法以來，在密碼學(xué)家們的共同努力下，利用組合群論的理論已經(jīng)提出多個(gè)公鑰密碼體制和密鑰交換協(xié)議。由于組合群論中的數(shù)學(xué)工具和以前數(shù)論中的內(nèi)容截然不同，有必要對組合群論中的一些定義和定理加以說明，從而可運(yùn)用到密碼學(xué)中去，得到不同的加密算法。群G稱作是有限生成的(finitelygenerated),如果G存在有限個(gè)生成元gg，…,g，滿足G中任意一個(gè)元素(又稱為字)都可以表示成生成元和它們1,2n的逆的有限乘積。群G稱作是可以有限表示的(finitelyrepresented)，如果在G中有有限個(gè)元素r，r，…，r滿足在群G中，r=e，r=e,…，r=e，其中e是單位元，12k12k那么r，r，…，r稱為G的生成元g,g，…,g的一組定義關(guān)系，。12k12n換一種角度，如果把群G看成是n個(gè)元素X={a,a,…,a}生成的自由群12nF(X)的商群，即存在F(X)的正規(guī)子群N，使得G=F(X)，N成立，那么G是可以有限表示的意思是：如果r，r，…r對應(yīng)F(X)中的元素w，w…w，那么12k12k{w,w，…,w}是F(X)的正規(guī)子群N的生成元。12k可以有限表示的群G可表示為：G=gg,…,g'12 n［〔，…,rk辮群B是一種有限表示的群，B的生成兀是b，b，n n 1 2…，b，它的生成n-1關(guān)系滿足：bbb-Q-1=e，當(dāng)li-j>2時(shí)；bbbb-Q-Q-1=e當(dāng)i-j=1時(shí)。ijij ijijij因此，辮群B可以表示為：B,bn n■ 1 2,bn-1bbb=bbb;當(dāng)i一j=1. .. .. . "Iiji jZjbb=bb;當(dāng)li-j>2ijji組合群論中有些基本問題相對于某個(gè)特定的群是困難問題，可以作為構(gòu)造公鑰密碼體制的基礎(chǔ)，例如第一個(gè)公鑰密碼體制［Wag84］就是根據(jù)不可解的字問題所構(gòu)造的，而隨后的［Anshel93］等主要運(yùn)用了組合群論中的共軛問題。字問題(wordproblem):是否存在一個(gè)算法來判斷群G中的元素是不是單位元。一個(gè)問題是算法上可解的(algorithmicallysolvable)是指存在一組計(jì)算機(jī)程序，通過計(jì)算，對該問題的結(jié)果是“是”或“否”做出明確的回答。如果不存在這樣的程序，就稱這個(gè)問題是算法上不可解的(algorithmicallyunsolvable)。關(guān)于字問題對于某些群是否是算法上不可解的，Novikov-Boone定理(見②)對此做出了肯定的回答，定理中利用了有限表示的群，這也是用字問題作為困難問題構(gòu)造加密算法的基礎(chǔ)。Novikov-Boone定理：存在有限表示的群G有著算法上不可解的字問題，并且存在有效的算法B，如果輸入有限表示的一個(gè)系統(tǒng)T，且該系統(tǒng)有著不可解的字問題，通過算法B將會(huì)輸出有限表示的群B(T)，使得B(T)有著算法上不可解的字問題。第一次提出利用組合群論的思想來構(gòu)造的［Wag84］密碼體制就利用了Novikov-Boone定理。共軛問題(conjugacyproblem):是否存在算法來判斷群G中給定的任意兩個(gè)元素是共軛元素。所謂兩個(gè)元素x,y共軛是指，存在G中元素w,使得y二w-1xw成立。關(guān)于組合群論中是否存在群有著算法上不可解的共軛問題，同樣可由一個(gè)定理加以保證。在該定理中，所涉及的群是剩余有限群。一個(gè)群G被稱為是剩余有限的(residuallyfinite)，如果給定了群中任意一個(gè)元素geG，g豐e,都存在G的正規(guī)子群NVG,使得g不是N中的元素。g g運(yùn)用剩余有限的群，Miller證明了具有算法上不可解共軛問題的群的存在性，這就是Miller定理：Miller定理:存在有限表示且剩余有限的群，其共軛問題是算法上不可解的。并且存在快速算法C使得輸入一個(gè)有限表示的群G(G的字問題不可解)后會(huì)

輸出有限表現(xiàn)且剩余有限的群C(G),C(G)有著不可解的共軛問題。Miller定理是1993年IrisLeeAnshel和MichaelAnshel提出的基于不可解的共軛問題而構(gòu)造的公鑰加密體制的理論基礎(chǔ)。辮群B在組合群論應(yīng)用于密碼學(xué)中扮演了重要的角色。在1999年I.Anshel,nM.Anshel和D.Goldfeld提出的密鑰交換協(xié)議和2000年Hyoung.Ko,SangJinLee和JungHeeCheon提出的密鑰交換協(xié)議和加密算法中，他們都利用了辮群的共軛問題,這是因?yàn)檗p群的一些重要性質(zhì)可以很好的利用到密碼體制中去。辮群的定義在前面已經(jīng)提到過了,但是辮群除了可以用有限生成元表示出來以外,還有著其獨(dú)特的幾何意義。辮群B中每一個(gè)元素都對應(yīng)了兩條平行直n線間的n股線,每一股線的兩個(gè)端點(diǎn)開始于上面的平行直線,并中止于下端對應(yīng)平行直線。下面的兩幅圖對應(yīng)于B中的生成元Q和◎-1。如圖一對應(yīng)于Q，圖niii二對應(yīng)于◎-1。i辮群中的兩個(gè)元素a,b相乘在幾何上對應(yīng)了把兩個(gè)辮群的圖像拼接起來。另外，B中兩個(gè)元素相等從幾何上來說，是指a，b兩個(gè)元素對應(yīng)的圖案能夠在n三維空間中從一個(gè)圖像連續(xù)的變動(dòng)到另一個(gè)。根據(jù)文獻(xiàn)⑤，⑦，辮群有一些性質(zhì)特別適合密碼學(xué)的要求，用來構(gòu)造公鑰密碼體制。辮群的元素可以通過標(biāo)準(zhǔn)形式(canonicalform)來統(tǒng)一表示，即由p+1個(gè)參量(u,兀,兀,…,兀)表示，u是整數(shù)，兀代表了一個(gè)n階置換，該表示是唯一的。12pi辮群內(nèi)元素的乘法和求逆都存在快速算法，可以用計(jì)算機(jī)編程計(jì)算。并且辮群中有很多的困難問題可以作為構(gòu)造密碼體制和密碼交換協(xié)議的基礎(chǔ)，比如說辮群的共軛問題就是困難問題。

第二節(jié)：密碼體制和密鑰交換協(xié)議2.2.1［Wag84］公鑰密碼體制1984年N.R.Waner和M.R.Magyarik利用了有限表示群的不可解的字問題，構(gòu)造了第一個(gè)以組合群論思想為基礎(chǔ)的公鑰密碼體制。由前面的Novikov-Boone定理可知，存在群滿足不可解的字問題，這是［Wag84］公鑰密碼體制成立的基礎(chǔ)。下面是整個(gè)加密算法：G=；取G是有限表示的群，有著不可解的字問題，G=；u—1,u—1,12利用一個(gè)秘密同態(tài)函數(shù) h:GTAA可以是大的有限群或者是有限表示的群，它的字問題有著快速的解法。在群G中取兩個(gè)字y和y，使得這兩個(gè)01字滿足h(y)豐h(y)。把群G，y和y公開，作為公鑰，而把同態(tài)函數(shù)h保密，0101作為秘密密鑰。加密算法很簡單，只要將消息M寫成二進(jìn)制數(shù)的形式以后，每個(gè)0-bit位由隨機(jī)選擇的y'代替，只要滿足y'三ymodG(意思是指y'和y是G中同一個(gè)元00000素的不同表現(xiàn)形式)。同理，1-bit位用y'代替，y'三ymodG。這樣的話，消息111M中的每個(gè)比特位都有G中的元素來表示，從密文中任取G的一個(gè)元素z,由于G有著不可解的字問題，即無法利用算法判斷zy-1和zy-1中哪一個(gè)是單位元01素，因此，加密是成功的。解密時(shí)需要運(yùn)用解密密鑰h，在密文中取元素z，只要h(z)=h(y)，說明z代0表的比特位是0，反之是1。因?yàn)樵贏中字問題是可解的，上面的結(jié)果可以判斷,因此消息被解密。對于以上的利用組合群論所構(gòu)造加密算法的討論：首先它需要找一個(gè)合適的具有不可解的字問題的群，要使加密算法適合實(shí)用，必須使群里的元素應(yīng)該在群中有唯一的標(biāo)準(zhǔn)表示，通過計(jì)算機(jī)很容易進(jìn)行存儲(chǔ)和計(jì)算。即使是這樣，原文中一個(gè)比特位的0或者1經(jīng)過轉(zhuǎn)化成密文以后，需要用群的一個(gè)元素來表示。而群中元素在計(jì)算機(jī)的傳輸和存儲(chǔ)的方面，所需要的存儲(chǔ)量遠(yuǎn)遠(yuǎn)大過比特位。并且在密文處理方面有很多的不方便的地方，比如說如何選擇和Y0或者Y］等價(jià)元素，有沒有快速算法等等，這些缺點(diǎn)都降低了效率，所以總的來說，這只是一個(gè)不太成熟，不能實(shí)用的方案，但畢竟，它在把組合群論利用到密碼學(xué)中開創(chuàng)了新的一步。2?2?2［Anshel93］密碼體制接下來由文獻(xiàn)②，在1993年，M.Anshel和I.Anshel繼續(xù)了利用組合群論中的問題提出了另一個(gè)新的加密算法，與前一個(gè)有所不同的是，這次他們所采用的群是有限生成的群，群中元素具有不可解的共軛問題，并且群是剩余有限群。在他們所提出的方案中，需要用到前面提到的Miller定理作為保障。G中任意的一個(gè)元素g,存在從G到有限群的一個(gè)同態(tài)①，滿足①(g)豐1。任取G中一個(gè)元素w，存在G的正規(guī)子群N，使得w不是N中的元素，在群WWG中，記z為單位元素，由于G是剩余有限的，存在一個(gè)有限群G/N，可考慮W同態(tài)H：G~G/N，因?yàn)閣不屬于N，H(w)豐1，H(z)=1，由此，由于H(w)WW和H(z)不是共軛元素，而同態(tài)運(yùn)算保持共軛性質(zhì)不變，w和z也不是共軛元素。把同態(tài)運(yùn)算H保密，并假設(shè)在商群G/N中，求解共軛問題和字問題在算法上W是多項(xiàng)式內(nèi)實(shí)現(xiàn)的。在加密問題上Anshel所采用的方法與前文類似，那就是把1用任一與z共軛的元素代替，把0用與w共軛的任一元素代替，用這個(gè)方法，可隨機(jī)地把明文中的二進(jìn)制數(shù)字轉(zhuǎn)化成密文中組合群中的元素，而通過保密的同態(tài)加以解密，最終得到原文。［wag84］和［Ansh93］從設(shè)計(jì)的思想上來說，是基本上類似的，它們都是設(shè)法利用組合論中有特定性質(zhì)的群，即有著不可解的字問題或是共軛問題，以群中兩類不同的元素分別代表0和1兩個(gè)數(shù)字，同時(shí)均將一個(gè)同態(tài)映射做密鑰保存，只要知道了所選用的群和兩個(gè)代表0和1的群元素就可以對消息進(jìn)行加密，作為密鑰的同態(tài)運(yùn)算所對應(yīng)的群的字問題和共軛問題則是可解的。它們的差別是［wag84］所選用的群是以字問題做為困難問題，而［Ansh93］是把共軛問題做為困難問題，兩者的區(qū)別是群選擇的不同。2?2?3[Anshel-Anshel-Goldfeld]密鑰交換協(xié)議1999年的時(shí)候，不同于以上的幾個(gè)公鑰密碼系統(tǒng)，在組合群論的基礎(chǔ)上，I.Anshel,MAnshel和DGoldfeld提出了一個(gè)新的密鑰交換協(xié)議(見③和④)，該協(xié)議中所采用的群是辮群，具有不可解的共軛問題，但是辮群的字問題可以在多項(xiàng)式時(shí)間內(nèi)解決。在協(xié)議中，［Anshel99］利用換位子的思想，XYX-iY-i,其中Y均為辨群B中的元素，其中XYX-iY-i可以看成是Y的共軛元素和Y-1相n乘得到，或者可以看成是X和X-1的共軛元素相乘得到的，具體的密鑰交換步驟如下：兩方Alice和Bob分別公布字a(1)，a(2)，…，a(n)；b(1)，b(2)，…，b(m)。這些字均從群G={SID}得到，其中S是生成元，D是定義關(guān)系。Alice和Bob之間的密鑰由它的共同的行為產(chǎn)生，Alice和Bob同時(shí)執(zhí)行以下的步驟，一起產(chǎn)生秘密密鑰：1、 Alice首先進(jìn)行如下運(yùn)算，Alice選擇一個(gè)群G中的由a(1)，a(2)，…，a(n)生成的秘密的字X，對每一個(gè)b(i)進(jìn)行共軛運(yùn)算，產(chǎn)生m個(gè)新字c(1)，c(2)，…,c(m)，c(i)=Xb(i)X-1。2、 Alice對每一個(gè)c(i)進(jìn)行改寫，寫成B(i)的形式，B(i)和c(i)是G中同一個(gè)元素的不同表示，i=1，…，m。B(i)能夠完全掩蓋住c(i)中有關(guān)X的秘密信息。由于B(i)和b(i)是關(guān)于X的共軛元素，但不能從B(i)中推斷出X是什么(G有著不可解的共軛問題)，X是不可知的。3、 Alice通過公開的渠道把B(1)，B(2),…，B(m)傳送給Bob。在Alice進(jìn)行計(jì)算的同時(shí)，Bob進(jìn)行類似的計(jì)算。1、 Bob從b(1),b(2),…，b(m)生成的G的子群中，選擇一個(gè)秘密的元素Y, 用每個(gè)a(i)進(jìn)行共軛等。產(chǎn)生d(1)，d⑵……d(n),d(i)=Ya(i)Y-1。2、 對每個(gè)d(i)進(jìn)行改寫，寫成A(i)的形式，使得A(i)和d(i)表示相同的元素。3、 Bob把A(1),A(2),…,A(n)傳送給Alice。第三步，Alice和Bob可根據(jù)所得的結(jié)果分別計(jì)算出換位子(X，Y)=XYX-1Y-1。因?yàn)?，Alice可以從V=X(YXY-1)-1=Xx(A(1)),…人(n))-1中計(jì)算，如果X=x(a(l),-a(n))。并且Bob也可以計(jì)算換位子W=(XYX-i)Y-i=y(B(l),B(2),…，B(m))Y-i,如果Y=y(b(1),……,b(n))。X由a(1),a(2),…，a(n)生成，僅為Alice所知，而A(1),A(2),…,A(n)是a(1),a(2),…，a(n)關(guān)于Y的共軛元素，通過類似的計(jì)算，Alice可以知道YXY-i,Bob也是可以由秘密的Y以及Alice傳送給它的B(1),B(2),…，B(m)來得到XYX-i,但是對于Alice所掌握的字X一無所知，當(dāng)Alice和Bob經(jīng)過計(jì)算出V和W以后，V和W是同一個(gè)字的不同表現(xiàn)形式，從字V和W得到Alice和Bob的共同的密鑰有兩個(gè)方法,第一個(gè)是辮群G中的每個(gè)元素都有且僅有一種唯一的特殊表現(xiàn)形式,稱作經(jīng)典形式，那么把V和W都寫成經(jīng)典形式之后，這時(shí)它們的標(biāo)準(zhǔn)形式是相同的，然后可以定義從辮群的標(biāo)準(zhǔn)形式到二進(jìn)制數(shù)的單向函數(shù)H,從而使密鑰K=H(V)=H(W),第二個(gè)方法是把G作為群作用在某個(gè)集合S上,并且滿足E(S)=SG1(G2(S))=(G］G2)(S),(G1、G2屬于G,E是G的單位元)，且G內(nèi)不同的字作用到S上的元素S所得的值也是不同的。在這種條件下，密鑰K=V(S)=W(S)也同樣可以得到。對［Anshel-Anshel-Goldfeld］密鑰交換協(xié)議的分析：首先我們不知道，上述的密鑰交換協(xié)議的安全性是否以辮群共軛問題的難解程度為基礎(chǔ)的，但是，實(shí)際上已知XYX-1和Y求解X的問題和已知XB(1)X-1,XB(2)X-1…，XB(M)X-1和B(1),B(2),-*B(M)的值來求解X的困難程度是不一樣的，顯然后一個(gè)問題比前面的問題要容易的多，后一個(gè)問題所面臨的困難問題是不同于標(biāo)準(zhǔn)形式的共軛問題，我們可以把它稱之為新的共軛問題(MSCSP),應(yīng)該說這個(gè)也是從算法上來說不可解的。另一點(diǎn)是［Anshel-Anshel-Goldfeld］密鑰交換協(xié)議所利用的辮群中密鑰的共軛運(yùn)算的同態(tài)性質(zhì)；即XA(1)X-1XA(2)X-1=XA(1)A(2)X-1,以及(XYX-1)-1=XY-1X-1但是在Alice和Bob對X,Y進(jìn)行改寫，并使得從XB(1)X-1,…，XB(M)X-1或YA(1)Y-1,…，YA(N)Y-1中不能得出X,Y的值的時(shí)候，通過改寫,即把上述這些辮群里的元素寫成標(biāo)準(zhǔn)形式時(shí)，并不能夠保證所有的標(biāo)準(zhǔn)形式能完全掩蓋住秘密信息。但是只要有一個(gè)元素泄露出X或者Y的值，那么密鑰就可以被破解，所以X(B1)X-1,…，XB(M)X-1和YA(1)Y-1,…，YA(N)Y-1中的秘密信息必須完全被改寫掉。2?2?4［Ko-Lee-Cheon］密鑰交換協(xié)議和公鑰密碼體制從上述的密鑰交換協(xié)議可以看出，上述的協(xié)議的主要思想是利用組合群論中的一般理論，關(guān)于換位子的思想適用于任何一個(gè)群，只是在具體的實(shí)現(xiàn)方法上，才使用了辮群，因?yàn)檗p群在實(shí)現(xiàn)過程中，有一些較好的優(yōu)點(diǎn)。比如有唯一的標(biāo)準(zhǔn)形式，并且它的字問題有著快速算法，而共軛問題是困難問題等等。應(yīng)該可以看出，任何具有類似性質(zhì)的群都可以做為構(gòu)造［Anshel-Anshel-Goldfeld］密鑰交換協(xié)議的群。下面所提到的［Ko-Lee-Cheon］密鑰交換協(xié)議則是更立足于辮群本身的性質(zhì)（文獻(xiàn)⑦），因此在討論密鑰交換協(xié)議的時(shí)候，對于密鑰交換協(xié)議的安全性分析將更加成熟一點(diǎn)，并且能夠相對比較實(shí)用。韓國學(xué)者HyoungKo，SangJinLee和JungHeeCheon提出，在辮群中有一些問題屬于困難問題，其中能夠適用于構(gòu)造密鑰體制的有以下一些：假設(shè)B是由a,c，…，b生成，B由c,c，…，b生成，m<n，n 12 n-1 m 12 m-1那么，辮群B可以看成是B的子群，那么有以下幾個(gè)問題是困難問題：mn1、 普通的尋找共軛元素問題（GCSP）元素（X,Y）eBxB，并且Y=BXB-1，其中，BeB，m<nnm n問題：尋找AeB使行Y=AXA-1成立，m2、 共軛元素分解問題（QCDP）（X，Y）eBxB，滿足Y=BXB-1，BeB，m<nnm m問題：尋找A'，A''eB，滿足Y二A'XA''。m3、 尋找P次根問題，（X,Y）eBxB，滿足Y=XP，XeB，nn n問題：尋找ZeB，滿足，Y=Zp。n在上述幾個(gè)問題的基礎(chǔ)上，HyoungKo等提出了密鑰交換協(xié)議，上述協(xié)議所利用的是第一個(gè)困難問題，在B中取兩個(gè)群，LB和RB，LB是由a.a，…,n l r l 1 2a生成，而RB由a，…，a生成，由于辮群的生成元滿足條件，l-l r l+l l+r-1aa=aa,i-j>2,因此對于任意的AwLB,BeRB，都能滿足AB=BA。TOC\o"1-5"\h\zijji 1 r所以辮群B中的子群LB和RB之間的任意兩個(gè)元素具有交換性，這是能否滿n l r足密鑰系統(tǒng)的關(guān)鍵。密鑰交換協(xié)議的具體實(shí)現(xiàn)如下：1、 首先選擇充分大并且較合適的兩個(gè)整數(shù)（L,R）以及辮群B，LB和RB。n l r在B中選擇一個(gè)比較合適的元素X,并將X公開。n2、 密鑰交換者Alice和Bob分別執(zhí)行以下步驟：（A） Alice從LB中任意選擇一個(gè)秘密元素A，把Y.=AXA-1，傳送給Bob。l1（B） Bob從RB中選擇一個(gè)元素B，并將，Y2=BXB-1傳送給Alice，r2（C）Alice收到Y(jié)以后，計(jì)算K=AY2A-1（D）Bob收到X以后，計(jì)算K=BY]B-1。由于,AB是交換的，即AB=BA，所以，A-1B-1=B-1A-1并且,AY2A-1=A（BXB-1）A-1=B（AXB-1）B-1=BY1B-1，因此Alice和Bob兩人得到的密鑰是相同的。值得注意的是，在密鑰交換協(xié)議中利用的困難問題和普通的尋找共軛元素問題（GCSP）不完全是等價(jià)的，但是兩者之間有緊密的關(guān)系。關(guān)于這一點(diǎn)，有點(diǎn)類似于Diffie-Hellman的密鑰交換協(xié)議，因?yàn)镈iffie-Hellman協(xié)議中就是由已知Gx和Y以及Gx，X中分別得到Gxy,但是這個(gè)問題可以歸結(jié)為求解離散對數(shù)的問題。在辮群的協(xié)議中，也是類似的。竊聽者即使能夠知道AXA-1，B和BXB-1和A但要計(jì)算ABXA-1B-1,還是會(huì)歸結(jié)為求解共軛元素的問題。雖然[Anshel99]也是利用了辮群的共軛算法，但在這一點(diǎn)上和韓國學(xué)者提出是的不一樣的。與密鑰交換協(xié)議非常相似，HyoungKo等同時(shí)利用辮群可以構(gòu)造一個(gè)新的公鑰密碼體制。運(yùn)用到的方法和上面基本一致，只是需要增加一個(gè)散列函數(shù)。首先定義一個(gè)從辮群元素到二進(jìn)制數(shù)字的單向散列函數(shù)H:Bt{0,1}kl+r1、產(chǎn)生公鑰及私鑰階段。（A）從B中選擇一個(gè)適當(dāng)?shù)模蒩,a，…，a 生成的X。l+r 12 l+r-1取LB中元素A,l設(shè)Y=AXA-i是X關(guān)于A的共軛，把Y公開，當(dāng)做公鑰，并且使A保密，當(dāng)作私鑰。2、加密運(yùn)算：如給定明文Me{0，1}k和(X、Y)以后，任意從RB中選擇元素Br加密以后的密文是(C，D)，C=BXB-i和D=H(BYB-i)十M3、解密通過計(jì)算M=H(ACA-i)十D可得，上面這個(gè)步驟的原因是因?yàn)锳CA-i=ABXB-iA-i=(BA)XA-iB-i=BYB-i，因此，H(ACA-i［十D=H(BYB-i)十H(BYB-i)十M=M。十代表了異或運(yùn)算。這個(gè)新的加密算法和密鑰交換協(xié)議的理論基礎(chǔ)相同，并且比較實(shí)用。第三章組合群論在電子支票的多簽名體制中的應(yīng)用

第一節(jié)三方密鑰交換協(xié)議考慮將兩方的密鑰交換協(xié)議推廣到三方或者更多的人中去，就必須利用協(xié)議本身的性質(zhì)。關(guān)于Anshel-Anshel-Goldfeld密鑰交換協(xié)議，因?yàn)閰f(xié)議中利用了換位子XYX-iY-i，很難推廣到多方中去。但是Ko-Lee-Cheon協(xié)議采用了Diffie-Hellman算法的思想，因此可以稍做修改，使參加協(xié)議的人增加到三人或者多人。下面就是具體的三方協(xié)議。首先可在辮群中取三個(gè)子群LB，MB和RB，LB由q，q，???,◎生l k rli2 l-i成，MB由q，…，q生成，RB由q ，…，q生成，其中1，k，k l+1 l+k—i r l+k+1 l+k+r—ir滿足條件：1+r+k=n。利用辮群中生成元的性質(zhì)可知，任意aeLB，beMB，lkceRB，都滿足：ab二ba，bc二cb，ac=ca，這就是說，群LB，MB和RBr l k r中任意元素都是可以交換的。和兩方協(xié)議類似，Alice，Bob和Carol執(zhí)行以下的步驟：(l)Alice,Bob和Carol共同選擇一個(gè)恰當(dāng)?shù)霓p元x,xgB。n⑵Alice從LB中隨機(jī)選擇辨兀a,把x=axa-1發(fā)送給Bob。ll(3)Bob從MB中任意選擇辮元bgMB，把x二bxb-1發(fā)送給Carol。kk2(4)Carol從RB中任意選擇cgRB，把x=cxc-1發(fā)送給Alice。r r 3⑸Alice把y=axa-1發(fā)送給Bob。13(6)Bob把y=bxb-1發(fā)送給Carol。21(7)Carol把y=cxc-1發(fā)送給Alice。32⑻Alice計(jì)算密鑰k=aya-1。3(9)Bob計(jì)算密鑰k二byb-1。1(10)Carol計(jì)算密鑰k=cyc-1。2由于a，b，c三個(gè)元素有交換性，因此有以下等式成立:aya-1=a(cxc-1)a-1=ac(bxb-1)c-1a-1=abcxc-1b-1a-1；32和byb-1=b(acxc-1a-1)b-1=abcxc-1b-1a-1=cyc-1=aya-1；1 2 3可知k為Alice，Bob，Carol三方的共同密鑰。因?yàn)檫@個(gè)三方協(xié)議和Diffie-Hellman協(xié)議類似，由Diffie-Hellman協(xié)議的安全性可知，上述協(xié)議是安全的，它的困難程度基于在辮群中破解共軛問題的難度。另外，出于安全性的考慮，由文獻(xiàn)[7]中對滿足條件的辮元x所加的限制條件可知在上述協(xié)議中，x不能取成aaaz123的類型，其中agLB，agMB，agRB，而z是B中能夠和LB，MB和RBTOC\o"1-5"\h\z1l2 k3r n l k r中元素都交換的辮元。因?yàn)槿绻鹸=aaaz，密鑰k滿足條件:123k=abcxc-1b-1a-1 =aaa-1bab-1cac-1z。1 2 3又因?yàn)閤=(aaa-1)aaz，x=a(bab-1)az，x=aa(cac-1)z，通過公開1 1 23 2 1 2 3 3 12 3傳輸?shù)膞，x，x和x就可以計(jì)算得到aaa-1，bab-1，cac-1，從而計(jì)算出密鑰。1 2 3 1 2 3因此，應(yīng)該選擇適當(dāng)?shù)膞滿足安全性的要求。不過有一點(diǎn)比較有利的是，同樣是在文獻(xiàn)⑺中對x的討論中，上述x出現(xiàn)的概率非常小，一般不用多做考慮。第二節(jié)基于辮群的多簽名體制方案3.2.1多簽名介紹利用公開密鑰算法對一段消息進(jìn)行數(shù)字簽名，這是簽名方案中最常用的一種方法，它在理論上發(fā)展的已經(jīng)比較完善，在實(shí)際應(yīng)用中也有成熟的體制。比如說由RSA加密算法轉(zhuǎn)化而成的數(shù)字簽名、ElGamal簽名方案、Schnorr簽名算法、經(jīng)過改進(jìn)的Fiat-Shamir簽名方案以及Guillon-Quisquater數(shù)字簽名方案等等。這些數(shù)字簽名的安全性或是建立在大整數(shù)分解的難度上，或是建立在計(jì)算離散對數(shù)的難度上，或是利用其他數(shù)論中的困難問題。不過這些方案都有一個(gè)特點(diǎn)，這些數(shù)字簽名只是單個(gè)人對一份文件的簽名，很少有簽名方案可以拓展到多個(gè)人對同一份文件的簽名上去。即使有，也只是簡單的通過單簽名加以迭代而得到的。但是由于實(shí)際應(yīng)用的需要，對簽名人數(shù)提出了更高的要求?，F(xiàn)在需要一種新的簽名方案，可以使多個(gè)人對同一份文件進(jìn)行簽名，這就是多簽名。多簽名有著廣泛的應(yīng)用，比如說一份文件必須有多個(gè)人簽署才能執(zhí)行，缺乏了其中任意一人的同意就不可以；或者是電子支票在銀行、客戶、商店之間轉(zhuǎn)賬時(shí)，銀行、客戶、商店為了使轉(zhuǎn)賬過程得以紀(jì)錄，在每次交易時(shí)對同一份文件——支票進(jìn)行數(shù)字簽名，也需要利用多簽名的技術(shù)。這些應(yīng)用使得數(shù)字多簽名方案的發(fā)展成為一種必然。為了滿足著一要求，密碼學(xué)家利用數(shù)學(xué)理論也構(gòu)造了一系列多簽名方案，其中比較實(shí)用且計(jì)算速度較快的是日本學(xué)者EikohChida，TakoNishizeki等基于單向環(huán)同態(tài)所構(gòu)造的多簽名方案。在本文中，除了介紹他們的多簽名體制以外，我們還考慮利用辮群中的困難問題對基于單向環(huán)同態(tài)而構(gòu)造的多簽名方案進(jìn)行改進(jìn)，提出把組合群論思想和多簽名方案結(jié)合起來，提出一個(gè)新的多簽名方案。數(shù)字多簽名的安全性要求：多簽名方案由于簽名過程涉及了多個(gè)人，并且簽名完成以后要求能檢驗(yàn)所有人對同一消息的簽名，所以在安全性方面比一般的數(shù)字簽名有著更高的安全性要求。首先要求多簽名能夠抵抗外部攻擊，3.2.2基于單向環(huán)同態(tài)的多簽名體制在文獻(xiàn)⑥中，EikohChida,TakoNishzeki等首先提出了問題：在代數(shù)結(jié)構(gòu)中除了群中存在單向群同態(tài)函數(shù)(即函數(shù)既是單向函數(shù)，也滿足群中的同態(tài)運(yùn)算)以外是否還有其它的單向函數(shù)同態(tài),比如在環(huán),幺半群中等。實(shí)際上,以前所構(gòu)造的RSA加密算法、離散對數(shù)算法都是利用了基于單向群同態(tài)的單向陷門函數(shù)。而環(huán)同態(tài)對于這個(gè)問題的肯定回答,他們是構(gòu)造了一個(gè)單向環(huán)同態(tài)來實(shí)現(xiàn)的。如果A是交換環(huán)R(A，+，*)，U是在加法+下的A-模，對于任意A和U,直和A十U內(nèi)的元素(a,u)和(a,u)，可定義A十U中的加法十：(A十U)x1122(A十U)tA十U和乘法*：(A十U)x(A十U)tA十U如下：(a,u)十(a,u)=(a+a,u+u)；(a,u)*(a,u)=(a*a,au+au)；可以112212121122121122證明所得的(A十U,十，*)是交換環(huán)。利用這個(gè)交換環(huán)，EikohChida等有進(jìn)一步證明了單向環(huán)同態(tài)的存在性，這可以表述為下面這個(gè)定理：定理：U，V都是有限交換群，”|=n，如果U和V內(nèi)二進(jìn)制運(yùn)算是多項(xiàng)式內(nèi)可計(jì)算的，如果存在單向群同態(tài)函數(shù)f:UtV，那么存在單向環(huán)同態(tài)F:Z十UtZ十Imf。(F的定義是：F(n,x)=(n,f(x))。)nn為了構(gòu)造適當(dāng)?shù)亩嗪灻w制，文獻(xiàn)⑥中利用了z上的同態(tài)函數(shù)：P-1f:ZtZ*，f(x)二gxmodp，g是Z*的生成元，這個(gè)函數(shù)是單向的。運(yùn)用P-1 P P上面的定理，可以得到單向環(huán)同態(tài)函數(shù)：F:(Z十Z*)t(Z十Z*)，P-1 P P-1 PF(n,x)二(n,gx)。關(guān)于文獻(xiàn)中有根據(jù)上述函數(shù)而構(gòu)造的多簽名體制，在此不再詳述。3.2.3基于辮群的多簽名體制如果要把辮群應(yīng)用到構(gòu)造單向環(huán)同態(tài)中，就必須考慮辮群的很多基本性質(zhì)和上述單向群同態(tài)中對群的要求不完全相同，因此，必須對直和A十U和A十V的一些定義加以修改，以滿足單向函數(shù)的要求，不過用辮群Bn很難滿足單向函數(shù)同時(shí)又是環(huán)同態(tài)，所以經(jīng)修改后的多簽名體制和文獻(xiàn)⑥中的有所不同。首先，辮群Bn是無限群，不是有限的。對于這一點(diǎn)，可以把環(huán)Zn改成環(huán)乙把直和Z十Z改成Z十B。另外一點(diǎn)限制是，A十U中的U是交換群，這是p-1 p-1 nA十U是交換環(huán)的定義中對U的基本要求，但是辮群Bn不是交換群。因此，利用辮群不一定能夠構(gòu)造出單向環(huán)同態(tài)，不過根據(jù)辮群的性質(zhì)，辮群還是可以用來構(gòu)造多簽名體制。注意在文獻(xiàn)⑦中提到了辮群的一個(gè)困難問題：(y,p)gBxZ,y二xp,xgB，nn尋找滿足條件的x。利用上述困難問題構(gòu)造單向函數(shù)f:BTB，f(x)二xp(pnn是固定的正整數(shù))，如果B中元素x,y滿足條件f(xy)=f(x)f(y)，根據(jù)前文EikohnChida等證明的定義和定理，則在直和Z十B中定義函數(shù)F:Z十BTZ十B為n n nF(n,x)=(n,xp)，F(xiàn)(,)也是單向函數(shù)，并且(n,x)，(m,y)同時(shí)滿足加法和乘法運(yùn)算：F((n,x)十(m,y))=F(n,x)十F(m,y)；F((n,x)(m,y))=F(n,x)F(m,y)。加法和乘法的同態(tài)性質(zhì)正是構(gòu)造多簽名體制所必須使用的。因?yàn)閍a=◎a，li-j>2。由c，c，…，c生成的Bn的子群LBlTOC\o"1-5"\h\zij ji 1 2 l-1和a，…，a生成的子6群RB內(nèi)元素是互相交換的，即ab=ba,任意agLB,l+1 l+r-1 r lbgRB，所以只要取元素agLB，bgRB，a,b滿足群的同態(tài)性質(zhì)：r l rf(ab)=(ab)p=apbp=f(a)f(b)，因此直和Z十B中的(n,a)，(m,b)也滿足加法n和乘法的同態(tài)性質(zhì)。利用上述性質(zhì)，構(gòu)造多簽名體制如下：記U,U，…，U為簽名方，對1<i<r,X二(n,x)為U的秘密密鑰，1 2 r iiiixgLB，其中LB是B的子群，每個(gè)LB分別由生成元c ，…，q生成。TOC\o"1-5"\h\zi i in i (i—1)t+1 it-1Y=F(X)=(n,xp)是U的公共密鑰，并且假設(shè)存在散列函數(shù)H:ZTZ十LB,iiiii r+1LB也是B的子群，生成元是q ，…，q。因此LB中的任意元素都滿r+1 n rt+1 (r+1)t-1 i足交換性。設(shè)待簽名的消息為M,并且H(M)=(n,x)。U，U，…，U等簽名1 2 r方相繼執(zhí)行一下步驟：第一名簽名者U:1隨機(jī)生成k=(m,y)gZ十LB，LB與LB的定義類似。1 11 r+2 r+2 i計(jì)算R=F(k)gZ十LB。1 1 r+2計(jì)算S=X*R十H(M)*k1111把M、R和S