TP de Cryptographie numéro 3



L’ALGORITHME RSA






Julien VEHENT


Novembre 2004









Dans cet exposé, nous allons voir comment crypter des données selon l’algorithme RSA. Tout d’abord, nous allons voir le principe de fonctionnement de l’algorithme. Ensuite, nous allons étudier un code source en C permettant de crypter et de décrypter un fichier en entrée. A la suite de ce code, nous allons voir un autre code permettant cette fois de génèrer des clés publiques et privées pour crypter un message. Enfin, une conclusion discutera des avantages et failles de RSA.




PRINCIPE DE FONCTIONNEMENT


Ce système de chiffrement est une méthode à clé publique qui repose sur certains concepts de la théorie des nombres. Il a été nommé à partir des noms de famille de ses inventeurs : Ronald Rivest, Adi Shamir, et Leonard Adleman.

Le principe est très simple et en voici les principales étapes :

1.

Trouver deux nombres premiers p et q distincts

(p et q doivent rester secrets)

2.

Calculer n = p × q

(n est clé publique)

3.

Choisir e tel que son PGCD avec
(p-1)×(q-1) soit 1

(e est clé publique)

4.

Trouver d tel que
e × d 1 (mod (p-1) ×(q-1))

(d est la clé privée)















Le cryptage fonctionne ainsi :


B génère n, e et d. Il envoie à A les nombres n et e qui constituent la clé publique.


Soit M un nombre qui correspond au message à envoyer.

Note : L'émetteur ne connaît que la clé publique c'est-à-dire les nombres e et n.


Ce dernier calcule Me N (mod n) et envoie au destinataire le message N.


Le récepteur calcule Nd W (mod n). On constate que W est exactement le message M.



PROGRAMME DE CRYPTAGE/DECRYPTAGE SELON LA METHODE RSA


En parralléle de ce code source figurent dans l’archive un éxecutable « RSA.exe » et un fichier « result.cry ». Vous pouvez décrypter le fichier en utilisant RSA.exe, la clés privées de décryptage est « n=221 | d=11 ».



Le programme suivant permet de crypter via la méthode RSA. Nous allons décomposer en détail ce programme.




************************************************************************************************

************************************************************************************************

************************************************************************************************

*********************CODE*****SOURCE*****CRYPTAGE*****DECRYPTAGE*****RSA****************

************************************************************************************************

************************************************************************************************

************************************************************************************************

#include <conio.h>

#include <stdio.h>

#include <string.h>

#include <malloc.h>

#include <math.h>

#include <time.h>

#include <stdlib.h>

void menu(void);

void quitter(void);

void erreur(void);

void choix_crypto(void);

unsigned long int crypt(unsigned char k,unsigned long int n,unsigned long int e);

unsigned char decrypt( unsigned long int k,unsigned long int d,unsigned long int n);

void crypter(void);

void decrypter(void);

void main(void)

{

printf("\n\n\n\n\n\n\n\n\t\t\t CRYPTOGRAPHIE\n\n\n\n\n\n\n\n\n");

printf("\n\n\t\t\t version 1.0");

getch();


menu();

getch();

}


/***************************MENU CRYPTOGRAPHIE*********************************

Menu de choix au lancement du programme */

void menu(void)

{

int choix=0;

printf("\n\n\t\t\t ********************\n");

printf("\t\t\t *MENU CRYPTOGRAPHIE*\n");

printf("\t\t\t ********************\n\n\n\n");

printf("\t TAPEZ :\n\n\n\n");

printf("\t\t1\t POUR\t CRYPTER\n\n");

printf("\t\t2\t POUR\t DECRYPTER\n\n");


printf("\t CHOIX : ");

scanf("%d",&choix);

switch(choix)

{

case 1 : crypter();

choix_crypto();

break;

case 2 : decrypter();

choix_crypto();

break;

default : erreur();

}

}

/*******************************CRYPTER****************************************

Fonction de cryptage

Cette fonction retourne un fichier binaire */

void crypter(void)

