elgamal.cpp

本项目实现Elgalma体制的加解密

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
unsigned int buffer[5];  //定义缓冲区为全局变量
//--------------------------定义基本的逻辑函数--------------------
#define f1 (B&C)|(~B&D) 
#define f2 B^C^D
#define f3 (B&C)|(B&D)|(C&D)
#define f4 B^C^D
#define MAX 32  //定义位数
int i;
//*------------------------------------------------------------------------*
//*-----------------------------生成随机素数-------------------------------*
//*------------------------------------------------------------------------*
int toBinary(unsigned int r, int *binary)  //将十进制数转换为二进制数的函数
{
    for(i=0;i<MAX;i++) 
	{
		binary[i]=r%2;	
        r=r/2;
	}
	return 0;
}

unsigned int toDecimal(int *binary)  //将二进制数转换为十进制数的函数
{
    unsigned int d=0,k=1;
    for(i=0;i<MAX;i++)  
    {
        d=d+binary[i]*k;
        k=k*2;
    }
    return d;
}

int getRand(int *R)  //生成随机数的函数
{
	unsigned int r;
	srand((unsigned long)time(NULL));  //设置时间为随机数种子
    r=rand()*rand(); //产生随机数

	toBinary(r,R);  //使生成的随机数转换为二进制数存入32位的数组中
	return 0;
}

unsigned int Mod(int *n,unsigned int b,unsigned int m)  //模重复平方算法的函数
{
    unsigned int a=1;
    for(i=0;i<MAX;i++)  
    {
        if(n[i]==1)  
            a=(a*(__int64)b)%m;
		else 
			a=a%m;
        b=(b*(__int64)b)%m;
    }
    return a;
}

int testPrime(unsigned int random)   //测试生成的随机数是否的素数的函数
{
	int p[MAX];
	int a[5]={2,3,5,7,11};  //定义测试使用的素数
    toBinary(random,p);
	p[0]=0;
    for(i=0;i<5;i++)  //测试五次
    {
        if(Mod(p,a[i],random)!=1)   //如果不是素数返回0
			return 0;
    }
    return 1;   //否则，返回1
}

unsigned int getPrime()
{
    unsigned int Prime;
    int P[MAX];
	int flag=0;

	getRand(P);  //获取随机数（二进制）
	Prime=toDecimal(P);  //将得到的二进制随机数转换为十进制数
	Prime |= 0x80000001;  //将随机数的首位和末尾置1，使满足32位的要求
	flag=testPrime(Prime); 
	while(!flag)  //根据标志位生成素数
	{ 
		Prime = Prime+2;  //避免生成随机数的过程以减少程序运行的时间  
		flag=testPrime(Prime);  //测试生成的随机数是否是素数       
	}
	return Prime;
}

//*------------------------------------------------------------------------*
//*------------------------Elgamal算法密钥对生成---------------------------*
//*------------------------------------------------------------------------*
unsigned int getG(unsigned int p)  //生成本原元g的函数
{
	unsigned int g=3;  //初始化g的值
	int temp[MAX];
	toBinary(p/2,temp);  //(p-1)/2
	while(Mod(temp,g,p)==1)  //如果为1则不是原根，将g进行加1，继续测试 
		g++;
	return g;
}

int getKeys()  //生成密钥的函数
{
	FILE *pri,*pub;
	int temp[MAX];
	unsigned int p,g,x,y;
	pri=fopen("My.pri","wb");  //公私钥文件
    pub=fopen("My.pub","wb");
	p=getPrime();  
	g=getG(p); 
    x=getPrime();  //获取x（x<p-1） 
	while(x>=(p-1))
		x=getPrime();
	toBinary(x,temp);
    y=Mod(temp,g,p);  //获取y,y=g^x % p
	fprintf(pri,"%u,%u,%u",x,g,p);  //公私钥分别存入文件中
    fprintf(pub,"%u,%u,%u",y,g,p);
	fclose(pri);
	fclose(pub);
	return 0;
}

//*------------------------------------------------------------------------*
//*----------------------Elgamal对数据的加解密算法-------------------------*
//*------------------------------------------------------------------------*
unsigned int getInverse(unsigned int e,unsigned int Q)  //求逆元
{  
	unsigned int k,r,n1,n2,t;
	unsigned int b1=0,b2=1;
	n1=Q;
	n2=e;
	while(1)
	{
		k=n1/n2; //试商
		r=n1-k*n2;  //取余,相当于"r=n1%n2;"当r=0时，说明Q是e的倍数，则d=(Q+1)%Q时满足要求（b2=1）。
		if(r!=0)  //当r!=0时，根据gcd(n1,n2)=gcd(n2,r),r=n1%n2,算出b2的值,直到r=0为止
		{
			n1=n2;
			n2=r;
			t=b2;
			b2=b1-k*b2;  
			b1=t;
		}
		else
			break;
	}
	return (Q+b2)%Q;  //当r=0时，说明n1是n2的倍数
}

