secretsharedlg.cpp

Shamir秘密分享与恢复算法的VC++程序

		if((memcmp(Model[i],mZEROVALUE,len))==0)  
			i--;
		k--;                          //保证所产生的数不为0
		if (k<0) k=len-2;
		
	
	}
	
}

/*---------------------------------------------------------------------------
功能：该函数用来将十进制的大整数转换成二进制的数
入口参数：需转换的大数B，二进制结果flag[300]
返回值：无
----------------------------------------------------------------------------*/
void TransBi(byteint B,signed char flag[300])
{
	byteint buf;
	byteint result;
	byteint temp;
	register i;
	SetZero(buf);  SetZero(result);  SetZero(temp);
	memset(flag,0,300);                     //将flag数组清零

	i=299;
	IntCpy(buf,B);                          //将B拷贝到buf中
	while(IntCmp(buf,ZEROVALUE)==1)         //如果buf内容为0
	{
		Division(buf,TWOVALUE,temp,result);  //将buf进行大数的模2运算，商在result中，余数temp
		flag[i]=temp[DATALENGTH-1];         
		IntCpy(buf,result);                 //对商继续进行模2运算
		i--;
	}
	flag[i]=-1;                             //设置一个标志位，表明二进制数的开始
}

/*---------------------------------------------------------------------------
功能：该函数用来进行模幂算法，A为底数，模为c，二进制的指数B存放在数组flag中
入口参数：底数A，模C，结果D，二进制质数flag[300]
返回值：A^B=1(mod C),返回1；A^B=p-1(mod C),返回2；否则返回0
----------------------------------------------------------------------------*/
int PowerMode(byteint A,byteint C,byteint D,signed char flag[300])
{
	byteint buf;
	byteint result;
	byteint temp,P;
	register i;
	SetZero(D);   SetZero(buf); SetZero(result); SetZero(temp); SetZero(P);  //将D清零

	IntCpy(temp,A);                       //将A的值拷贝到temp中
	if(flag[299]==1)                      //最低位为1，拷贝本身，flag[i]只有1或者0两种情况
		IntCpy(result,A);
	else								  //最低位为0，则幂为1
		IntCpy(result,ONEVALUE);
	i=298;
	while(flag[i]!=-1)                    //判断是否已经到达指数尽头
	{
	    //Sqrt(temp,buf);          //temp*temp->buf 
		//SetZero(temp);
		//temp[168]=4;
	//	temp[169]=2;
		Power(temp,buf,2);
		Division(buf,C,temp,P);            //buf%c余数->temp,商->p
		if(flag[i]!=0)                    //如果该位不是0，则将其和前一步低一位的结果进行乘法运算
		{                                 //否则，将其作为该位的模，在高一位的运算中，只要进行一次
			Multiply(temp,result,buf);    //平方运算，就可以得到高一位的模
			Division(buf,C,result,P);
		}
		i--;
	}                                     //result中存放的是最终结果
	IntCpy(buf,C);
	IntCpy(D,result);
	Substract(buf,ONEVALUE,temp);
	if(IntCmp(result,ONEVALUE)==0)        //p mod n=1，判断是否有A^B=1(mod C)
		return 1;
	if(IntCmp(result,temp)==0)            //p mod n=-1[p-1=-1(mod p)]，判断是否有A^B=p-1(mod C)
		return 2;
	return 0;
}

