实现数字签名的RSA算法的设计和实现

课程实践汇报书课程名称：密码学和网络安全课程实践题目：实现数字署名RSA算法设计和实现学生姓名：专业：班别：学号：指导老师：日期：年6月18日实现数字署名RSA算法设计和实现摘要伴随计算机网络和信息技术发展，信息安全在各领域发挥着越来越关键作用，其中密码学已成为信息安全技术关键，本文关键介绍了信息加密技术应用。RSA算法是现在公认在理论和实际应用中最为成熟和完善一个公钥密码体制，它是第一个既能用于数据加密也能用于数字署名算法，是公钥密码体制代表。数字署名是起到身份认证、核准数据完整性一个信息安全技术。它经过认证技术来识别真伪。RSA数字署名体制使用是RSA公开密钥密码算法进行数字署名。本文关键内容包含：第一,对RSA算法进行系统介绍；第二,介绍RSA数字署名部分基础概念和数字署名理论实现过程；第三详述RSA数字署名设计和实现，关键实现模块包含RSA密钥产生（一对公钥和私钥），RSA加密算法和解密算法实现，；第四,对该系统进行了整体测试和分析改善。关键字：RSA算法；加密；解密；RSA数字署名目录284451引言 3151161.1课题研究背景 342541.2课题研究意义 3241882RSA算法和RSA数字署名算法概念设计 3228082.1RSA算法概念和原理 332812.1.1RSA算法介绍 3221252.1.2RSA算法实现原理 374062.2RSA数字署名基础概念和RSA数字署名算法实现原理 4108432.2.1RSA数字署名基础概念 4159942.2.2RSA数字署名算法实现原理 5285063RSA数字署名逻辑设计和实现 6280793.1RSA数字署名总体设计 6301463.1.1RSA数字署名所需实现功效 6293173.1.2总体要求和设计 688913.2各部分设计实现 7118493.2.1密钥产生实现 7184333.2.2产生消息摘要设计实现 10212193.2.3数字署名设计实现 12170353.2.4验证数字署名设计和实现 15146823.2.5RSA数字署名运行结果 18244594软件整体测试和分析改善 18310544.1软件整体测试 18170044.2性能分析和改善设想 1912684开发体会 197091参考文件 201引言1.1课题研究背景伴随电子信息技术快速发展，人类已步入信息社会。不过因为整个社会形成了一个巨大计算机网络，任何一个计算机网络出现安全问题，全部会影响整个国家网络安全，所以信息安全、计算机网络安全问题已引发了人类高度重视。网络安全方法应是能全方位地针对多种不一样威胁和脆弱性，这么才能确保网络信息保密性、完整性和可用性。现代密码学已成为信息安全技术关键，密码学是以研究通信安全保密学科，即研究对传输信息采取何种秘密变换以预防第三者对信息窃取。RSA公钥加密算法是第一个既能用于数据加密也能用于数字署名算法。它易于了解和操作，也十分流行。伴随越来越多商业应用和标准化工作，RSA已经成为最具代表性公钥加密技术。现今，网上交易加密连接、网上银行身份验证、多种信用卡使用数字证书、智能移动电话和存放卡验证功效芯片等，大多数使用RSA技术。1.2课题研究意义伴随电子商务发展，网络上资金电子交换日益频繁，怎样预防信息伪造和欺骗成为很关键问题。现在相关数字署名研究关键集中点是基于公钥密码体制数字署名。手写署名每一项业务全部是数字署名潜在用场。数字署名能够提供数据完整性、真实性和不可否认性。数字署名技术在身份识别和认证、数据完整性、抵赖等方面含有其它技术无法替换作用，它在军事、电子商务和电子政务等领域有着极广泛应用。而在公钥体制中，RSA是一个较为完善公钥密码算法，不仅能够同时用于加密和数字署名，而且易于了解和操作，是被广泛研究公钥密码算法。所以，基于RSA数字署名含有较强研究性和实际应用意义。2RSA算法和RSA数字署名算法概念设计2.1RSA算法概念和原理2.1.1RSA算法介绍RSA算法是一个公钥密码算法,实现RSA算法包含生成RSA密钥，加密和解密数据。RSA算法是第一个能同时用于加密和数字署名算法，也易于了解和操作。RSA是被研究得最广泛公钥算法。RSA缺点关键有：A)产生密钥很麻烦，受到素数产生技术限制，所以难以做到一次一密。B)分组长度太大，为确保安全性，n最少也要600bits。2.1.2RSA算法实现原理1)随机选择两个不一样素数p和q，它们宽度是密钥宽度二分之一。2)计算出p和q乘积n。3)在2和Φ(n)之间随机选择一个数e,e必需和Φ(n)互素，整数e用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。4)从公式ed≡1modΦ(n)中求出解密密钥d。5)得公钥（e，n）,私钥(d,n)。6)公开公钥，但不公开私钥。7)将明文P(假设P是一个小于n整数)加密为密文C，计算方法为：C=P^emodn;8)将密文C解密为明文P，计算方法为：P=C^dmodn;然而只依据n和e（不是p和q）要计算出d是不可能。所以，任何人全部可对明文进行加密，但只有授权用户（知道d）才可对密文解密。2.2RSA数字署名基础概念和RSA数字署名算法实现原理2.2.1RSA数字署名基础概念RSA数字署名体制使用了RSA公开密钥密码算法进行数字署名，鉴于RSA算法在实践中已经被证实了安全性，RSA数字署名体制在很多安全标准中得以广泛应用。ISO/IEC9796和ANSIX9.30-199X和美国联邦信息处理标准FIPS186-2已经将RSA作为推荐数字署名标准算法之一。RSA数字署名算法，包含署名算法和验证署名算法。它是利用RSA算法加密和解密算法原理进行一个数字署名，实际上是经过一个哈希函数来实现（本设计是经过MD5算法）产生消息摘要MD来实现所需加密对象。数字署名特点是它代表了消息特征，消息假如发生改变，数字署名值也将发生改变，不一样消息将得到不一样数字署名。安全数字署名使接收方能够得到确保：消息确实来自发送方。因为署名私钥只有发送方自己保留，她人无法做一样数字署名，假如第三方冒充发送方发出一个消息，而接收方在对数字署名进行解密时使用是发送方公开密钥，只要第三方不知道发送方私有密钥，加密出来数字署名和经过计算数字署名肯定是不相同，这就提供了一个安全确实定发送方身份方法，即数字署名真实性得到了确保。数字署名类似手书署名，它含有以下性质：1）能够验证署名产生者身份，和产生署名日期和时间；2）能用于证实被签消息内容；3）数字署名可由第三方验证，从而能够处理通信双方争议。为了满足数字署名这些要求，比如，通信双方在发送消息时，既要预防接收方或其它第三方伪造，又要预防发送方因对自己不利而否认，也就是说，为了确保数字署名真实性。数字署名原理是：（发送方和接收方依据要求各自产生自己一对公钥和私钥）1）被发送文件采取某种算法对原始消息进行运算，得到一个固定长度数字串，称为消息摘要（MD），不一样消息得到消息摘要各异，不过对相同消息它消息摘要却是唯一；2）发送方生成消息消息摘要，用自己私钥对摘要进行加密来形成发送方数字署名；3）这个数字署名将作为消息附件和消息一同用接收方公钥进行加密，将加密后密文一起发送给接收方；4）接收方首先把接收到密文用自己私钥解密，得到原始消息和数字署名，再用发送方公钥解密数字署名，随即用一样算法计算出消息摘要；5）假如计算出来消息摘要和发送方发送给她消息摘要（经过解密数字署名得到）是相同，这么接收方就能确定数字署名确实是发送方，不然就认为收到消息是伪造或是中途被篡改。数字署名原理图如2-1所表示ABEDEDEDED用A私钥加密用B公钥用B私钥用A公钥解密数字署名加密解密核实署名图2-1数字署名原理2.2.2RSA数字署名算法实现原理RSA数字署名算法分为以下两个步骤：1）署名算法（包含两步：消息摘要计算，RSA加密）(1)消息摘要MD计算：消息在署名前首先经过MD5计算，生成128位消息摘要；MD5函数是一个单向散列函数，它将任意长度消息压缩成128位消息摘要。应用MD5单向性（即给定散列值,计算消息极难）和抗碰撞性(即给定消息M，要找到另一消息M’并满足二者散列值极难)，能够实现信息完整性检验。另外该函数设计不基于任何假设和密码体制而直接结构，实施速度快，是一个被广泛认可单向散列算法。(2)对MD作RSA加密算法：采取署名者私钥加密消息摘要，得到加密后字符串即数字署名；2）验证署名算法（RSA解密、对消息摘要计算和比较）验证署名算法包含两步：RSA解密得署名者消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证署名过程输入为消息，署名者公钥，署名；输出为验证结果，即是否是正确署名。(1)RSA解密：署名实际是加密消息摘要，用以上所述RSA解密方法采取署名者公钥对这个加密消息摘要解密，解密结果应为128位消息摘要。(2)消息摘要计算和比较：验证者对消息用MD5算法重新计算，得到验证者自己消息摘要。验证者比较解密得到消息摘要和自己消息摘要，假如二者相同，则验证成功，能够确定消息完整性及署名确实为署名者；不然，验证失败，确定署名被冒充或是被篡改。3RSA数字署名逻辑设计和实现3.1RSA数字署名总体设计3.1.1RSA数字署名所需实现功效在本软件中需要实现功效有以下多个：（1）生成RSA密钥：公钥ke=（e,n），私钥kd=(d,n)；（2）利用MD5算法计算出消息摘要MD；（3）数字署名实现：用私钥d对消息摘要进行加密计算（RSA算法中加密方法）；（4）验证数字署名：用公钥e对数字署名进行解密计算（RSA算法中解密方法），得到解密结果和(2)步计算出消息摘要比较，假如两个消息摘要一样则署名成功。3.1.2总体要求和设计本软件总体要求有：1）按要求生成非对称密钥——公钥和私钥；2）按任意写入消息字符串(明文信息)生成所需要消息摘要MD；3）在本设计中用产生私钥d依据RSA算法加密原理对所生成消息摘要进行加密运算，得到数字署名；4）在本设计中用产生公钥e依据RSA算法解密原理对所加密消息摘要即数字署名进行解密运算，得到对应消息摘要（在本设计中标示为解密信息），比较两个消息摘要，验证数字署名者身份真实是否；5）提醒信息完整、操作舒适、图形界面雅观。本软件总体设计全部是基于C++开发环境，采取是MicrosoftVisualc++6.0运行环境。3.2各部分设计实现3.2.1密钥产生实现在密钥产生部分中起决定性作用是素数选择，

