群论应用举例

组合群论在密码学和电子商务的安全性中的应用目录第一章密码学和电子商务的安全性………………1第一节密码学概述………………1第二节电子支付系统的安全性…………………4第二章组合群论和密码学…………4第一节基础知识和背景…………4第二节密码体制和密钥交换协议………………7TOC\o"1-5"\h\z\o"CurrentDocument"[Wag84]公钥密码体制 72.2.2[Anshel93]密码体制 9\o"CurrentDocument"2.2.3[Anshel-Anshel-Goldfeld]密钥交换协议 9\o"CurrentDocument"2.2.4[Ko-Lee-Cheon]密钥交换协议和密码体制 11第三章组合群论在电子支票的多签名体制中的应用……………14第一节三方密钥交换协议……14第二节基于辫群的多签名体制方案…………15多签名介绍……………163.2.2基于单向环同态的多签名体制 173.2.3基于辫群的多签名体制 18第一章密码学和电子商务的安全性第一节密码学概述信息安全是密码学的基本要求，为了要达到这一点，密码学始终涉及两个方面的斗争。其中一方（发送者）是设法对消息进行加密，使得只能是具有特殊权利的人（接受者）才能够接受和阅读信息。而另一方则是尽力设法截获信息，破译密文，或者用修改以后的假信息欺骗接收者。在本文中，我们主要讨论的是前一方，即考虑用何种方法能够对消息进行安全、有效且快捷的加密，保证消息的传送。待加密的消息被称作明文（plaintext），用某种方法伪装消息并隐藏它的内容的方法称作加密（encryption），被加密以后的消息称为密文，而把密文转变成明文的过程称为解密。加密体制中的加密运算是由一个算法类组成，这些算法类的不同运算可用不同的参数表示，不同的参数分别代表不同的算法，被称作密钥，密钥空间是所有密钥的集合。密码体制一般是指密钥空间与相应的加密运算结构，同时还包括了明文和密文的结构特征。在密码体制的设计和评价中要考虑到以下一些基本原则：（1） 不可破原则，指该密码体制在理论上或实际上是不可破解的。（2） 部分信息丢失不会影响整个系统的安全性。即硬件设备、加密算法或全部密文与部分明文这些信息的丢失不会危及整个系统的安全。（3） 与计算机、通信系统匹配原则。要求密码系统不是独立存在的，而可以在计算机或通信系统中使用。密码体制发展到现在，已经有了很多种不同的类型。但是从密码体制所使用算法的分类上说，可以分为两种。一种是利用了对称算法，又称作传统密码算法；另一种则是利用了公开密钥算法。对称算法是指加密密钥和解密密钥能够互相推算出来，公开了一个也就相当于公开另一方。因此对称算法的密钥只能由发送者和接收者两方知道，他们必须事先商定好密钥，这一点就涉及了密钥交换协议。公开密钥算法是指公开了加密算法E以后不会泄露解密算法D，因此和KK对称算法相比，任何人都可以通过公开渠道(网络或密钥管理中心)已知他人的加密密钥，把明文加密以后传送给接收者，而只有拥有解密密钥D的人才能够K对密文解密。这在密钥管理和消息的传送方面更具有优势。另外，公开密钥算法还可以运用在数字签名中。在目前应用于实际生活比较广泛的公钥加密算法包含有RSA密码体制和椭圆曲线密码体制。RSA密码体制：1979年，ShamirRivest和Adelman提出了第一个也是应用最广的公钥密码体制，即RSA体制。经过20多年的密码分析和攻击，迄今为止，RSA被证明仍是安全的。设n=pq,p和q是两个大素数，a和b是两个整数，定义密钥空间为｛(n,p,q,a,b):n=pq,ab三1(mod申(n))｝。把n，b作为公开密钥，而p，q，a，申(n)，作为秘密密钥。整个加密算法就是y=E(x)=xbmodn，而解密算法K是D(y)=yamodn，由Euler定理知道，x=D(y)成立，上述解密的方法正确。KK由于RSA加密算法是指数运算，因此当密钥越大时，计算速度越慢。RSA算法比通常的DES算法慢了1500倍。并且RSA的计算量很大，为了要达到较高的安全程度，RSA的密钥位数比其它的密码体制大的多，现在一般需要1024位的密钥。所以一般对速度要求较高的数字签名或智能卡中的身份验证不太使用RSA密码体制，而采用其它较快的算法。椭圆曲线密码系统就是其中的一种。椭圆曲线密码系统：椭圆曲线密码体制和RSA体制比较起来，所需要的密钥量小，安全程度高，比如RSA密码体制需要1024-bit的密钥才能达到的安全程度，利用椭圆曲线只需要160比特位的密钥就能够保证同样的安全(文献⑨)，密钥长度的减少同时带来了计算速度的提高。即使是在剩余类环Z运用离散对数而构造的加密P系统的安全程度也要低于椭圆曲线，因此椭圆曲线系统不愧为一个性质较好的密码系统。椭圆曲线第一次运用于公钥密码算法是在1985年NealKoblitz和V.S.Miller提出来的。他们并没有提出新的算法，只是把椭圆曲线运用到已存在的公钥密码算法中，比如说ElGamal加密算法。利用ElGamal思想构造的椭圆曲线密码体制如下显示：首先是产生密钥阶段。Bob从Z中随机选取充分大的整数k，随后计算nB出椭圆曲线上的点P=kQ(Q是椭圆曲线上的适当的一点)，将k保密，作为秘BB密密钥，并将P公开，作为公钥。加密方法如下：如果Alice想把消息M(同样是椭圆曲线上的一点)发送给Bob，就从Z中随机选择整数lgZ后，计算出S=IQ和S=M+IP的值，加nn12密以后的信息就是椭圆曲线上两点(S,S)。12解密：Bob收到加密信息(S,S)后，通过密钥k就可以计算M=S-kS12B2B1得到消息M。纵观上面提出的两个公钥密码体制，再加上其它的密码系统，在加密的时候都采用了单向函数的思想。单向函数是指函数f满足从x计算f(x)容易，但从f(x)计算x有可能不可行。单向函数的构造依赖于计算复杂度理论，即利用一些困难问题。上述两个系统的安全性都依赖于一些数论中的基本困难问题。比如说RSA体制利用了把大整数n分解为两个大素数的难度，而椭圆曲线是利用了求解离散对数问题的困难程度，(即根据P=kQ和Q求解Z中整数k)。这些BnB密码体制都是很成功的，在实际中也有了进一步的应用。对于本文来说，我们的主要目的是把组合群论的思想引进到密码学中，所以利用了组合群论中的一些困难问题，如字问题，共轭问题等等，由此构造出新的密码体制。协议(protocol)是指一系列的步骤，它包括两方或者多方，设计它的目的是要完成一项任务。密钥交换协议(keyexchangeprotoco1)是指两人或多人之间通过一个协议取得密钥并用于进一步的加密算法中的方法。在实际的密码世界中密钥交换其实是很重要的一个环节。比如说利用对称加密算法，如果双方没有约定好密钥，就必须再进行密钥交换。但是如何使得密钥到达接收者和发送者手里是件很复杂的事情。最早利用公钥密码思想提出的密钥交换协议有Difffie-Hellman算法。新的密钥交换协议有利用组合群论中的辫群B构造的两个n协议，Anshel-Anshel-Goldfeld协议和Ko-Lee-Cheon协议。第二节电子支付系统的安全性电子商务作为新兴事务，已经随着计算机和网络技术的成熟得到了飞速发展，而且使得商家的整体经营方式都有了变化。电子商务是以数字化的电子方式，以网络为媒体进行的商业数据交换或其他商业活动。电子商务的一个重要组成部分就是电子支付系统。电子支付是指交易的各方是通过电子手段，比如说银行的电子存款系统和电子清算系统来记录和转移资金的方式。一个安全、可靠的电子支付系统是电子商务的交易活动能够正常进行的保证。目前INTERNET上的电子支付系统主要有四种:信用卡、IC卡、电子现金(e-Cash)和电子支票(e-Check)。一般来说，电子支付系统必须满足以下的安全性要求，包括有消息的保密性、能够确认双方都具有合法的交易身份的能力、保证交易完毕以后的信息是无法修改的和交易以后各方对业务的不可否认性。作为电子支付系统的不同代表，电子现金和电子支票虽然有一定的共性，但在安全性要求和性质方面有着各自独特的特点。电子支票和纸张支票转移支付的原理类似，是利用数字传递将钱款从一个账户转移到另一个账户的电子付款方式。在电子支票实现的过程中，它的安全性问题是，如何保证银行、用户、商场对电子支票进行签名的有效性。由于转账在银行、用户和商场三方进行，在每一次交易完成以后都必须对消息签名，用来保证交易信息的真实、完整和不可否认。所以在交易过程中将会涉及到数字多签名。在本文中，我们最后讨论了一种利用辫群构造的多签名体制，可以把上述多签名运用到电子支票转账系统中去。电子现金是一种以数据形式流行的货币，因此和支票相比，电子现金更强调满足隐私性和可分割性，另外，虽然要保证用户的隐私权，电子现金出于安全性的考虑，还需要满足电子现金的不可伪造性和不可重用性。如果同一份电子现金被使用两次，使用者的身份就可以被发现。关于电子现金，现在最主要讨论的是它的可分性的实现。第二章组合群论和密码学第一节基础知识和背景自从1984年N.R.Wager和M.R.Magyarik在①中提出了第一个用组合群论的理论构造公钥密码体制的方法以来，在密码学家们的共同努力下，利用组合群论的理论已经提出多个公钥密码体制和密钥交换协议。由于组合群论中的数学工具和以前数论中的内容截然不同，有必要对组合群论中的一些定义和定理加以说明，从而可运用到密码学中去，得到不同的加密算法。群G称作是有限生成的(第二章组合群论和密码学第一节基础知识和背景自从1984年N.R.Wager和M.R.Magyarik在①中提出了第一个用组合群论的理论构造公钥密码体制的方法以来，在密码学家们的共同努力下，利用组合群论的理论已经提出多个公钥密码体制和密钥交换协议。由于组合群论中的数学工具和以前数论中的内容截然不同，有必要对组合群论中的一些定义和定理加以说明，从而可运用到密码学中去，得到不同的加密算法。群G称作是有限生成的(finitelygenerated),如果G存在有限个生成元gg，…,g，满足G中任意一个元素(又称为字)都可以表示成生成元和它们1,2n的逆的有限乘积。群G称作是可以有限表示的(finitelyrepresented)，如果在G中有有限个元素r，r，…，r满足在群G中，r=e，r=e,…，r=e，其中e是单位元，12k12k那么r，r，…，r称为G的生成元g,g，…,g的一组定义关系，。12k12n换一种角度，如果把群G看成是n个元素X={a,a,…,a}生成的自由群12nF(X)的商群，即存在F(X)的正规子群N，使得G=F(X)，N成立，那么G是可以有限表示的意思是：如果r，r，…r对应F(X)中的元素w，w…w，那么12k12k{w,w，…,w}是F(X)的正规子群N的生成元。12k可以有限表示的群G可表示为：G=gg,…,g'12 n［〔，…,rk辫群B是一种有限表示的群，B的生成兀是b，b，n n 1 2…，b，它的生成n-1关系满足：bbb-Q-1=e，当li-j>2时；bbbb-Q-Q-1=e当i-j=1时。ijij ijijij因此，辫群B可以表示为：B,bn n■ 1 2,bn-1bbb=bbb;当i一j=1. .. .. . "Iiji jZjbb=bb;当li-j>2ijji组合群论中有些基本问题相对于某个特定的群是困难问题，可以作为构造公钥密码体制的基础，例如第一个公钥密码体制［Wag84］就是根据不可解的字问题所构造的，而随后的［Anshel93］等主要运用了组合群论中的共轭问题。字问题(wordproblem):是否存在一个算法来判断群G中的元素是不是单位元。一个问题是算法上可解的(algorithmicallysolvable)是指存在一组计算机程序，通过计算，对该问题的结果是“是”或“否”做出明确的回答。如果不存在这样的程序，就称这个问题是算法上不可解的(algorithmicallyunsolvable)。关于字问题对于某些群是否是算法上不可解的，Novikov-Boone定理(见②)对此做出了肯定的回答，定理中利用了有限表示的群，这也是用字问题作为困难问题构造加密算法的基础。Novikov-Boone定理：存在有限表示的群G有着算法上不可解的字问题，并且存在有效的算法B，如果输入有限表示的一个系统T，且该系统有着不可解的字问题，通过算法B将会输出有限表示的群B(T)，使得B(T)有着算法上不可解的字问题。第一次提出利用组合群论的思想来构造的［Wag84］密码体制就利用了Novikov-Boone定理。共轭问题(conjugacyproblem):是否存在算法来判断群G中给定的任意两个元素是共轭元素。所谓两个元素x,y共轭是指，存在G中元素w,使得y二w-1xw成立。关于组合群论中是否存在群有着算法上不可解的共轭问题，同样可由一个定理加以保证。在该定理中，所涉及的群是剩余有限群。一个群G被称为是剩余有限的(residuallyfinite)，如果给定了群中任意一个元素geG，g丰e,都存在G的正规子群NVG,使得g不是N中的元素。g g运用剩余有限的群，Miller证明了具有算法上不可解共轭问题的群的存在性，这就是Miller定理：Miller定理:存在有限表示且剩余有限的群，其共轭问题是算法上不可解的。并且存在快速算法C使得输入一个有限表示的群G(G的字问题不可解)后会

输出有限表现且剩余有限的群C(G),C(G)有着不可解的共轭问题。Miller定理是1993年IrisLeeAnshel和MichaelAnshel提出的基于不可解的共轭问题而构造的公钥加密体制的理论基础。辫群B在组合群论应用于密码学中扮演了重要的角色。在1999年I.Anshel,nM.Anshel和D.Goldfeld提出的密钥交换协议和2000年Hyoung.Ko,SangJinLee和JungHeeCheon提出的密钥交换协议和加密算法中，他们都利用了辫群的共轭问题,这是因为辫群的一些重要性质可以很好的利用到密码体制中去。辫群的定义在前面已经提到过了,但是辫群除了可以用有限生成元表示出来以外,还有着其独特的几何意义。辫群B中每一个元素都对应了两条平行直n线间的n股线,每一股线的两个端点开始于上面的平行直线,并中止于下端对应平行直线。下面的两幅图对应于B中的生成元Q和◎-1。如图一对应于Q，图niii二对应于◎-1。i辫群中的两个元素a,b相乘在几何上对应了把两个辫群的图像拼接起来。另外，B中两个元素相等从几何上来说，是指a，b两个元素对应的图案能够在n三维空间中从一个图像连续的变动到另一个。根据文献⑤，⑦，辫群有一些性质特别适合密码学的要求，用来构造公钥密码体制。辫群的元素可以通过标准形式(canonicalform)来统一表示，即由p+1个参量(u,兀,兀,…,兀)表示，u是整数，兀代表了一个n阶置换，该表示是唯一的。12pi辫群内元素的乘法和求逆都存在快速算法，可以用计算机编程计算。并且辫群中有很多的困难问题可以作为构造密码体制和密码交换协议的基础，比如说辫群的共轭问题就是困难问题。

第二节：密码体制和密钥交换协议2.2.1［Wag84］公钥密码体制1984年N.R.Waner和M.R.Magyarik利用了有限表示群的不可解的字问题，构造了第一个以组合群论思想为基础的公钥密码体制。由前面的Novikov-Boone定理可知，存在群满足不可解的字问题，这是［Wag84］公钥密码体制成立的基础。下面是整个加密算法：G=；取G是有限表示的群，有着不可解的字问题，G=；u—1,u—1,12利用一个秘密同态函数 h:GTAA可以是大的有限群或者是有限表示的群，它的字问题有着快速的解法。在群G中取两个字y和y，使得这两个01字满足h(y)丰h(y)。把群G，y和y公开，作为公钥，而把同态函数h保密，0101作为秘密密钥。加密算法很简单，只要将消息M写成二进制数的形式以后，每个0-bit位由随机选择的y'代替，只要满足y'三ymodG(意思是指y'和y是G中同一个元00000素的不同表现形式)。同理，1-bit位用y'代替，y'三ymodG。这样的话，消息111M中的每个比特位都有G中的元素来表示，从密文中任取G的一个元素z,由于G有着不可解的字问题，即无法利用算法判断zy-1和zy-1中哪一个是单位元01素，因此，加密是成功的。解密时需要运用解密密钥h，在密文中取元素z，只要h(z)=h(y)，说明z代0表的比特位是0，反之是1。因为在A中字问题是可解的，上面的结果可以判断,因此消息被解密。对于以上的利用组合群论所构造加密算法的讨论：首先它需要找一个合适的具有不可解的字问题的群，要使加密算法适合实用，必须使群里的元素应该在群中有唯一的标准表示，通过计算机很容易进行存储和计算。即使是这样，原文中一个比特位的0或者1经过转化成密文以后，需要用群的一个元素来表示。而群中元素在计算机的传输和存储的方面，所需要的存储量远远大过比特位。并且在密文处理方面有很多的不方便的地方，比如说如何选择和Y0或者Y］等价元素，有没有快速算法等等，这些缺点都降低了效率，所以总的来说，这只是一个不太成熟，不能实用的方案，但毕竟，它在把组合群论利用到密码学中开创了新的一步。2・2・2［Anshel93］密码体制接下来由文献②，在1993年，M.Anshel和I.Anshel继续了利用组合群论中的问题提出了另一个新的加密算法，与前一个有所不同的是，这次他们所采用的群是有限生成的群，群中元素具有不可解的共轭问题，并且群是剩余有限群。在他们所提出的方案中，需要用到前面提到的Miller定理作为保障。G中任意的一个元素g,存在从G到有限群的一个同态①，满足①(g)丰1。任取G中一个元素w，存在G的正规子群N，使得w不是N中的元素，在群WWG中，记z为单位元素，由于G是剩余有限的，存在一个有限群G/N，可考虑W同态H：G~G/N，因为w不属于N，H(w)丰1，H(z)=1，由此，由于H(w)WW和H(z)不是共轭元素，而同态运算保持共轭性质不变，w和z也不是共轭元素。把同态运算H保密，并假设在商群G/N中，求解共轭问题和字问题在算法上W是多项式内实现的。在加密问题上Anshel所采用的方法与前文类似，那就是把1用任一与z共轭的元素代替，把0用与w共轭的任一元素代替，用这个方法，可随机地把明文中的二进制数字转化成密文中组合群中的元素，而通过保密的同态加以解密，最终得到原文。［wag84］和［Ansh93］从设计的思想上来说，是基本上类似的，它们都是设法利用组合论中有特定性质的群，即有着不可解的字问题或是共轭问题，以群中两类不同的元素分别代表0和1两个数字，同时均将一个同态映射做密钥保存，只要知道了所选用的群和两个代表0和1的群元素就可以对消息进行加密，作为密钥的同态运算所对应的群的字问题和共轭问题则是可解的。它们的差别是［wag84］所选用的群是以字问题做为困难问题，而［Ansh93］是把共轭问题做为困难问题，两者的区别是群选择的不同。2・2・3[Anshel-Anshel-Goldfeld]密钥交换协议1999年的时候，不同于以上的几个公钥密码系统，在组合群论的基础上，I.Anshel,MAnshel和DGoldfeld提出了一个新的密钥交换协议(见③和④)，该协议中所采用的群是辫群，具有不可解的共轭问题，但是辫群的字问题可以在多项式时间内解决。在协议中，［Anshel99］利用换位子的思想，XYX-iY-i,其中Y均为辨群B中的元素，其中XYX-iY-i可以看成是Y的共轭元素和Y-1相n乘得到，或者可以看成是X和X-1的共轭元素相乘得到的，具体的密钥交换步骤如下：两方Alice和Bob分别公布字a(1)，a(2)，…，a(n)；b(1)，b(2)，…，b(m)。这些字均从群G={SID}得到，其中S是生成元，D是定义关系。Alice和Bob之间的密钥由它的共同的行为产生，Alice和Bob同时执行以下的步骤，一起产生秘密密钥：1、 Alice首先进行如下运算，Alice选择一个群G中的由a(1)，a(2)，…，a(n)生成的秘密的字X，对每一个b(i)进行共轭运算，产生m个新字c(1)，c(2)，…,c(m)，c(i)=Xb(i)X-1。2、 Alice对每一个c(i)进行改写，写成B(i)的形式，B(i)和c(i)是G中同一个元素的不同表示，i=1，…，m。B(i)能够完全掩盖住c(i)中有关X的秘密信息。由于B(i)和b(i)是关于X的共轭元素，但不能从B(i)中推断出X是什么(G有着不可解的共轭问题)，X是不可知的。3、 Alice通过公开的渠道把B(1)，B(2),…，B(m)传送给Bob。在Alice进行计算的同时，Bob进行类似的计算。1、 Bob从b(1),b(2),…，b(m)生成的G的子群中，选择一个秘密的元素Y, 用每个a(i)进行共轭等。产生d(1)，d⑵……d(n),d(i)=Ya(i)Y-1。2、 对每个d(i)进行改写，写成A(i)的形式，使得A(i)和d(i)表示相同的元素。3、 Bob把A(1),A(2),…,A(n)传送给Alice。第三步，Alice和Bob可根据所得的结果分别计算出换位子(X，Y)=XYX-1Y-1。因为，Alice可以从V=X(YXY-1)-1=Xx(A(1)),…人(n))-1中计算，如果X=x(a(l),-a(n))。并且Bob也可以计算换位子W=(XYX-i)Y-i=y(B(l),B(2),…，B(m))Y-i,如果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)关于Y的共轭元素，通过类似的计算，Alice可以知道YXY-i,Bob也是可以由秘密的Y以及Alice传送给它的B(1),B(2),…，B(m)来得到XYX-i,但是对于Alice所掌握的字X一无所知，当Alice和Bob经过计算出V和W以后，V和W是同一个字的不同表现形式，从字V和W得到Alice和Bob的共同的密钥有两个方法,第一个是辫群G中的每个元素都有且仅有一种唯一的特殊表现形式,称作经典形式，那么把V和W都写成经典形式之后，这时它们的标准形式是相同的，然后可以定义从辫群的标准形式到二进制数的单向函数H,从而使密钥K=H(V)=H(W),第二个方法是把G作为群作用在某个集合S上,并且满足E(S)=SG1(G2(S))=(G］G2)(S),(G1、G2属于G,E是G的单位元)，且G内不同的字作用到S上的元素S所得的值也是不同的。在这种条件下，密钥K=V(S)=W(S)也同样可以得到。对［Anshel-Anshel-Goldfeld］密钥交换协议的分析：首先我们不知道，上述的密钥交换协议的安全性是否以辫群共轭问题的难解程度为基础的，但是，实际上已知XYX-1和Y求解X的问题和已知XB(1)X-1,XB(2)X-1…，XB(M)X-1和B(1),B(2),-*B(M)的值来求解X的困难程度是不一样的，显然后一个问题比前面的问题要容易的多，后一个问题所面临的困难问题是不同于标准形式的共轭问题，我们可以把它称之为新的共轭问题(MSCSP),应该说这个也是从算法上来说不可解的。另一点是［Anshel-Anshel-Goldfeld］密钥交换协议所利用的辫群中密钥的共轭运算的同态性质；即XA(1)X-1XA(2)X-1=XA(1)A(2)X-1,以及(XYX-1)-1=XY-1X-1但是在Alice和Bob对X,Y进行改写，并使得从XB(1)X-1,…，XB(M)X-1或YA(1)Y-1,…，YA(N)Y-1中不能得出X,Y的值的时候，通过改写,即把上述这些辫群里的元素写成标准形式时，并不能够保证所有的标准形式能完全掩盖住秘密信息。但是只要有一个元素泄露出X或者Y的值，那么密钥就可以被破解，所以X(B1)X-1,…，XB(M)X-1和YA(1)Y-1,…，YA(N)Y-1中的秘密信息必须完全被改写掉。2・2・4［Ko-Lee-Cheon］密钥交换协议和公钥密码体制从上述的密钥交换协议可以看出，上述的协议的主要思想是利用组合群论中的一般理论，关于换位子的思想适用于任何一个群，只是在具体的实现方法上，才使用了辫群，因为辫群在实现过程中，有一些较好的优点。比如有唯一的标准形式，并且它的字问题有着快速算法，而共轭问题是困难问题等等。应该可以看出，任何具有类似性质的群都可以做为构造［Anshel-Anshel-Goldfeld］密钥交换协议的群。下面所提到的［Ko-Lee-Cheon］密钥交换协议则是更立足于辫群本身的性质（文献⑦），因此在讨论密钥交换协议的时候，对于密钥交换协议的安全性分析将更加成熟一点，并且能够相对比较实用。韩国学者HyoungKo，SangJinLee和JungHeeCheon提出，在辫群中有一些问题属于困难问题，其中能够适用于构造密钥体制的有以下一些：假设B是由a,c，…，b生成，B由c,c，…，b生成，m<n，n 12 n-1 m 12 m-1那么，辫群B可以看成是B的子群，那么有以下几个问题是困难问题：mn1、 普通的寻找共轭元素问题（GCSP）元素（X,Y）eBxB，并且Y=BXB-1，其中，BeB，m<nnm n问题：寻找AeB使行Y=AXA-1成立，m2、 共轭元素分解问题（QCDP）（X，Y）eBxB，满足Y=BXB-1，BeB，m<nnm m问题：寻找A'，A''eB，满足Y二A'XA''。m3、 寻找P次根问题，（X,Y）eBxB，满足Y=XP，XeB，nn n问题：寻找ZeB，满足，Y=Zp。n在上述几个问题的基础上，HyoungKo等提出了密钥交换协议，上述协议所利用的是第一个困难问题，在B中取两个群，LB和RB，LB是由a.a，…,n l r l 1 2a生成，而RB由a，…，a生成，由于辫群的生成元满足条件，l-l r l+l l+r-1aa=aa,i-j>2,因此对于任意的AwLB,BeRB，都能满足AB=BA。TOC\o"1-5"\h\zijji 1 r所以辫群B中的子群LB和RB之间的任意两个元素具有交换性，这是能否满n l r足密钥系统的关键。密钥交换协议的具体实现如下：1、 首先选择充分大并且较合适的两个整数（L,R）以及辫群B，LB和RB。n l r在B中选择一个比较合适的元素X,并将X公开。n2、 密钥交换者Alice和Bob分别执行以下步骤：（A） Alice从LB中任意选择一个秘密元素A，把Y.=AXA-1，传送给Bob。l1（B） Bob从RB中选择一个元素B，并将，Y2=BXB-1传送给Alice，r2（C）Alice收到Y以后，计算K=AY2A-1（D）Bob收到X以后，计算K=BY]B-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两人得到的密钥是相同的。值得注意的是，在密钥交换协议中利用的困难问题和普通的寻找共轭元素问题（GCSP）不完全是等价的，但是两者之间有紧密的关系。关于这一点，有点类似于Diffie-Hellman的密钥交换协议，因为Diffie-Hellman协议中就是由已知Gx和Y以及Gx，X中分别得到Gxy,但是这个问题可以归结为求解离散对数的问题。在辫群的协议中，也是类似的。窃听者即使能够知道AXA-1，B和BXB-1和A但要计算ABXA-1B-1,还是会归结为求解共轭元素的问题。虽然[Anshel99]也是利用了辫群的共轭算法，但在这一点上和韩国学者提出是的不一样的。与密钥交换协议非常相似，HyoungKo等同时利用辫群可以构造一个新的公钥密码体制。运用到的方法和上面基本一致，只是需要增加一个散列函数。首先定义一个从辫群元素到二进制数字的单向散列函数H:Bt{0,1}kl+r1、产生公钥及私钥阶段。（A）从B中选择一个适当的，由a,a，…，a 生成的X。l+r 12 l+r-1取LB中元素A,l设Y=AXA-i是X关于A的共轭，把Y公开，当做公钥，并且使A保密，当作私钥。2、加密运算：如给定明文Me{0，1}k和(X、Y)以后，任意从RB中选择元素Br加密以后的密文是(C，D)，C=BXB-i和D=H(BYB-i)㊉M3、解密通过计算M=H(ACA-i)㊉D可得，上面这个步骤的原因是因为ACA-i=ABXB-iA-i=(BA)XA-iB-i=BYB-i，因此，H(ACA-i［㊉D=H(BYB-i)㊉H(BYB-i)㊉M=M。㊉代表了异或运算。这个新的加密算法和密钥交换协议的理论基础相同，并且比较实用。第三章组合群论在电子支票的多签名体制中的应用

第一节三方密钥交换协议考虑将两方的密钥交换协议推广到三方或者更多的人中去，就必须利用协议本身的性质。关于Anshel-Anshel-Goldfeld密钥交换协议，因为协议中利用了换位子XYX-iY-i，很难推广到多方中去。但是Ko-Lee-Cheon协议采用了Diffie-Hellman算法的思想，因此可以稍做修改，使参加协议的人增加到三人或者多人。下面就是具体的三方协议。首先可在辫群中取三个子群LB，MB和RB，LB由q，q，•••,◎生l k rli2 l-i成，MB由q，…，q生成，RB由q ，…，q生成，其中1，k，k l+1 l+k—i r l+k+1 l+k+r—ir满足条件：1+r+k=n。利用辫群中生成元的性质可知，任意aeLB，beMB，lkceRB，都满足：ab二ba，bc二cb，ac=ca，这就是说，群LB，MB和RBr l k r中任意元素都是可以交换的。和两方协议类似，Alice，Bob和Carol执行以下的步骤：(l)Alice,Bob和Carol共同选择一个恰当的辫元x,xgB。n⑵Alice从LB中随机选择辨兀a,把x=axa-1发送给Bob。ll(3)Bob从MB中任意选择辫元bgMB，把x二bxb-1发送给Carol。kk2(4)Carol从RB中任意选择cgRB，把x=cxc-1发送给Alice。r r 3⑸Alice把y=axa-1发送给Bob。13(6)Bob把y=bxb-1发送给Carol。21(7)Carol把y=cxc-1发送给Alice。32⑻Alice计算密钥k=aya-1。3(9)Bob计算密钥k二byb-1。1(10)Carol计算密钥k=cyc-1。2由于a，b，c三个元素有交换性，因此有以下等式成立:aya-1=a(cxc-1)a-1=ac(bxb-1)c-1a-1=abcxc-1b-1a-1；32和byb-1=b(acxc-1a-1)b-1=abcxc-1b-1a-1=cyc-1=aya-1；1 2 3可知k为Alice，Bob，Carol三方的共同密钥。因为这个三方协议和Diffie-Hellman协议类似，由Diffie-Hellman协议的安全性可知，上述协议是安全的，它的困难程度基于在辫群中破解共轭问题的难度。另外，出于安全性的考虑，由文献[7]中对满足条件的辫元x所加的限制条件可知在上述协议中，x不能取成aaaz123的类型，其中agLB，agMB，agRB，而z是B中能够和LB，MB和RBTOC\o"1-5"\h\z1l2 k3r n l k r中元素都交换的辫元。因为如果x=aaaz，密钥k满足条件:123k=abcxc-1b-1a-1 =aaa-1bab-1cac-1z。1 2 3又因为x=(aaa-1)aaz，x=a(bab-1)az，x=aa(cac-1)z，通过公开1 1 23 2 1 2 3 3 12 3传输的x，x，x和x就可以计算得到aaa-1，bab-1，cac-1，从而计算出密钥。1 2 3 1 2 3因此，应该选择适当的x满足安全性的要求。不过有一点比较有利的是，同样是在文献⑺中对x的讨论中，上述x出现的概率非常小，一般不用多做考虑。第二节基于辫群的多签名体制方案3.2.1多签名介绍利用公开密钥算法对一段消息进行数字签名，这是签名方案中最常用的一种方法，它在理论上发展的已经比较完善，在实际应用中也有成熟的体制。比如说由RSA加密算法转化而成的数字签名、ElGamal签名方案、Schnorr签名算法、经过改进的Fiat-Shamir签名方案以及Guillon-Quisquater数字签名方案等等。这些数字签名的安全性或是建立在大整数分解的难度上，或是建立在计算离散对数的难度上，或是利用其他数论中的困难问题。不过这些方案都有一个特点，这些数字签名只是单个人对一份文件的签名，很少有签名方案可以拓展到多个人对同一份文件的签名上去。即使有，也只是简单的通过单签名加以迭代而得到的。但是由于实际应用的需要，对签名人数提出了更高的要求。现在需要一种新的签名方案，可以使多个人对同一份文件进行签名，这就是多签名。多签名有着广泛的应用，比如说一份文件必须有多个人签署才能执行，缺乏了其中任意一人的同意就不可以；或者是电子支票在银行、客户、商店之间转账时，银行、客户、商店为了使转账过程得以纪录，在每次交易时对同一份文件——支票进行数字签名，也需要利用多签名的技术。这些应用使得数字多签名方案的发展成为一种必然。为了满足着一要求，密码学家利用数学理论也构造了一系列多签名方案，其中比较实用且计算速度较快的是日本学者EikohChida，TakoNishizeki等基于单向环同态所构造的多签名方案。在本文中，除了介绍他们的多签名体制以外，我们还考虑利用辫群中的困难问题对基于单向环同态而构造的多签名方案进行改进，提出把组合群论思想和多签名方案结合起来，提出一个新的多签名方案。数字多签名的安全性要求：多签名方案由于签名过程涉及了多个人，并且签名完成以后要求能检验所有人对同一消息的签名，所以在安全性方面比一般的数字签名有着更高的安全性要求。首先要求多签名能够抵抗外部攻击，3.2.2基于单向环同态的多签名体制在文献⑥中，EikohChida,TakoNishzeki等首先提出了问题：在代数结构中除了群中存在单向群同态函数(即函数既是单向函数，也满足群中的同态运算)以外是否还有其它的单向函数同态,比如在环,幺半群中等。实际上,以前所构造的RSA加密算法、离散对数算法都是利用了基于单向群同态的单向陷门函数。而环同态对于这个问题的肯定回答,他们是构造了一个单向环同态来实现的。如果A是交换环R(A，+，*)，U是在加法+下的A-模，对于任意A和U,直和A㊉U内的元素(a,u)和(a,u)，可定义A㊉U中的加法㊉：(A㊉U)x1122(A㊉U)tA㊉U和乘法*：(A㊉U)x(A㊉U)tA㊉U如下：(a,u)㊉(a,u)=(a+a,u+u)；(a,u)*(a,u)=(a*a,au+au)；可以112212121122121122证明所得的(A㊉U,㊉，*)是交换环。利用这个交换环，EikohChida等有进一步证明了单向环同态的存在性，这可以表述为下面这个定理：定理：U，V都是有限交换群，”|=n，如果U和V内二进制运算是多项式内可计算的，如果存在单向群同态函数f:UtV，那么存在单向环同态F:Z㊉UtZ㊉Imf。(F的定义是：F(n,x)=(n,f(x))。)nn为了构造适当的多签名体制，文献⑥中利用了z上的同态函数：P-1f:ZtZ*，f(x)二gxmodp，g是Z*的生成元，这个函数是单向的。运用P-1 P P上面的定理，可以得到单向环同态函数：F:(Z㊉Z*)t(Z㊉Z*)，P-1 P P-1 PF(n,x)二(n,gx)。关于文献中有根据上述函数而构造的多签名体制，在此不再详述。3.2.3基于辫群的多签名体制如果要把辫群应用到构造单向环同态中，就必须考虑辫群的很多基本性质和上述单向群同态中对群的要求不完全相同，因此，必须对直和A㊉U和A㊉V的一些定义加以修改，以满足单向函数的要求，不过用辫群Bn很难满足单向函数同时又是环同态，所以经修改后的多签名体制和文献⑥中的有所不同。首先，辫群Bn是无限群，不是有限的。对于这一点，可以把环Zn改成环乙把直和Z㊉Z改成Z㊉B。另外一点限制是，A㊉U中的U是交换群，这是p-1 p-1 nA㊉U是交换环的定义中对U的基本要求，但是辫群Bn不是交换群。因此，利用辫群不一定能够构造出单向环同态，不过根据辫群的性质，辫群还是可以用来构造多签名体制。注意在文献⑦中提到了辫群的一个困难问题：(y,p)gBxZ,y二xp,xgB，nn寻找满足条件的x。利用上述困难问题构造单向函数f:BTB，f(x)二xp(pnn是固定的正整数)，如果B中元素x,y满足条件f(xy)=f(x)f(y)，根据前文EikohnChida等证明的定义和定理，则在直和Z㊉B中定义函数F:Z㊉BTZ㊉B为n n nF(n,x)=(n,xp)，F(,)也是单向函数，并且(n,x)，(m,y)同时满足加法和乘法运算：F((n,x)㊉(m,y))=F(n,x)㊉F(m,y)；F((n,x)(m,y))=F(n,x)F(m,y)。加法和乘法的同态性质正是构造多签名体制所必须使用的。因为aa=◎a，li-j>2。由c，c，…，c生成的Bn的子群LBlTOC\o"1-5"\h\zij ji 1 2 l-1和a，…，a生成的子6群RB内元素是互相交换的，即ab=ba,任意agLB,l+1 l+r-1 r lbgRB，所以只要取元素agLB，bgRB，a,b满足群的同态性质：r l rf(ab)=(ab)p=apbp=f(a)f(b)，因此直和Z㊉B中的(n,a)，(m,b)也满足加法n和乘法的同态性质。利用上述性质，构造多签名体制如下：记U,U，…，U为签名方，对1<i<r,X二(n,x)为U的秘密密钥，1 2 r iiiixgLB，其中LB是B的子群，每个LB分别由生成元c ，…，q生成。TOC\o"1-5"\h\zi i in i (i—1)t+1 it-1Y=F(X)=(n,xp)是U的公共密钥，并且假设存在散列函数H:ZTZ㊉LB,iiiii r+1LB也是B的子群，生成元是q ，…，q。因此LB中的任意元素都满r+1 n rt+1 (r+1)t-1 i足交换性。设待签名的消息为M,并且H(M)=(n,x)。U，U，…，U等签名1 2 r方相继执行一下步骤：第一名签名者U:1随机生成k=(m,y)gZ㊉LB，LB与LB的定义类似。1 11 r+2 r+2 i计算R=F(k)gZ㊉LB。1 1 r+2计算S=X*R㊉H(M)*k1111把M、R和S