on trouve le projet complet projetRSA16
genrsa16.c
Ce code va nous générer une clé privée et une clé publique
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/**
* is_prime - Teste si un entier n est premier (test simple)
* @n: le nombre à tester
*
* Retourne 1 si premier, 0 sinon
*
* Méthode : on teste la divisibilité par tous les entiers impairs de 3 à sqrt(n)
*/
igenrnt is_prime(int n) {
if (n < 2) return 0; // Les nombres < 2 ne sont pas premiers
if (n == 2) return 1; // 2 est premier
if (n % 2 == 0) return 0; // Les nombres pairs > 2 ne sont pas premiers
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return 0; // Divisible par i -> pas premier
}
return 1; // Aucun diviseur trouvé -> premier
}
/**
* random_prime - Génère un nombre premier impair aléatoire dans [min..max]
*
* Boucle jusqu'à obtenir un nombre premier
*/
int random_prime(int min, int max) {
int p;
do {
p = rand() % (max - min + 1) + min; // Tirage aléatoire dans l'intervalle
if (p % 2 == 0) p++; // S'assurer que p est impair
} while (!is_prime(p)); // Répéter tant que p n'est pas premier
return p;
}
/**
* egcd - Algorithme d'Euclide étendu pour calculer le PGCD de a et b
* et trouver les coefficients x et y tels que a*x + b*y = gcd(a, b)
*
* Retourne le PGCD et remplit x et y par les coefficients de Bézout
*/
int egcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1; *y = 0;
return a; // PGCD trouvé = a
}
int x1, y1;
int gcd = egcd(b, a % b, &x1, &y1); // Appel récursif
*x = y1;
*y = x1 - (a / b) * y1; // Mise à jour des coefficients
return gcd;
}
/**
* modinv - Calcul de l'inverse modulaire de e modulo phi
* C'est-à-dire trouver d tel que (d*e) mod phi = 1
*
* Utilise l'algorithme d'Euclide étendu
* Retourne -1 si l'inverse n'existe pas
*/
int modinv(int e, int phi) {
int x, y;
int g = egcd(e, phi, &x, &y);
if (g != 1) return -1; // Inverse modulaire n'existe que si e et phi sont premiers entre eux
return (x % phi + phi) % phi; // On normalise x pour qu'il soit positif
}
int main() {
// Initialisation du générateur de nombres aléatoires avec l'heure actuelle
srand(time(NULL));
// Génération aléatoire de deux nombres premiers p et q distincts dans [50..100]
int p = random_prime(50, 100);
int q;
do {
q = random_prime(50, 100);
} while (q == p); // On s'assure que p et q soient différents
int n = p * q; // Calcul de n = p*q, utilisé pour la clé publique et privée
int phi = (p - 1) * (q - 1); // Calcul de phi(n), la fonction d'Euler
// Choix de e : on cherche un nombre impair e premier avec phi
int e;
for (e = 3; e < phi; e += 2) {
int x, y;
if (egcd(e, phi, &x, &y) == 1)
break; // e trouvé, premier avec phi
}
// Calcul de d, l'inverse modulaire de e modulo phi
int d = modinv(e, phi);
if (d == -1) {
fprintf(stderr, "Erreur : pas d'inverse modulaire pour e=%d\n", e);
return EXIT_FAILURE;
}
// Affichage des résultats (clés publique et privée)
printf("p = %d, q = %d\n", p, q);
printf("n = %d\n", n);
printf("phi = %d\n", phi);
printf("Clé publique (e, n) : (%d, %d)\n", e, n);
printf("Clé privée (d, n) : (%d, %d)\n", d, n);
return EXIT_SUCCESS;
}# compilation du code
gcc genrsa16.c -o genrsa16bruno@debian:~/Works/langageC/rsa16/projet_rsa16$ ./genrsa16
p = 73, q = 59
n = 4307
phi = 4176
Clé publique (e, n) : (5, 4307)
Clé privée (d, n) : (3341, 4307)on va noter la clé public d’Alice , ici 5 et 4307 que Alice va diffuser , surtout a Bob , elle va garder la clé privée de son coté bien secrète 3341 4307
rsa16.c
#include <stdio.h>
#include <stdlib.h>
typedef unsigned short u16;
/**
* modexp - Calcul rapide de l’exponentiation modulaire (base^exp mod modulo)
*/
u16 modexp(u16 base, u16 exp, u16 mod) {
u16 result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
int main(int argc, char *argv[]) {
if (argc != 4) {
fprintf(stderr, "Usage : %s fichier.txt e n\n", argv[0]);
return EXIT_FAILURE;
}
u16 e = (u16)atoi(argv[2]);
u16 n = (u16)atoi(argv[3]);
FILE *in = fopen(argv[1], "rb");
if (!in) {
perror("fopen input");
return EXIT_FAILURE;
}
char outname[256];
snprintf(outname, sizeof(outname), "%s.chi", argv[1]);
FILE *out = fopen(outname, "wb");
if (!out) {
perror("fopen output");
fclose(in);
return EXIT_FAILURE;
}
int ch;
while ((ch = fgetc(in)) != EOF) {
u16 encrypted = modexp((u16)ch, e, n);
fwrite(&encrypted, sizeof(u16), 1, out);
}
fclose(in);
fclose(out);
printf("Fichier chiffré : %s\n", outname);
return EXIT_SUCCESS;
}gedit rsaBob va lui faire un petit message secret en code ascii
echo "Bonjour Alice, voila mon message secret !" > message.txt
cat message.txt
Bonjour Alice, voila mon message secret !bruno@debian:~/Works/langageC/rsa16/projet_rsa16$ ./rsa16 message.txt 5 4307
Fichier chiffré : message.txt.chi
bruno@debian:~/Works/langageC/rsa16/projet_rsa16$ cat message.txt.chi
y�~y^
�V
�1
���V
�y1
�KV
|
y�V
|
�� � K
�V
� �����V
��bCe message est devenu illisible !
Bob le transmet à Alice , qui dispose de sa clé privée
decrsa16.c
#include <stdio.h>
#include <stdlib.h>
/**
* modexp - Calcul rapide de l’exponentiation modulaire (base^exp mod modulo)
*
* @param base La base (entier)
* @param exp L'exposant (clé privée d)
* @param mod Le modulo n
* @return (base^exp) mod mod
*/
typedef unsigned short u16;
u16 modexp(u16 base, u16 exp, u16 mod) {
u16 result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
int main(int argc, char *argv[]) {
if (argc != 4) {
fprintf(stderr, "Usage : %s fichier.chi d n\n", argv[0]);
return EXIT_FAILURE;
}
FILE *in = fopen(argv[1], "rb");
if (!in) {
perror("fopen");
return EXIT_FAILURE;
}
// Conversion des paramètres d et n passés en argument (clé privée)
u16 d = (u16)atoi(argv[2]);
u16 n = (u16)atoi(argv[3]);
FILE *out = fopen("dechiffre.txt", "wb");
if (!out) {
perror("fopen output");
fclose(in);
return EXIT_FAILURE;
}
u16 chunk;
// Lecture bloc par bloc (2 octets) du fichier chiffré
while (fread(&chunk, sizeof(u16), 1, in) == 1) {
// Déchiffrement RSA : m = c^d mod n
u16 decrypted = modexp(chunk, d, n);
fputc((char)decrypted, out);
}
fclose(in);
fclose(out);
printf("Déchiffré dans dechiffre.txt\n");
return EXIT_SUCCESS;
}
bruno@debian:~/Works/langageC/rsa16/projet_rsa16$ ./decrsa16 message.txt.chi 3341 4307
Déchiffré dans dechiffre.txt
bruno@debian:~/Works/langageC/rsa16/projet_rsa16$ cat dechiffre.txt
Bonjour Alice, voila mon message secret !
bruno@debian:~/Works/langageC/rsa16/projet_rsa16$
A vous de jouer
vous pouvez tester avec un autre jeu de clés