RSA
Fonctions
Référence du fichier rsamaths.c

Contient des fonctions permettant de générer les clefs RSA et de les utiliser pour chiffrer et déchiffrer. Plus de détails...

#include "rsamaths.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "pointeurs.h"
#include <time.h>

Fonctions

GRDNB calcul_e (GRDNB phi_n, GRDNB *d)
 Permet de calculer e et d à partir de phi(n) tel que e * d = 1 mod phi(n) Plus de détails...
 
int aleatoire (int a, int b)
 Génére alétoirement un entier entre a et b, les deux inclus, avec a <= b. Plus de détails...
 
GRDNB rabinmillerdeux ()
 Génére un entier ayant une très forte chance d'être premier. Plus de détails...
 
GRDNB aleaGRDNB (int taille, int base)
 Génére un entier aléatoire d'une taille et base précises. Plus de détails...
 
void chiffrer (char *fichier, char *fichdest, GRDNB n, GRDNB a)
 Chiffre un fichier selon la clef a (d ou e, tout dépend le contexte de l'appel, signature ou chiffrement) et son produit pq = n et écrit le résultat dans fichdest. Plus de détails...
 
void dechiffrer (char *fichier, char *fichdest, GRDNB n, GRDNB a)
 Dechiffre un fichier selon la clef a (e ou d, tout dépend le contexte de l'appel, vérification de signature ou déchiffrement) et son produit pq = n et écrit le résultat dans fichdest. Plus de détails...
 
int tailleNombre (int nombre, int base)
 Permet de savoir quelle taille le nombre prend à écrire dans une base donnée. Plus de détails...
 

Description détaillée

Contient des fonctions permettant de générer les clefs RSA et de les utiliser pour chiffrer et déchiffrer.

Auteur
I. Laruelle / A. Masciulli - UTT NF05 A18

Documentation des fonctions

◆ aleaGRDNB()

GRDNB aleaGRDNB ( int  taille,
int  base 
)

Génére un entier aléatoire d'une taille et base précises.

Paramètres
[in]tailleUn entier spécifiant la taille que le nombre généré doit respecter.
[in]baseUn entier spécifiant la base.
Renvoie
Un GRDNB tel que nombre >= base^(taille-1).
Avertissement
La fonction srand() doit avoir été appellée auparavant.

Exemple : aleaGRDNB(5,10) = 77760 (taille = 5, base 10).
Vous n'aurez jamais aleaGRDNB(5,10) = 1452 (car le résultat doit être de taille 5)

◆ aleatoire()

int aleatoire ( int  a,
int  b 
)

Génére alétoirement un entier entre a et b, les deux inclus, avec a <= b.

Paramètres
[in]aest un entier
[in]best un entier tel que b >= a
Renvoie
un entier aléatoire compris entre a et b les deux inclus.
Avertissement
La fonction srand() doit avoir été appellée auparavant.

◆ calcul_e()

GRDNB calcul_e ( GRDNB  phi_n,
GRDNB *  d 
)

Permet de calculer e et d à partir de phi(n) tel que e * d = 1 mod phi(n)

Paramètres
[in]phi_nUn grand nombre phi_n
[out]dAddresse du GRDNB de la clef privée
Renvoie
Un GRDNB qui contient la clef publique
Avertissement
La fonction srand() doit avoir été appellée auparavant.

Cette fonction génére aléatoirement e impair et non divisible par 5, et recherche e * d + phi_n * k = pgcd(e,phi_n) via euclide étendu.

Tant que pgcd(e,phi_n) différent de 1, on régénère e et on recommence.

◆ chiffrer()

void chiffrer ( char *  fichier,
char *  fichdest,
GRDNB  n,
GRDNB  a 
)

Chiffre un fichier selon la clef a (d ou e, tout dépend le contexte de l'appel, signature ou chiffrement) et son produit pq = n et écrit le résultat dans fichdest.

Paramètres
[in]fichierChaine de caractères contenant le chemin relatif ou absolu du fichier à chiffrer, accessible en lecture.
[in]fichdestChaine de caractères contenant le chemin relatif ou absolu du fichier chiffré, accessible en écriture, créé s'il n'existe pas et écrasé s'il existe.
[in]nC'est le produit p*q en base 2, qui va servir ici de modulo à toutes les données chiffrées. nb de bits(n) > 8 (taille d'un caractère).
[in]aC'est l'exposant en base 2 de toutes les données chiffrées, d ou e selon que l'on signe avec sa clef privée ou que l'on chiffre avec la clef publique du destinataire.
Avertissement
"fichbin.txt", dans le répertoire d'éxécution doit être accessible en écriture et sera créé ou sera écrasé puis effacé.
  • Le programme commence par lire le fichier source en convertissant un à un tous les caractères en ASCII en base 2 sur 8 bits et en les écrivant dans un autre fichier (fichbin.txt) sur une seule ligne sous forme binaire (un caractère = 8 * '0' et '1').
  • On s'assure que la taille de ce nouveau fichier soit un multiple de ent(log2(n)) (équivalent à (nb de bits de n en base 2) - 1), sinon on complète avec des '0' à la fin.
  • On écrit au début du fichier de destination le nombre de '0' ajoutés.
  • On lit le nouveau fichier par bloc de ent(log2(n)) caractères (car 1 caractère = '0' ou '1' dans ce nouveau fichier).
    • Pour chaque bloc, on récupére bloc^a % n, c'est notre message chiffré. On compléte ce nouveau chiffre par des zeros pour qu'il ait une taille ent(log2(n)) + 1, la taille maximale que le reste peut avoir.
    • On écrit ce nombre dans le fichier de destination
  • On répéte la lecture jusqu'à ce qu'il n'y ait plus de blocs à lire.

◆ dechiffrer()

void dechiffrer ( char *  fichier,
char *  fichdest,
GRDNB  n,
GRDNB  a 
)

Dechiffre un fichier selon la clef a (e ou d, tout dépend le contexte de l'appel, vérification de signature ou déchiffrement) et son produit pq = n et écrit le résultat dans fichdest.

Paramètres
[in]fichierChaine de caractères contenant le chemin relatif ou absolu du fichier à déchiffrer, accessible en lecture.
[in]fichdestChaine de caractères contenant le chemin relatif ou absolu du fichier déchiffré, accessible en écriture, créé s'il n'existe pas et écrasé s'il existe.
[in]nC'est le produit p*q en base 2, qui va servir ici de modulo à toutes les données chiffrées. nb de bits(n) > 8 (taille d'un caractère).
[in]aC'est l'exposant en base 2 de toutes les données chiffrées, d ou e selon que l'on déchiffre avec sa clef privée ou que l'on vérifie une signature avec la clef publique de l'émetteur.
Avertissement
"dechifbin.txt", dans le répertoire d'éxécution doit être accessible en écriture et sera créé ou sera écrasé puis effacé.
  • On lit dans le fichier chiffré le nombre de zeros ajoutés.
  • On lit le fichier chiffré par bloc de ent(log2(n)) caractères, donc nb de bits(n) - 1.
    • Pour chaque bloc, on enlève les zéros devant, on récupére bloc^a % n, c'est notre message déchiffré. On compléte ce nouveau chiffre par des zeros pour qu'il ait une taille ent(log2(n)), la taille maximale que le reste peut avoir.
    • Si on est sur le dernier bloc, on enlève les zeros ajoutés à la fin s'il y en a.
    • On écrit ce nombre dans le fichier temporaire
  • On répéte la lecture jusqu'à ce qu'il n'y ait plus de blocs à lire.
  • Le programme recommence à lire le fichier temporaire en convertissant les '0' et les '1' par bloc de 8 en caractères en ASCII et en écrivant le caractère dans le fichier de destination.

◆ rabinmillerdeux()

GRDNB rabinmillerdeux ( )

Génére un entier ayant une très forte chance d'être premier.

Renvoie
Un GRDNB positif en base 2 s'écrivant sous la forme 2^s * d + 1, avec 70 <= s <= 125 et 2^9 <= d < 2^20 et ayant une probabilité 1 - 1/4^5 d'être premier.
Avertissement
La fonction srand() doit avoir été appellée auparavant.
  • On génére n = 2^s * d + 1, avec 70 <= s (aléatoire) <= 125 et 2^9 <= d (aléatoire) < 2^21 avec d impair, et on répéte la génération tant que n pas impair.
    • On génére a aléatoirement entre 10 et n/100
      • Si reste = a^d % n est égal à 1 ou n-1, on dit que a passe le test.
      • Sinon, on fait s fois l'opération reste = reste^2 % n, en regardant à chaque fois si reste est égal à n-1. Si on en trouve un seul, alors a passe le test.
      • Si on fait l'opération s fois sans trouver de reste égal à n-1, a ne passe pas le test et n ne peut pas être premier. On génére alors un nouveau n.
    • Si a passe le test, alors on regénére un nouveau a et on refait les opération précédentes pour 4 a (5 a en tout). Si un seul d'entre eux ne passe pas le test, on regénére n.
  • Si on a 5 a qui passent le test de Rabin Miller, alors n a une probabilité 1 - 1/4^5 = 0.9990234375 d'être premier.

◆ tailleNombre()

int tailleNombre ( int  nombre,
int  base 
)

Permet de savoir quelle taille le nombre prend à écrire dans une base donnée.

Paramètres
[in]nombreUn entier à tester.
[in]baseLa base dans laquelle on veut savoir la taille.
Renvoie
Un entier, le nombre de chiffres nécessaires pour écire nombre dans la base donnée.

Il suffit de compter le nombre de fois que le nombre est divisible entièrement par la base donnée.