Consignes

Le TP est à rendre, par email, avant le dimanche 24 avril à 23h59...

Pour ce TP comme pour les suivants, la pièce la plus importante sera une archive tp2-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 tp2-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 est disponible ici. Il suppose l'existence de deux fichiers tp2-nom-prenom-gmp.c et ``tp2-nom-prenom-rsa.c.)

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
• page wikipedia sur RSA.
• le fichier Makefile
• le fichier tp2-gmp.h et le fichier tp2-rsa.h
• un petit fichier texte pour tester votre programme
• un gros fichier texte pour tester votre programme

1. La bibliothèque GMP et les grands entiers

1.1. Les types de données

La bibliothèque GMP est une bibliothèque pour manipuler des nombres (entiers, rationnels ou flottants) avec une précision arbitraire. Les initiales signifient « GNU Multi Precision ». Pour compiler du code utilisant cette bibliothèque avec gcc, il faut ajouter le drapeau de compilation -lgmp. (Il faut bien entendu que la bibliothèque soit installée sur votre machine. Pour Debian ou Ubuntu, il s'agit du paquet libgmp3-dev.)

Nous allons essentiellement nous intéresser aux nombres entiers. Pour GMP, un entier est simplement un tableau de « chiffres ». Les types suivants sont définis par GMP :

• mpz_t pour le type des entiers signés (mp pour « multiprecision », z pour le symbole mathématique des entiers Z, et _t pour « type »),
• mp_limb_t pour le type des « digit » (normalement un entier machine 32 ou 64 bits).

En fait, le type mp_limb_t est plus général que juste des « digit », mais cette intuition est suffisante pour les entiers.

Les autres types importants sont :

• mpq_t pour le type des rationnels,
• mpf_t pour le type des flottants avec mantisse arbitraire et exposant borné.

1.2. Les opérations

Je vous renvoie à la documentation, et plus particulièrement à la partie sur les entiers et celle sur les fonctions de formatage.

J'attire votre attention sur le fait que toutes les opérations sur les grands entiers sont en passage par adresse. Ceci vient du fait que les grands entiers sont stockés dans des tableaux, et que l'on veut pouvoir contrôler l'utilisation de la mémoire.

1.3. Structure d'un grand entier

void affiche_grand_entier(mpz_t n) ;

1.4. Arithmétique

void puissance_naive (mpz_t resultat, mpz_t x, mpz_t n, mpz_t m) ;
void puissance_chinoise (mpz_t resultat, mpz_t x, mpz_t n, mpz_t m) ;

void pgcd_bezout (mpz_t g, mpz_t x, mpz_t y, const mpz_t a, const mpz_t b) ;

void pgcd (mpz_t g, const mpz_t a, const mpz_t b) ;

2. RSA

2.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. (Dans notre cas, n=pq et φ(n) = (p-1)(q-1)). 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...)

2.2. Rappels : 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 également deux fonctions pour écrire et lire le contenu d'une clé en ASCII dans un fichier :

/*
 * lecture d'une clé (base et clé) dans un fichier.
 * Le format du fichier est simplement :
 *   - première ligne : base de la clé en base 62
 *   - seconde ligne : clé en base 62
 */
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é (privée ou publique) dans un fichier
 * Le format du fichier est simplement :
 *   - première ligne : base de la clé en base 62
 *   - seconde ligne : clé (d ou e) en base 62
 *
 * Attention, le fichier est écrasé s'il existait.
 */
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);
}

3. Implémentation

3.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).
• void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2).
• int mpz_invert (mpz_t rop, mpz_t op1, mpz_t op2).

  /* initialisation de la graine pour la génération des nombres aléatoires */
  gmp_randstate_t state;
  gmp_randinit_default (state);
  gmp_randseed_ui (state, (unsigned) time(NULL));

/*
 * génère une paire de clés privée / publique.
 *   - "taille_base" est la taille, en bits, de la base (second argument)
 *   - base est la base (c'est le produit des nombres p et q générés
 *     temporairement dans la fonction)
 *   - cle_d et cle_e sont la clé privée et publique
 */
void genere_cles(unsigned taille_base, mpz_t base, mpz_t cle_d, mpz_t cle_e) ;

3.2. Codage à partir de la clé publique

/*
 * écrit "nb_octets" octets du nombre "bloc" dans le fichier. Si l'entier est trop petit,
 * complète par des 0 devant pour ecrire exactement "nb_octets" octets.
 * La valeur de retour est le nombre total d'octets écrits.
 */
int mpz_fwrite(mpz_t bloc, int nb_octets, FILE *fichier) ;

La fonction mpz_fread se trouve ici :

/*
 * lit au plus "nb_octets" octets dans un fichier et les met dans un grand entier.
 * La valeur de retour est le nombre d'octets lus.
 */
int mpz_fread(mpz_t bloc, int nb_octets, FILE *fichier) {
  int i;
  unsigned c;
  int nb_limb = 1 + ((nb_octets-1) / sizeof(mp_limb_t));
  if (bloc->_mp_alloc < nb_limb) {
    mpz_realloc(bloc,nb_limb);
  }
  for(i=0; i<bloc->_mp_alloc ; i++) bloc->_mp_d[i] = 0;

  c = fread(bloc->_mp_d, 1, nb_octets, fichier);
  bloc->_mp_size = 1 + ((c-1) / sizeof(mp_limb_t));

  return(c);
}

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

3.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);

3.4. Petite interface

Utilisation : ./pierre-hyvernat-rsa [options]
  -h :         affiche ce message d'aide
  -g :         génère une paire de clés publique / privée
  -X :         encrype
  -D :         decrypte
  -N n :       précise la taille de la clé (utile avec -g) ; par défaut : 512
  -c fichier : précise le fichier contenant la clé publique à utiliser
               obligatoire avec -X et -g
  -C fichier : précise le fichier contenant la clé privée à utiliser
               obligatoire avec -D et -g
  -I fichier : précise le fichier à traiter ; par défaut : STDIN
  -O fichier : précise le fichier de sortie ; par défaut : STDOUT

3.5. Test

3.6. Finalisation

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