{

FILE *source_crypt; //fichier en entrée - à  crypter

FILE *res_crypt; //fichier en sortie - crypté

unsigned char c;

unsigned long int i=0;

unsigned long int k,n,e;

char nom_fichier[20];

printf("\n\n\t\t\t *********\n");

printf("\t\t\t *CRYPTER*\n");

printf("\t\t\t *********\n\n\n\n");

//réception sur l'entrée standard d'un flux de caractère

fflush(stdin);


//chemin absolu du fichier a crypter

printf("Donner le nom du fichier source avec son extension : ");

gets(nom_fichier);

/*Fonction n de la clé

L'algorithme RSA définie n = p*q avec p et q deux entiers*/

printf("\n\n\n\tdonner votre cle publique n : ");

scanf("%d",&n);

/*Clé publique e

e est calculé à  partir de phi(n). On a phi(n)=(p-1)(q-1).

e est premier à  phi(n) */


printf("\n\n\n\tdonner votre cle publique e : ");

scanf("%d",&e);

//ouverture du fichier à  crypter en lecture seule et en binaire

source_crypt=fopen(nom_fichier,"rb");

if(source_crypt==NULL)

{

printf("Impossible d'ouvrir le fichier source.\n");

}


//création et ouverture du fichier crypté en écriture seule et en binaire

res_crypt=fopen("result.cry" , "wb");

if(res_crypt==NULL)

{

printf("Impossible d'ouvrir le fichier resultat.\n");

}

printf("\n\n\t\tATTENDEZ SVP PENDANT LE CRYPTAGE.");


//boucle "tant que" qui parcours le fichier jusqu'à  la fin

while((feof(source_crypt)==0) && (fread(&c,sizeof(unsigned char),1,source_crypt)!=0))

{

//on avance d'un caractère dans le fichier

fseek(source_crypt,sizeof(unsigned char)*i,SEEK_SET);

//stocke le caractére courant dans le pointeur "c"

//&c est le pointeur dans lequel on stocke le caractère courant

//sizeof(unsigned char) et "1" représente la taille mémoire que l'on récupére, ici un caractère

//source_crypt et le fichier source

fread(&c,sizeof(unsigned char),1,source_crypt);

//execute la fonction "crypt" et stocke le resultat dans "k"

k=crypt(c,n,e);

//écrit le caractére "k" dans le fichier "res_crypt"

fwrite(&k,sizeof(unsigned long int),1,res_crypt);

//incrémente i pour passer au caractére suivant

i=i+1;

}


//fermeture des fichiers

fclose(source_crypt);

fclose(res_crypt);

printf("\n\n\n\n\n\n\n\n\n\nLe cryptage de votre fichier est termine.");

printf("\n\nvotre fichier crypter se nomme result.cry");

//attend un retour chariot pour continuer (pause)

getch();

}

/******************************FONCTION CRYPTAGE*******************************/

unsigned long int crypt(unsigned char k,unsigned long int n,unsigned long int e)

{

unsigned long int i,res=1,nbre;

//nbre prend la valeur "k" qui est converti en entier long non signé (positif)

nbre=((unsigned long int)k);

//boucle "pour" qui vas jusqu'à  "e"

for(i=0;i<e;i++)

{

//res se multiplie par nbre

res = res * nbre;

//effectue "res mod (n)" et le stocke dans res

res=fmod(res,n);

}

//renvoi res

return res;

}

/*******************************DECRYPTER**************************************

Le principe du décryptage est le meme que pour le cryptage mais les

variables changent. De plus, on décrypte en utilisant "d" et non pas "e"

avec "n". Enfin, le fichier crypté est directement en binaire, on a donc

pas besoin de conversion mais a l'inverse de la fonction de cryptage,

on retournera ici un fichier de caractères */

void decrypter(void)

