Cryptosystème elgamal librairie gmp

Soyez le premier à donner votre avis sur cette source.

Vue 9 771 fois - Téléchargée 1 271 fois

Description

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
1
Date d'inscription
dimanche 22 avril 2007
Statut
Membre
Dernière intervention
30 juin 2012

salut
je veux executer ces classe sous turbo c mais j ai pas trouver la biblio gmp.h????
Messages postés
20
Date d'inscription
vendredi 23 septembre 2005
Statut
Membre
Dernière intervention
10 juin 2010

Ton code est plus beau que le mien =>10/10 !
Mais bon, j'étais en L2 quand je l'ai fait, c'est marrant, j'ai aussi fait un Master Réseau/Sécurité après ! Bonne chance !
Messages postés
3
Date d'inscription
lundi 7 mars 2011
Statut
Membre
Dernière intervention
8 mars 2011

Merci PGL10 je vais le compiler sous windows aussi et je testerai les caractères accentués
Pour la doc promis j'écrirai un ptit truc
le lien en 4°) est très très instructif
Messages postés
317
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
7 août 2020
2
Bravo pour ce logiciel bien présenté et instructif. Quatre remarques :
1°) Il se compile sans aucun problème sous Windows XP avec Visual C++ 6.0
2°) Une petite documentation et un mode d'emploi seraient les bienvenus
3°) Pour les caractères accentués sous Windows on peut utiliser :
void print(char* s) { // pour afficher avec conversion ANSI to OEM
int n;
char* c;
n = strlen(s);
c = (char *)malloc(n*sizeof(char));
CharToOem(s,c);
printf("%s",c);
free(c);
return;
}
4°) Et de plus, il est intéressant de visiter le site web de Paul Herman à :
http://www.frenchfries.net/paul/factoring/source.html où se trouvent des
sources complémentaires de cryptage et surtout la bibliothèque Integer.h
et Integer.cc qui permet d'utiliser GMP comme de vrais entiers en C et C++

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.