/*---------------------------------------------------------------------------
功能：随机地产生一个大数奇数，长度为num，最高位不是0，存放在RandomA中
入口参数：大数A，长度num
返回值：无
----------------------------------------------------------------------------*/
void IntRandom(byteint RandomA,int num)
{
	int i;
	SetZero(RandomA);                     //将RandomA清零
	srand( (unsigned)time( NULL ) );      //时间种子初始化
	
	while(!(RandomA[DATALENGTH-1]%2))     //判断条件保证RandomA的最后一位数是奇数
		RandomA[DATALENGTH-1]=rand()%10;  //如果最后一位是偶数，则从新产生最后一位
    while(!(RandomA[DATALENGTH-num]))     //判断条件保证RandomA最高位不是0
		RandomA[DATALENGTH-num]=rand()%10;//如果最高位是0,则从新产生最高位

	i=DATALENGTH-2;
	while(i>=DATALENGTH-num+1)            //循环产生从次低位开始到次高位的所有位上的数
		RandomA[i--]=rand()%10;
}
/*---------------------------------------------------------------------------
功能：得到一个大数的非零位数
入口参数：大数validtemp
返回值：大数中非零的位数
----------------------------------------------------------------------------*/
int IntValid(byteint validtemp)
{
	register i=0;
	while(validtemp[i]==0 && i<DATALENGTH)
		i++;
	return DATALENGTH-i;
}
/*---------------------------------------------------------------------------
功能：将一个大数A转换为相应的字符串形式
入口参数：大数A
返回值：相对应的字符串
----------------------------------------------------------------------------*/
CString PrtInt(byteint A)
{
	register i=0;	
	while(i<DATALENGTH && A[i]==0)          //跳过大数开始的空白0
		i++;							//注意到这里的i已经是数组中第一个非零元素的对应位置，
	CString str="";							//因此下面的循环就是从数组中
											//存放的数的最高位开始输出。
	while(i<DATALENGTH)
	{
		str += (A[i++]+'0');
	}
	return str;
}
/*---------------------------------------------------------------------------
功能：该函数用来从产生若干个不超过指定位数（十进制）的随机数，存放在tmp中
入口参数：二维大数tmp,个数n，最大位数len
返回值：无
----------------------------------------------------------------------------*/
void RandomData(byteint2 tmp,int n,int len)
{
	register i,j,q;   
//	byteint q;
	CString Q;
	int k=len-2;
	memset(Model,0,n*len);  //这个函数在这里用来将整个数组清零，进行初始化
	srand( (unsigned)time( NULL ) );  //进行随机函数的初始化
	for(i=0;i<n;i++)            
	{
		for(j=len-1;j>=k;j--)
		{
			Model[i][j]=rand()%10;   
			
		}
		if((memcmp(Model[i],mZEROVALUE,len))==0)  
			i--;
		k--;                          //保证所产生的数不为0
		if (k<0) k=len-2;


		 SetZero(tmp[i]);

		for(j=len-1;j>=0;j--)	
    	tmp[i][DATALENGTH-j-1]=int(Model[i][j]);

		//if(q[DATALENGTH-j-1]>=p[DATALENGTH-j-1])
         // q[DATALENGTH-j-1]=p[DATALENGTH-j-1]-1;
		 for(q=0;q<i;q++)                          //保证随机数不同
		  if(IntCmp(tmp[i],tmp[q])==0 )
				goto E;
		Q=PrtInt(tmp[i]);
		if(strcmp(Q,R)<0)
		{
		  //cout<<Q<<endl;
	    continue;}
		else
E:		{i--;
		  continue;}
		 
	 }

	
}

/*---------------------------------------------------------------------------
/*---------------------------------------------------------------------------
功能：大数A^n，结果放入大数C中
入口参数：大数A，结果C，次方n
返回值：无
----------------------------------------------------------------------------*/
void Power(byteint A,byteint C,int n)
{
	int X,Y,Z;	
	int i, j,r;
	int k = IntValid(A);
	byteint T,B,buf1;	
	IntCpy(C,A);     //将C初始化为A
	int s = IntValid(C);
	//SetZero(C);
	SetZero(T);
	//SetZero(B);
	SetZero(buf1);
	
  for(r=0;r<n-1;r++)	
  {
    for(i=0;i<k;i++)
	{
	    j=0;
		SetZero(B);
		X = C[DATALENGTH-1-j]*A[DATALENGTH-1-i]; //乘数A的每一位分别与被乘数C的个位相乘
	   	Y = X/10;
		Z = X-Y*10;
		B[DATALENGTH-1-i-j] = Z;
        B[DATALENGTH-2-i-j] = Y;                 //进位
	   for (j=1;j<s;j++)                         //乘数A的每一位分别与被乘数C的其它位相乘
	  {
        X = C[DATALENGTH-1-j]*A[DATALENGTH-1-i];
	   	Y = X/10;
		Z = X-Y*10;
		B[DATALENGTH-1-i-j] = Z+B[DATALENGTH-1-i-j];//加进位
        B[DATALENGTH-2-i-j] = Y;
		//k +=2;
	  }
      Plus(B,T,buf1);
      IntCpy(T,buf1);
	  
	}
	s = IntValid(buf1);
  IntCpy(C,buf1);                                   //赋给C作为结果，如果没乘完就作为新的被乘数
  SetZero(buf1);
  SetZero(T);
  }
  if(n==0)                                          //如果是0次方，就使C为1
   IntCpy(C,ONEVALUE);
 
}

/*----------------------------------------------------------------------------*/

