RSA加解密

n = p * qz = (p - 1) * (q - 1)

e * d = 1 (mod z)

c = pe (mod n)

p = cd (mod n)

//C++程序源码，VC++中实现#include<stdio.h>#include<string.h>#include<stdlib.h>#include<time.h>#include<math.h>#include<malloc.h>#define MAX 100#define LEN sizeof(struct slink)void sub(int a[MAX],int b[MAX] ,int c[MAX] );struct slink{int bignum[MAX];//bignum[98]用来标记正负号，1正，0负bignum[99]来标记实际长struct slink *next;};//大数运算

void print( int a[MAX] ){int i;for(i=0;i<a[99];i++)printf("%d",a[a[99]-i-1]);printf("nn");return;}int cmp(int a1[MAX],int a2[MAX]){   int l1, l2;int i;l1=a1[99];l2=a2[99];if (l1>l2)return 1;if (l1<l2)return -1;for(i=(l1-1);i>=0;i--){if (a1[i]>a2[i])return 1 ;if (a1[i]<a2[i])return -1;}return 0;}void mov(int a[MAX],int *b){int j;for(j=0;j<MAX;j++)b[j]=a[j];return ;}

//大数相乘（向左移）void mul(int a1[MAX],int a2[MAX],int *c){int i,j,y,x,z,w,l1,l2;l1=a1[MAX-1];l2=a2[MAX-1];if (a1[MAX-2]=='-'&& a2[MAX-2]=='-')c[MAX-2]=0;else if (a1[MAX-2]=='-')c[MAX-2]='-';else if (a2[MAX-2]=='-')c[MAX-2]='-';for(i=0;i<l1;i++){for(j=0;j<l2;j++){x=a1[i]*a2[j];y=x/10;z=x%10;w=i+j;c[w]=c[w]+z;c[w+1]=c[w+1]+y+c[w]/10;c[w]=c[w]%10;}}w=l1+l2;if(c[w-1]==0)w=w-1;c[MAX-1]=w;return;}//大数相加，注意进位void add(int a1[MAX],int a2[MAX],int *c){int i,l1,l2;int len,temp[MAX];int k=0;l1=a1[MAX-1];l2=a2[MAX-1];if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-')){c[MAX-2]='-';}else if (a1[MAX-2]=='-'){mov(a1,temp);temp[MAX-2]=0;sub(a2,temp,c);return;}else if (a2[MAX-2]=='-'){mov(a2,temp);temp[98]=0;sub(a1,temp,c);return;}if(l1<l2)len=l1;else len=l2;for(i=0;i<len;i++){c[i]=(a1[i]+a2[i]+k)%10;k=(a1[i]+a2[i]+k)/10;}if(l1>len){for(i=len;i<l1;i++){c[i]=(a1[i]+k)%10;k=(a1[i]+k)/10;}if(k!=0){c[l1]=k;len=l1+1;}else len=l1;}else{for(i=len;i<l2;i++){c[i]=(a2[i]+k)%10;k=(a2[i]+k)/10;}if(k!=0){c[l2]=k;len=l2+1;}else len=l2;}c[99]=len;return;}//大数相减，注意借位void sub(int a1[MAX],int a2[MAX],int *c){int i,l1,l2;int len,t1[MAX],t2[MAX];int k=0;l1=a1[MAX-1];l2=a2[MAX-1];if ((a1[MAX-2]=='-') && (a2[MAX-2]=='-')){mov(a1,t1);mov(a2,t2);t1[MAX-2]=0;t2[MAX-2]=0;sub(t2,t1,c);return;}else if( a2[MAX-2]=='-'){mov(a2,t2);t2[MAX-2]=0;add(a1,t2,c);return;}else if (a1[MAX-2]=='-'){mov(a2,t2);t2[MAX-2]='-';add(a1,t2,c);return;}if(cmp(a1,a2)==1){

