【正文】 式，以網(wǎng)絡(luò)為媒體進(jìn)行的商業(yè)數(shù)據(jù)交換或其他商業(yè)活動(dòng)。電子商務(wù)的一個(gè)重要組成部分就是電子支付系統(tǒng)。電子支付是指交易的各方是通過(guò)電子手段，比如說(shuō)銀行的電子存款系統(tǒng)和電子清算系統(tǒng)來(lái)記錄和轉(zhuǎn)移資金的方式。一個(gè)安全、可靠的電子支付系統(tǒng)是電子商務(wù)的交易活動(dòng)能夠正常進(jìn)行的保證。目前INTERNET 上的電子支付系統(tǒng)主要有四種：信用卡、IC 卡、電子現(xiàn)金（eCash）和電子支票（eCheck） 。一般來(lái)說(shuō)，電子支付系統(tǒng)必須滿足以下的安全性要求，包括有消息的保密性、能夠確認(rèn)雙方都具有合法的交易身份的能力、保證交易完畢以后的信息是無(wú)法修改的和交易以后各方對(duì)業(yè)務(wù)的不可否認(rèn)性。作為電子支付系統(tǒng)的不同代表，電子現(xiàn)金和電子支票雖然有一定的共性，但在安全性要求和性質(zhì)方面有著各自獨(dú)特的特點(diǎn)。電子支票和紙張支票轉(zhuǎn)移支付的原理類似，是利用數(shù)字傳遞將錢款從一個(gè)賬戶轉(zhuǎn)移到另一個(gè)賬戶的電子付款方式。在電子支票實(shí)現(xiàn)的過(guò)程中，它的安全性問(wèn)題是，如何保證銀行、用戶、商場(chǎng)對(duì)電子支票進(jìn)行簽名的有效性。由于轉(zhuǎn)賬在銀行、用戶和商場(chǎng)三方進(jìn)行，在每一次交易完成以后都必須對(duì)消息簽名，用來(lái)保證交易信息的真實(shí)、完整和不可否認(rèn)。所以在交易過(guò)程中將會(huì)涉及到數(shù)7 / 25字多簽名。在本文中，我們最后討論了一種利用辮群構(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ǔ)知識(shí)和背景自從 1984 年 和 在①中提出了第一個(gè)用組合群論的理論構(gòu)造公鑰密碼體制的方法以來(lái)，在密碼學(xué)家們的共同努力下，利用組合群論的理論已經(jīng)提出多個(gè)公鑰密碼體制和密鑰交換協(xié)議。由于組合群論中的數(shù)學(xué)工具和以前數(shù)論中的內(nèi)容截然不同，有必要對(duì)組合群論中的一些定義和定理加以說(shuō)明，從而可運(yùn)用到密碼學(xué)中去，得到不同的加密算法。群 G 稱作是有限生成的（finitely generated） ，如果 G 存在有限個(gè)生成元… ，滿足 G 中任意一個(gè)元素（又稱為字）都可以表示成生成元和它們1,2gn的逆的有限乘積。群 G 稱作是可以有限表示的（finitely represented） ，如果在 G 中有有限個(gè)元素 ， ，…， 滿足在群 G 中， ， ，…， ，其中 e 是單位元，1r2kr1re?2kr?那么 ， ，…， 稱為 G 的生成元 … 的一組定義關(guān)系， 。,g,n換一種角度，如果把群 G 看成是 n 個(gè)元素 { … }生成的自由群X12,an的商群，即存在 的正規(guī)子群 ，使得 成立，那么 G 是可以F(X)F(X)NF()G=有限表示的意思是：如果 ， ，… 對(duì)應(yīng) F(X)中的元素 ， … ，那么1r2kr1w2k… 是 F(X)的正規(guī)子群 N 的生成元。?12,w?,k8 / 25可以有限表示的群 G 可表示為：G= … ； …21,g,n12,rk辮群 是一種有限表示的群， 的生成元是 ， ，…， ，它的生nBnB?1n?成關(guān)系滿足： ， 時(shí)； 當(dāng)1ijije???ij??當(dāng) 1ijijije??時(shí)。因此，辮群 可以表示為： =1ij??nn。121。1, 2ijijijnijjij?????當(dāng)當(dāng)組合群論中有些基本問(wèn)題相對(duì)于某個(gè)特定的群是困難問(wèn)題，可以作為構(gòu)造公鑰密碼體制的基礎(chǔ)，例如第一個(gè)公鑰密碼體制[Wag84]就是根據(jù)不可解的字問(wèn)題所構(gòu)造的，而隨后的[Anshel93]等主要運(yùn)用了組合群論中的共軛問(wèn)題。字問(wèn)題(word problem)：是否存在一個(gè)算法來(lái)判斷群 G 中的元素是不是單位元。一個(gè)問(wèn)題是算法上可解的(algorithmically solvable)是指存在一組計(jì)算機(jī)程序，通過(guò)計(jì)算，對(duì)該問(wèn)題的結(jié)果是“是”或“否”做出明確的回答。如果不存在這樣的程序，就稱這個(gè)問(wèn)題是算法上不可解的(algorithmically unsolvable) 。關(guān)于字問(wèn)題對(duì)于某些群是否是算法上不可解的，NovikovBoone 定理（見(jiàn)②）對(duì)此做出了肯定的回答，定理中利用了有限表示的群，這也是用字問(wèn)題作為困難問(wèn)題構(gòu)造加密算法的基礎(chǔ)。NovikovBoone 定理：存在有限表示的群 G 有著算法上不可解的字問(wèn)題，并且存在有效的算法 B，如果輸入有限表示的一個(gè)系統(tǒng) T，且該系統(tǒng)有著不可解的字問(wèn)題，通過(guò)算法 B 將會(huì)輸出有限表示的群 B(T)，使得 B(T)有著算法上不可解的字問(wèn)題。第一次提出利用組合群論的思想來(lái)構(gòu)造的[Wag84]密碼體制就利用了NovikovBoone 定理。共軛問(wèn)題(conjugacy problem)：是否存在算法來(lái)判斷群 G 中給定的任意兩個(gè)元素是共軛元素。所謂兩個(gè)元素 x,y 共軛是指，存在 G 中元素 w，使得成立。1ywx??關(guān)于組合群論中是否存在群有著算法上不可解的共軛問(wèn)題，同樣可由一個(gè)9 / 25定理加以保證。在該定理中，所涉及的群是剩余有限群。一個(gè)群 G 被稱為是剩余有限的(residually finite)，如果給定了群中任意一個(gè)元素 ，g ,都存在?e?G 的正規(guī)子群 ，使得 g 不是 中的元素。gNG?gN運(yùn)用剩余有限的群，Miller 證明了具有算法上不可解共軛問(wèn)題的群的存在性，這就是 Miller 定理：Miller 定理：存在有限表示且剩余有限的群，其共軛問(wèn)題是算法上不可解的。并且存在快速算法 C 使得輸入一個(gè)有限表示的群 G（G 的字問(wèn)題不可解）后會(huì)輸出有限表現(xiàn)且剩余有限的群 C(G)，C(G)有著不可解的共軛問(wèn)題。Miller 定理是 1993 年 Iris Lee Anshel 和 Michael Anshel 提出的基于不可解的共軛問(wèn)題而構(gòu)造的公鑰加密體制的理論基礎(chǔ)。辮群 在組合群論應(yīng)用于密碼學(xué)中扮演了重要的角色。在 1999 年nB， 和 提出的密鑰交換協(xié)議和 2022 年，Sang Jin Lee 和 Jung Hee Cheon 提出的密鑰交換協(xié)議和加密算法中，他們都利用了辮群的共軛問(wèn)題，這是因?yàn)檗p群的一些重要性質(zhì)可以很好的利用到密碼體制中去。 辮群的定義在前面已經(jīng)提到過(guò)了，但是辮群除了可以用有限生成元表示出來(lái)以外，還有著其獨(dú)特的幾何意義。辮群 中每一個(gè)元素都對(duì)應(yīng)了兩條平行直nB線間的 n 股線，每一股線的兩個(gè)端點(diǎn)開始于上面的平行直線，并中止于下端對(duì)應(yīng)平行直線。下面的兩幅圖對(duì)應(yīng)于 中的生成元 和 。如圖一對(duì)應(yīng)于 ，ni?1i?i?圖二對(duì)應(yīng)于 。1i??+圖 一 1+1n圖 二辮群中的兩個(gè)元素 a，b 相乘在幾何上對(duì)應(yīng)了把兩個(gè)辮群的圖像拼接起來(lái)。10 / 25另外， 中兩個(gè)元素相等從幾何上來(lái)說(shuō)，是指 a，b 兩個(gè)元素對(duì)應(yīng)的圖案能夠nB在三維空間中從一個(gè)圖像連續(xù)的變動(dòng)到另一個(gè)。根據(jù)文獻(xiàn)⑤，⑦，辮群有一些性質(zhì)特別適合密碼學(xué)的要求，用來(lái)構(gòu)造公鑰密碼體制。辮群的元素可以通過(guò)標(biāo)準(zhǔn)形式(canonical form)來(lái)統(tǒng)一表示,即由 p+1個(gè)參量 … 表示，u 是整數(shù)， 代表了一個(gè) n 階置換，該表示是唯12(,u?,)p i?一的。辮群內(nèi)元素的乘法和求逆都存在快速算法，可以用計(jì)算機(jī)編程計(jì)算。并且辮群中有很多的困難問(wèn)題可以作為構(gòu)造密碼體制和密碼交換協(xié)議的基礎(chǔ)，比如說(shuō)辮群的共軛問(wèn)題就是困難問(wèn)題。 第二節(jié)： 密碼體制和密鑰交換協(xié)議 [Wag84]公鑰密碼體制1984 年 和 利用了有限表示群的不可解的字問(wèn)題，構(gòu)造了第一個(gè)以組合群論思想為基礎(chǔ)的公鑰密碼體制。由前面的 NovikovBoone定理可知，存在群滿足不可解的字問(wèn)題，這是[Wag84]公鑰密碼體制成立的基礎(chǔ)。下面是整個(gè)加密算法：取 G 是有限表示的群，有著不可解的字問(wèn)題，G 可以表示為：…12,a?n12,1muu??利用一個(gè)秘密同態(tài)函數(shù) A 可以是大的有限群或者是有限表:hG?示的群，它的字問(wèn)題有著快速的解法。在群 G 中取兩個(gè)字 和 ，使得這兩個(gè)0y1字滿足 。把群 G， 和 公開，作為公鑰，而把同態(tài)函數(shù) 保密，01()hy?0y1 h作為秘密密鑰。加密算法很簡(jiǎn)單，只要將消息 M 寫成二進(jìn)制數(shù)的形式以后，每個(gè) 0bit 位由隨機(jī)選擇的 代替，只要滿足 （意思是指 和 是 G 中同一39。0y39。0mody?39。0y個(gè)元素的不同表現(xiàn)形式） 。同理，1bit 位用 代替， 。這樣的話，39。139。1mod?消息 M 中的每個(gè)比特位都有 G 中的元素來(lái)表示，從密文中任取 G 的一個(gè)元素z，由于 G 有著不可解的字問(wèn)題，即無(wú)法利用算法判斷 和 中哪一個(gè)是10zy?11 / 25單位元素，因此，加密是成功的。解密時(shí)需要運(yùn)用解密密鑰 h，在密文中取元素 z，只要 h(z)=h( ),說(shuō)明 z 代0y表的比特位是 0，反之是 1。因?yàn)樵?A 中字問(wèn)題是可解的，上面的結(jié)果可以判斷，因此消息被解密。對(duì)于以上的利用組合群論所構(gòu)造加密算法的討論：首先它需要找一個(gè)合適的具有不可解的字問(wèn)題的群，要使加密算法適合實(shí)用，必須使群里的元素應(yīng)該在群中有唯一的標(biāo)準(zhǔn)表示，通過(guò)計(jì)算機(jī)很容易進(jìn)行存儲(chǔ)和計(jì)算。即使是這樣，原文中一個(gè)比特位的 0 或者 1 經(jīng)過(guò)轉(zhuǎn)化成密文以后，需要用群的一