rsa.cpp

RSA机密算法,可以提供低位数密钥的加密,利用miral库实现

#include <cstdlib>
#include <iostream>

using namespace std;

unsigned long int *add=new unsigned long int[50];
unsigned long int *multi=new unsigned long int[50];
unsigned long int *multix=new unsigned long int[50];
unsigned long int *depart=new unsigned long int[50];
unsigned long int *multirN=new unsigned long int[50];

void INC(unsigned long int a[],unsigned long int k=1);
void DEC(unsigned long int a[]);
int CMP(unsigned long int a[],unsigned long int b[]);
void X(unsigned long int a[],unsigned long int k);
void SUB(unsigned long int a[],unsigned long int b[]);
void ADD(unsigned long int a[],unsigned long int b[]);
void rol(unsigned long int a[],unsigned long int count);
void XX(unsigned long int a[],unsigned long int b[]);
int depart2(unsigned long int a[]);
unsigned long int mi(unsigned long int a[]);
void DIV(unsigned long int a[],unsigned long int b[]);
void mol(unsigned long int a[],unsigned long int b[]);
void mimo(const unsigned long int x[],const unsigned long int r[],unsigned long int n[]);
void GetData(unsigned long int a[]);
unsigned long int *MOD_(unsigned long int u[],const unsigned long int n[]);
void DataPut(unsigned long int a[]);

int main()
{
  unsigned long int *p=new unsigned long int[50];
  unsigned long int *q=new unsigned long int[50];
  unsigned long int *e=new unsigned long int[50];
  unsigned long int *n=new unsigned long int[50];
  unsigned long int *fai=new unsigned long int[50];
  unsigned long int *date=new unsigned long int[50];
  unsigned long int *mdate=new unsigned long int[50];
  unsigned long int i;
  char s='\0';
  while(s!='q')
    {
    cout<<"十进制rsa加密实验"<<endl;
    cout<<"******************准备工作开始*************************"<<endl;
    cout<<"请输入p:"<<endl;
    GetData(p);
    cout<<"请输入q:"<<endl;
    GetData(q);
    cout<<"请输入e:"<<endl;
    GetData(e);
    cout<<"******************准备工作正在进行*************************"<<endl;
    XX(p,q);
    DataPut(multix);
    cout<<multix[0]<<endl;
    cout<<"n的值为："<<endl;
    for(i=multix[0];i>0;i--)n=multix;n[0]=multix[0];
    DataPut(n);
    DEC(p);DEC(q);
    XX(p,q);
    cout<<"fai的值为："<<endl;
    for(i=multix[0];i>0;i--) fai=multix;fai[0]=multix[0];
    DataPut(fai);
    unsigned long int *d=MOD_(e,fai);
    cout<<"d的值为："<<endl;
    DataPut(d);
    cout<<"******************准备工作完毕，开始加密*************************"<<endl;
    cout<<"请输入要加密的数据:"<<endl;
    GetData(date);
    mimo(date,e,n);
    cout<<"密文是:"<<endl;
    for(i=multirN[0];i>0;i--) mdate=multirN;mdate[0]=multirN[0];
    DataPut(mdate);
    cout<<"解密出来的原数据为:"<<endl;
    mimo(mdate,d,n);
    DataPut(multirN);
    cout<<"退出请按q,否则按任意键重做......"<<endl;
    cin>>s;
  } 
  return 1;
}

void INC(unsigned long int a[],unsigned long int k)
{
  unsigned long int i=1;
  a[1]=a[1]+k;
  if(a[1]<10000)return ;
  while(a==10000&&i<=a[0])
  {
    a=0;a[i+1]+=1;
    i++;
  } 
  if(a[a[0]]==0)a[0]+=1;
}

void DEC(unsigned long int a[])
{ 
  unsigned long int i=1;
  a[1]=a[1]-1;
  while(a==-1&&i<=a[0])
  {
    a=9999;
    a[i+1]-=1;i++;
  }  
  if(a[a[0]]==0)a[0]-=1;
}

int CMP(unsigned long int a[],unsigned long int b[])
{
  if(a[0]>b[0])
    return  1;
  if(a[0]<b[0])
    return -1;
  unsigned long int i=a[0];
  while(i<=a[0]&&i>=1)
  {
    if(a>b)
      return   1;
    if(a<b)
      return -1;
    i--;
  }
  return 0;
}

void SUB(unsigned long int a[],unsigned long int b[])
{
  if(CMP(a,b)==-1)return ;
  if(CMP(a,b)==0)
  {
    for(unsigned long int k=0;k<=a[0];k++) a[k]=0;
    return ;
  }
  unsigned long int j;
  for(unsigned long int i=1;i<=b[0];i++)
  {
    if(a>=b) a-=b;
    else
    {
      a=10000-b+a;
      j=i+1;a[j]-=1;
      while(a[j]==-1&&j<=a[0])
      {
         a[j]=9999;
         a[j+1]-=1;
         j++;  
      }    
    }      
  }
  while(a[a[0]]==0&&a[0]>0)  a[0]-=1;
}

