给出p、q、e、M，求公钥，私钥，并且利用RSA算法加密和解密？

假定用户A要发送消息m给用户B，1）用户B要产生两个素数p和q；2）用户B计算n=pq和φ(n)=(p-1)(q-1)；3）用户B选着一个数e（0公钥就是（n,e) 私钥就是（n,d)
ps:若不想产生数据溢出（mod后的数大于25）的话，n最好选取0~25之间的数；如若是解密后的明文不出现差错，选取的n最好大于m中十进制数最大的数。
example:令26个英文字母对应于0-25的整数，用户B产生两个素数p=3，q=11，φ(n)=2*10=20，取e=3，则d=7，用户B将n=33和e=3公开
如果A想发送in给B，则A会通过公共渠道找到（n,e),然后将信息加密，E(i)=8^3 mod 33=17,E（n）=13^3 mod 33=19 则它对应的密文为c=rt；用户B收到A给的密文解密：D（r）=17^7 mod 33=8即明文i,D(t)=19 ^7 mod 33=13,即明文n。

#include
#include
#include

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<<"*********************************************"< cout<<"*** Welcome to use RSA encoder ***"< cout<<"*** a.about ***"< cout<<"*** e.encrypt ***"< cout<<"*** d.decrypt ***"< cout<<"*** s.setkey ***"< cout<<"*** q.quit ***"< cout<<"**********************************by*Terry***"< cout<<"press a key:"<}
/* 将两个数排序，大的在前面*/
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!"< 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 = "< 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: "< cout<<"PU.e: "<}
/* 加密 */
void encrypt() {
if(flag == 0) {
cout<<"setkey first:"< produce_key();
}
cout<<"input m:";
cin>>m;
c = modular_multiplication(m,pu.e,pu.n);
cout<<"c is:"<}
/* 解密 */
void decrypt() {
if(flag == 0) {
cout<<"setkey first:"< produce_key();
}
cout<<"input c:";
cin>>c;
m = modular_multiplication(c,pr.d,pr.n);
cout<<"m is:"<}
/* 版权信息 */
void about() {
cout<<"*********************************************"< cout<<"*** by Terry ***"< cout<<"*** copyright 2010,All rights reserved by ***"< cout<<"*** Terry,technology supported by weizuo !***"< cout<<"*** If you have any question, please mail ***"< cout<<"*** to 18679376@qq.com ! ***"< cout<<"*** Computer of science and engineering ***"< cout<<"*** XiDian University 2010-4-29 ***"< cout<<"*********************************************"< cout< 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++;
}
}
}

设p=17 q=11，这两个数明显是一个素数，根据这2个素数，选择一个e值，e=7，关于e怎么选，一会儿在下面的算法里你就知道。假设明文M=88，则开始如下算法：
1. 计算n=pq=187
2. 计算φ(n)=(p-1)(q-1)=160
3. 选择e，使用它与160互素且小于160，因此选e=7
4. 确定d，使de除160的余数为1，取d=23。
这样得到公钥PU={e,n}={7,187} 私钥={d,n}={23,187}
加密：密文C=M^e mod n=88^7 mod 187=11
解密：明文M=C^d mod n=88

ziji