Consignes

Le TP est à rendre, par email, avant le mercredi 28 avril à 20h00...

Pour ce TP comme pour les suivants, la pièce la plus importante sera une archive tp1-nom-prenom.tar contenant votre programme. J'insiste sur les points suivants :

1. l'archive est au format tar (éventuellement au format tar.gz ou tar.bz2),
2. l'archive contient un répertoire tp1-nom-prenom contenant votre code (elle ne crée rien d'autre dans le répertoire courant),
3. l'archive ne contient pas de fichier binaire ou exécutable (seulement des fichiers sources),
4. l'archive contient un fichier Makefile pour compiler votre programme, avec au minimum les cibles all et clean.

Le non-respect des ces consignes risque de me mettre de mauvaise humeur... (Remarque : un fichier Makefile basique mais modulaire est disponible ici.)

Attention, le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

1. l'architecture de votre programme (code découpé en fonctions etc.),
2. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
3. la présence de commentaires aux endroits appropriés,
4. la présence de documentation pour vos fonctions.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal. Si vous le souhaitez vraiment, vous pouvez aussi m'envoyer un rapport de TP. Le format de ce rapport sera au choix, mais par ordre de préférence :

• dans le corps de votre programme en commentaire,
• dans un fichier README au format texte (mais avec un minimum de mise en page),
• au format pdf,
• au format OpenOffice (.odt),
• au format Word (beurk).

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

• chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,
• votre code doit compiler avec les options -Wall -Werror -Wextra -pedantic -std=c99,
• le sujet de votre message email pour m'envoyer le TP devra comporter la chaîne info614, ou info-614 ou info 614,
• une exécution du programme principal « à vide » ne devra pas provoquer d'erreur.

Liens utiles

• page de la bibliothèque GMP,
• TP1,
• page wikipedia sur RSA.
• mon fichier tp2.h
• les fonction mpz_fwrite et mpz_fread

1. Préliminaires

Le but de ce TP est de programmer un petit logiciel de cryptage / basé sur RSA.

1.1. Rappel sur RSA

Le principe de RSA est basé sur le théorème d'Euler (a^φ(n) = 1 (mod n) si a est premier avec n). RSA fonctionne de la manière suivante :

• on choisit deux nombres premiers p et q ; on note base = pq),
• on choisit un e premier avec (p-1)(q-1),
• on calcule d, l'inverse de e modulo (p-1)(q-1) (en utilisant l'algorithme d'Euclide étendu par exemple),
• on code avec la fonction t ↦ t^e (mod base),
• on décode avec la fonction c ↦ t^d (mod base).

La clé publique est e (et base) et la clé privée est d (et base). Les nombres p et q ne servent plus, sauf si l'ont souhaite optimiser les calculs. (Et il faut les garder secrets...)

1.2. Entrées / sorties en C

Pour manipuler les fichiers, vous utiliserez de préférence les fonctions

• FILE *fopen(const char *path, const char *mode);
• int fclose(FILE *fp);
• size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);

et similaires.

Voici de plus deux fonctions pour écrire et lire le contenu d'une clé dans un fichier :

/* lecture d'une clé */
void lire_cle(char *fichier, mpz_t base, mpz_t cle_e) {
  FILE *cle ;

  if (NULL == (cle = fopen(fichier, "r"))) {
      fprintf(stderr, "Erreur lors de l'ouverture du fichier \"%s\".\nAbandon.\n", fichier);
      exit(-1);
  }

  char str[MAX_SIZE] ;
  fgets(str, MAX_SIZE, cle);
  mpz_set_str(base, str, 62);
  fgets(str, MAX_SIZE, cle);
  mpz_set_str(cle_e, str, 62);
  fclose(cle);
}

/* écriture d'une clé */
void ecrire_cle(char *fichier, mpz_t base, mpz_t cle_e) {
  FILE *cle ;

  if (NULL == (cle = fopen(fichier, "w+"))) {
      fprintf(stderr, "Erreur lors de l'ouverture du fichier \"%s\".\nAbandon.\n", fichier);
      exit(-1);
  }

  fputs(mpz_get_str(NULL, 62, base), cle);
  fputs("\n",cle);
  fputs(mpz_get_str(NULL, 62, cle_e), cle);
  fputs("\n",cle);
  fclose(cle);
}

2. Implémentation

2.1. Génération de la paire clé privée / clé publique

Pour générer une paire clé privée / clé publique, il faut choisir deux nombres premiers p et q de tailles similaires. En partant d'un nombre e premier avec (p-1)(q-1), calculez l'inverse de e modulo (p-1)(q-1).

• d est la clé privée,
• e et base = pq forment la clé publique.

Pour générer ces clés, il faut donc chercher des nombres premiers assez grand (plusieurs centaines de chiffres). Vous pouvez pour ceci utiliser les fonctions

• void mpz_nextprime (mpz_t ROP, mpz_t OP),
• int mpz_probab_prime_p (mpz_t N, int REPS),
• void mpz_urandomb (mpz_t ROP, gmp_randstate_t STATE, unsigned long int N),
• void mpz_urandomm (mpz_t ROP, gmp_randstate_t STATE, mpz_t N).

Pour générer le nombre e, vous pouvez simplement tirer un nombre au hasard et vérifier s'il est premier avec (p-1)(q-1). S'il ne l'est pas, recommencez. (L'espérance du nombre de tirage est assez faible et cette méthode fonctionne donc bien...)

void genere_cles(unsigned taille_base, mpz_t base, mpz_t cle_d, mpz_t cle_e) ;

2.2. Codage à partir de la clé publique

int mpz_fwrite(mpz_t bloc, int nb_limbs, FILE *fichier) ;

int mpz_fread(mpz_t bloc, int nb_limbs, FILE *fichier) ;

int coder_RSA(mpz_t base, mpz_t cle_e, FILE *fichier_clair, FILE *fichier_crypte);

2.3. Décodage à partir de la clé privée

int decoder_RSA(mpz_t base, mpz_t cle_d, FILE *fichier_crypte, FILE *fichier_clair);

2.4. Petite interface

2.5. Test

2.6. Finalisation

void genere_cles(unsigned taille_base, mpz_t base, mpz_t cle_d, mpz_t cle_e) ;