第一章密碼學(xué)和電子商務(wù)的安全性

1、摘要摘要公鑰密碼體制從開始提出到現(xiàn)在，它的主要思想是利用了數(shù)論中的困難問題。例如，應(yīng)用最廣泛的 RSA 加密體制是基于大整數(shù)分解成兩個素數(shù)的困難問題構(gòu)造的加密算法，ElGamal 數(shù)字簽名是根據(jù)在剩余類環(huán)中由生成元求解其離散對數(shù)的問題的困難程度來實現(xiàn)的。和這些加密算法不同的是本文中利用了組合群論的思想構(gòu)造的一些加密體制。組合群論中有些特定的字問題和共軛問題是困難問題，可用于構(gòu)造密碼學(xué)的基礎(chǔ)。N.R.Wager 和M.R.Magyarik 第一次提出了用組合群論的理論來構(gòu)造公鑰加密算法的方法，他們所利用的是不可解的字問題，其次在 93 年，M.Anshel 和 I.Anhel 提出了利用不可解的

2、共軛問題對信息進(jìn)行加密的算法，這也是公鑰密碼算法，其基本思想和第一個基本相似。更進(jìn)一步，在99 年 I.Anshel，M.Anshel 和 D.Goldfeld 利用辮群的共軛問題實現(xiàn)了一個新的密鑰交換協(xié)議。密碼學(xué)在組合群論中的最新進(jìn)展是 Hyoung.Ko，Sang Jin Lee 和Jung Hee Cheon 提出的密鑰交換協(xié)議和加密協(xié)議，他們同樣是利用了辮群的不可解共軛問題，但是主要思想和具體的實現(xiàn)上和 I.Anshel 等提出的密鑰交換協(xié)議有很大的區(qū)別。本文簡要介紹這些加密算法和協(xié)議。同時，利用辮群的一些基本特點把辮群的另一個困難問題應(yīng)用到基于單向環(huán)同態(tài)的多簽名體制中去，提出了一個新

3、的多簽名方案，并且討論了這個多簽名方案在電子支付系統(tǒng)中的應(yīng)用。關(guān)鍵詞：關(guān)鍵詞：辮群，字問題，共軛問題，密鑰交換協(xié)議，多簽名體制組合群論在密碼學(xué)和電子商務(wù)組合群論在密碼學(xué)和電子商務(wù)的安全性中的應(yīng)用的安全性中的應(yīng)用 數(shù)學(xué)學(xué)院 98 級數(shù)學(xué)系 方初瑩目錄目錄 第一章第一章 密碼學(xué)和電子商務(wù)的安全性密碼學(xué)和電子商務(wù)的安全性 1第一節(jié) 密碼學(xué)概述 1第二節(jié) 電子支付系統(tǒng)的安全性 4第二章第二章組合群論和密碼學(xué)組合群論和密碼學(xué) 4第一節(jié) 基礎(chǔ)知識和背景 4第二節(jié) 密碼體制和密鑰交換協(xié)議 72.2.1 Wag84公鑰密碼體制 72.2.2Anshel93密碼體制 9 2.2.3Anshel-Anshel-G

4、oldfeld密鑰交換協(xié)議 9 2.2.4Ko-Lee-Cheon密鑰交換協(xié)議和密碼體制 11第三章第三章組合群論在電子支票的多簽名體制中的應(yīng)用組合群論在電子支票的多簽名體制中的應(yīng)用14第一節(jié) 三方密鑰交換協(xié)議 14第二節(jié) 基于辮群的多簽名體制方案 15 3.2.1 多簽名介紹 16 3.2.2 基于單向環(huán)同態(tài)的多簽名體制 17 3.2.3 基于辮群的多簽名體制 18 第一章第一章 密碼學(xué)和電子商務(wù)的安全性密碼學(xué)和電子商務(wù)的安全性第一節(jié)第一節(jié) 密碼學(xué)概述密碼學(xué)概述信息安全是密碼學(xué)的基本要求，為了要達(dá)到這一點，密碼學(xué)始終涉及兩個方面的斗爭。其中一方（發(fā)送者）是設(shè)法對消息進(jìn)行加密，使得只能是具有特

5、殊權(quán)利的人（接受者）才能夠接受和閱讀信息。而另一方則是盡力設(shè)法截獲信息，破譯密文，或者用修改以后的假信息欺騙接收者。在本文中，我們主要討論的是前一方，即考慮用何種方法能夠?qū)ο⑦M(jìn)行安全、有效且快捷的加密，保證消息的傳送。待加密的消息被稱作明文明文(plaintext)，用某種方法偽裝消息并隱藏它的內(nèi)容的方法稱作加密加密(encryption)，被加密以后的消息稱為密文密文，而把密文轉(zhuǎn)變成明文的過程稱為解密解密。加密體制中的加密運(yùn)算是由一個算法類組成，這些算法類的不同運(yùn)算可用不同的參數(shù)表示，不同的參數(shù)分別代表不同的算法，被稱作密鑰密鑰，密鑰空間密鑰空間是所有密鑰的集合。密碼體制密碼體制一般是指密

6、鑰空間與相應(yīng)的加密運(yùn)算結(jié)構(gòu)，同時還包括了明文和密文的結(jié)構(gòu)特征。在密碼體制的設(shè)計和評價中要考慮到以下一些基本原則：（1） 不可破原則，指該密碼體制在理論上或?qū)嶋H上是不可破解的。（2） 部分信息丟失不會影響整個系統(tǒng)的安全性。即硬件設(shè)備、加密算法或全部密文與部分明文這些信息的丟失不會危及整個系統(tǒng)的安全。（3） 與計算機(jī)、通信系統(tǒng)匹配原則。要求密碼系統(tǒng)不是獨立存在的，而可以在計算機(jī)或通信系統(tǒng)中使用。密碼體制發(fā)展到現(xiàn)在，已經(jīng)有了很多種不同的類型。但是從密碼體制所使用算法的分類上說，可以分為兩種。一種是利用了對稱算法，又稱作傳統(tǒng)密碼算法；另一種則是利用了公開密鑰算法。對稱算法對稱算法是指加密密鑰和解密密鑰

