精华区 [关闭][返回]

当前位置:网易精华区>>讨论区精华>>编程开发>>C/C++>>算法集锦--------梦入玄机>>关于RSA算法的一些话(2)

主题:关于RSA算法的一些话(2)
发信人: 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]

[关闭][返回]