CRYPTOSYSTÈME ELGAMAL LIBRAIRIE GMP

#____________________________________________________
# Makefile
#----------------------------------------------------
SHELL = /bin/bash
CC = gcc
RM = rm -rf
TAR = tar
MKDIR = mkdir
CHMOD = chmod
CP = cp
MV = mv

PROGNAME = elgamal
EXEC = elg
PACKAGE = $(PROGNAME)
VERSION = 0.3
DISTDIR = $(PACKAGE)-$(VERSION)
HEADERS = elgamal.h algmod.h  
SOURCES = algmod.c elgamal.c main.c 

LDFLAGS = -lgmp
CFLAGS = -Wall

OBJ = $(SOURCES:.c=.o) 
DISTFILES = $(SOURCES) Makefile $(HEADERS) 

all: $(EXEC)  

$(EXEC): $(OBJ)	 
	$(CC) $(LDFLAGS) $(OBJ) -o $(EXEC)

%.o:%.c $(HEADERS) 
	$(CC) -c $< $(CFLAGS)

dist: distdir
	$(CHMOD) -R a+r $(DISTDIR)
	$(TAR) zcvf $(DISTDIR).tar.gz $(DISTDIR)
	$(RM) $(DISTDIR)

distdir: $(DISTFILES)
	$(RM) $(DISTDIR)
	$(MKDIR) $(DISTDIR)
	$(CHMOD) 777 $(DISTDIR)
	$(CP) -rf $(DISTFILES) $(DISTDIR)
clean:
	$(RM) $(PROGNAME) $(OBJ) *~ $(DISTDIR).tar.gz

//____________________________________________________
// main.c
//----------------------------------------------------
/*
UNIVERSITE PARIS 8 MASTER MFPI / RESEAUX ET SECURITE 

CRYPTOSYSTEME ELGAMAL
UTILISANT LA BIBLIOTHEQUE GMP 
FEV 2011 

BILAL LOUELH 
louelh@gmail.com
 */
#include <stdio.h>
#include <stdlib.h>

#include <string.h>
#include "elgamal.h"
void usage(char * exec)
{
  printf("Usage : %s [-g] [-e] [-d]\n-g\tGénérer les clés publique et privée \n-e\tChiffrer avec la clé publique générée\n-d\tDéchiffrer avec la clé privée\n" ,exec);
}

int
main (int argc, char*argv[])
{
  if(argc>1)
    {
      
      if(strcmp(argv[1],"-g")==0)
	{
	  clegen();
	}
	  else if(strcmp(argv[1],"-e")==0)
	    {
	    chiffrer();
	    }
      else if(strcmp(argv[1],"-d")==0)
	{
	  dechiffrer();
	}
      else usage(argv[0]);
      
    }//if argc > 0
  else
    {
      usage(argv[0]);
    }
  return 0;  
}
//____________________________________________________
// elgamal.c
//----------------------------------------------------
/*
UNIVERSITE PARIS 8 MASTER MFPI / RESEAUX ET SECURITE 

CRYPTOSYSTEME ELGAMAL
UTILISANT LA BIBLIOTHEQUE GMP 
FEV 2011 

BILAL LOUELH 
louelh@gmail.com
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
#include "algmod.h"
#include "elgamal.h"

void cles_elgamal(mpz_t P,mpz_t g,mpz_t x,mpz_t h,gmp_randstate_t state)
{    
  gen_premier_alea_intervalle(P,LONGUEUR_PREMIER,state);
  element_generateur(g,P,state);
  gen_alea(x,LONGUEUR_PREMIER,state);
  mpz_mod(x,x,P);
  mpz_powm(h,g,x,P);  
}
     
void cryptage(mpz_t c1, mpz_t c2, mpz_t g, mpz_t h,mpz_t k,mpz_t m,mpz_t P) 
{
  mpz_powm(c1,g,k,P);
  mpz_powm(c2,h,k,P);
  mpz_mulm(c2,c2,m,P);
} 

void decryptage(mpz_t m, mpz_t c1, mpz_t c2, mpz_t x, mpz_t P)
{
  /*
  //Une maniere de faire
  mpz_powm(c1,c1,x,P);
  mpz_invert(c1,c1,P);
  mpz_mulm(m,c2,c1,P);
  */
  //Une bonne maniere de faire (sans inversion)
  mpz_t si;
  mpz_init(si);
  mpz_sub(si,P,x);//si=c1^(q-x) si est l'inverse de s
  mpz_sub_ui(si,si,1);//l'ordre du groupe Zp* est q=p-1 
  mpz_powm(si,c1,si,P);//Theoreme de Lagrange : s*si=1 mod P
  mpz_mulm(m,c2,si,P);// c2 * si = m * s * si = m
}