7、能夠互相推算出來，公開了一個也就相當(dāng)于公開另一方。因此對稱算法的密鑰只能由發(fā)送者和接收者兩方知道，他們必須事先商定好密鑰，這一點就涉及了密鑰交換協(xié)議。公開密鑰算法公開密鑰算法是指公開了加密算法以后不會泄露解密算法，因此和對稱算法相KEKD比，任何人都可以通過公開渠道（網(wǎng)絡(luò)或密鑰管理中心）已知他人的加密密鑰，把明文加密以后傳送給接收者，而只有擁有解密密鑰的人才能夠?qū)γ芪慕饷?。這在密鑰管理和消息KD的傳送方面更具有優(yōu)勢。另外，公開密鑰算法還可以運(yùn)用在數(shù)字簽名中。在目前應(yīng)用于實際生活比較廣泛的公鑰加密算法包含有 RSA 密碼體制和橢圓曲線密碼體制。RSA 密碼體制：密碼體制：1979 年，Shami

8、r Rivest 和 Adelman 提出了第一個也是應(yīng)用最廣的公鑰密碼體制，即 RSA 體制。經(jīng)過 20 多年的密碼分析和攻擊，迄今為止，RSA 被證明仍是安全的。設(shè)n=pq，p 和 q 是兩個大素數(shù)，a 和 b 是兩個整數(shù)，定義密鑰空間為。把 n，b 作為公開密鑰，而 p，q，a，作為秘( , , , , ):,1(mod ( )n p q a bnpq abn( )n密密鑰。整個加密算法就是 y=，而解密算法是，由 Euler( )modbKExxn( )modaKDyyn定理知道，成立，上述解密的方法正確。( )KxDy由于 RSA 加密算法是指數(shù)運(yùn)算，因此當(dāng)密鑰越大時，計算速度越慢。

9、RSA 算法比通常的 DES 算法慢了 1500 倍。并且 RSA 的計算量很大，為了要達(dá)到較高的安全程度，RSA的密鑰位數(shù)比其它的密碼體制大的多，現(xiàn)在一般需要 1024 位的密鑰。所以一般對速度要求較高的數(shù)字簽名或智能卡中的身份驗證不太使用RSA 密碼體制，而采用其它較快的算法。橢圓曲線密碼系統(tǒng)就是其中的一種。橢圓曲線密碼系統(tǒng)：橢圓曲線密碼系統(tǒng)：橢圓曲線密碼體制和 RSA 體制比較起來，所需要的密鑰量小，安全程度高，比如RSA 密碼體制需要 1024-bit 的密鑰才能達(dá)到的安全程度，利用橢圓曲線只需要 160 比特位的密鑰就能夠保證同樣的安全（文獻(xiàn)） ，密鑰長度的減少同時帶來了計算速度的提

10、高。即使是在剩余類環(huán)運(yùn)用離散對數(shù)而構(gòu)造的加密系統(tǒng)的安全程度也要低于橢圓曲線 ，因此橢圓PZ曲線系統(tǒng)不愧為一個性質(zhì)較好的密碼系統(tǒng)。橢圓曲線第一次運(yùn)用于公鑰密碼算法是在 1985 年 Neal Koblitz 和 V.S.Miller 提出來的。他們并沒有提出新的算法，只是把橢圓曲線運(yùn)用到已存在的公鑰密碼算法中，比如說ElGamal 加密算法。利用 ElGamal 思想構(gòu)造的橢圓曲線密碼體制如下顯示： 首先是產(chǎn)生密鑰階段。Bob 從中隨機(jī)選取充分大的整數(shù)，隨后計算出橢圓曲線nZBk上的點 P=（是橢圓曲線上的適當(dāng)?shù)囊稽c） ，將保密，作為秘密密鑰，并將 P 公開，Bk QQBk作為公鑰。 加密方法如

11、下：如果 Alice 想把消息 M（同樣是橢圓曲線上的一點）發(fā)送給 Bob,就從中隨機(jī)選擇整數(shù)后，計算出和的值，加密以后的信息就是橢圓曲nZnlZ1SlQ2SMlP線上兩點。12(,)S S解密：Bob 收到加密信息后，通過密鑰就可以計算 M=-得到消息12(,)S SBk2SBk1SM。縱觀上面提出的兩個公鑰密碼體制，再加上其它的密碼系統(tǒng)，在加密的時候都采用了單向函數(shù)的思想。單向函數(shù)單向函數(shù)是指函數(shù)滿足從 x 計算容易，但從計算 x 有可能不f( )f x( )f x可行。單向函數(shù)的構(gòu)造依賴于計算復(fù)雜度理論，即利用一些困難問題。上述兩個系統(tǒng)的安全性都依賴于一些數(shù)論中的基本困難問題。比如說 R

12、SA 體制利用了把大整數(shù) n 分解為兩個大素數(shù)的難度，而橢圓曲線是利用了求解離散對數(shù)問題的困難程度， （即根據(jù) P=和 Q 求解Bk Q中整數(shù)） 。這些密碼體制都是很成功的，在實際中也有了進(jìn)一步的應(yīng)用。對于本文來說，nZBk我們的主要目的是把組合群論的思想引進(jìn)到密碼學(xué)中，所以利用了組合群論中的一些困難問題，如字問題，共軛問題等等，由此構(gòu)造出新的密碼體制。協(xié)議協(xié)議（protocol）是指一系列的步驟，它包括兩方或者多方，設(shè)計它的目的是要完成一項任務(wù)。密鑰交換協(xié)議密鑰交換協(xié)議(key exchange protocol)是指兩人或多人之間通過一個協(xié)議取得密鑰并用于進(jìn)一步的加密算法中的方法。在實際的

13、密碼世界中密鑰交換其實是很重要的一個環(huán)節(jié)。比如說利用對稱加密算法，如果雙方?jīng)]有約定好密鑰，就必須再進(jìn)行密鑰交換。但是如何使得密鑰到達(dá)接收者和發(fā)送者手里是件很復(fù)雜的事情。最早利用公鑰密碼思想提出的密鑰交換協(xié)議有 Difffie-Hellman 算法。新的密鑰交換協(xié)議有利用組合群論中的辮群構(gòu)造的兩個協(xié)nB議，Anshel-Anshel-Goldfeld 協(xié)議和 Ko-Lee-Cheon 協(xié)議。第二節(jié)第二節(jié)電子支付系統(tǒng)的安全性電子支付系統(tǒng)的安全性電子商務(wù)作為新興事務(wù)，已經(jīng)隨著計算機(jī)和網(wǎng)絡(luò)技術(shù)的成熟得到了飛速發(fā)展，而且使得商家的整體經(jīng)營方式都有了變化。電子商務(wù)是以數(shù)字化的電子方式，以網(wǎng)絡(luò)為媒體進(jìn)行的商

