求教RSA加密得问题,散尽所有分数

Question

#include<iostream.h>
#include"math.h"
#include"stdlib.h"
#include<iomanip.h>
const int num1=256;
const int num2=512;
const int num3=768;
const int num4=1280;
//------------------------------------------------------------------------------------check
struct rsaint{
int rsa[num1];
};struct rsaint_1{
int rsa[num1];
int rsa_temp;
};
struct rsaint_2{
int rsa[num2];
};
struct rsaint_3{
int rsa[num3];
};
struct rsaint_4{
int rsa[num4];
};
//-----------------------------------------------------------------------------------check
rsaint_1 operator+(rsaint a,rsaint b)
{rsaint_1 d;
int temp=0;
for(int i=0;i<num1;i++){
d.rsa[i]=a.rsa[i]+b.rsa[i]+temp;
temp=0;
if(d.rsa[i]>=10) 
{d.rsa[i]=d.rsa[i]-10;
temp++;}
}
d.rsa_temp=temp;
return d;
}
//------------------------------------------------------------------------------------check
rsaint initialization (rsaint a)
{   //srand(6);
for(int i=0;i<num1;i++)
a.rsa[i]=rand()%2;
return a;
}
rsaint_1 initialization (rsaint_1 a)
{   a.rsa_temp=0;
for(int i=0;i<num1;i++)
a.rsa[i]=0;
return a;
}
rsaint_2 initialization (rsaint_2 a)
{
for(int i=0;i<num2;i++)
a.rsa[i]=0;
return a;
}
rsaint_2 initialization2 (rsaint_2 a)
{
for(int i=0;i<num2;i++)
a.rsa[i]=0;
a.rsa[0]=1;
return a;
}
rsaint_3 initialization (rsaint_3 a)
{
for(int i=0;i<num3;i++)
a.rsa[i]=0;
return a;
}
rsaint_4 initialization (rsaint_4 a)
{
for(int i=0;i<num4;i++)
a.rsa[i]=0;
return a;
}
//-----------------------------------------------------------------------------------check
ostream & operator<<(ostream &os,rsaint_2 c)
{
for(int i=num2-1;i!=-1;i--)
os<<c.rsa[i];
return os;
}
//-----------------------------------------------------------------------------------check
ostream & operator<<(ostream &os,rsaint_4 c)
{
for(int i=num4-1;i!=-1;i--)
os<<c.rsa[i];
return os;
}
//-----------------------------------------------------------------------------------check
rsaint_2 operator*(rsaint a,rsaint b)
{rsaint_2 c;
c=initialization(c);
//关键头(乘法)
int h=0;
for(int i=0;i<num1;i++)
{for(int j=0;j<num1;j++)
c.rsa[j+h]=a.rsa[i]*b.rsa[j]+c.rsa[j+h];
h++;}
//关键末(乘法)
//关键(乘后的处理)
for(int k=0;k<num2;k++)
{
while(c.rsa[k]>=2)
{c.rsa[k]=c.rsa[k]-2;
c.rsa[k+1]++;
}
}
return c;}
//------------------------------------------------------------------------------------check
//rsaint与0或1的乘法
rsaint operator*(rsaint a,int x)
{
if(x==0) 
{
initialization(a);
for(int i=0;i<num1;i++)//调试后去掉
a.rsa[i]=0;//调试后去掉
a.rsa[0]=1;
}
return a;
}
//-----------------------------------------------------------------------------------check
//1024位的rsaint_2与512位的rsaint相乘得1536位的rsaint_3
rsaint_3 operator*(rsaint_2 temp,rsaint xb)
{
rsaint_3 c;
c=initialization(c);
int h=0;
for(int i=0;i<num1;i++)
{
for(int j=0;j<num2;j++)
c.rsa[j+h]=xb.rsa[i]*temp.rsa[j]+c.rsa[j+h];
h++;
}
for(int k=0;k<num3;k++)
{
while(c.rsa[k]>=2)
{
c.rsa[k]=c.rsa[k]-2;
c.rsa[k+1]++;
}
}
return c;
}
//--------------------------------------------------------------------------------check
//1536位的rsaint_3与1024位的rsaint_2相乘得2560位的rsaint_4
rsaint_4 operator*(rsaint_2 temp,rsaint_3 xb)
{
rsaint_4 c;
c=initialization(c);
int h=0;
for(int i=0;i<num3;i++)
{
for(int j=0;j<num2;j++)
c.rsa[j+h]=xb.rsa[i]*temp.rsa[j]+c.rsa[j+h];
h++;
}
for(int k=0;k<num4;k++)
{
while(c.rsa[k]>=2)
{
c.rsa[k]=c.rsa[k]-2;
c.rsa[k+1]++;
}
}//cout<<"2560c:"<<c<<endl;
return c;
}
//---------------------------------------------------------------------------------check2
//检查第一个1的位置
int check(rsaint_2 a)
{  
int i=num2-1;
while(a.rsa[i]==0&&i>=0)
i--; 
if(a.rsa[i]==-1) {cout<<"wrong1";exit(-1);}
return i;
}int check2(rsaint_4 a)
{//cout<<"检查第一个1的位置 "<<endl;
int i=num4-1;
while(a.rsa[i]==0&&i>=0)
i--;//cout<<i;
if(a.rsa[i]==-1) {cout<<"wrong2";exit(-1);}
return i;
}

Answer 1