void clegen()
{
 gmp_randstate_t state;
  mpz_t P;
  mpz_t g;
  mpz_t x;
  mpz_t h;

  gmp_randinit_default(state);
  init_alea(state);         

  mpz_init(P);
  mpz_init(g);
  mpz_init(x);
  mpz_init(h);

  cles_elgamal(P,g,x,h,state);
  gmp_printf("\nClé publique : \n[P] = %Zd  \n[g] = %Zd  \n[h] = %Zd \n",P,g,h);
  gmp_printf("\nClé privée : \n[x] = %Zd \n",x);
   
  FILE * fpublique;
  fpublique=fopen("cle.publique","w");
  gmp_fprintf(fpublique,"%Zd \t %Zd \t %Zd",P,g,h);
  fclose(fpublique);  
  
  FILE * fprivee;
  fprivee=fopen("cle.privee","w");
  gmp_fprintf(fprivee,"%Zd",x);
  fclose(fprivee);  
  
  printf("\n[Clés publique et privée générées]\n\n");
  
  //mpz_clear(P);...
}

void chiffrer ()
{
  char message[LONGUEUR_CHAINE];
  gmp_randstate_t state;
  
  mpz_t m;
  mpz_t P;
  mpz_t g;
  mpz_t h;
  mpz_t k;
  mpz_t c1;
  mpz_t c2;
  
  mpz_init(P);
  mpz_init(g);
  mpz_init(h);
  FILE * fpublique;
  fpublique=fopen("cle.publique","r");
  mpz_inp_str(P,fpublique,10);
  mpz_inp_str(g,fpublique,10); 
  mpz_inp_str(h,fpublique,10);
  fclose(fpublique);
  
  gmp_printf("Clé publique : \n[P] = %Zd  \n[g] = %Zd  \n[h] = %Zd \n",P,g,h);  

  gmp_randinit_default(state);
  init_alea(state);         
  printf("entrez une chaine à crypter : ");
  fgets(message,LONGUEUR_CHAINE,stdin);
  vider_tampon(message,stdin);
  
  mpz_init_set_ui(m,0);
  transcodage(m,message);
  gmp_printf("[Message transcodé] = %Zd\n",m);
  mpz_init(c1);
  mpz_init(c2);
  mpz_init(k);
  gen_alea(k,LONGUEUR_PREMIER-1,state);
  
  cryptage(c1, c2, g,h,k,m,P);
  printf("\n[Message chiffré]\n\n");
  FILE * fcrypte;
  fcrypte=fopen("chiffre.out","w");
  gmp_fprintf(fcrypte,"%Zd \t %Zd",c1,c2);
  fclose(fcrypte); 
  
  printf("[Cryptogrammes enregistrés dans chiffre.out]\n");
  
}