14、業(yè)數(shù)據(jù)交換或其他商業(yè)活動。電子商務(wù)的一個重要組成部分就是電子支付系統(tǒng)。電子支付是指交易的各方是通過電子手段，比如說銀行的電子存款系統(tǒng)和電子清算系統(tǒng)來記錄和轉(zhuǎn)移資金的方式。一個安全、可靠的電子支付系統(tǒng)是電子商務(wù)的交易活動能夠正常進(jìn)行的保證。目前 INTERNET 上的電子支付系統(tǒng)主要有四種：信用卡、IC 卡、電子現(xiàn)金（e-Cash）和電子支票（e-Check） 。一般來說，電子支付系統(tǒng)必須滿足以下的安全性要求，包括有消息的保密性、能夠確認(rèn)雙方都具有合法的交易身份的能力、保證交易完畢以后的信息是無法修改的和交易以后各方對業(yè)務(wù)的不可否認(rèn)性。作為電子支付系統(tǒng)的不同代表，電子現(xiàn)金和電子支票雖然有一定的共

15、性，但在安全性要求和性質(zhì)方面有著各自獨特的特點。電子支票和紙張支票轉(zhuǎn)移支付的原理類似，是利用數(shù)字傳遞將錢款從一個賬戶轉(zhuǎn)移到另一個賬戶的電子付款方式。在電子支票實現(xiàn)的過程中，它的安全性問題是，如何保證銀行、用戶、商場對電子支票進(jìn)行簽名的有效性。由于轉(zhuǎn)賬在銀行、用戶和商場三方進(jìn)行，在每一次交易完成以后都必須對消息簽名，用來保證交易信息的真實、完整和不可否認(rèn)。所以在交易過程中將會涉及到數(shù)字多簽名。在本文中，我們最后討論了一種利用辮群構(gòu)造的多簽名體制，可以把上述多簽名運(yùn)用到電子支票轉(zhuǎn)賬系統(tǒng)中去。電子現(xiàn)金是一種以數(shù)據(jù)形式流行的貨幣，因此和支票相比，電子現(xiàn)金更強(qiáng)調(diào)滿足隱私性和可分割性，另外，雖然要保證用戶

16、的隱私權(quán)，電子現(xiàn)金出于安全性的考慮，還需要滿足電子現(xiàn)金的不可偽造性和不可重用性。如果同一份電子現(xiàn)金被使用兩次，使用者的身份就可以被發(fā)現(xiàn)。關(guān)于電子現(xiàn)金，現(xiàn)在最主要討論的是它的可分性的實現(xiàn)。 第二章第二章 組合群論和密碼學(xué)組合群論和密碼學(xué) 第一節(jié)第一節(jié) 基礎(chǔ)知識和背景基礎(chǔ)知識和背景自從 1984 年 N.R.Wager 和 M.R.Magyarik 在中提出了第一個用組合群論的理論構(gòu)造公鑰密碼體制的方法以來，在密碼學(xué)家們的共同努力下，利用組合群論的理論已經(jīng)提出多個公鑰密碼體制和密鑰交換協(xié)議。由于組合群論中的數(shù)學(xué)工具和以前數(shù)論中的內(nèi)容截然不同，有必要對組合群論中的一些定義和定理加以說明，從而可運(yùn)用到

17、密碼學(xué)中去，得到不同的加密算法。群 G 稱作是有限生成的有限生成的（finitely generated） ，如果 G 存在有限個生成元，滿1,2,g g,ng足 G 中任意一個元素（又稱為字）都可以表示成生成元和它們的逆的有限乘積。群 G 稱作是可以有限表示的可以有限表示的（finitely represented） ，如果在 G 中有有限個元素，1r，滿足在群 G 中，其中 e 是單位元，那么，2rkr1re2rekre1r2r稱為 G 的生成元的一組定義關(guān)系， 。kr12,g g,ng換一種角度，如果把群 G 看成是 n 個元素生成的自由群的商群，X 12,a a,naF(X)即存在的正

18、規(guī)子群，使得成立，那么 G 是可以有限表示的意思是：如果，F(xiàn)(X)NF(X)G=N1r，對應(yīng) F(X)中的元素，那么是 F(X)的正規(guī)子群 N 的生成2rkr1w2wkw12,w w,kw元?？梢杂邢薇硎镜娜?G 可表示為：G= ；21,g g,ng12,r r,kr辮群是一種有限表示的群，的生成元是，它的生成關(guān)系滿足：nBnB121n，時；當(dāng)時。因此，辮群可以表11ijije 2ij當(dāng)111ijijije 1ijnB示為：=。nB121;1,;2ijijijnijjiijij 當(dāng)當(dāng)組合群論中有些基本問題相對于某個特定的群是困難問題，可以作為構(gòu)造公鑰密碼體制的基礎(chǔ)，例如第一個公鑰密碼體制Wag

19、84就是根據(jù)不可解的字問題所構(gòu)造的，而隨后的Anshel93等主要運(yùn)用了組合群論中的共軛問題。字問題字問題(word problem)：是否存在一個算法來判斷群 G 中的元素是不是單位元。一個問題是算法上可解的算法上可解的(algorithmically solvable)是指存在一組計算機(jī)程序，通過計算，對該問題的結(jié)果是“是”或“否”做出明確的回答。如果不存在這樣的程序，就稱這個問題是算法上不可解的算法上不可解的(algorithmically unsolvable)。關(guān)于字問題對于某些群是否是算法上不可解的，Novikov-Boone 定理（見）對此做出了肯定的回答，定理中利用了有限表示的

20、群，這也是用字問題作為困難問題構(gòu)造加密算法的基礎(chǔ)。Novikov-Boone 定理：定理：存在有限表示的群 G 有著算法上不可解的字問題，并且存在有效的算法 B，如果輸入有限表示的一個系統(tǒng) T，且該系統(tǒng)有著不可解的字問題，通過算法 B 將會輸出有限表示的群 B(T)，使得 B(T)有著算法上不可解的字問題。第一次提出利用組合群論的思想來構(gòu)造的Wag84密碼體制就利用了 Novikov-Boone 定理。共軛問題共軛問題(conjugacy problem)：是否存在算法來判斷群 G 中給定的任意兩個元素是共軛元素。所謂兩個元素 x,y 共軛是指，存在 G 中元素 w，使得成立。1yw xw關(guān)于

21、組合群論中是否存在群有著算法上不可解的共軛問題，同樣可由一個定理加以保證。在該定理中，所涉及的群是剩余有限群。一個群 G 被稱為是剩余有限剩余有限的(residually finite)，如果給定了群中任意一個元素，g,都存在 G 的正規(guī)子群，使得 g 不是中g(shù)GegNGgN的元素。運(yùn)用剩余有限的群，Miller 證明了具有算法上不可解共軛問題的群的存在性，這就是Miller 定理：Miller 定理定理：存在有限表示且剩余有限的群，其共軛問題是算法上不可解的。并且存在快速算法 C 使得輸入一個有限表示的群 G（G 的字問題不可解）后會輸出有限表現(xiàn)且剩余有限的群 C(G)，C(G)有著不可解的

