Projet de cryptographie: rsa à jeu reduit d'instruction

Soyez le premier à donner votre avis sur cette source.

Snippet vu 7 364 fois - Téléchargée 18 fois

Contenu du snippet

L'objectif de ce projet est d’implémenter les différentes fonctionnalités du RSA avec la contrainte de ne pas disposer de fonctions mathématiques évoluées, et de se limiter aux seules quatre opérations de base sur grands entiers.
Cette limitation permet de se rapprocher d'un contexte de développement du RSA en environnement contraint comme par exemple la programmation d'un cryptoprocesseur pour carte à puce.
Un façon pratique d'implémenter ces fonctionnalités consiste à utiliser la bibliothèque C de calcul sur les grands nombres entiers, GMP GNU.

Source / Exemple :



            • la classe rsa_gmp.h *******
#include <string.h> #include <stdlib.h> #include <stdio.h> #include <gmp.h> // La fonction PGCD en s'appuyant sur l'algorithme d'EUCLIDE void PGCD (mpz_t r, mpz_t a , mpz_t b) ; // La fonction Genere_nbPremier retourne les deux entiers P et Q // aleatoires et premiers void Genere_nbPremier( mpz_t p, mpz_t q, int n, gmp_randstate_t state ) ; // la fonction genere_PK() permet de créer la clé public e void Genere_publicKey( mpz_t e ,mpz_t p , mpz_t q ,gmp_randstate_t state ); // La fonction genere_privateKey permet de determiner la clé public // algorithme euclide etendu void Genere_privateKey (mpz_t d , mpz_t e , mpz_t phi) ; // la fonction initializeRandom permet d,initialiser le generateur de nombre aleatoire void InitializeRandom(gmp_randstate_t r_state ); // le nextprime permet de calculer le nombre premier suivant void nextprime (mpz_ptr p, mpz_srcptr t) ; //la fonction puissances calcule a exponsant e (mod n) pour de grandes valeurs de l'exposant e void puissance (mpz_t resultat ,mpz_t a, mpz_t e, mpz_t n) ; //La test_primalite verifie si un nombre est premier,c'est une application void test_primalite ( mpz_t resultat , mpz_t n); // calculer different parametre de la clé void Calcul_CRT(mpz_t ip ,mpz_t dp ,mpz_t dq , mpz_t e,mpz_t p,mpz_t q); // fonction de chiffrement de message void chiffre_Msg( mpz_t chiffre, mpz_t message , mpz_t e, mpz_t n); // fonction dechiffrement de message void dechiffre_Msg( mpz_t message2, mpz_t chiffre , mpz_t d, mpz_t n); //dechiffrement en mode CRT void dechiffre_MsgCRT(mpz_t message2, mpz_t cipher , mpz_t dp, mpz_t p, mpz_t dq, mpz_t q, mpz_t ip) ; // la fonction principal du rsa en mode Standard void crypter(); // la fonction principal du rsa en mode CRT void crypterCRT() ; // La fonction qui permet de signer un message m void signer_Msg(mpz_t msg_signe, mpz_t message , mpz_t d, mpz_t n); // La fonction qui permet de signer un message m au mode CRT void signer_MsgCRT(mpz_t msg_signe, mpz_t message , mpz_t dp, mpz_t p, mpz_t dq, mpz_t q , mpz_t ip) ; // fonction verifier_sign verifier si le message a ete altere ou modifie void verifier_sign( mpz_t signature_msg , mpz_t message, mpz_t e, mpz_t n) ;
                          • la classe rsa_gmp.c *******************************************
#include "rsa_gmp.h" #define BITSTRENGTH 1024 /* size of modulus (n) in bits */ #define PRIMESIZE (BITSTRENGTH / 2) /* size of the primes p and q */ #include "rsa_gmp.h" /* la fonction PGCD calcule le PGCD de deux entiers a et b en s'appuyant sur l'algorithme d'Euclide
  • /
