《基于二次剩余设计的密码方案设计》13000字（论文）

[。非对称加密技术也被称为公钥密码技术。与对称加密不同，非对称加密技术在加解密过程中使用的密钥并不是相同的，这两个密钥分别为公钥和私钥，通常来讲公钥是根据私钥进行生成的，不能通过公钥来反推出私钥。如果用公钥对消息加密，只有用该公钥对应的私钥才能解密出原消息；同样的，如果使用私有密钥对一个消息进行加密，也只能通过该对密钥的公开密钥进行解密。非对称加密的流程如图2.2所示，故公钥可作为公开信息进行管理维护，用户只需将私钥进行保密储存，防止他人窃取即可。相对于对称加密，其优点是公私钥分开，可在不安全的信道中进行会话密钥的协商，缺点就是在生成公私钥对的速度较慢，加解密速度过慢。图2.2非对称加密模型3基于二次剩余密码方案介绍3.1基于Paillier的改进数字签名方案介绍文献[16]根据文献[7]所提出的基于函数F的加解密的思路，对Paillier的单向陷门置换进行了改进，通过将其陷门置换应用得到了一个改进以后的Paillier的数字签名方案。该方案提高了Paillier在签名产生和验证的效率，对这两方面都有所改进。该方案主要分为三个部分，分别为密钥生成、签名生成以及签名验证。下面为该方案的详细介绍：密钥生成部分：随机选取两个大素数x和y，且存在一个数n，使得n=xy，Carmichael函数（n）=lcm（x-1，y-1）（其中lcm（a，b）表示a和b的最小公倍数），而且b=modn。为了后续方便表示，以后都以代替（n）。此处g选取的值为1+n，除此之外，定义L函数为L（q）=。并选取一个Hash函数h，该函数为：。由此可知，（x，y）作为签名者的私钥，n作为签名者的公钥。签名生成部分：先给定一个消息m，将m通过hash函数进行摘要计算生成h（m），然后通过生成的私钥（x，y）或来生成对应的签名（s1，s2），具体流程如下：s1生成过程：通过将计算出的h（m）经由L函数计算并与b相乘进行模n的结果即是s1：s1=bL（h（m））modns2生成过程：将计算出的h（m）以及s1通过除法运算再进行乘方运算进行模n的结果即是s2：s2=modn。签名验证部分：当签名接收者接收到消息m和数字签名（s1，s2）以后，便可通过验证下面的等式来看是否接受签名。若等式成立，验签成功，那么接受签名，否则验签失败，拒绝签名。等式如下：h（m）=（1+s1n）s2bmodn3.2基于二次剩余的签名方案介绍在不断对Paillier的体制以及它的变体进行深入的学习和研究以后，在Paillier签名方案改进的基础之上，通过引入二次剩余定理相关问题对该方案的安全性进行改进，即在Blum-Williams函数模型下，构造出一个新的数字签名方案。改进后的方案完善了已有的Paillier签名方案的不足之处，除此之外，还解决了签名方案中效率和安全性之间的问题，改进后的方案主要也分为三个部分，分别为密钥生成、签名生成和签名验证三个方面，具体方案如下所示：第一部分是密钥生成部分，即选取两个大素数x和y，其中x和y需满足x3mod8，y7mod8，x和y的大小需接近，存在一个=lcm（x-1，y-1），且n=xy，=modn，L函数的定义为：L（q）=，函数h为md5，即通过md5对消息进行摘要计算。那么改进后签名方案的私钥为（x，y），公钥为n。第二部分为密钥生成部分，该部分主要分为6个步骤，首先给定一个消息m，签名者可以按照下面的步骤来对消息进行签名。步骤1：将消息m经由md5进行摘要计算得到对应的消息摘要h（m），接下来计算s的值：s=L（h（m））modn步骤2：首先应该验证步骤1中所得到的s能否满足s与n互素，即（s，n）=1，如果不满足互素条件，那么可以通过引入随机数以用于修改s的值（s加减随机数），从而让s、n互素。实际上，由文献[18]可知，当n很大的时候，s与n不互素的概率可以忽略不计，当s与n互素之后，可以计算m，计算m的公式如下：0（）=1，即s的勒让德符号为1。m=1（）=-1，即s的勒让德符号为-1。步骤3：通过Jacobi相关的运算结果可以知道，（2s）modnJ，此时，m的计算公式如下：0（2smodn）qm=-1（2smodn）步骤4：计算s的值，其中d的值为，计算公式如下：s=（2s）modn步骤5：计算s，公式如下：s=modn步骤6：将消息m生成的对应签名（m，m，s，s）用公钥进行加密，将加密后的签名和消息m以及公钥n私钥（x，y）一起发送给接收者。第三部分为签名验证部分，接收者接收到加密的签名、消息m以及公钥n私钥（x，y）后，首先利用私钥对签名进行解密，然后根据解密后的签名去验证下列等式是否成立，如果等式成立，那么就接收签名，等式不成立，就拒绝签名，等式如下：h（m）=[1+]mod3.3基于二次剩余签名方案特点签名方案设计基于二次剩余定理及相关数论知识。在Paillier签名方案基础上引进了Blum-Williams函数，根据其是单向陷门置换从而构造出一个新的签名方案，该方案在安全性和效率方面都有所提升。在安全性方面是基于大整数分解困难的前提下，是能够抵抗各种已知的伪造攻击的。即使获得签名，但根据解模合数n平方根困难性很难把求出来；即使能够将伪造出来，但是想要等式成立还得计算出对应的m，由于hash函数的不可逆性，所以在计算上是不能得到m；除此之外，在生成签名后还会对签名进行加密，接收者收到的是加密后的签名，需对签名进行解密才可进行验证。因此，从多个方面都可以表明方案安全性较高。本文签名方案在效率方面也有所提升。在运算代价方面，与其他方案相比，减少了L函数和模幂的计算，增加了模乘运算，减少了计算量，具有明显的计算优势。在通信代价方面，本文方案只需要传输公开参数n，虽然签名长度多了a、b两个因子，但在n比较大的时候可以忽略不计，即签名长度未发生变化。从这两方面可以看出本文方案有较高的效率。4方案分析4.1正确性分析根据签名的全过程我们可以推导出如下式子：h（m）=[1+]mod=[1+]mod且其中存在：（2s）modnJ，且n=xy，x3mod8，y7mod8，那么xy3mod4，因此可以分为以下两种情况：当（2smodn）q时，此时m=0，由2.1.4定理3可得：（2s）=（-1）2smodn当（2smodn）时，此时m=1，由2.1.4定理3可得：是啥（2s）=n-2s=（-1）2smodn所以，上述等式可变化为：[1+]mod=[1+（-1）2s2(-1）n]mod=（1+sn）mod现在将s=modn代入，即可得到下列等式：h（m）=[1+]mod=（1+sn）mod综上所述：如果存在有（m，m，s，s）能够对消息m进行正确签名，那么就一定存在一个值使得等式：[1+]mod=h（m）成立，所以我们的改进方案是正确的。4.2安全性分析因为在文献[16]中所设计的签名方案中，它的安全性是以RSA[n，n]的难解性为基础的。在本文所设计的方案中，通过将二次剩余定理引入到原方案中，从而让s的计算所依赖于大整数的分解难题，以此来完善文献[16]中签名方案的安全方面的不足。由于本文的签名方案是将改进后的Paillier签名方案和Rabin签名方案进行融合后而形成的，所以本文的方案在原有方案的安全性上有很大的完善和提升，即本文签名方案具有更高的安全性。又根据文献[2]中的定理，即RSA[n，n]的问题可以归结于Fact[n]上面。那么求解RSA[n，n]的难度是不会超过大整数的素因子分解问题的，又因为Rabin签名方案已经证明了其安全性等价于大整数分解问题的困难性。所以，总的来说，本文所提出的数字签名方案是以大整数分解难题为基础来分析其安全性的。引理如果大整数分解问题是困难的，那么本文所提出的数字签名方案是能够抵抗适应性的选择消息攻击。证明过程：假设攻击者想进行攻击操作，那么他会向签名者请求对消息m,m签名，那么他会得到相对应的签名q，q，即q=（r，s，a，b），q=（r，s，a，b），那么我们可以进行验证从而得到如下等式：h（m）=[1+r2n]smodnh（m）=[1+r2n]smodn此时攻击者可以通过上述等式从而得到下面的式子，如下所示：h（m）==这个时候，如果存在一个消息m’以及签名r和s，而这些信息恰好被攻击者所获得，从而使得等式h（m’）=h（m）=[1+r2n]smodn成立，那么显而易见，本文的数字签名方案是不能够抵抗适应性选择消息攻击的。而通过分析可以知道的是，要满足上述等式，需选取t=modn，但是现在所选取的rZ则需要满足下列等式：[1+r2n]=。又因为当n分解未知的情况下，对模合数n的平方根求解的困难性是和整数分解是一样的。所以，当大整数分解问题是困难的时候，利用上面的式子去求解r也是很困难的，那么则证明了本文的数字签名方案是安全的。就算攻击者能够得到或者伪造出相应的r，但是要让等式h（m’）=h（m）=[1+r2n]smodn成立，还要找到对应的m’，这就要对hash函数进行求逆运算，很显然在计算上这是不可行的。所以，只有成功分解出n以后才可以得到私钥（x，y）。所以，根据上述描述，大整数分解困难问题是本文数字签名方案安全性的基础保障。同时以大整数分解为基础，本文签名方案还能抵抗各种已知的伪造攻击，安全性有了很大的提升。4.3效率分析从方案的整体设计思路上看，如表4.1所示。本文方案与文献［2］和文献［16］都是基于公钥加密构造的签名，而文献［19］中签名方案则是构造了一种“等式关系”进行签名。本文方案与文献［2］和文献［16］中签名方案的安全性都基于数论中的困难问题，而文献［19］中方案的安全性基于ＲSa-Paillier陷门函数为单向陷门置换。表4.1签名方案设计思路比较方案陷门函数安全性基于公钥加密的签名文献[2]RSA[n，n]可以文献[16]RSA[n，n]可以文献[19]E是单向陷门置换不可以本文方案Fact[n]可以运算代价的比较在运算代价上，本文从以下四个方面比较了三种签名方案的效率，如表4.2所示。1－L表示1个L函数的运算。1－d(n)表示一个模n的除法运算。1－m(n)表示1个模n的乘法运算。1－E(n)表示1个模n的幂运算。在Paillier签名产生过程中，L函数的计算量相对较大。由表2可知，文献［16］中的方案之所以提高了Paillier签名方案的效率，是因为其在L函数运算和模幂运算上的计算量都有所减少。而本文方案在不增加L函数运算的基础上，出于安全性考虑，在文献［16］方案的基础上只增加了一次模幂运算，与安全的Paillier签名方案相比，具有明显的计算优势。相应的，与文献［16］中签名方案相比，在签名验证过程中，本文方案也避免了计算量相对较大的模幂运算，只增加了一次模乘运算，而且在计算上明显优于Paillier签名方案。而文献［19］中的方案由于利用的单向函数和构造方法的特殊性，签名产生阶段不需要L函数的运算，但是签名验证的运算代价与本文方案相同。表4.2签名方案运算的代价签名方案签名产生签名验证文献[2]2-L，1-d（n），1-m（n），2-E（n）2-E（）1-m（）文献[16]1-L，1-d（n），1-m（n），1-E（n）1-E（）1-m（）文献[19]1-E（）3-m（）1-E（）3-m（）本文方案1-L，1-d（n），1-m（n），2-E（n）1-E（）3-m（）通信的代价比较由于签名者和签名接收者之间传输的主要是公开参数和产生的签名，因此通信代价考虑的是传输的公开参数的数据量和签名的长度。在表4.3中，||表示Zn中元素的长度，||表示中元素的长度，||表示中的元素。如表3所示，在公开参数传输的数据量上，本文方案与文献［16］中方案相同，只需要传输公开参数n，不需要传输g，与文献［2］的方案相比，传输参数的数据量降低了，减少了带宽。另外，本文的方案产生的签名的长度仅仅比文献［16］中方案增加了a和b两个比特因子，而且由于签名验证方可以在验证过程中计算出b，所以实际上只增加了一个比特因子，在n比较大时，可以忽略不计，因此两方之间需要传输的签名的长度基本没有变化。由此可知，在通信代价上，本文方案与文献［16］的方案基本相同，相较于Paillier签名方案［2］都有所减少。而文献［19］中签名由三个部分组成，与本文方案相比，签名长度较长，需要传输的数据量也较多。表4.3签名方案通信代价的比较签名方案公开参数签名长度文献[2]n，g+文献[16]n+文献[19]n，e，y3本文方案n+++5方案实现5.1实现环境本方案采用了Java语言进行进行实现，具体实现环境如表5.1所示：表5.1实现环境名称类型版本操作系统Windows101903编辑器IDEA18.3编译器JDK1.8.05.2主要流程本方案在改进的Paillier签名方案的基础上，并结合Rabin密码方案，通过二次剩余定理，从而形成新的数字签名方案，该方案主要分为三个部分：分别为生成密钥、生成签名和验证签名，具体流程如图5.2所示：图5.2签名方案主要流程5.3重点函数详解（1）密钥生成部分①判断是否为素数：publicstaticBigIntegerisprime(BigIntegernumber){BigIntegeri=newBigInteger("2");while(pareTo(number)==-1){if((number.remainder(i).compareTo(newBigInteger("0"))==0))break;elsei=i.add(newBigInteger("1"));}if(pareTo(number)==0)returnnewBigInteger("1");elsereturnnewBigInteger("0");}//②求逆运算：通过扩展的欧几里得算法，进行递归，求得该数的逆，在求的结果时，也会用到扩展的欧几里得算法求n的逆。publicstaticvoidexgcd(BigIntegera,BigIntegerb){BigIntegert;if(pareTo(newBigInteger("0"))==0){x=newBigInteger("1");y=newBigInteger("0");return;}exgcd(b,a.remainder(b));//递归运算t=x;x=y;y=t.subtract((a.divide(b).multiply(y)));}签名生成部分①求s时要经过L函数L（q）=，在L函数计算时由于位数过大可能会导致结果输出异常，于是在计算时，会加入一个循环，首先计算，再进行模计算；计算完毕后再与q相乘，模计算，这样得到了，以此类推，一直计算到，循环结束，在后面中和中计算也是用相同的方法。这样计算的好处则是将结果始终控制在一个较小的范围，不至于数据太大从而出现异常，但存在的缺点是如果q和很大，则计算时间会比较长，以下是该过程的部分代码：BigIntegertemp,S;BigIntegercount=newBigInteger("2");BigIntegermod=n.multiply(n);temp=(miu.multiply(miu)).mod(mod);//计算；while(pareTo(lamuda)<0){//进入循环，计算；temp=temp.multiply(miu);temp=temp.mod(mod);count=count.add(newBigInteger("1"));}②在的计算中有的计算，在计算时，采用的方法是遍历，即求出从到模n的结果，把它们的结果组成一个集合，如果计算的结果是属于该集合，那么值为零。在1到（n-1）的所有数里面，出去集合里面的数，所剩下的数组成的集合则为，若计算的结果是属于集合中，那么的取值为1。BigIntegertemp=newBigInteger("2").pow(-a);BigIntegernumber=(temp.multiply(s)).mod(n);//计算得结果；BigIntegertemp1=null;//初始化；BigIntegeri=newBigInteger("1");do{temp1=(i.multiply(i)).mod(n);if(pareTo(temp1)==0){System.out.println("i="+i);return0;}i=i.add(newBigInteger("1"));}while(pareTo(n)<0);//计算、的结果，并与进行比较，得到的取值；return1;}5.4实现截图①选取两个素数x和y，x的取值为，y的取值为，他们分别满足x3mod8，y7mod8，由此可以计算出n的大小，为，以及的大小。此时的私钥为（x，y），公钥为n，具体如图5.3所示：图5.3密钥生成结果②此时输入消息m为message，经由hash函数摘要以及L函数计算可以得到s的值，为，通过s可以计算出的值为，以此类推，环环相扣，计算出、、、的值，它们分别为，此时将消息m以及对应的签名（，，，，）发给接收者，具体如图5.4所示：图5.4签名生成过程③接收者收到消息m以及签名以后则开始进行验证，验证等式是否成立，若成立则接收签名，否则拒绝签名。由于接收的数据通过公式计算出的结果和消息摘要的结果是一直的，那么是成功的，所以接受签名，具体如图5.55.6所示：图5.5消息摘要结果图5.6签名验证结果6结语尽管在学习过程中学了有关于二次剩余的相关内容，但也仅限于基础知识和很少的应用，而基于二次剩余设计实现密码方案还从来没有接触过，是非常陌生的，于是为了更好的完成毕业设计，我主要分为3步计划进行。第一步则是进行理论知识的学习，这是方案设计的基础。前期我主要是进行二次剩余理论的学习，学习相关的数论知识，了解它们相关的应用，尤其是在密码学方面，同时我也了解到二次剩余理论在公钥密码体制中的重要性，与我们生活息息相关；由于是设计密码方案，所以密码学知识必不可少，于是我还重新温习了密码学的相关知识，了解了签名相关流程；最终方案需要实现，所以编程学习必不可少，于是我便温习java、c语言等相关编程语言知识，为后面方案实现打下基础。第二步则是要进行方案的设计，由于之前一直未接触过相关内容，所以不知道方案应该是什么样的，于是便先去了解密码方案的相关内容，密码方案就是要实现加解密或者签名等功能，根据功能不同也可以分为不同的方案。在了解到密码方案相关知识，我又继续查阅资料，查找现在已有的基于二次剩余的密码方案，去学习现有的方案，为自己设计方案打下基础。在学习完他们的方案以后，以及和指导老师协商，我根据改进的Paillier签名方案以及Rabin密码方案相结合，在此基础上进行改进，在签名过程中加入了另外的签名元素，克服了Paillier方案效率和安全性不能兼顾的问题，并对方案进行了安全性分析和效率分析。第三步则是对密码方案进行实现，我选择用java进行密码方案的实现，实现了密码方案的功能，做到了能够验证签名和拒绝签名，只是碍于能力有限，所实现的数据位数还不够大，我会在指导老师帮助下尽可能解决这个问题。参考文献diffieW,Hellmanm.newdirectionsincryptography［J］.IEEETransactionsonInformationTheory，1976，22(6):644-654．Paillierp．public-keycryptosystemsbasedoncompositedegreeresiduosityclasses［C］//InternationalConferenceonTheoryandapplicationofCryptographicTechniques，Springer-Verlag，1999:223-238.damgrdI，Jurikm．ageneralisation，asimplicationandsomeapplicationsofPaillier＇sprobabilisticpublic-keysystem［C］//pKC’01proceedingsofthe4thInternationalWorkshoponpracticeandTheoryinpublicKeyCryptography:publicKeyCryptography．Springer-VerlagLondon，UK，2001:119-136.Catalanod，GennaroＲ，Howgrave-Grahamn，etal．Paillier’scryptosystemrevisited［C］//aCmConferenceonComputer＆CommunicationsSecurity，2002:206-214.Galindod，martynS，morillop，etal．apracticalpublicKeyCryptosystemfromPaillierandRabinSchemes［C］//InternationalWorkshoponTheoryandpracticeinpublicKeyCryptography:publicKeyCryptography．Springer-Verlag，1993:279-291.BressonE，Catalanod，pointchevald．asimplepublic-keycryptosystemwithadoubletrapdoordecryptionmechanismanditsapplications［J］．LecturenotesinComputerScience，2003，2894:37-54．姜正涛，刘建伟，秦波，等．加密|n|+kbit明文的高效公钥概率加密体制［J］．北京航空航天大学学报，2008，34(1):43-46．姜正涛，刘建伟，王育民．Paillier-pointcheval公钥概率加密体制的改进［J］．计算机工程，2008，34(3):38-39.manHa，WeiVK．Id-basedCryptographyfromCompositedegreeＲesiduosity［J］．IacrCryptologyEprintarchive，2004，2004.ZhouSujing，Lindongdai．aninterestingmemberId-basedgroupsignature［J］．Recentdevelopmentsinalgebra＆Relatedareas，2007，2007:279-302.WangZhiwei．anewconstructionoftheserver-aidedverificationsignaturescheme［J］.mathematicalandComputermodelling，2012，55(1-2):97-101.ChengZhen，ChiKaikai，Tianxianzhong，etal．Securenetworkcodingbasedonhomomorpuicsignatureagainstpollutionattacks［C］//2012IEEE2ndInternationalConferenceonCloudComputingandIntelligenceSystems，Hangzhou，2012:1092-1096.岳泽轮，韩益亮，杨晓元．基于Paillier公钥密码体制的签密方案［J］．小型微型计算机系统，2013，34(10):2310-2314.Tingpy，HseuCH．asecurethresholdPaillierproxysignaturescheme［J］．JournalofZhejiangUniversityScienceC，2010，11(3):206-213.CaoZhengjun，LiuLihua．ThePaillier’s