cdzjm.cpp

基于控制台下的基于超递增背包的的公钥算法

// cdzjm.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "string.h"
#include "process.h"
/*功能：输入私钥a、素数m、n；产生相应的公钥b*/
int public_key(int *a,int m,int n,int *b)
{
	int k=0,sum=0;
	cout<<"输入背包序列的长度："<<'\n';
	cin>>a[0];
	cout<<"输入递增背包序列(每个元素都大于前面所有元素之和)："<<'\n';
t:	for(int i=1;i<=a[0];i++)
	{
		cin>>a[i];
		if(sum<a[i])
			sum=sum+a[i];
		else
		{
			cout<<"背包序列不合要求，请重新输入！"<<'\n';
			sum=0;
			goto t;
		}
	}
	cout<<"输入素数m：";
	cin>>m;
	cout<<'\n';
	cout<<"输入素数n：";
l:	cin>>n;
		if(n<=sum)
		{
			cout<<"n值必须大于背包序列中所有数的和，请重新输入！"<<endl;
			goto l;
		}
	for(int j=1;j<=a[0];j++)
		b[j]=a[j]*m%n;
	b[0]=a[0];
	cout<<"公钥是："<<endl;
	for(int s=1;s<=a[0];s++)
		cout<<b[s]<<"  ";
	cout<<'\n';
	return 0;
}
/*功能：求a对b的逆元*/
int niyuan(int a,int b)
{
	int x1=1,x2=0,x3=b,y1=0,y2=1,y3=a,t1=0,t2=0,t3=0,temp=0;

	while(1)
	{
		if(y3==0)
		{
			cout<<"无逆元";
			exit(1);
			return 0;
		}
		if(y3==1)
		{
			if(y2<=0)
				return b+y2;
			else
				return y2;
		}
		temp=x3/y3;
		t1=x1-temp*y1;
		t2=x2-temp*y2;
		t3=x3-temp*y3;
		x1=y1;
		x2=y2;
		x3=y3;
		y1=t1;
		y2=t2;
		y3=t3;
	}
}
/*功能：利用公钥b对消息str加密
参数：str表示消息、b表示公钥、c表示密文*/
void jiami(char *str,int *b,int *c)
{
	int i=0,j=0,sum=0;
	cout<<"输入消息："<<'\n';
	cin>>str;
	i=strlen(str);
	char *temp=new char[(i/b[0]+1)*b[0]+1];
	strcpy(temp,str);
	if(i%b[0]!=0)
	{		
		for( j=i;j<(i/b[0]+1)*b[0];j++)
			temp[j]='0';
		temp[j]='\0';
	}
	i=strlen(temp);
	c[0]=i/b[0];
	for(int m=1;m<=i/b[0];m++)
	{
		for(int n=0;n<b[0];n++)
			sum=sum+(temp[(m-1)*b[0]+n]-48)*b[n+1];
		c[m]=sum;
		sum=0;
	}
	cout<<"密文是："<<'\n';
	for(j=1;j<=c[0];j++)
		cout<<c[j]<<"  ";
	cout<<'\n';
}

/*功能：利用私钥a、素数m、n；对密文c解密*/
void jiemi(int* a,int m,int n,int* c,char *str)
{
	int sum=0,m_1=0,i=0,j=0,num=0;
	for(i=1;i<=a[0];i++)
		sum=sum+a[i];
	cout<<"输入素数m：";
	cin>>m;
	cout<<'\n';
	cout<<"输入素数n：";
l:	cin>>n;
		if(n<=sum)
		{
			cout<<"n值必须大于背包序列中所有数的和，请重新输入！"<<endl;
			goto l;
		}
	m_1=niyuan(m,n);
	char *temp=new char[c[0]*a[0]+1];
	for(i=0;i<c[0];i++)
	{
		num=(c[i+1]*m_1)%n;
		for(j=a[0];j>0;j--)
		{
			if(num<a[j])
				temp[i*a[0]+j-1]='0';
			else
			{
				temp[i*a[0]+j-1]='1';
				num=num-a[j];
			}
		}
	}
	temp[strlen(str)]='\0';
	cout<<"消息是："<<'\n'<<temp<<'\n';

}
int main(int argc, char* argv[])
{
	int *a=new int[80];
	int *b=new int[80];
	int *c=new int[80];
	char *str=new char[200];
	int m=0, n=0;
	public_key(a,m,n,b);
	jiami(str,b,c);
	jiemi(a,m,n,c,str);

	return 0;
}