基于rsa的分布式密钥托管算法研究--大学毕业设计论文.doc

摘要
随着国内电子政务、电子商务和计算机技术的快速发展,计算机成为信息加工、信息传递、信息保存的主要工具,互联网则成为信息获取和信息发布的重要渠道,信息传播及扩散的速度得到了极大的提升。信息安全问题也越来越得到国家、机构、个人的重视,对敏感信息进行加密处理是信息保护的主要手段。为电子政务和电子商务起到信息安全保护的公钥设施越来越受到关注，而这些公钥基础设施在运行和正常工作的进行中,也有很大几率沦为不法分子的犯罪工具。为了降低这种风险,人们引出了密钥托管的概念。在多种密钥托管方案的算法实现上，RSA密码算法以良好的安全性，易实现性和易懂性而被广泛应用。
RSA算法是目前使用最广泛的一种密码体制，也是一种公钥密码体制。但由于RSA算法的破解困难性是基于大素数分解，因此基于防止各种各样的破解、攻击,RSA算法的大整数模长在不断的增长，同时，RSA算法的大部分数学运算都是基于大整数的模幂和模乘,因此RSA算法的运行速度较慢成为了RSA算法的一个显著特点。另外随着各种各样的攻击手段的多样化,RSA算法在安全性上也受到了极大的冲击。RSA密码体制在理论上来说是非常安全的,但是，由于在实际应用过程中,具体的每一个RSA密码系统都是不一样的,每一个系统的详细设计都有着自己的不同要求,或是对速度的要求,或是对安全性的要求。要求不同，系统设置也就不一样。
标准的RSA算法的加密操作指令流和解密操作指令流很难被分解为多个活动序列,从而达到并列开发的目的。对RSA算法进行的完善改造操作， 在加密过程中要进行bxk+l次模幂操作，而在解密过程中要进行bxk次模幂操作。通过这样的改进，RSA算法的操作方式被规范化，即将RSA算法模幂操作分步进行，减少模幂位数，提高了RSA算法的解密机动性。同时对RSA算法加密和解密过程所使用的单个命令流加以规范，是的RSA算法加密方和解密更能快速的进行，进而提高RSA密码的适用性。RSA密码加密模式中各个加密操作和解密操作的数据载入都是互不相关的，由此，数据载入的相互独立为数据活动分解打下了基础，从而让数据单元进行的加密与解密的分别进行提供可能。
本论文的研究目标是为提升RSA密码算法解密性能做出贡献，通过针对分布式密钥托管方案中的多素数RSA算法在进行解密和数字签名时需要进行多次大数的模幂、模乘运算,特别当RSA密钥强度较高时,性能受限尤为突出等问题，从RSA密码算法的数学基础出发，研究分析改进的多素数RSA算法——EAMRSA算法，旨在提高分布式密钥托管方案中多素数RSA算法的解密性能，进一步保障信息安全性。
关键词:密钥托管；公钥密码体制;多素数RSA密码体制;EAMRSA算法；解密性能