void ADD(unsigned long int a[],unsigned long int b[])
{
  unsigned long int count=(a[0]>=b[0]?a[0]:b[0])+1;
  for(unsigned long int j=0;j<50;j++)  add[j]=0;
  unsigned long int r,i=0;
  unsigned long int carry=0;
  for(i=1;i<count;i++)
  {
    r=(i<=(a[0]<=b[0]?a[0]:b[0])?a+b:(a[0]>=b[0]?a:b))+carry;
    add=r%10000;
    carry=r/10000;
  }
  if(carry)
  {
    add[count]=carry;
    add[0]=count;
  }
  else
    add[0]=count-1;
}

void rol(unsigned long int a[],unsigned long int count)
{
  unsigned long int i=0;
  for( i=a[0];i>=1;i--)
    a[i+count]=a;
  for(i=1;i<=count;i++)
    a=0;
  a[0]+=count;
}

void X(unsigned long int a[],unsigned long int k)
{  
  unsigned long int i,r,carry=0;
  multi[0]=a[0];
  for(i=1;i<50;i++) multi=0;
  for(i=1;i<=a[0];i++)
  {
    r=a*k+carry;
    multi=r%10000;
    carry=r/10000;
  }
  if(carry)
  {
    multi[0]+=1;
    multi[multi[0]]=carry;
  }
}

void XX(unsigned long int a[],unsigned long int b[])
{
  unsigned long int i=0;
  for( i=0;i<50;i++)
    multix=0;

  for(i=1;i<=b[0];i++)
  {
    X(a,b);
    rol(multi,i-1);
    ADD(multix,multi);
    for(unsigned long int j=0;j<=add[0];j++)
      multix[j]=add[j];
  }
}

int depart2(unsigned long int a[])
{  
  if(a[0]==1&&a[1]<=1)
    return 0;
  if(a[1]%2)
    return -1;
  unsigned long int count;
  if(a[a[0]]==1)
    count=a[0]-1;
  else
    count=a[0];
  for(unsigned long int i=a[0];i>=1;i--)
  {
    a[i-1]+=(a&0x1)*10000;
    a/=2;
  }
  a[0]=count;
  return 1;
}

unsigned long int mi(unsigned long int a[])
{
  unsigned long int k=0;
  while(depart2(a)==1)
    k++;
  return k;
}

void DIV(unsigned long int a[],unsigned long int b[])
{

  if(b[0]==0)return ;
  unsigned long int flag=a[0];
  for(unsigned long int j=0;j<50;j++)
    depart[0]=0;
  if(CMP(a,b)==-1) return ;
  unsigned long int i,r=a[0]-b[0]+1,sum,count=b[0],k;
  unsigned long int *p=new unsigned long int[b[0]+2];
  for(i=1;i<=b[0];i++)
    p=a[a[0]-count+i];
  p[0]=count;
  p[count+1]=0;
  depart[0]=r;
  while(r>=1)
  {
    k=0;
    if(CMP(p,b)!=-1)
    {
      if(p[0]>b[0])
        sum=p[p[0]-1]+(p[p[0]]*10000);
      else
        sum=p[p[0]];
      k=sum/b[b[0]];
      X(b,k);
      while(CMP(p,multi)==-1)
      {
        k-=1;SUB(multi,b);
      }
      SUB(p,multi);
    }
    depart[r]=k;
    if(r>1)
    {
      rol(p,1);p[1]=a[r-1];
    }
    r--; 
  }
  if(depart[depart[0]]==0)
    depart[0]-=1;
  for(i=0;i<=p[0];i++)
    a=p;
  for(i=p[0]+1;i<=flag;i++)
    a=0;
  delete []p; 
}

void mol(unsigned long int a[],unsigned long int b[])
{ 
  if(b[0]==0)return ;
  unsigned long int flag=a[0];
  for(unsigned long int j=0;j<50;j++)
    depart[0]=0;
  if(CMP(a,b)==-1)
    return ;
  unsigned long int i,r=a[0]-b[0]+1,sum,count=b[0],k;
  unsigned long int *p=new unsigned long int[b[0]+2];
  for(i=1;i<=b[0];i++)
    p=a[a[0]-count+i];
  p[0]=count;
  p[count+1]=0;
  while(r>=1)
  {
    if(CMP(p,b)!=-1)
    {
      if(p[0]>b[0])
        sum=p[p[0]-1]+(p[p[0]]*10000);
      else
        sum=p[p[0]]; 
      k=sum/b[b[0]]; 
      X(b,k);
      while(CMP(p,multi)==-1)
        SUB(multi,b);
      SUB(p,multi);
    }
    if(r>1)
    {
      rol(p,1);p[1]=a[r-1];
    }
    r--; 
  }
  for(i=0;i<=p[0];i++)
    a=p;
  for(i=p[0]+1;i<=flag;i++)
    a=0;
  delete []p; 
}

