MH背包密码算法算法原理与实现

MH背包密码算法算法原理与C语言实现 运行环境：WINDOWS下VC6.0及以上编程工具 运行方式：（1）WINDOWS下VC6.0及以上编程工具编译链接运行 （2）工程文件夹下Debug下的*.exe

#include
#include
#include
#include


#define p_num 5                 //定义加密的0-1序列位数为p_num可以相应的更改


void increase（int numlong a[]）    //num为超递增数列的个数，数组a为存放生成的结果，且数组中只有0num-1是有用数
{
	int isum;
    a[0]=1+rand（）%num;
    sum=a[0];
    for（i=1;i	{ 
	    a[i]=sum+1+rand（）%num;
        sum=sum+a[i];
	}
}

//求一个数w在MOD N 下的逆元w-1函数；
int inv（int xinint n0）        //求xin*xin-1=1 mod n0
{
	long n1n2qrb1b2t;
    if（xin==0）
       b2=0;
    else
	{ 
		n1=n0;n2=xin;b2=1;b1=0;
        do{
			r=（n1%n2）;
            q=（n1-r）/n2;
            if（r==0）
			{
				if（b2<0） b2=n0+b2;
			}
            else
			{
				n1=n2;
				n2=r;
	            t=b2;
	            b2=b1-q*b2;
				b1=t;
			}

		}while（r!=0）;
    }
	return（b2）;
}

//求两个数的最大公约数函数，该函数可用于检测两个数是否互素；
int gcd（long along b）
{
	long t;
    t=a;
    while（!（（a%t==0）&&（b%t==0））） t--;
    return t;                          //t=1时，a与b互素，否则不互素。
}

//整数N和w选择函数；
void select_n_w（int numlong s[]int b[]）     /* num为超递增的个数数组s为调用时传超递增数组的地址，
                                         数组b为存放N和w其中b[0]存放Nb[1]存放w   */
{
    b[0]=2*s[num-1]+rand（）%num+1;       //b[0]存放N，作为模数N
    while（1）                             //在1~9999的范围内寻找合适的乘数w
	{
		b[1]=rand（）%9999+1;              //w作为乘数，小于9999，存放在b[1]中
		if（gcd（b[1]b[0]）==1） break;     //w与N互素
   }
}
          
//主函数实现
void main（）
{
	int p_text[p_num]={0}inv_p_text[p_num]={0}; //为了方便演示，p_test[p_num]为既定赋值，实际中可以更改
	long sk[p_num]={0}pk[p_num]={0}b[2]={01};
	int wNij=0;
	long inv_w;
	unsigned __int64 tempmidtemp1temp2;
	long c_text=0;
	clock_t t_startt_end;
	printf（“请输入%d位的0-1明文信息序列（0-1代码以“，”隔开）：\n“p_num）;       //明文输入提示为0-1序列
	for（i=0;i	{
		scanf（“%d“&p_text[i]）;
	}

	//记录程序运行时间开始
	t_start=clock（）;
	printf（“\n**********************$演示程序开始$**********************\n“）;
	printf（“输入的%d位0-1明文信息序列为：\n“p_num）;
	for（i=0;i	{
		printf（“%d“p_text[i]）;
	}
	printf（“\n“）;

	//私钥sk[]-超递增序列的生成存放在sk[]中
	increase（p_numsk）;
	printf（“生成的私钥序列为：“）;
	for（j=0;j	{
		printf（“%d “sk[j]）;
	}
	printf（“\n“）;
	
	//选择合适的模数N和乘数w存放在b[2]中
	select_n_w（p_numskb）;
	w=b[1];N=b[0];
	printf（“乘数w=%d模数N=%d“wN）;
	
	//求乘数w关于模数N的逆元w^（-1）;
	inv_w=inv（wN）;
	printf（“乘数w关于模数N的逆元inv_w=%d\n“inv_w）;
	
	//通过M-H变换求出公钥pk[]
	for（j=0;j	{
		mid=w*sk[j];
		pk[j]=mid%N;
	}
	printf（“生成的公钥序列为：“）;
	for（j=0;j	{
		printf（“%d  “pk[j]）;
	}
	printf（“\n“）;

	//加密方案的实现过程
	for（i=0;i	{
		c_text+=pk[i]*p_text[i];
	}
	
	//输出加密后的密文
	printf（“加密后的密文形式为：%ld\n“c_text）;
	
	//解密方案的实现过程与输出结果
	temp1=inv_w%N;
	//temp=（inv_w*c_text）%N;                       //测试程序所用
	//printf（“inv_w%N=%ld\n“temp1）;
	temp2=c_text%N;
	//printf（“c_text%N=%ld\n“temp2）;
	temp=temp1*temp2; 
	//printf（“temp=%I64d\n“temp）;
	temp=temp%N;
	//print

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2299  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\0-1序列分组.txt

     文件      58368  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.bsc

     文件     184480  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.exe

     文件     188380  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.ilk

     文件      11423  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.obj

     文件      10719  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.obj.enc

     文件     199400  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.pch

     文件     476160  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.pdb

     文件      10951  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\MH.sbr

     文件      66560  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\vc60.idb

     文件      69632  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\Debug\vc60.pdb

     文件       3870  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\MH.c

     文件       3351  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\MH.dsp

     文件        512  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\MH.dsw

     文件      66560  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\MH.ncb

     文件      53760  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\MH.opt

     文件        828  2013-10-09 16:18  第五章  MH背包密码算法算法原理与实现\MHbag_01代码_加密解密\MH.plg

     文件      58368  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.bsc

     文件     237730  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.exe

     文件     261876  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.ilk

     文件      17639  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.obj

     文件      10719  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.obj.enc

     文件     211060  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.pch

     文件     558080  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.pdb

     文件      10951  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\MH.sbr

     文件      74752  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\vc60.idb

     文件      69632  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\Debug\vc60.pdb

     文件       6958  2013-10-09 16:20  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\MH.c

     文件       3351  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\MH.dsp

     文件        512  2013-10-07 18:07  第五章  MH背包密码算法算法原理与实现\MHbag_文件读取_加密解密\MH.dsw

............此处省略12个文件信息