void dechiffrer ()
{
  char message[LONGUEUR_CHAINE];
  
  mpz_t m;
  mpz_t c1;
  mpz_t c2;
  mpz_t x;
  mpz_t P;
  
  mpz_init(m);
  mpz_init(x);
  mpz_init(P);
  mpz_init(c1);
  mpz_init(c2);
  
  FILE * fcrypte;
  fcrypte=fopen("chiffre.out","r");
  mpz_inp_str(c1,fcrypte,10);
  mpz_inp_str(c2,fcrypte,10); 
  fclose(fcrypte);
  
  FILE * fprivee;
  fprivee=fopen("cle.privee","r");
  mpz_inp_str(x,fprivee,10);
  fclose(fprivee);
  
  FILE * fpublique;
  fpublique=fopen("cle.publique","r");
  mpz_inp_str(P,fpublique,10);
  fclose(fpublique);
  
  decryptage(m, c1, c2, x, P);
  detranscodage(message,m);
  
  printf("\n[MESSAGE] %s\n",message);
  //mpz_clear(c1);...
}
//____________________________________________________
// algmod.c
//----------------------------------------------------
/*
UNIVERSITE PARIS 8 MASTER MFPI / RESEAUX ET SECURITE 

CRYPTOSYSTEME ELGAMAL
UTILISANT LA BIBLIOTHEQUE GMP 
FEV 2011 

BILAL LOUELH 
louelh@gmail.com
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
#include "algmod.h"
  
void vider_tampon(const char *buffer,FILE *fp)
{
  char *p = strchr(buffer,'\n');
  if (p == NULL)
    {
      int c;
      while ((c = fgetc(fp)) != '\n' && c != EOF); 
    }  
}
 
void init_alea(gmp_randstate_t state)
      {  
           printf("entrez une chaine aléatoire : ");
           char seed[100];
           fgets(seed,strlen(seed),stdin);
           vider_tampon(seed,stdin);
           printf("\n");
           mpz_t tseed;
           mpz_init(tseed);
           transcodage(tseed,seed);
           gmp_randseed(state,tseed);
           return;
      }

void gen_alea(mpz_t alea,int n,gmp_randstate_t state)
{ mpz_t max;
  mpz_init(max);
  mpz_ui_pow_ui(max,10,n+1);
  mpz_urandomm(alea,state,max); 
}

void gen_alea_intervalle(mpz_t alea,int n,gmp_randstate_t state)
{
     mpz_t max;
     mpz_init(max);
     mpz_ui_pow_ui(max,10,n+1);
     mpz_t min;
     mpz_init(min);
     mpz_ui_pow_ui(min,10,n);
     do
     {
     mpz_urandomm(alea,state,max); 
     }while(mpz_cmp(alea,min) > 0); 
    
     return;
}


void gen_premier_alea_intervalle(mpz_t prime,int n,gmp_randstate_t state)
{
  mpz_t prime2;
  mpz_init(prime2);
  gen_alea_intervalle(prime,n,state);
 
  do
    {
      mpz_nextprime(prime,prime);
      mpz_sub_ui(prime2,prime,1);        // P2=(P-1)/2
      mpz_divexact_ui(prime2,prime2,2);// div exact car 2 | P-1 
      gmp_printf("test P = %Zd \n",prime);
    }while( !mpz_probab_prime_p(prime,MR_REP)//20 tests de Miller-Rabin
	    ||
	    !mpz_probab_prime_p(prime2,MR_REP)
	    );
  
  return;
}

void element_generateur(mpz_t g, mpz_t P,gmp_randstate_t state)
//on sait que (P-1)/2=prime2 est premier
{
  mpz_t prime2;
  mpz_t test;
  mpz_init(prime2);
  mpz_init(test);
  
  mpz_sub_ui(prime2,P,1);        
  mpz_divexact_ui(prime2,prime2,2);
  
  do 
    { 
      gen_alea(g,LONGUEUR_PREMIER,state);
      mpz_mod(g,g,P);
      mpz_powm(test,g,prime2,P);
    
    }while(!mpz_cmp_ui(test,1));
  
}

void mpz_mulm (mpz_t o, mpz_t a, mpz_t b, mpz_t m)
{
mpz_mul (o, a, b); mpz_mod (o, o, m);
}


void transcodage(mpz_t cryptogramme,char * message)
{
  int i;   
  mpz_t Mb;
  mpz_init(Mb);
  mpz_set_ui(Mb,1);
  for(i = 0; message[i];i++)
    {
      mpz_addmul_ui(cryptogramme,Mb,(int)message[i]); 
      mpz_mul_2exp(Mb,Mb,8);
    }
  return;
}

void detranscodage(char* message,mpz_t cryptogramme)  
{
  mpz_t k; 
  mpz_init(k);
  int m;
  for( m = 0; mpz_sgn(cryptogramme)!=0; m++ )
    {
      message[m] = (char) mpz_mod_ui(k,cryptogramme,0x100);  
      mpz_tdiv_q_2exp(cryptogramme,cryptogramme,8);
    }
  message[m] ='\0';
  return;
}
//____________________________________________________
// elgamal.h
//----------------------------------------------------
/*
UNIVERSITE PARIS 8 MASTER MFPI / RESEAUX ET SECURITE 

CRYPTOSYSTEME ELGAMAL
UTILISANT LA BIBLIOTHEQUE GMP 
FEV 2011 

BILAL LOUELH 
louelh@gmail.com
 */

#ifndef ELGAMAL_H
#define ELGAMAL_H
#include <gmp.h>


void cryptage(mpz_t c1, mpz_t c2, mpz_t g, mpz_t h,mpz_t k,mpz_t m,mpz_t P);
void decryptage(mpz_t m, mpz_t c1, mpz_t c2, mpz_t x, mpz_t P);
void cles_elgamal(mpz_t P,mpz_t g,mpz_t x,mpz_t h,gmp_randstate_t state);

void clegen();
void chiffrer();
void dechiffrer();

#endif
//____________________________________________________
// algmod.h
//----------------------------------------------------
/*
UNIVERSITE PARIS 8 MASTER MFPI / RESEAUX ET SECURITE 

CRYPTOSYSTEME ELGAMAL
UTILISANT LA BIBLIOTHEQUE GMP 
FEV 2011 

BILAL LOUELH 
louelh@gmail.com
 */

#ifndef ALGMOD_H
#define ALGMOD_H
#include <gmp.h>

#define LONGUEUR_CHAINE 128 //longueur maximale en nombre de caracteres (octets)
#define LONGUEUR_PREMIER 309 //longueur exacte en chiffres decimaux
//Valeurs ajustables selon puissance de calcul ex 256:617 128:309 ou 64:155  
#define MR_REP 12 //nombre de répétition du test de primalité Miller-Rabin

void init_alea(gmp_randstate_t t);
void gen_alea(mpz_t alea,int n,gmp_randstate_t state);
void gen_alea_intervalle(mpz_t alea,int n,gmp_randstate_t state);
void gen_premier_alea_intervalle(mpz_t premier, int taille, gmp_randstate_t state );
void element_generateur(mpz_t g, mpz_t P,gmp_randstate_t state);
void detranscodage( char * message, mpz_t cryptogramme);
void transcodage(mpz_t cryptogramme, char * message);
void vider_tampon(const char *buffer,FILE *fp);
void mpz_mulm (mpz_t o, mpz_t a, mpz_t b, mpz_t m);

#endif