22、共軛問題。Miller 定理是 1993 年 Iris Lee Anshel 和 Michael Anshel 提出的基于不可解的共軛問題而構(gòu)造的公鑰加密體制的理論基礎(chǔ)。辮群在組合群論應(yīng)用于密碼學(xué)中扮演了重要的角色。在 1999 年 I.Anshel，M.AnshelnB和 D.Goldfeld 提出的密鑰交換協(xié)議和 2000 年Hyoung.Ko，Sang Jin Lee 和Jung Hee Cheon提出的密鑰交換協(xié)議和加密算法中，他們都利用了辮群的共軛問題，這是因為辮群的一些重要性質(zhì)可以很好的利用到密碼體制中去。 辮群的定義在前面已經(jīng)提到過了，但是辮群除了可以用有限生成元表示出來以外，還

23、有著其獨特的幾何意義。辮群中每一個元素都對應(yīng)了兩條平行直線間的 n 股線，每一股nB線的兩個端點開始于上面的平行直線，并中止于下端對應(yīng)平行直線。下面的兩幅圖對應(yīng)于中的生成元和。如圖一對應(yīng)于，圖二對應(yīng)于。nBi1ii1i1ii+1n圖一11ii+1n圖二辮群中的兩個元素 a，b 相乘在幾何上對應(yīng)了把兩個辮群的圖像拼接起來。另外，中nB兩個元素相等從幾何上來說，是指 a，b 兩個元素對應(yīng)的圖案能夠在三維空間中從一個圖像連續(xù)的變動到另一個。根據(jù)文獻(xiàn)，辮群有一些性質(zhì)特別適合密碼學(xué)的要求，用來構(gòu)造公鑰密碼體制。辮群的元素可以通過標(biāo)準(zhǔn)形式(canonical form)來統(tǒng)一表示,即由 p+1 個參量表示

24、，12( ,u ,)pu 是整數(shù)，代表了一個 n 階置換，該表示是唯一的。辮群內(nèi)元素的乘法和求逆都存在快速i算法，可以用計算機(jī)編程計算。并且辮群中有很多的困難問題可以作為構(gòu)造密碼體制和密碼交換協(xié)議的基礎(chǔ)，比如說辮群的共軛問題就是困難問題。 第二節(jié)：第二節(jié)： 密碼體制和密鑰交換協(xié)議密碼體制和密鑰交換協(xié)議2.2.1 Wag84公鑰密碼體制公鑰密碼體制1984 年 N.R.Waner 和 M.R.Magyarik 利用了有限表示群的不可解的字問題，構(gòu)造了第一個以組合群論思想為基礎(chǔ)的公鑰密碼體制。由前面的 Novikov-Boone 定理可知，存在群滿足不可解的字問題，這是Wag84公鑰密碼體制成立的

25、基礎(chǔ)。下面是整個加密算法：取 G 是有限表示的群，有著不可解的字問題，G 可以表示為：12,Ga a,na121,1,1muuu利用一個秘密同態(tài)函數(shù) A 可以是大的有限群或者是有限表示的群，它:h GA的字問題有著快速的解法。在群 G 中取兩個字和，使得這兩個字滿足。把0y1y01()()h yh y群 G，和公開，作為公鑰，而把同態(tài)函數(shù)保密，作為秘密密鑰。0y1yh加密算法很簡單，只要將消息 M 寫成二進(jìn)制數(shù)的形式以后，每個 0-bit 位由隨機(jī)選擇的代替，只要滿足（意思是指和是 G 中同一個元素的不同表現(xiàn)形式） 。0y00modyyG0y0y同理，1-bit 位用代替，。這樣的話，消息 M

26、 中的每個比特位都有 G 中的元1y11modyyG素來表示，從密文中任取 G 的一個元素 z，由于 G 有著不可解的字問題，即無法利用算法判斷和中哪一個是單位元素，因此，加密是成功的。10zy11zy解密時需要運(yùn)用解密密鑰 h，在密文中取元素 z，只要 h(z)=h(),說明 z 代表的比特位0y是 0，反之是 1。因為在 A 中字問題是可解的，上面的結(jié)果可以判斷，因此消息被解密。對于以上的利用組合群論所構(gòu)造加密算法的討論：首先它需要找一個合適的具有不可解的字問題的群，要使加密算法適合實用，必須使群里的元素應(yīng)該在群中有唯一的標(biāo)準(zhǔn)表示，通過計算機(jī)很容易進(jìn)行存儲和計算。即使是這樣，原文中一個比特

27、位的 0 或者 1 經(jīng)過轉(zhuǎn)化成密文以后，需要用群的一個元素來表示。而群中元素在計算機(jī)的傳輸和存儲的方面，所需要的存儲量遠(yuǎn)遠(yuǎn)大過比特位。并且在密文處理方面有很多的不方便的地方，比如說如何選擇和 Y0或者 Y1等價元素，有沒有快速算法等等，這些缺點都降低了效率，所以總的來說，這只是一個不太成熟，不能實用的方案，但畢竟，它在把組合群論利用到密碼學(xué)中開創(chuàng)了新的一步。2.2.2Anshel93密碼體制密碼體制接下來由文獻(xiàn)，在 1993 年，M.Anshel 和 I.Anshel 繼續(xù)了利用組合群論中的問題提出了另一個新的加密算法，與前一個有所不同的是，這次他們所采用的群是有限生成的群，群中元素具有不可解

28、的共軛問題，并且群是剩余有限群。在他們所提出的方案中，需要用到前面提到的 Miller 定理作為保障。G 中任意的一個元素 g，存在從 G 到有限群的一個同態(tài) ，滿足。任取 G 中( )1g一個元素，存在 G 的正規(guī)子群，使得不是中的元素，在群 G 中，記 z 為單位元wWNwWN素，由于 G 是剩余有限的，存在一個有限群，可考慮同態(tài) H：GG/，因為不/WG NWNw屬于，由此，由于和不是共軛元素，而同態(tài)運(yùn)算保持WN( )1H w ( )1H z ( )H w( )H z共軛性質(zhì)不變，和 z也不是共軛元素。把同態(tài)運(yùn)算 H 保密，并假設(shè)在商群中，求解w/WG N共軛問題和字問題在算法上是多項式

