#include <iostream.h>
#include <math.h>
#include <stdio.h>
typedef int Elemtype;
Elemtype p,q,e; Elemtype fn; Elemtype m,c; int flag = 0;
typedef void (*Msghandler) (void);
struct MsgMap { char ch; Msghandler handler; }; /* 公钥 */
struct PU { Elemtype e; Elemtype n; } pu; /* 私钥 */
struct PR { Elemtype d; Elemtype n; } pr; /* 判定一个数是否为素数 */
bool test_prime(Elemtype m)
{
if (m <= 1) { return false; }
else if (m == 2) { return true; }
else {
for(int i=2; i<=sqrt(m); i++)
{
if((m % i) == 0)
{ return false; break; }
}
return true;
}
} /* 将十进制数据转化为二进制数组 */
void switch_to_bit(Elemtype b, Elemtype bin[32])
{
int n = 0;
while( b > 0) { bin[n] = b % 2; n++; b /= 2; } } /* 候选菜单,主界面 */
void Init()
{
cout<<"*********************************************"<<endl;
cout<<"*** Welcome to use RSA encoder***"<<endl;
cout<<"*** a.about ***"<<endl;
cout<<"*** e.encrypt ***"<<endl;
cout<<"*** d.decrypt ***"<<endl;
// cout<<"***s.setkey***"<<endl;
cout<<"*** q.quit***"<<endl;
cout<<"*********************************************"<<endl;
cout<<"press a key:"<<endl;
} /* 将两个数排序,大的在前面*/
void order(Elemtype &in1, Elemtype &in2)
{
Elemtype a = ( in1 > in2 ? in1 : in2);
Elemtype b = ( in1 < in2 ? in1 : in2);
in1 = a; in2 = b;
} /* 求最大公约数 */
Elemtype gcd(Elemtype a, Elemtype b)
{
order(a,b); int r;
if(b == 0) { return a; }
else { while(true)
{ r = a % b; a = b; b = r; if (b == 0) { return a; break; }
}
}
} /* 用扩展的欧几里得算法求乘法逆元 */
Elemtype extend_euclid(Elemtype m, Elemtype bin)
{
order(m,bin);
Elemtype a[3],b[3],t[3];
a[0] = 1, a[1] = 0, a[2] = m;
b[0] = 0, b[1] = 1, b[2] = bin;
if (b[2] == 0) { return a[2] = gcd(m, bin); }
if (b[2] ==1) { return b[2] = gcd(m, bin); }
while(true) {
if (b[2] ==1) { return b[1]; break; }
int q = a[2] / b[2];
for(int i=0; i<3; i++)
{ t[i] = a[i] - q * b[i]; a[i] = b[i]; b[i] = t[i]; }
}
} /* 快速模幂算法 */
Elemtype modular_multiplication(Elemtype a, Elemtype b, Elemtype n)
{
Elemtype f = 1;
Elemtype bin[32];
switch_to_bit(b,bin);
for(int i=31; i>=0; i--)
{
f = (f * f) % n;
if(bin[i] == 1) {
f = (f * a) % n;
}
}
return f;
} /* 产生密钥 */
void produce_key()
{
cout<<"input two primes p and q:";
cin>>p>>q;
while (!(test_prime(p)&&test_prime(q)))
{ cout<<"wrong input,please make sure two number are both primes!"<<endl;
cout<<"input two primes p and q";
cin>>p>>q;
}
pr.n = p * q;
pu.n = p * q; fn = (p - 1) * (q - 1);
cout<<"fn = "<<fn<<endl;
cout<<"input e :";
cin>>e;
while((gcd(fn,e)!=1))
{
cout<<"e is error,try again!";
cout<<"input e :";
cin>>e;
}
pr.d = (extend_euclid(fn,e) + fn) % fn; pu.e = e; flag = 1;
cout<<"PR.d: "<<pr.d<< "PR.n: "<<pr.n<<endl;
cout<<"PU.e:" <<pu.e<< "PU.n: "<<pu.n<<endl;
} /* 加密 */
void encrypt()
{
if(flag == 0)
{
cout<<"setkey first:"<<endl;
produce_key();
}
cout<<"input m:";
cin>>m;
c = modular_multiplication(m,pu.e,pu.n);
cout<<"c is:"<<c<<endl;
} /* 解密 */
void decrypt()
{
if(flag == 0) { cout<<"setkey first:"<<endl; produce_key(); }
cout<<"input c:";
cin>>c;
m = modular_multiplication(c,pr.d,pr.n);
cout<<"m is:"<<m<<endl;
} /* 版权信息 */
void about()
{
cout<<"*********************************************"<<endl;
cout<<"*** by Terry***"<<endl;
cout<<"*** copyright 2010,All rights reserved by ***"<<endl;
cout<<"*** Terry,technology supported by weizuo !***"<<endl;
cout<<"*** If you have any question, please mail ***"<<endl;
cout<<"*********************************************"<<endl;
cout<<endl<<endl;
Init();
} /* 消息映射 */
MsgMap Messagemap[] = { {'a',about}, {'s',produce_key}, {'d',decrypt}, {'e',encrypt}, {'q',NULL} }; /* 主函数,提供循环 */
void main()
{
Init(); char d;
while((d = getchar())!='q')
{
int i = 0;
while(Messagemap[i].ch) {
if(Messagemap[i].ch == d) { Messagemap[i].handler(); break; }
i++;
}
}
}