🔐 Paramètres RSA (exemple pédagogique)

Initiales de : Rivest, Shamir et Adleman les découvreurs de ce chiffrement

Supposons que nous avons :

• p = 17, q = 19 → deux petits nombres premiers, volontairement pour des raisons pédagogique
• n = p × q = 17 × 19 = 323
• φ(n) = (p−1)(q−1) = 16 × 18 = 288
• e = 7 (choisi tel que gcd(e, φ) = 1)
• d = 247 (car 7 × 247 ≡ 1 mod 288 → inverse modulaire de 7 mod 288)

✉️ Message à chiffrer : 'A'

• Code ASCII de 'A' = 65
• On veut chiffrer ce nombre avec la clé publique (e = 7, n = 323)

🔒 Chiffrement

Formule : C=Memod  nC = M^e \mod nC=Memodn C=657mod  323C = 65^7 \mod 323C=657mod323

Faisons les puissances successives (modulo 323) :

1. 652=4225mod  323=4225−13×323=4225−4199=2665^2 = 4225 \mod 323 = 4225 – 13×323 = 4225 – 4199 = 26652=4225mod323=4225−13×323=4225−4199=26
2. 654=(652)2=262=676mod  323=676−2×323=676−646=3065^4 = (65^2)^2 = 26^2 = 676 \mod 323 = 676 – 2×323 = 676 – 646 = 30654=(652)2=262=676mod323=676−2×323=676−646=30
3. 657=65×652×654=65×26×3065^7 = 65 × 65^2 × 65^4 = 65 × 26 × 30657=65×652×654=65×26×30

Calcul :

• 26×30=78026 × 30 = 78026×30=780
• 780×65=50700780 × 65 = 50700780×65=50700
• 50700mod  323=50700−157×323=50700−50711=−11≡312mod  32350700 \mod 323 = 50700 – 157×323 = 50700 – 50711 = -11 ≡ 312 \mod 32350700mod323=50700−157×323=50700−50711=−11≡312mod323

🔐 Message chiffré = 312

🔓 Déchiffrement

Formule : M=Cdmod  n=312247mod  323M = C^d \mod n = 312^{247} \mod 323M=Cdmodn=312247mod323

C’est long à faire à la main, mais en pratique on utiliserait l’exponentiation rapide ou un programme. Si on le fait (ou vérifie) à la machine : 312247mod  323=65312^{247} \mod 323 = 65312247mod323=65

✔️ On retrouve bien le message original !

chiffrement pourquoi ?

Pourquoi c’est un chiffrement, concrètement ?

1. Transforme le message (texte clair) en un code incompréhensible (texte chiffré)
   Ici, on transforme le nombre M = 65 en C = 312. Sans la clé privée, 312 ne veut rien dire.
2. Reversible seulement avec la clé privée
   Le déchiffrement utilise la clé privée d pour inverser l’opération et retrouver le message initial M.
3. Basé sur un problème mathématique difficile
   Le chiffrement RSA repose sur la difficulté de factoriser n (ici 323) en ses facteurs premiers (p et q).
   • Si tu ne connais pas p et q, il est extrêmement compliqué (pour des grands nombres) de calculer d et donc de déchiffrer.
   • Sans d, tu ne peux pas récupérer le message clair.
4. Fonction mathématique asymétrique
   • Clé publique e permet de chiffrer.
   • Clé privée d permet de déchiffrer.
     Chiffrer avec e est facile, mais sans d, inverser la fonction est « facile à faire dans un sens, difficile dans l’autre ».

---

En résumé :

• Tu passes du message clair (M) au message chiffré (C) grâce à la clé publique.
• Seule la clé privée peut transformer C en M.
• Sans la clé privée, même en connaissant C et la clé publique, tu ne peux pas retrouver M (au moins pour des grands nombres).
• Le message chiffré est un secret codé que personne d’autre ne peut lire.

Théorie

On va volontairement travailler sur 16 bits pour comprendre le principe!

✅ Concepts RSA simplifiés :

1. Choisir deux petits nombres premiers p et q.
2. Calculer n = p * q.
3. Calculer φ(n) = (p-1) * (q-1).
4. Choisir un exposant e tel que 1 < e < φ(n) et e est premier avec φ(n).
5. Calculer d, l’inverse modulaire de e modulo φ(n).

• Clé publique : (e, n)
• Clé privée : (d, n)
• Chiffrement : c = m^e mod n
• Déchiffrement : m = c^d mod n

Clé privée / public 16 bits

// genrsa16.c : Génère une paire de clés RSA 16 bits
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <math.h>

bool est_premier(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; i <= sqrt(n); i += 2)
        if (n % i == 0) return false;
    return true;
}

