%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Cryptographie/Cryptographie|Accueil · Cryptographie]]
>
> | [[Code et Développement/Programmation/Cryptographie/04_Le chiffre de Vigenère\|← Le chiffre de Vigenère]] | [[Code et Développement/Programmation/Cryptographie/06_Tables de hachage\|Tables de hachage →]] |
> |:---|---:|
%% nav-fin %%
# Algorithme RSA
## Le chiffrement asymétrique
Les chiffrements des pages précédentes sont **symétriques** : la même clé sert à chiffrer et à déchiffrer.
Un chiffrement **asymétrique** utilise deux clés différentes.
La **clé publique** sert à chiffrer.
La **clé privée** sert à déchiffrer.
Le propriétaire diffuse sa clé publique à tous.
Seul le détenteur de la clé privée peut lire les messages chiffrés avec la clé publique.
RSA porte les initiales de ses inventeurs : Rivest, Shamir et Adleman.
Il est utilisé dans de nombreux protocoles de sécurité d'Internet.
## Le principe mathématique
On choisit deux nombres premiers P et Q, puis on calcule N = P × Q.
N fait partie des deux clés.
La clé privée se calcule à partir de P et de Q.
Retrouver P et Q à partir de N demande de factoriser N.
Quand P et Q sont très grands, plusieurs centaines de chiffres, aucun ordinateur ne réalise cette factorisation en un temps raisonnable.
La sécurité de RSA repose sur cette difficulté.
## Construire les clés
```python
P = 13
Q = 19
N = P * Q # 247
R = (P - 1) * (Q - 1) # 216
```
On choisit E, compris entre 2 et R − 1, sans facteur commun avec R.
Autrement dit, le plus grand commun diviseur de E et de R vaut 1.
```python
from math import gcd
E = 11
print(gcd(E, R)) # 1 : E convient
```
La clé publique est le couple (E, N) = (11, 247).
On cherche ensuite D tel que le reste de E × D par R vaut 1.
D est l'**inverse modulaire** de E modulo R.
```python
D = 1
while (D * E) % R != 1:
D += 1
print(D) # 59, car 59 × 11 = 649 = 3 × 216 + 1
```
La clé privée est le couple (D, N) = (59, 247).
## Chiffrer et déchiffrer
Chaque lettre est d'abord codée par un nombre M : a vaut 1, b vaut 2, … z vaut 26.
Tout autre caractère vaut 0.
```python
from string import ascii_lowercase
lower = ascii_lowercase
def nombre(c):
"""Renvoie le nombre associé à la lettre c, ou 0."""
if c in lower:
return lower.index(c) + 1
return 0
def lettre(n):
"""Renvoie la lettre associée au nombre n, ou une espace pour 0."""
if n > 0:
return lower[n - 1]
return ' '
```
Pour chiffrer M avec la clé publique (E, N), on calcule C = M^E mod N.
Pour déchiffrer C avec la clé privée (D, N), on calcule C^D mod N, qui redonne M.
```python
def chiffrer_rsa(x, cle_publique):
E, N = cle_publique
return [pow(nombre(c), E, N) for c in x]
def dechiffrer_rsa(liste, cle_privee):
D, N = cle_privee
return ''.join(lettre(pow(C, D, N)) for C in liste)
C = chiffrer_rsa('bonjour', (11, 247))
print(C) # [72, 98, 222, 147, 98, 148, 151]
print(dechiffrer_rsa(C, (59, 247))) # bonjour
```
La fonction `pow(m, e, n)` calcule la puissance modulo n sans calculer d'abord m^e en entier.
Cette méthode reste rapide avec les très grands nombres utilisés en pratique.
L'algorithme repose sur l'égalité (M^E mod N)^D mod N = M, démontrée en arithmétique.
**À manipuler :** modifiez P, Q, E ou le message. Le composant vérifie que P et Q sont premiers et que E n'a aucun facteur commun avec R.
```sq-rsa
p: 13
q: 19
e: 11
message: bonjour
```
## Les limites de cet exemple
Le chiffrement lettre par lettre fait correspondre une même lettre à un même nombre : les deux o de « bonjour » donnent deux fois 98.
Il reste donc exposé à l'analyse de fréquences.
En pratique, RSA chiffre de grands blocs de données, avec des nombres premiers de plusieurs centaines de chiffres.
Les majuscules et la ponctuation valent 0 et redeviennent des espaces au déchiffrement.
```sq-quiz
? Quelle clé faut-il connaître pour déchiffrer un message chiffré avec la clé publique (E, N) ?
- [ ] La clé publique (E, N)
- [x] La clé privée (D, N)
- [ ] Le couple (P, Q) seulement
> Le message se déchiffre par C^D mod N. D se calcule à partir de P et Q, que seul le propriétaire connaît.
? Pourquoi publier N ne permet-il pas de retrouver la clé privée ?
- [ ] N ne contient aucune information sur P et Q
- [x] Factoriser un très grand N en P × Q prend un temps démesuré
- [ ] La clé privée ne dépend pas de N
> En théorie, la factorisation de N donne P et Q, donc R et D. En pratique, elle est hors de portée quand P et Q sont très grands.
```
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Cryptographie/Cryptographie|Accueil · Cryptographie]]
>
> | [[Code et Développement/Programmation/Cryptographie/04_Le chiffre de Vigenère\|← Le chiffre de Vigenère]] | [[Code et Développement/Programmation/Cryptographie/06_Tables de hachage\|Tables de hachage →]] |
> |:---|---:|
%% nav-fin %%