第一章绪论
1.1研究背景
21世纪是信息化的时代，信息已成为了一种非常重要的国家战略资源,信息的获取、处理以及安全保障能力成为一个国家综合国力的重要组成部分。信息安全离不开密码学，而秘钥安全是密码学研究的一个重要组成部分。密钥托管研究为解决这个问题应运而生。密钥托管可以这样简单地理解，将客户的密钥托付给合法的第三方进行合法托管,为让其便于利用得到的密钥以及解密双方通信的内容,以达到通信双方监视监管的目的。以此所述,合法的第三方的为政府部门以及法律执行部门等。密钥托管为之一个最简单简洁的方法就是由一个(或多个)可信认的国家政府相关代理机构为个人以及保管密钥。密钥托管的研究领域非常广范,但首先必须要解决的问题却是密钥的安全托管问题。即在用户使用过程中密钥的丢失或损坏,或者在用户需要密钥而拿不到时,执行掌管密钥托管系统中的密钥恢复功能,可以安全有效的得到用户所需要的密钥或者相关信息。
目前有关于密钥托管的算法应用非常之多，其中公钥密码体制是目前一种国际上公认的较为理想的密码体制。在信息安全体系运用中,算法选择方面一般都会采用公开形式的密码算法标准,公开形式的密码算法标准的安全性已经是经过了较长时间的论证与考验。。也同样是目前网络上进行保密通讯最为之有效的安全算法。RSA算法是基于数论中的大素数分解的难解问题[1],RSA的密码体制也是是采用的足够大的整数作为模数。基本理论是靠因子分解越困难,密码就较之越难以破解,当然同时加密安全度也就相对越高 [2]。目前由于计算机分解大整数的能力表现为日益增强,因此为了保证RSA密码算法的安全性就相对应要增加模长。同时大整数的分解问题运用了大量的模乘以及模幂运算而在数学运算中这两种运算方式的时间都相对比较长,因此RSA的密码体制有较为显著的缺点那就是运算效率低下,运算时间过长等缺点。另外，RSA的密码算法模数位数的变大,需要进行更大位数的模幂运算,也耗费更多的计算时间以及资源,限制了RSA密码算法的性能。总之,关于快速有效实现RSA密码算法的研究对于提升当前密钥托管的服务质量以及用于保障信息安全都有之非常重要的理论意义以及实用价值。
1.2国内外研究现状
1.2.1密钥托管研究现状
RSA公钥密码体制是在20世纪70年代由LenAdleman，、Adi Shamirh 和Ron Rivest在(美国著名理工类学院麻省理工学院)提出来的。RSA所代表的就是取这三位作者的名字的首写字母的得来的。RSA密码算法目前仍旧是世界上很有影响力的公钥加密体制,自RSA密码体制提出以来,最为经典的密钥托管方案主要有几下几种：
完全密钥托管的方案。这样密钥对于完全交由相关密钥管理中心进行控制,而用户则只是被动的进行提交密钥服务的申请。这种方法的一个突出优点就是运算起来比较容易操作，也很容易就可以实现。但是完全密钥托管的方案也存在一些不足之处，它无法防止一些机构对提交密钥服务的权力作为一些另外的用途。
有人提出了可验证的密钥托管方案[3,4,5]，就是为了使用户亲自能够参与密钥产生的过程,在该方案中,用户是负责产生私钥的,密钥的托管机构确实用于负责托管。为了托管的安全,那么该托管方案就仅仅吸收了部分对称密钥托管中的密钥托管的思想。那么这种私钥分割的方法是密钥托管方式上一个的巨大进步。
在改进可验证密钥托管方案中和门限密钥的托管方案的基础上，人们又再次提出分布式的密钥托管方案[2009论文]，他的基本思想就是,各密钥托管机构只仅仅负责托管用户公钥N的安全素数的分解因子。
1.2.2 RSA算法研究现状
在以上这些托管方案当中，应用最多的就是基于公钥安全的RSA算法。前面章节已经提到密钥的安全性是一个系统安全的关键所在,纵然在安全密钥的存储技术方面已经有了很多的技术来为密钥的安全存储提供技术保障,但是在系统的实际应用过程中仍然存在着很多的不当之处,如果在实际应用中采用了不合理的密钥存储方式和分析算法,那么不仅会使密钥的安全性受到威胁,而且很有可能会成为极大的系统漏洞,这会给系统带来潜在威胁，安全应用遭到挑战。在安全系统应用中，算法选择有很多种，要从根本上解决密钥存储安全的问题,不仅要选择适当的安全密钥存储技术,更要有合适的算法加固系统安全。1978 年 Ron Rivest 和 Adi Shamir 以及 Leonard Adleman 提出来的 RSA密码体制到目前来说一直被认为是一种安全实用性很高的密码体制【11，12】。对各种如何实现RSA密码算法自身效率提高的研究目前有下面四种策略：第一种策略为不废除标准RSA密码算法本身的模式,对RSA密码运行中算法和运作进行了完善，如改善模乘、模加的算法。第二种策略为对RSA算法本身运作模式进行改善,以实现提升RSA密码算法工作效率的任务。第三种策略是对RSA密码算法硬件进行升级,以达到从本质上提高运算效率的目标。第四种策略是RSA算法的并行运作,通过并行运作的模式来实现RSA密码算法的效率提升。
针对与第一种策略,国内的学者还提出了一些可行的方案。如1997年, 柳青等学者文献〔14〕提出了基于乘同余对称特性的快速RSA改进的算法。2000年,文献「15〕提出了关于二进制冗余数的递归余数算法,以通过减少运算迭代步数,来使RSA密码体制的速度实现进一步加快,但是该算法是要事先建立起来余数表,仅适用于对长明文来加密。2001年,文献「16」将指数。 2006年,文献「17」利用计算近似最短加法链的算法来给出了软件的实现RSA密码算法模幂运算的一种改进方法。文献「18」采用一种有效的滑动窗口法进而来实现模幂运算,并且通过Montgomery算法来实现快速RSA算法。
对于第二种加速RSA密码算法的方法是改进标准RSA密码算法自身结构。目前,国内外已经有多种相关通过对RSA密码算法自身结构进行改进来提升RSA密码算法解密性能的改进算法。多素数RSA算法(Multi一PrimeRSA )就是其中之一。多素数RSA算法是由文献「19]提出的,它是将标准的RSA算法大数模N的结构由N=pq改变成为其中的pi为i个不同的素数。然后再通过与中国剩余定理[20]来相结合,从而来使得RSA密码的算法在解密时大数模幂运算的模幂指数与大数模的位数进行变小,对RSA密码算法解密的过程进行加速。多素数RSA改进算法和中国剩余定理结合之后,将会使得RSA算法解密时的大数模幂运算的模和指数的位数都会变小,进而来提升了RSA密码算法的执行效率。
对于第三种就是用于通过硬件来实现加速RSA密码的算法。2009年,文献「23」给出一种用于支持多种位数的RSA密码算法加密芯片的完整的设计方案。此方案不仅减少了硬件的使用量,而且可以实现高效率的运算能力。但与前两种方案相比，利用硬件的升级来提高RSA密码算法效率成本要更高。
所谓并行运作策略主要是通过RSA密码算法的模幂或模乘运算的改变来实现同步进行，从而达到优化处理的目的。文献〔24〕提出了一种使用冗余系统的并行模乘的算法。文献「25」和「26]中对RSA密码算法的模幂运算来进行了并行以实现其优化。文献[27]通过使用openMP以及MPI对RSA密码算法进行了并行优化。以上文献针对RSA密码算法的并行运作方案的研究,虽然都能实现优化的目的，但其效果都不太明显,并且操作起来有一定的难度。
从全球各地学者就RSA密码算法的研究现状来看,已经成功研究得出了多种能使RSA密码算法提升效率的解密方法,只是效果大都不尽人意。为了保证当前密钥托管系统的高效性以及未来信息安全服务的高安全性和高质量,必须进一步来提升RSA密码算法的解密和数字签名的性能。RSA密码算法的安全性是完全依赖于大素数因子分解的数学难解问题。多素数RSA密码体制存在很多优点，首先，采用中国剩余定力进行签名，速度与标准RSA算法相比，快了很多；其次，多素数RSA算法采用多个素因子乘积，更有利于抵抗wiener攻击。所以，多素数RSA密码体制其安全性更高。RSA的密码算法模数位数的变大,需要进行更大位数的模幂运算,也耗费更多的计算时间以及资源,限制了RSA密码算法的性能。总之,关于快速有效实现RSA密码算法的研究对于提升当前密钥托管的服务质量以及用于保障信息安全都有之非常重要的理论意义以及实用价值。分布式密钥托管方案中的多素数RSA算法在进行解密和数字签名时需要进行多次大数的模幂、模乘运算,特别当RSA密钥强度较高时,性能受限尤为突出的问题，本论文从RSA密码算法的数学基础出发，研究分析改进的多素数RSA算法——EAMRSA算法，旨在提高分布式密钥托管方案中多素数RSA算法的解密性能，进一步保障信息安全性。虽然在理论研究方面我们基本能够跟上国际水平脚步,但对于信息安全技术来说,在技术和产品实现方面还要依赖其它的技术,如集成电路等,在这些方面我们欠缺更多。
1.3 论文的主要内容和创新点
本文是在介绍密钥托管理论的基础上，分析了几种有关通过改变标准RSA密码算法自身的结构以及对RSA密码算法来进行并行优化用于实现RSA密码算法的解密性能优化方案，着力点在于密钥管理系统的优化和信息安全的保障。主要内容包括以下几点：
1 分析并介绍了相关几种密钥托管方案、主要思想和意义,进而分析了国内外的密钥管理应用的情况和相关国内外的理论研究成果。
2 针对目前现有密钥托管方案中基于公钥安全的RSA算法进行相关研究，分析RSA改进的算法提升效率的本质以及不足之处。
3 从影响RSA密码算法解密性能的最主要因素进行入手,针对标准RSA算法来改进算法Multi一PrimeRSA算法在分布式密钥托管方案中的运用，进一步进行优化，以实现提高解密性能
1.4 论文的组织结构
第一章绪论：介绍了本文的研究背景及意义、国内外对此研究的现状、主要工作、论文的特色以及创新点。
第二章预备知识：本章主要介绍了与密钥托管以及RSA算法相关的知识。其中主要包括了公钥密码体制的相关知识、RSA算法及其改进算法的相关数学的基础，为后文的论证方案的正确性打下理论基础。
第三章几种密钥托管方案进行相关研究并主要针对方案RSA算法及其改进算法进行的分析，总结改进算法提升效率的本质,以及发现当中存在的不足。
第四章对于分布式密钥托管方案中的多素数RSA（Multi一PrimeRSA）算法进行有关研究和分析，并对该算法提出改进，进而进一步提高解密的性能。
第五章从密码算法的内容、安全性、理论加速对比分析以及解密过程正确性几个方面对改进算法进行相关研究和分析。
第六章总结与展望。本章节主要是从一些相关理论出发，结合一些相关的参考文献，总结了一下文章的主要内容，对目前国内外的研究现状和研究前景进行了描述和展望，同时提出一些目前所存在的一些不足之处，进而提出一些改进的方案，以更好地为相关的研究提供理论上的借鉴。
第二章 预备知识
2．1数论基础
2.1.1素数
一个大于1的整数,如果它的整因数只有1和它本身,这个数就是个素数(称为质数),反之则是合数。例如:2、3、5、7等等都是素数。
2.1.2最大公因数和最小公倍数
设是个不全为零的整数。若整数d是它们之中每一个的因数,那么d就叫做的一个公因数。这时,这些整数的公因数的个数是有限的。整数的所有公因数的最大的一个就是它们的最大公因数,记作（）也可记作
例如(4,8) =4, (12, 36)=12
设a1,a2….an是n个整数(n>2),若m是这个n个整数中每一个数的倍数,则m就叫做这n个整数的一个公倍数。在a1,a2…..an的一切公倍数中最小的正数叫做最小公倍数,记作[ai,a2, 。
例如:[2,3, 5] =30, [7,9] =63.
2.1.3同余式
同余:假设一个正整数m,如果用m去除两个整数a和b后计算结果的余数一样,我们就说a,b对模数m同余,记作.如果余数不一样,我们就说a,b对模数m不同余,记作
。
剩余类:设m是一个给定的正整数,Cr(r = 0,1,….m - 1)表示所有形如qm + r的整数组成的集,其中q = 0,±1,±2,...,则叫做模数m的剩余类。
完全剩余系:在模数m的剩余类中各取一数此m个数a。,a1,,,,,am-1称为模数m的一组完全剩余式。
模运算:amodm表示计算a被n除的余数,这种运算称为模运算。
2.1.4单项函数和单项限门函数
公钥密码理论的数学基础就是单项陷门函数。
单项函数。例如:有函数f(x) = aX,根据我们己经掌握的数学知识我们知道给定任意的一个X,计算aX都是容易的,因为我们完全可以将此公式转化成我们已经学习过的X个a相乘的方式。然而对于给定的任意y,计算X使得f（x） = y这样的计算至今还没有发现一个有效的计算logay的计算方法。所以我们可以把f(x) = aX看做是一个单项函数。
定义2:陷门单项函数。在公明密码体制中,加密变换本身就是一个陷门单项函数,如果知道陷门就可以很容易的进行解密变换,如果不知道陷门则很难进行解密变换从而保证的信息的安全性。
2.1.5 Euler函数，Euler定理和Fermat定理
定义1:欧拉函数(n)是一个定义在正整数集上的函数,0(n)的值等于序列0,1,2,…,n-1中与n互素的数的个数。
从上面定义可得0(1) = 1,0(2) = 1,0(3) = 2,...。当P是素数时,0(p)=p — 1。
Euler定理:设X和n都是正整数。如果gcd(x,n)=l,则

Fermat定理:设x和p都是正整数。如果p是素数,则

2.1.6乘法逆元及其求法
定义:若ab = l(modn;),则称b为a在模n的乘法逆元,b的结果可以表示
求乘法逆元主要利用欧几里得和辗转相除法来进行计算。给出求逆元的过程:以及a和b并且(a, n) = 1,求欧几里得给出了一种计算最大公约数的算法,如果(a,n) = 1,则可以判定b —定存在。下面是欧几里得求gcd(a, n)的方法:
mm就是a和n的最大公因子。
2.1.7素数检测
素数是数学中最重要、最基本的概念之一,人们一直对素数的研究及其的关注。在很多密码系统中,都具有举足轻重的地位，同时也是数论主要研究的主要对象之一。但是,如何得到素数,尤其是大素数呢，公元前250年由古希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法埃拉托斯特尼筛法。然而在历史的长河中人们不断的在寻找一个万能公式，它适用于所有素数，并能由它直接生成素数。然而两千多年来，尽管数学家及数学爱好者们从来没有放弃对这样一个公式的寻找，可遗憾的是,到目前为止,仍没有找到。
2.2公钥密码体制研究
我们都知道，密码学(cryptology)[29]是研究密码系统与通信安全的科学，现代密码的基石是信息安全技术,目标是为了保护信息的完整性、机密性、认证证性和不可抵赖性提供技术上的支持。其密码体制表示如下图所示:

密码体制示意图（图片来源【30】）
早期的密钥体制中，加解密算法是保密的,不需要密钥,也就是是说,密文的不可识别性是通过算法的保密性来实现的,这种形式灵活性差。现代密码体制中，密码算法都是公开的,密文的不可识别性是通过密钥保密实现的,加密算法和解密算法的操作通常都是在一组密钥的控制下进行,密钥是密码体制安全保密的关键。如果在一个密码算法中，加密密钥和解密密钥是一样的,或者虽然不一样,但是由其中的一个可以很容易地推导出来另一个,则称之为对称密码算法。对称密码算法的优点主要有一下几点：可以经受较高级破译力量的分析和攻击、具有很高的保密强度、可以经受较高级破译力量的分析和攻击、能够在处理能力受限的环境下实现、运算速度和处理效率高。与此同时，对称密码算法也同样存在很多问题:首先,对称密码算法面临着密钥管理的难题。现代网络中,如果某一个节点需要和n个节点进行通信,那么它就要维护n个专用密钥。其次,对称密码算法一个固有的问题是对处理不可抵赖有着先天性的不足，即无法实现鉴别。常见的对称密码算法有DES、IDEA、AES等。同样的，如果一个密码算法的加密密钥和解密密钥不相同,并且不可能由其中一个推导出另外一个,解密密钥则秘密保存,通常把公开的加密密钥称为公钥,秘密保存的解密密钥称为私钥。非对称密码算法的问题:在处理能力受限的环境中实现较难系统的安全保障在于从公钥和密文C推出明文或私钥在计算上是不可行的。非对称密码算法的优点:密钥管理问题相对简单、可以方便、安全地实现数字签名和验证、从而有效实现不可抵赖性的安全目标。。常见的非对称密码算法有RSA、背包、Rabin、EIGamal、ECC等。
在公钥密码体制中,加密和解密使用不同的密钥,对于每一个（代表明文空间),存在（代表明文空间),这两个密钥是不同的并且互相匹配。
1978年由 Ron Rivest 和 Adi Shamir 以及 Leonard Adleman 提出来的 RSA密码体制到现在一直被认为是一种安全性能很高的密码体制。因为R S A密码算法的安全性是完全依赖于大素数因子分解的数学难解问题[31]。在公开密钥(e,N)中,如果N能被因子解,那么模N中所有元素阶的最小公倍数0(N) = (p-l)(q - 1)即无从隐藏。这样解密密朗就可以求出,从而整个RSA公钥密码系统就不安全了。学术界现在还无法证明破解RSA公钥密码系统等于因子分解,但现在我们公认RSA公钥密码系统的安全性等价于因子分解。为了保证RSA算法的安全性,对于RSA密码体制的所有的参数选择都要认真研宄。在使用RSA公钥密码系统时,对于参数N的选择,都要使无法从N得到C，对于e和d的选择也是有所要求的。
在N的选择上，p和q必须是强素数；要求p与q的差值很大一般要求差好几个数量级；另外，p与q还应该过选择比较大的数，使得在现有条件下分解N在计算上是不可能的。在e的选择上，首先不可以太小，在RSA系统中，很多人为了提高系统的运行速度，一般建议e选择比较小的数，一般是3。可是实际上，如果这样，会使系统比较容易遭受低指数攻击，给系统带来安全隐患。关于d的选择，同样也要考虑安全性和运行速度两个方面的因素。具体说来，如果d很长，则会大大影响系统的运行速度。相反，如果d太小，则通过铭文M的加密变换来猜测d的话，会使猜测空间变小，d被猜出来的几率很高。
2.2.1 RSA 算法
关于RSA算法算法描述：
首先，密钥生成阶段
为了生成用户的基本参数,执行以下的步骤:
(1)首先输入安全参数（是大数模的位数），随机选择两个素数和，位长都是，满足；
(2)计算；
(3)计算；
(4)随机选择整数，使e满足条件并通过关系式
计算得到；
(5)用户把()公共，作为用户公钥,不再需要，应该并且安全的销毁和，不让任何人知道，用户自己保留作为私钥。
公钥密码体制中，用户用RSA公钥密码体制加密的时候,需要先将明文信息进行数字化处理,然后在对处理过的明文信息进行分组,并且要求分组的长度满足条件，
最后再对分组单独进行加密和解密处理。
加密过程
加密明文信息时，为了秘密的将明文安全无误的发送给用户,发送者要把铭文进行
处理得到密文。
解密过程
用户得到密文后，对密文进行
的处理，得到明文。
算法过程中，由于N和d的位长接近安全参数n，都是非常大的数。因此对于解密方来说,解密过程计算复杂度高，是一个较为耗费时间的过程。最后还要对加密方的加密过程进行逆向操作,将大数M格式转化为比特串X。再次过程中必须要求d必须是一个很大的数否则RSA会不安全[31,32]，容易被攻击。
2.2.2RSA密码体制的标准化
RSA密码体制的标准化在PKCS#1[33]标准中有比较详尽的描述。一个有效的RSA模数满足条件，它是一个由不同奇素数的积构成的。。
多素数RSA密码体制存在很多优点，首先，采用中国剩余定力进行签名，速度与标准RSA算法相比，快了很多；其次，多素数RSA算法采用多个素因子乘积，更有利于抵抗wiener攻击。所以，多素数RSA密码体制其安全性更高。
2.2.3　RSA算法安全性分析
RSA密码体制也都基于数学困难问题。这也是这些算法可以应用于密码学的最根本原因，总结起来，与RSA密码体制有关的困难问题有如下几个【35]。
RSA问题　　　输入　　　　
,其中p和q为素数;
:一个整数,满足，；
输出　　　唯一的整数,满足
；
整数分解问题(IF问题)　　输入N:奇合数,至少两个素因子;
输出　　素数p,满足ｐ｜N。
RSA密码体制提出来以后，很多专家、学者致力于RSA问题的研究，可是人们始终找不到一个快速的方法来攻击它，即便有些研究取得一些进展，但是理论上可行，实际计算上不可行。所以，可以知道，RSA密码体制理论上来说目前还是安全的。
２.３　中国剩余定理加速ＲＳＡ算法
RSA密码算法复杂的模幂运算模式，导致解密时所耗费的时间会比较长，文献〔36]借鉴中国剩余定理(定理2.4)的运作模式对RSA算法进行改善，促进了RSA算法的解密过程的快速完成,使得RSA算法的解密的效率在原有性能上提升了近4倍。中国剩余定理在RSA算法中的成功运用，使得RSA密码算法效率大为提高的同时，更是成为其算法的核心。定理2.4(中国剩余定理)在RSA算法解密过程中应用的步骤如下所示:首先设c是RsA加密得到的密文,p,q,是两个互为素数的整数，且N＝Pq。选取公钥ｅ,且与(p一l)(q一l)互素,求出来。为得到明文M，通过得。利用定理2.4加速RSA算法解密的过程如下所示:
(l)计算；
(2)求解
(3)计算方程组:，
(4)计算,进而可计算，其中,现对进行分析:由于,所以存在一个整数k,满足
,则有，可推出
根据定理2.3和同余定理[37]可以推出，则有