len=l2;for(i=0;i<len;i++){if ((a1[i]-k-a2[i])<0){c[i]=(a1[i]-a2[i]-k+10)%10;k=1;}else{c[i]=(a1[i]-a2[i]-k)%10;k=0;}}

for(i=len;i<l1;i++){if ((a1[i]-k)<0){c[i]=(a1[i]-k+10)%10;k=1;}else{c[i]=(a1[i]-k)%10;k=0;}}if(c[l1-1]==0)//使得数组C中的前面所以0字符不显示了，如1000-20=0980--->显示为980了{len=l1-1;i=2;while (c[l1-i]==0)//111456-111450=00006，消除0后变成了6{len=l1-i;i++;}}else{len=l1;}}elseif(cmp(a1,a2)==(-1)){c[MAX-2]='-';len=l1;for(i=0;i<len;i++){if ((a2[i]-k-a1[i])<0){c[i]=(a2[i]-a1[i]-k+10)%10;k=1;}else{c[i]=(a2[i]-a1[i]-k)%10;k=0;}}for(i=len;i<l2;i++){if ((a2[i]-k)<0){c[i]=(a2[i]-k+10)%10;k=1;}else{c[i]=(a2[i]-k)%10;k=0;}}if(c[l2-1]==0){len=l2-1;i=2;while (c[l1-i]==0){len=l1-i;i++;}}else len=l2;

}else if(cmp(a1,a2)==0){len=1;c[len-1]=0;}c[MAX-1]=len;return;}

//取模数void mod(int a[MAX],int b[MAX],int *c)//c=a mod b,注意：经检验知道此处A和C的数组都改变了{ int d[MAX];mov (a,d);while (cmp(d,b)!=(-1))//c=a-b-b-b-b-b.......until(c<b){sub(d,b,c);mov(c,d);//c复制给a}return ;}//大数相除(向右移)//试商法,调用以后w为a mod b, C为a div bvoid divt(int t[MAX],int b[MAX],int *c ,int *w){int a1,b1,i,j,m;//w用于暂时保存数据int d[MAX],e[MAX],f[MAX],g[MAX],a[MAX];

mov(t,a);for(i=0;i<MAX;i++)e[i]=0;for(i=0;i<MAX;i++)d[i]=0;for(i=0;i<MAX;i++) g[i]=0;a1=a[MAX-1];b1=b[MAX-1];if (cmp(a,b)==(-1)){c[0]=0;c[MAX-1]=1;mov(t,w);return;}else if (cmp(a,b)==0){c[0]=1;c[MAX-1]=1;w[0]=0;w[MAX-1]=1;return;}m=(a1-b1);for(i=m;i>=0;i--)//例如341245/3=341245-300000*1--->41245-30000*1--->11245-3000*3--->2245-300*7--->145-30*4=25--->25-3*8=1{for(j=0;j<MAX;j++)d[j]=0;d[i]=1;d[MAX-1]=i+1;mov(b,g);mul(g,d,e);

while (cmp(a,e)!=(-1)){c[i]++;sub(a,e,f);mov(f,a);//f复制给g}for(j=i;j<MAX;j++)//高位清零e[j]=0;

}mov(a,w);if (c[m]==0) c[MAX-1]=m;else c[MAX-1]=m+1;return;}//解决了 m=a*b mod nvoid mulmod(int a[MAX] ,int b[MAX] ,int n[MAX],int *m){int c[MAX],d[MAX];int i;for(i=0;i<MAX;i++)d[i]=c[i]=0;mul(a,b,c);divt(c,n, d,m);for(i=0;i<m[MAX-1];i++)printf("%d",m[m[MAX-1]-i-1]);printf("nm length is : %d n",m[MAX-1]);}//解决了 m=a^p mod n的函数问题。void expmod(int a[MAX] ,int p[MAX] ,int n[MAX],int *m){int t[MAX],l[MAX],temp[MAX]; //t放入2，l放入1int w[MAX],s[MAX],c[MAX],b[MAX],i;for(i=0;i<MAX-1;i++)b[i]=l[i]=t[i]=w[i]=0;t[0]=2;t[MAX-1]=1;l[0]=1;l[MAX-1]=1;mov(l,temp);mov(a,m);mov(p,b);while(cmp(b,l)!=0){for(i=0;i<MAX;i++)w[i]=c[i]=0;divt(b,t,w,c);// c=p mod 2 w= p /2