void PGCD ( mpz_t resultat, mpz_t a , mpz_t b ) { mpz_t r , r1 ,r2; //intialiser les variables mpz_init( r ); mpz_init( r1 ); mpz_init( r2 ); // affectation mpz_set (r , a ) ; mpz_set (r1 , b) ; while ( mpz_cmp_ui ( r1, 0) != 0) { mpz_mod ( r2, r, r1); mpz_set (r , r1 ) ; mpz_set (r1 , r2) ; } mpz_set (resultat , r) ; // liberer l'espace de variable mpz_clear( r ); mpz_clear( r1 ); mpz_clear( r2 ); } // le nextprime permet de calculer le nombre premier suivant void nextprime (mpz_ptr p, mpz_srcptr t) { mpz_t test ; mpz_init( test ); mpz_add_ui (p, t, 13); test_primalite ( test , p); while (mpz_cmp_ui( test , 0)!= 1 ) { mpz_add_ui (p, p, 13); test_primalite ( test , p); } } /* la fonction puissances calcule a exponsant e (mod n) pour de grandes valeurs de l'exposant e
  • /
void puissance (mpz_t resultat ,mpz_t a, mpz_t e, mpz_t n) { mpz_t temp,t,a_bis,e_bis ; // initialise la variable local mpz_init( temp ); mpz_init( t ); mpz_init( a_bis ); mpz_set( a_bis , a ); mpz_init( e_bis ); mpz_set( e_bis , e ); mpz_set_ui (temp , 1); while ( mpz_cmp_ui ( e_bis,0 )> 0) { mpz_mod_ui( t , e_bis , 2); if( mpz_cmp_ui( t , 0 ) != 0) { mpz_mul( temp , temp , a_bis); mpz_mod( temp , temp ,n ); } mpz_mul(a_bis , a_bis, a_bis); mpz_mod ( a_bis, a_bis, n); mpz_tdiv_q_ui(e_bis,e_bis,2); } mpz_set( resultat , temp ); // liberer l'espace utilisé mpz_clear( temp );mpz_clear(t); mpz_clear(a_bis );mpz_clear(e_bis ); } /* La test_primalite verifie si un nombre est premier,c'est une application de Miller_Rabin @ param long a, n( mod n) @return 1 ou 0
  • /
void test_primalite ( mpz_t resultat , mpz_t n) { mpz_t var ,p, e, m , i , k ,temp ; // initialiser les variables locals mpz_init(var) ;mpz_init(p) ;mpz_init(e) ;mpz_init( temp ) ; mpz_init( m) ;mpz_init( i) ;mpz_init( k) ; mpz_sub_ui ( m , n , 1); mpz_sub_ui ( e , n , 1); mpz_set_ui( var , 10 ); mpz_set_ui ( k , 0 ); mpz_mod_ui ( temp , e , 2); while ( mpz_cmp_ui ( temp , 0 )== 0) { mpz_tdiv_q_ui( e , e , 2); mpz_add_ui ( k , k , 1); mpz_mod_ui ( temp , e , 2); } puissance( p ,var , e , n ); if( mpz_cmp_ui ( p , 1) == 0) { mpz_set_ui( resultat , 1); return; } mpz_set_ui( i , 0); while( mpz_cmp ( i , k ) < 0) { if( mpz_cmp( p , m )== 0) { mpz_set_ui( resultat , 1); break ; } if( mpz_cmp_ui( p , 1 )== 0) { mpz_set_ui( resultat , 0); break ; } mpz_mul( p, p , p ); mpz_mod( p , p , n) ; mpz_add_ui (i, i , 1); } // liberer l'espace utilisé par les variables locals mpz_init(var) ;mpz_init(p) ; mpz_init(e) ;mpz_init(temp) ; mpz_init( m) ;mpz_init( i) ;mpz_init( k) ; } // la fonction initializeRandom permet d,initialiser le generateur de nombre aleatoire void InitializeRandom(gmp_randstate_t r_state ) { /* Initialisation de nombre aleatoire*/ unsigned long int seed; seed = time(0); gmp_randinit_default (r_state); gmp_randseed_ui(r_state, seed); } /* La fonction Genere_nbPremier retourne les deux entiers P et Q aleatoires et premiers
  • /
void Genere_nbPremier( mpz_t p, mpz_t q, int n, gmp_randstate_t state ) { //création de varaiable locale mpz_t rand, nb_aleatoire, max , min , varp , varq; // initialiser les variables mpz_init( rand ); mpz_init( nb_aleatoire ); mpz_init( max ); mpz_init( min );mpz_init( varp );mpz_init( varq ); // calcule du Borne Superieur mpz_ui_pow_ui( max, 2, n+1 ); // calcule du borne inferieur mpz_ui_pow_ui( min, 2, n ); // Génère un nombre compris entre 0 et max et le stocke dans rand. state initialise le générateur aléatoire. do { mpz_urandomm( rand, state, max ); }while( mpz_cmp( rand, min) > 0 ); // Vérifie que rand est supérieur à la borne inférieure nextprime ( p , rand ); // Génère un nombre Q compris entre 0 et max et le stocke dans rand. state initialise le générateur aléatoire. do { mpz_urandomm( nb_aleatoire, state, max ); }while(( mpz_cmp( nb_aleatoire, min) > 0 )|| ( mpz_cmp ( p , q ) == 0)); // Vérifie que rand est supérieur à la borne inférieure nextprime( q , nb_aleatoire ); // clear l'espace utilisé mpz_clear( nb_aleatoire );mpz_clear( rand );mpz_clear( max ); mpz_clear( min );mpz_clear( varq );mpz_clear( varp ); } // la fonction genere_PK() permet de créer la clé public e void Genere_publicKey( mpz_t e ,mpz_t p , mpz_t q ,gmp_randstate_t state ) { mpz_t a , b , c, r , y ,rand_Num; // initialiser les avriable locale mpz_init( a ); mpz_init( b ); mpz_init( c ); mpz_init( y ); mpz_init( r ); mpz_init( rand_Num ); mpz_sub_ui( a, p, 1 ); mpz_sub_ui( b, q, 1 ); mpz_mul( y, a, b ); //Définition d'une valeur max de E. mpz_t max; mpz_init( max ); mpz_set_str ( max , "97" ,0); mpz_urandomm( rand_Num, state, max ); mpz_add_ui ( rand_Num , rand_Num , 3); mpz_mod(c,rand_Num,y); PGCD( r , c, y); while (( mpz_cmp_ui( r,1 )!= 0) ||mpz_cmp( c ,max )>0 ||mpz_cmp_ui( c ,0) ==0 ) { mpz_urandomm( rand_Num, state, max ); mpz_add_ui ( rand_Num , rand_Num , 3); mpz_mod(c,rand_Num,y); PGCD( r , c, y); } mpz_set( e ,c ) ; // effacer les espaces utilisées par les variables mpz_clear( a );mpz_clear( b );mpz_clear( y );mpz_clear( r ); mpz_clear( rand_Num );mpz_clear( max );mpz_clear( c ); } // La fonction genere_privateKey permet de determiner la clé public // algorithme euclide etendu void Genere_privateKey (mpz_t d , mpz_t e , mpz_t phi) { mpz_t e0,t0 , t , q, r, n0, temp ,temp2; // initialiser les variables mpz_init ( e0);mpz_init ( t0 );mpz_init ( t );mpz_init ( q ); mpz_init ( r );mpz_init ( n0 );mpz_init ( temp );mpz_init ( temp2 ); mpz_set_ui( t , 1) ; mpz_set ( n0 , phi ); mpz_set ( e0 , e ); mpz_tdiv_q( q , n0 , e0); mpz_mod ( r ,n0 , e0) ; while( mpz_cmp_ui ( r, 0) > 0) { mpz_mul( temp , q, t); mpz_sub( temp , t0, temp ); if( mpz_cmp_ui ( temp , 0) >= 0) { mpz_mod ( temp , temp ,phi); } else { mpz_mod( temp , temp , phi); } mpz_set( t0 , t); mpz_set( t , temp); mpz_set( n0, e0); mpz_set( e0, r); mpz_tdiv_q( q , n0 , e0); mpz_mod ( r ,n0 , e0) ; } mpz_set ( d , t); // liberer l'espaces des variables mpz_clear( e0 );mpz_clear( t0 );mpz_clear( t );mpz_clear( q ); mpz_clear( r );mpz_clear( n0 );mpz_clear( temp );mpz_clear( temp2 ); } // fonction de chiffrement de message void chiffre_Msg( mpz_t chiffre, mpz_t message , mpz_t e, mpz_t n) { mpz_t cipher; mpz_t i; mpz_t temp; mpz_init(cipher); mpz_init(i); mpz_init(temp); mpz_set_si(cipher,1); puissance (cipher ,message, e, n); mpz_set(chiffre,cipher); mpz_clear(cipher); mpz_clear(temp); } // fonction dechiffrement de message void dechiffre_Msg( mpz_t message2, mpz_t chiffre , mpz_t d, mpz_t n) { mpz_t message; mpz_t i; mpz_t temp; mpz_init(message); mpz_init(i); mpz_init(temp); mpz_set(temp,chiffre); puissance ( message,temp , d, n); mpz_set(message2,message); mpz_clear(message); mpz_clear(temp); } //dechiffrement en mode CRT void dechiffre_MsgCRT(mpz_t message2, mpz_t cipher , mpz_t dp, mpz_t p, mpz_t dq, mpz_t q, mpz_t ip) { // variables locaux mpz_t message,mp,mq ,n; mpz_t temp , pq , var; // initialisation des variables mpz_init(mp); mpz_init(mq);mpz_init( n ); mpz_init(message); mpz_init(temp); mpz_init( pq );mpz_init( var ); mpz_set_ui(message,1); mpz_mul ( n , p , q); dechiffre_Msg(mp, cipher , dp, p); dechiffre_Msg(mq, cipher , dq, q); mpz_sub(pq,mq,mp); mpz_mul(temp,pq,ip); mpz_mod(var,temp,q); mpz_mul( message,var,p); mpz_add(message,message,mp); mpz_mod( message , message , n); mpz_set(message2,message); mpz_clear(mp);mpz_clear( n ); mpz_clear(mq);mpz_clear( var ); mpz_clear(message);mpz_clear(pq); mpz_clear(temp); } // La fonction qui permet de signer un message m au mode STANDARD void signer_Msg(mpz_t msg_signe, mpz_t message , mpz_t d, mpz_t n) { //calcul le haché du message dechiffre_Msg (msg_signe, message ,d ,n); } // La fonction qui permet de signer un message m au mode CRT void signer_MsgCRT(mpz_t msg_signe, mpz_t message , mpz_t dp, mpz_t p, mpz_t dq, mpz_t q , mpz_t ip) { //calcul le haché du message dechiffre_MsgCRT(msg_signe, message , dp, p, dq, q, ip); } // fonction verifier_sign verifier si le message a ete altere ou modifie void verifier_sign( mpz_t signature_msg , mpz_t message, mpz_t e, mpz_t n) { mpz_t msg_hache; mpz_init(msg_hache); // On calcule la signature exposnt e modulo n chiffre_Msg(msg_hache,signature_msg, e , n); // on compare avec la signature du message if(mpz_cmp (message,msg_hache)==0) { printf("\n\n \t Resultat du verificateur : Message correct\n\n\n\n "); } else { printf("\n\n \t Resultat du verificateur : Message corrompu \n\n\n\n"); } mpz_clear(msg_hache); } // la fonction principal du rsa en mode Standard void crypter() { // Variable locales mpz_t p , q ,cipher ,e,d , n , phi , message,msg_chiffre ,sign ; //initialiser les variables locales mpz_init(msg_chiffre); mpz_init(cipher); mpz_init(e); mpz_init(n); mpz_init(p); mpz_init(q); mpz_init(d); mpz_init(phi); mpz_init(sign);mpz_init( message); // initialisationn du generateur gmp_randstate_t state; InitializeRandom(state); Genere_nbPremier( p,q ,512, state); // la valeur de N mpz_mul ( n , p , q); // les variablesP et Q gmp_printf ("\n\n \t P \t: \t%Zd \n", p ); gmp_printf ("\n\n \t Q \t: \t%Zd \n", q ); // Generer la clé public Genere_publicKey( e, p ,q , state); gmp_printf("\n\n \t clef pubic : \t%Zd \n",e); /* // Calculer la valeur de phi mpz_sub_ui( p , p , 1); mpz_sub_ui( q , q , 1); mpz_mul( phi , p , q) ; // genere la cle privee Genere_privateKey ( d , e , phi ); gmp_printf("\n\n \t clef prive : \t%Zd \n",d); // le message a chiffre // le message a chiffre printf("\n\n\n\t Entrez le message a crypter: "); gmp_scanf("%Zd",&message); //chiffre le message chiffre_Msg( msg_chiffre, message, e, n); gmp_printf("\n\n\t Le message chiffre : \t%Zd\n",msg_chiffre); // Signer le message //gmp_printf("\n\n\t Le message \t ,%Zd ,%Zd,%Zd\n",message ,d,n); signer_Msg( sign , message ,d, n ); gmp_printf("\n\n \t Voici la signature du message : %ld\n ", sign ); //dechiffrement du message mpz_init_set_str(cipher, "1",0); dechiffre_Msg (cipher, msg_chiffre ,d ,n); gmp_printf("\n\n\t Le message dechiffre :\t%Zd\n\n",cipher); //verifier la signature du message verifier_sign( sign , message ,e , n);
  • /
printf("\t ------------ Retour au menu ------------------\n\n\n\n "); // liberer les variables locales mpz_clear(p); mpz_clear(q); mpz_clear(cipher); mpz_clear(e);mpz_clear(phi);mpz_clear(n); mpz_clear(message);mpz_clear( msg_chiffre); mpz_clear(sign); } // Mode de CRT du RSA void crypterCRT() { // Variable locales mpz_t p , q ,e ,d , n , phi , message,msg_chiffre ,cipher , msg_dechiffre , dp , dq , ip ,ed ,sp ,sq ,sign; //initialiser les variables locales //mpz_init_set_str(message, "12345678901234567890",0); mpz_init(msg_chiffre); mpz_init(cipher);mpz_init ( message); mpz_init( msg_dechiffre) ;mpz_init(e); mpz_init(n); mpz_init(p); mpz_init(q); mpz_init(d); mpz_init(phi); mpz_init(dp); mpz_init(dq ); mpz_init(ip);mpz_init(ed); mpz_init(sp); mpz_init(sq );mpz_init(sign ); // initialisationn du generateur gmp_randstate_t state; InitializeRandom(state); Genere_nbPremier( p,q ,512, state); // la valeur de N mpz_mul ( n , p , q); // les variablesP et Q gmp_printf ("\n\n \t P \t: \t%Zd \n", p ); gmp_printf ("\n\n \t Q \t: \t%Zd \n", q ); // Generer la clé public Genere_publicKey( e, p ,q , state); gmp_printf("\n\n \t clef pubic : \t%Zd \n",e); // Calculer la valeur de phi Calcul_CRT( ip ,dp ,dq ,e , p , q); mpz_sub_ui( sp , p , 1); mpz_sub_ui( sq , q , 1); mpz_mul( phi , sp , sq) ; // genere la cle privee Genere_privateKey ( d , e , phi ); gmp_printf("\n\n \t clef prive : {\t%Zd%\n ,\n\t%Zd\n\n ,\t%Zd\n\n ,\t%Zd\n\n ,\t%Zd \n\n}", p, q,dp, dq,ip); // le message a chiffre printf("\n\n\n\t Entrez le message a crypter: "); gmp_scanf("%Zd",&message); //Chiffre le message en mode CRT chiffre_Msg( cipher , message, e , n); gmp_printf("\n\n \t Voici le message chiffre : %Zd\n ", cipher ); // Signer le message signer_MsgCRT( sign,message , dp, p, dq, q , ip); gmp_printf("\n\n \t Voici la signature du message au mode CRT: %ld\n ", sign ); //Dechiffre le message au mode CRT mpz_init_set_str(msg_dechiffre, "1",0); dechiffre_MsgCRT(msg_dechiffre, cipher , dp, p, dq, q, ip); gmp_printf("\n\n\t Le message apres le decryptage : %Zd\n", msg_dechiffre); //verifier la signature du message verifier_sign( sign , message ,e , n); printf("\t ------------ Retour au menu ------------------\n\n\n\n "); // Liberer l'espace occupé par les variables locaux mpz_clear( message); mpz_clear( cipher );mpz_clear( msg_dechiffre ); mpz_clear(d);mpz_clear(p);mpz_clear(q); mpz_clear(n); mpz_clear(phi); mpz_clear(dp); mpz_clear(dq); mpz_clear(ip);mpz_clear (msg_dechiffre); mpz_clear(ed);mpz_clear(sp); mpz_clear(sq);mpz_clear(sign); } // calculer different parametre de la clé void Calcul_CRT(mpz_t ip ,mpz_t dp ,mpz_t dq , mpz_t e,mpz_t p,mpz_t q) { //Variable local mpz_t ep, eq ; //initialiser les variable locaux mpz_init ( ep ); mpz_init ( eq ); mpz_sub_ui(ep , p , 1 ) ; mpz_sub_ui(eq , q , 1 ) ; Genere_privateKey( ip , p ,q ); Genere_privateKey( dp , e , ep ); Genere_privateKey( dq , e, eq ); //liberer l'espaces de variables locaux mpz_clear ( ep );mpz_clear ( eq ); }
                              • le Main **********************************************************
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <conio.h> #include <string.h> #include "rsa_gmp.h" int main() { int choix, quit = 0; /* printf("\n\n\t\t\t ********************\n"); printf("\t\t\t *MENU CRYPTOGRAPHIE*\n"); printf("\t\t\t ********************\n\n\n\n"); while ( quit!=1 ) { printf("\t TAPEZ :\n\n\n\n"); printf("\t\t1\t POUR\t RSA en mode STANDARD\n\n"); printf("\t\t2\t POUR\t RSA en mode CRT\n\n"); printf("\t\t3\t POUR\t Quitter\n\n\n"); printf("\t CHOIX : "); scanf("%d",&choix); switch(choix) { case 1 : crypter(); break; case 2 : crypterCRT(); break; case 3 : quit = 1; break; } }
  • /
crypter(); return 0; }
                                                        • FIN ********************************************************

A voir également

Ajouter un commentaire Commentaire
Messages postés
5
Date d'inscription
vendredi 6 novembre 2009
Statut
Membre
Dernière intervention
20 juin 2011

Code bien documenté et clair. cette source peut être très utile notamment dans le cas de programmation embarqué, je vais tester ^^.

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.