,最后得

,同理可得,

(5)通过

通过整理,可以得到结果。
2.4 零知识证明
零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。对高级密码协议的设计具有重大意义，当然零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。零知识证明协议可以用于证明用户的身份,即在不泄漏私钥的前提下证明用户具有私钥，证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息，零知识证明也可以用于证明用户具有有关某些秘密信息的知识。

第三章密钥托管技术中ＲＳＡ算法研究
本章将针对几种现有密钥托管方案进行相关研究，并在此基础上来分析分布式密钥托管方案中ＲＳＡ算法的实现。并对现有的一些通过改变RSA算法自身结构来加速RSA算法解密过程的改进算法进行研究，通过对改进算法的研究的方式，总结算法改进的本质以及可改进的地方。
3．1密钥管理研究
随着迅猛发展和日益成熟的信息技术,现代通信网络作为担负信息主要传输通道其规模也是在飞速增大,节点数量的庞大给密钥管理同样带来了新的挑战。集中分配式密钥管理需要在密钥申请方与密钥管理中心之间建立起一条网络或物理安全有效通道。所谓物理通道一般指依靠人工传递方式,花费较大,通常该方式是使用在国家、军事等要求安全性较高并且有能力负担的通信场合;而网络安全通道就是长期使用一个秘密密钥来对信道进行加密建立来实现的,这样要求中心与每个参与方都保持一个秘密密钥,但是随着参与方增多节点数目也随之增大,如何安全有效地保存这些庞大数量的秘密密钥就成为一个难题。
分布式密钥管理的概念来源于分布式系统【39】,常见的分布式系统包含分布式计算机系统、分布式操作系统、分布式计算机网络系统,而这些分布式系统的基本特征就是资源共享、协同计算,相比于集中式、分散式系统分布式系统具有可扩充性好,可靠性高等优点。分布式系统原理伴随着计算机网络结构逐渐显现分布式、开放性特征，也随之应用到密钥管理中,进而形成了分布式密钥管理的概念。
在国内外密钥管理技术的发展过程中,随着PKI的进步，对密钥管理也同样提出了新的要求。伴随着密码算法数量的增多、强度的增强,不法分子可以通过采用强有力的加密措施进行保密通信,是密码世界进入无政府状态。从而使国家、组织、个人受到威胁。为了达到保护用户隐私和监视和防止犯罪活动的双重目的，为更有效地保护政府和个人信息数据，防止密码学的这种无政府状态,密钥托管因此产生。
3.1.1密钥托管研究
密钥托管技术它是基于一系列的数学公式作为基础的，是在某些紧急的情况下用来获取所需要的解密信息的技术。他可以对用户的私钥备份进行保存，也可以在用户丢失或者把自己的密钥损坏的情况下可以进行自动回复。因此，他与一般的解密措施有着很大的区别的。在国外，某些国家就规定了不允许社会上将密系统普遍运用到市场上。密钥托管为之一个最简单简洁的方法就是由一个(或多个)可信认的国家政府相关代理机构为个人以及保管密钥。密钥托管的研究领域非常广范,但首先必须要解决的问题却是密钥的安全托管问题。即在用户使用过程中密钥的丢失或损坏,或者在用户需要密钥而拿不到时,执行掌管密钥托管系统中的密钥恢复功能,可以安全有效的得到用户所需要的密钥或者相关信息。
密钥托管可以这样简单地理解，将客户的密钥托付给合法的第三方进行合法托管,为让其便于利用得到的密钥以及解密双方通信的内容,以达到通信双方监视监管的目的。以此所述,合法的第三方的为政府部门以及法律执行部门等。密钥托管为之一个最简单简洁的方法就是由一个(或多个)可信认的国家政府相关代理机构为个人以及保管密钥。密钥托管的研究领域非常广范,但首先必须要解决的问题却是密钥的安全托管问题。密钥托管的算法应用非常之多，其中公钥密码体制是目前一种国际上公认的较为理想的密码体制。在信息安全体系运用中,算法选择方面一般都会采用公开形式的密码算法标准,公开形式的密码算法标准的安全性已经是经过了较长时间的论证与考验。
3.1.2 密钥托管方案分析
密钥托管过程中，托管机构的权力滥用问题和托管用户托管密钥真实性问题一直是托管技术需要攻克的两大难题。而密钥托管技术的发展却离不开托管机构与用户之间的坦诚相待，相互信任。
早期的密钥体制中，加解密算法是保密的,不需要密钥,也就是是说,密文的不可识别性是通过算法的保密性来实现的,这种形式灵活性差。现代密码体制中，密码算法都是公开的,密文的不可识别性是通过密钥保密实现的,加密算法和解密算法的操作通常都是在一组密钥的控制下进行,密钥是密码体制安全保密的关键。如果在一个密码算法中，加密密钥和解密密钥是一样的,或者虽然不一样,但是由其中的一个可以很容易地推导出来另一个,则称之为对称密码算法。密码体制到现在一直被认为是一种安全性能很高的密码体制。因为R S A密码算法的安全性是完全依赖于大素数因子分解的数学难解问题。多素数RSA密码体制存在很多优点，首先，采用中国剩余定力进行签名，速度与标准RSA算法相比，快了很多；其次，多素数RSA算法采用多个素因子乘积，更有利于抵抗wiener攻击。所以，多素数RSA密码体制其安全性更高
完全密钥托管方案的工作原理如下图:

