Implémentation en C à un but pédagogique du cryptosystème Elgamal
utilisant la bibliothèque GMP
- Le code est simplifié pour une meilleure compréhension
- Une bonne introduction de l'utilisation de la bibliothèque GMP pour les calculs des grands nombres
- Application de la cryptographie asymétrique (la partie la plus délicate du protocole SSL enfin je crois :p )
- Une source de copier-coller pour les étudiants
les sources une fois décompressés se compilent sous Linux
par un $>make ce qui crée l exécutable elg
puis
$>./elg -g génére les clés publique et privée
$>./elg -e Chiffre le message que vous entrez au clavier avec la clé publique
$>./elg -d Déchiffre le message avec la clé privée
_________________________________________________________________________
Sous windows le programme s exécute dans une console et faut lier la
bibliothèque GMP lors de la compilation, j'ai compilé le programme sous code::blocks
en utilisant MinGW, j écrirai un tutoriel pour détailler la procédure d'installation de GMP sous windows
dont voici grossièrement la procédure :
1/ Télécharger la dernier version MinGW (Auto-installer pour faire vite)
2/ Cocher MSYS lors de l'installation
3/ Télécharger la dernière version de GMP et la décompressée dans c:\gmp-5.0.1 par exemple
3/ Lancer le terminal Shell (fourni par MinGW)
4/ Se positionner dans le dossier des sources gmp $> cd /c/gmp-5.0.1
5/ ./configure --prefix=/c/MinGW ajouter aussi --enable-cxx pour ceux qui compileront du C++
6/ make
7/ make check
8/ make install
A présent GMP est installé dans MinGW est peut être utilisé depuis votre IDE préféré par exemple Code::blocks
9/ installer Code::blocks
10/ Créer un nouveau projet, Lier la libgmp : project->build options->Linker settings->add c:\Mingw\lib\libgmp.a Ajouter aussi dans Other linker options: -static-libgcc pour éviter de se trimballer la dll
11/ Écrire un programme de calcul multi-précision où il y'aura #include<gmp.h> :)
12/ compiler et exécuter
__________________________________________________________________
Un exécutable pré-compiler Windows est inclus dans l'archive
Source / Exemple :
#____________________________________________________
# 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
Conclusion :
Une implémentation effective du cryptosystème Elgamal
le code n'est pas beaucoup commenté mais assez aéré
je répondrai à vos questions si vous n'arrivez pas à comprendre
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.