第一篇：RSA加密解密算法C語(yǔ)言代碼
#include
#include
#include
void sub(int a[MAX],int b[MAX] ,int c[MAX]);
struct slink {
int bignum[MAX];/*bignum[98]用來(lái)標(biāo)記正負(fù)號(hào)，1正，0負(fù)bignum[99]來(lái)標(biāo)記實(shí)際長(zhǎng)度*/
struct slink *next;};
/*/-------自己建立的大數(shù)運(yùn)算庫(kù)------*/
void print(int a[MAX])
{
int i;
for(i=0;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 return-1; for(i=(l1-1);i>=0;i--) { if(a1[i]>a2[i]) return 1; if(a1[i] return-1; } return 0;} void mov(int a[MAX],int *b){ int j; for(j=0;j b[j]=a[j]; return;} void mul(int a1[MAX],int a2[MAX],int *c){ int i,j;int y;int x;int z;int w;int 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 for(j=0;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 c[i]=(a1[i]+a2[i]+k)%10; k=(a1[i]+a2[i]+k)/10;} if(l1>len){ for(i=len;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 { 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 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 { 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)/*使得數(shù)組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; } } else if(cmp(a1,a2)==(-1)){ c[MAX-2]='-'; len=l1; for(i=0;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 { 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//注意：經(jīng)檢驗(yàn)知道此處A和C的數(shù)組都改變了。*/ { int d[MAX];mov(a,d);while(cmp(d,b)!=(-1))/*/c=a-b-b-b-b-b.......until(c sub(d,b,c); mov(c,d);/*/c復(fù)制給a*/ } return;} void divt(int t[MAX],int b[MAX],int *c ,int *w)/*//試商法//調(diào)用以后w為a mod b, C為a div b;*/ { int a1,b1,i,j,m;/*w用于暫時(shí)保存數(shù)據(jù)*/ int d[MAX],e[MAX],f[MAX],g[MAX],a[MAX]; mov(t,a); for(i=0;i e[i]=0;for(i=0;i d[i]=0;for(i=0;i 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 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復(fù)制給g*/ } for(j=i;j e[j]=0; } mov(a,w);if(c[m]==0)c[MAX-1]=m;else c[MAX-1]=m+1; return;} void mulmod(int a[MAX] ,int b[MAX] ,int n[MAX],int *m)/*解決 了 m=a*b mod n;*/ { int c[MAX],d[MAX];int i;for(i=0;i d[i]=c[i]=0;mul(a,b,c); divt(c,n, d,m); for(i=0;i printf(“%d”,m[m[MAX-1]-i-1]); printf(“nm length is : %d n”,m[MAX-1]);} /*接下來(lái)的重點(diǎn)任務(wù)是要著手解決 m=a^p mod n的函數(shù)問(wèn)題。*/ void expmod(int a[MAX] ,int p[MAX] ,int n[MAX],int *m){ int t[MAX],l[MAX],temp[MAX];/*/t放入2，l放入1；*/ int w[MAX],s[MAX],c[MAX],b[MAX],i;for(i=0;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 divt(b,t,w,c);/*// c=p mod 2 w= p /2*/ mov(w,b);/*//p=p/2*/ if(cmp(c,l)==0)/*/余數(shù)c==1*/ { for(i=0;i mul(temp,m,w); mov(w,temp); for(i=0;i divt(temp,n,w,c);/* /c為余c=temp % n，w為商w=temp/n */ mov(c,temp);} for(i=0;i mul(m,m,s);//s=a*a for(i=0;i divt(s,n,w,c);/*/w=s/n;c=s mod n*/ mov(c,m);} for(i=0;i mul(m,temp,s); for(i=0;i divt(s,n,w,c); mov(c,m);/*余數(shù)s給m*/ m[MAX-2]=a[MAX-2];/*為后面的漢字顯示需要，用第99位做為標(biāo)記*/ 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 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 expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } a[0]=5; for(i=0;i expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } a[0]=7; for(i=0;i expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } return 1;} int coprime(int e[MAX],int s[MAX])/*//// 求兩個(gè)大數(shù)之間是否互質(zhì)////*/ { int a[MAX],b[MAX],c[MAX],d[MAX],o[MAX],l[MAX]; int i;for(i=0;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 }while(cmp(c,o)!=0);/* printf(“Ihey are not coprime!n”);*/ return 0;} void 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 k=rand()%10;} p[p[MAX-1]-1]=k; }while((is_prime_san(p))!=1); printf(“素?cái)?shù) p 為 : ”); for(i=0;i printf(“nn”); do { t=time(NULL); srand((unsigned long)t);for(i=1;i }while((is_prime_san(q))!=1); printf(“素?cái)?shù) q 為 : ”); for(i=0;i printf(“nn”);return;} void erand(int e[MAX],int m[MAX]){ int i,k;time_t t;e[MAX-1]=5;printf(“隨機(jī)產(chǎn)生一個(gè)與(p-1)*(q-1)互素的 e :”); do { t=time(NULL); srand((unsigned long)t);for(i=0;i k=rand()%10;e[e[MAX-1]-1]=k;}while(coprime(e, m)!=1); for(i=0;i printf(“nn”);return;} void 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 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 k[i]=w[i]=0; divt(n1,n2,k,w);/*/k=n1/n2;*/ for(i=0;i temp[i]=0; mul(k,n2,temp);/*/temp=k*n2;*/ for(i=0;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 temp[i]=0; mul(k,b2,temp);/*/b2=b1-k*b2;*/ for(i=0;i b2[i]=0; sub(b1,temp,b2); mov(t,b1); } } for(i=0;i t[i]=0; add(b2,g,t); for(i=0;i temp[i]=d[i]=0; divt(t,g,temp,d); printf(“由以上的(p-1)*(q-1)和 e 計(jì)算得出的 d : ”); for(i=0;i printf(“nn”);} /*/求解密密鑰d的函數(shù)(根據(jù)Euclid算法)***68000*/ unsigned long rsa(unsigned long p,unsigned long q,unsigned long e)/*/求解密密鑰d的函數(shù)(根據(jù)Euclid算法)*/ { 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;} /*/-----------導(dǎo)入導(dǎo)出公鑰和私鑰-----/*/ void loadpkey(int e[MAX],int n[MAX])//導(dǎo)入公鑰 { FILE *fp;char filename[25],str[MAX],ch;int i,k;for(i=0;i e[i]=n[i]=0;while(1){ printf(“n”);printf(“為導(dǎo)入(e,n)，請(qǐng)輸入加密密鑰對(duì)文件路徑: n”); scanf(“%s”,filename); if((fp=fopen(filename,“r”))==NULL) printf(“輸入的文件不存在，請(qǐng)重新輸入!n”); else break;} k=0; while((ch=fgetc(fp))!=EOF) { if(ch!=' ') { str[k]=ch; k++; } else { for(i=0;i { e[i]=str[k-i-1]-48; } e[MAX-1]=k; k=0; } } for(i=0;i n[i]=str[k-i-1]-48; n[MAX-1]=k; printf(“n加密密鑰 e : ”); for(i=0;i printf(“%d”,e[e[MAX-1]-i-1]); printf(“n”); printf(“n 公鑰 n : ”); for(i=0;i printf(“%d”,n[n[MAX-1]-i-1]); printf(“n”); fclose(fp); printf(“n導(dǎo)入(e,n)成功!n”); getchar();} void loadskey(int d[MAX],int n[MAX])//導(dǎo)入私鑰 { { FILE *fp;char filename[25],str[MAX],ch;int i,k;for(i=0;i d[i]=n[i]=0;while(1){ printf(“為導(dǎo)入(d,n)，請(qǐng)輸入解密密鑰對(duì)文件的路徑: n”); scanf(“%s”,filename); if((fp=fopen(filename,“r”))==NULL) { printf(“輸入的文件不存在，請(qǐng)重新輸入!n”); } else break;} k=0; while((ch=fgetc(fp))!=EOF) { if(ch!=' ') { str[k]=ch; k++; } else { for(i=0;i { d[i]=str[k-i-1]-48; } d[MAX-1]=k; k=0; } } for(i=0;i n[i]=str[k-i-1]-48; n[MAX-1]=k; printf(“n解密密鑰 d : ”); for(i=0;i printf(“%d”,d[d[MAX-1]-i-1]); printf(“n”); printf(“n 公鑰 n : ”); for(i=0;i printf(“%d”,n[n[MAX-1]-i-1]); printf(“n”); fclose(fp); printf(“n導(dǎo)入(d,n)成功!n”); getchar();} } void savepkey(int e[MAX],int n[MAX])//導(dǎo)出公鑰 { FILE *fp; int i; char savefile[25],ch;printf(“導(dǎo)出加密密鑰(e,n)，存放的文件路徑為: ”); scanf(“%s”,savefile);printf(“n”); fp=fopen(savefile,“w”);for(i=0;i ch=e[e[MAX-1]-i-1]+48; fputc(ch,fp);} ch=' ';fputc(ch,fp);for(i=0;i ch=n[n[MAX-1]-i-1]+48; fputc(ch,fp);} fclose(fp);printf(“n保存(e,n)操作完成!n”);} void saveskey(int d[MAX],int n[MAX])//導(dǎo)出私鑰 { FILE *fp; int i; char savefile[25],ch;printf(“導(dǎo)出解密密鑰(d,n)，存放的文件路徑為: ”); scanf(“%s”,savefile);printf(“n”); fp=fopen(savefile,“w”);for(i=0;i ch=d[d[MAX-1]-i-1]+48; fputc(ch,fp);} ch=' ';fputc(ch,fp);for(i=0;i ch=n[n[MAX-1]-i-1]+48; fputc(ch,fp);} fclose(fp);printf(“n保存(d,n)操作完成!n”); } /*/-----------加密和解密的塊-----/*/ 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 bignum[MAX-1];i++) printf(“%d”,p->bignum[p->bignum[MAX-1]-i-1]); p=p->next;} while(p!=NULL); printf(“nn”); } void tencrypto(int e[MAX], int n[MAX])/*//對(duì)有需要的文件進(jìn)行加密*/ { FILE *fp; int i,k,count,temp,c; char filename[25],ch,encryfile[25]; struct slink *p,*p1,*p2; struct slink *h; h=p=p1=p2=(struct slink *)malloc(LEN); h=NULL; printf(“n輸入需要加密的文件路徑 : ”); scanf(“%s”,filename); if((fp=fopen(filename,“r”))==NULL) { printf(“Cannot open file!n”); exit(0); } printf(“n文件的原文內(nèi)容：nn”); count=0; while((ch=fgetc(fp))!=EOF) { putchar(ch); c=ch; k=0;if(c<0){ c=abs(c);/*/把負(fù)數(shù)取正并且做一個(gè)標(biāo)記*/ p1->bignum[MAX-2]='0';} else { p1->bignum[MAX-2]='1';} while(c/10!=0){ temp=c%10; c=c/10; p1->bignum[k]=temp; k++;} p1->bignum[k]=c; p1->bignum[MAX-1]=k+1;count=count+1;if(count==1) h=p1;else p2->next=p1;p2=p1; p1=(struct slink *)malloc(LEN);} p2->next=NULL; printf(“n”); fclose(fp); // printf(“加密后文件的保存路徑 : n”);// scanf(“%s”,encryfile);// fp=fopen(encryfile,“w”); fp=fopen(filename,“w”); p=p1=(struct slink *)malloc(LEN); p=h; printf(“n加密后文件中所形成密文：nn”); if(h!=NULL)do { expmod(p->bignum , e ,n ,p1->bignum); ch=p1->bignum[MAX-2]; printf(“%c”,ch); fputc(ch,fp); if((p1->bignum[MAX-1]/10)==0)/*/判斷p1->bignum[99]的是否大于十；*/ { ch=0+48; printf(“%c”,ch); fputc(ch,fp); ch=p1->bignum[MAX-1]+48; printf(“%c”,ch); fputc(ch,fp); } else { ch=p1->bignum[MAX-1]/10+48; printf(“%c”,ch); fputc(ch,fp); ch=p1->bignum[MAX-1]%10+48; printf(“%c”,ch); fputc(ch,fp); } for(i=0;i bignum[MAX-1];i++) { printf(“%d”,p1->bignum[i]); ch=p1->bignum[i]+48; fputc(ch,fp); } p=p->next; p1=(struct slink *)malloc(LEN);}while(p!=NULL);printf(“nn”); fclose(fp);return;} void tdecrypto(int d[MAX], int n[MAX]){ FILE *fp; struct slink *h,*p1,*p2; char ch,encryfile[25],decryfile[25]; int i,j,k,c,count,temp; printf(“n輸入加密過(guò)的文件路徑 : ”); scanf(“%s”,encryfile); if((fp=fopen(encryfile,“r”))==NULL) { printf(“此文件不存在!n”); exit(0); } printf(“n文件中密文內(nèi)容：nn”); i=0; j=3; count=0; h=p1=p2=(struct slink *)malloc(LEN); while((ch=fgetc(fp))!=EOF) { putchar(ch); c=ch; if(j==3) { p1->bignum[MAX-2]=c; j--; } else if(j==2) { temp=c-48; j--; } else if(j==1) { p1->bignum[MAX-1]=temp*10+c-48; j--; } else if(j==0) { p1->bignum[i]=c-48; i++; if(i==p1->bignum[MAX-1]) { i=0; j=3; count++; if(count==1) h=p1; else p2->next=p1; p2=p1; p1=(struct slink *)malloc(LEN); } } } p2->next=NULL; printf(“n”); fclose(fp); // printf(“解密后的明文文件保存路徑 : n”);// scanf(“%s”,decryfile);// fp=fopen(decryfile,“w”); fp=fopen(encryfile,“w”);printf(“n解密密文后文件中的明文:nn”);p2=(struct slink *)malloc(LEN); p1=h;k=0;if(h!=NULL)/*/temp為暫存ASIIC碼的int值*/ do { for(i=0;i p2->bignum[i]=0; expmod(p1->bignum , d ,n ,p2->bignum); temp=p2->bignum[0]+p2->bignum[1]*10+p2->bignum[2]*100; if((p2->bignum[MAX-2])=='0') { temp=0-temp; }/*/轉(zhuǎn)化為正確的ASIIC碼，如-78-96形成漢字 */ ch=temp;/* str[k]--->ch */ printf(“%c”,ch);/* str[k]--->ch */ fputc(ch,fp);/*/寫(xiě)入文件str[k]--->ch*/ k++; p1=p1->next; p2=(struct slink *)malloc(LEN); }while(p1!=NULL); printf(“nn”); fclose(fp);return;} struct slink *input(void)/*/輸入明文并且返回頭指針，沒(méi)有加密時(shí)候轉(zhuǎn)化的數(shù)字*/ { 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請(qǐng)輸入你所要加密的內(nèi)容 : n”);while((ch=getchar())!='n') { i=0;c=ch;if(c<0){ c=abs(c);/*/把負(fù)數(shù)取正并且做一個(gè)標(biāo)記*/ 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);} struct slink *jiami(int e[MAX],int n[MAX],struct { struct slink *p; struct slink *h; struct slink *p1,*p2; int m=0,i;printf(“n”); printf(“加密后形成的密文內(nèi)容：n”);p1=p2=(struct slink*)malloc(LEN);h=NULL; p=head; if(head!=NULL)do slink *head){ expmod(p->bignum , e ,n ,p1->bignum); for(i=0;i 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); } void 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 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 printf(“%c”,ch[i]);printf(“n”);return; } void menu(){ printf(“nnn”);printf(“nnn”);printf(“ R--------產(chǎn)生密鑰對(duì) nnn”); printf(“ S--------保存密鑰對(duì) nnn”);printf(“ L--------載入密鑰對(duì) nnn”);printf(“ E--------對(duì)文件加密 nnn”);printf(“ D--------對(duì)文件解密 nnn”);printf(“ T--------簡(jiǎn)單測(cè)試 nnn”);printf(“ Q--------退出 nnn”);printf(“請(qǐng)選擇一種操作：”);} /*/------------------主MAIN函數(shù)----/*/ 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 m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0;/*/簡(jiǎn)單初始化一下*/ while(1) { menu(); c=getchar(); getchar();//接受回車(chē)符 if((c=='r')||(c=='R'))//操作r產(chǎn)生密鑰對(duì) { for(i=0;i m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0; printf(“nnnnnnnnn”); printf(“nn隨機(jī)密鑰對(duì)產(chǎn)生如下：nn”); prime_random(p,q);/*/隨機(jī)產(chǎn)生兩個(gè)大素?cái)?shù)*/ mul(p,q,n); printf(“由 p、q 得出 n :”); print(n); mov(p,p1); p1[0]--; mov(q,q1); q1[0]--; /*/q-1;*/ mul(p1,q1,m);//m=(p-1)*(q-1) erand(e,m); rsad(e,m,d); printf(“密鑰對(duì)產(chǎn)生完成，現(xiàn)在可以直接進(jìn)行加解密文件!n”); printf(“n按任意鍵回主菜單…………”); getchar();} else if((c=='l')||(c=='L')) { printf(“nn選擇導(dǎo)入密鑰類(lèi)型：加密密鑰(P)還是解密密鑰(S)?”); c=getchar(); getchar(); if((c=='p')||(c=='P')) loadpkey(e,n); else if((c=='s')||(c=='S')) loadskey(d,n); printf(“n按任意鍵回主菜單…………”); getchar(); } else if((c=='e')||(c=='E')) { tencrypto(e, n); printf(“n加密文件操作完成!n”); printf(“n按任意鍵回主菜單…………”); getchar(); getchar(); } else if((c=='d')||(c=='D')) { tdecrypto(d, n); printf(“n解密文件操作完成!n”); printf(“n按任意鍵回主菜單…………”); getchar(); getchar(); } else if((c=='s')||(c=='S')) { savepkey(e,n); printf(“n”); saveskey(d,n); printf(“n按任意鍵回主菜單…………”); getchar(); getchar(); } else if((c=='T')||(c=='t')) { head=input(); h1=jiami(e, n, head); jiemi(d, n, h1); printf(“nRSA測(cè)試工作完成!n”); printf(“n按任意鍵回主菜單…………”); getchar(); } else if((c=='Q')||(c=='q')) break; } } #include #include #include //將十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制，用于檢驗(yàn)大素?cái)?shù)p和q int zhuan_huan(int b,int a[],int k) { int t,temp=-1; while(b>0){ t=b%2; temp++; a[temp]=t; b=b/2; } return temp; } //歐幾里得算法，用于判斷加密指數(shù)e是否符合要求 int gcd(int n,int b) { int r1=n,r2=b,r; while(r2>0){ r=r1%r2; r1=r2; r2=r; } return r1; } //擴(kuò)展歐幾里得算法求乘法逆元，即求解密指數(shù)d int extend(int n,int b) { int q,r,r1=n,r2=b,t,t1=0,t2=1,i=1; while(r2>0) { q=r1/r2; r=r1%r2; r1=r2;r2=r; t=t1-q*t2; t1=t2; t2=t; } if(t1>=0)return t1%n; else{ while((t1+i*n)<0) i++; return t1+i*n; } } //檢驗(yàn)大素?cái)?shù)，符合要求返回1，否則返回0 int Witness(int a,int n) { int d=1,k,r=n-1,i,x,b[1000]; k=zhuan_huan(r,b,1000); for(i=k;i>=0;i--){ x=d; d=(d*d)%n; if((d==1)&&(x!=1)&&(x!=n-1))return 0; if(b[i]==1)d=(d*a)%n; } if(d!=1)return 0; else return 1; } //快速計(jì)算模指數(shù) int js_mod(int a,int b,int n) { int x=0,y=1,k,i,s[1000]; k=zhuan_huan(b,s,1000); for(i=k;i>=0;i--){ x=2*x; y=(y*y)%n; if(s[i]==1){ x++; y=(y*a)%n; } } return y; } //主函數(shù)。。。。。。。。。。。。。。。。。。。。。。 void main() { int p,q,e,d,n,yn,m[1000],c[10000];//c[10000]存放加密后的數(shù)字密文，m[1000]存放解密后的數(shù)字明文，即英文明文在zimu_biao[69]中的下標(biāo)。 int i,j;//i,j用于循環(huán)遍歷數(shù)組 int mi_yue;//用戶(hù)輸入的密鑰 int count=1;//統(tǒng)計(jì)輸入密鑰的次數(shù)，count>3時(shí)將不允許用戶(hù)再輸入。 char min_wen[1000],re_min_wen[1000];//分別為用戶(hù)輸入的明文、密文，解密后的明文。//密鑰生成char zimu_biao[69]=“abcdefghijklmnopqrstuvwxyz,ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789'.?!”; printf(“請(qǐng)輸入您要發(fā)送的明文文件（小寫(xiě)英文表示）:n”); printf(“******************************************************n”); gets(min_wen); printf(“******************************************************n”); printf(“n加密開(kāi)始，請(qǐng)按要求操作。。nn”); printf(“請(qǐng)輸入第一個(gè)大素?cái)?shù)p：n”); while(1){ scanf(“%d”,&p); if(Witness(2,p)==1){ printf(“您輸入的第一個(gè)大素?cái)?shù) %d 符合要求n”,p); break; } else printf(“您輸入的 %d 不是素?cái)?shù),請(qǐng)重新輸入：n”,p); } printf(“請(qǐng)輸入第二個(gè)大素?cái)?shù)q：n”); while(1){ scanf(“%d”,&q); if(Witness(2,q)){ printf(“您輸入的第二個(gè)大素?cái)?shù) %d 符合要求n”,q); break; } else printf(“您輸入的 %d 不是素?cái)?shù),請(qǐng)重新輸入：n”,q); } n=p*q;yn=(p-1)*(q-1); printf(“請(qǐng)輸入加密指數(shù)（整數(shù)）e,且0 scanf(“%d”,&e); if(gcd(yn,e)==1){ printf(“您輸入加密指數(shù) %d 與 %d 互素,符合要求n”,e,yn); break; } else printf(“您輸入加密指數(shù) %d 與 %d 不互素,請(qǐng)重新輸入。。n”,e,yn); } d=extend(yn,e);//求解密指數(shù)d printf(“nn請(qǐng)記住您的兩個(gè)大素?cái)?shù)分別為p=%d(保密),q=%d(保密),模數(shù)n=%d(公開(kāi)),歐拉函數(shù)yn=%d(保密),加密指數(shù)e=%d(公鑰,公開(kāi)),。。解密指數(shù) d=%d(私鑰,保密)nn”,p,q,n,yn,e,d); //明文轉(zhuǎn)換過(guò)程 /* scanf(“%s”,min_wen); printf(“%s”,min_wen);*/ for(i=0;i for(j=0;j<68;j++)//for(j=0;j<26;j++) if(min_wen[i]==zimu_biao[j]) m[i]=j;//將字符串明文換成數(shù)字，并存到整型數(shù)組m里面，即明文的另一種表示方法 //加密過(guò)程 for(i=0;i c[i]=js_mod(m[i],e,n); printf(“輸出密文：n”); printf(“******************************************************n”); for(i=0;i printf(“%d”,c[i]); printf(“n******************************************************n”); //解密過(guò)程 for(i=0;i m[i]=js_mod(c[i],d,n); for(i=0;i re_min_wen[i]=zimu_biao[m[i]]; //提示用戶(hù)解密 printf(“nn您有3次輸入密鑰的機(jī)會(huì)，密鑰正確后將進(jìn)行解密顯示明文，3次輸入錯(cuò)誤解密將終止，請(qǐng)注意。。nn”); while(1){ scanf(“%d”,&mi_yue); if(mi_yue==d){ printf(“密鑰輸入正確，您得到的明文為：nn”); for(i=0;i printf(“%c”,re_min_wen[i]); printf(“nn”); break; } else{ }} }}printf(“您第%d次輸入的密鑰錯(cuò)誤，請(qǐng)重新輸入。。n”,count);count++;if(count>3){printf(“n您已%d次輸入的密鑰錯(cuò)誤，將不允許繼續(xù)輸入n”,count-1);break; C 語(yǔ) 言 課 程 設(shè) 計(jì) 實(shí) 驗(yàn) 報(bào) 告 實(shí)驗(yàn)名稱(chēng)：文件加密解密 院系：軟件學(xué)院 學(xué)號(hào)： 年9月3日—9月17日 日期：2012 一：設(shè)計(jì)題目 1：設(shè)計(jì)圖形用戶(hù)界面。 2：對(duì)文件進(jìn)行加密并對(duì)加密文件進(jìn)行保存。3：對(duì)加密了的文件進(jìn)行解密。 二：設(shè)計(jì)過(guò)程 設(shè)計(jì)過(guò)程中遇到的困難和解決方法： 1：不能很好地理解題意（通過(guò)老師的講解）。 2：不知道如何設(shè)計(jì)加密解密程序（通過(guò)翻閱書(shū)籍和上網(wǎng)查找資料）過(guò)程： 首先通過(guò)學(xué)習(xí)老師提供的資料了解大致的設(shè)計(jì)過(guò)程并懂得運(yùn)用一些以前沒(méi)有學(xué)習(xí)過(guò)的c語(yǔ)言。先利用文本文件設(shè)計(jì)出加密解密的主要過(guò)程并能運(yùn)行。知道如何運(yùn)用fopen將原文件打開(kāi)并用fread將原文件內(nèi)容讀出來(lái)，然后進(jìn)行加密設(shè)計(jì)并將加密的數(shù)據(jù)用fwrite寫(xiě)進(jìn)指定的文件中并保存。然后讀出加密的文件并解密并保存。最后在寫(xiě)出的程序中加入圖形用戶(hù)界面，運(yùn)用window，box，gotoxy等進(jìn)行設(shè)計(jì)。 三：源代碼 #include ///////////////////////////////////////////////////////////////加密解密 */ void fun(char *list,char *sd)/*加密過(guò)程*/ { FILE *fp1,*fp2;char buf[1000];/*文件臨時(shí)存放處*/ register int ch;fp1=fopen(“e:list.txt”,“r”);/*用可讀方式打開(kāi)文件*/ fp2=fopen(“e:sd.txt”,“w”);/*用可寫(xiě)方式創(chuàng)建一個(gè)文件*/ if(fp1==NULL){ printf(“cannot open filen”);exit(1);} if(fp2==NULL){ printf(“cannot build filen”);exit(1);} ch=fgetc(fp1);/*讀出打開(kāi)文件的光標(biāo)處的一個(gè)字符*/ while(!feof(fp1))/*讀出的字符不是最后的字符*/ { ch=ch<<1;/*加密方法*/ fputc(ch,fp2);/*加密的字符存放在指定的地方*/ ch=fgetc(fp1); } rewind(fp2);/*將光標(biāo)移動(dòng)到第一個(gè)字符前面*/ fread(buf,sizeof(buf),1,fp2);/*從文件的當(dāng)前位置開(kāi)始中讀取buf中存放的數(shù)據(jù)*/ printf(“%s”,buf);/*fclose(fp1);fclose(fp2);*/ } void man(char *sd,char *ds)/*解密過(guò)程*/ { /*int n=0;*/ FILE *fp2,*fp3;register int fh;char buf1[1000]; fp2=fopen(“e:sd.txt”,“rb”);/*用可讀方式打開(kāi)文件*/ fp3=fopen(“e:ds.txt”,“wb”);/*用可寫(xiě)方式創(chuàng)建一文件*/ if(fp2==NULL){ printf(“cannot open filen”);exit(1);} if(fp3==NULL){ printf(“cannot build filen”);exit(1);} fh=fgetc(fp2);/*從光標(biāo)處讀出一個(gè)字符*/ while(!feof(fp2))/*當(dāng)讀出的字符到達(dá)最后一個(gè)則停止*/ { fh=fh>>1;/*解密方式*/ fputc(fh,fp3);/*解密的字符存放在指定的地方*/ fh=fgetc(fp2);} fread(buf1,sizeof(buf1),1,fp3);/*讀出buf1中所存放的數(shù)據(jù)*/ printf(“%s”,buf1);} void main(){ int k;char *f[]={“jiami”,“jiemi”};/**界面的形式/ int key,y;int j,q;char list[300];char sd[300];char ds[300];char ch,fh;char buf[1000];char buf1[1000];FILE *fp1;FILE *fp2;int l1,l2;window(1,1,80,25);/*left,top,right,bottom,相對(duì)于屏幕的字符坐標(biāo)，屏幕原點(diǎn)在左上角*/ gettext(20,10,40,14,buf);/*保存矩形屏幕上的字符*/ textbackground(7);/*背景顏色*/ textcolor(0);/*字體顏色*/ clrscr();/*清除矩形屏幕上的所有字符*/ gotoxy(24,10);/*將當(dāng)前字符屏幕的光標(biāo)位置移動(dòng)到x,y的坐標(biāo)位子*/ printf(“%s”,f[0]);gotoxy(24,14);printf(“%s”,f[1]);gettext(10,8,60,16,buf);box(22,9,3,30);/*建立一個(gè)小窗口*/ key=0;while(1){ while(bioskey(1)==0);/*讀取鍵盤(pán)值查詢(xún)鍵盤(pán)是否按下*/ key=get_key();/*按下了什么鍵盤(pán)*/ if(key==key_up||key==key_down){ y=wherey();/*得到字符模式下窗口光標(biāo)的x坐標(biāo)數(shù)值*/ if(key==key_up)y=y==10? y+4:10;/*當(dāng)y=10光標(biāo)向下移動(dòng)四個(gè)位置否則將光標(biāo)移動(dòng)到y(tǒng)=10處*/ if(key==key_down)y=y==14? y-4:14;/*當(dāng)y=14光標(biāo)向下移動(dòng)四個(gè)位置否則將光標(biāo)移動(dòng)到y(tǒng)=14處*/ puttext(10,8,60,16,buf);/*將gettext函數(shù)保存的字符恢復(fù)到屏幕上 */ gotoxy(24,y); if(y==10){ textbackground(7);textcolor(0);box(22,9,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[0]);} else { textbackground(7);textcolor(0);box(22,13,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[1]);} } if(key==key_enter&&y==10)且光標(biāo)在y=10處 /*當(dāng)按下enter鍵且光標(biāo)在y=10處進(jìn)行下步*/ { clrscr();textbackground(3);textcolor(15);/*clrscr();*/ gotoxy(24,5);printf(“input the file name for jiamin”);/*用戶(hù)給需要加密的文件加密 */ l1=strlen(“input the file name for jiami:”);/*待求長(zhǎng)度的字符串指針*/ gotoxy(24+l1,5);scanf(“%s”,list);gotoxy(24,10);printf(“input file name for saven”);/*給加密后的文件命名，并保存*/ l2=strlen(“input file name for save:”);gotoxy(24+l2,10);scanf(“%s”,sd);fun(list,sd);fp1=fopen(“e:sd.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp1);gotoxy(10,15);printf(“%sn”,buf1);getch();printf(“file haven jiami ,save now”);getche();break;} if(key==key_enter&&y==14){ clrscr();textbackground(3);textcolor(15);gotoxy(24,5); printf(“input the file name for jiemi n”);/*用戶(hù)給需要解密的文件解密 */ l1=strlen(“input the file name for jiemi: ”);gotoxy(24+l1,5);scanf(“%s”,sd);gotoxy(24,10);printf(“input file name for save：n”);/*對(duì)解密的文件系統(tǒng)又可以提供保存路徑 */ l2=strlen(“input file name for save: ”);gotoxy(24+l2,10);scanf(“%s”,ds);man(sd,ds);fp2=fopen(“e:ds.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp2);gotoxy(10,15);printf(“%sn”,buf1);getch(); printf(“file haven jiemi,save now”);getche();break;} } window(1,1,80,25);gettext(20,10,40,14,buf); textbackground(7);textcolor(0);clrscr();gotoxy(24,10);printf(“%s”,f[0]);gotoxy(24,14);printf(“%s”,f[1]);gettext(10,8,60,16,buf);box(22,9,3,30);key=0;while(1){ while(bioskey(1)==0);key=get_key(); if(key==key_up||key==key_down){ y=wherey();if(key==key_up)y=y==10? y+4:10;if(key==key_down)y=y==14? y-4:14;puttext(10,8,60,16,buf); gotoxy(24,y); if(y==10)/*光標(biāo)在10處的窗口*/ { textbackground(7);textcolor(0);box(22,9,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[0]);} else { textbackground(7);textcolor(0);box(22,13,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[1]);} } if(key==key_enter&&y==10){ clrscr();textbackground(3);textcolor(15);/*clrscr();*/ gotoxy(24,5);printf(“input the file name for jiamin”);/*用戶(hù)給需要加密的文件加密 */ l1=strlen(“input the file name for jiami:”);gotoxy(24+l1,5);scanf(“%s”,list);gotoxy(24,10);printf(“input file name for saven”);/*給加密后的文件命名，并保存*/ l2=strlen(“input file name for save:”);gotoxy(24+l2,10);scanf(“%s”,sd);fun(list,sd);fp1=fopen(“e:sd.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp1);gotoxy(10,15);printf(“%sn”,buf1);getch();printf(“file haven jiami ,save now”);getche();} if(key==key_enter&&y==14){ clrscr();textbackground(3);textcolor(15);gotoxy(24,5); printf(“input the file name for jiemi n”);/*用戶(hù)給需要解密的文件解密 */ l1=strlen(“input the file name for jiemi: ”);gotoxy(24+l1,5);scanf(“%s”,sd);gotoxy(24,10);printf(“input file name for save：n”);/*對(duì)解密的文件系統(tǒng)又可以提供保存路徑 */ l2=strlen(“input file name for save: ”);gotoxy(24+l2,10);scanf(“%s”,ds);man(sd,ds);fp2=fopen(“e:ds.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp2);gotoxy(10,15);printf(“%sn”,buf1);getch(); printf(“file haven jiemi,save now”);getche();break;} } } int get_key(){ union REGS rg;rg.h.ah=0;int86(0x16,&rg,&rg);return rg.h.ah;getchar();} void box(int startx,int starty,int high,int width)/*的建立*/ { int i;gotoxy(startx,starty);putch(0xda);for(i=startx+1;i for(i=starty+1;i 屏幕 } gotoxy(startx,starty+high-1);putch(0xc0);gotoxy(startx+1,starty+high-1);for(i=startx+1;i 通過(guò)這次的作業(yè)我覺(jué)得最大的收獲是不僅把平時(shí)學(xué)習(xí)到的知識(shí)理解的更加透徹，而且使知識(shí)更加系統(tǒng)化，同時(shí)還把有些平時(shí)不太注意的小問(wèn)題發(fā)現(xiàn)了出來(lái)，這不但有利于我學(xué)習(xí)C語(yǔ)言，而且對(duì)于我學(xué)習(xí)任何一門(mén)課程都是很有益處的。總之，做這份作業(yè)對(duì)于我們學(xué)習(xí)C語(yǔ)言有很大的幫助。 在做課程設(shè)計(jì)時(shí)，由于運(yùn)用了很多新知識(shí)，新的方法，還有題目更加復(fù)雜，應(yīng)用性更強(qiáng)，在編寫(xiě)過(guò)程中遇到了很多困難，從而使自己能夠?qū)W習(xí)到更多以前不懂，難懂的東西。 信息安全實(shí)驗(yàn)報(bào)告 題 目 RSA算法 姓 名 學(xué) 號(hào) 專(zhuān)業(yè)年級(jí) 計(jì)算機(jī)科學(xué)與技術(shù)2014級(jí)（1）班 指導(dǎo)教師 2016年 12 月 10日 一、實(shí)驗(yàn)?zāi)康?/p> 了解非對(duì)稱(chēng)加密機(jī)制 理解RSA算法的加解密原理 熟悉Java的學(xué)習(xí)以及運(yùn)用Java實(shí)現(xiàn)RSA算法的加解密過(guò)程 二、實(shí)驗(yàn)背景 鑰密碼體制中，加密密鑰(即公開(kāi)密鑰)PK是公開(kāi)信息，而解密密鑰(即秘密密鑰)SK是需要保密的。加密算法E和解密算法D也都是公開(kāi)的。雖然秘密密鑰SK是由公開(kāi)密鑰PK決定的，但卻不能根據(jù)PK計(jì)算出SK。正是基于這種理論，1978年出現(xiàn)了著名的RSA算法，它通常是先生成一對(duì)RSA 密鑰，其中之一是保密密鑰，由用戶(hù)保存；另一個(gè)為公開(kāi)密鑰，可對(duì)外公開(kāi)，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)。為提高保密強(qiáng)度，RSA密鑰至少為500位長(zhǎng)，一般推薦使用1024位。這就使加密的計(jì)算量很大。為減少計(jì)算量，在傳送信息時(shí)，常采用傳統(tǒng)加密方法與公開(kāi)密鑰加密方法相結(jié)合的方式，即信息采用改進(jìn)的DES或IDEA對(duì)話(huà)密鑰加密，然后使用RSA密鑰加密對(duì)話(huà)密鑰和信息摘要。對(duì)方收到信息后，用不同的密鑰解密并可核對(duì)信息摘要。RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在的這么多年里，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。 三、實(shí)驗(yàn)原理 1.非對(duì)稱(chēng)密鑰加解密概述 使用對(duì)稱(chēng)密鑰加密體制進(jìn)行保密通信時(shí)，任意不同的兩個(gè)用戶(hù)之間都應(yīng)該使用互不相同的密鑰。這樣，如果一個(gè)網(wǎng)絡(luò)中有n個(gè)用戶(hù)，他們之間彼此都可能進(jìn)行秘密通信，這時(shí)網(wǎng)絡(luò)中將需要n(n-1)/2個(gè)密鑰(其中，每個(gè)用戶(hù)都需要保存n-1個(gè)密鑰)，這樣巨大的密鑰量給密鑰分配和管理帶來(lái)了極大的困難。另外，隨著計(jì)算機(jī)網(wǎng)絡(luò)，特別是因特網(wǎng)的發(fā)展，網(wǎng)絡(luò)上互不相識(shí)的用戶(hù)可能需要進(jìn)行保密的會(huì)話(huà)(例如，如果用戶(hù)在進(jìn)行電子商務(wù)活動(dòng)時(shí)，需要保密的連接，這時(shí)的客戶(hù)對(duì)象可能根本不是固定的對(duì)象)。最后，對(duì)稱(chēng)密鑰加密機(jī)制難以解決簽名驗(yàn)證問(wèn)題。 非對(duì)稱(chēng)密鑰加密也稱(chēng)為公開(kāi)密鑰加密，或者叫做公鑰加密算法。使用公開(kāi)密鑰密碼的每一個(gè)用戶(hù)都分別擁有兩個(gè)密鑰：加密密鑰和解密密鑰，它們兩者并不相同，并且由加密密鑰得到解密密鑰在計(jì)算機(jī)上是不可行的。每一個(gè)用戶(hù)的加密密鑰都是公開(kāi)的。因此，加密密鑰也稱(chēng)為公開(kāi)密鑰。所有用戶(hù)的公開(kāi)密鑰都將記錄在作用類(lèi)似于電話(huà)號(hào)碼薄的密鑰本上，而它可以被所有用戶(hù)訪(fǎng)問(wèn)，這樣每一個(gè)用戶(hù)都可以得到其他所有用戶(hù)的公開(kāi)密鑰。同時(shí)，每一個(gè)用戶(hù)的解密密鑰將由用戶(hù)保存并嚴(yán)格保密。因此，解密密鑰也稱(chēng)為私有密鑰。 非對(duì)稱(chēng)密碼算法解決了對(duì)稱(chēng)密碼體制中密鑰管理的難題，并提供了對(duì)信息發(fā)送人的身份進(jìn)行驗(yàn)證的手段，是現(xiàn)代密碼學(xué)最重要的發(fā)明。公鑰加密算法一般是將對(duì)密鑰的求解轉(zhuǎn)化為對(duì)數(shù)學(xué)上的困難問(wèn)題的求解，例如RSA算法的安全性是建立在“大數(shù)分解和素性檢測(cè)”這個(gè)數(shù)論難題的基礎(chǔ)上，已知兩個(gè)大素?cái)?shù)a和b，求出a*b是容易計(jì)算的，而已知a*b，想知道其是哪兩個(gè)大素?cái)?shù)的乘積目前還沒(méi)有好的計(jì)算方法，另外也有一些非對(duì)稱(chēng)加密算法(如ELGamal算法)的安全性是基于求“離散對(duì)數(shù)”這個(gè)數(shù)學(xué)難題上的。 在公鑰密碼系統(tǒng)中每個(gè)實(shí)體都有自己的公鑰和相應(yīng)的私鑰。公鑰密碼系統(tǒng)的加密變換和解密變換分別用E和D表示。任何實(shí)體B要向?qū)嶓wA發(fā)送信息m的步驟如下：實(shí)體B首先獲得實(shí)體A的真實(shí)公鑰的拷貝(eA)，實(shí)體B使用eA計(jì)算密文c=E(m)并發(fā)送給實(shí)體A，實(shí)體A使用自己的私鑰dA，計(jì)算m=D(c)解密密文，恢復(fù)出明文m。這里公鑰不需要保密，但要保證它的真實(shí)性，即eA確實(shí)是實(shí)體A掌握的私鑰dA所對(duì)應(yīng)的公鑰。提供真實(shí)的公鑰比安全地分配密鑰實(shí)現(xiàn)起來(lái)要容易得多。這也是公鑰密碼系統(tǒng)的主要優(yōu)點(diǎn)之一。 公鑰密碼系統(tǒng)的主要目的是提供保密性，它不能提供數(shù)據(jù)源認(rèn)證(data origin authentication)和數(shù)據(jù)完整性(data integrity)。數(shù)據(jù)源認(rèn)證是指：指定的數(shù)據(jù)是在以前的某個(gè)時(shí)間確實(shí)是由真正的源創(chuàng)建的。數(shù)據(jù)完整性是指：真正的源創(chuàng)建該數(shù)據(jù)后經(jīng)過(guò)傳輸后存儲(chǔ)沒(méi)有發(fā)生改變。數(shù)據(jù)源認(rèn)證和數(shù)據(jù)完整性要由其他技術(shù)來(lái)提供(如消息認(rèn)證碼技術(shù)、數(shù)字簽名技術(shù)等)。 從本質(zhì)上來(lái)看，公鑰密碼比對(duì)稱(chēng)密鑰密碼加密的速度要慢，粗略的說(shuō)，公鑰加密算法RSA硬件實(shí)現(xiàn)比分組加密算法DES硬件實(shí)現(xiàn)的速度慢1500倍，而軟件實(shí)現(xiàn)的速度要慢100倍。 公鑰解密也可以提供認(rèn)證保證(如：在實(shí)體認(rèn)證協(xié)議、帶認(rèn)證的密鑰建立協(xié)議等)。公鑰加密中必須有頒發(fā)讓發(fā)送消息的人得到想要發(fā)送到的那個(gè)人的公鑰的真實(shí)拷貝，否則就會(huì)受到偽裝攻擊。在實(shí)踐中有很多方法分發(fā)真實(shí)的公鑰，如：使用可信的公共文件，使用在線(xiàn)可信服務(wù)器，使用離線(xiàn)服務(wù)器和認(rèn)證。 2.公鑰加解密的優(yōu)缺點(diǎn)： 1)大型網(wǎng)絡(luò)中的每個(gè)用戶(hù)需要的密鑰數(shù)量少。 2)對(duì)管理公鑰的可信第三方的信任程度要求不高而且是離線(xiàn)的。3)只有私鑰是保密的，而公鑰只要保證它的真實(shí)性。4)多數(shù)公鑰加密比對(duì)稱(chēng)密鑰加密的速度要慢幾個(gè)數(shù)量級(jí)。5)公鑰加密方案的密鑰長(zhǎng)度比對(duì)稱(chēng)加密的密鑰要長(zhǎng)。6)公鑰加密方案沒(méi)有被證明是安全的。 公鑰密碼的概念本身就被公認(rèn)為是密碼學(xué)上的一塊里程碑。三十多年來(lái)的研究表明，公鑰密碼成功地解決了計(jì)算機(jī)網(wǎng)絡(luò)安全中的密鑰管理，身份認(rèn)證和數(shù)字簽名等問(wèn)題，已經(jīng)成為信息安全技術(shù)中的重大核心技術(shù)。 四、RSA算法 1.概述 RSA加密算法于1977年由美國(guó)麻省理工學(xué)院的Ronal Rivest，Adi Shamir和Len Adleman三位年輕教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名為RSA算法。這三位科學(xué)家榮獲2002圖靈獎(jiǎng)，以表彰他們?cè)谒惴ǚ矫娴耐怀鲐暙I(xiàn)。該算法利用了數(shù)論領(lǐng)域的一個(gè)事實(shí)，那就是雖然把兩個(gè)大質(zhì)數(shù)相乘生成一個(gè)合數(shù)是件十分容易的事情，但要把一個(gè)合數(shù)分解為兩個(gè)質(zhì)數(shù)的乘積卻十分困難。合數(shù)分解問(wèn)題目前仍然是數(shù)學(xué)領(lǐng)域尚未解決的一大難題，至今沒(méi)有任何高效的分解方法。它無(wú)須收發(fā)雙方同時(shí)參與加密過(guò)程，既可以用于保密也可以用于簽名，因而非常適合于電子郵件系統(tǒng)的加密，互連網(wǎng)和信用卡安全系統(tǒng)。 算法概述：找兩素?cái)?shù)p和q，取n=p*q，取t=(p-1)*(q-1)，取任何一個(gè)數(shù)e，要求滿(mǎn)足e 2.算法設(shè)計(jì) 1)publicstaticvoid GetPrime()說(shuō)明：利用Java語(yǔ)言的中的java.math.BigInteger類(lèi)的方法中隨機(jī)產(chǎn)生大數(shù)。 2)public static boolean MillerRobin(BigInteger num)參數(shù)說(shuō)明：num是由GetPrime方法產(chǎn)生的大數(shù)。 說(shuō)明：這個(gè)方法判斷GetPrime方法傳過(guò)來(lái)的是否是一個(gè)素?cái)?shù)，是就返回true,否就返回false。 3)public static BigInteger powmod(BigIntegera，BigIntegert，BigInteger num)說(shuō)明：這個(gè)方法對(duì)傳入的大數(shù)進(jìn)行冪運(yùn)算。 4)public static BigInteger invmod(BigInteger a，BigInteger b)說(shuō)明：這個(gè)方法對(duì)大數(shù)進(jìn)行取模運(yùn)算。 5)public static String Encode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextFieldd)方法名稱(chēng)：加密算法。參數(shù)說(shuō)明： inStr是從界面輸入的明文。 PrimeP和PrimeQ是由GetPrime方法產(chǎn)生的兩個(gè)大素?cái)?shù)。n是由PrimeP和PrimeQ得到的值。nLen為n的長(zhǎng)度。d為公鑰。 6)publicstatic String Decode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextField e)方法名稱(chēng)：解密算法。參數(shù)說(shuō)明： inStr是從界面輸入的明文。 PrimeP和PrimeQ是由GetPrime方法產(chǎn)生的兩個(gè)大素?cái)?shù)。n是由PrimeP和PrimeQ得到的值。nLen為n的長(zhǎng)度。e為私鑰。 在對(duì)稱(chēng)加密中：n，d兩個(gè)數(shù)構(gòu)成公鑰，可以告訴別人；n，e兩個(gè)數(shù)構(gòu)成私鑰，e自己保留，不讓任何人知道。給別人發(fā)送的信息使用e加密，只要?jiǎng)e人能用d解開(kāi)就證明信息是由你發(fā)送的，構(gòu)成了簽名機(jī)制。別人給你發(fā)送信息時(shí)使用d加密，這樣只有擁有e的你能夠?qū)ζ浣饷堋?/p> RSA的安全性在于對(duì)于一個(gè)大數(shù)n，沒(méi)有有效的方法能夠?qū)⑵浞纸鈴亩谝阎猲，d的情況下無(wú)法獲得e；同樣在已知n，e的情況下無(wú)法求得d。 五、實(shí)驗(yàn)結(jié)果 實(shí)驗(yàn)結(jié)果如下圖所示： 六、實(shí)驗(yàn)總結(jié) 本次實(shí)驗(yàn)對(duì)輸入的任意一段明文字母，實(shí)現(xiàn)了輸出對(duì)應(yīng)密鑰的密文字母。親手實(shí)際編寫(xiě)RSA密碼算法代碼，更好的了解和掌握了RSA的相關(guān)內(nèi)容。通過(guò)用Java對(duì)RSA密碼體制進(jìn)行編程，對(duì)RSA密碼體制的加解密過(guò)程有了更深入的理解。通過(guò)這個(gè)實(shí)驗(yàn)更是讓我獲得了很多實(shí)際工作中所要具備的能力。 七、代碼附錄 略 C語(yǔ)言常用算法歸納 應(yīng)當(dāng)掌握的一般算法 一、基本算法： 交換、累加、累乘 二、非數(shù)值計(jì)算常用經(jīng)典算法： 窮舉、排序（冒泡，選擇）、查找（順序即線(xiàn)性） 三、數(shù)值計(jì)算常用經(jīng)典算法： 級(jí)數(shù)計(jì)算（直接、簡(jiǎn)接即遞推）、一元非線(xiàn)性方程求根（牛頓迭代法、二分法）、定積分計(jì)算（矩形法、梯形法） 四、其他： 迭代、進(jìn)制轉(zhuǎn)換、矩陣轉(zhuǎn)置、字符處理（統(tǒng)計(jì)、數(shù)字串、字母大小寫(xiě)轉(zhuǎn)換、加密等）、整數(shù)各數(shù)位上數(shù)字的獲取、輾轉(zhuǎn)相除法求最大公約數(shù)（最小公倍數(shù)）、求最值、判斷素?cái)?shù)（各種變形）、數(shù)組元素的插入（刪除）、二維數(shù)組的其他典型問(wèn)題（方陣的特點(diǎn)、楊輝三角形） 詳細(xì)講解 一、基本算法 1．交換（兩量交換借助第三者） 例 1、任意讀入兩個(gè)整數(shù)，將二者的值交換后輸出。main(){ int a,b,t; scanf(“%d%d”,&a,&b); printf(“%d,%dn”,a,b);t=a;a=b;b=t; printf(“%d,%dn”,a,b);} 1 【解析】程序中加粗部分為算法的核心，如同交換兩個(gè)杯子里的飲料，必須借助第三個(gè)空杯子。 假設(shè)輸入的值分別為3、7，則第一行輸出為3，7；第二行輸出為7，3。其中t為中間變量，起到“空杯子”的作用。 注意：三句賦值語(yǔ)句賦值號(hào)左右的各量之間的關(guān)系！ 【應(yīng)用】 例 2、任意讀入三個(gè)整數(shù)，然后按從小到大的順序輸出。main(){ int a,b,c,t;scanf(“%d%d%d”,&a,&b,&c);/*以下兩個(gè)if語(yǔ)句使得a中存放的數(shù)最小*/ if(a>b){ t=a;a=b;b=t;} if(a>c){ t=a;a=c;c=t;} /*以下if語(yǔ)句使得b中存放的數(shù)次小*/ if(b>c){ t=b;b=c;c=t;} printf(“%d,%d,%dn”,a,b,c);} 2．累加 累加算法的要領(lǐng)是形如“s=s+A”的累加式，此式必須出現(xiàn)在循環(huán)中才能被反復(fù)執(zhí)行，從而實(shí)現(xiàn)累加功能。“A”通常是有規(guī)律變化的表達(dá)式，s在進(jìn)入循環(huán)前必須獲得合適的初值，通常為0。 例 1、求1+2+3+……+100的和。main(){ int i,s;s=0;i=1;while(i<=100){ s=s+i;/*累加式*/ i=i+1;/*特殊的累加式*/ } printf(“1+2+3+...+100=%dn”,s);} 【解析】程序中加粗部分為累加式的典型形式，賦值號(hào)左右都出現(xiàn)的變量稱(chēng)為累加器，其中“i = i + 1”為特殊的累加式，每次累加的值為1，這樣的累加器又稱(chēng)為計(jì)數(shù)器。 3．累乘 累乘算法的要領(lǐng)是形如“s=s*A”的累乘式，此式必須出現(xiàn)在循環(huán)中才能被反復(fù)執(zhí)行，從而實(shí)現(xiàn)累乘功能。“A”通常是有規(guī)律變化的表達(dá)式，s在進(jìn)入循環(huán)前必須獲得合適的初值，通常為1。 例 1、求10！ [分析] 10！=1×2×3×……×10 main(){ int i;long c;c=1;i=1;while(i<=10){ c=c*i;/*累乘式*/ i=i+1;} printf(“1*2*3*...*10=%ldn”,c);} 二、非數(shù)值計(jì)算常用經(jīng)典算法 1．窮舉 也稱(chēng)為“枚舉法”，即將可能出現(xiàn)的每一種情況一一測(cè)試，判斷是否滿(mǎn)足條件，一般采用循環(huán)來(lái)實(shí)現(xiàn)。 例 1、用窮舉法輸出所有的水仙花數(shù)（即這樣的三位正整數(shù)：其每位數(shù)位上的數(shù)字的立方和與該數(shù)相等，比如：1*1*1+5*5*5+3*3*3=153）。 [法一] main(){ int x,g,s,b;for(x=100;x<=999;x++){ g=x%10;s=x/10%10;b=x/100; if(b*b*b+s*s*s+g*g*g==x)printf(“%dn”,x);} } 【解析】此方法是將100到999所有的三位正整數(shù)一一考察，即將每一個(gè)三位正整數(shù)的個(gè)位數(shù)、十位數(shù)、百位數(shù)一一求出（各數(shù)位上的數(shù)字的提取算法見(jiàn)下面的“數(shù)字處理”），算出三者的立方和，一旦與原數(shù)相等就輸出。共考慮了900個(gè)三位正整數(shù)。 [法二] main(){int g,s,b;for(b=1;b<=9;b++)for(s=0;s<=9;s++)for(g=0;g<=9;g++) if(b*b*b+s*s*s+g*g*g==b*100+s*10+g)printf(“%dn”,b*100+s*10+g);} 【解析】此方法是用1到9做百位數(shù)字、0到9做十位和個(gè)位數(shù)字，將組成的三位正整數(shù)與每一組的三個(gè)數(shù)的立方和進(jìn)行比較，一旦相等就輸出。共考慮了900個(gè)組合（外循環(huán)單獨(dú)執(zhí)行的次數(shù)為9，兩個(gè)內(nèi)循環(huán)單獨(dú)執(zhí)行的次數(shù)分別為10次，故if語(yǔ)句被執(zhí)行的次數(shù)為9×10×10=900），即900個(gè)三位正整數(shù)。與法一判斷的次數(shù)一樣。 2．排序 （1）冒泡排序（起泡排序） 假設(shè)要對(duì)含有n個(gè)數(shù)的序列進(jìn)行升序排列，冒泡排序算法步驟是： ①?gòu)拇娣判蛄械臄?shù)組中的第一個(gè)元素開(kāi)始到最后一個(gè)元素，依次對(duì)相鄰兩數(shù)進(jìn)行比較，若前者大后者小，則交換兩數(shù)的位置； ②第①趟結(jié)束后，最大數(shù)就存放到數(shù)組的最后一個(gè)元素里了，然后從第一個(gè)元素開(kāi)始到倒數(shù)第二個(gè)元素，依次對(duì)相鄰兩數(shù)進(jìn)行比較，若前者大后者小，則交換兩數(shù)的位置； ③重復(fù)步驟①n-1趟，每趟比前一趟少比較一次，即可完成所求。例 1、任意讀入10個(gè)整數(shù)，將其用冒泡法按升序排列后輸出。#define n 10 main(){ int a[n],i,j,t;for(i=0;i scanf(“%d”,&a[i]);for(j=1;j<=n-1;j++) /*n個(gè)數(shù)處理n-1趟*/ for(i=0;i<=n-1-j;i++)/*每趟比前一趟少比較一次*/ if(a[i]>a[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;} for(i=0;i （2）選擇法排序 選擇法排序是相對(duì)好理解的排序算法。假設(shè)要對(duì)含有n個(gè)數(shù)的序列進(jìn)行升序排列，算法步驟是： ①?gòu)臄?shù)組存放的n個(gè)數(shù)中找出最小數(shù)的下標(biāo)（算法見(jiàn)下面的“求最值”），然后將最小數(shù)與第1個(gè)數(shù)交換位置； ②除第1個(gè)數(shù)以外，再?gòu)钠溆鄋-1個(gè)數(shù)中找出最小數(shù)（即n個(gè)數(shù)中的次小數(shù)）的下標(biāo)，將此數(shù)與第2個(gè)數(shù)交換位置； ③重復(fù)步驟①n-1趟，即可完成所求。 例 1、任意讀入10個(gè)整數(shù)，將其用選擇法按升序排列后輸出。#define n 10 main(){ int a[n],i,j,k,t;for(i=0;i if(a[j] < a[k])k = j; if(k!= i){ t = a[i];a[i] = a[k];a[k] = t;} } for(i=0;i printf(“%dn”,a[i]);} （3）插入法排序 要想很好地掌握此算法，先請(qǐng)了解“有序序列的插入算法”，就是將某數(shù)據(jù)插入到一個(gè)有序序列后，該序列仍然有序。插入算法參見(jiàn)下面的“數(shù)組元素的插入”。 例 1、將任意讀入的整數(shù)x插入一升序數(shù)列后，數(shù)列仍按升序排列。#define n 10 main(){ int a[n]={-1,3,6,9,13,22,27,32,49},x,j,k; /*注意留一個(gè)空間給待插數(shù)*/ scanf(“%d”,&x);if(x>a[n-2])a[n-1]=x; /*比最后一個(gè)數(shù)還大就往最后一個(gè)元素中存放*/ else /*查找待插位置*/ { j=0; while(j<=n-2 && x>a[j])j++; for(k=n-2;k>=j;k--)/*從最后一個(gè)數(shù)開(kāi)始直到待插位置上的數(shù)依次后移一位*/ a[k+1]=a[k]; a[j]=x; /*插入待插數(shù)*/ } for(j=0;j<=n-1;j++)printf(“%d ”,a[j]);} 插入法排序的要領(lǐng)就是每讀入一個(gè)數(shù)立即插入到最終存放的數(shù)組中，每次插入都使得該數(shù)組有序。 例 2、任意讀入10個(gè)整數(shù)，將其用插入法按降序排列后輸出。（提示：將第2至第10個(gè)數(shù)一一有序插入到數(shù)組a中）#define n 10 main(){ int a[n],i,j,k,x;scanf(“%d”,&a[0]);/*讀入第一個(gè)數(shù)，直接存到a[0]中*/ for(j=1;j { scanf(“%d”,&x); if(x else /*以下查找待插位置*/ { i=0; while(x /*以下for循環(huán)從原最后一個(gè)數(shù)開(kāi)始直到待插位置上的數(shù)依次后移一位*/ for(k=j-1;k>=i;k--)a[k+1]=a[k]; a[i]=x;/*插入待插數(shù)*/ } } for(i=0;i （4）歸并排序 即將兩個(gè)都升序（或降序）排列的數(shù)據(jù)序列合并成一個(gè)仍按原序排列的序列。 例 1、有一個(gè)含有6個(gè)數(shù)據(jù)的升序序列和一個(gè)含有4個(gè)數(shù)據(jù)的升序序列，將二者合并成一個(gè)含有10個(gè)數(shù)據(jù)的升序序列。 #define m 6 #define n 4 main(){ int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22};int i,j,k,c[m+n];i=j=k=0;while(i /*將a、b數(shù)組中的較小數(shù)依次存放到c數(shù)組中*/ { if(a[i] else {c[k]=b[j];j++;} k++;} while(i>=m && j （1）順序查找（即線(xiàn)性查找）順序查找的思路是：將待查找的量與數(shù)組中的每一個(gè)元素進(jìn)行比較，若有一個(gè)元素與之相等則找到；若沒(méi)有一個(gè)元素與之相等則找不到。 例 1、任意讀入10個(gè)數(shù)存放到數(shù)組a中，然后讀入待查找數(shù)值，存放到x中，判斷a中有無(wú)與x等值的數(shù)。 #define N 10 main(){ int a[N],i,x;for(i=0;i （2）折半查找（即二分法） 順序查找的效率較低，當(dāng)數(shù)據(jù)很多時(shí)，用二分法查找可以提高效率。使用二分法查找的前提是數(shù)列必須有序。 二分法查找的思路是：要查找的關(guān)鍵值同數(shù)組的中間一個(gè)元素比較，若相同則查找成功，結(jié)束；否則判別關(guān)鍵值落在數(shù)組的哪半部分，就在這半部分中按上述方法繼續(xù)比較，直到找到或數(shù)組中沒(méi)有這樣的元素值為止。 例 1、任意讀入一個(gè)整數(shù)x，在升序數(shù)組a中查找是否有與x等值的元素。#define n 10 main(){ int a[n]={2,4,7,9,12,25,36,50,77,90};int x,high,low,mid;/*x為關(guān)鍵值*/ scanf(“%d”,&x);high=n-1;low=0;mid=(high+low)/2;while(a[mid]!=x&&low else low=mid+1;/*修改區(qū)間下界*/ mid=(high+low)/2;} if(x==a[mid])printf(“Found %d,%dn”,x,mid);else printf(“Not foundn”);} 三、數(shù)值計(jì)算常用經(jīng)典算法 1．級(jí)數(shù)計(jì)算 級(jí)數(shù)計(jì)算的關(guān)鍵是“描述出通項(xiàng)”，而通項(xiàng)的描述法有兩種：一為直接法、二為間接法又稱(chēng)遞推法。 直接法的要領(lǐng)是：利用項(xiàng)次直接寫(xiě)出通項(xiàng)式；遞推法的要領(lǐng)是：利用前一個(gè)（或多個(gè)）通項(xiàng)寫(xiě)出后一個(gè)通項(xiàng)。 可以用直接法描述通項(xiàng)的級(jí)數(shù)計(jì)算例子有：（1）1+2+3+4+5+…… （2）1+1/2+1/3+1/4+1/5+……等等。 可以用間接法描述通項(xiàng)的級(jí)數(shù)計(jì)算例子有：（1）1+1/2+2/3+3/5+5/8+8/13+……（2）1+1/2!+1/3!+1/4!+1/5!+……等等。（1）直接法求通項(xiàng) 例 1、求1+1/2+1/3+1/4+1/5+……+1/100的和。main(){ float s;int i;s=0.0;for(i=1;i<=100;i++)s=s+1.0/i;printf(“1+1/2+1/3+...+1/100=%fn”,s);} 【解析】程序中加粗部分就是利用項(xiàng)次i的倒數(shù)直接描述出每一項(xiàng)，并進(jìn)行累加。注意：因?yàn)閕是整數(shù)，故分子必須寫(xiě)成1.0的形式！ （2）間接法求通項(xiàng)（即遞推法） 例 2、計(jì)算下列式子前20項(xiàng)的和：1+1/2+2/3+3/5+5/8+8/13+……。[分析]此題后項(xiàng)的分子是前項(xiàng)的分母，后項(xiàng)的分母是前項(xiàng)分子分母之和。main(){ float s,fz,fm,t,fz1;int i;s=1;/*先將第一項(xiàng)的值賦給累加器s*/ fz=1;fm=2;t=fz/fm;/*將待加的第二項(xiàng)存入t中*/ for(i=2;i<=20;i++){ s=s+t; /*以下求下一項(xiàng)的分子分母*/ fz1=fz;/*將前項(xiàng)分子值保存到fz1中*/ fz=fm;/*后項(xiàng)分子等于前項(xiàng)分母*/ fm=fz1+fm;/*后項(xiàng)分母等于前項(xiàng)分子、分母之和*/ t=fz/fm;} printf(“1+1/2+2/3+...=%fn”,s);} 下面舉一個(gè)通項(xiàng)的一部分用直接法描述，另一部分用遞推法描述的級(jí)數(shù)計(jì)算的例子： 例 3、計(jì)算級(jí)#include 數(shù)的值，當(dāng)通項(xiàng)的絕對(duì)值小于eps時(shí)計(jì)算停止。 { float x,eps;scanf(“%f%f”,&x,&eps);printf(“n%f,%fn”,x,g(x,eps));} float g(float x,float eps){ int n=1;float s,t;s=1;t=1;do { t=t*x/(2*n); s=s+(n*n+1)*t;/*加波浪線(xiàn)的部分為直接法描述部分，t為遞推法描述部分*/ n++;}while(fabs(t)>eps);return s;} 2．一元非線(xiàn)性方程求根 （1）牛頓迭代法 牛頓迭代法又稱(chēng)牛頓切線(xiàn)法：先任意設(shè)定一個(gè)與真實(shí)的根接近的值x0作為第一次近似根，由x0求出f(x0),過(guò)(x0，f(x0))點(diǎn)做f(x)的切線(xiàn)，交x軸于x1，把它作為第二次近似根，再由x1求出f(x1),過(guò)(x1，f(x1))點(diǎn)做f(x)的切線(xiàn)，交x軸于x2，……如此繼續(xù)下去，直到足夠接近（比如|x-x0|<1e-6時(shí)）真正的根x*為止。 而f '(x0)=f(x0)/(x1-x0)所以 x1= x0-f(x0)/ f '(x0) 例如，用牛頓迭代法求下列方程在1.5附近的根：2x3-4x2+3x-6=0。#include “math.h” main(){ float x,x0,f,f1;x=1.5;do{ x0=x; f=2*x0*x0*x0-4*x0*x0+3*x0-6; f1=6*x0*x0-8*x0+3; x=x0-f/f1;}while(fabs(x-x0)>=1e-5);printf(“%fn”,x);} （2）二分法 算法要領(lǐng)是：先指定一個(gè)區(qū)間[x1, x2]，如果函數(shù)f(x)在此區(qū)間是單調(diào)變化的，則可以根據(jù)f(x1)和 f(x2)是否同號(hào)來(lái)確定方程f(x)=0在區(qū)間[x1, x2]內(nèi)是否有一個(gè)實(shí)根；如果f(x1)和 f(x2)同號(hào)，則f(x)在區(qū)間[x1, x2]內(nèi)無(wú)實(shí)根，要重新改變x1和x2的值。當(dāng)確定f(x)在區(qū)間[x1, x2]內(nèi)有一個(gè)實(shí)根后，可采取二分法將[x1, x2]一分為二，再判斷在哪一個(gè)小區(qū)間中有實(shí)根。如此不斷進(jìn)行下去，直到小區(qū)間足夠小為止。 具體算法如下： （1）輸入x1和x2的值。（2）求f(x1)和f(x2)。 （3）如果f(x1)和f(x2)同號(hào)說(shuō)明在[x1, x2] 內(nèi)無(wú)實(shí)根，返回步驟（1），重新輸入x1和x2的值；若f(x1)和f(x2)不同號(hào)，則在區(qū)間[x1, x2]內(nèi)必有一個(gè)實(shí)根，執(zhí)行步驟（4）。（4）求x1和x2的中點(diǎn)：x0=（x1+ x2）/2。（5）求f(x0)。 （6）判斷f(x0)與f(x1)是否同號(hào)。 ①如果同號(hào)，則應(yīng)在[x0, x2]中尋找根，此時(shí)x1已不起作用，用x0代替x1，用f(x0)代替f(x1)。 ②如果不同號(hào)，則應(yīng)在[x1, x0]中尋找根，此時(shí)x2已不起作用，用x0代替x2，用f(x0)代替f(x2)。 （7）判斷f(x0)的絕對(duì)值是否小于某一指定的值（例如10-5）。若不小于10-5，則返回步驟（4）重復(fù)執(zhí)行步驟（4）、（5）、（6）；否則執(zhí)行步驟（8）。（8）輸出x0的值，它就是所求出的近似根。 例如，用二分法求方程2x3-4x2+3x-6=0在(-10，10)之間的根。#include “math.h” main(){ float x1,x2,x0,fx1,fx2,fx0;do { printf(“Enter x1&x2”); scanf(“%f%f”,&x1,&x2); fx1=2*x1*x1*x1-4*x1*x1+3*x1-6; fx2=2*x2*x2*x2-4*x2*x2+3*x2-6; }while(fx1*fx2>0);do { x0=(x1+x2)/2; fx0=2*x0*x0*x0-4*x0*x0+3*x0-6; if((fx0*fx1)<0){ x2=x0;fx2=fx0;} else {x1=x0;fx1=fx0;} }while(fabs(fx0)>1e-5);printf(“%fn”,x0);} 3．梯形法計(jì)算定積分 定積分 的幾何意義是求曲線(xiàn)y=f(x)、x=a、x=b以及x軸所圍成的面積。 可以近似地把面積視為若干小的梯形面積之和。例如，把區(qū)間[a, b]分成n個(gè)長(zhǎng)度相等的小區(qū)間，每個(gè)小區(qū)間的長(zhǎng)度為h=(b-a)/n，第i個(gè)小梯形的面積為[f(a+(i-1)·h)+f(a+i·h)]·h/2，將n個(gè)小梯形面積加起來(lái)就得到定積分的近似值： 根據(jù)以上分析，給出“梯形法”求定積分的N-S結(jié)構(gòu)圖： 輸入?yún)^(qū)間端點(diǎn)：a，b 輸入等分?jǐn)?shù)n h=(b-a)/2, s=0 i從1到n si=(f(a+(i-1)*h)+f(a+i*h))*h/2 s=s+si 輸出s 11 上述程序的幾何意義比較明顯，容易理解。但是其中存在重復(fù)計(jì)算，每次循環(huán)都要計(jì)算小梯形的上、下底。其實(shí)，前一個(gè)小梯形的下底就是后一個(gè)小梯形的上底，完全不必重復(fù)計(jì)算。為此做出如下改進(jìn)： 矩形法求定積分則更簡(jiǎn)單，就是將等分出來(lái)的圖形當(dāng)作矩形，而不是梯形。例如：求定積分的值。等分?jǐn)?shù)n=1000。 #include “math.h” float DJF(float a,float b){ float t,h;int n,i;float HSZ(float x);n=1000;h=fabs(a-b)/n;t=(HSZ(a)+HSZ(b))/2;for(i=1;i<=n-1;i++)t=t+HSZ(a+i*h);t=t*h;return(t);} float HSZ(float x){ return(x*x+3*x+2);} main(){ float y;y=DJF(0,4); printf(“%fn”,y);} 四、其他常見(jiàn)算法 1．迭代法 其基本思想是把一個(gè)復(fù)雜的計(jì)算過(guò)程轉(zhuǎn)化為簡(jiǎn)單過(guò)程的多次重復(fù)。每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。 例如，猴子吃桃問(wèn)題。猴子第一天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過(guò)癮，又多吃了一個(gè)。第二天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上想再吃時(shí)，就只剩一個(gè)桃子了。編程求第一天共摘多少桃子。 main(){ int day,peach;peach=1;for(day=9;day>=1;day--)peach=(peach+1)*2;printf(“The first day:%dn”,peach);} 又如，用迭代法求x= 的根。 求平方根的迭代公式是：xn+1=0.5×(xn+a/ xn)[算法]（1）設(shè)定一個(gè)初值x0。 （2）用上述公式求出下一個(gè)值x1。 （3）再將x1代入上述公式，求出下一個(gè)值x2。 （4）如此繼續(xù)下去，直到前后兩次求出的x值（xn+1和xn）滿(mǎn)足以下關(guān)系： | xn+1-xn|<10-5 #include “math.h” main(){ float a,x0,x1;scanf(“%f”,&a);x0=a/2;x1=(x0+a/x0)/2;do{ x0=x1; x1=(x0+a/x0)/2; }while(fabs(x0-x1)>=1e-5); printf(“%fn”,x1);} 2．進(jìn)制轉(zhuǎn)換 （1）十進(jìn)制數(shù)轉(zhuǎn)換為其他進(jìn)制數(shù) 一個(gè)十進(jìn)制正整數(shù)m轉(zhuǎn)換成r進(jìn)制數(shù)的思路是，將m不斷除以r取余數(shù)，直到商為0時(shí)止，以反序輸出余數(shù)序列即得到結(jié)果。 注意，轉(zhuǎn)換得到的不是數(shù)值，而是數(shù)字字符串或數(shù)字串。 例如，任意讀入一個(gè)十進(jìn)制正整數(shù)，將其轉(zhuǎn)換成二至十六任意進(jìn)制的字符串。void tran(int m,int r,char str[],int *n){ char sb[]=“0123456789ABCDEF”;int i=0,g;do{ g=m%r; str[i]=sb[g]; m=m/r; i++; }while(m!=0);*n=i;} main(){ int x,r0;/*r0為進(jìn)制基數(shù)*/ int i,n;/*n中存放生成序列的元素個(gè)數(shù)*/ char a[50]; scanf(“%d%d”,&x,&r0);if(x>0&&r0>=2&&r0<=16){ tran(x,r0,a,&n);for(i=n-1;i>=0;i--)printf(“%c”,a[i]); printf(“n”);} else exit(0);}（2）其他進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù) 其他進(jìn)制整數(shù)轉(zhuǎn)換為十進(jìn)制整數(shù)的要領(lǐng)是：“按權(quán)展開(kāi)”，例如，有二進(jìn)制數(shù)101011，則其十進(jìn)制形式為1×25+0×24+1×23+0×22+1×21+1×20=43。若r進(jìn)制數(shù)an……a2a1（n位數(shù)）轉(zhuǎn)換成十進(jìn)制數(shù)，方法是an×r n-1+……a2×r1+a1×r0。 注意：其他進(jìn)制數(shù)只能以字符串形式輸入。 例 1、任意讀入一個(gè)二至十六進(jìn)制數(shù)（字符串），轉(zhuǎn)換成十進(jìn)制數(shù)后輸出。 #include “string.h” #include “ctype.h” main(){ char x[20];int r,d;gets(x);/*輸入一個(gè)r進(jìn)制整數(shù)序列*/ scanf(“%d”,&r);/*輸入待處理的進(jìn)制基數(shù)2-16*/ d=Tran(x,r);printf(“%s=%dn”,x,d);} int Tran(char *p,int r){ int d,i,cr;char fh,c;d=0;fh=*p;if(fh=='-')p++;for(i=0;i if(toupper(c)>='A')cr=toupper(c)-'A'+10; else cr=c-'0'; d=d*r+cr;} if(fh=='-')d=-d;return(d);} 3．矩陣轉(zhuǎn)置 矩陣轉(zhuǎn)置的算法要領(lǐng)是：將一個(gè)m行n列矩陣（即m×n矩陣）的每一行轉(zhuǎn)置成另一個(gè)n×m矩陣的相應(yīng)列。 例 1、將以下2×3矩陣轉(zhuǎn)置后輸出。即將 1 2 3 轉(zhuǎn)置成 1 4 6 main(){ int a[2][3],b[3][2],i,j,k=1;for(i=0;i<2;i++) for(j=0;j<3;j++) a[i][j]=k++;/*以下將a的每一行轉(zhuǎn)存到b的每一列*/ for(i=0;i<2;i++)for(j=0;j<3;j++) b[j][i]=a[i][j];for(i=0;i<3;i++)/*輸出矩陣b*/ { for(j=0;j<2;j++) printf(“%3d”,b[i][j]); printf(“n”);} } 4．字符處理 （1）字符統(tǒng)計(jì)：對(duì)字符串中各種字符出現(xiàn)的次數(shù)的統(tǒng)計(jì)。典型例題：任意讀入一個(gè)只含小寫(xiě)字母的字符串，統(tǒng)計(jì)其中每個(gè)字母的個(gè)數(shù)。#include “stdio.h ” main(){ char a[100];int n[26]={0};int i;/*定義26個(gè)計(jì)數(shù)器并置初值0*/ gets(a);for(i=0;a[i]!= '
主站蜘蛛池模板：
精品九九人人做人人爱|
一本久久伊人热热精品中文|
大伊香蕉av最新播放|
97精品人人妻人人|
巨爆乳无码视频在线观看|
国产成人无码a区在线观看视频app|
欧美日韩不卡视频合集|
亚洲国产精品无码第一区二区三区|
波多野结衣办公室双飞|
国产亚洲精品超碰热|
久久人妻国产精品31|
中文字幕无码一区二区免费|
亚洲偷自拍国综合|
亚洲欧美精品伊人久久|
97se亚洲精品一区二区|
亚洲综合久久成人a片|
久久久久久无码精品人妻a片软件|
99久久久成人国产精品免费|
色一情一乱一伦一区二区三区小说|
欲色天天网综合久久|
亚洲熟女www一区二区三区|
影音先锋在线亚洲网站|
人人综合亚洲无线码另类|
亚洲精品国产suv一区|
亚洲欧美综合精品久久成人网|
青草草97久热精品视频|
俺来也俺去啦久久综合网|
一本大道大臿蕉无码视频|
五月丁香六月激情综合在线视频|
国产色婷婷亚洲99精品|
国产手机在线无码播放视频|
亚洲欧美综合精品成人网|
国产精品www夜色视频|
9999国产精品欧美久久久久久|
亚洲精品久久66国产高清|
日韩精品无码中文字幕一区二区|
亚洲精品一线二线三线无人区|
无码人妻精品一区二区三区99不卡|
国产成年无码久久久免费|
无码人妻丰满熟妇啪啪网不卡|
天天躁日日躁狠狠躁性色avq|
第二篇：RSA加密解密算法c語(yǔ)言程序
第三篇：c語(yǔ)言課程設(shè)計(jì)-文件加密解密(含源代碼)
第四篇：RSA算法實(shí)驗(yàn)報(bào)告
第五篇：C語(yǔ)言常用算法歸納