RSA数字签名算法的模拟实现.doc

河北大学2010级网络安全概论学年论文（课程设计）RSA数字签名算法的模拟实现摘 要本程序为简易版RSA算法加密解密过程的模拟实现。程序分为加密和验证两部分。根据课上所学的MD5加密过程，以及RSA算法，本程序采用MD5算法，先对文件内容进行加密，得到文字摘要；再利用RSA算法的私钥，对文字摘要进行加密，得到数字签名。在验证部分，用RSA公钥对数字证书签名解密，得到文字摘要S1，再将需要验证的文档用公用的MD5算法处理，得到文字摘要S2，检验文字摘要S1与S2的一致性，从而断定原文是否被篡改。程序采用树形图对文件进行直观的显示管理。采用文本文档存储数字签名。 关键词：RSA MD5 文字摘要 数字签名AbstractThis program is simple version of the RSA algorithm encryption and decryption process simulation. The procedures are divided into two parts, encryption and authentication. Lessons learned based on the MD5 encryption process, as well as RSA algorithm, the procedures used MD5 algorithm, first pairs contents of the file carry on encrypt, to obtain text abstract; re-use RSA algorithms private key, encryption for text abstract, obtain the digital signature. In the verification part, with the RSA algorithms public key pairs of digital certificate signature decryption, get text abstract S1, and then using a public MD5 algorithm encryption the document which need to be verify, to obtain text abstract S2, text the consistency of S1 and S2, thereby conclude that original text whether the been tampered with. Program uses the file tree intuitively display management the files. Adopt text document storage digital signatures.Key words：RSA MD5 Text abstract Digital signature目 录一 引言11.1理论背景11.2教学目的11.3任务和要求11.4意义11.5论文结构安排1二 问题分析22.1程序要求22.2实验原理22.2.1 MD522.2.2 RSA算法2三 实验设计33.1设计流程图33.2关键问题及算法设计33.2.1素数判定33.2.2互质的判断33.2.3乘法逆元求解43.2.4快速幂模算法43.2.5文字摘要生成53.2.6文字摘要加密53.3数据处理63.3.1树形图显示63.3.2文件存取6四 实验实现74.1整体界面如下设计：74.2文件操作84.3加密区8五 结束语15六 源代码16河北大学2010级网络安全概论学年论文（课程设计）一 引言1.1理论背景RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和Leonard Adleman开发的，是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有的密码攻击，已被ISO推荐为公钥数据加密标准。RSA是第一个能同时用于加密和数字签名的算法，采用公开密钥密码体制，即使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。通常RSA先生成一对密钥，其中之一是保密的，由用户保存；另一个为公开密钥，可对外公开，甚至可以在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。1.2教学目的通过模拟RSA数字签名算法，了解RSA数字签名体制原理，掌握一般数字签名算法的工作过程。1.3任务和要求1、实现RSA算法的参数选择；2、用MD5算法得到给定电子文档的信息摘要；3、将信息摘要变换为大整数形式，并在其上使用RSA数字签名体制进行签名，得到电子文档的数字签名；4、给定电子文档及其数字签名，判断电子文档的完整性和真实性。1.4意义通过模拟RSA数字签名算法，了解RSA算法的加密解密原理和过程，提升学生分析实际问题的能力以及动手能力，为今后在相关领域开展工作打下基础。1.5论文结构安排第一章、引言，说明课程设计理论背景、目的、要求和意义以及论文结构安排。第二章、问题分析，写出程序要求和主要算法原理。第三章、实验设计，包括流程图和各个功能的原理和代码实现。第四章、实验实现和成员分工，结合截图说明各个部件的功能以及小组成员分工。第五章、结束语，总结课程设计的体会。二 问题分析2.1程序要求模拟实现RSA数字签名的加密、解密和验证过程。2.2实验原理2.2.1 MD5MD5即Message-Digest Algorithm 5（信息摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，又译摘要算法、哈希算法。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理。MD5在本程序中起到的作用是让大容量信息在用数字签名签署私人密钥前，被“压缩”成一种保密的格式，就是把一个任意长度的字节串变换成一定长的十六进制数字串。MD5以512位分组处理输入的信息，且每一分组又被划分为16个32为子分组，经过一系列的处理后，算法的输入由32位分组组成，将这四个32位分组级联后将生成一个128位散列值。此处我们称这个128位的散列值为文件摘要。对于原始文件的大量信息进行整合，所得到文件摘要与原文保持一致性，且具有唯一性，为证明文件是否在传输过程中被篡改，提供了可靠的证据。2.2.2 RSA算法RSA的算法涉及三个参数，n、e1、e2。其中，n是两个大素数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求（e2*e1）mod（p-1）*（q-1）=1。（n，e1）（n，e2）就是密钥对。其中（n，e1）为公钥，（n，e2）为私钥。RSA加密与解密的算法完全相同，设A为明文，B为密文，则：A=Be2 mod n；B=Ae1 mod n。e1和e2可以互相使用，即：A=Be1 mod n；B=Ae2 mod n。本程序，主要是利用RSA算法的原理进行的操作，对于过程有个细致的操作。三 实验设计3.1设计流程图对于简单RSA模拟程序设计，现设计好RSA算法中的密钥，根据自设的P、Q值算出私钥，组合好后期所需要的公钥与私钥。选择要加密的文本，对其用公钥加密，等到数字签名，并加以保存。验证过程将原文进行MD5算法加密，得到文字摘要a；对于保存的数字签名，用保存的私钥进行解密，等到文字摘要b，将两个文字摘要进行比较，验证一致性。如下图：输入两个素数p、q计算n=p*q和（p-1）*（q-1）选定e1，计算e2利用RSA加密文字摘要利用MD5加密给定电子文档利用RSA解密数字签名验证利用MD5加密要验证的电子文档3.2关键问题及算法设计3.2.1素数判定在本程序中，对于素数判定很重要，素数P、Q的输入需要验证，在这里设计一个函数sushu ()，利用循环找其可能存在的因数，判断是否为素数。int sushu(long m)int i;for(i=2;i*i=d )?f:d;y3 = ( f=d )?d:f;while( 1 ) if ( y3 = 0 ) *result = x3; return 0; if ( y3 = 1 ) *result = y2; return 1; q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3;x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;3.2.4快速幂模算法在加密解密时都要用到类似A B（mod C）的计算，当指数B较大时，如果先计算A B的值时间较慢，且结果过大会溢出。依据模运算的性质（a*b）mod n=（a mod n）*（b mod n）mod n 可以将A B分解为较小几个数的乘积分别进行模运算，利用将指数分解成二进制，根据其分解的过程，逆推将原来的算式分解成较小的数相互叠乘的形式，最后用迭代法计算。例如（3 999）可以分解为(3 512) * (3 256) * (3 128) * (3 64) * (3 32) * (3 4) * (3 2) * 3 这样只要做16次乘法。把999转为2进制数：1111100111，其各位就是要乘的数。根据转化为二进制的逆推过程，可得到算式(31)2 * 31)2 * 31)2* 31)2 * 31)2 * 30)2 * 30)2 * 31)2 * 31)2 * 31所以程序中要有函数int a_b_Mod_c（long a, long b, long c）计算a b mod c的值并返回结果。int a_b_Mod_c(long a, long b, long c) int digit32;long i,k,resualt = 1; i = 0; while(b) digiti+ = b%2; b = 1; for(k = i-1; k = 0; k-) resualt=(resualt*resualt)%c; if(digitk=1) resualt=(resualt*a)%c; return resualt;3.2.5文字摘要生成本程序采用编写环境Visul Studio中命名空间System.Security.Cryptography，用其已有的MD5算法运行在本程序中。string str = textBox1.Text;byte result = Encoding.Default.GetBytes(textBox1.Text.Trim();MD5 md5 = new MD5CryptoServiceProvider();byte output = md5.ComputeHash(result);textBox3.Text = BitConverter.ToString(output).Replace(-, );3.2.6文字摘要加密本程序中得到的文字摘要，是根据原文经MD5算法得到的32位16进制的数字串。本程序采用对文字摘要进行逐位加密的方法，32为数字串存放在数组中，循环加密。在循环中，先将16进制转化为十进制，再利用加密公式对其加密，得到新的数字，显示在文本框中。for (int i = 0; i txtMshort.Text.Length; i+) string str = txtMshort.Text.Substring(i, 1);/逐位读取32位数字串 char key = Convert.ToChar(str); switch (key)/16进制转变为10进制 case A: zhuanhuai = 10; break; case B: zhuanhuai = 11; break; . default: break; sta.jiami(zhuanhuai);/加密 shuzhengi = (int)sta.MESSAGE; rtxtMnum.Text = rtxtMnum.Text + shuzhengi + -;/显示class类：using System;using System.Collections.Generic;using System.Text;using System.Windows.Forms;namespace MyWork class Rsamine private long pzn = 0; private long qzn = 0; private long emn = 0; private long N = 0; private long N1 = 0; private long dmn = 0; private long message = 0; public Rsamine() pzn = 0; qzn = 0; emn = 0; N = 0; N1 = 0; dmn = 0; message = 0; public long PZN get return pzn; set pzn = value; public long QZN get return qzn; set qzn = value; public long EMN get return emn; set emn = value; public long DMN get return dmn; public long Read_N() return N; public long MESSAGE get return message; public int gcd(long a, long b) if (b = 0) return (int)a; return gcd(b, a % b); public bool sushu(long m) int i; for (i = 2; i * i = d) ? f : d; y3 = (f = d) ? d : f; while (true) if (y3 = 0) result0 = x3; result1 = 0; return result; if (y3 = 1) MessageBox.Show(随机密钥已生成！); result0 = y2; result1 = 1; return result; q = x3 / y3; t1 = x1 - q * y1; t2 = x2 - q * y2; t3 = x3 - q * y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; public int a_b_Mod_c(long a, long b, long c) int digit = new int4000; long i, k, resualt = 1; i = 0; while (b != 0) digiti+ = (int)b % 2; b = 1; for (k = i - 1; k = 0; k-) resualt = (resualt * resualt) % c; if (digitk = 1) resualt = (resualt * a) % c; return (int)resualt; public void input_P_Q() if (pzn = 0) MessageBox.Show(素数p值为空，请输入); return; else if (!sushu(pzn) MessageBox.Show(输入的p值非素数); return; if (qzn = 0) MessageBox.Show(素数q值为空，请输入); return; else if (!sushu(qzn) MessageBox.Show(输入q值非素数); return; N = pzn * qzn; N1 = (pzn - 1) * (qzn - 1); public void input_E() if (pzn = 0) | (qzn = 0) MessageBox.Show(没有输入素数p或是输入q); if (emn = 0) MessageBox.Show(没有输入e值); if (gcd(emn, N1) != 1) MessageBox.Show(输入的E值不与 + N1 + 互质，其重新输入); long result = new long2; result = ExtendedEuclid(emn, N1); if (result1 = 1) dmn = result0; else MessageBox.Show(私钥算法错误); emn = 0; public void jiami(long a) if (emn = 0) | (N = 0) MessageBox.Show(e或n值为空); return; if (a N) MessageBox.Show(明文应小于 + N + ,错误); return; long c; c = a_b_Mod_c(a, emn, N); message = c; public void jiemi(long c) if (dmn = 0) | (N = 0) MessageBox.Show(d或n值为空); return; long a = 0; a = a_b_Mod_c(c, dmn, N); message = a; 3.3数据处理3.3.1树形图显示对于文件的操作，为了便于用户直观的查看和操作，利用树形图显示所有文件，在程序设计的过程中，可调用treeview控件进行具体的设计。3.3.2文件存取由于实验要求，要将数字证书进行存储，以及为了对树形图进一步操作（读取，编写）的实现，此处文件管理显然成为了本程序的一个重要组成部分，程序中，利用C#流、文件操作进行了实现。四 实验实现4.1整体界面如下设计：4.2加密4.3解密五 结束语首先，本程序用C#编写，因此在窗体实现部分比较容易，分为主窗体Form1和用于提示的操作步骤的窗体About，但由于技术和时间有限，窗体的美化还有待提高。此外，在程序编写过程中，遇到了错误和意想不到的结果，但我们团队协同合作，通过查阅资料，多次尝试，突破了重重困难。最后，本程序虽然功能完善，但也存在不少瑕疵，不过这是和同组人员共同努力的结果，在这个过程中，不仅提高了我们每个人的编程能力，还使得我们的团队合作能力得到了提升，可谓受益匪浅。小组成员:井启超、王海利六 源代码using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;using System.Security.Cryptography;using System.IO;namespace MyWork public partial class MainForm : Form private Rsamine sta = new Rsamine(); public MainForm() InitializeComponent(); void button1_Click_1(object sender, EventArgs e) if (textBox1.Text = ) MessageBox.Show(文档区不能为空！); else byte result = Encoding.Default.GetBytes(textBox1.Text.Trim(); MD5 md5 = new MD5CryptoServiceProvider(); byte output = md5.ComputeHash(result); textBox2.Text = BitConverter.ToString(output).Replace(-, ); int zhuanhua = new inttextBox2.Text.Length; int shuzheng = new inttextBox2.Text.Length; for (int i = 0; i textBox1.Text.Length; i+) string str = textBox1.Text.Substring(i, 1); char key = Convert.ToChar(str); switch (key) case A: zhuanhuai = 10; break; case B: zhuanhuai = 11; break; case C: zhuanhuai = 12; break; case D: zhuanhuai = 13; break; case E: zhuanhuai = 14; break; case F: zhuanhuai = 15; break; case 1: zhuanhuai = 1; break; case 2: zhuanhuai = 2; break; case 3: zhuanhuai = 3; break; case 4: zhuanhuai = 4; break; case 5: zhuanhuai = 5; break; case 6: zhuanhuai = 6; break; case 7: zhuanhuai = 7; break; case 8: zhuanhuai = 8; break; case 9: zhuanhuai = 9; break; case 0: zhuanhuai = 0; break; default: break; sta.jiami(zhuanhuai); shuzhengi = (int)sta.MESSAGE; textBox3.Text = textBox3.Text + shuzhengi + -; textBox3.Text = textBox3.Text.Substring(0, (textBox3.Text.Length - 1); private void button2_Click(object sender, EventArgs e) /解密 if (textBox3.Text = ) MessageBox.Show(数字签名不能为空！); else string temp = textBox3.Text.Split(-); int zhuanhua = new int32; char wenzhai = new char32; for (int i = 0; i temp.Length; i+) int key = Convert.ToInt32(tempi); sta.jiemi(ke