好久没上了，贴一个自己以前用C++写的程序，感觉不是特别的优雅。是一个64位的RSA。
首先，来介绍一个RSA算法的加密和解密原理。选择两个不同的大素数p和q，n是二者的乘积，即n＝p*q，使fn=(p-1)*(q-1)，随机选取正整数e，使其满足(e,fn)=1,即互素。则将（n，e）作为公钥。求出正数d，使其满足e*d=1(mod fn)，则将（n，d）作为私钥。加密算法：对于明文m，密文c=m的e次幂模n。解密算法：对于密文c，明文m=c的d次幂模n。
编写RSA，首先要解决的位数问题，一般语言所提供整型最高为64位，在RSA中，这种数实在太小，更何况要求幂。故要写一个高精度运算，要有加、减、乘、除、求模以及输入、输出、比较、整数转化为高精度等。高精度的算法一般网上可以找到。我进行了修改，具体的如下：
|
# include<iostream.h>
# include <string>
# include <math.h>
using namespace std;
# define maxsize 100
struct hp
{
int len;
int s[maxsize+1];
};
hp input(string str) //输入字符串形成高精度数
{
hp a;
int i;
while(str[0]=='0' && str.size()!=1)
str.erase(0,1);
a.len=(int)str.size();
for(i=1;i<=a.len;++i)
a.s[i]=str[a.len-i]-48;
for (i=a.len+1;i<=maxsize;++i)
a.s[i]=0;
return a;
}
void output(hp &y) //输出高精度数
{
int i;
for(i=y.len;i>=1;i--)
cout<<y.s[i];
}
hp add(hp &a,hp &b) //高精度加法c=a+b,返回c
{
hp c;
int i,len;
for(i=1;i<=maxsize;i++) c.s[i]=0;
if(a.len>b.len) len=a.len;
else len=b.len;
for(i=1;i<=len;i++)
{
c.s[i]+=a.s[i]+b.s[i];
if(c.s[i]>=10)
{
c.s[i]-=10;
c.s[i+1]++;
}
}
if(c.s[len+1]>0) len++;
c.len=len;
return c;
}
hp sub(hp &a,hp &b) //高精度减法c=a-b,返回c
{
hp c;
int i,len;
for(i=1;i<=maxsize;i++) c.s[i]=0;
if(a.len>b.len) len=a.len;
else len=b.len;
for(i=1;i<=len;i++)
{
c.s[i]+=a.s[i]-b.s[i];
if(c.s[i]<0)
{
c.s[i]+=10;
c.s[i+1]--;
}
}
while(len>1&&c.s[len]==0) len--;
c.len=len;
return c;
}
int com(hp &a,hp &b) //对a，b进行比较，若a>b,返回正数，相等时返回0，否则返回负数
{
int len;
if(a.len>b.len)
len=a.len;
else
len=b.len;
while(len>0 && a.s[len]==b.s[len])
len--;
if(len==0)
return 0;
else
return a.s[len]-b.s[len];
}
hp mul(hp &a,hp &b) //高精度乘法c = a * b,返回c
{
hp c;
int i,j,len;
for(i=1;i<=maxsize;i++) c.s[i]=0;
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
{
c.s[i+j-1]+=a.s[i]*b.s[j];
c.s[i+j]+=c.s[i+j-1]/10;
c.s[i+j-1]%=10;
}
len=a.len+b.len+1;
while(len>1&&c.s[len]==0) len--;
c.len=len;
return c;
}
void multiply10(hp &a) //高精度*10
{
int i;
for(i=a.len;i>=1;i--)
a.s[i+1]=a.s[i];
a.s[1]=0;
a.len++;
while(a.len>1&&a.s[a.len]==0) a.len--;
}
hp div(hp &a,hp &b)//高精度/高精度{d为余数}
{
hp c, d, e;
int i,len;
for(i=1;i<=maxsize;i++)
{
c.s[i]=0;
d.s[i]=0;
}
len=a.len;
d.len=1;
for(i=len;i>=1;i--)
{
multiply10(d);
d.s[1]=a.s[i];
while(com(d,b)>=0)
{
e = sub(d,b);
d=e;
c.s[i]++;
}
}
while(len>1&&c.s[len]==0) len--;
c.len=len;
return c;
}
hp mod(hp &a,hp &b)//高精度/高精度{d为余数}
{
hp c, d, e;
int i,len;
for(i=1;i<=maxsize;i++)
{
c.s[i]=0;
d.s[i]=0;
}
len=a.len;
d.len=1;
for(i=len;i>=1;i--)
{
multiply10(d);
d.s[1]=a.s[i];
while(com(d,b)>=0)
{
e = sub(d,b);
d=e;
c.s[i]++;
}
}
while(len>1&&c.s[len]==0) len--;
c.len=len;
return d;
}
hp cstr(int k) //整数k转化为高精度
{
char a[100];
hp x;
string str;
int len,i,t;
len=log10(k)+1;
for (i=len;i > 0; i--)
{
t=k%10;
k-=t;
k/=10;
a[i-1]='0'+t;
}
a[len]='\0';
for (i = 0; i < len; i++)
str+=a[i];
x=input( str);
return x;
}
hp app(hp temp, int k) //在高精度前面增加一位k
{
int len = temp.len + 1;
temp.s[len] = k;
temp.len = len;
return temp;
}
|
接着是素数的生成，用到的是Miller_Rabin算法。这一算法首先要产生一个随机数，判断是否为素数。在判断的过程中最重要的是求a的p次幂模n，如果这个算法没写好，就很容易溢出，或速度慢（可以说是没法运行）。
|
/* 定义0、1、2高精度数 */
hp zero = input("0");
hp one = input("1");
hp two = input("2");
/* 求a的p次幂模n */
hp exp_mod(hp a, hp p, hp n)
{
hp temp = one, y = a;
while (com(p, zero) != 0)
{
if (com(mod(p, two), one) == 0)
temp = mod(mul(temp, y), n);
y = mod(mul(y, y),n);
p = div(p, two);
}
return temp;
}
|
素数的判断如下：
|
/* 用来生成64比特的数，并转化为十进制的高精度数 */
hp make_64bit()
{
hp temp = zero;
hp exp_two = one;
for (int i = 0; i < 64; i++)
{
unsigned random = rand() % 2;
if (random == 1)
temp = add(temp, exp_two);
exp_two = mul(exp_two, two);
}
return temp;
}
/* Miller_Rabin算法来判断是否为素数 */
bool Miller_Rabin(hp n) //为素数返回false，为合数返回true
{
hp x = make_64bit();
hp m = sub(n, one); //m = n -1
hp i, y, k;
/* 将n-1分解成2的k次幂乘以m */
/* for (k = 1; m % 2 == 0; k++)*/
for(k=one;com(mod(m, two), zero) == 0;k = add(k, one))
m = div(m, two);
y=exp_mod(x,m,n); //y等于x的m次幂模n
if(com(y, one) == 0)
return false;
for(i=one; com(k, i) > 0; i = add(i, one))
{
if (com(mod(y, n), sub(n, one)) == 0 )
return false;
y = mod(mul(y,y), n);
}
return true;
}
|
之后，随便写个主函数，就可以产生64位的素数了（当然也能产生其他位数的）。
用产生的素数（比如p，q）就可以构造加密和解密算法了，这里除了要用到上面提到的函数外，还要用到的是求与fn=(p-1)*(q-1)互素的e，之后还要求得e的模逆，即e*d=1(mod fn)，具体如下：
|
/* 求a与b的最大公约数 */
hp GCD(hp a, hp b)
{
if (com(b, zero) == 0)
return a;
else
return GCD(b, mod(a, b));
}
/* 求u*x=1(mod m)中的x的值 */
hp moni(hp u, hp m)
{
hp r1 = m, r2 = u;
hp b1 = zero, b2 = one;
hp r3 = two, b3 = zero, q = zero;
while (com(r3, one) > 0)
{
r3 = mod(r1, r2);
q = div(r1, r2);
b3 = sub(add(b1, mul(q, m)), mul(q, b2));
b3 = mod(b3, m);
if (com(r3, one) > 0)
{
r1 = r2; r2 = r3;
b1 = b2; b2 = b3;
}
else
{
if (com(r3, one) == 0)
return mod((add(b3, m)), m);
else
{
cout<<"无解!"<<endl;
cout<<"(u, m) = ";
output(r2);
cout<<endl;
return zero;
}
}
}
return zero;
}
|
其他就不是什么问题了。
PS：本人菜鸟一个，可能会有很多问题，望指正。
|
|
