RSA数字签名算法的模拟实现
摘要
本程序为简易版RSA算法加密解密过程的模拟实现。
程序分为加密和验证两部分。根据课上所学的MD5加密过程，以及RSA算法，本程序采用MD5算法，先对文件内容进行加密，得到文字摘要；再利用RSA算法的私钥，对文字摘要进行加密，得到数字签名。在验证部分，用RSA公钥对数字证书签名解密，得到文字摘要S1，再将需要验证的文档用公用的MD5算法处理，得到文字摘要S2，检验文字摘要S1与S2的一致性，从而断定原文是否被篡改。程序采用树形图对文件进行直观的显示管理。采用文本文档存储数字签名。
关键词：RSA MD5 文字摘要数字签名
Abstract
This 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 algorithm's private key, encryption for text abstract, obtain the digital signature. In the verification part, with the RSA algorithm's 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
目录
一引言 (1)
1.1理论背景 (1)
1.2教学目的 (1)
1.3任务和要求 (1)
1.4意义 (1)
1.5论文结构安排 (1)
二问题分析 (2)
2.1程序要求 (2)
2.2实验原理 (2)
2.2.1 MD5 (2)
2.2.2 RSA算法 (2)
三实验设计 (3)
3.1设计流程图 (3)
3.2关键问题及算法设计 (3)
3.2.1素数判定 (3)
3.2.2互质的判断 (3)
3.2.3乘法逆元求解 (4)
3.2.4快速幂模算法 (4)
3.2.5文字摘要生成 (5)
3.2.6文字摘要加密 (5)
3.3数据处理 (6)
3.3.1树形图显示 (6)
3.3.2文件存取 (6)
四实验实现 (7)
4.1整体界面如下设计： (7)
4.2文件操作 (8)
4.3加密区 (8)
五结束语 (15)
六源代码 (16)
一引言
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 MD5
MD5即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=B^e2 mod n；B=A^e1 mod n。
e1和e2可以互相使用，即：
A=B^e1 mod n；B=A^e2 mod n。
本程序，主要是利用RSA算法的原理进行的操作，对于过程有个细致的操作。
三实验设计
3.1设计流程图
对于简单RSA模拟程序设计，现设计好RSA算法中的密钥，根据自设的P、Q值算出私钥，组合好后期所需要的公钥与私钥。选择要加密的文本，对其用公钥加密，等到数字签名，并加以保存。验证过程将原文进行MD5算法加密，得到文字摘要a；对于保存的数字签名，用保存的私钥进行解密，等到文字摘要b，将两个文字摘要进行比较，验证一致性。如下图：
3.2关键问题及算法设计
3.2.1素数判定
在本程序中，对于素数判定很重要，素数P、Q的输入需要验证，在这里设计一个函数sushu ()，利用循环找其可能存在的因数，判断是否为素数。
int sushu(long m)
{
int i;
for(i=2;i*i<=m;i++)
if(m%i==0)return 0;
return 1;
}
3.2.2互质的判断
因为存在e1与（p-1）*（q-1）互质，所以判定互质也是必要的问题。设计函数bool gcb（a，b），利用辗转相处法判定。
int gcd(long a, long b)
{
if(b == 0)return a;
return gcd(b, a % b);
}
3.2.3乘法逆元求解
因为需要计算私钥d= e ?-1(modψ(n))，所以有函数long ExtendedEuclid（）计算d并返回d的值，这里用到扩展欧几里德算法。大体思路与欧几里德算法一致：
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b 组合整数d，m，n称为组合系数。当d=1时，有ma + nb = 1 ，此时可以看出m 是a模b的乘法逆元，n是b模a的乘法逆元。
long ExtendedEuclid(long f,long d ,long *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;x2 = y1 = 0;x3 = ( f>=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 digit[32];long i,k,resualt = 1;
i = 0;
while(b)
{ digit[i++] = b%2;
b >>= 1; }
for(k = i-1; k >= 0; k--)
{ resualt=(resualt*resualt)%c;
if(digit[k]==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 = https://www.doczj.com/doc/2018962247.html,puteHash(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':
zhuanhua[i] = 10;
break;
case'B':
zhuanhua[i] = 11;
break;
......
default:
break;
}
sta.jiami(zhuanhua[i]);//加密
shuzheng[i] = (int)sta.MESSAGE;
rtxtMnum.Text = rtxtMnum.Text + shuzheng[i] + "-";//显示
}
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 <= m; i++)
if (m % i == 0)
return false;
return true;
}
public long[] ExtendedEuclid(long f, long d)
{
long[] result = new long[2];
long x1, x2, x3, y1, y2, y3, t1, t2, t3, q; x1 = y2 = 1;
x2 = y1 = 0;
x3 = (f >= d) ? f : d;
y3 = (f >= d) ? d : f;
while (true)
{
if (y3 == 0)
{
result[0] = x3;
result[1] = 0;
return result;
}
if (y3 == 1)
{
MessageBox.Show("随机密钥已生成！"); result[0] = y2;
result[1] = 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 int[4000];
long i, k, resualt = 1;
i = 0;
while (b != 0)
{
digit[i++] = (int)b % 2;
b >>= 1;
}
for (k = i - 1; k >= 0; k--)
{
resualt = (resualt * resualt) % c;
if (digit[k] == 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 long[2];
result = ExtendedEuclid(emn, N1);
if (result[1] == 1)
dmn = result[0];
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整体界面如下设计：
五结束语
首先，本程序用C#编写，因此在窗体实现部分比较容易，分为主窗体Form1和用于提示的操作步骤的窗体About，但由于技术和时间有限，窗体的美化还有待提高。
此外，在程序编写过程中，遇到了错误和意想不到的结果，但我们团队协同合作，通过查阅资料，多次尝试，突破了重重困难。
最后，本程序虽然功能完善，但也存在不少瑕疵，不过这是和同组人员共同努力的结果，在这个过程中，不仅提高了我们每个人的编程能力，还使得我们的团队合作能力得到了提升，可谓受益匪浅。
小组成员:井启超、王海利
六源代码
using System;
using System.Collections.Generic;
using https://www.doczj.com/doc/2018962247.html,ponentModel;
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 = https://www.doczj.com/doc/2018962247.html,puteHash(result);
textBox2.Text = BitConverter.ToString(output).Replace("-", "");
int[] zhuanhua = new int[textBox2.Text.Length];
int[] shuzheng = new int[textBox2.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':
zhuanhua[i] = 10;
break;
case'B':