Cryptographie asymétrique

RSA

Kamel Adi

UQO

Kamel Adi (UQO) Cryptographie asymétrique 1 / 15

 RSA

Introduction
RSA : Introduit par Rivest, Shamir et Adleman en 1978.
ë idée : Sous certaines conditions sur des nombres e, d et n, nous avons
pour tout m < n :

med mod n = m

û Exemple : Si e = 3, d = 7 et n = 33 alors ∀ m ∈ {0, . . . , 32} :

m21 mod 33 = m
û Encrypter un message m : ⇒ calculer c = me mod n
û Décrypter un message c : ⇒ calculer c d mod n
c d mod n = (me mod n)d mod n
= med mod n
= m

Kamel Adi (UQO) Cryptographie asymétrique 2 / 15

 RSA

Introduction

Kamel Adi (UQO) Cryptographie asymétrique 3 / 15

 RSA

Génération des clés

1. Choisir deux grands nombres entiers premiers (p, q)

2. Calculer leur produit n = p ∗ q
3. Calculer Φ(n) = (p − 1) ∗ (q − 1)
4. Choisir e tel que : pgcd(e, Φ(n)) = 1 et e < Φ(n)
5. Calculer d tel que e ∗ d ≡ 1 mod Φ(n) (d existe et est unique)
6. Clé privée= (n, d) (les valeurs de p, q et Φ(n) sont gardées secrètes)
7. Clé publique= (n, e)

Kamel Adi (UQO) Cryptographie asymétrique 4 / 15

 RSA

Cryptage/Décryptage

ë Cryptage : Pour chiffrer un message et l’envoyer à Bob, Alice a besoin

d’avoir le message en clair m et la clé publique (eb , nb ) de Bob.

• 0 ≤ m < n, le message en clair

• Le message chiffré est : ekpb (m) = c = meb mod nb

ë Décryptage : Bob a besoin d’avoir le message chiffré c et sa clé privée

(db , nb ) (correspondant à celle utilisée pour le chiffrement)

• 0 ≤ c < n, le message crypté

• Le message original est dkpr (c) = m = c db mod nb

Kamel Adi (UQO) Cryptographie asymétrique 5 / 15

 RSA

Signature
ë Signature : Pour signer un message, Alice a besoin d’avoir le message
en clair m et sa clé privée (da , na )

• 0 ≤ m < n, le message à signer

• Le message signé est : ekpr (m) = sig = mda mod na

ë Vérification de la signature : Pour vérifier un message signé par Alice,

Bob a besoin d’avoir le message m, sa signature sig et la clé publique
(ea , na ) de Alice (celle correspondant à la clé privée utilisée pour la
signature).

• Est ce que sig est le message m signé par kpr ?

• La réponse est oui ssi : m = sig ea mod na

Kamel Adi (UQO) Cryptographie asymétrique 6 / 15

 RSA

Exemple

ë Alice veut envoyer à Bob le message m = 4

Alice Bob
(1) p = 3, q = 11
(2) n = p ∗ q = 33
(3)Φ(n) = (3 − 1) ∗ (11 − 1) = 20
(4)e = 3, pgcd(3, 20) = 1
m=4 kpb = (3, 33) ←− (5)d = e −1 = 7 mod 20
c = me mod 33
m = c d mod 33
= 43 mod 33
−→ c = 31 = 317 mod 33
= 64 mod 33
= 4
= 31

Kamel Adi (UQO) Cryptographie asymétrique 7 / 15

 RSA

Exemple
ë Alice veut envoyer à Bob le message m = 688232687966668
Alice Bob
(1) p = 47, q = 71
(2) n = p ∗ q = 3337
(3)Φ(n) = (47 − 1) ∗ (71 − 1) = 3220
(4)e = 79, pgcd(79, 3220) = 1
m = 688232687966668 kpb = (79, 3337) ←− (5)d = e −1 = 1019 mod 3220
=⇒ découpage
m1 = 688; m2 = 232;
m3 = 687; m4 = 966;
m5 = 668
c1 = 68879 mod 3337 = 1570
c2 2 = 23279 mod 3337 = 2756;
c3 = 68779 mod 3337 = 2091;
c4 = 96679 mod 3337 = 2276;
c5 = 66879 mod 3337 = 2423 −→ c1 c2 c3 c4 c5 m1 = 15701019 mod 3337 = 668
m2 = 27561019 mod 3337 = 232
m3 = 20911019 mod 3337 = 687
m4 = 22761019 mod 3337 = 966
m5 = 24231019 mod 3337 = 668
m = m1 m2 m3 m4 m5
= 688232687966668

Kamel Adi (UQO) Cryptographie asymétrique 8 / 15

 RSA

Pourquoi RSA marche

I Pour que RSA fonctionne, il faut que pour tout 0 ≤ m ≤ n − 1 :

dkpr (ekpb (m)) = m

I Or
dkpr (ekpb (m)) = (md mod n)e mod n
= (md∗e mod n) mod n
= md∗e mod n
I Donc, pour que RSA fonctionne, il suffit que :

