036_基于RSA的数字签名

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算法的解密原理对所加密的消息摘要即数字签名进行解密运算，得到对应的消息摘要（在本设计中标示的为解密信息），比较两个消息摘要，验证数字签名者的身份的真实与否； 【www.think58.com计算机毕业论文网】
5）提示信息完整、操作舒适、图形界面雅观。

[版权所有：http://think58.com]

本软件的总体设计都是基于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所示：

图3-1 密钥产生
密钥产生的部分代码实现：
CString str;
//第一步 产生任意素数
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(); [资料来源：http://think58.com]
//显示公钥和私钥
//(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()
{ CString str;
for(float i=2;i<100000;i++)
{
if(IsRelativePrime((float)m_Undef,(float)i))
{
m_e=(long)i;
return;
}
}
}
//互为素数的函数的实现
IsRelativePrime(float X,float Y)
{ float R;
//输入: 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)
return false;
else
return true;//互素
}
// 计算D的函数的实现
CalculateD()
{
float d;
long d_dash;
CString str;

copyright think58 [资料来源：http://www.THINK58.com]

for(float k=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()
{
CString str;
UpdateData(TRUE);
//通过以下两个函数可获得两个大素数，但增加了计算复杂性，为了方便，直接给定素数
// m_Prime1 = FindPrime(1);
// m_Prime2 = FindPrime(m_Prime1);
m_Prime1=47;
m_Prime2=71;
}
3.2.2 产生消息摘要的设计实现
计算消息摘要的理论实现流程图如图3-2所示：
think58好，好think58 [资料来源：www.THINK58.com]

图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位)
产生消息摘要的主要代码如下：
int i;int Index;
//初始化MD5所需常量
Init();
//计算追加长度
Append(WriteMessage.length());
//对原始信息进行补位
for( i=0;i<m_AppendByte;i++)
{
if(i==0) WriteMessage+=(unsigned char)0x80; 内容来自think58 [来源：http://think58.com]
else WriteMessage+=(unsigned char)0x0;
}
//将原始信息长度附加在补位后 的数据后面
for( i=0;i<8;i++) WriteMessage+=m_MsgLen[i];
//位块数组
unsigned char x[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进制返回给用户
return ToHex(UpperCase);
copyright think58

[来源：http://think58.com]