{

FILE *source;

FILE *res_decrypt;

char l;

unsigned long int h=0;

unsigned long int d,n;

unsigned long int lect_int;

char nom_fichier[20],nom_fin[20];

printf("\n\n\t\t\t ***********\n");

printf("\t\t\t *DECRYPTER*\n");

printf("\t\t\t ***********\n\n\n\n");

fflush(stdin);

printf("Donner le nom du fichier avec son extension : ");

gets(nom_fichier);

printf("Donner le nom du fichier de destination avec son extension : ");

gets(nom_fin);

printf("\n\n\n\tdonner votre cle prive n : ");

scanf("%d",&n);

printf("\n\n\n\tdonner votre cle prive d : ");

scanf("%d",&d);

source=fopen(nom_fichier , "rb");

if(source==NULL)

{

printf("Impossible d'ouvrir le fichier a decrypter.\n");

erreur();

}

res_decrypt=fopen(nom_fin , "wb");

if(res_decrypt==NULL)

{

printf("Impossible d'ouvrir le fichier resultat.\n");

erreur();

}

printf("\n\n\t\tATTENDEZ SVP PENDANT LE DECRYPTAGE.");

while((feof(source)==0) && (fread(&lect_int,sizeof(unsigned long int),1,source)!=0))

{

fseek(source,sizeof(unsigned long int)*h,SEEK_SET);

fread(&lect_int,sizeof(unsigned long int),1,source);

l=decrypt(lect_int,d,n);

fwrite(&l,sizeof(unsigned char),1,res_decrypt);

h=h+1;

}

fclose(source);

fclose(res_decrypt);

printf("\n\n\n\n\n\n\n\n\n\nLe decryptage de votre fichier est termine.");

getch();

}

/****************************FONCTION DECRYPTAGE*******************************/

unsigned char decrypt(unsigned long int k,unsigned long int d,unsigned long int n)

{

unsigned long int i,res=1;

unsigned char x;

//boucle "pour" qui vas jusqu'à  "d"

for(i=0;i<d;i++)

{

//res se multiplie par k

res=res*k;

//effectue "res mod (n)" et le stocke dans res

res=fmod(res,n);

}

//converti l'entier non signé "res" en char non signé et le stocke dans "x"

x=((unsigned char)res);

//renvoi le caractère "x"

return x;

}


/******************************CHOIX CRYPTO************************************

menu de choix a la sortie d'une premiére action */

void choix_crypto(void)

{

int choix;

printf("\n\n\n\n\t QUE SOUHAITEZ VOUS FAIRE ?\n\n\n\n\n");

printf("\t TAPEZ :\n\n\n");

printf("\t\t1\t POUR\t REVENIR AU MENU CRYPTOGRAPHIE\n\n");

printf("\t\t2\t POUR\t QUITTER LE LOGICIEL\n\n\n");

printf("\t CHOIX : ");

scanf("%d",&choix);

switch(choix)

{

case 1 : menu();

break;

case 2 : quitter();

break;

default : erreur();

}

}


/********************************ERREUR****************************************

affichage lors d'une erreur de saisie et nouveau menu */

void erreur(void)

{

int choix;

printf("\nERREUR DE SAISIE.");

getch();

printf("\n\n\n\n\t\tSOUHAITEZ VOUS REVENIR AU MENU ?\n\n\n\n\n");

printf("\t TAPEZ :\n\n\n");

printf("\t\t1\t POUR\t REVENIR AU MENU \n\n");

printf("\t\t2\t POUR\t QUITTER LE LOGICIEL\n\n\n");

printf("\t CHOIX : ");

scanf("%d",&choix);

switch(choix)

{

case 1 : menu();

break;

case 2 : quitter();

break;

default : erreur();

}

}


/******************************************************************************/

void quitter(void)

{

printf("\n\n\n\n\n\n\n\n\n");

printf("\t\ta bientot");


}

/*************************************FIN**************************************/



PROGRAMME DE GENERATION DE CLES POUR LA METHODE RSA


Le code source suivant permet de générer des clés en se basant sur des entiers de 32 bits. Ce code source en C est compilable, il demande en entrée deux nombres premiers et calcule de lui-même « n », « e » et « d ».




************************************************************************************************

************************************************************************************************

************************************************************************************************

*********************CODE*****SOURCE*****GENERATION*****DES*****CLES**********************

************************************************************************************************

************************************************************************************************

************************************************************************************************





/* Ce programme va vous poposer une cle secrete et une cle public

pour utiliser l'algorithme de cryptage RSA.

Ce code travaille sur des entiers de 32 bits

*/


#include<stdio.h>

#include<stdlib.h>


void main()