29、內(nèi)實現(xiàn)的。在加密問題上 Anshel 所采用的方法與前文類似，那就是把 1 用任一與 z 共軛的元素代替，把 0 用與共軛的任一元素代替，用這個方w法，可隨機(jī)地把明文中的二進(jìn)制數(shù)字轉(zhuǎn)化成密文中組合群中的元素，而通過保密的同態(tài)加以解密，最終得到原文。wag84和Ansh 93從設(shè)計的思想上來說，是基本上類似的，它們都是設(shè)法利用組合論中有特定性質(zhì)的群，即有著不可解的字問題或是共軛問題，以群中兩類不同的元素分別代表 0和 1 兩個數(shù)字，同時均將一個同態(tài)映射做密鑰保存，只要知道了所選用的群和兩個代表 0和 1 的群元素就可以對消息進(jìn)行加密，作為密鑰的同態(tài)運(yùn)算所對應(yīng)的群的字問題和共軛問題則是可解的。它們

30、的差別是wag84所選用的群是以字問題做為困難問題，而Ansh93是把共軛問題做為困難問題，兩者的區(qū)別是群選擇的不同。2.2.3Anshel-Anshel-Goldfeld密鑰交換協(xié)議密鑰交換協(xié)議1999 年的時候，不同于以上的幾個公鑰密碼系統(tǒng)，在組合群論的基礎(chǔ)上，I.Anshel，M Anshel 和 D Goldfeld 提出了一個新的密鑰交換協(xié)議（見和） ，該協(xié)議中所采用的群是辮群，具有不可解的共軛問題，但是辮群的字問題可以在多項式時間內(nèi)解決。在協(xié)議中，Anshel99利用換位子的思想，XYX-1Y-1，其中 X，Y 均為辨群中的元素，其中 XYX-1Y-1nB可以看成是 Y 的共軛元素

31、和 Y-1相乘得到，或者可以看成是 X 和 X-1的共軛元素相乘得到的，具體的密鑰交換步驟如下：兩方 Alice 和 Bob 分別公布字 a(1)，a(2)，a(n)；b(1)，b(2)，b(m)。這些字均從群 G=S|D得到，其中 S 是生成元，D 是定義關(guān)系。Alice 和 Bob 之間的密鑰由它的共同的行為產(chǎn)生，Alice 和 Bob 同時執(zhí)行以下的步驟，一起產(chǎn)生秘密密鑰：1、Alice 首先進(jìn)行如下運(yùn)算，Alice 選擇一個群 G 中的由 a(1)，a(2)，a(n)生成的秘密的字 X，對每一個 b(i)進(jìn)行共軛運(yùn)算，產(chǎn)生 m 個新字 c(1)，c(2)，c (m)，c (i)=X b