md∗e mod n = m mod n

I Puisque d ∗ e = 1 mod Φ(n), donc il existe un entier k tel que :

d ∗ e = 1 + k ∗ Φ(n)

Kamel Adi (UQO) Cryptographie asymétrique 9 / 15

 RSA

Pourquoi RSA marche

I On déduit que pour que RSA fonctionne, il suffit que :

m1+k∗Φ(n) mod n = m mod n

I Pour atteindre cet objectif, il suffit de démontrer que :

mΦ(n) mod n = 1 mod n

I Définition (Totient d’Euler) : Φ(n) = nombre d’entiers positifs dans

{1, . . . , n − 1} et relativement premiers avec n.
Pour n premier, Φ(n) = n − 1
Pour p et q premiers (p 6= q), n = p ∗ q et Φ(n) = Φ(p) ∗ Φ(q) =
(p − 1) ∗ (q − 1)
I Théorème (Euler) : Si m et n sont relativement premiers alors

mΦ(n) ≡ 1 mod n

Kamel Adi (UQO) Cryptographie asymétrique 10 / 15

 RSA

Pourquoi RSA marche

û Question : Quoi faire si m et n ne sont pas relativement premiers ?

û Réponse : Le théorème d’Euler tient encore pour n = p ∗ q.
û Preuve : p et q sont premiers
Supposant que : pgcd(m, n) = pgcd(m, p ∗ q) 6= 1
Donc pgcd(m, n) = p ou pgcd(m, n) = q (car m < n)
Donc il existe un entier r < p, r < q tel que :

(m = r ∗ p) ou (m = r ∗ q)

Supposons que m = r ∗ p (la preuve sera similaire pour le cas où m =

r ∗ q), dans ce cas on a :

pgcd(m, q) = 1 (autrement p et q auront un diviseur commun)

Kamel Adi (UQO) Cryptographie asymétrique 11 / 15

 RSA

Pourquoi RSA marche

û Preuve (suite) :
Puisque pgcd(m, q) = 1, donc d’après le théorème d’Euler, on aura :

mΦ(n) = m(p−1)(q−1) = (mΦ(q) )(p−1) = 1 mod q

On déduit qu’il existe un entier k tel que :

mΦ(n) = 1 + k ∗ q

Puisque m = r ∗ p, on déduit que :

m∗mΦ(n) = m∗(1+k∗q) = m+m∗k∗q = m+r ∗p∗k∗q = m+r ∗k∗n ≡ m m

On conclut que :
mΦ(n) ≡ 1 mod n

Kamel Adi (UQO) Cryptographie asymétrique 12 / 15

 RSA

RSA en pratique

û Comment trouver deux grands nombres premiers p et q ?

Test probabiliste de primalité

û Comment trouver e premier avec Φ(n) ?

Algorithme d’Euclide

û Comment déterminer d à partir de e ?

Algorithme d’Euclide étendu

û Comment effectuer les gros calculs x k mod n ?

Algorithmes d’exponentiation

Kamel Adi (UQO) Cryptographie asymétrique 13 / 15

 RSA

Sécurité de RSA

û Attaquer RSA revient à :

Trouver x tel que x e = a mod n (e, a et n sont connus).
Factoriser un nombre assez grand : Trouver deux nombres premiers p et
q tels que p ∗ q = n (n est connu).
û Les meilleurs algorithmes connus pour résoudre ces problèmes ne sont
pas polynomiaux.
1
û Meilleure algorithme de factorisation est de l’ordre exp(4|n| 3 ) avec |n|
le nombre de bits dans n
û Il se peut que quelqu’un connaisse un algorithme très efficace pour fac-
toriser des nombres entiers et qu’il le garde secret ! Pour cette personne
ou groupe de personnes RSA n’est pas de tout sécuritaire.
û Il se peut bien aussi que les lois des mathématique interdisent la
résolution de ce problème en un temps raisonnable.

Kamel Adi (UQO) Cryptographie asymétrique 14 / 15

 RSA

Sécurité de RSA
û Compétition de factorisation RSA (1991-2007) :

source : https ://[Link]/wiki/Compétition de factorisation RSA

RSA-768 = 1 230 186 684 530 117 755 130 494 958 384 962 720 772 853 569 595 334 792 197 322 452 151 726 400

507 263 657 518 745 202 199 786 469 389 956 474 942 774 063 845 925 192 557 326 303 453 731 548 268 507 917 026

122 142 913 461 670 429 214 311 602 221 240 479 274 737 794 080 665 351 419 597 459 856 902 143 413

RSA-768 = 33 478 071 698 956 898 786 044 169 848 212 690 817 704 794 983 713 768 568 912 431 388 982 883 793

878 002 287 614 711 652 531 743 087 737 814 467 999 489 x 36 746 043 666 799 590 428 244 633 799 627 952 632

279 158 164 343 087 642 676 032 283 815 739 666 511 279 233 373 417 143 396 810 270 092 798 736 308 917

Kamel Adi (UQO) Cryptographie asymétrique 15 / 15