La cryptographie RSA – Qu'est-ce que c'est ? – Le principe

View Github Repository Open presentation in a new window

Floatshow

See all presentation from Floatshow

La cryptographie RSA – Qu'est-ce que c'est ? – Le principe

0 0

cryptoparty-rsa-slides

On Github Floatshow / cryptoparty-rsa-slides

La cryptographie RSA

Qu'est-ce que c'est ?

Présentation par Théo Piboubès / @TheoPib

Le principe

RSA est un algorithme de cryptographie asymétrique, aussi dit à clé publique.Il repose sur l'utilisation d'une clé publique, et d'une clé privée.

« En 2 étapes »

Pour crypter : utilisation de la clé publique (diffusée)

Pour décrypter : utilisation de la clé privée (gardée secrète).

Clé publique, contrairement aux algorithmes symétriques, dits à clé privée/secrète

Création des clés

Étapes

Exemple

Étape 1 : choisir deux nombres premiers distincts p et q

p=31, q=73

Étape 2 : calculer leur produit n=p×q

n=31×73=2263

Étape 3 : calculer ϕ(n)=(p−1)×(q−1)

ϕ(n)=(31−1)×(73−1)=2160

Étape 4 : choisir un entier e premier avec ϕ(n)

e=29

Étape 5 : calculer l'entier d≡e−1[ϕ(n)]

d=149

Clé publique : (2263, 29)

Clé privée : (2263, 149)

ϕ(n) = valeur de l'indicatrice d'Euler en n : nombre d'entiers naturels <=n qui lui sont premierse : exposant de chiffrement (e doit être inférieur à ϕ(n) !d : exposant de déchiffrement, déterminé à partir de l'algorithme d'Euclide étendu.

Crypter

On va crypter cette phrase :

« Cryptoparty IUT Blagnac »

Comme RSA ne fonctionne qu'avec des nombres, on "pré-encode" le message avec la table ASCII.

Caractère C r y p t o p a r t y I U T B l a g n a c ASCII 0067 0114 0121 0112 0116 0111 0112 0097 0114 0116 0121 0032 0073 0085 0084 0032 0066 0108 0097 0103 0110 0097 0099

On applique ensuite la fonction de cryptage : C≡Me[n]

Crypter : application

C r y p t o p a r t y I U T B l a g n a c x=1 0067 0114 0121 0112 0116 0111 0112 0097 0114 0116 0121 0032 0073 0085 0084 0032 0066 0108 0097 0103 0110 0097 0099 x=2 2226 1681 1063 1229 2141 1006 1229 0357 1681 2141 1063 1024 0803 0436 0267 1024 2093 0349 0357 1557 0785 0357 0749 x=3 2047 1542 1895 1868 1689 0779 1868 0684 1542 1689 1895 1086 2044 0852 2061 1086 0095 1484 0684 1961 0356 0684 1735 ... ... x=e=29 0707 1677 2056 0483 0678 0298 0483 1682 1677 0678 2056 1024 0730 0895 0396 1024 1589 0432 1682 1950 2026 1682 0336 C 07071677205604830678029804831682167706782056102407300895039610241589043216821950202616820336

Message crypté :

07071677205604830678029804831682167706782056102407300895039610241589043216821950202616820336

Décrypter

Pour décrypter, on applique la fonction de décryptage, c'est-à-dire la fonction inverse de la fonction de cryptage :

D≡Cd[n]≡(Me)d[n]≡M[n]

(M^e)^d ≡ M car ed ≡ 1 [φ(n)]

Décrypter : application

C 07071677205604830678029804831682167706782056102407300895039610241589043216821950202616820336 x=1 0707 1677 2056 0483 0678 0298 0483 1682 1677 0678 2056 1024 0730 0895 0396 1024 1589 0432 1682 1950 2026 1682 0336 x=2 1989 1683 2115 0200 0295 0547 0200 0374 1683 0295 2115 0807 1095 2186 0669 0807 1676 1058 0374 0660 1857 0374 2009 x=3 0900 0430 1217 1554 0866 0070 1554 2217 0430 0866 1217 0373 0511 1238 0153 0373 1876 2193 2217 1616 1176 2217 0650 ... ... x=d=149 0067 0114 0121 0112 0116 0111 0112 0097 0114 0116 0121 0032 0073 0085 0084 0032 0066 0108 0097 0103 0110 0097 0099 D 67 114 121 112 116 111 112 97 114 116 121 32 73 85 84 32 66 108 97 103 110 97 99 M C r y p t o p a r t y I U T B l a g n a c

Message décrypté :

Cryptoparty IUT Blagnac

Quelques infos pratiques...

En pratique, on utilise des facteurs p et q très grands :d'une taille d'au moins 100 chiffres chacun pour une bonne sécurité
RSA coûteux en ressources et en temps :peu viable pour crypter de grandes quantités de données
On préfère alors crypter les données à l'aide d'un algorithme symétrique (AES par exemple)et utiliser le RSA pour crypter la clé symétrique.
Quelques 3×1080 années nécessaires pour retrouver la clé privée (n,d)
Le RSA est utilisé par OpenPGP
Le RSA fait partie d'une "famille" de chiffrement, mais il en existe principalement trois :
  • Factorisation de grands nombres premiers : RSA
  • Logarithme discret : échange de clés Diffie-Hellman, chiffrement El-Gamal (PGP/GPG, DSA)
  • Courbes elliptiques : ECC
AES est considéré comme suffisament sûr aujourd'hui pour garder des données secrètes. A noter que le niveau de sécurité est proportionnel à la longueur (en bits) de la clé.