第一章密码学和电子商务的安全性

摘要公钥密码体制从开始提出到现在，它的主要思想是利用了数论中的困难问题。例如，应用最广泛的RSA加密体制是基于大整数分解成两个素数的困难问题构造的加密算法，ElGamal数字签名是根据在剩余类环中由生成元求解其离散对数的问题的困难程度来实现的。和这些加密算法不同的是本文中利用了组合群论的思想构造的一些加密体制。组合群论中有些特定的字问题和共轭问题是困难问题，可用于构造密码学的基础。N.R.Wager和M.R.Magyarik第一次提出了用组合群论的理论来构造公钥加密算法的方法，他们所利用的是不可解的字问题，其次在93年，M.Anshel和I.Anhel提出了利用不可解的共轭问题对信息进行加密的算法，这也是公钥密码算法，其基本思想和第一个基本相似。更进一步，在99年I.Anshel，M.Anshel和D.Goldfeld利用辫群的共轭问题实现了一个新的密钥交换协议。密码学在组合群论中的最新进展是Hyoung.Ko，SangJinLee和JungHeeCheon提出的密钥交换协议和加密协议，他们同样是利用了辫群的不可解共轭问题，但是主要思想和具体的实现上和I.Anshel等提出的密钥交换协议有很大的区别。本文简要介绍这些加密算法和协议。同时，利用辫群的一些基本特点把辫群的另一个困难问题应用到基于单向环同态的多签名体制中去，提出了一个新的多签名方案，并且讨论了这个多签名方案在电子支付系统中的应用。关键词：辫群，字问题，共轭问题，密钥交换协议，多签名体制组合群论在密码学和电子商务的安全性中的应用数学学院98级数学系方初莹目录第一章密码学和电子商务的安全性………………………………1第一节密码学概述………………………………………………1第二节电子支付系统的安全性…………………………………4第二章组合群论和密码学…………………………………………4第一节基础知识和背景…………………………………………4第二节密码体制和密钥交换协议………………………………72.2.1[Wag84]公钥密码体制…………………………………72.2.2[Anshel93]密码体制……………………………………92.2.3[Anshel-Anshel-Goldfeld]密钥交换协议………………92.2.4[Ko-Lee-Cheon]密钥交换协议和密码体制……………11第三章组合群论在电子支票的多签名体制中的应用……………14第一节三方密钥交换协议……………………………………14第二节基于辫群的多签名体制方案…………………………153.2.1多签名介绍……………………………………………163.2.2基于单向环同态的多签名体制………………………173.2.3基于辫群的多签名体制………………………………18第一章密码学和电子商务的安全性第一节密码学概述信息安全是密码学的基本要求，为了要达到这一点，密码学始终涉及两个方面的斗争。其中一方（发送者）是设法对消息进行加密，使得只能是具有特殊权利的人（接受者）才能够接受和阅读信息。而另一方则是尽力设法截获信息，破译密文，或者用修改以后的假信息欺骗接收者。在本文中，我们主要讨论的是前一方，即考虑用何种方法能够对消息进行安全、有效且快捷的加密，保证消息的传送。待加密的消息被称作明文(plaintext)，用某种方法伪装消息并隐藏它的内容的方法称作加密(encryption)，被加密以后的消息称为密文，而把密文转变成明文的过程称为解密。加密体制中的加密运算是由一个算法类组成，这些算法类的不同运算可用不同的参数表示，不同的参数分别代表不同的算法，被称作密钥，密钥空间是所有密钥的集合。密码体制一般是指密钥空间与相应的加密运算结构，同时还包括了明文和密文的结构特征。在密码体制的设计和评价中要考虑到以下一些基本原则：（1）不可破原则，指该密码体制在理论上或实际上是不可破解的。（2）部分信息丢失不会影响整个系统的安全性。即硬件设备、加密算法或全部密文与部分明文这些信息的丢失不会危及整个系统的安全。（3）与计算机、通信系统匹配原则。要求密码系统不是独立存在的，而可以在计算机或通信系统中使用。密码体制发展到现在，已经有了很多种不同的类型。但是从密码体制所使用算法的分类上说，可以分为两种。一种是利用了对称算法，又称作传统密码算法；另一种则是利用了公开密钥算法。对称算法是指加密密钥和解密密钥能够互相推算出来，公开了一个也就相当于公开另一方。因此对称算法的密钥只能由发送者和接收者两方知道，他们必须事先商定好密钥，这一点就涉及了密钥交换协议。公开密钥算法是指公开了加密算法KE以后不会泄露解密算法KD，因此和对称算法相比，任何人都可以通过公开渠道（网络或密钥管理中心）已知他人的加密密钥，把明文加密以后传送给接收者，而只有拥有解密密钥KD的人才能够对密文解密。这在密钥管理和消息的传送方面更具有优势。另外，公开密钥算法还可以运用在数字签名中。在目前应用于实际生活比较广泛的公钥加密算法包含有RSA密码体制和椭圆曲线密码体制。RSA密码体制：1979年，ShamirRivest和Adelman提出了第一个也是应用最广的公钥密码体制，即RSA体制。经过20多年的密码分析和攻击，迄今为止，RSA被证明仍是安全的。设n=pq，p和q是两个大素数，a和b是两个整数，定义密钥空间为(,,,,):,1(mod())npqabnpqabn。把n，b作为公开密钥，而p，q，a，()n，作为秘密密钥。整个加密算法就是y=()modbKExxn，而解密算法是()modaKDyyn，由Euler定理知道，()KxDy成立，上述解密的方法正确。由于RSA加密算法是指数运算，因此当密钥越大时，计算速度越慢。RSA算法比通常的DES算法慢了1500倍。并且RSA的计算量很大，为了要达到较高的安全程度，RSA的密钥位数比其它的密码体制大的多，现在一般需要1024位的密钥。所以一般对速度要求较高的数字签名或智能卡中的身份验证不太使用RSA密码体制，而采用其它较快的算法。椭圆曲线密码系统就是其中的一种。椭圆曲线密码系统：椭圆曲线密码体制和RSA体制比较起来，所需要的密钥量小，安全程度高，比如RSA密码体制需要1024-bit的密钥才能达到的安全程度，利用椭圆曲线只需要160比特位的密钥就能够保证同样的安全（文献⑨），密钥长度的减少同时带来了计算速度的提高。即使是在剩余类环PZ运用离散对数而构造的加密系统的安全程度也要低于椭圆曲线，因此椭圆曲线系统不愧为一个性质较好的密码系统。椭圆曲线第一次运用于公钥密码算法是在1985年NealKoblitz和V.S.Miller提出来的。他们并没有提出新的算法，只是把椭圆曲线运用到已存在的公钥密码算法中，比如说ElGamal加密算法。利用ElGamal思想构造的椭圆曲线密码体制如下显示：首先是产生密钥阶段。Bob从nZ中随机选取充分大的整数Bk，随后计算出椭圆曲线上的点P=BkQ（Q是椭圆曲线上的适当的一点），将Bk保密，作为秘密密钥，并将P公开，作为公钥。加密方法如下：如果Alice想把消息M（同样是椭圆曲线上的一点）发送给Bob,就从nZ中随机选择整数nlZ后，计算出1SlQ和2SMlP的值，加密以后的信息就是椭圆曲线上两点12(,)SS。解密：Bob收到加密信息12(,)SS后，通过密钥Bk就可以计算M=2S-Bk1S得到消息M。纵观上面提出的两个公钥密码体制，再加上其它的密码系统，在加密的时候都采用了单向函数的思想。单向函数是指函数f满足从x计算()fx容易，但从()fx计算x有可能不可行。单向函数的构造依赖于计算复杂度理论，即利用一些困难问题。上述两个系统的安全性都依赖于一些数论中的基本困难问题。比如说RSA体制利用了把大整数n分解为两个大素数的难度，而椭圆曲线是利用了求解离散对数问题的困难程度，（即根据P=BkQ和Q求解nZ中整数Bk）。这些密码体制都是很成功的，在实际中也有了进一步的应用。对于本文来说，我们的主要目的是把组合群论的思想引进到密码学中，所以利用了组合群论中的一些困难问题，如字问题，共轭问题等等，由此构造出新的密码体制。协议（protocol）是指一系列的步骤，它包括两方或者多方，设计它的目的是要完成一项任务。密钥交换协议(keyexchangeprotocol)是指两人或多人之间通过一个协议取得密钥并用于进一步的加密算法中的方法。在实际的密码世界中密钥交换其实是很重要的一个环节。比如说利用对称加密算法，如果双方没有约定好密钥，就必须再进行密钥交换。但是如何使得密钥到达接收者和发送者手里是件很复杂的事情。最早利用公钥密码思想提出的密钥交换协议有Difffie-Hellman算法。新的密钥交换协议有利用组合群论中的辫群nB构造的两个协议，Anshel-Anshel-Goldfeld协议和Ko-Lee-Cheon协议。第二节电子支付系统的安全性电子商务作为新兴事务，已经随着计算机和网络技术的成熟得到了飞速发展，而且使得商家的整体经营方式都有了变化。电子商务是以数字化的电子方式，以网络为媒体进行的商业数据交换或其他商业活动。电子商务的一个重要组成部分就是电子支付系统。电子支付是指交易的各方是通过电子手段，比如说银行的电子存款系统和电子清算系统来记录和转移资金的方式。一个安全、可靠的电子支付系统是电子商务的交易活动能够正常进行的保证。目前INTERNET上的电子支付系统主要有四种：信用卡、IC卡、电子现金（e-Cash）和电子支票（e-Check）。一般来说，电子支付系统必须满足以下的安全性要求，包括有消息的保密性、能够确认双方都具有合法的交易身份的能力、保证交易完毕以后的信息是无法修改的和交易以后各方对业务的不可否认性。作为电子支付系统的不同代表，电子现金和电子支票虽然有一定的共性，但在安全性要求和性质方面有着各自独特的特点。电子支票和纸张支票转移支付的原理类似，是利用数字传递将钱款从一个账户转移到另一个账户的电子付款方式。在电子支票实现的过程中，它的安全性问题是，如何保证银行、用户、商场对电子支票进行签名的有效性。由于转账在银行、用户和商场三方进行，在每一次交易完成以后都必须对消息签名，用来保证交易信息的真实、完整和不可否认。所以在交易过程中将会涉及到数字多签名。在本文中，我们最后讨论了一种利用辫群构造的多签名体制，可以把上述多签名运用到电子支票转账系统中去。电子现金是一种以数据形式流行的货币，因此和支票相比，电子现金更强调满足隐私性和可分割性，另外，虽然要保证用户的隐私权，电子现金出于安全性的考虑，还需要满足电子现金的不可伪造性和不可重用性。如果同一份电子现金被使用两次，使用者的身份就可以被发现。关于电子现金，现在最主要讨论的是它的可分性的实现。第二章组合群论和密码学第一节基础知识和背景自从1984年N.R.Wager和M.R.Magyarik在①中提出了第一个用组合群论的理论构造公钥密码体制的方法以来，在密码学家们的共同努力下，利用组合群论的理论已经提出多个公钥密码体制和密钥交换协议。由于组合群论中的数学工具和以前数论中的内容截然不同，有必要对组合群论中的一些定义和定理加以说明，从而可运用到密码学中去，得到不同的加密算法。群G称作是有限生成的（finitelygenerated），如果G存在有限个生成元1,2,gg…,ng，满足G中任意一个元素（又称为字）都可以表示成生成元和它们的逆的有限乘积。群G称作是可以有限表示的（finitelyrepresented），如果在G中有有限个元素1r，2r，…，kr满足在群G中，1re，2re，…，kre，其中e是单位元，那么1r，2r，…，kr称为G的生成元12,,gg…,ng的一组定义关系，。换一种角度，如果把群G看成是n个元素X{12,,aa…,na}生成的自由群F(X)的商群，即存在F(X)的正规子群N，使得F(X)G=N成立，那么G是可以有限表示的意思是：如果1r，2r，…kr对应F(X)中的元素1w，2w…kw，那么12,,ww…,kw是F(