{

unsigned long int existe;

unsigned long int e, d, ed;

unsigned long int p, q, fct_euler, tab_e[5*1024];

unsigned long int i, rest, l, b, m, r;

char c;


printf("\n Ce programme va vous generez une cle secrete pour l'algorithme RSA ") ;

printf("\n Donner p un nombre premier: ");

scanf("%ld", &p);

printf(" Donner q un nombre premier: ");

scanf("%ld", &q);


/* Calcul de "e" */

m = 0; //index du "tab_e"

e = 3; //initialisation de "e"

existe = 0; // aucun "e" trouvé pour l'instant


//calcul de la fonction phi(n)

fct_euler = (p - 1) * (q - 1);


printf("Les nbres premier avec %ld:", fct_euler);

getch();


do{

b = 1;

//tant que b=1 et e inférieur à phi(n), on reste dans la boucle

while( b & e < fct_euler)

{

i = fct_euler;

l = e;

do{// algo d'euclide pour calculer le pgcd(e, nbr_euler)


//on effectue phi(n) modulo (e) et on stocke le resultat dans rest

rest = i % l;


//phi(n) prend la valeur de e

i = l;


//e prend la valeur du reste

l = rest;

}

//on effectue ces opérations tant que le reste est supérieur à 1

while (rest > 1);


if (rest == 0) e = e + 2; // Si le reste est nul, c'est que le "e" courant est un diviseur de phi(n),

// donc on ne va pas le prendre


else b = 0; // b prend la valeur 0, c'est à dire qu'on va casser la boucle pour enregistrer "e" ds "tab_e"

}

if ( ! b) // Si e est supérieur ou égal à fct_euler

{

existe = 1; //on a un "e" qui existe

printf("\n%ld", e); //on l'affiche

tab_e[m] = e; //on le stocke a l'emplacement "m" du tableau "tab_e"

m=m+1 ; //on incrémente "m"

m = m%(5*1024); //Pour ne pas depasser la taille du tableau,

//donc seul les 5*1024 valeurs seront sauvegardées.

e = e + 2; //on augmente "e" de 2 (la valeur suivante étant paire)

}

else if(! existe) //On est sortie avec "e" supérieur à fct_euler, ce qui signifie qu'on n'a pas trouvé de "e" valable

{

printf("\nImpossible d'obtenir e ") ;

exit(1) ;

} else break;


} while(1);


//selection d'une valeur de "e" dans le tableau "tab_e"

e = tab_e[rand(m)];



/* calcul de « d » */

// nous avons "ed" est premier avec "fct_euler"

// ed = 1 + k*fct_euler

// donc: d = ed / e

// donc: il faut chercher "ed" multiple de "e"


ed = 1;

do

{

//"ed" additionné à phi(n) est stocké dans "ed"

ed = ed + (p-1)*(q-1);

//"ed" modulo "e" est stocké dans "r"

r = ed % e;

}while (r != 0); //On est sur que "d" existe. donc la boucle doit terminer sur r = 1


d = ed / e;

// on va choisir, parmi les 4*1024 valeurs possible de "e", une seul au hasard

printf("\n\t----Cle prive proposee est :%ld ",e ) ;

printf("\n\t----Cle public(d) proposee est : %ld", d);

getch();

}




CONCLUSION



Les attaques actuelles du RSA se font essentiellement en factorisant l'entier « n » de la clé publique. La sécurité du RSA repose donc sur la difficulté de factoriser de grands entiers. Le record établi en 1999, avec l'algorithme le plus performant et des moyens matériels considérables, est la factorisation d'un entier à 155 chiffres (soit une clé de 512 bits, 2512 étant proche de 10155). Il faut donc, pour garantir une certaine sécurité, choisir des clés plus grandes : les experts recommandent des clés de 768 bits pour un usage privé, et des clés de 1024, voire 2048 bits, pour un usage sensible.


En conclusion, on peut dire que le RSA est probablement une méthode de chiffrement assez sûre; il y a très certainement plus de risques liés à une mauvaise utilisation qu'à une attaque. Il ne faut toutefois pas imaginer que cet algorithme va rester aussi sûr qu’on le dit aujourd’hui. Dans l'histoire, des dizaines de fois, les armées ont cru posséder un chiffrement absolument sûr, et l'utilisaient avec une confiance aveugle; des dizaines de fois les adversaires ont rivalisé d'ingéniosité et ont réussi à décrypter ces messages. Il n'est donc pas exclu qu'un service secret comme la NSA ait réussi une percée considérable et que pour lui, le décryptage du RSA ne soit plus qu'un jeu d'enfant!