发信人: ytam()
整理人: girlrong(1999-11-13 15:03:31), 站内信件
|
【 在 tsingxiao (脑袋) 的大作中提到: 】
: 关于质数的选取........
:
: 上一篇提到为了使因数分解发生困难, 所选择的质数要愈大愈好,
: 但这也意味著, 质数的选取也同样的困难......
: .......
the following is a RSA encryption program.
/*
(1) This program can effectively produce big prime reaching 90 decima
l digits.
(2) Completely implement RSA algorithm
(3) Parameters: ( Set according to your requirements )
MLENGTH :LENGTH OF PRIME p,q
SKLENGTH :length of secret key
TEXTLENGTH :length of plain text and ciper text
by YTAM (i4q4ever&1收皮！）
no right reserved
(Feb 3rd,1999)
*/
#include <mem.h>
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define DATALENGTH 350 /* length of the very long data */
#define MLENGTH 4 /* change this parameter */
#define TESTNUM 20
#define SKLENGTH 4
#define TEXTLENGTH 20
typedef signed char byteint[DATALENGTH];
typedef signed char mtype[MLENGTH];
mtype Model[TESTNUM];
byteint plaintext[20];
byteint cipertext[20];
byteint ONEVALUE,ZEROVALUE,TWOVALUE,EIGHTVALUE;
/* 0 contant and 1 constant */
void InitInt(void); /* initialize basic data */
void SetZero(byteint A); /* A=0 */
void IntCpy(byteint A,byteint B); /* A=B */
int IntValid(byteint validtemp); /* return the number of non zero d
igits */
int PrtInt(byteint A); /* output a very large num */
int IntCmp(byteint A,byteint B); /* compare two integer */
void Plus(byteint A,byteint B,byteint C); /* C=A+B */
void Substract(byteint SA,byteint SB,byteint SC); /* SC=SA-SB */
void Multiply(byteint A,byteint B,byteint C); /* C=A*B */
void SetMode(byteint A,byteint B,byteint C,byteint D); /* C=A%B,D=A/B
*/
void IntRandom(byteint RondomA,int num); /* generating a big random */
int Prime(byteint Pm); /* generating a prime to Pm */
void LoadInt(byteint A,mtype B);
int ComputingPK(byteint Rvalue,byteint SK,byteint PK);
int GetPlaintext(void);
void PackInt(byteint A,int B);
/*byteint PRIME1={7,7,1,5,3,7,7,2,5,1,1,9,9,4,8,0,2,7,9,9,2,1,6,4,2,4,
9,2,3,9};
byteint PRIME2={1,0,4,2,2,4,5,8,5,2,2,1,4,0,8,2,9,6,8,9,1,3,0,9,4,4,
6,0,2,1}; /* 30 bits */
byteint PRIME3={7,2,1,7,3,3,3,6,8,3,4,7,9,3,4,2,0,6,3,6,3,8,7,1,4,7,
9,0,3,9,2,9,6,6,5,3,4,9,8,7,2,0,6,0,8,9,0,1,3,3,0,1,3,6,2,2,2,3,7,0,5,
0,9,1,1,3,7,5,1,9,9,8,2,5,9,7,3,2,6,7,0,7,6,3,2,7,1,3,1,1};
byteint PRIME4={3,3,9,0,1,5,3,8,4,7,4,2,1,3,1,3,0,4,7,9,7,7,5,4,8,8,
9,6,5,2,3,0,8,7,8,7,6,3,3,5,9,1,3,3,6,6,0,1,9,7,1,4,6,8,2,7,5,5,8,0,3,
2,3,8,4,9,7,2,3,0,3,9,6,4,3,6,3,5,2,7,8,8,9,8,7,9,5,7,5,9}; /* 90 bits
*/
byteint PRIME5={9,8,0,0,5,2,5,8,1,9,8,1,3,8,5,9,1,1,1,0,7,5,8,0,8,7,
0,9,0,9,8,6,7,6,0,5,5,2,4,0,8,9,0,3,6,2,5,0,6,6,6,6,2,4,6,3,6,5,6,3,0,
2,9,0,5,9,7,0,2,5};
byteint PRIME6={7,5,6,4,4,1,9,2,9,9,7,4,7,9,8,7,8,2,8,3,0,4,5,5,1,9,
9,2,3,8,7,2,1,1,6,0,0,4,0,3,0,9,0,3,0,6,1,4,7,6,0,1,3,4,9,4,3,5,3,8,0,
9,4,7,6,9,0,0,3,8};*/
void Mdata(void)
{
register i,j;
int k=MLENGTH-2;
memset(Model,0,TESTNUM*MLENGTH);
for(i=0;i<TESTNUM;i++)
{
for(j=MLENGTH-1;j>=k;j--)
Model[i][j]=rand()%10;
k-=1;
}
}
void TransBi(byteint B,signed char flag[400])
{
byteint buf,result,temp;
register i,j;
memset(flag,0,400);
i=399;
IntCpy(buf,B);
while(IntCmp(buf,ZEROVALUE)==1)
{
SetMode(buf,TWOVALUE,temp,result);
flag[i]=temp[DATALENGTH-1];
IntCpy(buf,result);
i--;
}
flag[i]=-1;
}
int PowerMode(byteint A,byteint C,byteint D,signed char flag[400])
{
/* compute A^B mod C */
byteint buf,result,temp,P;
register i,j;
IntCpy(temp,A);
if (flag[399]==1)
IntCpy(result,A);
else
IntCpy(result,ONEVALUE);
i=398;
while(flag[i]!=-1)
{
Multiply(temp,temp,buf);
SetMode(buf,C,temp,P);
if (flag[i]!=0)
{
Multiply(temp,result,buf);
SetMode(buf,C,result,P);
}
i--;
}
IntCpy(buf,C);
IntCpy(D,result);
Substract(buf,ONEVALUE,temp);
if (IntCmp(result,ONEVALUE)==0) /* p mod n=1 */
return 1;
if (IntCmp(result,temp)==0) /* p mod n=-1 */
return 2;
return 0;
}
int Prime(byteint Pm)
{
int i,j,k,ok,cnt=0;
signed char flag[400];
byteint A,B,D,buf1,buf2,result;
int pass,pass_2;
while(1)
{
pass=0;pass_2=0;
cnt++;
IntRandom(B,MLENGTH); /* try b if prime */
printf("\n %3d try:",cnt);
PrtInt(B);
IntCpy(Pm,B);
Substract(B,ONEVALUE,buf1);
SetMode(buf1,TWOVALUE,buf2,B);
TransBi(B,flag);
ok=1;
for(i=0;i<TESTNUM;i++)
{
LoadInt(A,Model[i]);
k=PowerMode(A,Pm,D,flag);
if (k!=1&&k!=2)
break;
if (k==1)
printf("\n pass the %dth test---1",pass++);
if (k==2)
{
pass_2=1;
printf("\n pass the %dth test---2",pass++);
}
}
if (ok&&pass_2) /* at least there is one p-1 */
{
printf("\n\n prime found:");
PrtInt(Pm);
return 0;
}
printf(" failure!");
}
}
void InitInt(void)
{
SetZero(ONEVALUE);
ONEVALUE[DATALENGTH-1]=1;
SetZero(ZEROVALUE);
SetZero(TWOVALUE);SetZero(EIGHTVALUE);
TWOVALUE[DATALENGTH-1]=2;
EIGHTVALUE[DATALENGTH-1]=8;
randomize();
}
int GetIp(int num)
{
return (num/10);
}
int PrtInt(byteint A)
{
register i=0;
int n,m;
while(i<DATALENGTH&&A[i]==0) i++;
if (i<DATALENGTH) m=DATALENGTH-i;
n=0;
while(i<DATALENGTH)
{
printf("%1d",A[i++]);
n++;
if (n>65)
{
n=0;
printf("\n");
}
}
return m;
}
void Multiply(byteint A,byteint B,byteint C)
{
register i,j,w;
int X,Y,Z;
int Avalid=0,Bvalid=0; /* Avalue=validating bits of A */
while(A[Avalid]==0&&Avalid<DATALENGTH)
Avalid++;
while(B[Bvalid]==0&&Bvalid<DATALENGTH)
Bvalid++;
SetZero(C);
for(i=DATALENGTH-1;i>=Avalid;i--)
for(j=DATALENGTH-1;j>=Bvalid;j--)
{
X=A[i]*B[j];
Y=GetIp(X);
Z=X-10*Y;
w=i+j-(DATALENGTH-1);
C[w]=C[w]+Z;
C[w-1]=C[w-1]+GetIp(C[w])+Y;
C[w]=C[w]-GetIp(C[w])*10;
}
}
void SetZero(byteint A)
{
register i;
for(i=0;i<DATALENGTH;i++)
A[i]=0;
}
void IntCpy(byteint A,byteint B)
{
register i;
SetZero(A);
for(i=0;i<DATALENGTH;i++)
A[i]=B[i];
}
void Plus(byteint A,byteint B,byteint C)
{
register i,w;
int X,Y,Z,m,n,valid;
m=IntValid(A);
n=IntValid(B);
valid=(m>n)?m+1:n+1;
SetZero(C);
for(i=DATALENGTH-1;i>=DATALENGTH-valid;i--)
{
X=A[i]+B[i];
Y=GetIp(X);
Z=X-10*Y;
C[i]=C[i]+Z;
C[i-1]=C[i-1]+Y;
}
}
void Substract(byteint SA,byteint SB,byteint SC)
{
byteint buf;
register i,j,w;
int X,Y,Z;
IntCpy(buf,SA);
SetZero(SC);
for(i=DATALENGTH-1;i>=0;i--)
{
if (buf[i]<SB[i])
{
buf[i]=buf[i]+10;
if (buf[i-1]>0)
(buf[i-1])--;
else
{
j=i-1;
while(buf[j]==0)
buf[j--]=9;
buf[j]=buf[j]-1;
}
}
X=buf[i]-SB[i];
SC[i]=X;
}
}
int IntCmp(byteint A,byteint B)
{
register i;
i=0;
while((A[i]==B[i])&&(i<DATALENGTH)) i++;
if (i>=DATALENGTH) return 0;
else if (A[i]>B[i]) return 1;
else return -1;
}
int IntValid(byteint validtemp)
{
register i=0;
while(validtemp[i]==0&&i<DATALENGTH)
i++;
return DATALENGTH-i;
}
void SetMode(byteint A,byteint B,byteint C,byteint D)
{
register i,j,k;
int valid_1,valid_2,valid,sbits,cmpval;
byteint buf1,buf2;
SetZero(D);
IntCpy(C,A);
valid_2=IntValid(B);
while((cmpval=IntCmp(C,B))>0)
{
valid_1=IntValid(C);
valid=valid_1-valid_2;
if (valid>0)
{
i=DATALENGTH-valid_1;
j=DATALENGTH-valid_2;
sbits=0;
for(k=j;k<DATALENGTH;k++)
{
if (C[i]>B[j]) break;
if (C[i]<B[j]) {sbits=1;break;}
i++;j++;
}
valid=valid-sbits;
SetZero(buf1);
for(i=valid;i<DATALENGTH;i++)
{
j=i-valid;
buf1[j]=B[i];
}
}
else IntCpy(buf1,B);
D[DATALENGTH-1-valid]++;
Substract(C,buf1,buf2);
IntCpy(C,buf2);
}
if (cmpval==0)
{
SetZero(C);
D[DATALENGTH-1]++;
} /* reminder = 0 */
}
void IntRandom(byteint RandomA,int num)
{
int i,x;
SetZero(RandomA);
while(!(RandomA[DATALENGTH-1]%2))
RandomA[DATALENGTH-1]=rand()%10;
while(!RandomA[DATALENGTH-num])
RandomA[DATALENGTH-num]=rand()%10;
i=DATALENGTH-2;
while(i>=DATALENGTH-num+1)
RandomA[i--]=rand()%10;
/* for(i=DATALENGTH-1;i>=DATALENGTH-num;i--)
RandomA[i]=PRIME6[DATALENGTH-1-i];*/
}
void LoadInt(byteint A,mtype B)
{
register i,j;
SetZero(A);
i=DATALENGTH-1;
j=MLENGTH-1;
while(j>=0)
A[i--]=B[j--];
}
main(void)
{
byteint p,q,R,PK,SK,Rvalue,desti,buf1,buf2;
signed char flag[400];
int num,i,k;
Mdata();
InitInt();
printf("\n RSA Encryptosystem Procedure\n");
printf("\n 1.Randomly select two prime numbers.\n");
Prime(p);Prime(q);
Multiply(p,q,R);
Substract(p,ONEVALUE,buf1);
Substract(q,ONEVALUE,buf2);
Multiply(buf1,buf2,Rvalue);
ComputingPK(Rvalue,SK,PK);
printf(" Paramenters:\n");
printf(" p= ");PrtInt(p);
printf("\n q= ");PrtInt(q);
printf("\n R= ");PrtInt(R);
printf("\n S(R)= ");PrtInt(Rvalue);
printf("\n SK= ");PrtInt(SK);
printf("\n PK= ");PrtInt(PK);
printf("\n 2.Please input plain text (format 1243,0812):");
printf(" (All data must be less than ");PrtInt(R);
k=GetPlaintext();
printf("\n\n 3.Your plain text as following:\n");
for(i=0;i<k;i++)
{
printf(" ");PrtInt(plaintext[i]);
}
printf("\n\n 4. Ciper text as following:\n");
TransBi(PK,flag);
for(i=0;i<k;i++)
{
PowerMode(plaintext[i],R,desti,flag);
PrtInt(desti);
IntCpy(cipertext[i],desti);
printf(" ");
}
printf("\n\n 5.restored plaintext as following:\n");
printf(" ");
TransBi(SK,flag);
for(i=0;i<k;i++)
{
PowerMode(cipertext[i],R,desti,flag);
PrtInt(desti);
printf(" ");
}
return 0;
}
int ComputingPK(byteint Rvalue,byteint SK,byteint PK)
{
register i,j;
byteint PA,PB,PC,buf,temp,buf2;
SetZero(PK);
while(1)
{
IntRandom(SK,SKLENGTH);
printf(" Try SK: ");
PrtInt(SK);
IntCpy(PB,SK);IntCpy(PA,Rvalue);
while(1)
{
SetMode(PA,PB,PC,PK);
i=IntCmp(PC,ONEVALUE);
if (i==0) break;
i=IntCmp(PC,ZEROVALUE);
if (i==0)
{
i=-1;break;
}
IntCpy(PA,PB);IntCpy(PB,PC);
}
if (i==0) break;
}
IntCpy(temp,ONEVALUE);IntCpy(PA,Rvalue);IntCpy(PB,PK);
while(1)
{
Multiply(PA,temp,buf);
Plus(buf,ONEVALUE,buf);
SetMode(buf2,PB,buf,PK);
if (IntCmp(buf,ZEROVALUE)==0) break;
Plus(temp,ONEVALUE,buf);
IntCpy(temp,buf);
}
return 1;
}
void PackInt(byteint A,int B)
{
register i=DATALENGTH-1;
SetZero(A);
while(B>0)
{
A[i--]=B%10;
B=B/10;
}
}
int GetPlaintext(void)
{
int i,k,num;
char str[80],*p;
k=0;
printf("\n");
gets(str);
p=str;
while(*p!=NULL)
{
while(*p<'0'||*p>'9') p++;
i=DATALENGTH-1;
while(*p>='0'&&*p<='9')
{
plaintext[k][i]=*p-'0';
i--;
p++;
}
k++;
}
return k;
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.137.160]
|
|