int pgcd(int a, int b) {
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

// Inverse modulaire : retourne d tel que (d * e) % phi == 1
int mod_inverse(int e, int phi) {
    int t = 0, newt = 1;
    int r = phi, newr = e;
    while (newr != 0) {
        int quotient = r / newr;
        int tmp = newt;
        newt = t - quotient * newt;
        t = tmp;

        tmp = newr;
        newr = r - quotient * newr;
        r = tmp;
    }
    if (r > 1) return -1; // Pas d'inverse
    if (t < 0) t += phi;
    return t;
}

int main() {
    srand(time(NULL));
    int p, q;
    do {
        p = rand() % 256;
    } while (!est_premier(p));
    do {
        q = rand() % 256;
    } while (!est_premier(q) || q == p);

    int n = p * q;
    int phi = (p - 1) * (q - 1);

    int e;
    do {
        e = rand() % phi;
    } while (pgcd(e, phi) != 1 || e <= 1);

    int d = mod_inverse(e, phi);

    printf("Clé publique (e, n) : (%d, %d)\n", e, n);
    printf("Clé privée  (d, n) : (%d, %d)\n", d, n);
    printf("p = %d, q = %d, φ(n) = %d\n", p, q, phi);

    return 0;
}

bruno@debian:~/Works/langageC/rsa16$ ./genrsa16 
Clé publique (e, n) : (6107, 10823)
Clé privée  (d, n) : (5555, 10823)
p = 79, q = 137, φ(n) = 10608

p = 79, q = 137

n = 79 × 137 = 10823

φ(n) = (p-1)×(q-1) = 78 × 136 = 10608

Clé publique : (e = 6107, n = 10823)

Clé privée : (d = 5555, n = 10823)

Concepts Mathématiques utilisés

modulo (mod)

on a besoin de mod , qui est simplement le reste .

17/5= 3 et il reste 2

donc 17 mod 5 = 2

La congruence

on a besoin de la congruence.

ce symbole ≡ « congruent »

a≡b mod n

Terme	Signification
a ≡ b mod  n	a et b laissent le même reste modulo n
Même reste	⇒ congruence
Base des maths modulaires	cryptographie, informatique

Exemple de code C pour savoir si a et congru a b modulo n

congrus.c

#include <stdio.h>
#include <stdlib.h>

// Fonction qui teste si a ≡ b mod n
int est_congru(int a, int b, int n) {
    return ((a - b) % n == 0);
}

int main() {
    int a, b, n;

    printf("Entrez a : ");
    scanf("%d", &a);

    printf("Entrez b : ");
    scanf("%d", &b);

    printf("Entrez le modulo n : ");
    scanf("%d", &n);

    if (est_congru(a, b, n)) {
        printf("%d et %d sont congrus modulo %d : %d ≡ %d mod %d\n", a, b, n, a, b, n);
    } else {
        printf("%d et %d ne sont pas congrus modulo %d\n", a, b, n);
    }

    return EXIT_SUCCESS;
}

bruno@debian:~/Works/langageC/congruent$ ./congrus 
Entrez a : 17
Entrez b : 2
Entrez le modulo n : 5
17 et 2 sont congrus modulo 5 : 17 ≡ 2 mod 5

Génération :
p, q → choisis aléatoirement (premiers)
n = p × q
φ(n) = (p – 1) × (q – 1) , la fonction d’euler
e = exposant public, tel que gcd(e, φ(n)) = 1
d = inverse modulaire de e mod φ(n)

Clés :
Publique = (e, n)
Privée = (d, n)

exemple:

p = 17 et q = 11

n = p × q = 17 × 11 = 187

φ(n) = (p – 1) × (q – 1) = 16 × 10 = 160

✅ Choix de e (exposant public)

On veut 1 < e < φ(n) et gcd(e, φ(n)) = 1.

Prenons par exemple e = 7.

✔ Vérification :

gcd(7, 160) = 1 → OK

✅ Calcul de d (exposant privé)

On cherche d tel que :

d × e ≡ 1 mod 160
d × 7 ≡ 1 mod 160

On résout cette équation avec l’inverse modulaire.

🧮 Résultat (via l’algorithme d’Euclide étendu) :

d = 23 (car 23 × 7 = 161 ≡ 1 mod 160)

✅ Résumé des clés

Clé	Valeur
Publique	(e = 7, n = 187)
Privée	(d = 23, n = 187)

Exemple avec Alice et Bob

Imaginons que Bob veut envoyer le nombre 88 à Alice.

Chiffrement (Bob utilise la clé publique (7, 187))

luaCopierModifier

c = m^e mod n
  = 88^7 mod 187

88^7 = 33232930569601
33232930569601 mod 187 = 11

🔒 Message chiffré : c = 11

🔓 Déchiffrement (Alice utilise sa clé privée (23, 187))

m = c^d mod n = 11^23 mod 187

11^23 mod 187 = 88

✅ Message d’origine retrouvé : m = 88

📌 Conclusion

• p = 17, q = 11
• n = 187, φ(n) = 160
• e = 7, d = 23
• Message original : 88
• Message chiffré : 11
• Message déchiffré : 88

rsa_demo.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

// Fonction d'exponentiation modulaire rapide : (base^exp) % mod
long long modexp(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1)  // exp impair
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main(void) {
    // Clés RSA fixes pour démonstration
    long long p = 17;
    long long q = 11;
    long long n = p * q;               // n = 187
    long long phi = (p - 1) * (q - 1); // phi = 160
    long long e = 7;                   // clé publique
    long long d = 23;                  // clé privée

    printf("Clé publique  (e = %lld, n = %lld)\n", e, n);
    printf("Clé privée    (d = %lld, n = %lld)\n\n", d, n);

    // Message clair à chiffrer
    long long message;
    printf("Entrez un message (entier < %lld) à chiffrer : ", n);
    if (scanf("%lld", &message) != 1 || message <= 0 || message >= n) {
        fprintf(stderr, "Entrée invalide. Le message doit être un entier entre 1 et %lld.\n", n - 1);
        return EXIT_FAILURE;
    }

    // Chiffrement
    long long chiffre = modexp(message, e, n);
    printf("\nMessage chiffré : %lld\n", chiffre);

    // Déchiffrement
    long long dechiffre = modexp(chiffre, d, n);
    printf("Message déchiffré : %lld\n", dechiffre);

    return EXIT_SUCCESS;
}

Entrez un message (entier < 187) à chiffrer : 88

Message chiffré : 11
Message déchiffré : 88