完全密钥托管方案模型
为了解决完全密钥托管存在的缺陷，密钥托管技术【41,42,43〕被提出来，并运用到完全密钥托管模式中去。密钥产生阶段用户密钥的公钥e和私钥d可以自动产生,然后把产生的d分成不同的部分，交给多个托管机构分别托管。其主要思想是,由用户产生密钥,然后使用一种可验证的托管协议将私钥分割并交付给多个托管机构托管,托管机构可以凭借此协议检查用户托管的私钥d是否真实，而且多个托管机构联合才可以恢复出用户的私钥。同时，该方案中，用户参与了密钥的产生，增加了密钥的可信度。然而该方案提出几年后，Kilianl在文献[44]中指出,可验证密钥托管由于采用了用户单独产生密钥的方法,“阈下攻击”又成了新的威胁，对于托管机构的权利滥用仍然还是没有解决。同时，由于方案自身的一些缺憾，在实际用用中并不可行。
可验证的密钥托管方案的工作原理如下图

可验证密钥托管方案原理图
随着密钥托管技术的发展，在可验证密钥托管方案的基础上,有人提出了改进的可验证密钥托管方案【34，45】。鉴于完全密钥托管与可验证密钥托管的特点，在本方案中，用户和托管机构共同参与密钥的产生。在托管方面，托管机构只是托管私钥d的部分信息，在庄涌[34]提出的可验证部分密钥托管方案中,也是类似 的托管思想。可验证的密钥托管中多个密钥托管机构联合才可以恢复出用户的私钥。
总结前人的经验，结合密钥托管的研究现状，有人把门限方案御用到密钥托管方案中，。但是简单的把门限方案运用于密码算法是不对的，不能解决“一次监听，永久监听”问题。用户与托管机构的共同参与，解决了“阈下攻击”的问题，
分布式密钥托管方案：这个方案是以素数作为运算媒介来实现密钥托管，又称为多素数RSA算法（Multi-Prime RSA算法），即,这种方案由多个密钥托管机构一起组合产生用户的公钥N,而N是t个安全素数的积,即公钥N是由t(,可任意指定)个不同的安全素数相乘而得。其基本思想是,各密钥托管机构,只负责托管用户公钥N的安全素数分解因子。
工作原理如图