void Encipher(char *infile,char *outfile,unsigned int y,unsigned int g,unsigned int p) //Elgamal加密函数
{
	FILE *in,*out;
	unsigned int M,C2,C1;
	unsigned int X=0,K=0; 
	int temp[MAX];
	if((in=fopen(infile,"rb"))==NULL)
	{
		printf("Can not open the file!\n");
		exit(0);
	}
    if((out=fopen(outfile,"wb"))==NULL)
	{
		printf("Can not open the file!\n");
		exit(0);
	}
	X=rand()*rand();   //随机生成一个X
	while(X>=(p-1))
		X=rand()*rand();
    toBinary(X,temp);  
    C1=Mod(temp,g,p);  //获取c1
    K=Mod(temp,y,p);  //获取K
	fwrite(&C1,4,1,out); //先将c1写入文件中
    while(!feof(in))
    {
		M=fgetc(in);  
        C2=(unsigned __int64)K*(unsigned __int64)M%p; //根据C2=K*P mod p
        fwrite(&C2,4,1,out);   
    }
	fclose(out);
    fclose(in);   
}

void Decipher(char *infile,char *outfile,unsigned int x,unsigned int p) //Elgamal解密函数
{
	FILE *in,*out;
	unsigned int M,C2,C1;
	unsigned int K=0,Kf=0; 
	int temp[MAX];
	if((in=fopen(infile,"rb"))==NULL)
	{
		printf("Can not open the file!\n");
		exit(0);
	}
    if((out=fopen(outfile,"wb"))==NULL)
	{
		printf("Can not open the file!\n");
		exit(0);
	}
    fread(&C1,4,1,in);  //先从文件中读取c1
    toBinary(x,temp);  
    K=Mod(temp,C1,p);  //得到K
    Kf=getInverse(K,p);  //求K的逆元Kf
    while(!feof(in))
    {
		fread(&C2,4,1,in);  
        M=(unsigned __int64)Kf*(unsigned __int64)C2%p;  //M=Kf*c2 mod p
        fputc(M,out);   
    }
	fclose(out);
    fclose(in);    
}
//*------------------------------------------------------------------------*
//*-------------------------SHA-1生成hash值算法----------------------------*
//*------------------------------------------------------------------------*
void Init()  //初始化缓冲区函数
{
	buffer[0] = 0x67452301;  
	buffer[1] = 0xefcdab89;
	buffer[2] = 0x98badcfe;
	buffer[3] = 0x10325476;
	buffer[4] = 0xc3d2e1f0;	
}	

void Compress(unsigned char *M)  //SHA的压缩函数
{
	int i,j;
	unsigned int A,B,C,D,E;  //寄存器
	unsigned int W[80];  //为由512比特的输入值输入组导出32比特字的块
	unsigned int K[4];  //每一轮使用的加法常量K	
	unsigned int temp;  //中间变量
    //---------赋值---------
    A = buffer[0];  
	B = buffer[1];
	C = buffer[2];
	D = buffer[3];
	E = buffer[4];
	K[0] = 0x5a827999;  
	K[1] = 0x6ed9eba1;
	K[2] = 0x8f1bbcdc;
	K[3] = 0xca62c1d6;

	for(i=0;i<16;i++)  //按照Big-Endian模式，最高位放在最低位的地址，W前16个值
	{
		j=4*i;
		W[j+3]=M[j];
        W[j+2]=M[j+1];
		W[j+1]=M[j+2];
		W[j]=M[j+3];
	}

	for(i=16;i<80;i++)  //计算W后面（16~79）的值
		W[i]=((W[i-16]^W[i-14]^W[i-8]^W[i-3])<<1)|((W[i-16]^W[i-14]^W[i-8]^W[i-3])>>31);

	for(i=0;i<20;i++)  //第一轮
	{
		temp=E+f1+((A<<5)|(A>>27))+W[i]+K[0];  
		E=D;D=C;
		C=(B<<30)|(B>>2);
		B=A;A=temp;
	}

	for(i=20;i<40;i++)  //第二轮
	{
		temp=E+f2+((A<<5)|(A>>27))+W[i]+K[1];
		E=D;D=C;
		C=(B<<30)|(B>>2);
		B=A;A=temp;
	}

	for(i=40;i<60;i++)  //第三轮
	{
		temp=E+f3+((A<<5)|(A>>27))+W[i]+K[2];
		E=D;D=C;
		C=(B<<30)|(B>>2);
		B=A;A=temp;
	}