secretsharedlg.cpp

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

// SecretShareDlg.cpp : implementation file
//

#include "stdafx.h"
#include "SecretShare.h"
#include "SecretShareDlg.h"

#include<stdio.h>
#include <conio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<iostream.h>
#include<afx.h>

#include<string>
using namespace std; 

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

const DATALENGTH=270;   //大数类型的长度
const MLENGTH=50;       //质数的长度
const TESTNUM=10;       //测试质数时的比较的次数
const DATANUM=20;       //二维大数的长度

typedef unsigned char byteint[DATALENGTH];   //定义大数类型
typedef unsigned char byteint2[DATANUM][DATALENGTH];//定义二维大数类型
typedef unsigned char mtype[MLENGTH];        //定义质数的大数类型

    long int i;
	int n,j,l,th,flag1=0;
	int r[50],sign[50];
    CString Q;
	//string Key;
    char maink[100];
    byteint2 X,Y;
    byteint temp,temp5,temp1,temp2,temp3,temp4,key,lagrange1,lagrange2,lagrange; 
    byteint2 factor;

    byteint p; 
	byteint ONEVALUE;
	byteint ZEROVALUE;
	byteint TWOVALUE;
	mtype Model[TESTNUM];  //TESTNUM big number to be compared
	mtype mZEROVALUE,tempModel;  //0 constant
	byteint EIGHTVALUE; //O,1,2,8 constant
	CString R;
	signed char flag[300];


void SetZero(byteint A);                 //将大数A清零
	int IntValid(byteint validtemp);         //返回大数validtemp的非零位的个数
	void IntCpy(byteint A1,byteint B1);      //将大数B1的值拷贝到大数A1中	
	int IntCmp(byteint A,byteint B);         //比较大数A和B是否相等
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 Division(byteint A,byteint B,byteint C,byteint D);//C=A%B
	int PowerMode(byteint A,byteint C,byteint D,signed char flag[300]);//computing A^B mod C-->D	
	void IntRandom(byteint RandomA,int num);                //随机产生一个大数
	void LoadInt(byteint A,mtype B);                        //将质数类型转换为大数类型
	void TransBi(byteint B,signed char flag[300]);          //将大数B转换为二进制形式
	void Mdata(int len);                                           //产生用于生成质数中进行比较的数
	void RandomData(byteint2 tmp,int n,int len);
	void Power(byteint A,byteint B,int n);
	int Prime(byteint Prm,int len); 
	CString PrtInt(byteint A);                              //将一个大数A转换为相应的字符串形式	
    //CString InttoStr(mtype A);
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSecretShareDlg dialog

CSecretShareDlg::CSecretShareDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CSecretShareDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CSecretShareDlg)
	str_edit = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CSecretShareDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CSecretShareDlg)
	DDX_Control(pDX, IDC_Prime, edit1);
	DDX_Control(pDX, IDC_Rkey_Out, m_edit);
	DDX_Control(pDX, IDC_SLIST, list_right);
	DDX_Control(pDX, IDC_LIST, list_left);
	DDX_Text(pDX, IDC_Prime, str_edit);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CSecretShareDlg, CDialog)
	//{{AFX_MSG_MAP(CSecretShareDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_CONFIRM, OnConfirm)
	ON_BN_CLICKED(IDC_Xuanze, OnXuanze)
	ON_BN_CLICKED(IDC_Rkey, OnRkey)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSecretShareDlg message handlers

BOOL CSecretShareDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CSecretShareDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CSecretShareDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CSecretShareDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

/*---------------------------------------------------------------------------
功能：产生一个质数
入口参数：大数Prm
返回值：产生成功，返回0
----------------------------------------------------------------------------*/
int Prime(byteint Prm,int len)
{

	int i,k,ok;	
	signed char flag[300];
	byteint A,B,C,buf1,buf2;
	SetZero(A); SetZero(B); SetZero(C); SetZero(buf1); SetZero(buf2);	
	
	IntRandom(Prm,len);                //随机产生一个大数B  try b if prime,B是一个奇数	
	SetZero(ONEVALUE);                      //对大数变量ONEVALUE进行清零
	ONEVALUE[DATALENGTH-1]=1;				//ONEVALUE的最后一位为1
	while(1)                                 //一直循环直到找到一个素数为止
	{	
	//	IntRandom(Prm,MLENGTH); 
		ok=1;
		IntCpy(B,Prm);                       //将Prm拷贝到B中 C=N result prime
	    Substract(B,ONEVALUE,buf1);          //将B-ONEVALUE的结果放到buf1中
	    Division(buf1,TWOVALUE,buf2,B);       //B=(B-1)/2的商,buf2=(B-1)/2的余数=0
	    TransBi(B,flag);                     //将B转换为二进制大数	    
	    for(i=0;i<TESTNUM;i++)
		{
		    LoadInt(A,Model[i]);             //将数组Model中的第i+1个数读取到A中
		    k=PowerMode(A,Prm,C,flag);       //(A^flag) mod Prm ->C
			//cout<<k<<endl;
		    if(k!=1 && k!=2)                 //不符合判定规则  
			{
				Plus(Prm,TWOVALUE,buf1);
                IntCpy(Prm,buf1);
				ok=0;
				break;  
			}		
		}

		if(ok) return 0; 
//	if(ok) 
//	for(i=0;i<DATALENGTH;i++)
//		printf("%d",Prm[i]);
	}	
}