分布式密钥托管方案原理图
3.2 RSA一51和RSA一52系统
RSA一S1系统和RSA一S2系统的产生最开始是由文献「46〕引出的,这两个系统的目标是将终端设备中运算能力相对较差的系统担任的任务中的一些计算量转至计算能力较强的系统中去,从而让计算能力强的客户端系统为终端设备减少计算压力。后来文献「47」对RSA一51系统和RSA一52系统进行了完善,将服务器系统因计算压力过大而造成的过载问题进行了缓压。文献「48〕和「49〕将RSA一52系统的运用领域扩大化，将其服务器系统运用到RSA算法系统中去，将其服务器端变为RSA算法的解密端,而将客户端变为RSA算法的加密端。通过这样的转换,陈功的将解密端的负载压力过渡到加密端,从而促进了RSA算法的运行效率。文献「48〕将这种算法称为EARSA(EnervptASSIStantRSA一52RSA)算法。
3.2.1 RSA一51系统
文献【42】改进RSA一51系统的方法是,将服务器端生成的私钥表示为di和fi两个向量，而di和fi是两个随机产生且长度分别为c位和n位的二进制向量，通过这样的方式将解密时形成负载压力由服务器端转直客户端，其具体过程如下:
1). 向量由服务器端过渡到客户端。

