Elgamalcipher

Soyez le premier à donner votre avis sur cette source.

Vue 6 329 fois - Téléchargée 456 fois

Description

Ce programme est une implémentation du chiffrement asymétrique publié par Taher ElGamal en 1985.
Cette implémentation chiffre des fichiers en générant des clef.
Pour utiliser le programme (ligne de commande, pas d'interface graphique), utiliser l'aide "elgamal -h".
Cette implémentation utilise la librairie GMP (http://gmplib.org/)

Source / Exemple :


#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <math.h>
#include <string.h>
#include <time.h>
#define TAILLE_MESSAGE 50
#define PMIN "99999"

void genererClef(mpz_t ,mpz_t ,mpz_t ,mpz_t);
void effacerClef(mpz_t ,mpz_t ,mpz_t ,mpz_t);
void trouverGenerateur(mpz_t,mpz_t);
void chiffrer(char *,mpz_t ,mpz_t ,mpz_t);
void dechiffrer(char *,char *);
void genererFichierDesClefsPrivees(char *,mpz_t ,mpz_t,mpz_t);
void genererFichierDesClefsPubliques(char *,mpz_t ,mpz_t,mpz_t);
void getBlocMessage(mpz_t,FILE *,unsigned long int);
void generationClefEph(mpz_t,mpz_t);
void recupererClefPublique(char *,mpz_t ,mpz_t,mpz_t);
void cryptanalyser(char *,mpz_t );
unsigned long int getTailleOptimale(FILE *,mpz_t );

int main(int argc, char **argv)
{

	if(strcmp(argv[1],"-d")==0)
	{
		dechiffrer(argv[2],argv[3]);
	}
	else{
				if(strcmp(argv[1],"-k")==0)
				{
					mpz_t p,g,Y;
					
					recupererClefPublique(argv[3],p,Y,g);
					
					chiffrer(argv[2],p,g,Y);
					
				}else{
								if(strcmp(argv[1],"-h")==0)
								{
									printf("\n  @$!_______________________@$!\n   | ElGamalEncryptionByCHAR |\n  @$!_______________________@$!\n\nUtilisation:\n\n elgamal cheminVersClair\nChiffre un message en générant une paire de clef\n\n elgamal -k cheminVersClair cheminVersClefPublique\nChiffre un message en utilisant une clef spécifié\n\n elgamal -d cheminVersMessage cheminVersClefPrivee\nDechiffre un message\n\n elgamal -c cheminVersFichierDeDéfinitionDeClefsPublique\nTente une cryptanalyse sur le fichier de clefs publiques spécifié\n");
								}else{
												if(strcmp(argv[1],"-c")==0)
												{
													mpz_t x;
														cryptanalyser(argv[2],x);
														
													mpz_clear(x);
												}else{
																mpz_t p,g,Y,x;
																genererClef(p,g,Y,x);
																gmp_printf("\nAffichage de la génaration des clefs\np=%Zd\ng=%Zd\nY=%Zd\nx=%Zd\n------\n",p,g,Y,x);
																genererFichierDesClefsPrivees(argv[1],p,x,g);
																genererFichierDesClefsPubliques(argv[1],p,Y,g);
																chiffrer(argv[1],p,g,Y);
															}
											}
							}
			}
	
	
	return EXIT_SUCCESS;
}

void trouverGenerateur(mpz_t g,mpz_t p)
{
	mpz_t pm1,pm1sqrt,a,temp,temp2;
	mpz_init(pm1);
	mpz_init(pm1sqrt);
	mpz_init(a);												/*Initialisation, a=0*/
	mpz_init(temp);											/*Initialisation, temp = 0*/
	mpz_init(temp2);										/*Initialisation, temp2 = 0*/
	
		mpz_set_ui(g,2);									/*Initialisation, g=2*/
		mpz_sub_ui(pm1,p,1);							/*Initialisation, pm1= p - 1*/
		mpz_root(pm1sqrt,pm1,2);					
		mpz_add_ui(pm1sqrt,pm1sqrt,1);		/*Initialisation, pm1sqrt = (p - 1)^{1/2} + 1 */
		
		
		gmp_printf("\npm1sqrt : %Zd\ng : %Zd",pm1sqrt,g);
		
		/*On recherche tout les facteurs premiers de pm1*/
		while(mpz_cmp(pm1sqrt,a)>0)
		{
			mpz_nextprime(a,a);							/*Assignation de a au nombre premier suivant sa précédente valeur*/
			
			mpz_powm_ui(temp,pm1,1,a);			/*Assignation, temp = (p-1) mod a*/
			
			
				if(mpz_cmp_ui(temp,0)==0)/*Dans ce cas, a divise pm1*/
				{
					mpz_divexact(temp,pm1,a);		/*Assignation, temp = (p-1) / a*/
					
					mpz_powm(temp2,g,temp,p);	/* Assignation, temp2 = g^{(p-1)/a} mod (p)*/
					
					mpz_set(temp,temp2);
					
					if(mpz_cmp_ui(temp,(unsigned int)1)==0) /*Si g^{(p-1)/a} = 1 mod p*/
						{
							/*Changement du générateur*/		
							mpz_add_ui(g,g,1);
							/*Redémarrage des a, diviseurs premiers de p-1*/
							mpz_init(a);
						}
				}
		}
		
	mpz_clear(pm1);
	mpz_clear(temp);
	mpz_clear(a);
	mpz_clear(pm1sqrt);
}

void genererClef(mpz_t p,mpz_t g,mpz_t Y,mpz_t x)
{
	mpz_init(p);
	mpz_init(g);
	mpz_init(Y);
	mpz_init(x);
	mpz_set_str(p,PMIN,(int)10);
	mpz_nextprime(p,p);
	trouverGenerateur(g,p);
	generationClefEph(x,p);
	mpz_powm(Y,g,x,p);
	
}

void chiffrer(char *message,mpz_t p,mpz_t g,mpz_t Y)
{
	/*Initialisations*/
	mpz_t m,c1,c2,temp,Ke;
	unsigned long int tailleBlocs;
	FILE *fichierACrypter=NULL;
	FILE *fichierCrypte=NULL;
	mpz_init(m);
	mpz_init(c1);
	mpz_init(c2);
	mpz_init(Ke);
	mpz_init(temp);
	
/*Ouverture du fichier à crypter en lecture seule*/
	fichierACrypter = fopen(message,"r");

/*Récupération de la longueur optimale des blocs*/
tailleBlocs = getTailleOptimale(fichierACrypter,p);
fichierACrypter = fopen(message,"r");

if(fichierACrypter == NULL)
	{
		printf("\n\n______________________________\nLe fichier n'a pas pu être chargé______________________________\n\n");
	}else{
/*Création du fichier crypté en écriture effacement*/
	strcat(message,".elGamal");
	fichierCrypte = fopen(message,"w+");

/*Création de l'en-tête du fichier */
fprintf(fichierCrypte,"ElGamalEncryptionByCHAR:BT=%lu\n",(long unsigned int)1);

	getBlocMessage(m,fichierACrypter,1);
do{
/*Génération de la clef éphémère*/	
	generationClefEph(Ke,p);
	
/* Chiffrement du bloc: assignation de c1 et c2*/
	gmp_printf("chiffrement commencé\n c1: %Zd\nc2: %Zd\nm: %Zd\n",c1,c2,m);
	mpz_powm(c1,g,Ke,p);
	mpz_powm(temp,Y,Ke,p);
	mpz_mul(temp,temp,m);
	mpz_powm_ui(c2,temp,1,p);
	gmp_printf("chiffrement effectué\nc1: %Zd\nc2: %Zd\nm: %Zd\n",c1,c2,m);

/* Ecriture des données chiffrées */	
	gmp_fprintf(fichierCrypte,"c1=%Zdc2=%Zd\n",c1,c2);
	
	
/*récupération d'une partie du message*/
	getBlocMessage(m,fichierACrypter,1);
	
}while(mpz_cmp_ui(m,0)!=0);

	/*Tests
	mpz_t x;
	mpz_init(x);
	mpz_set_ui(x,100);
	dechiffrer(message,c1,c2,p,x);
	mpz_clear(x);

  • /
} /*Effacements*/ fclose(fichierACrypter); fclose(fichierCrypte); mpz_clear(m); mpz_clear(Ke); mpz_clear(temp); mpz_clear(c1); mpz_clear(c2); mpz_clear(p); mpz_init(g);/*Me demandez pas pourquoi, il ne veut pas s'effacer sinon !*/ mpz_clear(g); mpz_clear(Y); } void dechiffrer(char *message,char *keys) { mpz_t temp,c1,c2,p,x,g; unsigned long int tailleBlocs; char ligneFichierADecrypter[200]; FILE *fichierADecrypter=NULL; FILE *fichierClair=NULL; FILE *fichierClefs=NULL; mpz_init(temp); mpz_init(c1); mpz_init(c2); mpz_init(p); mpz_init(x); mpz_init(g); /*Ouverture du fichier à décrypter en lecture seule*/ fichierADecrypter = fopen(message,"r"); if(fichierADecrypter == NULL) { printf("\nLe fichier à décrypter n'a pas été trouvé \n"); }else { /*Ouverture du fichier des clefs en lecture seule*/ fichierClefs = fopen(keys,"r"); if(fichierClefs == NULL) { printf("\nLe fichier des clefs n'a pas été trouvé \n"); }else{ /*Récupération des clefs*/ gmp_fscanf(fichierClefs,"ElGamalEncryptionByCHAR_Keys_:p=%Zdx=%Zdg=%Zd",p,x,g); gmp_printf("c1=%Zdc2=%Zdp=%Zdx=%Zd",c1,c2,p,x); /*Ouverture en écriture et effacement du fichier de résultats*/ strcat(message,".elGamalDeCiphered"); fichierClair = fopen(message,"w+"); /*Récupération de la taille en octet des blocs de messages clair*/ gmp_fscanf(fichierADecrypter,"ElGamalEncryptionByCHAR:BT=%Zd",temp);tailleBlocs=mpz_get_ui(temp);mpz_init(temp); printf("\nTaille:%lu\n\n\n",tailleBlocs); /*fgets(ligneFichierADecrypter,200,fichierADecrypter); printf("\n1ere ligne, probleme %s\n",ligneFichierADecrypter);*/ while(NULL != fgets(ligneFichierADecrypter,200,fichierADecrypter) ){ /*Récupération de c1 et c2*/ printf("\nLA LIGNE : %s\n",ligneFichierADecrypter); gmp_sscanf(ligneFichierADecrypter,"c1=%Zdc2=%Zd*",c1,c2); gmp_printf("c1=%Zdc2=%Zdp=%Zdx%Zd",c1,c2,p,x); /*Déchiffrement avec l'amélioration due au théorème de Legendre*/ mpz_sub_ui(temp,p,1); mpz_sub(temp,temp,x); mpz_powm(temp,c1,temp,p); mpz_mul(temp,temp,c2); mpz_powm_ui(c2,temp,1,p); /*Ecriture du résultat */ fprintf(fichierClair,"%c",(int)mpz_get_ui(c2)); printf("%c %d",(int)mpz_get_ui(c2),strlen(ligneFichierADecrypter)); } } } gmp_printf("Déchiffrement effectué\nmessage: %Zd\n",c2); /*Effacement et fermetures*/ mpz_clear(temp); mpz_clear(c1); mpz_clear(c2); mpz_clear(p); mpz_clear(x); mpz_clear(g); fclose(fichierADecrypter); fclose(fichierClair); fclose(fichierClefs); } void genererFichierDesClefsPrivees(char *fichier, mpz_t p, mpz_t x,mpz_t g) { FILE *fichierClefs=NULL; char nomFichier[TAILLE_MESSAGE]; strcpy(nomFichier,fichier); strcat(nomFichier,".elGamalKeys"); fichierClefs = fopen(nomFichier,"w+"); gmp_fprintf(fichierClefs,"ElGamalEncryptionByCHAR_Keys_:p=%Zdx=%Zdg=%Zd",p,x,g); fclose(fichierClefs); } void genererFichierDesClefsPubliques(char *fichier,mpz_t p,mpz_t Y,mpz_t g) { FILE *fichierClefs=NULL; char nomFichier[TAILLE_MESSAGE]; strcpy(nomFichier,fichier); strcat(nomFichier,".elGamalPublicKeys"); fichierClefs = fopen(nomFichier,"w+"); gmp_fprintf(fichierClefs,"ElGamalEncryptionByCHAR_PublicKeys_:p=%ZdY=%Zdg=%Zd",p,Y,g); fclose(fichierClefs); } void recupererClefPublique(char *nomFichier,mpz_t p,mpz_t Y,mpz_t g) { FILE *fichierClefs=NULL; fichierClefs = fopen(nomFichier,"r"); mpz_init(p); mpz_init(Y); mpz_init(g); gmp_fscanf(fichierClefs,"ElGamalEncryptionByCHAR_PublicKeys_:p=%ZdY=%Zdg=%Zd",p,Y,g); gmp_printf("p=%ZdY=%Zdg=%Zd",p,Y,g); fclose(fichierClefs); } void getBlocMessage(mpz_t m, FILE *fichierACrypter ,unsigned long int p) { unsigned long int i; char c; char resultat[TAILLE_MESSAGE]; char tmp[10]; mpz_t temp; mpz_init(temp); mpz_init(m); strcpy(resultat,""); /* Récupération de la chaine de code ASCII du message */ for(i=0;i<=p-1;i++) { c = fgetc(fichierACrypter); if(c==EOF) { break; }else{ sprintf(tmp,"%d",(int)c); strcat(resultat,tmp); mpz_set_str(temp,resultat,10); mpz_set(m,temp); } } mpz_clear(temp); } void generationClefEph(mpz_t clef ,mpz_t p) { int nombreAleatoire; mpz_t MAX; mpz_init(MAX); mpz_set(MAX,p); mpz_sub_ui(MAX,MAX,(unsigned long int) 1); /*Génération d'un nombre aléatoire entre 0 et 2 milliards*/ srand(rand()*time(NULL)); nombreAleatoire=0+(int) (2000000000.0*rand()/(RAND_MAX+1.0)); mpz_mul_ui(MAX,MAX,(unsigned long int)nombreAleatoire); mpz_powm_ui(MAX,MAX,1,p); mpz_set(clef,MAX); mpz_clear(MAX); } unsigned long int getTailleOptimale(FILE *fichierACrypter,mpz_t p) { unsigned long int retour=0; short tailleTrouve=0; char c=0; char resultat[TAILLE_MESSAGE]; char tmp[10]; mpz_t temp; mpz_init(temp); strcpy(resultat,""); /* Récupération de la chaine de code ASCII du message */ while(c != EOF && tailleTrouve==0) { c=fgetc(fichierACrypter); sprintf(tmp,"%d",(int)c); strcat(resultat,tmp); mpz_set_str(temp,resultat,10); if(mpz_cmp(p,temp)>0) { retour++; }else{ retour--; tailleTrouve=1; } } fclose(fichierACrypter); mpz_clear(temp); return retour; } void cryptanalyser(char *cheminVersClefPublique, mpz_t x) { mpz_t p,Y,g,Ytemp; double dif; time_t debut,fin; unsigned long int i=1; int arret = 0; FILE *fichierClefPublique=NULL; fichierClefPublique = fopen(cheminVersClefPublique,"r"); mpz_init(x); mpz_init(p); mpz_init(Y); mpz_init(g); mpz_init(Ytemp); gmp_fscanf(fichierClefPublique,"ElGamalEncryptionByCHAR_PublicKeys_:p=%ZdY=%Zdg=%Zd",p,Y,g); fclose(fichierClefPublique); time(&debut); while(arret == 0) { mpz_add_ui(x,x,i); mpz_powm(Ytemp,g,x,p); if(mpz_cmp(Y,Ytemp)==0) { gmp_printf("\nClef privée potentielle x = %Zd\n",x); } /*Condition d'arret*/ if(mpz_cmp(x,p)==0) { arret=1; } } time(&fin); dif = difftime(fin,debut); gmp_printf("Clef privée cassée en %lf seconde(s) ",dif); mpz_clear(p); mpz_clear(Y); mpz_clear(g); mpz_clear(Ytemp); }

Conclusion :


L'algorithme d'elgamal repose sur le problème des logarithmes discrets. Une fonction de cryptanalyse naïve est fournie par cette implémentation.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

pgl10
Messages postés
310
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1
Bonjour,
- Pour afficher les é, vous pouvez remplacer les é par \202
- Ce serait bien sympathique d'ajouter un zip avec elgamal.exe renommé en elgamal.exx
CHAR As Human
Messages postés
20
Date d'inscription
vendredi 23 septembre 2005
Statut
Membre
Dernière intervention
10 juin 2010

Salut PGL10, ça m'a tout l'air de ne pas être en accord avec la charte de code-sources ce que tu me propose là...
Par contre, ici, sur une petite page google, j'ai mis l'exe (il faudra le renommer) => http://sites.google.com/site/charcrypto/home/elgamal
pgl10
Messages postés
310
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1
Bonjour CHAR As Human. Un grand merci pour ces informations complémentaires. On
peut en trouver d'autres à http://www.bibmath.net/crypto/plan.php3 - Je mets 10
pour le sujet, le source, l'emploi de GMP et la compilation que j'ai pu faire
sans aucun problème. La publication d'un exécutable renommé est conforme à
CodeS-SourceS, explication : http://www.cppfrance.com/code.aspx?ID=41851
pgl10
Messages postés
310
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1
Cela vaut bien un 10
CHAR As Human
Messages postés
20
Date d'inscription
vendredi 23 septembre 2005
Statut
Membre
Dernière intervention
10 juin 2010

Merci beaucoup pour cette note !
J'ai mis en ligne le .exx (à renommer en .exe), c'est donc la version compilé pour Windows.
J'aurais voulu mettre en ligne la version compilé pour Linux (car j'aime bien la portabilité) mais malheureusement, je n'ai pas réussi à compiler "en dur", ce que je veux dire est qu'avec l'exécutable créé pour Linux, il faut installer GMP, j'ai pourtant tenté de compiler avec des librairies statiques ! D'ailleurs, j'espère qu'il n'est pas nécessaire d'installer GMP pour utiliser le programme Windows (j'ai pas essayé sur d'autres Windows que le mien)?

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.