【文章內(nèi)容簡(jiǎn)介】 個(gè)元素來(lái)表示。而群中元素在計(jì)算機(jī)的傳輸和存儲(chǔ)的方面，所需要的存儲(chǔ)量遠(yuǎn)遠(yuǎn)大過(guò)比特位。并且在密文處理方面有很多的不方便的地方，比如說(shuō)如何選擇和 Y0 或者 Y1 等價(jià)元素，有沒(méi)有快速算法等等，這些缺點(diǎn)都降低了效率，所以總的來(lái)說(shuō)，這只是一個(gè)不太成熟，不能實(shí)用的方案，但畢竟，它在把組合群論利用到密碼學(xué)中開(kāi)創(chuàng)了新的一步。[Anshel93]密碼體制接下來(lái)由文獻(xiàn)②，在 1993 年， 和 繼續(xù)了利用組合群論中的問(wèn)題提出了另一個(gè)新的加密算法，與前一個(gè)有所不同的是，這次他們所采用的群是有限生成的群，群中元素具有不可解的共軛問(wèn)題，并且群是剩余有限群。在他們所提出的方案中，需要用到前面提到的 Miller 定理作為保障。G 中任意的一個(gè)元素 g，存在從 G 到有限群的一個(gè)同態(tài) Φ，滿足 。()1g??任取 G 中一個(gè)元素 ，存在 G 的正規(guī)子群 ，使得 不是 中的元素，在wWNwWN群 G 中，記 z 為單位元素，由于 G 是剩余有限的，存在一個(gè)有限群 ，可/G考慮同態(tài) H：G→G/ ，因?yàn)?不屬于 ， ， ，由此，由于WNW()1H?()z?和 不是共軛元素，而同態(tài)運(yùn)算保持共軛性質(zhì)不變， 和 z 也不是共()w(z w軛元素。把同態(tài)運(yùn)算 H 保密，并假設(shè)在商群 中，求解共軛問(wèn)題和字問(wèn)題/WGN在算法上是多項(xiàng)式內(nèi)實(shí)現(xiàn)的。在加密問(wèn)題上 Anshel 所采用的方法與前文類(lèi)似，那就是把 1 用任一與 z 共軛的元素代替，把 0 用與 共軛的任一元素代替，用12 / 25這個(gè)方法，可隨機(jī)地把明文中的二進(jìn)制數(shù)字轉(zhuǎn)化成密文中組合群中的元素，而通過(guò)保密的同態(tài)加以解密，最終得到原文。[wag84]和[Ansh 93]從設(shè)計(jì)的思想上來(lái)說(shuō)，是基本上類(lèi)似的，它們都是設(shè)法利用組合論中有特定性質(zhì)的群，即有著不可解的字問(wèn)題或是共軛問(wèn)題，以群中兩類(lèi)不同的元素分別代表 0 和 1 兩個(gè)數(shù)字，同時(shí)均將一個(gè)同態(tài)映射做密鑰保存，只要知道了所選用的群和兩個(gè)代表 0 和 1 的群元素就可以對(duì)消息進(jìn)行加密，作為密鑰的同態(tài)運(yùn)算所對(duì)應(yīng)的群的字問(wèn)題和共軛問(wèn)題則是可解的。它們的差別是[wag84]所選用的群是以字問(wèn)題做為困難問(wèn)題，而[Ansh93]是把共軛問(wèn)題做為困難問(wèn)題，兩者的區(qū)別是群選擇的不同。[AnshelAnshelGoldfeld]密鑰交換協(xié)議1999 年的時(shí)候，不同于以上的幾個(gè)公鑰密碼系統(tǒng)，在組合群論的基礎(chǔ)上，M Anshel 和 D Goldfeld 提出了一個(gè)新的密鑰交換協(xié)議（見(jiàn) ③和④） ，該協(xié)議中所采用的群是辮群，具有不可解的共軛問(wèn)題，但是辮群的字問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)解決。在協(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)。這些字均從群 G={S|D}得到，其中 S 是生成元，D 是定義關(guān)系。Alice 和 Bob 之間的密鑰由它的共同的行為產(chǎn)生，Alice 和 Bob 同時(shí)執(zhí)行以下的步驟，一起產(chǎn)生秘密密鑰：Alice 首先進(jìn)行如下運(yùn)算，Alice 選擇一個(gè)群 G 中的由 a(1)，a(2)，…，a(n)生成的秘密的字 X，對(duì)每一個(gè) b(i)進(jìn)行共軛運(yùn)算，產(chǎn)生 m 個(gè)新字 c(1)，c(2)，…，c (m)，c (i)=X b(i)X1。Alice 對(duì)每一個(gè) 進(jìn)行改寫(xiě)，寫(xiě)成 B(i)的形式， B(i)和 是 G 中同一c(i) c(i)個(gè)元素的不同表示，i=1 ，…，m。B(i)能夠完全掩蓋住 中有關(guān) X 的秘密信(i)息。由于 B(i)和 b(i)是關(guān)于 X 的共軛元素，但不能從 B(i)中推斷出 X 是什么13 / 25（G 有著不可解的共軛問(wèn)題） ，X 是不可知的。Alice 通過(guò)公開(kāi)的渠道把 B(1)，B(2)，…，B(m) 傳送給 Bob。在 Alice 進(jìn)行計(jì)算的同時(shí)，Bob 進(jìn)行類(lèi)似的計(jì)算。Bob 從 b(1)，b(2) ，…，b(m) 生成的 G 的子群中，選擇一個(gè)秘密的元素Y，用每個(gè) a(i)進(jìn)行共軛等。產(chǎn)生 d(1)，d(2) ……d(n)，d(i)=Ya(i)Y 1。對(duì)每個(gè) d(i)進(jìn)行改寫(xiě)，寫(xiě)成 A(i)的形式，使得 A(i)和 d(i)表示相同的元素。Bob 把 A(1)，A(2), …,A(n)傳送給 Alice。第三步，Alice 和 Bob 可根據(jù)所得的結(jié)果分別計(jì)算出換位子（ X，Y）=XYX1Y1。因?yàn)椋?Alice 可以從 V=X（YXY 1） 1=Xx（A(1) ） ，…A （n）) 1 中計(jì)算，如果 X=x（a(1) ，…a(n)） 。并且 Bob 也可以計(jì)算換位子 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)生成，僅為 Alice 所知，而 A(1)，A(2), …,A(n)是 a(1)，a(2)，…，a(n)關(guān)于 Y 的共軛元素，通過(guò)類(lèi)似的計(jì)算， Alice 可以知道 YXY1，Bob 也是可以由秘密的 Y 以及 Alice 傳送給它的 B(1)，B(2)，… ，B(m)來(lái)得到 XYX1，但是對(duì)于 Alice 所掌握的字 X 一無(wú)所知，當(dāng) Alice 和 Bob 經(jīng)過(guò)計(jì)算出 V 和 W 以后，V 和 W 是同一個(gè)字的不同表現(xiàn)形式，從字 V 和 W 得到 Alice 和 Bob 的共同的密鑰有兩個(gè)方法，第一個(gè)是辮群 G 中的每個(gè)元素都有且僅有一種唯一的特殊表現(xiàn)形式，稱(chēng)作經(jīng)典形式，那么把 V 和 W 都寫(xiě)成經(jīng)典形式之后，這時(shí)它們的標(biāo)準(zhǔn)形式是相同的，然后可以定義從辮群的標(biāo)準(zhǔn)形式到二進(jìn)制數(shù)的單向函數(shù) H，從而使密鑰 K=H（V）=H （Ｗ） ，第二個(gè)方法是把 G 作為群作用在某個(gè)集合 S上，并且滿足 E（S）=SG 1（G 2（S ） ）= （G 1G2） （S ） ， （G 1 、G 2 屬于 G，E 是G 的單位元） ，且 G 內(nèi)不同的字作用到 S 上的元素 S 所得的值也是不同的。在這種條件下，密鑰 K=V（S）=W（S ）也同樣可以得到。對(duì)[AnshelAnshelGoldfeld]密鑰交換協(xié)議的分析：首先我們不知道，上述的密鑰交換協(xié)議的安全性是否以辮群共軛問(wèn)題的難解程度為基礎(chǔ)的，但是，實(shí)際上已知 XYX1 和 Y 求解 X 的問(wèn)題和已知XB（1 ）X 1，XB （2）X 1…，XB（M）X 1 和 B（ 1） ， B（2） ，…B（M ）的值來(lái)求解 X 的困難程度是不一樣的，顯然后一個(gè)問(wèn)題比前面的問(wèn)題要容易的多，14 / 25后一個(gè)問(wèn)題所面臨的困難問(wèn)題是不同于標(biāo)準(zhǔn)形式的共軛問(wèn)題，我們可以把它稱(chēng)之為新的共軛問(wèn)題（MSCSP） ，應(yīng)該說(shuō)這個(gè)也是從算法上來(lái)說(shuō)不可解的。另一點(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 對(duì) X，Y 進(jìn)行改寫(xiě)，并使得從 XB（1）X 1，…，XB（M）X 1 或 YA（1）Y 1，…，YA（N ）Y 1 中不能得出 X，Y 的值的時(shí)候，通過(guò)改寫(xiě)，即把上述這些辮群里的元素寫(xiě)成標(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 中的秘密信息必須完全被改寫(xiě)掉。[KoLeeCheon]密鑰交換協(xié)議和公鑰密碼體制從上述的密鑰交換協(xié)議可以看出，上述的協(xié)議的主要思想是利用組合群論中的一般理論，關(guān)于換位子的思想適用于任何一個(gè)群，只是在具體的實(shí)現(xiàn)方法上，才使用了辮群，因?yàn)檗p群在實(shí)現(xiàn)過(guò)程中，有一些較好的優(yōu)點(diǎn)。比如有唯一的標(biāo)準(zhǔn)形式，并且它的字問(wèn)題有著快速算法，而共軛問(wèn)題是困難問(wèn)題等等。應(yīng)該可以看出，任何具有類(lèi)似性質(zhì)的群都可以做為構(gòu)造[AnshelAnshelGoldfeld]密鑰交換協(xié)議的群。下面所提到的[KoLeeCheon]密鑰交換協(xié)議則是更立足于辮群本身的性質(zhì)（文獻(xiàn)⑦） ，因此在討論密鑰交換協(xié)議的時(shí)候，對(duì)于密鑰交換協(xié)議的安全性分析將更加成熟一點(diǎn)，并且能夠相對(duì)比較實(shí)用。韓國(guó)學(xué)者 Hyoung Ko，Sang Jin Lee 和 Jung Hee Cheon 提出，在辮群中有一些問(wèn)題屬于困難問(wèn)題，其中能夠適用于構(gòu)造密鑰體制的有以下一些：假設(shè) 是由 ，…， 生成， 由 ，…， 生成，mn，nB12,?1n?mB12,?1m?那么，辮群 可以看成是 的子群，那么有以下幾個(gè)問(wèn)題是困難問(wèn)題：m普通的尋找共軛元素問(wèn)題（GCSP）元素（X，Y）∈ ，并且 Y=BXB1，其中，B∈ ，mnnmB?n問(wèn)題：尋找 A∈ 使行 Y=AXA1 成立，15 / 25共軛元素分解問(wèn)題（QCDP）（X，Y）∈ ，滿足 Y=BXB1，B∈ ，mnnmB?m問(wèn)題：尋找 ， ∈ ，滿足 。39。A39。 39。39。YAX?尋找 P 次根問(wèn)題，（X,Y）∈ ，滿足 Y=XP，X