mov(w,b);//p=p/2if(cmp(c,l)==0) //余数c==1{for(i=0;i<MAX;i++)w[i]=0;mul(temp,m,w);mov(w,temp);

for(i=0;i<MAX;i++)w[i]=c[i]=0;divt(temp,n,w,c);//c为余c=temp % n，w为商w=temp/nmov(c,temp);}for(i=0;i<MAX;i++)s[i]=0;mul(m,m,s);//s=a*afor(i=0;i<MAX;i++)c[i]=0;divt(s,n,w,c);//w=s/n;c=s mod nmov (c,m);}for(i=0;i<MAX;i++)s[i]=0;mul(m,temp,s);for(i=0;i<MAX;i++)c[i]=0;divt(s,n,w,c);mov (c,m);//余数s给mm[MAX-2]=a[MAX-2];//为后面的汉字显示需要，用第99位做为标记return;//k=temp*k%n}

int   is_prime_san(int p[MAX] ){

int i,a[MAX],t[MAX],s[MAX],o[MAX];for(i=0;i<MAX;i++)s[i]=o[i]=a[i]=t[i]=0;t[0]=1;t[MAX-1]=1;a[0]=2;// { 2,3,5,7 }a[MAX-1]=1;sub(p,t,s);expmod ( a, s, p ,o);if ( cmp(o,t) != 0 ){return 0;}a[0]=3;for(i=0;i<MAX;i++) o[i]=0;expmod ( a, s, p ,o);if ( cmp(o,t) != 0 ){return 0;}a[0]=5;for(i=0;i<MAX;i++) o[i]=0;expmod ( a, s, p ,o);if ( cmp(o,t) != 0 ){return 0;}a[0]=7;for(i=0;i<MAX;i++) o[i]=0;expmod ( a, s, p ,o);if ( cmp(o,t) != 0 ){return 0;}return 1;}//检测两个大数之间是否互质int coprime(int e[MAX],int s[MAX]){int a[MAX],b[MAX],c[MAX],d[MAX],o[MAX],l[MAX];int i;for(i=0;i<MAX;i++)l[i]=o[i]=c[i]=d[i]=0;o[0]=0;o[MAX-1]=1;l[0]=1;l[MAX-1]=1;mov(e,b);mov(s,a);do{if(cmp(b,l)==0){return 1;}for(i=0;i<MAX;i++)c[i]=0;divt(a,b,d,c);mov(b,a);//b--->amov(c,b);//c--->b}while(cmp(c,o)!=0);//printf("They are not coprime!n")return 0;}//产生随机素数p和qvoid prime_random(int *p,int *q){int i,k;time_t t;p[0]=1;q[0]=3;

// p[19]=1;// q[18]=2;

p[MAX-1]=10;q[MAX-1]=11;

do{t=time(NULL);srand((unsigned long)t);for(i=1;i<p[MAX-1]-1;i++){k=rand()%10;p[i]=k;}k=rand()%10;while (k==0){k=rand()%10;}p
-1]=k;}while((is_prime_san(p))!=1);printf("素数 p 为 : ");for(i=0;i<p[MAX-1];i++){printf("%d",p
-i-1]);}printf("nn");do{t=time(NULL);srand((unsigned long)t);for(i=1;i<q[MAX-1];i++){k=rand()%10;q[i]=k;}}while((is_prime_san(q))!=1);printf("素数 q 为 : ");for(i=0;i<q[MAX-1];i++){printf("%d",q[q[MAX-1]-i-1]);}printf("nn");return;}//产生与（p-1）*（q-1）互素的随机数void erand(int e[MAX],int m[MAX]){int i,k;time_t t;e[MAX-1]=5;printf("随机产生一个与(p-1)*(q-1)互素的 e :");do{t=time(NULL);srand((unsigned long)t);for(i=0;i<e[MAX-1]-1;i++){k=rand()%10;e[i]=k;}while((k=rand()%10)==0)k=rand()%10;e[e[MAX-1]-1]=k;}while(coprime( e, m)!=1);for(i=0;i<e[MAX-1];i++){printf("%d",e[e[MAX-1]-i-1]);}printf("nn");return ;}//根据上面的p、q和e计算密钥dvoid rsad(int e[MAX],int g[MAX],int *d){int   r[MAX],n1[MAX],n2[MAX],k[MAX],w[MAX];int     i,t[MAX],b1[MAX],b2[MAX],temp[MAX];mov(g,n1);mov(e,n2);for(i=0;i<MAX;i++)k[i]=w[i]=r[i]=temp[i]=b1[i]=b2[i]=t[i]=0;b1[MAX-1]=0;b1[0]=0;//b1=0;b2[MAX-1]=1;b2[0]=1;//b2=1;while(1){for(i=0;i<MAX;i++)k[i]=w[i]=0;divt(n1,n2,k,w);//k=n1/n2;for(i=0;i<MAX;i++)temp[i]=0;mul(k,n2,temp);//temp=k*n2;for(i=0;i<MAX;i++)r[i]=0;sub(n1,temp,r);if((r[MAX-1]==1) && (r[0]==0))//r=0{break;}else{mov(n2,n1);//n1=n2;mov( r,n2);//n2=r;mov(b2, t);//t=b2;for(i=0;i<MAX;i++)temp[i]=0;mul(k,b2,temp);//b2=b1-k*b2;for(i=0;i<MAX;i++)b2[i]=0;sub(b1,temp,b2);mov(t,b1);}}for(i=0;i<MAX;i++)t[i]=0;add(b2,g,t);for(i=0;i<MAX;i++)temp[i]=d[i]=0;divt(t,g,temp,d);printf("由以上的(p-1)*(q-1)和 e 计算得出的 d : ");for(i=0;i<d[MAX-1];i++)printf("%d",d[d[MAX-1]-i-1]);printf("nn");}//求解密密钥d的函数(根据欧几里得算法)unsigned long rsa(unsigned long p,unsigned long q,unsigned long e) //求解密密钥d的函数(根据欧几里得算法){unsigned long g,k,r,n1,n2,t;unsigned long b1=0,b2=1;g=(p-1)*(q-1);n1=g;n2=e;

