基于RSA的盲签名方案的设计实现毕业论文

PAGE毕业论文基于RSA的盲签名方案的设计实现指导教师学院名称信息学院专业名称计算机科学与技术论文提交日期2009年5月论文答辩日期年月答辩委员会主席____________评阅人____________摘要盲签名是指签名者并不知道所签文件或消息的具体内容而文件或消息的拥有者又可以从签名人关于盲化后文件或消息的签名得到签名人关于真实文件或消息的签名。盲签名允许消息者先将消息盲化，而后让签名对盲化的消息进行签名，最后消息拥有者对签字除去盲因子，得到签名者关于原消息的签名。盲签名可以有效保护所签署消息的具体内容，所以在电子商务和电子选举等领域有着广泛的应用。本论文在研究网络信息安全技术的基础上，深入研究了基于RSA算法的盲签名体制，并简单实现了基于vc++6.0平台的盲签名系统。系统简单模拟了盲签名过程的各个步骤，实现了对一个随机产生的明文进行盲签名操作。该系统主要包括两个部分，即消息的盲签名部分和盲签名的验证部分。在该系统的签名部分，首先生成一个RSA密钥对，然后对一个随机产生的明文进行盲化，然后对盲化后的明文进行签名。在系统的验证部分，首先要对签名后的明文进行脱盲，此时得到的就是签名。然后对此签名用密钥计算，然后与最开始的明文进行对比，如果相同，则证明盲签名成功。系统简单模拟了盲签名过程的各个步骤，实现的功能比较简单，没有设计不可跟踪性的盲签名（即消息的签名者不知自己何时对这个消息签名），而且没有可视化的界面，还有许多不足的地方需要改进。关键词：盲签名数字签名电子商务电子选举