void mimo(const unsigned long int x[],const unsigned long int r[],unsigned long int n[])
{
  unsigned long int *a=new unsigned long int[n[0]+1];
  unsigned long int *b=new unsigned long int[n[0]+1];
  unsigned long int i=0; 
  for( i=0;i<=n[0];i++)
  {
    if(i<=x[0])
      a=x;
    else
      a=0;
  }
  for( i=0;i<=n[0];i++)
  {
    if(i<=r[0])
      b=r;
    else
      b=0;
  }
  for(i=2;i<50;i++)multirN=0;
    multirN[0]=multirN[1]=1;
  while(b[0]!=0)
  {  
    if(depart2(b)==1)
    {
      XX(a,a);
      mol(multix,n);
      for( i=0;i<=multix[0];i++)
        a=multix;   
    }  
    else
    {
      DEC(b);
      XX(multirN,a);
      mol(multix,n);
      for( i=0;i<=multix[0];i++)
      multirN=multix;
    } 
  } 
}

void GetData(unsigned long int a[])
{
  unsigned long int j=0,i,m,n,d[3];
  char *c=new char[50];
  for(i=0;i<50;i++) 
  {
    c='\0';
    a=0;
  }
  cin>>c;
  while(c[j]!='\0')
  {       
    n=j/4+1; 
    a[0]=n;
    if(j%4==0)
    {
      for(i=n;i>1;i--) a=a[i-1];
      a[1]=c[j]-'0';
    }
    else
    {
      m=c[j]-'0';
      a[1]=a[1]*10+m;
    }
    j++;
  }
  if(a[1]<10) d[1]=1000;
  else if(a[1]>=10&&a[1]<100) d[1]=100;
  else if(a[1]>=100&&a[1]<1000) d[1]=10;
  else d[1]=1;
  a[1]*=d[1];
  d[0]=1;
  DIV(a,d);   
  for(i=0;i<=depart[0];i++) a=depart;
  return ;
} 

void DataPut(unsigned long int a[])
{ 
  cout<<a[a[0]]<<' ';
  for(int i=a[0]-1;i>0;i--)
  {
     if(a<10) cout<<"000"<<a[1]<<' ';
     else if(a>=10&&a<100)  cout<<"00"<<a[1]<<' ';
     else if(a>=100&&a<1000)  cout<<"0"<<a[1]<<' ';
     else cout<<a<<' ';
  }
  cout<<endl;
  return ;     
}   

unsigned long int *MOD_(unsigned long int u[],const unsigned long int n[])
{
  unsigned long int *pp=new unsigned long int[n[0]+1];
  for(unsigned long int k=0;k<=n[0];k++)
    pp[k]=n[k];
  unsigned long int *b1=new unsigned long int[n[0]+1];
  unsigned long int *b2=new unsigned long int[n[0]+1];
  unsigned long int *n1=new unsigned long int[n[0]+1];
  unsigned long int *n2=new unsigned long int[n[0]+1];
  unsigned long int   *t=new unsigned long int[n[0]+1];
  unsigned long int i;
  bool flag=true;
  for(i=0;i<=u[0];i++)
    n2=u;
  for(i=0;i<=n[0];i++)
    n1=n; 
  for(i=0;i<=n[0];i++)
    b1=0;b2=0;
  b2[0]=b2[1]=1;
  unsigned long int BREAK=2;
  unsigned long int count=0;
  while(flag)
  {
    count++;    
    DIV(n1,n2);
    BREAK=n1[0]*n1[1]; 
    for(i=0;i<=n1[0];i++)
      t=n1; 
    for(i=0;i<=n2[0];i++)
      n1=n2; 
    for(i=0;i<=t[0];i++)
      n2=t; 
    XX(depart,b2);
    ADD(multix,b1);  
    for(i=0;i<=b2[0];i++)
      b1=b2; 
    for(i=0;i<=add[0];i++)
      b2=add;  
    if((n2[0]==1&&n2[1]==1))
    {
      flag=false; 
      if(count%2==1)
        SUB(pp,b2);
      else
        for(i=0;i<=b2[0];i++)
          pp=b2;
     }
   } 
   if(BREAK==0)
     cout<<"对不起，你选择的两个数不互质"<<endl;
   return pp;
}