void CSecretShareDlg::OnConfirm() 
{
	// TODO: Add your control notification handler code here
	CWnd* pwnd=(CWnd*)GetDlgItem(IDC_N);
	CString n_str;
	
	pwnd->GetWindowText(n_str);
    pwnd=(CWnd*)GetDlgItem(IDC_K);
	CString k_str;
	pwnd->GetWindowText(k_str);
	pwnd=(CWnd*)GetDlgItem(IDC_KEY);
	CString key_str;
	pwnd->GetWindowText(key_str);
    n = atoi(n_str.GetBuffer(0));
	th = atoi(k_str.GetBuffer(0));
    for(int i=0;i<key_str.GetLength();i++){
		maink[i]=key_str.GetAt(i);
	}
	l=key_str.GetLength();
    SetZero(key);
    for(i=0;i<l;i++)
    	key[DATALENGTH-l+i]=maink[i]-48;


	for(i=0;i<50;i++)
	  r[i]=0;
   // DATANUM=n-1;
	
  

	SetZero(p);
	//Mdata(l+5); 
	Mdata(l+10);         //生成比较数表
  // Mdata2(factor,TESTNUM,l+5);
//	printf("%d",i);
 	SetZero(ZEROVALUE);						//对大数变量ZEROVALUE清零
	memset(mZEROVALUE,0,l);
	//SetZero(ONEVALUE);                      //对大数变量ONEVALUE进行清零
   //ONEVALUE[DATALENGTH-1]=1;				//ONEVALUE的最后一位为1
	SetZero(TWOVALUE);						//将TOWVALUE进行清零
    TWOVALUE[DATALENGTH-1]=2;				//TOWVALUE的最后一位为2
	


 Prime(p,l+10);
 R=PrtInt(p);
 //edit1.
 //edit1.setWindowText(R);
 //edit1.setText(R);
 //cout<<R<<endl<<endl;
 //edit1.
 str_edit=R;
 UpdateData(false);
 RandomData(factor,th-1,3);

//cout<<endl;
 RandomData(X,n,2); 
 CListBox* pwnd1=(CListBox*)GetDlgItem(IDC_LIST);

 
 /*for(i=0;i<n;i++)
{
  Q=PrtInt(X[i]);
  
  pwnd1->AddString((LPCTSTR)Q);
  cout<<Q<<endl;
}*/
 /*for(i=1;i<=n;i++)
 {
	SetZero(X[i-1]);
	X[i-1][DATALENGTH-1]=i%10;
	X[i-1][DATALENGTH-2]=i/10;
	Q=PrtInt(X[i-1]);
    cout<<"X["<<i-1<<"]:"<<Q<<endl;
 }*/
 //cout<<endl;

 
 for(i=0;i<n;i++)
 {
    SetZero(Y[i]);
    for(j=0;j<th-1;j++)
	{
     SetZero(temp1);
	 SetZero(temp2);
	 Power(X[i],temp1,j+1);
	 Multiply(temp1,factor[j],temp2);
	 SetZero(temp1);
	 //Plus(X[j],temp2,temp1);
	 //SetZero(temp2);
     Plus(temp2,Y[i],temp1);
	 IntCpy(Y[i],temp1);
	}
    Plus(key,Y[i],temp1);
	IntCpy(Y[i],temp1);
	Division(temp1,p,Y[i],temp2);
//	Q=PrtInt(Y[i]);
    //cout<<"Y["<<i<<"]:"<<Q<<endl;
 }
 pwnd1->ResetContent();
 for(i=0;i<n;i++)
{
  Q=PrtInt(X[i]);
   CString str=Q;
   //pwnd1->AddString((LPCTSTR)Q);
   Q=PrtInt(Y[i]);
   str=str+"----"+Q;
   pwnd1->AddString((LPCTSTR)str);
}
cout<<endl;
  
 
    
}