//------------------------------------------------------------------------------------check2
//检查是否前（2560-1024+b前0的个数）位都为0//判断是否继续减
int check(rsaint_4 a,rsaint_2 n)
{
int i=check2(a),j=check(n);
if(i<j) return 0;
if(i>j) return 1;
if(i==j)
{   //cout<<"good"<<endl;
while(a.rsa[i]==n.rsa[j]&&i>=0)
{
i--;
j--;
}
if(a.rsa[i]>n.rsa[j]) {/*cout<<"正在模运算";*/return 1;}
else if(a.rsa[i]<n.rsa[j]) return 0;
{cout<<"答案为0";exit(-1);}
}

}//-----------------------------------------------------------------------------------------
//判断是否错位减
int check_minus(rsaint_4 a,rsaint_2 b)
{   
//cout<<"判断是否错位减"<<endl;
int i=check2(a);
int j=check(b);
while(a.rsa[i]==b.rsa[j])
{i--;j--;}
if(a.rsa[i]>b.rsa[i])
return 0;
else
return 1;
}
//-----------------------------------------------------------------------------------------
//不错位的减
rsaint_4 ready_minus(rsaint_4 a,rsaint_2 b)
{
// cout<<"不错位的减"<<endl;
rsaint_4 x=a;
int i=check2(x);cout<<i<<endl;
int j=check(b);cout<<j<<endl;
for(int u=j;u!=-1;u--)
{
x.rsa[i]=x.rsa[i]-b.rsa[u];
i--;
}cout<<x<<endl;
return x;
}
//------------------------------------------------------------------------------------------
//错位的减
rsaint_4 ready_minus2(rsaint_4 a,rsaint_2 b)
{
// cout<<"错位的减"<<endl;
rsaint_4 x=a;
int i=check2(x);
int j=check(b);
for(int u=j;u!=-1;u--)
{   
i--;
x.rsa[i]=x.rsa[i]-b.rsa[u];
}//cout<<x<<endl;
return x;
}
//------------------------------------------------------------------------------------------
//减后伺候
rsaint_4 after_minus(rsaint_4 a)
{   //cout<<"减后伺候"<<endl;
int find_wrong=num4-1;//check
while(a.rsa[find_wrong]==0&&find_wrong>=0)//check
find_wrong--;//check
if(a.rsa[find_wrong]!=1) {cout<<"death";exit(-1);}//check
    rsaint_4 x=a;
for(int j=0;j<num4-1;j++)
{
if(x.rsa[j]==-1)//j为-1所在
{   x.rsa[j]=0;
int u=0;
while(x.rsa[u+j]!=1)
{   
x.rsa[u+j]++;
u++;//----------------------------------------kaolv
}
x.rsa[u+j]=0;
//while(a.rsa[j]>=2) {cout<<"enter";a.rsa[j+1]++;a.rsa[j]=a.rsa[j]-2;}
}
}
return x;
}
//------------------------------------------------------------------------------------------
//最困难的MOD运算
rsaint_2 rsamod(rsaint_4 a,rsaint_2 b)
{   rsaint_4 x=a;
while(check(x,b)==1)//判断是否继续减
{   
if(check_minus(x,b)==1)
{x=ready_minus2(x,b);}
else if(check_minus(x,b)==0)
{x=ready_minus2(x,b);}
x=after_minus(x);
}
rsaint_2 aa;aa=initialization(aa);
for(int i=0;i<num2-1;i++)
aa.rsa[i]=x.rsa[i];
return aa;
}
//------------------------------------------------------------------------------------------
//最关键算法的实现。
//temp是initialization2()特别处理的rsaint_2
rsaint_2 rsapow(rsaint_2 n,rsaint b,rsaint x,rsaint_2 temp)
{   
for(int i=num1-1;i!=-1;i--)
{   //cout<<i<<"point left"<<endl;
temp=rsamod(temp*(temp*(x*b.rsa[i])),n);//x*b.rsa[i]要重新定义。rsamod(),temp*rsaint也要定义。
   // if(i<=10) cout<<temp<<endl;
}
return temp;
}//------------------------------------------------------------------------------------------
/*void main()
{
rsaint_2 a;rsaint b;
a=initialization(a);
b=initialization(b);

a.rsa[1]=1;
a.rsa[2]=1;a.rsa[4]=1;b.rsa[0]=1;b.rsa[1]=1;b.rsa[3]=1; //cout<<a*b<<endl;
    cout<<check((b*b)*(a*b),b*b);
}
*/
void main()
{cout<<"rsa算法按bit运算，请稍等....."<<endl;
cout<<"如例子P=5，Q=7，N=35，B=11，X=2 答案为18" <<endl;
cout<<"明文："<<endl;
rsaint p,q,x,b;
rsaint_2 n,temp,f;
p=initialization(p);
q=initialization(q);
x=initialization(x);
b=initialization(b);n=initialization(n);
f=initialization(f);
temp=initialization2(temp);p.rsa[0]=1;p.rsa[2]=1;//5
q.rsa[0]=1;q.rsa[2]=1;q.rsa[1]=1;//7
n=p*q;
cout<<n<<endl;
p.rsa[0]=0;
q.rsa[0]=0;
f=p*q;
x.rsa[1]=1;//2
b.rsa[0]=1;b.rsa[1]=1;b.rsa[3]=1;//11
//cout<<pow(512,20);
rsaint_2 k=rsapow(n,b,x,temp);//void after_minus(rsaint_3 a)为O（n2）复杂度
cout<<"密文"<<endl;
cout<<k<<endl;cout<<"type_cai";}