elgamal.cpp

ElGamal密码算法的程序实现

/*
*This program is about the ElGamal algorithm.
*Author : Ting 
*E-mail:[e-mail]	
*Addr: China University of Geosciences ( WuHan )
*Note: ElGamal algorithm is based on the Discrete Logarithm Problem
*/

#include <stdio.h>
/********************************
变量定义
p：大素数
d：随机选择的秘密的解密钥
y：公开的加密钥 
m: 明文 
*********************************/
int p , d , y , m ; 

/****************************************
int Mod(int x, int y , int m) ;
此函数运用模重复平方计算法快速计算幂取模 
需要将y转成2进制 ， 在此通过模2,除2,来求
y各个bit位上的值 
****************************************/
int Mod(int x,int y,int m){//模平方的运算
    int a,b;
    a=1;
    b=x;
    while( y ){
		if( y % 2 == 1 )
			a = a * b % m ;
		y /= 2 ;
		b = b * b % m ;
    }
    return a;
}

/**********************************************
int Inverse(int a , int b , int &x , int &y) ; 
这个函数是求逆元的，用的是扩展的欧几里得算法         
通过此算法得到的是    a_1*a+b_1*b=1 ; a_1就是
a mod b  的逆元 
***********************************************/ 
int a_1 , b_1 ;
int Inverse(int a,int b,int &a_1,int &b_1)    
{
	int t,d;
	if (b==0) { a_1=1; b_1=0; return a; }
	d=Inverse(b,a%b,a_1,b_1);
	t=a_1;
	a_1=b_1;
	b_1=t-a/b*b_1;
	return d;
}

void  Encry(int p,int a,int d,int m,int k)
{
    int  u , c1 , c2;
    y = Mod( a , d , p ) ;
    u = Mod( y , k , p ) ;
    c1 = Mod( a , k , p ) ;
    c2 = u * m % p ;
    printf("c1=%d c2=%d \n",c1,c2) ;
}

void  Decry(int c1,int c2,int d,int p)
{
    int v , v_1 , m ;
    v = Mod ( c1 , d , p ) ;
    Inverse( v , p ,a_1 , b_1 ) ;
    a_1 = ( a_1 + p ) % p ; 
    v_1 = a_1 ;
    m = c2 * v_1 % p ;
    printf("m=%d \n", m ) ;
}

int main()
{
	int flag ;     
    while( 1 ){
		printf("请选择要执行的操作： 1.Encryption  2.Decryption \n");         
		scanf("%d",&flag);
		if(1==flag){
			int a , k;
			printf("please input (p,a,d,m,k): ");
			scanf("%d%d%d%d%d",&p,&a,&d,&m,&k);
			Encry( p , a , d , m , k ) ;
        }
		else{
			int p , d , c1 , c2;
			printf("please input (c1,c2,d,p): ");
			scanf("%d%d%d%d",&c1,&c2,&d,&p);
			Decry( c1 , c2 , d , p ) ;
        }
	}
	return 0;
}
/*
p = 2579
a = 2
d = 765
m = 1299
k = 853
*/