while(1){ k=n1/n2;r=n1-k*n2;if(r!=0){n1=n2;n2=r;t=b2;b2=b1-k*b2;b1=t;}else{break;}}return (g+b2)%g;}//加密和解密void printbig(struct slink *h){struct slink *p;int i;p=(struct slink * )malloc(LEN);p=h;if(h!=NULL)do{for(i=0;i<p->bignum[MAX-1];i++)printf("%d",p->bignum[p->bignum[MAX-1]-i-1]);p=p->next;}while(p!=NULL);printf("nn");}struct slink *input(void)//输入明文并且返回头指针，没有加密时候转化的数字{struct slink *head;struct slink *p1,*p2;int i,n,c,temp;char ch;n=0;p1=p2=(struct slink * )malloc(LEN);head=NULL;printf("n请输入你所要加密的内容 : n");while((ch=getchar())!='n'){i=0;c=ch;if(c<0){c=abs(c);//把负数取正并且做一个标记p1->bignum[MAX-2]='0';}else{p1->bignum[MAX-2]='1';}while(c/10!=0){temp=c%10;c=c/10;p1->bignum[i]=temp;i++;}p1->bignum[i]=c;p1->bignum[MAX-1]=i+1;n=n+1;if(n==1)head=p1;else p2->next=p1;p2=p1;p1=(struct slink * )malloc(LEN);}p2->next=NULL;return(head);}//加密模块儿，例如C = P^e mod nstruct slink *jiami(int e[MAX],int n[MAX],struct slink *head){struct slink *p;struct slink *h;struct slink *p1,*p2;int m=0,i;printf("n");printf("加密后形成的密文内容：n");p1=p2=(struct slink* )malloc(LEN);h=NULL;p=head;if(head!=NULL)do{