32、(i)X-1。2、Alice 對每一個進(jìn)行改寫，寫成 B(i)的形式，B(i)和 是G 中同一個元素的不c(i)c(i)同表示，i=1，m。B(i)能夠完全掩蓋住中有關(guān) X 的秘密信息。由于 B(i)和 b(i)是關(guān)c(i)于 X 的共軛元素，但不能從 B(i)中推斷出 X 是什么（G 有著不可解的共軛問題） ，X 是不可知的。3、Alice 通過公開的渠道把 B(1)，B(2)，B(m)傳送給 Bob。在 Alice 進(jìn)行計算的同時，Bob 進(jìn)行類似的計算。1、Bob 從 b(1)，b(2)，b(m)生成的 G 的子群中，選擇一個秘密的元素 Y，用每個a(i)進(jìn)行共軛等。產(chǎn)生d(1)，d(2

33、)d(n)，d(i)=Ya(i)Y-1。2、對每個d(i)進(jìn)行改寫，寫成 A(i)的形式，使得 A(i)和d(i)表示相同的元素。3、Bob 把 A(1)，A(2),A(n)傳送給 Alice。第三步，Alice 和 Bob 可根據(jù)所得的結(jié)果分別計算出換位子（X，Y）=XYX-1Y-1。因為，Alice 可以從 V=X（YXY-1）-1=Xx（A(1)） ，A（n）)-1中計算，如果 X=x（a(1)，a(n)） 。并且 Bob 也可以計算換位子 W=（XYX-1）Y-1=y（B(1)，B(2)，B(m)）Y-1，如果Y=y(b(1),b(n)。X 由 a(1)，a(2)，a(n)生成，僅為

34、Alice 所知，而 A(1)，A(2),A(n)是a(1)，a(2)，a(n)關(guān)于 Y 的共軛元素，通過類似的計算，Alice 可以知道 YXY-1，Bob 也是可以由秘密的 Y 以及 Alice 傳送給它的 B(1)，B(2)，B(m)來得到 XYX-1，但是對于Alice 所掌握的字 X 一無所知，當(dāng) Alice 和 Bob 經(jīng)過計算出 V 和 W 以后，V 和 W 是同一個字的不同表現(xiàn)形式，從字 V 和 W 得到 Alice 和 Bob 的共同的密鑰有兩個方法，第一個是辮群 G 中的每個元素都有且僅有一種唯一的特殊表現(xiàn)形式，稱作經(jīng)典形式，那么把 V 和 W 都寫成經(jīng)典形式之后，這時它們

35、的標(biāo)準(zhǔn)形式是相同的，然后可以定義從辮群的標(biāo)準(zhǔn)形式到二進(jìn)制數(shù)的單向函數(shù) H，從而使密鑰 K=H（V）=H（） ，第二個方法是把 G 作為群作用在某個集合 S 上，并且滿足 E（S）=SG1（G2（S） ）=（G1G2） （S） ， （G1 、G2屬于 G，E 是 G 的單位元） ，且 G 內(nèi)不同的字作用到 S 上的元素 S 所得的值也是不同的。在這種條件下，密鑰K=V（S）=W（S）也同樣可以得到。對Anshel-Anshel-Goldfeld密鑰交換協(xié)議的分析：首先我們不知道，上述的密鑰交換協(xié)議的安全性是否以辮群共軛問題的難解程度為基礎(chǔ)的，但是，實際上已知 XYX-1和 Y 求解 X 的問題和

36、已知 XB（1）X-1，XB（2）X-1，XB（M）X-1和 B（1） ，B（2） ，B（M）的值來求解 X 的困難程度是不一樣的，顯然后一個問題比前面的問題要容易的多，后一個問題所面臨的困難問題是不同于標(biāo)準(zhǔn)形式的共軛問題，我們可以把它稱之為新的共軛問題（MSCSP） ，應(yīng)該說這個也是從算法上來說不可解的。另一點是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

37、（M）X-1或 YA（1）Y-1，YA（N）Y-1中不能得出 X，Y 的值的時候，通過改寫，即把上述這些辮群里的元素寫成標(biāo)準(zhǔn)形式時，并不能夠保證所有的標(biāo)準(zhǔn)形式能完全掩蓋住秘密信息。但是只要有一個元素泄露出 X 或者 Y 的值，那么密鑰就可以被破解，所以 X（B1）X-1，XB（M）X-1和YA（1）Y-1，YA（N）Y-1中的秘密信息必須完全被改寫掉。2.2.4Ko-Lee-Cheon密鑰交換協(xié)議和公鑰密碼體制密鑰交換協(xié)議和公鑰密碼體制從上述的密鑰交換協(xié)議可以看出，上述的協(xié)議的主要思想是利用組合群論中的一般理論，關(guān)于換位子的思想適用于任何一個群，只是在具體的實現(xiàn)方法上，才使用了辮群，因為辮群在

38、實現(xiàn)過程中，有一些較好的優(yōu)點。比如有唯一的標(biāo)準(zhǔn)形式，并且它的字問題有著快速算法，而共軛問題是困難問題等等。應(yīng)該可以看出，任何具有類似性質(zhì)的群都可以做為構(gòu)造Anshel-Anshel-Goldfeld密鑰交換協(xié)議的群。下面所提到的Ko-Lee-Cheon密鑰交換協(xié)議則是更立足于辮群本身的性質(zhì)（文獻(xiàn)） ，因此在討論密鑰交換協(xié)議的時候，對于密鑰交換協(xié)議的安全性分析將更加成熟一點，并且能夠相對比較實用。韓國學(xué)者 Hyoung Ko，Sang Jin Lee 和 Jung Hee Cheon 提出，在辮群中有一些問題屬于困難問題，其中能夠適用于構(gòu)造密鑰體制的有以下一些：假設(shè)是由，生成，由，生成，mn，那

39、么，辮群nB12,1nmB12,1m可以看成是的子群，那么有以下幾個問題是困難問題：mBnB1、普通的尋找共軛元素問題（GCSP）元素（X，Y），并且 Y=BXB-1，其中，B，mnnmBBnB問題：尋找 A使行 Y=AXA-1成立，mB2、共軛元素分解問題（QCDP）（X，Y） ，滿足 Y=BXB-1，B，mnnmBBmB問題：尋找，滿足。AAmBYA XA3、尋找 P 次根問題，（X,Y），滿足 Y=XP，X，nnBBnB問題：尋找 Z，滿足，Y=ZP。nB在上述幾個問題的基礎(chǔ)上，Hyoung Ko 等提出了密鑰交換協(xié)議，上述協(xié)議所利用的是第一個困難問題，在中取兩個群，和，是由，生成，而由

40、nBlLBrRBlLB121lrRB，生成，由于辮群的生成元滿足條件，因此對于任意1l1l r ijji 2ij的 A，B，都能滿足 AB=BA。所以辮群中的子群和 之間的任意兩個lLBrRBnBlLBrRB元素具有交換性，這是能否滿足密鑰系統(tǒng)的關(guān)鍵。密鑰交換協(xié)議的具體實現(xiàn)如下：1、首先選擇充分大并且較合適的兩個整數(shù)（L，R）以及辮群，和。在中選nBlLBrRBnB擇一個比較合適的元素 X，并將 X 公開。2、密鑰交換者 Alice 和 Bob 分別執(zhí)行以下步驟：（A）Alice 從中任意選擇一個秘密元素 A，把 Y1 =AXA-1，傳送給 Bob。lLB（B）Bob 從中選擇一個元素 B，并

41、將，Y2=BXB-1傳送給 Alice，rRB（C）Alice 收到 Y 以后，計算 K=AY2A-1（D）Bob 收到 X 以后 ，計算 K=BY1B-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）不完全是等價的，但是兩者之間有緊密的關(guān)系。關(guān)于這一點，有點類似于 Diffie-Hellman 的密鑰交換協(xié)議，因為 Diffie-Hellman 協(xié)議中就

42、是由已知 GX和 Y 以及 GX，X 中分別得到 GXY，但是這個問題可以歸結(jié)為求解離散對數(shù)的問題。在辮群的協(xié)議中，也是類似的。竊聽者即使能夠知道 AXA-1，B 和 BXB-1和 A 但要計算 ABXA-1B-1，還是會歸結(jié)為求解共軛元素的問題。雖然Anshel99也是利用了辮群的共軛算法，但在這一點上和韓國學(xué)者提出是的不一樣的。 與密鑰交換協(xié)議非常相似，Hyoung Ko 等同時利用辮群可以構(gòu)造一個新的公鑰密碼體制。運(yùn)用到的方法和上面基本一致，只是需要增加一個散列函數(shù)。首先定義一個從辮群元素到二進(jìn)制數(shù)字的單向散列函數(shù) H: 0，1Kl+rB1、產(chǎn)生公鑰及私鑰階段。（A） 從中選擇一個適當(dāng)?shù)?/p>

43、，由，生成的 X。l+rB12, 1l r （B） 取中元素 A，lLB（C）設(shè) Y=AXA-1是 X 關(guān)于 A 的共軛，把 Y 公開，當(dāng)做公鑰，并且使 A 保密，當(dāng)作私鑰。2、加密運(yùn)算：如給定明文 M 0，1K和（X、Y）以后，（A）任意從中選擇元素 BrRB（B）加密以后的密文是（C，D） ，C=BXB-1和 D=H（BYB-1）M3、解密通過計算 M=H（ACA-1）D 可得，上面這個步驟的原因是因為 ACA-1=ABXB-1A-1=（BA）XA-1B-1=BYB-1，因此，H（ACA-1）D=H（BYB-1）H（BYB-1）M=M。 +代表了異或運(yùn)算。這個新的加密算法和密鑰交換協(xié)議的理

44、論基礎(chǔ)相同，并且比較實用。第三章第三章 組合群論在電子支票的多簽名體制中的應(yīng)用組合群論在電子支票的多簽名體制中的應(yīng)用 第一節(jié)第一節(jié) 三方密鑰交換協(xié)議三方密鑰交換協(xié)議考慮將兩方的密鑰交換協(xié)議推廣到三方或者更多的人中去，就必須利用協(xié)議本身的性質(zhì)。關(guān)于 Anshel-Anshel-Goldfeld 密鑰交換協(xié)議，因為協(xié)議中利用了換位子，很11XYX Y難推廣到多方中去。但是 Ko-Lee-Cheon 協(xié)議采用了 Diffie-Hellman 算法的思想，因此可以稍做修改，使參加協(xié)議的人增加到三人或者多人。下面就是具體的三方協(xié)議。首先可在辮群中取三個子群，和，由，,生成，由lLBkMBrRBlLB12