/*---------------------------------------------------------------------------
功能：将指定的自定义的大数进行0初始化
入口参数：大数A名
返回值：无
----------------------------------------------------------------------------*/
void SetZero(byteint A)  
{
	memset(A,0,DATALENGTH);                    //调用系统函数进行初始化
}

/*---------------------------------------------------------------------------
功能：将大数B拷贝到大数A中
入口参数：大数A，大数B
返回值：无
----------------------------------------------------------------------------*/
void IntCpy(byteint A,byteint B)
{
	memcpy(A,B,DATALENGTH);                    //调用系统函数完成拷贝
}
/*---------------------------------------------------------------------------
功能：比较两个大数A和B的大小
入口参数：大数A和大数B
返回值：A>B:return 1 ; A=B:return 0 ; A<B:return -1
----------------------------------------------------------------------------*/
int IntCmp(byteint A,byteint B)
{
	int stat;
	stat=memcmp(A,B,DATALENGTH);    //系统函数
	if(stat==0)
		return 0;
	if(stat>0)
		return 1;
	return -1;
}
/*---------------------------------------------------------------------------
功能：A＋B的结果送C
入口参数：大数A,B,C
返回值：无
----------------------------------------------------------------------------*/
void Plus(byteint A,byteint B,byteint C)
{
	register i;
	int X,Y,Z,m,n,valid;
	m=IntValid(A);                 //计算A的长度         
	n=IntValid(B);                 //计算B的长度
	valid=(m>=n)?m+1:n+1;           //计算时要以最长的数为准
	SetZero(C);                    //将C清零
	for(i=DATALENGTH-1;i>=DATALENGTH-valid;i--)
	{
		X=A[i]+B[i];               //按位相加
		Y=X/10;
		Z=X-10*Y;

		C[i]=C[i]+Z;               //计算进位
		if(C[i]==10)
		{C[i]=0;C[i-1]=1;}
		C[i-1]=C[i-1]+Y;
	}
//	if(C[i+1]=10)
//	{	C[i+1]=0;C[i]=1;}
}

/*---------------------------------------------------------------------------
功能：大数SA减去大数SB，结果放入SC
入口参数：被减数SA，减数SB，差SC
返回值：无
----------------------------------------------------------------------------*/
void Substract(byteint SA,byteint SB,byteint SC)
{
	byteint buf;
	register i,j;
	int X;
	IntCpy(buf,SA);                  //将SA的内容拷贝到buf中
	SetZero(SC);                 //SC清零初始化
	for(i=DATALENGTH-1;i>=0;i--)	
	{
		if(buf[i]<SB[i])             //如果最低位不够减
		{
			buf[i]=buf[i]+10;        //向高位借1
			if(buf[i-1]>0)           //如果高位够减，直接减1
				(buf[i-1])--;    
			else                     //否则一直找到够减的位
			{
				j=i-1;
				while(buf[j]==0)     //j不会出现越界，是因为保证了最高位不为0
					buf[j--]=9;
				buf[j]=buf[j]-1;
			}
		}
		X=buf[i]-SB[i];              //将各位减的结果存入SC中
		SC[i]=X;
	}
}

/*---------------------------------------------------------------------------
功能：大数A与大数B相乘，结果放入C中 A×B->C
入口参数：被乘数A和乘数B，结果C
返回值：无
----------------------------------------------------------------------------*/
void Multiply(byteint A,byteint B,byteint C)
{
	register i,j,w;
	int X,Y,Z;
	int Avalid=0;								//Avalid=validating bits of A
	int Bvalid=0;								//Avalid=validating bits of B
	while (A[Avalid]==0 && Avalid<DATALENGTH)
		Avalid++;								//计算Avalid
	while (B[Bvalid]==0 && Bvalid<DATALENGTH)
		Bvalid++;								//计算Bvalid

	SetZero(C);									//将C清零初始化
	
	for(i=DATALENGTH-1;i>=Avalid;i--)
		for(j=DATALENGTH-1;j>=Bvalid;j--)       //逐位进行相乘运算
		{
			X=A[i]*B[j];        
			Y=X/10;
			Z=X-10*Y;
			w=i+j-(DATALENGTH-1);
			C[w]=C[w]+Z;
			C[w-1]=C[w-1]+(C[w]/10)+Y;         //加进位
			C[w]=C[w]-(C[w]/10)*10;            //减进位
		}
	return;
}