2).客户端计算
其中
得到向量,再将z向量发送到服务器端。进而服务器通过

调节过载压力。
3.2.2RSA一s2系统
文献[42]对RSA一52系统的优化方案为:第一步是让客户端产生两个二进制向量
和且满足:
和其中都是c位数的随机数,是n位的随机数。第二步为客户端将N、x和向量D发送到服务器端,让服务器端计算Z向量其中，并且将z向量发回到客户端。第三步客户端将z向量作为输入,并计算
和最后利用(定理2.4)进行合并,最终得到结果。

3.3分布式密钥拖管RSA算法分析
RSA 算法从提出到现在已三十多年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解,而就目前存在的以因子分解为主的运行方法,其模数分组长度很长,在实现安全的前提下,模数ｎ至少也要1 024ｂｉｔｓ以上,这就使得运算代价不断变高,而且运算速度也会相应的变慢,并且在大数分解技术不断成熟和发展的进程中,这个长度还会不断的增加,带来的运算难度随即增大，不利于密钥拖管的运作和管理。
广泛的应用证明RSA算法的安全性是非常可靠的。但在许多情况下,如果加密的设置和使用不当,会带来安全问题。同样，在本文研究的分布式托管方案中这些问题同样存在，我们经过对RSA密码体制的分析发现RSA存在以下3个主要缺陷:
3.3.1运行速度慢
例如,可以选e为小一点,可以大大减少运算量。但是值得注意的是e太小时可能会导致低加密指数攻击。RSA实验室的建议使用65537,65537已经使一个非常大的数字,在进行加解密运算时,所花费的时间相比其他加密系统开销非常大,下面我们仔细分析以下RSA算法时间消耗上的详细。RSA算法的大部分数学运算都是基于大整数的模幂和模乘,因此RSA算法的运行速度较慢成为了RSA算法的一个显著特点。另外随着各种各样的攻击手段的多样化,RSA算法在安全性上也受到了极大的冲击。RSA密码体制在理论上来说是非常安全的,但是，由于在实际应用过程中,具体的每一个RSA密码系统都是不一样的,每一个系统的详细设计都有着自己的不同要求,或是对速度的要求,或是对安全性的要求
3.3.2实现上的时间消耗
R. L. Rivest[50〕等人在建立RSA公钥密码体制时,对于求Me(rnodn)的算法的解决是根据重复平方求模和相乘后求模这两种算法相结合的方法进行处理的，即BR算法。BR算法在目前RSA算法的运行中起到了决定行的核心作用。BR算法的过程是：第一步将指数E表示成二进制形式， :第二步将幂模计算。其具体的实现步骤如下:
(以a =为例)
(1)将X表示成二进制数
(2)令 a=l
(3)对于 i=t, t 一 1,t — 2,,, 1,0 重复执行 步骤1 和 步骤2;
步