45、1lkMB，生成，由，生成，其中 l，k，r 滿足條件：l+r+k=n。1l1l k rRB1l k 1l k r 利用辮群中生成元的性質(zhì)可知，任意，都滿足：，alLBbkMBcrRBabba，這就是說，群，和中任意元素都是可以交換的。和兩方協(xié)bccbaccalLBkMBrRB議類似，Alice，Bob 和 Carol 執(zhí)行以下的步驟：(1)Alice ，Bob 和 Carol 共同選擇一個恰當(dāng)?shù)霓p元，。xnxB(2)Alice 從中隨機(jī)選擇辨元，把發(fā)送給 Bob。lLBa11xaxa(3)Bob 從中任意選擇辮元，把發(fā)送給 Carol。kMBkbMB12xbxb(4)Carol 從中任意選擇

46、，把發(fā)送給 Alice。rRBrcRB13xcxc(5)Alice 把發(fā)送給 Bob。113yax a(6)Bob 把發(fā)送給 Carol。121ybxb(7)Carol 把發(fā)送給 Alice。132ycx c(8)Alice 計算密鑰。13kay a(9)Bob 計算密鑰。11kby b(10)Carol 計算密鑰。12kcy c由于， 三個元素有交換性，因此有以下等式成立：abc；11111111132()()ay aa cx caac bxbc aabcxc b a和 ；111111111123()by bb acxc ababcxc b acy cay a可知為 Alice，Bob，Ca

47、rol 三方的共同密鑰。因為這個三方協(xié)議和 Diffie-Hellman 協(xié)議類似，k由 Diffie-Hellman 協(xié)議的安全性可知，上述協(xié)議是安全的，它的困難程度基于在辮群中破解共軛問題的難度。另外，出于安全性的考慮，由文獻(xiàn)7中對滿足條件的辮元所加的限制條x件可知在上述協(xié)議中， 不能取成的類型，其中，而x123a a a z1laLB2kaMB3raRBz 是中能夠和，和中元素都交換的辮元。因為如果=，密鑰 k 滿足條nBlLBkMBrRBx123a a a z件： k= = 。111abcxc b a111123aa a ba b ca c z又因為，通過公開傳輸?shù)模?1123()xa

48、a aa a z12123()xa ba ba z13123()xa a ca cz1x，和就可以計算得到，從而計算出密鑰。因此，應(yīng)該選擇適當(dāng)2x3xx11aa a12ba b13ca c的 x 滿足安全性的要求。不過有一點比較有利的是，同樣是在文獻(xiàn)7中對 x 的討論中，上述 x 出現(xiàn)的概率非常小，一般不用多做考慮。 第二節(jié)第二節(jié) 基于辮群的多簽名體制方案基于辮群的多簽名體制方案3.2.1 多簽名介紹多簽名介紹利用公開密鑰算法對一段消息進(jìn)行數(shù)字簽名，這是簽名方案中最常用的一種方法，它在理論上發(fā)展的已經(jīng)比較完善，在實際應(yīng)用中也有成熟的體制。比如說由 RSA 加密算法轉(zhuǎn)化而成的數(shù)字簽名、ElGam

49、al 簽名方案、Schnorr 簽名算法、經(jīng)過改進(jìn)的 Fiat-Shamir 簽名方案以及 Guillon-Quisquater 數(shù)字簽名方案等等。這些數(shù)字簽名的安全性或是建立在大整數(shù)分解的難度上，或是建立在計算離散對數(shù)的難度上，或是利用其他數(shù)論中的困難問題。不過這些方案都有一個特點，這些數(shù)字簽名只是單個人對一份文件的簽名，很少有簽名方案可以拓展到多個人對同一份文件的簽名上去。即使有，也只是簡單的通過單簽名加以迭代而得到的。但是由于實際應(yīng)用的需要，對簽名人數(shù)提出了更高的要求?，F(xiàn)在需要一種新的簽名方案，可以使多個人對同一份文件進(jìn)行簽名，這就是多簽名多簽名。多簽名有著廣泛的應(yīng)用，比如說一份文件必須

50、有多個人簽署才能執(zhí)行，缺乏了其中任意一人的同意就不可以；或者是電子支票在銀行、客戶、商店之間轉(zhuǎn)賬時，銀行、客戶、商店為了使轉(zhuǎn)賬過程得以紀(jì)錄，在每次交易時對同一份文件支票進(jìn)行數(shù)字簽名，也需要利用多簽名的技術(shù)。這些應(yīng)用使得數(shù)字多簽名方案的發(fā)展成為一種必然。為了滿足著一要求，密碼學(xué)家利用數(shù)學(xué)理論也構(gòu)造了一系列多簽名方案，其中比較實用且計算速度較快的是日本學(xué)者 Eikoh Chida，Tako Nishizeki 等基于單向環(huán)同態(tài)所構(gòu)造的多簽名方案。在本文中，除了介紹他們的多簽名體制以外，我們還考慮利用辮群中的困難問題對基于單向環(huán)同態(tài)而構(gòu)造的多簽名方案進(jìn)行改進(jìn)，提出把組合群論思想和多簽名方案結(jié)合起來，

51、提出一個新的多簽名方案。數(shù)字多簽名的安全性要求：數(shù)字多簽名的安全性要求：多簽名方案由于簽名過程涉及了多個人，并且簽名完成以后要求能檢驗所有人對同一消息的簽名，所以在安全性方面比一般的數(shù)字簽名有著更高的安全性要求。首先要求多簽名能夠抵抗外部攻擊，3.2.2 基于單向環(huán)同態(tài)的多簽名體制基于單向環(huán)同態(tài)的多簽名體制在文獻(xiàn)中，Eikoh Chida，Tako Nishzeki 等首先提出了問題：在代數(shù)結(jié)構(gòu)中除了群中存在單向群同態(tài)函數(shù)（即函數(shù)既是單向函數(shù)，也滿足群中的同態(tài)運(yùn)算）以外是否還有其它的單向函數(shù)同態(tài)，比如在環(huán)，幺半群中等。實際上，以前所構(gòu)造的 RSA 加密算法、離散對數(shù)算法都是利用了基于單向群同態(tài)