expmod( p->bignum , e ,n ,p1->bignum);for(i=0;i<p1->bignum[MAX-1];i++){printf("%d",p1->bignum[p1->bignum[MAX-1]-1-i]);}m=m+1;if(m==1)h=p1;else p2->next=p1;p2=p1;p1=(struct slink * )malloc(LEN);p=p->next;} while(p!=NULL);p2->next=NULL;p=h;printf("n");return(h);

}//解密模块儿，例如P = C^d mod nvoid jiemi(int d[MAX],int n[MAX],struct slink *h){int   i,j,temp;struct slink *p,*p1;char ch[65535];p1=(struct slink* )malloc(LEN);p=h;j=0;

if(h!=NULL)do{for(i=0;i<MAX;i++)p1->bignum[i]=0;expmod( p->bignum , d ,n ,p1->bignum);temp=p1->bignum[0]+p1->bignum[1]*10+p1->bignum[2]*100;if (( p1->bignum[MAX-2])=='0'){temp=0-temp;}

ch[j]=temp;j++;p=p->next;}while (p!=NULL);printf("n");printf("解密密文后所生成的明文:n");for(i=0;i<j;i++)printf("%c",ch[i]);printf("n");return;}//选择一种操作void menu(){printf("R--------产生 密钥对n");printf("T--------简单测试n");printf("Q--------退出n");printf("请选择一种操作:");}//主MAIN函数void main(){int i;char c;int p[MAX],q[MAX],n[MAX],d[MAX],e[MAX],m[MAX],p1[MAX],q1[MAX];struct slink *head,*h1,*h2;for(i=0;i<MAX;i++)m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0;//简单初始化一下

