🔐 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

    TermeSignification
    a ≡ b mod  na et b laissent le même reste modulo n
    Même reste⇒ congruence
    Base des maths modulairescryptographie, 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