52、的單向陷門函數(shù)。而環(huán)同態(tài)對于這個問題的肯定回答，他們是構(gòu)造了一個單向環(huán)同態(tài)來實現(xiàn)的。如果 A 是交換環(huán) R（A，+， ） ，U 是在加法+下的 A-模，對于任意 A 和 U，直和AU 內(nèi)的元素和，可定義AU 中的加法：（AU） （AU）AU11(,)a u22(,)a u和乘法*：（AU） （AU）AU 如下：=；*=；可以證明所得的11(,)a u22(,)a u1212(,)aa uu11(,)a u22(,)a u121 122(,)aa aua u（AU，*）是交換環(huán)。利用這個交換環(huán)，Eikoh Chida 等有進(jìn)一步證明了單向環(huán)同態(tài)的存在性，這可以表述為下面這個定理：定理：定理：U，

53、V 都是有限交換群，=n，如果 U 和 V 內(nèi)二進(jìn)制運(yùn)算是多項式內(nèi)可計算的，U如果存在單向群同態(tài)函數(shù)：UV，那么存在單向環(huán)同態(tài) F: 。 （F 的定fImnnZUZf義是：F()=（） 。 ）, n x,( )n f x為了構(gòu)造適當(dāng)?shù)亩嗪灻w制，文獻(xiàn)中利用了上的同態(tài)函數(shù)：:，1PZf*1PPZZ，g 是的生成元，這個函數(shù)是單向的。運(yùn)用上面的定理，可以得到單向( )modxf xgp*PZ環(huán)同態(tài)函數(shù)：F: ，。關(guān)于文獻(xiàn)中有根據(jù)上述函數(shù)而*11()()PPPPZZZZ( , )( ,)xF n xn g構(gòu)造的多簽名體制，在此不再詳述。3.2.3 基于辮群的多簽名體制基于辮群的多簽名體制 如果要把辮

54、群應(yīng)用到構(gòu)造單向環(huán)同態(tài)中，就必須考慮辮群的很多基本性質(zhì)和上述單向群同態(tài)中對群的要求不完全相同，因此，必須對直和 AU 和 AV 的一些定義加以修改，以滿足單向函數(shù)的要求，不過用辮群 Bn很難滿足單向函數(shù)同時又是環(huán)同態(tài)，所以經(jīng)修改后的多簽名體制和文獻(xiàn)中的有所不同。首先，辮群 Bn是無限群，不是有限的。對于這一點，可以把環(huán) Zn改成環(huán) Z，把直和改成。另外一點限制是，AU 中的 U 是交換群，這是 AU 是交換環(huán)的11ppZZnZB定義中對 U 的基本要求，但是辮群 Bn不是交換群。因此，利用辮群不一定能夠構(gòu)造出單向環(huán)同態(tài)，不過根據(jù)辮群的性質(zhì)，辮群還是可以用來構(gòu)造多簽名體制。注意在文獻(xiàn)中提到了辮群

55、的一個困難問題：，尋找滿足( , ),ny pBZ,pnyxxB條件的 x。利用上述困難問題構(gòu)造單向函數(shù)，（p是固定的正整數(shù)）,如:nnfBB( )pf xx果中元素 x, y 滿足條件，根據(jù)前文 Eikoh Chida 等證明的定義和定理，nB()( ) ( )f xyf x f y則在直和中定義函數(shù) F: 為，F(xiàn)(,)也是單向函數(shù)，并且nZBnnZBZB( , )( ,)pF n xn x，同時滿足加法和乘法運(yùn)算： ；( , )n x( , )m y( , )( , )( , )( , )F n xm yF n xF m y。加法和乘法的同態(tài)性質(zhì)正是構(gòu)造多簽名體制所必須使用的。( , )(

56、 , )( , ) ( , )F n x m yF n x F m y因為，。由，生成的 Bn的子群 LBl和，ijji 2ij121l1l生成的子 6 群內(nèi)元素是互相交換的，即任意， ，所以只要1l r rRB,abbalaLBrbRB取元素，a,b 滿足群的同態(tài)性質(zhì)：=，因此直laLBrbRB()()pf abab( ) ( )ppa bf a f b和中的，也滿足加法和乘法的同態(tài)性質(zhì)。nZB( , )n a( , )m b利用上述性質(zhì)，構(gòu)造多簽名體制如下：記，為簽名方，對，為的秘密密鑰，1U2UrU1ir ( ,)iiiXn xiUiixLB其中是的子群，每個分別由生成元，生成。是iLB

57、nBiLB(1)1it1it()( ,)piiiiYF Xn x的公共密鑰，并且假設(shè)存在散列函數(shù) H: ，也是的子群，生成元是iU1rZZLB1rLBnB，。因此中的任意元素都滿足交換性。設(shè)待簽名的消息為 M，并且 H(M)1rt(1)1rtiLB=。，等簽名方相繼執(zhí)行一下步驟：( , )n x1U2UrU第一名簽名者：1U（1） 隨機(jī)生成 ，與的定義類似。 1112(,)rkm yZLB2rLBiLB（2） 計算 。112( )rRF kZLB（3） 計算 1111*()*SXRH Mk（4） 把 M、和作為簽名結(jié)果傳給第二位簽名者。1R1S第 位簽名者：i（1） 生成。1(,)iiir i

58、km yZLB （2） 計算。1( )iir iRF kZLB （3） 計算。1*(*()*)iiiiiSSXRH Mk（4） 把，和傳送給下一位簽名者，如果是，則把，1,M RiRiSrU1,M R和傳送給驗證方 V。rRrS因為每個和及 H(M)分屬不同的子群，乘法運(yùn)算具有交換性。因此每個簽名方都能ikiX通過等式：11111()(*(*()*)()*( ()*()()*( )*()()* *()()*iiiiiiiiiiiiF SF SXRH MkF SF XF RF H MF kYF RF H MRYF RF H MR來驗證前人的簽名。如果說等式能夠成立，說明簽名是有效的。對上述多簽名體制的分析：因為這個多簽名體制中構(gòu)造了（2r+1）個中的子群，每個都有 t 個生成元，nBiLBiLB因此為了使這些子群能夠滿足條件，必須滿足（2r+1）tn。出于安全性的考慮，n 和 t 都必須取到充分大，而 r 則是根據(jù)簽名人數(shù)而定。上述多簽名體制的基本思想和基于單向環(huán)同態(tài)的多簽名體制非常相似，只是因為辮群中不滿足環(huán)同態(tài)的地方用子群來代替，用以保證iLB交換性質(zhì)的成立。另外，該多簽名體制的安全程度是基于通過公鑰來計()( ,)piiiiYF Xn x算秘密密鑰的困難程度的，易知這個問題的難度和已知求解 p 次根的困難( ,)iii