目录1引言 11.1选题背景 11.2选题意义 21.3研究内容及论文结构安排 22基本的数学理论 32.1素数 32.1.1素数 32.1.2拟素数的概述 42.1.3检验大素数的具体方法 52.2Euler函数的介绍 62.3同余理论 62.3.1同余的定义 62.3.2同余的常用定理 72.4扩展欧几里德算法 73基于RSA公钥密码盲签名算法 113.1公钥密码 113.1.1单钥密码 113.1.2公钥密码 123.2RSA算法 143.2.1具体原理 143.2.2RSA系统的参数选择 153.2.3举例说明 163.3基于RSA体制的盲签名体制 163.3.1盲签名 163.3.2完全盲签名协议 163.3.3盲签名协议 173.3.4基于RSA算法的盲签名 174基于RSA盲签名的设计与实现 194.1实验环境选择 194.2盲签名算法的详细设计 194.2.1生成公钥和私钥 194.2.2盲签名的过程 204.2.3盲签名的验证过程 214.3数据结构定义 234.4主要算法的实现 234.4.1随机产生大素数 234.4.2大整数的基本运算 244.4.3求大整数的逆元 254.5实现效果及分析 264.5.1盲签名的实现效果 274.5.2盲签名验证的实现效果 285结束语 29致谢 30参考文献 31英文摘要 32毕业论文成绩评定表……34PAGE231引言随着计算机互联网技术的不断进步，Internet前景越来越美好，全球经济发展正在进入一个全新的信息时代，知识经济初见端倪。计算机信息的保密问题也就显得越来越重要了，无论是个人信息通信还是电子商务发展，都迫切需要保证Internet网上信息传输的安全，也就是要保证信息安全。信息安全技术是一门综合学科，它涉及信息论、计算机科学和密码学等多方面知识，它的主要任务是研究计算机系统和通信网络内信息的保护方法以实现系统内信息的可靠、保密、真实和完整。其中，信息安全的核心是密码技术。密码技术是集数学、计算机科学、电子与通信等诸多学科于一身的交叉学科。它不仅能够保证机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。是现代化发展的重要科学之一。1.1选题背景随着Internet网络的不断普及，许多传统生活方式正受其影响逐渐朝着电子化，网络化的方向发展，如E-mail的普及已逐渐取代了传统书信的使用；再如，人们利用电子方式购物，足不出户就可以买到生活必需品，将来甚至可能在家中参与电子投票选举。但随着电子化网络化的便捷而带来的是众多的安全隐患，比如在网上用信用卡购物，相应的交易信息就会被存储到数据库中，久而久之，人们的消费习惯和财政状况就有可能被某些别有用心的人所获知，这肯定不是人们所希望看到的。消费者实用的电子现金必须加上银行的数字签名才能生效，此时为了保护消费者的匿名性，就要用到盲签名的技术；同样在电子选举中，选民提交的选票也必须盖上选委会的戳记（即数字签名）才合法，为了保护选民的匿名性也要用到盲签名技术[1]。Internet给人们的生活，工作带来许多方便，如便捷的网上购物，网上银行，网上证券，电子政务等。Internet的可怕之处在于网络中有一些人利用所掌握的技术非法侵入计算机系统，窃听、截取、篡改、伪造一些重要的数据，造成巨大损失。由于TCP/IP服务的脆弱性和系统漏洞的不可避免性，使得黑客攻击时间不但无法杜绝，反而日益增多。基于目前这种无网不入的黑客攻击现状，数据加密显得尤其重要[2]。RSA是使用最广泛的公钥密码系统，它可以用在保密性和数字签名中。1976年Diffie和Hellman提出了公钥密码思想，1977年由Rivest，Shamir和Adleman首次实现了著名的RSA密码系统，它的安全性是基于大整数素因子分解的困难性。而盲签名的概念是1983年由Chaum首先提出的，盲签名因其在不可跟踪电子支付系统中的重要应用而引起惯犯的兴趣。简而言之，盲签名方案是具有下列两个特征的普通数字签名方案：(1)盲性：消息内容对签名者是不可见的。(2)不可链接性：在签名被接受者泄漏后，签名者不能追踪签名[3]。1.2选题意义随着社会信息化的不断发展，特别是计算机及其网络在社会生活的各个领域得以普遍应用，人们对信息安全要求越来越强烈。密码技术是一项可防止信息泄露和篡改的技术，它是维护信息保密性、完整性和可靠性的重要手段。盲签名技术也是一种对原始信息加密的一种手段，它可以利用在很多地方，例如网上购物，电子选举之类的，盲签名是保障用户的匿名性，那些需要用到匿名签名的地方就会用到盲签名，从而盲签名的发展也就越来越快。选取该题目作为毕业论文，是希望对盲签名做更近一步的了解，理解其中的原理以及其他相关知识，熟悉生活中各个盲签名使用的领域。1.3研究内容及论文结构安排本论文在研究网络信息安全技术的基础上，深入研究了RSA公钥密码算法原理，讨论了该算法的安全性，研究了其实现过程，并且研究了基于RSA算法的盲签名及其实现。很多公钥密码体制如RSA公钥密码算法实现的关键问题是加解密运算中涉及大量计算问题，计算开销大，加解密运算时间长，其核心运算是大数模乘运算和乘法逆元计算。论文主要分为三个部分：第一部分：介绍了当前国内外盲签名研究现状以及选择该题目作为毕业论文的意义。第二部分：介绍了论文中所用到的基本数学理论第三部分：深入研究了基于rsa公钥密码的盲签名算法第四部分：详细阐述了基于rsa的盲签名的设计与实现过程第五部分，论文的结束语和展望。2基本的数学理论密码学是建立在坚实的数学基础之上的，它涉及代数、概率论、组合学以及信息论等，其中尤其是数论。曾被称为“象牙塔”的数论已经悄悄进入了普通人的生活。奇数、偶数、素数、合数，数论研究的就是这些最简单的数——整数及其内部关系，从这些简单的数中诞生了“费马大定理”、“哥德巴赫猜想”和“朗兰兹纲领”这样的难题，它们吸引数学家们花费数十年、甚至整世纪努力研究。密码系统多以大素数作为素材，因为它只能被1和它自身整除，作为密钥的素数越大，就意味着破解的可能性越小。本章主要介绍一下数论的一些基础知识，以便后文的理解。2.1素数2.1.1素数正整数分为素数、合数和1。一个正整数，除了能被1和自己整除外，再不能被其他的整除，那么我们就叫它素数，或者叫质数。比如2，3，5，7，11，…等。不要以为所有的奇数都是素数，比如9就不是。如果数a能被数b整除，就称b是a的一个因子，记为b|a。如果b是素数，则b是a的素因子。若a不能被b整除，就记为b+a。显然，除2以外的偶数都是合数，既是素数又是偶数的数仅有2一个，2也是最小的素数。素数的个数是无穷多个的吗？答案是肯定的。证明：假设素数的个数为有限的n个，列举为{}。我们考察数,显然{}中任何一个或若干个之积都不能整除m,也就是说m不能被这些素数或小于m的合数整除，所以m也是素数。与假设矛盾，命题得证。(1)素数的分布素数的分布式数论研究的一个重要内容，素数的分布极不规律。不过可以靠经验得出素数分布的一些推测和定理。例如10000以内的素数分布：1~100中间的素数个数为251~1000中间的素数个数为1681000~2000中间的素数个数为1352000~3000中间的素数个数为1273000~4000中间的素数个数为1204000~5000中间的素数个数为1195000~10000中间的素数个数为560可以初步看出越往上，素数分布越稀。令(x)表示不超过x的素数个数，有如下公式成立。可以看出：当x越大，越接近1。这就是素数定理。(2)几个基本定理[定理1]除法定理——对任意整数a和任意整数n,存在唯一的整数q和r,满足0<rn,并且。[定理2]算术基本定理——如果不计素因子的次序，则只有一种方法可以把一个大于1的整数分解成素数的连乘积。这定理非常重要，在计算机理论中很多重要的定理都需要这个定理来证明，这个定理实际上给出了整数集和素数集之间的对应关系。例如6000可以表示成(4,1,3),因为[4]。2.1.2拟素数的概述根据Fermat小定理，可得，如果n是一个素数，则对任意整数b，（b，n）=1，有bn-1=1（modn），那么可以得到：如果有一个整数b（b，n）=1使得bn-1≠1（modn）。（1）拟素数的定义设n是一个奇合数，如果整数b，（b，m）=1使得同余式bn-1=1（modn）（1）成立，则n叫做对于基b的拟素数。（2）有关拟素数的重要定理设n是一个奇合数，则（i）n是对于基b，((b,n)=1)，的拟素数当且仅当b模n的指数整除n-1（ii）如果n是对于基b1(b1,n)=1),和基b2((b2,n)=1),的拟素数，则n是对于基b1b2的拟素数（iii）如果n是对于基b，(b,n)=1,的拟素数，则n是对于基b-1的拟素数（iv）如果有一个整数b，（b,n）=1，使得同于式（1）不成立，则模n的简化剩余系中至少有一半的数使得同余式（1）不成立。（3）定理的应用对于大奇数，如果有一个整数b，（b，n）=1，使得同余式子（1）不成立，则模n的简化剩余系中至少有一半的数使得同余式（1）不成立。这就是说，对于随机选取的整数b，（b，n）=1，有50%以上的机会来判断出n是合数，或者说n是合数的可能性小于50%[5]。2.1.3检验大素数的具体方法随机选取整数b1，0<b1<n,利用广义欧几里德除法计算b1和n的最大公因数d1=（b1，n），如果d1>1,则n不是素数。如果d1=1，则计算b1n-1（modn），看同余式（1）是否成立。如果不成立，则n不是素数；如果成立，则n是合数的可能性小于1/2或者说n是素数的可能性大于1-1/2.重复上述步骤。再随机选取整数b2，0<b2<n,利用广义欧几里德除法计算b2和n的最大公因数d2=（b2，n），如果d2>1,则n不是素数。如果d2=1，则计算b2n-1（modn），看同余式（1）是否成立。如果不成立，则n不是素数；如果成立，则n是合数的可能性小于1/22或者说n是素数的可能性大于1-1/22.重复以上步骤，直至第t步。随机选取整数bt，0<bt<n,利用广义欧几里德除法计算bt和n的最大公因数dt=（bt，n），如果dt>1,则n不是素数。如果dt=1，则计算btn-1（modn），看同余式（1）是否成立。如果不成立，则n不是素数；如果成立，则n是合数的可能性小于1/2t或者说n是素数的可能性大于1-1/2t上述过程可简单归纳为：Fermat素性检验给定奇整数n>2,和安全参数t。随机选取整数b，1<b<n-1;计算r≡bn-1（modn）；如果r≠1，则n是合数上述过程重复t次[6]。本文使用Fermat素性检验来判断随机产生的大整数是否为素数。2.2Euler函数的介绍Euler函数，常用表示，就是小于且与互素的正整数的个数。显然，当为素数时，有。下面介绍一个结论：如果两个整数，且，则有。2.3同余理论同余是数论中一个十分重要的概念，同余理论在密码学，特别是公钥密码学中有着非常重要的作用。2.3.1同余的定义给定一个正整数m，两个整数a，b叫做模m同余，如果a-b被m整除，或者m|a-b，记作a≡b（modm）；否则，则叫作模m不同余，记作a≠b（modn）。注：模m是一个正整数，在同余性质的讨论中为一个固定整数。2.3.2同余的常用定理(1)设吗是一个正整数，a，b是两个正整数，则a≡b(modm)的充要条件是存在一个整数k使得a=b+km.(2)模m同余是等价关系，即(i)(自反性)对任意整数a，a≡a(modm);(ii)(对称性)若a≡b(modm),则b≡a(modm);(iii)(传递性)若a≡b(modm),b≡c(modm),则a≡c(modm);(3)整数a,b模m同余的充分必要条件是a，b被m除的余数相同。(4)设m是一个正整数，a1，a2，b1，b2是四个整数，如果a1≡b1(modm),a2≡b2(modm)则(i)a1+a2≡b1+b2(modm);(ii)a1a2≡b1b2(modm).(5)若x≡y(modm),ai≡bi(modm),0<i<k,则a0+a1x+…+akxk≡b0+b1y+…+bkyk(modm)(6)设整数n有十进制表示：n≡ak10k+ak-110k-1+…+a110+a0,0<=ai<10则3|n的充分必要条件是：3|ak+…+a0;而9|n的充分必要条件是：9|ak+…+a0;2.4扩展欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：定理：gcd(a,b)=gcd(b,amodb)证明：a可以表示成a=kb+r，则r≡amodb假设d是a,b的一个公约数，则有d|a,d|b，而r=a-kb，因此d|r因此d是(b,amodb)的公约数假设d是(b,amodb)的公约数，则d|b,d|r，但是a=kb+r因此d也是(a,b)的公约数因此(a,b)和(b,amodb)的公约数是一样的，其最大公约数也必然相等，得证欧几里德算法就是根据这个原理来做的，其算法用C语言描述为：voidswap(int&a,int&b){intc=a;a=b;b=c;}intgcd(inta,intb){if(0==a){returnb;}if(0==b){returna;}if(a>b){swap(a,b);}intc;for(c=a%b;c>0;c=a%b){a=b;b=c;}returnb;}扩展欧几里德算法扩展欧几里德算法不但能计算(a,b)的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下：intgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;if(0==a){//有一个数为0，就不存在乘法逆元ar=0;br=0;returnb;}if(0==b){ar=0;br=0;returna;}x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;intk;for(t3=x3%y3;t3!=0;t3=x3%y3){k=x3/y3;t2=x2-k*y2;t1=x1-k*y1;x1=y1;x1=y2;x3=y3;y1=t1;y2=t2;y3=t3;}if(y3==1){//有乘法逆元ar=y2;br=x1;return1;}else{//公约数不为1，无乘法逆元ar=0;br=0;returny3;}}本文用扩展欧几里德原理来求大整数的乘法逆元

3基于RSA公钥密码盲签名算法RSA算法是公钥密码体制中最负盛名的算法，也是第一个既能用于数据加密也能用于数字签名的算法，而且易于理解和操作。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。RSA算法的安全性是基于整数的因子分解困难性上的。国际上的一些标准化组织如ISO,IYU等都把RSA作为标准使用，现在流行的PGP也采用了RSA算法作为其加密解密和数字签名的算法[7]。3.1公钥密码按照密钥的不同，可以将密码体制分为公钥密码体制和单钥密码体制。3.1.1单钥密码单钥密码体制又称对称密码体制，是一种比较传统的加密方式，其加密运算、解密运算使用的是同样的密钥，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码（称为对称密码）。因此，通信双方都必须获得这把钥匙，并保持钥匙的秘密。单钥密码系统的安全性依赖于以下两个因素：第一，加密算法必须是足够强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保算法的秘密性（事实上，现实中使用的很多单钥密码系统的算法都是公开的），但是我们一定要保证密钥的秘密性。从单钥密码的这些特点我们容易看出它的主要问题有两点：第一，密钥量问题。在单钥密码系统中，每一对通信者就需要一对密钥，当用户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密钥的产生﹑存放和分配将是一个难以解决的问题。第二，密钥分发问题。单钥密码系统中，加密的安全性完全依赖于对密钥的保护，但是由于通信双方使用的是相同的密钥，人们又不得相互交流密钥，所以为了保证安全，人们必须使用一些另外的安全信道来分发密钥，例如用专门的信使来传送密钥，这种做法的代价是相当大的，甚至可以说是非常不现实的，尤其在计算机网络环境下，人们使用网络传送加密的文件，却需要另外的安全信道来分发密钥，显而易见，这是非常不智是甚至是荒谬可笑的。3.1.2公钥密码正因为单钥密码系统存在如此难以解决的缺点，发展一种新的﹑更有效﹑更先进的密码体制显得更为迫切和必要。在这种情况下，出现了一种新的公钥密码体制，它突破性地解决了困扰着无数科学家的密钥分发问题，事实上，在这种体制中，人们甚至不用分发需要严格保密的密钥，这次突破同时也被认为是密码史上两千年来自单码替代密码发明以后最伟大的成就。这一全新的思想是本世纪70年代，美国斯坦福大学的两名学者Diffie和Hellman提出的，该体制与单钥密码最大的不同是：在公钥密码系统中，加密和解密使用的是不同的密钥（相对于对称密钥，人们把它叫做非对称密钥），这两个密钥之间存在着相互依存关系：即用其中任一个密钥加密的信息只能用另一个密钥进行解密。这使得通信双方无需事先交换密钥就可进行保密通信。其中加密密钥和算法是对外公开的，人人都可以通过这个密钥加密文件然后发给收信者，这个加密密钥又称为公钥；而收信者收到加密文件后,它可以使用他的解密密钥解密，这个密钥是由他自己私人掌管的，并不需要分发，因此又成称为私钥，这就解决了密钥分发的问题。如果两个在不安全信道中通信的人，假设为A（收信者）和B（发信者），他们希望能够安全的通信而不被他们的敌手Hack破坏。A想到了一种办法，她使用了一种锁（相当于公钥），这种锁任何人只要轻轻一按就可以锁上，但是只有A的钥匙（相当于私钥）才能够打开。然后A对外发送无数把这样的锁，任何人比如B想给她寄信时，只需找到一个箱子，然后用一把A的锁将其锁上再寄给A，这时候任何人（包括B自己）除了拥有钥匙的A，都不能再打开箱子，这样即使Hack能找到A的锁，即使Hack能在通信过程中截获这个箱子，没有A的钥匙他也不可能打开箱子，而A的钥匙并不需要分发，这样Hack也就无法得到这把“私人密钥”。从以上的介绍可以看出，公钥密码体制的思想并不复杂，而实现它的关键问题是如何确定公钥和私钥及加/解密的算法，也就是说如何找到“A的锁和钥匙”的问题。我们假设在这种体制中,PK是公开信息，用作加密密钥，而SK需要由用户自己保密，用作解密密钥。加密算法E和解密算法D也都是公开的。虽然SK与PK是成对出现，但却不能根据PK计算出SK。它们须满足条件：(1)加密密钥PK对明文X加密后，再用解密密钥SK解密，即可恢复出明文，或写为：(2)加密密钥不能用来解密，即(3)在计算机上可以容易地产生成对的PK和SK。(4)从已知的PK实际上不可能推导出SK。(5)加密和解密的运算可以对调，即：从上述条件可看出，公开密钥密码体制下，加密密钥不等于解密密钥。加密密钥可对外公开，使任何用户都可将传送给此用户的信息用公开密钥加密发送，而该用户唯一保存的私人密钥是保密的，也只有它能将密文复原、解密。虽然解密密钥理论上可由加密密钥推算出来，但这种算法设计在实际上是不可能的，或者虽然能够推算出，但要花费很长的时间而成为不可行的。所以将加密密钥公开也不会危害密钥的安全。这种体制思想是简单的，但是，如何找到一个适合的算法来实现这个系统却是一个真正困扰密码学家们的难题，因为既然PK和SK是一对存在着相互关系的密钥，那么从其中一个推导出另一个就是很有可能的，如果敌手Hack能够从PK推导出SK，那么这个系统就不再安全了。因此如何找到一个合适的算法生成合适的Pk和SK，并且使得从PK不可能推导出SK，正是迫切需要密码学家们解决的一道难题。这个难题甚至使得公钥密码系统的发展停滞了很长一段时间。为了解决这个问题，密码学家们考虑了数学上的陷门单向函数，下面，我们可以给出它的非正式定义：A的公开加密函数应该是容易计算的，而计算其逆函数（即解密函数）应该是困难的（对于除A以外的人）。许多形式为Y=f（x）的函数，对于给定的自变量x值，很容易计算出函数Y的值；而由给定的Y值，在很多情况下依照函数关系f(x)计算x值十分困难。这样容易计算但难于求逆的函数，通常称为单向函数。在加密过程中，我们希望加密函数E为一个单项的单射函数，以便可以解密。虽然目前还没有一个函数能被证明是单向的，但是有很多单射函数被认为是单向的。例如，有如下一个函数被认为是单向的，假定n为两个大素数p和q的乘积，d为一个正整数，那么定义f：(如果，那么事实上这就是我们以下要说的RSA加密函数)如果要构造一个公钥密码体制，仅给出一个单向的单射函数是不够的。从A的观点来看，并不需要E是单向的，因为它需要用有效的方式解密所收到的信息。因此，A应该拥有一个陷门，其中包含容易求出E的你函数的秘密信息。也就是说，A可以有效解密，因为它有额外的秘密知识，即SK，能够提供给你解密函数D。因此，我们称一个函数为一个陷门单向函数，如果它是一个单向函数，并在具有特定陷门的知识后容易求出其逆。考虑上面的函数。我们能够知道其逆函数(x)有类似的形式，对于合适的取值d。陷门就是利用n的因子分解，有效的算出正确的指数d（对于给定的e）。为方便起见，我们在特定的某类陷门单向函数中随机选取一个函数作为公开加密函数；其逆函数(x)是秘密解密函数。那么公钥密码体制就能够实现了。根据以上关于陷门单向函数的思想,学者们提出了许多种公钥加密的方法，它们的安全性都是基于复杂的数学难题。根据所基于的数学难题，至少有以下三类系统目前被认为是安全和有效的：大整数因子分解系统(代表性的有RSA)、椭园曲线离散对数系统(ECC)和离散对数系统(代表性的有DSA)[8]。3.2RSA算法该算法基于下面的两个事实,这些事实保证了RSA算法的安全有效性：(1)已有确定一个数是不是质数的快速算法；(2)尚未找到确定一个合数的质因子的快速算法。3.2.1具体原理(1)任意选取两个不同的大质数p和q，计算乘积；(2)任意选取一个大整数e，e与互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用。(3)确定解密密钥d：根据e、p和q可以容易地计算出d。(4)公开整数n和e，但是不公开d；(5)将明文P(假设P是一个小于n的整数)加密为密文C，计算方法为：(6)将密文C解密为明文P，计算方法为：P≡modn然而只根据n和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。RSA的证明如下：先不加证明的引用两个正确的定理。定理1(Euler)对任意的aZn*,有,其中Zn*={xZn|gcd(x,n)=1},(·)表示Euler函数。定理2设p和q是两个不同的素数，n=pq,，对任意的xZn及任意的非负整数k,有.现在来证明RSA算法的加密变换和解密变换的正确性。证明：对于加密变换Ek和解密变换Dk。因为，所以可设,t是整数且t1。对于任意的xZn，有(xb)a=.因此解密过程是正确的。3.2.2RSA系统的参数选择若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度位512比特位.至1996年，建议使用768位的模n。为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同(2)p-1和q-1分别含有大素因子和(3)-1和-1分别含有大素因子和(4)p+1和q+1分别含有大素因子和为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e＝216＋1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。e＝216＋1优于e＝3之处在于它能够抵抗对RSA的小加密指数攻击。[9]3.2.3举例说明为了说明该算法的工作过程,我们下面给出一个简单例子,显然我们在这只能取很小的数字，但是如上所述，为了保证安全，在实际应用上我们所用的数字要大的多得多。例：选取p=7,q=17，则n=119，。选取（大于p和q的质数），gcd(e,φ(n))=1,通过d*5=1mod96，计算出。假定明文为整数p=19。则密文C为复原明文P为：3.3基于RSA体制的盲签名体制3.3.1盲签名盲签名最早由DavidChaum于1983年提出的。盲签名在数字现金、电子投票以及军事等领域有着较大的应用，特别是目前的数字现金，大部分是采用盲签名的原理实现的。盲签名的基本思想是：求签名者把明文m作盲变换b(m),b(m)隐藏了m的内容；然后把b(m)给签字者（仲裁者）签名得到s[b(m)],然后求签名者把s[b(m)]通过逆向的盲变换取得签名s(m)。。3.3.2完全盲签名协议A请求B签署一个文件，而且完全不想让B知道文件的内容是什么，只想在以后需要时B可以对他的文件进行仲裁，这就用到了完全盲签名协议。具体实现如下：(1)A把文件用一个随机数乘之，得到一个盲变换后的文件，该随机数称为盲因子。(2)B对上面产生的盲文件进行签名，此时B完全不知道文件的内容。(3)A取到签名后的盲文件，在除以盲变换时所用的那个盲因子得到B对原文件的签名。上面就是完全盲签名的过程，这显然也有些问题，比如A别有用心的让B签署一个有害的文件，而B在签名的时候完全不知情，这样的后果是可想而知的。看来有时候让B知道要签署的文件的大概的信息是有必要的，只就是下面要提到的盲签名协议。3.3.3盲签名协议使用分割-选择(Cut-and-Choose)技术，可以使签名者B知道他签署的是那方面的信息，但是还保留盲签名的特征——他不知道所签署文件的具体内容。下面举个例子来说明。例反间谍组织的成员的身份必须保密，就连他们的领导头子都不知道他们具体的名字，现在需要领导B签署一份文件，内容是“A具持此文件具有外交豁免权”，而A这个人有10个不同的名字，这份文件使用哪个名字是无所谓的，B不全知道他的名字就不会泄密。于是他准备了10份这样的文件，每个文件使用不同的名字。A将这10份文件分别用不同的盲因子盲变换后通过某种方式安全的交给B，B随机选出其中的9份文件，索要他们的盲因子来查看文件的内容，于是B明白了要签署文件的大概内容。B在对剩下的那份文件签名，于是A顺利取得签名。在上面的那个协议中，如果A想让B签署一份“A可以每年领到100万工资”的文件，那么成功率只有1/9，这个险不是很好冒的[10]。3.3.4基于RSA算法的盲签名D.Chaum曾提出第一个盲签名的概念，并设计了计入RSA签名体制的盲签名方案。下面为了叙述方便，用m代表待签署的消息，Bob代表签名者，Alice代表签名的接受者。RSA盲签名由以下几个部分组成： (一)初始化阶段(1)Bob随机选取两个大素数p，q，计算n=p*q，=(p-1)*(q-1)(2)Bob随机选取一个大整数e，使得(e,)=1.(3)Bob用扩展Euclidean算法计算d，使之满足ed≡1mod（），即d≡(1/e)mod().(e,n)是Bob的公开密钥，d为Bob的私钥，两个大素数p，q由Bob秘密保存(二)签名阶段(1)Alice选择待签名消息m，随机数r是整数。计算m1=m*remodn将m1发给Bob(2)Bob计算s1=(m1)dmodn,将s1发给Alice(三)脱盲阶段 Alice计算s=s1r-1modn,s就是签名(四)验证阶段判断验证等式m=(s)emodn是否成立，由此可确定签名是否有效。RSA签名体制的安全依赖分解大数的困难性。分解n是常用的攻击方法，攻击者只要能分解n，求出签名者的私钥是轻而易举的事，因此，n的取值要尽可能大些。另外，为了防止攻击者的穷举攻击，可以有效防止攻击者迭代逐一测试攻击。

4基于RSA盲签名的设计与实现4.1实验环境选择VisualC++6.0是运行于Windows98/NT/2000/XP环境下的可视化编程工具中最重要的软件开发工具之一，它把Windows统一直观的界面风格和面向对象的编程技术结合在一起，形成一个功能强大的集成开发环境，提供了简单高效的操作方式、高效的内存管理、与设备无关的图形接口、数据共享和多任务运行机制，同时又提供了一系列功能强大的开发工具。这一切使得VisualC++在Windows应用程序开发方面具有极强的优势，因此使用VisualC++6.0开发平台对本程序进行开发。4.2盲签名算法的详细设计盲签名实现，首先随机生成两个大素数，计算出公钥和密钥。然后随机生成一个明文，并对明文进行盲化。然后，用密钥对盲化的文件进行签名。最后用公钥进行盲签名验证。4.2.1生成公钥和私钥本文通过先随机产生大整数，然后利用Fermat素性检验来判断大整数为素数的概率。具体实现中，通过4次检测以增加素性的概率。随机生成两个大素数后，根据n=(p-1)*(q-1)计算出n的值，然后随机选取e，根据n和e计算出d的值。生成公钥和密钥的设计流程图，如图1。开始开始随机产生大整数利用Fermat素性检验进行检测检验通过？p，q都已产生？根据p,q计算出n的值随机选择e，并根据n计算出d值结束NYNY图1RSA密钥对的生成流程图4.2.2盲签名的过程盲签名的过程，首先产生随机一个盲因子r，然后利用r对明文进行盲化，最后用私钥d对盲化后的内容进行盲签名。盲签名的具体设计流程图，如图2。开始开始随机产生一个明文mtext随机产生一个盲因子r利用r对明文进行盲化得到mtext1利用私钥d对mtext1进行盲签名,得到mtext2结束图2盲签名过程流程图4.2.3盲签名的验证过程盲签名的验证过程，首先利用扩展欧几里德算法求盲因子r的逆元r1。然后，利用r1对签名内容进行脱盲。最后，利用公钥e计算签名验证的值并与原来的明文进行比较。盲签名的验证过程流程图如图3。开始开始利用扩展欧几里德算法，求盲因子r的逆元r1利用r1对签名内容mtext2进行脱盲利用r1对签名内容mtext2进行脱盲,得到mtext3利用公钥e计算验证签名的值mtext4mtext4与原文mtext是否相等？NY验证成功验证失败结束图3盲签名验证流程图4.3数据结构定义structslink{ intbignum[100];/*bignum[98]用来标记正负号，1正，0负bignum[99]来标记实际长度*/};4.4主要算法的实现盲签名算法的实现首先要实现随机产生大素数的算法，大整数的基本运算，运用欧几里德求大整数的逆元。在此基础上，实现盲签名的算法，并进行验证。4.4.1随机产生大素数本文主要利用Fermat素性检测法，检测生成的大整数是否为素数。大整数p对于基b的拟素数，当且仅当b模p的指数整除p-1，即bp-1=1(modp).对于b，本文分别选取2，3，5，7进行检测，以增加p是素数的可能性。经过四次检测，p是素数的可能性大于1-1/24。检查整数素性的具体的实现如图4。图4Fermat素性检验4.4.2大整数的基本运算为了实现盲签名算法的运算，大整数需要实现的基本运算有四则运算，模运算，模乘运算，和幂模运算。首先定义一个大小为100的数组存储大整数，然后根据整数的算术基本原则来实现。模乘和幂模在大整数基本运算的基础上，利用同余的基本性质进行实现[11][12][13][14][15]。具体的实现函数，加法：add(inta1[MAX],inta2[MAX],int*c)//c=a1+a2减法：sub(inta1[MAX],inta2[MAX],int*c)//c=a1-a2乘法：mul(inta1[MAX],inta2[MAX],int*c)//c=a1*a2除法：divt(intt[MAX],intb[MAX],int*c,int*w)//c=a/b,w=amodb模运算：mod(inta[MAX],intb[MAX],int*c)//c=amodb模乘：mulmod(inta[MAX],intb[MAX],intn[MAX],int*m)//m=a*bmodn幂模：expmod(inta[MAX],intp[MAX],intn[MAX],int*m)//m=apmodn4.4.3求大整数的逆元求逆元是本文的一个重点和难点。本文利用扩展欧几里德原理来求整数的逆元。现假设已知d，m，求e，使得edmodm≡1。即是求d对m的逆元e。利用扩展欧几里德求解x，y使得gcd(d,m)=dx+my。x就是所要求的e。具体的实现如图5。图5乘法逆元的求解4.5实现效果及分析整个过程的实现效果图，如图6图6整个过程的实现效果图以下对实现的效果进行具体的分析。4.5.1盲签名的实现效果(1)RSA密钥对的产生，随机生成两个大素数p和q，由p,q计算得出n，n=p*q,再随机生成一个与（p-1）*（q-1）互素的公钥e，然后根据欧几里德算法求出私钥d，具体实现效果如图7：图7生成rsa密钥对(2)密钥对生成完成以后，随机生成一个大整数类型的明文，实现效果如图8图8随机产生明文(3)对明文进行盲签名操作，首先生成一个大整数类型的盲因子r，然后用此盲因子对明文进行盲化，盲化以后用私钥d对其进行签名，具体实现效果如图9：图9明文的盲化和签名4.5.2盲签名验证的实现效果(1)用扩展欧几里德算法求盲因子r对n的逆元，具体实现效果如图10：图10逆元的求解(2)对忙签名后的内容进行脱盲得到签名，具体实现效果如图11：图11签名的脱盲(3)利用公钥e对签名进行验证计算，然后与原始明文比较，如果相同则验证成功，反之，则失败，具体实现效果如图12：图12盲签名的验证

5结束语随着社会信息化的不断发展，特别是计算机及其网络在社会生活的各个领域得以普遍应用，人们对信息安全要求越来越强烈。密码技术是一项可防止信息泄露和篡改的技术，它是维护信息保密性、完整性和可靠性的重要手段。本课题研究主要是用c语言实现基于rsa的盲签名并对其进行验证，首先是RSA密钥对的生成，然后对随机生成的明文进行盲化和签名。签名过程完成以后对此签名进行验证，验证盲签名是否正确。本论文在研究网络信息安全技术的基础上，深入研究了RSA公钥密码算法原理，讨论了该算法的安全性，研究了其实现过程，并且研究了基于RSA算法的盲签名及其实现。RSA公钥密码算法实现的关键问题是加解密运算中涉及大量计算问题，计算开销大，加解密运算时间长，其核心运算是大数模乘运算和乘法逆元计算以及大素数的生成。本文在生成大素数的时候采用了Fermat素性检验法来快速生成大素数，在实现了大整数基本运算的前提下利用同余性质实现大整数的模乘运算，利用扩展欧几里德算法来实现逆元的求解。希望论文的工作能对RSA公钥密码算法的研究和实际应用、对大整数模乘算法的研究和实现，对我国自主开发信息安全产品做出一些贡献。致谢本论文是在我的导师郭艾侠老师的亲切关怀和悉心指导下完成的。她严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。从课题的选择到项目的最终完成，郭老师都始终给予我细心的指导和不懈的支持，感谢郭老师。感谢四年来一直栽培我的各位老师，他们循循善诱的教导和不拘一格的思路给予我无尽的启迪。他们的辛勤教诲，使我学到了丰富的专业知识和为人处世之道，提高了我的自学能力以及分析问题和解决问题的能力。感谢我身边的同学和朋友，他们在我的生活上和学习上都给了我莫大的支持，不厌其烦的指出我的错误，同时总能在我迷惘时为我解惑。感谢审阅本文的老师，感谢你们在百忙之中抽出宝贵时间来审阅本文，并期待你们的批评指正。最后，衷心地感谢我挚爱的父母，多年来他们一直在默默地支持着我，在生活上对我悉心照顾，在学习上给予我支持和鼓励，他们的支持是我最大的动力。

参考文献[1]汪旦华.盲签名及其应用研究.信息技术,2005,(2):35-38[2]李天增，王瑜.RSA密码体制的安全性分析和算法实现.四川理工学院学报,2009,22(1):41-43[3]李萍，张建中.基于RSA密码体制的盲签名方案.信息与通信保密,2006,(9):121-122[4]王英.RSA算法中大素数的快速生成方法.湖南科技学院学报年,2005,26(5):14-16[5]刘少涛，凌捷.数据加密算法与大素数的生成.广东工业大学学报,2001,18(4):25-29[6]陈晓文，郑建德.新型大素数快速并行搜索策略.厦门大学学报2008，47，(2):21-25[7]李力，周升力，郑超美.RSA密码的一种快速实现算法.南昌大学学报理科版,2008,32(5):498-500[8]LiPing，ZhangJianzhong.UntraceableBlindSignatureSchemeBasedontheRSA.CryptosystemChinaInformationSecurity,2006,(9):121-122[9]Lili,ZHOUShengli,ZhengChaomei.AFastImplementationofRSAEncryptionAlgorithm.JOURNALOFNANCHANGUNIVERSITY,2008,32(5):498-500[10]Zhanglei,ZhangFutai.CERTIFICATELESSSIGNATUREANDBLINDSIGNATURE.JOURNALOFELECTRONICS,2007,25(5):629-635[11]王岩，周亮.大整数模运算的软件实现方案.信息安全与通信保密,2005,(2):150-151[12]刘宇东.基于数组的大整数的运算与实现.计算机与现代化,2008,(3):20-22[13]周天宏.大整数的计算.郧阳师范高等专科学校学报,1992,33(1):75-82[14]曾联明.用C语言链表解决大整数运算的精度问题.电脑学习,2002,(3):31[15]石研,姚晟.大整数算术运算的实现.安庆师范学院学报(自然科学版),2004,10(2):75-78

英文摘要UntraceableBlindSignatureSchemeBasedontheRSACryptosystemWangYongliang（CollegeofInformatics,SouthChinaAgriculturalUniversityGuangzhou510642,China）AbstractBlindsignatureisthesignaturedidnotknowwhosignedthedocumentorthespecificcontentofnewsanddocumentsorinformationtheownercanbeblindfromthesignatoryonthedocumentsorinformationafterthesignaturetobesignatoryonthedocumentsorinformationtherealsignature.Blindsignatureinformationtoallowblindpersonsofthenewsfirstandthenallowtheblindsignaturetothesignatureofthemessage,thelastmessageoftheownertoremovetheblindsignaturefactor,tobethesigner'ssignatureontheoriginalmessage.Blindsignaturecanbesignedbytheeffectiveprotectionofthespecificcontentofmessages,soine-commerceande-electionsinareassuchasshareawiderangeofapplications.

Inthispaper,aresearchnetworkininformationsecuritytechnology,basedonin-depthstudyoftheRSAalgorithmisbasedonblindsignaturesystem,andsimpletoachievevc++6.0-basedblindsignaturesystemplatform.Simplesystemtosimulatetheprocessofblindsignatureofthevariousstepsoftherealizationofar