对随机数作素性检测，若经过则为素数；不然增加一个步长后再做素性检测，直到找出素数。素性检测采取Fermat测试。这个算法理论依据是费尔马小定理：假如m是一个素数，且a不是m倍数，那么依据费尔马小定理有：am-1=1(modm)。实际应用时：am-1=1(modm)am=a(modm)a=am(modm)，所以对于整数m，只需计算am(modm)，再将结果和a比较，假如二者相同，则m为素数。选择a=2，则a一定不会是任何素数倍数。依据所选素数不一样产生不一样密钥。密钥理论产生模块步骤图图3-1所表示：产生任意素数产生任意素数p和q计算n=p*q计算ou_la=(p-1)(q-1)选择e作为公钥计算d作为私钥图3-1密钥产生密钥产生部分代码实现： CStringstr; //第一步产生任意素数 GeneratePrimeNumbers(); //第二步计算n=p*q m_n=m_Prime1*m_Prime2; //第三步0=(p-1)(q-1) m_Undef=(m_Prime1-1)*(m_Prime2-1); //第四步选择'e' SelectE(); //第五步计算D CalculateD(); //显示公钥和私钥 //(1)公钥KU={e,n} str.Format("{%d,%d}",m_e,m_n); m_public_key.SetWindowText(str); //(2)私钥KU={d,n} str.Format("{%d,%d}",m_d,m_n); m_private_key.SetWindowText(str); //选择一个'e'使'e'和m_Undef互素//选择e函数实现SelectE(){CStringstr;for(floati=2;i<100000;i++) { if(IsRelativePrime((float)m_Undef,(float)i)) { m_e=(long)i; return; } }}//互为素数函数实现IsRelativePrime(floatX,floatY){floatR;//输入:X,Y if(X<Y)//假如X较小则交换两个值 { X=X+Y; Y=X-Y; X=X-Y; } //在这时X总是比Y大 for(;;) { if(Y==0) break; R=fmod(X,Y); X=Y; Y=R; }if(X!=1) returnfalse; else returntrue;//互素}//计算D函数实现CalculateD(){ floatd; longd_dash; CStringstr; for(floatk=1;k<100000;k++) { d=(m_Undef*k+1)/m_e; d_dash=(long)((m_Undef*k+1)/m_e); if(d==d_dash) { m_d=d; return; } }}//产生素数函数实现GeneratePrimeNumbers(){ CStringstr; UpdateData(TRUE);//经过以下两个函数可取得两个大素数，但增加了计算复杂性，为了方便，直接给定素数// m_Prime1=FindPrime(1);// m_Prime2=FindPrime(m_Prime1); m_Prime1=47; m_Prime2=71;}3.2.2产生消息摘要设计实现计算消息摘要理论实现步骤图图3-2所表示：初始化MD5初始化MD5所需常量计算所需追加长度对原始信息进行补位将输入分成512位块循环处理块得到消息摘要得到消息摘要图3-2消息摘要计算步骤在以上步骤图中其中循环处理块是最关键一步，也是MD5关键算法，在这一步中包含了：（1）把四个连接变量复制到了四个变量a,b,c,d中，使a=A，b=B，c=C，d=D；其中a,b,c,d组合成128位寄存器，且在实际算法运算中保留中间结果和最终止果；（2）将目前512位块分解为16个子块，每个子块为32位；（3）要循环四轮，每一轮处理一个块中16个子块，四轮第一步进行不一样处理，其它相同：每一轮有16个输入子块M[0]，M[1]，…………..M[15]，或表示为M[i]，其中i为0-15；t是常量数组，包含64个元素，每个元素为32位，数组t表示为t[1]，t[2]，………t[64]，或t[k]，k为1-64；MD5循环四轮操作过程用下式表示：a=b+((a+proccessP(b,c,d)+M[i]+T[k])<<<s)(<<<s表示循环左移s位)产生消息摘要关键代码以下： inti;intIndex; //初始化MD5所需常量Init(); //计算追加长度Append(WriteMessage.length());//对原始信息进行补位 for(i=0;i<m_AppendByte;i++) { if(i==0)WriteMessage+=(unsignedchar)0x80; elseWriteMessage+=(unsignedchar)0x0; }//将原始信息长度附加在补位后数据后面for(i=0;i<8;i++)WriteMessage+=m_MsgLen[i]; //位块数组unsignedcharx[64]={0};//循环，将原始信息以64字节为一组拆分进行处理 for(i=0,Index=-1;i<WriteMessage.length();i++) { x[++Index]=WriteMessage[i]; if(Index==63) { Index=-1;//将64字节位转换为16个字节 Transform(x); } }//将寄存器ABCD最终值转换为16进制返回给用户 returnToHex(UpperCase);3.2.3数字署名设计实现数字署名理论实现步骤图图3-3所表示，数字署名，就是经过在数据单元上附加数据，或对数据单元进行加密变换，从而使接收者能够确定数据起源和完整性。数字署名是预防她人对传输文件进行破坏，和确定发信人身份手段。数字署名中加密算法就是应用RSA加密原理，而它验证算法则是应用RSA解密原理。开始得到数字署名开始得到数字署名得到消息摘要MD用私钥d加密MD结束图3-3数字署名实现步骤RSA加密、解密过程全部为求一个整数整数次幂，再取模。假如按其含义直接计算，则中间结果很大，有可能超出计算机所许可整数取值范围。为了减小中间结果和提升加、解密运算中指数运算有效性，本设计采取了快速指数算法。它运算过程为（假如要算a^mmodn）：1）将m表示为二进制形式；2）初始化c=0，d=1，c在这里表示指数部分结果，它终值即为指数m，d是中间结果，它终值即为所求结果；3）从二进制数最高位到最低位开始对每一位全部用公式1进行运算，得到d为该步结果，公式1：c=2*c;d=fmod(d*d,n);4）若二进制数是1,则在上面运算后继续以下运算：c=c+1;d=fmod(d*a,n);得到结果d才为该步最终止果。数字署名关键实现过程代码以下：//消息摘要，8位为一组一个字符一组 charmessage[200];//从文本框中得到消息摘要m_message.GetWindowText(message,200); len=strlen(message); charshowstr[1000]=""; intNO_BITS=32; doublec=0,d=1; charbits[100]; doublen=(double)m_n; unsignedcharch; doubledata;//19; longi,k=NO_BITS; intsizeof_d=sizeof(double);//将十进制数私钥d转换为二进制D_to_B(m_d,32,bits);//得到适宜字节 GetOnlyProperBits(bits); k=NO_BITS=strlen(bits)-1; for(intii=0;ii<len;ii++) { //从message中读取字符放入'data'中 ch=message[ii]; data=(double)ch; //计算((data)^dmodn)快速指数算法实现 c=0;d=1; for(i=k;i>=0;i--) { c=2*c; d=fmod(d*d,n); if(bits[NO_BITS-i]=='1') { c=c+1; d=fmod(data*d,n); } } //从'd'中读取字符放入result中 result[ii]=d;//把字符串变为十六进制数后连接字符串 strcat(showstr,longtohex(d)); }//结束循环//显示结果 m_result.SetWindowText(showstr); }//字符串变为16进制数函数实现longtohex(longx){charstr[8]; inti=0;//商 inta;//余数 intb; longtt=x; while(tt>=16) { a=tt/16; b=tt%16; switch(b) { case0:str[i]='0';break; case1:str[i]='1';break; case2:str[i]='2';break; case3:str[i]='3';break; case4:str[i]='4';break; case5:str[i]='5';break; case6:str[i]='6';break; case7:str[i]='7';break; case8:str[i]='8';break; case9:str[i]='9';break; case10:str[i]='A';break; case11:str[i]='B';break; case12:str[i]='C';break; case13:str[i]='D';break; case14:str[i]='E';break; case15:str[i]='F';break; }; i++;tt=a; } str[i]='\0'; strrev(str); returnstr;}3.2.4验证数字署名设计和实现得到数字署名得到数字署名用公钥e解密数字署名得到消息摘要（解密信息）开始结束图3-4验证数字署名步骤验证数字署名正确和成功性，关键是比较得到两次消息摘要是否一样，假如验证方用署名方公钥解密得到消息摘要（即是本设计中得到解密信息）和她自己计算得到消息摘要（在本系统中为第一次计算得到消息摘要）是一样，则证实署名是正确，没有被篡改或是冒充，验证署名原理则是依据RSA解密算法，具体理论步骤图图3-4所表示：（在本设计中署名和验证署名全部在同一界面实现，不进行文件双方传输）验证数字署名过程时应用解密算法是RSA解密原理，而RSA解密过程也应用了求一个整数整数次幂，再取模运算。在此也采取了快速指数算法，具体算法过程同RSA加密过程中应用快速指数算法是一样。验证数字署名关键实现过程代码以下：intNO_BITS; doublec=0,d=1; charbits[100]; doublen=(double)m_n; doubledata;//19; longi,k;intsizeof_d=sizeof(double);//用于存放解密信息 charmessage[200];//将十进制数公钥e转换为二进制 D_to_B(m_e,32,bits); GetOnlyProperBits(bits); k=NO_BITS=strlen(bits)-1; for(intj=0;j<len;j++) { //从result中读取字符放入'data'中 data=result[j]; //计算((data)^emodn)快速指数算法实现 c=0;d=1; for(i=k;i>=0;i--) { c=2*c; d=fmod(d*d,n); if(bits[NO_BITS-i]=='1') { c=c+1; d=fmod(data*d,n); } }//结束循环 //从'd'中读取字符放入message中 message[j]=d; }//显示结果 m_mingwen.SetWindowText(message); }3.2.5RSA数字署名运行结果图3-5RSA数字署名运行结果在本软件中得到二个消息摘要：依据写入消息（明文信息）计算出来消息摘要、解密数字署名得到消息摘要（即是本设计中解密信息）。假如两个消息摘要是一样则证实RSA数字署名者身份真实性，从而实现了RSA数字署名。该系统运行结果图3-5所表示。产生消息摘要和解密得到消息摘要（在此处是解密信息）是完全一样，则证实了数字署名真实性。4软件整体测试和分析改善4.1软件整体测试（1）测试密钥生成：产生密钥前提是要有两个素数生成，密钥产生依靠于素数生成，素数生成不一样则密钥也会不相同，在本设计中素数是47和71，则相对应密钥是公钥（3，3337）和私钥（2147，3337）；（2）测试消息摘要MD生成：写入消息（明文信息）不一样得到消息摘要就有所区分，不过在产生消息摘要时所使用计算方法是一样即MD5算法，该算法关键是其中四轮循环，假如四轮循环中一个细节出了问题则所产生MD便是相差极远，如若明文信息是dfgfhfhgjk则得到消息摘要A4127B4881D24B01A85696477A07C17C，若明文信息是cvnjj则得到消息摘要是A1E2C15FF4C9F4D407EF33D1AC56C632；（3）测试数字署名生成：依据RSA算法加密原理对不一样消息摘要MD进行加密运算，得到便是不一样数字署名DS；若消息摘要MD是A1E2C15FF4C9F4D407EF33D1AC56C63