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