/*---------------------------------------------------------------------------
功能：计算大数A÷B的结果，余数放在C中，商在D中
入口参数：被除数A，除数B，余数C，商D
返回值：无
----------------------------------------------------------------------------*/
void Division(byteint A,byteint B,byteint C,byteint D)
{
	register i,j,m;
	int valid_1,valid_2,valid,sbits,cmpval;
	byteint buf1,buf2;
    
	SetZero(buf1);  SetZero(buf2);
	SetZero(D);                       //将大数D进行清零初始化
    IntCpy(C,A);                      //将被除数A拷贝到C中
	valid_2=IntValid(B);              //计算B(除数)的位数,
//	int ii=1;
	while((cmpval=IntCmp(C,B))>0)     //变除法为减法,每减一次就判断是否有C>B,如果满足就继续减。
	{//	cout<<ii++<<endl;
		valid_1=IntValid(C);          //计算C(被除数)的位数,因为它的位数在循环过程中是变化的
		                              //做减法后(C-B)仍然存放在C中
		valid=valid_1-valid_2;        //C的长度与B的长度的差（该值最小为0）
		if(valid>0)                   //如果被除数比除数的位数多
		{
			i=DATALENGTH-valid_1;     //被除数前导零的个数
			j=DATALENGTH-valid_2;     //除数前导零的个数，作下标指示器
			sbits=0;
			for(m=j;m<DATALENGTH;m++)
			{
				if(C[i]>B[j])         //从C和B的最高位开始依次比较对应位的大小，判断是否够减
					break;
				if(C[i]<B[j])
				{
					sbits=1;          //如果不够减，那么C就退一位，再做减法
					break;
				}
				i++;j++;              //当C和B的最高位相等时,就比较二者的次高位
			}
			valid=valid-sbits;
			SetZero(buf1);            //buf1清零
			for(i=valid;i<DATALENGTH;i++)
			{
				j=i-valid;
				buf1[j]=B[i];         //buf1中存放的是B左移若干位之后得到的值
				                      //如果够减,则B左移后最高位与C的最高位对齐,
				                      //否则与C的次高位对齐
			}
		}
		else
			IntCpy(buf1,B);           //当C和B的位数相同时,就直接把B放入缓冲区buf1中

		D[DATALENGTH-1-valid]++;      //这里保存的是在某一位上所做的减法的次数，每做一次就加1
		Substract(C,buf1,buf2);       //不论C的长度与B的长度的差是否大于0，都要做减法，直到C<=B
		IntCpy(C,buf2);
	}
	if(cmpval==0)                     //两个数相等
	{
		SetZero(C);                   //余数为0
		D[DATALENGTH-1]++;            //商为1
	}
}

/*---------------------------------------------------------------------------
功能：将质数类型B拷贝到大数A中，实现类型转换
入口参数：大数A，质数类型B
返回值：无
----------------------------------------------------------------------------*/
//功能：将数B拷贝到大数A，实现类型转换
void LoadInt(byteint A,mtype B)
{
	register i,j;
	SetZero(A);                  //A进行清零初始化
	i=DATALENGTH-1;
	j=MLENGTH-1;
	while(j>0)                   //循环拷贝各位数字
	{
		A[i--]=B[j--];
	}
}

/*---------------------------------------------------------------------------
功能：该函数用来从集合[1,b-1]中产生若干个用于检测的数，存放在Model[]中
入口参数：无
返回值：无
----------------------------------------------------------------------------*/
void Mdata(int len)
{
	register i,j;   
	byteint q;
	CString Q;
	SetZero(q);//Randomly choose a set of 10 numbers in [1,b-1]
	int k=len-2;
	memset(Model,0,TESTNUM*len);  //这个函数在这里用来将整个数组清零，进行初始化
	srand( (unsigned)time( NULL ) );  //进行随机函数的初始化
	for(i=0;i<TESTNUM;i++)            //TESTNUM为需要产生的个数
	{
		for(j=MLENGTH-1;j>=k;j--)
		{
			Model[i][j]=rand()%10;    //注意这里与测试素数的程序中的区别，
			
		}