void CSecretShareDlg::OnXuanze() 
{
	// TODO: Add your control notification handler code here
    list_right.ResetContent();
	int count=list_left.GetCount();
	for(int i=0;i<count;i++){
		CString str;
		if(list_left.GetSel(i)==1){
		list_left.GetText(i,str);
		list_right.AddString(str);
		}
	}
  /* for(i=n;i<DATANUM;i++)
	{
	 SetZero(X[i]);
     SetZero(Y[i]);
	}*/
	for(i=0;i<list_right.GetCount();i++){
		CString str;
		list_right.GetText(i,str);
		int index=str.Find('-')-1;
		CString str_left="",str_right="";
		for(int j=0;j<=index;j++){
			str_left+=str.GetAt(j);			
		}
		/*for( k=0;k<270;k++){
		   X[i][k]=0;
		}*/
        SetZero(X[i]);
		for(int k=0;k<str_left.GetLength();k++){
		    CString tmp=str_left.GetAt(k);
			int tmp1=atoi(tmp.GetBuffer(0));
			X[i][270-str_left.GetLength()+k]=tmp1;
		}
	    
		for(j=index+5;j<str.GetLength();j++){
			str_right+=str.GetAt(j);
		}
		/*for(k=0;k<270;k++){
		   Y[i][k]=0;
		}*/
		SetZero(Y[i]);
		for(k=0;k<str_right.GetLength();k++){
		    CString tmp=str_right.GetAt(k);
			int tmp1=atoi(tmp.GetBuffer(0));
			Y[i][270-str_right.GetLength()+k]=tmp1;
		}
	
	}
	if(list_right.GetCount()<th)
	 for(i=list_right.GetCount();i<th;i++)
	{
	 SetZero(X[i]);
     //SetZero(Y[i]);
	}
    
    int kks=1;
	kks=2;
}

void CSecretShareDlg::OnRkey() 
{
	// TODO: Add your control notification handler code here
   byteint TEN_THOUSAND;
   SetZero(TEN_THOUSAND);
   TEN_THOUSAND[DATALENGTH-20]=1;

for(i=0;i<th;i++)
   sign[i]=0;

 SetZero(ZEROVALUE);	
 SetZero(lagrange1);
 SetZero(lagrange2);
 SetZero(lagrange);

for(i=0;i<th;i++)
 {
  SetZero(temp);
  SetZero(temp5);
  IntCpy(temp,ONEVALUE);
  IntCpy(temp5,ONEVALUE);
  //SetZero(temp4);
 
  for(j=0;j<th;j++)
  {
   SetZero(temp1);	
   SetZero(temp2);	
   SetZero(temp3);
   SetZero(temp4);
   
   if(j==i) continue;
   //Substract(ZEROVALUE,X[j],temp1);
   if( IntCmp(X[i],X[j])==-1 )
   {
	 Substract(X[j],X[i],temp2);
	 sign[i]++;
   }

   else Substract(X[i],X[j],temp2);

   Multiply(temp,temp2,temp4);
   IntCpy(temp,temp4);
   SetZero(temp4);
   Multiply(temp5,X[j],temp4);
   IntCpy(temp5,temp4);
   //temp=temp*(ZEROVALUE-X[j])/(X[i]-X[j]);
  }
   SetZero(temp4);
  Multiply(temp5,TEN_THOUSAND,temp1);
  Division(temp1,temp,temp3,temp4);
   
   SetZero(temp1);
   SetZero(temp2);
   if((th-1)%2==1)
   sign[i]++;
   sign[i]=sign[i]%2;
   Multiply(temp4,Y[i],temp1);
   if((sign[i])==1)
   {
	 Plus(lagrange1,temp1,temp2);
     IntCpy(lagrange1,temp2);}
   else
   {
	 Plus(lagrange2,temp1,temp2);
     IntCpy(lagrange2,temp2);}
  //lagrange=lagrange+temp*Y[i];

 }
 //printf("lagrage(%f)=%f\n",x,lagrange);
    if(IntCmp(lagrange1,lagrange2)==-1)
    Substract(lagrange2,lagrange1,lagrange);
	else 
	{
		flag1=1;
		Substract(lagrange1,lagrange2,lagrange);
	}
    SetZero(temp1);
    SetZero(temp3);
    Division(lagrange,TEN_THOUSAND,temp3,temp1);
	Q=PrtInt(temp1);
    R=PrtInt(temp3);
	//if(flag==0)
   // cout<<Q<<"."<<R<<endl;
//	else  cout<<"-"<<Q<<"."<<R<<endl;
	if(temp3[DATALENGTH-19]>3)
    flag1=2;
    //temp1[DATALENGTH-1]++;
	IntCpy(lagrange,temp1);
	SetZero(temp1);
    SetZero(temp3);
    Division(lagrange,p,temp3,temp1);
	IntCpy(lagrange,temp3);
    if(flag1==2)
	Plus(temp3,ONEVALUE,lagrange);	
    Q=PrtInt(lagrange);
	m_edit.SetWindowText((LPCTSTR)Q);
	
}