【正文】 計它的目的是要完成一項任務(wù)。在實際的密碼世界中密鑰交換其實是很重要的一個環(huán)節(jié)。但是如何使得密鑰到達(dá)接收者和發(fā)送者手里是件很復(fù)雜的事情。新的密鑰交換協(xié)議有利用組合群論中的辮群 構(gòu)造的兩nB個協(xié)議，AnshelAnshelGoldfeld 協(xié)議和 KoLeeCheon 協(xié)議。電子商務(wù)是以數(shù)字化的電子方式，以網(wǎng)絡(luò)為媒體進(jìn)行的商業(yè)數(shù)據(jù)交換或其他商業(yè)活動。電子支付是指交易的各方是通過電子手段，比如說銀行的電子存款系統(tǒng)和電子清算系統(tǒng)來記錄和轉(zhuǎn)移資金的方式。目前INTERNET 上的電子支付系統(tǒng)主要有四種：信用卡、IC 卡、電子現(xiàn)金（eCash）和電子支票（eCheck） 。作為電子支付系統(tǒng)的不同代表，電子現(xiàn)金和電子支票雖然有一定的共性，但在安全性要求和性質(zhì)方面有著各自獨(dú)特的特點(diǎn)。在電子支票實現(xiàn)的過程中，它的安全性問題是，如何保證銀行、用戶、商場對電子支票進(jìn)行簽名的有效性。所以在交易過程中將會涉及到數(shù)7 / 25字多簽名。電子現(xiàn)金是一種以數(shù)據(jù)形式流行的貨幣，因此和支票相比，電子現(xiàn)金更強(qiáng)調(diào)滿足隱私性和可分割性，另外，雖然要保證用戶的隱私權(quán)，電子現(xiàn)金出于安全性的考慮，還需要滿足電子現(xiàn)金的不可偽造性和不可重用性。關(guān)于電子現(xiàn)金，現(xiàn)在最主要討論的是它的可分性的實現(xiàn)。由于組合群論中的數(shù)學(xué)工具和以前數(shù)論中的內(nèi)容截然不同，有必要對組合群論中的一些定義和定理加以說明，從而可運(yùn)用到密碼學(xué)中去，得到不同的加密算法。群 G 稱作是可以有限表示的（finitely represented） ，如果在 G 中有有限個元素 ， ，…， 滿足在群 G 中， ， ，…， ，其中 e 是單位元，1r2kr1re?2kr?那么 ， ，…， 稱為 G 的生成元 … 的一組定義關(guān)系， 。?12,w?,k8 / 25可以有限表示的群 G 可表示為：G= … ； …21,g,n12,rk辮群 是一種有限表示的群， 的生成元是 ， ，…， ，它的生nBnB?1n?成關(guān)系滿足： ， 時； 當(dāng)1ijije???ij??當(dāng) 1ijijije??時。121。字問題(word problem)：是否存在一個算法來判斷群 G 中的元素是不是單位元。如果不存在這樣的程序，就稱這個問題是算法上不可解的(algorithmically unsolvable) 。NovikovBoone 定理：存在有限表示的群 G 有著算法上不可解的字問題，并且存在有效的算法 B，如果輸入有限表示的一個系統(tǒng) T，且該系統(tǒng)有著不可解的字問題，通過算法 B 將會輸出有限表示的群 B(T)，使得 B(T)有著算法上不可解的字問題。共軛問題(conjugacy problem)：是否存在算法來判斷群 G 中給定的任意兩個元素是共軛元素。1ywx??關(guān)于組合群論中是否存在群有著算法上不可解的共軛問題，同樣可由一個9 / 25定理加以保證。一個群 G 被稱為是剩余有限的(residually finite)，如果給定了群中任意一個元素 ，g ,都存在?e?G 的正規(guī)子群 ，使得 g 不是 中的元素。并且存在快速算法 C 使得輸入一個有限表示的群 G（G 的字問題不可解）后會輸出有限表現(xiàn)且剩余有限的群 C(G)，C(G)有著不可解的共軛問題。辮群 在組合群論應(yīng)用于密碼學(xué)中扮演了重要的角色。 辮群的定義在前面已經(jīng)提到過了，但是辮群除了可以用有限生成元表示出來以外，還有著其獨(dú)特的幾何意義。下面的兩幅圖對應(yīng)于 中的生成元 和 。1i??+圖 一 1+1n圖 二辮群中的兩個元素 a，b 相乘在幾何上對應(yīng)了把兩個辮群的圖像拼接起來。根據(jù)文獻(xiàn)⑤，⑦，辮群有一些性質(zhì)特別適合密碼學(xué)的要求，用來構(gòu)造公鑰密碼體制。辮群內(nèi)元素的乘法和求逆都存在快速算法，可以用計算機(jī)編程計算。 第二節(jié)： 密碼體制和密鑰交換協(xié)議 [Wag84]公鑰密碼體制1984 年 和 利用了有限表示群的不可解的字問題，構(gòu)造了第一個以組合群論思想為基礎(chǔ)的公鑰密碼體制。下面是整個加密算法：取 G 是有限表示的群，有著不可解的字問題，G 可以表示為：…12,a?n12,1muu??利用一個秘密同態(tài)函數(shù) A 可以是大的有限群或者是有限表:hG?示的群，它的字問題有著快速的解法。把群 G， 和 公開，作為公鑰，而把同態(tài)函數(shù) 保密，01()hy?0y1 h作為秘密密鑰。0y39。0y個元素的不同表現(xiàn)形式） 。這樣的話，39。1mod?消息 M 中的每個比特位都有 G 中的元素來表示，從密文中任取 G 的一個元素z，由于 G 有著不可解的字問題，即無法利用算法判斷 和 中哪一個是10zy?11 / 25單位元素，因此，加密是成功的。因為在 A 中字問題是可解的，上面的結(jié)果可以判斷，因此消息被解密。即使是這樣，原文中一個比特位的 0 或者 1 經(jīng)過轉(zhuǎn)化成密文以后，需要用群的一個元素來表示。并且在密文處理方面有很多的不方便的地方，比如說如何選擇和 Y0 或者 Y1 等價元素，有沒有快速算法等等，這些缺點(diǎn)都降低了效率，所以總的來說，這只是一個不太成熟，不能實用的方案，但畢竟，它在把組合群論利用到密碼學(xué)中開創(chuàng)了新的一步。在他們所提出的方案中，需要用到前面提到的 Miller 定理作為保障。()1g??任取 G 中一個元素 ，存在 G 的正規(guī)子群 ，使得 不是 中的元素，在wWNwWN群 G 中，記 z 為單位元素，由于 G 是剩余有限的，存在一個有限群 ，可/G考慮同態(tài) H：G→G/ ，因為 不屬于 ， ， ，由此，由于WNW()1H?()z?和 不是共軛元素，而同態(tài)運(yùn)算保持共軛性質(zhì)不變， 和 z 也不是共()w(z w軛元素。在加密問題上 Anshel 所采用的方法與前文類似，那就是把 1 用任一與 z 共軛的元素代替，把 0 用與 共軛的任一元素代替，用12 / 25這個方法，可隨機(jī)地把明文中的二進(jìn)制數(shù)字轉(zhuǎn)化成密文中組合群中的元素，而通過保密的同態(tài)加以解密，最終得到原文。它們的差別是[wag84]所選用的群是以字問題做為困難問題，而[Ansh93]是把共軛問題做為困難問題，兩者的區(qū)別是群選擇的不同。在協(xié)議中，[Anshel99]利用換位子的思想，XYX 1Y1，其中 X，Y 均為辨群 中的元素，其中 XYX1Y1 可以看成是 Y 的共軛元素和 Y1nB相乘得到，或者可以看成是 X 和 X1 的共軛元素相乘得到的，具體的密鑰交換步驟如下：兩方 Alice 和 Bob 分別公布字 a(1)，a(2)，…，a(n)；b(1)，b(2)，…，b(m)。Alice 和 Bob 之間的密鑰由它的共同的行為產(chǎn)生，Alice 和 Bob 同時執(zhí)行以下的步驟，一起產(chǎn)生秘密密鑰：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(i)X1。B(i)能夠完全掩蓋住 中有關(guān) X 的秘密信(i)息。Alice 通過公開的渠道把 B(1)，B(2)，…，B(m) 傳送給 Bob。Bob 從 b(1)，b(2) ，…，b(m) 生成的 G 的子群中，選擇一個秘密的元素Y，用每個 a(i)進(jìn)行共軛等。對每個 d(i)進(jìn)行改寫，寫成 A(i)的形式，使得 A(i)和 d(i)表示相同的元素。第三步，Alice 和 Bob 可根據(jù)所得的結(jié)果分別計算出換位子（ X，Y）=XYX1Y1。并且 Bob 也可以計算換位子 W=（XYX 1）Y 1=y（B(1)，B(2) ，…，B(m) ）Y 1，如果 Y=y(b(1),……,b(n))。在這種條件下，密鑰 K=V（S）=W（S ）也同樣可以得到。另一點(diǎn)是[AnshelAnshelGoldfeld]密鑰交換協(xié)議所利用的辮群中密鑰的共軛運(yùn)算的同態(tài)性質(zhì)；即 XA（1）X 1XA（2）X 1=XA（1）A（2）X 1，以及（XYX 1） 1=XY1X1 但是在 Alice 和 Bob 對 X，Y 進(jìn)行改寫，并使得從 XB（1）X 1，…，XB（M）X 1 或 YA（1）Y 1，…，YA（N ）Y 1 中不能得出 X，Y 的值的時候，通過改寫，即把上述這些辮群里的元素寫成標(biāo)準(zhǔn)形式時，并不能夠保證所有的標(biāo)準(zhǔn)形式能完全掩蓋住秘密信息。[KoLeeCheon]密鑰交換協(xié)議和公鑰密碼體制從上述的密鑰交換協(xié)議可以看出，上述的協(xié)議的主要思想是利用組合群論中的一般理論，關(guān)于換位子的思想適用于任何一個群，只是在具體的實現(xiàn)方法上，才使用了辮群，因為辮群在實現(xiàn)過程中，有一些較好的優(yōu)點(diǎn)。應(yīng)該可以看出，任何具有類似性質(zhì)的群都可以做為構(gòu)造[AnshelAnshelGoldfeld]密鑰交換協(xié)議的群。韓國學(xué)者 Hyoung Ko，Sang Jin Lee 和 Jung Hee Cheon 提出，在辮群中有一些問題屬于困難問題，其中能夠適用于構(gòu)造密鑰體制的有以下一些：假設(shè) 是由 ，…， 生成， 由 ，…， 生成，mn，nB12,?1n?mB12,?1m?那么，辮群 可以看成是 的子群，那么有以下幾個問題是困難問題：m普通的尋找共軛元素問題（GCSP）元素（X，Y）∈ ，并且 Y=BXB1，其中，B∈ ，mnnmB?n問題：尋找 A∈ 使行 Y=AXA1 成立，15 / 25共軛元素分解問題（QCDP）（X，Y