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

课程实践汇报书课程名称： 密码学和网络安全课程实践 题 目：实现数字署名RSA算法设计和实现学生姓名： 专 业：班 别： 学 号： 指导老师： 日 期： 年 6 月 18 日实现数字署名RSA算法设计和实现摘 要伴随计算机网络和信息技术发展，信息安全在各领域发挥着越来越关键作用，其中密码学已成为信息安全技术关键，本文关键介绍了信息加密技术应用。 RSA算法是现在公认在理论和实际应用中最为成熟和完善一个公钥密码体制，它是第一个既能用于数据加密也能用于数字署名算法，是公钥密码体制代表。数字署名是起到身份认证、核准数据完整性一个信息安全技术。它经过认证技术来识别真伪。RSA数字署名体制使用是RSA公开密钥密码算法进行数字署名。本文关键内容包含：第一,对RSA算法进行系统介绍；第二,介绍RSA数字署名部分基础概念和数字署名理论实现过程；第三详述RSA数字署名设计和实现，关键实现模块包含RSA密钥产生（一对公钥和私钥），RSA加密算法和解密算法实现，；第四,对该系统进行了整体测试和分析改善。关键字：RSA算法；加密； 解密；RSA数字署名 目 录 1 引言31.1 课题研究背景31.2 课题研究意义32 RSA算法和RSA数字署名算法概念设计32.1 RSA算法概念和原理32.1.1 RSA算法介绍32.1.2 RSA算法实现原理32.2 RSA数字署名基础概念和RSA数字署名算法实现原理42.2.1 RSA数字署名基础概念42.2.2 RSA数字署名算法实现原理53 RSA数字署名逻辑设计和实现63.1 RSA数字署名总体设计63.1.1 RSA数字署名所需实现功效63.1.2 总体要求和设计63.2 各部分设计实现73.2.1 密钥产生实现73.2.2 产生消息摘要设计实现103.2.3 数字署名设计实现123.2.4 验证数字署名设计和实现153.2.5 RSA数字署名运行结果184 软件整体测试和分析改善184.1软件整体测试184.2 性能分析和改善设想19开发体会19参考文件201 引言1.1 课题研究背景伴随电子信息技术快速发展，人类已步入信息社会。不过因为整个社会形成了一个巨大计算机网络，任何一个计算机网络出现安全问题，全部会影响整个国家网络安全，所以信息安全、计算机网络安全问题已引发了人类高度重视。网络安全方法应是能全方位地针对多种不一样威胁和脆弱性，这么才能确保网络信息保密性、完整性和可用性。现代密码学已成为信息安全技术关键，密码学是以研究通信安全保密学科，即研究对传输信息采取何种秘密变换以预防第三者对信息窃取。RSA公钥加密算法是第一个既能用于数据加密也能用于数字署名算法。它易于了解和操作，也十分流行。伴随越来越多商业应用和标准化工作，RSA已经成为最具代表性公钥加密技术。现今，网上交易加密连接、网上银行身份验证、多种信用卡使用数字证书、智能移动电话和存放卡验证功效芯片等，大多数使用RSA技术。1.2 课题研究意义伴随电子商务发展，网络上资金电子交换日益频繁，怎样预防信息伪造和欺骗成为很关键问题。现在相关数字署名研究关键集中点是基于公钥密码体制数字署名。手写署名每一项业务全部是数字署名潜在用场。数字署名能够提供数据完整性、真实性和不可否认性。数字署名技术在身份识别和认证、数据完整性、抵赖等方面含有其它技术无法替换作用，它在军事、电子商务和电子政务等领域有着极广泛应用。而在公钥体制中，RSA是一个较为完善公钥密码算法，不仅能够同时用于加密和数字署名，而且易于了解和操作，是被广泛研究公钥密码算法。所以，基于RSA数字署名含有较强研究性和实际应用意义。2 RSA算法和RSA数字署名算法概念设计2.1 RSA算法概念和原理2.1.1 RSA算法介绍RSA算法是一个公钥密码算法,实现RSA算法包含生成RSA密钥，加密和解密数据。RSA算法是第一个能同时用于加密和数字署名算法，也易于了解和操作。RSA是被研究得最广泛公钥算法。RSA缺点关键有：A)产生密钥很麻烦，受到素数产生技术限制，所以难以做到一次一密。B)分组长度太大，为确保安全性，n 最少也要 600 bits。2.1.2 RSA算法实现原理1) 随机选择两个不一样素数p和q，它们宽度是密钥宽度二分之一。2) 计算出p和q乘积n 。3) 在2和(n)之间随机选择一个数e , e 必需和(n)互素，整数e用做加密密钥（其中(n)=(p-1)*(q-1)）。4) 从公式ed 1 mod (n)中求出解密密钥d 。5) 得公钥（e ，n ）, 私钥 (d , n) 。6) 公开公钥，但不公开私钥。7) 将明文P (假设P是一个小于n整数)加密为密文C，计算方法为：C = Pe mod n;8) 将密文C解密为明文P，计算方法为：P=Cd mod n;然而只依据n和e（不是p和q）要计算出d是不可能。所以，任何人全部可对明文进行加密，但只有授权用户（知道d）才可对密文解密。2.2 RSA数字署名基础概念和RSA数字署名算法实现原理2.2.1 RSA数字署名基础概念RSA数字署名体制使用了RSA公开密钥密码算法进行数字署名，鉴于RSA算法在实践中已经被证实了安全性，RSA数字署名体制在很多安全标准中得以广泛应用。ISO/IEC 9796和ANSI X9.30-199X 和美国联邦信息处理标准FIPS 186-2已经将RSA作为推荐数字署名标准算法之一。RSA数字署名算法，包含署名算法和验证署名算法。它是利用RSA算法加密和解密算法原理进行一个数字署名，实际上是经过一个哈希函数来实现（本设计是经过MD5算法）产生消息摘要MD来实现所需加密对象。数字署名特点是它代表了消息特征，消息假如发生改变，数字署名值也将发生改变，不一样消息将得到不一样数字署名。安全数字署名使接收方能够得到确保：消息确实来自发送方。因为署名私钥只有发送方自己保留，她人无法做一样数字署名，假如第三方冒充发送方发出一个消息，而接收方在对数字署名进行解密时使用是发送方公开密钥，只要第三方不知道发送方私有密钥，加密出来数字署名和经过计算数字署名肯定是不相同，这就提供了一个安全确实定发送方身份方法，即数字署名真实性得到了确保。数字署名类似手书署名，它含有以下性质：1）能够验证署名产生者身份，和产生署名日期和时间；2）能用于证实被签消息内容；3）数字署名可由第三方验证，从而能够处理通信双方争议。为了满足数字署名这些要求，比如，通信双方在发送消息时，既要预防接收方或其它第三方伪造，又要预防发送方因对自己不利而否认，也就是说，为了确保数字署名真实性。数字署名原理是：（发送方和接收方依据要求各自产生自己一对公钥和私钥）1）被发送文件采取某种算法对原始消息进行运算，得到一个固定长度数字串，称为消息摘要（MD），不一样消息得到消息摘要各异，不过对相同消息它消息摘要却是唯一；2）发送方生成消息消息摘要，用自己私钥对摘要进行加密来形成发送方数字署名；3）这个数字署名将作为消息附件和消息一同用接收方公钥进行加密，将加密后密文一起发送给接收方；4）接收方首先把接收到密文用自己私钥解密，得到原始消息和数字署名，再用发送方公钥解密数字署名，随即用一样算法计算出消息摘要；5）假如计算出来消息摘要和发送方发送给她消息摘要（经过解密数字署名得到）是相同，这么接收方就能确定数字署名确实是发送方，不然就认为收到消息是伪造或是中途被篡改。数字署名原理图如2-1所表示 A BEDED 用A私钥加密 用B公钥 用B私钥 用A公钥解密 数字署名 加密 解密 核实署名图2-1 数字署名原理2.2.2 RSA数字署名算法实现原理RSA数字署名算法分为以下两个步骤： 1） 署名算法（包含两步：消息摘要计算，RSA加密）(1)消息摘要MD计算： 消息在署名前首先经过MD5计算，生成128位消息摘要 ；MD5函数是一个单向散列函数，它将任意长度消息压缩成128位消息摘要。应用MD5单向性（即给定散列值,计算消息极难）和抗碰撞性(即给定消息M，要找到另一消息M并满足二者散列值极难)，能够实现信息完整性检验。另外该函数设计不基于任何假设和密码体制而直接结构，实施速度快，是一个被广泛认可单向散列算法。(2)对MD作RSA加密算法：采取署名者私钥加密消息摘要，得到加密后字符串即数字署名；2）验证署名算法 （RSA解密、对消息摘要计算和比较）验证署名算法包含两步：RSA解密得署名者消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证署名过程输入为消息，署名者公钥，署名；输出为验证结果，即是否是正确署名。(1)RSA解密： 署名实际是加密消息摘要，用以上所述RSA解密方法采取署名者公钥对这个加密消息摘要解密，解密结果应为128位消息摘要。(2)消息摘要计算和比较： 验证者对消息用MD5算法重新计算，得到验证者自己消息摘要。验证者比较解密得到消息摘要和自己消息摘要，假如二者相同，则验证成功，能够确定消息完整性及署名确实为署名者；不然，验证失败，确定署名被冒充或是被篡改。3 RSA数字署名逻辑设计和实现3.1 RSA数字署名总体设计3.1.1 RSA数字署名所需实现功效在本软件中需要实现功效有以下多个：（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+开发环境，采取是Microsoft Visual c+ 6.0运行环境。3.2 各部分设计实现3.2.1 密钥产生实现在密钥产生部分中起决定性作用是素数选择，对随机数作素性检测，若经过则为素数；不然增加一个步长后再做素性检测，直到找出素数。素性检测采取Fermat测试。这个算法理论依据是费尔马小定理：假如m是一个素数，且a不是m倍数，那么依据费尔马小定理有：a m-1=1 ( mod m)。 实际应用时：a m-1 = 1 ( mod m) a m = a ( mod m) a= a m ( mod m)， 所以对于整数m，只需计算a m ( mod m)，再将结果和a比较，假如二者相同，则m为素数。选择a=2，则a一定不会是任何素数倍数。依据所选素数不一样产生不一样密钥。密钥理论产生模块步骤图图3-1所表示：产生任意素数p和q计算n=p*q计算ou_la=(p-1)(q-1)选择e作为公钥计算d作为私钥图3-1 密钥产生密钥产生部分代码实现：CString str;/第一步 产生任意素数GeneratePrimeNumbers();/第二步 计算 n=p*qm_n = m_Prime1 * m_Prime2;/第三步 0=(p-1)(q-1)m_Undef = (m_Prime1-1) * (m_Prime2-1);/第四步 选择eSelectE();/第五步 计算DCalculateD();/显示公钥和私钥/(1) 公钥 KU=e,nstr.Format(%d, %d,m_e,m_n);m_public_key.SetWindowText(str);/(2) 私钥KU=d,nstr.Format(%d, %d,m_d,m_n);m_private_key.SetWindowText(str);/ 选择一个 e 使 e和 m_Undef互素/选择e函数实现SelectE() CString str;for(float i=2;i100000;i+)if(IsRelativePrime(float)m_Undef,(float)i)m_e=(long)i;return;/互为素数函数实现IsRelativePrime(float X,float Y) float R;/输入: X,Yif(XY)/假如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) return false;else return true;/互素/ 计算D函数实现CalculateD()float d;long d_dash;CString str;for(float k=1;k100000;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()CString str;UpdateData(TRUE);/经过以下两个函数可取得两个大素数，但增加了计算复杂性，为了方便，直接给定素数/m_Prime1 = FindPrime(1);/m_Prime2 = FindPrime(m_Prime1);m_Prime1=47;m_Prime2=71;3.2.2 产生消息摘要设计实现计算消息摘要理论实现步骤图图3-2所表示：初始化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个输入子块M0，M1，.M15，或表示为Mi，其中i为0-15；t是常量数组，包含64个元素，每个元素为32位，数组t表示为t1，t2，t64，或tk，k为1-64；MD5循环四轮操作过程用下式表示： a=b+(a+proccessP(b,c,d)+Mi+Tk)s) (s表示循环左移s位)产生消息摘要关键代码以下：int i;int Index;/初始化MD5所需常量Init(); /计算追加长度Append(WriteMessage.length();/对原始信息进行补位for( i=0;im_AppendByte;i+)if(i=0) WriteMessage+=(unsigned char)0x80;else WriteMessage+=(unsigned char)0x0; /将原始信息长度附加在补位后 数据后面for( i=0;i8;i+) WriteMessage+=m_MsgLeni;/位块数组unsigned char x64=0;/循环，将原始信息以64字节为一组拆分进行处理for( i=0,Index=-1;iWriteMessage.length();i+)x+Index=WriteMessagei;if(Index=63)Index=-1;/将64字节位转换为16个字节Transform(x);/将寄存器ABCD最终值转换为16进制返回给用户return ToHex(UpperCase);3.2.3 数字署名设计实现 数字署名理论实现步骤图图3-3所表示，数字署名，就是经过在数据单元上附加数据，或对数据单元进行加密变换，从而使接收者能够确定数据起源和完整性。数字署名是预防她人对传输文件进行破坏，和确定发信人身份手段。数字署名中加密算法就是应用RSA加密原理，而它验证算法则是应用RSA解密原理。 开始得到数字署名得到消息摘要MD用私钥d 加密MD结束图3-3 数字署名实现步骤RSA加密、解密过程全部为求一个整数整数次幂，再取模。假如按其含义直接计算，则中间结果很大，有可能超出计算机所许可整数取值范围。为了减小中间结果和提升加、解密运算中指数运算有效性，本设计采取了快速指数算法。它运算过程为（假如要算am mod n）：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位为一组 一个字符一组char message200; /从文本框中得到消息摘要 m_message.GetWindowText(message,200);len=strlen(message); char showstr1000=;int NO_BITS=32;double c=0,d=1;char bits100;double n=(double)m_n;unsigned char ch;double data;/19;long i,k=NO_BITS;int sizeof_d=sizeof(double); /将十进制数私钥d转换为二进制D_to_B(m_d,32,bits);/得到适宜字节GetOnlyProperBits(bits);k=NO_BITS = strlen(bits)-1;for(int ii=0;ii=0;i-)c=2*c;d=fmod(d*d,n);if(bitsNO_BITS-i = 1)c=c+1;d=fmod(data*d,n);/ 从d中读取字符放入result中 resultii=d; /把字符串变为十六进制数后连接字符串 strcat(showstr,longtohex(d);/结束循环 /显示结果m_result.SetWindowText(showstr); /字符串变为16进制数函数实现longtohex(long x) char str8; int i=0; /商 int a; /余数 int b; long tt=x; while(tt=16) a=tt/16; b=tt%16; switch(b) case 0 : stri=0; break; case 1 : stri=1; break; case 2 : stri=2; break; case 3 : stri=3; break; case 4 : stri=4; break; case 5 : stri=5; break; case 6 : stri=6; break; case 7 : stri=7; break; case 8 : stri=8; break; case 9 : stri=9; break; case 10 : stri=A; break; case 11 : stri=B; break; case 12 : stri=C; break; case 13 : stri=D; break; case 14 : stri=E; break; case 15 : stri=F; break; ; i+; tt=a; stri=0; strrev(str); return str;3.2.4 验证数字署名设计和实现得到数字署名用公钥e解密数字署名得到消息摘要（解密信息）开始结束图3-4 验证数字署名步骤 验证数字署名正确和成功性，关键是比较得到两次消息摘要是否一样，假如验证方用署名方公钥解密得到消息摘要（即是本设计中得到解密信息）和她自己计算得到消息摘要（在本系统中为第一次计算得到消息摘要）是一样，则证实署名是正确，没有被篡改或是冒充，验证署名原理则是依据RSA解密算法，具体理论步骤图图3-4所表示：（在本设计中署名和验证署名全部在同一界面实现，不进行文件双方传输）验证数字署名过程时应用解密算法是RSA解密原理，而RSA解密过程也应用了求一个整数整数次幂，再取模运算。在此也采取了快速指数算法，具体算法过程同RSA加密过程中应用快速指数算法是一样。验证数字署名关键实现过程代码以下：int NO_BITS;double c=0,d=1;char bits100;double n=(double)m_n;double data;/19;long i,k; int sizeof_d=sizeof(double); /用于存放解密信息char message200; /将十进制数公钥e转换为二进制D_to_B(m_e,32,bits); GetOnlyProperBits(bits); k=NO_BITS = strlen(bits)-1;for(int j=0;j=0;i-)c=2*c;d=fmod(d*d,n);if(bitsNO_BITS-i = 1)c=c+1;d=fmod(data*d,n);/结束循环/从d中读取字符放入message中 messagej=d; /显示结果m_mingwen.SetWindowText(message);3.2.5 RSA数字署名运行结果图3-5 RSA数字署名运行结果在本软件中得到二个消息摘要：依据写入消息（明文信息）计算出来消息摘要、解密数字署名得到消息摘要（即是本设计中解密信息）。假如两个消息摘要是一样则证实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是A1E2C15FF4C9F4D407EF33D1AC56C632 则得到DS是DD6865036DC98523593FD6D36411F361F050，若消息摘要MD是66F753A8408C91EC0B16D91A1100902A则得到DS是1F1F98F2410D1F5931F366CDD61F236CD6DD6D693936C9350D；（4）测试数字署名真实是否（验证数字署名）：依据RSA算法解密原理对得到数字署名DS进行解密，得到是消息摘要，假如得到消息摘要和（2）中得到消息摘要是一样，则证实该数字署名是真实没有被冒充和篡改，数字署名DS 1F1F98F2410D1F5931F366CDD61F236CD6DD6D693936C9350D 依据解密得到消息摘要是66F753A8408C91EC0B16D91A1100902A 若依据明文信息得到消息摘要和解密得到消息摘要一样，则证实署名真实。4.2 性能分析和改善设想经过一系列测试，本软件存在较多需要改善和优化地方：（1）在素数任意产生时没有做到任意，本软件只产生了两个固定素数即47和71，所以在密钥产生时也就只有一对公钥和一对私钥，应该进行改善是在素数产生中增加对应函数来实现素数任意产生，方便生成不一样密钥；（2）在产生消息摘要时针正确仅是一系列字符串，即只能对字符串产生消息摘要而不能对文件产生消息摘要，进行改善是能同时对字符串和文件全部能计算出所对应消息摘要； （3）和（2）相关是数字署名中加密和解密也仅是字符串，而不能选择所加密和解密消息类型（字符串和文件），为了使这类软件能在实际应用中发挥愈加好作用所需要改善一个关键就是能把文件部分也加入该软件，使该软件能同时对字符串和文件发挥作用；（4）该软件署名和验证全部是在同一界面实现，而数字署名应该在两个不一样界面下完成即有发送方和接收方，则对应改善是能实现文件传送。开发体会本文讨论了RSA算法基础原理、基础实现和消息摘要产生所需要MD5算法和怎样利用RSA算法实现数字署名。RSA算法是一个安全技术，不过RSA算法安全性只是一个计算安全性，绝不是无条件安全性，这是由它理论基础决定。所以，在实现RSA算法过程中，每一步全部应尽可能从安全性考虑,而该设计中它安全性则依靠于素数选择。RSA数字署名提供了一个安全确实定发送方身份方法，即数字署名真实性得到了确保，预防了第三方冒充和篡改，肯定了数字署名真实性。经过此次课题实践，我充足了解到了RSA算法基础原理和基础实现步骤，RSA算法，它是第一个既能用于数据加密也能用于数字署名算法，是公钥密码体制代表。此次开发让我系统总结了这个学期所学知识，同时对以前所学知识有了更深入认识和利用，发觉自己在代码实现利用方面还存在很多不足，以后会努力更正，加强对所学知识了解和利用。参考文件1 谭浩强.C程序设计（第四版）M.北京：清华大学出版社，。 2 张焕国,唐明密码学导引M. 武汉：武汉大学出版社， 。