while (1){menu();c=getchar();getchar();//接受回车符if ((c=='R') || (c=='r'))//操作r产生密钥对{for(i=0;i<MAX;i++)m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0;printf("nn随机密钥对产生如下：nn");prime_random(p,q);//随机产生两个大素数mul(p,q,n);//p*qprintf("由 p、q 得出 n :");print(n);mov(p,p1);p1[0]--;    //p-1mov(q,q1);q1[0]--;      //q-1mul(p1,q1,m);//m=(p-1)*(q-1)erand(e,m);//产生一个与m互素的随机数rsad(e,m,d);//e * d = 1 mod mprintf("密钥对产生完成，现在可以直接进行加解密!n");printf("n按任意键回主菜单…………");getchar();}else if((c=='T') || (c=='t'))//加密解密测试{head=input();h1=jiami( e, n, head);jiemi( d, n, h1);printf("nRSA测试工作完成!n");printf("n按任意键回主菜单…………");getchar();}else if ((c=='Q') || (c=='q'))//结束退出{break;}}}

import gmpy2p = 2499568793q = 4568695582742345507136251229217400959960856046691733722988345503429689799935696593516299458516865110324638359470761456115925725067558499862591063153473862179550706262380644940013531317571260647226561004191266100720745936563550699000939117068559232225644277283541933064331891245169739139886735615435506152070330233107807124410892978280063993668726927377177983100529270996547002022341628251905780873531481682713820809147098305289391835297208890779643623465917824350382592808578978330348769060448006691307027594085634520759293965723855183484366752511654099121387261343686017189426761536281948007104498017003911e = 65537c = 575061710950381118206735073806398116370706587076775765253483131078316908073202143802386128272374323616239083134747318254436706806781744501903333604772961927966747648954315962269321297121495398057938617145017999482722197661065698707836824505023856306403892307944203245563411961302499347604417024064678999003637933185177922884103362203639349298263339808508185861692596967147081382566246627668898774233029198694500565511361867375668367875805985660705137109665107860799277624050210666866958502948062330037309873148963011192405012811945540153592090345668265964477204465327474208098404082920129178960510763496025906621820n = p * qfn = (p - 1) * (q - 1)d = gmpy2.invert(e, fn)h = hex(gmpy2.powmod(c, d, n))[2:]if len(h) % 2 == 1:h = '0' + hs = h.decode('hex')print s

import libnumfrom Crypto.Util.number import long_to_bytes

p = 2499568793q = 4568695582742345507136251229217400959960856046691733722988345503429689799935696593516299458516865110324638359470761456115925725067558499862591063153473862179550706262380644940013531317571260647226561004191266100720745936563550699000939117068559232225644277283541933064331891245169739139886735615435506152070330233107807124410892978280063993668726927377177983100529270996547002022341628251905780873531481682713820809147098305289391835297208890779643623465917824350382592808578978330348769060448006691307027594085634520759293965723855183484366752511654099121387261343686017189426761536281948007104498017003911

e = 65537

c = 575061710950381118206735073806398116370706587076775765253483131078316908073202143802386128272374323616239083134747318254436706806781744501903333604772961927966747648954315962269321297121495398057938617145017999482722197661065698707836824505023856306403892307944203245563411961302499347604417024064678999003637933185177922884103362203639349298263339808508185861692596967147081382566246627668898774233029198694500565511361867375668367875805985660705137109665107860799277624050210666866958502948062330037309873148963011192405012811945540153592090345668265964477204465327474208098404082920129178960510763496025906621820n = 11419768903339716189261532371559705252086398275876008505047375123074727093589680611869748263351554093957968142343831331654606932684767042958427409579115435445187908134556329979271179879129295667476493886787230948520371350715808988496083694717544298343260369816980228394498856751096191942011545898984240281874509791880690092840536597771674772617299407710771426964764347566008897012753022763270832647775571317162594044338095870404550665457899223394942640876850692848671826594750236910363027949459768124646230555766323417693441861436560072288812137944884954974348317322412816157152702695143094487806945533233359294549423



d = libnum.invmod(e, (p - 1) * (q - 1))print("d:" + d)

m = pow(c, d, n)  # m 的十进制形式string = long_to_bytes(m)  # m明文print(string)  # 结果为 b‘ m ’ 的形式

#-*- coding:utf-8 -*-# 当指数e和Phi(n)不互素时from Crypto.Util.number import *

import sympy

def gcd(a,b):if a < b:a,b = b,awhile b != 0:tem = a % ba = bb = temreturn a

def invalidExponent(p,q,e,c):phiN = (p - 1) * (q - 1)n = p * qGCD = gcd(e, phiN)if (GCD == 1):return "Public exponent is valid....."d = inverse(e//GCD,phiN)c = pow(c, d, n)plaintext = sympy.root(c, GCD)plaintext = long_to_bytes(plaintext)return plaintext



def main():e = 0x20002

c = 69775954010477827342655007357413905879265207201140046408669586721885526123784907133716642304622235420317538384169817488136355157658329703705226141938991105912868209447036610553660972001461632840370922684108791263764483626927583087998066070299767122268085587208956687449243493403662943691619787801332549149107

p = 12470704223521630361963826771946763220892587623191431207923413178791149916874153397100361890510496084700189763294677638398021009427510131598570281465633547

q = 12470704223521630361963826771946763220892587623191431207923413178791149916874153397100361890510496084700189763294677638398021009427510131598570281465633283

plaintext = invalidExponent(p,q,e,c)print plaintext

main()