Cryptographie asymétrique
La cryptographie asymétrique, aussi appelée cryptographie à clef publique, permet de chiffrer et déchiffrer un message en utilisant deux clefs différentes :
- la clef publique : clef partagée qui sert à chiffrer un message dont on est sûr que seul le détenteur de la clef privée sera capable de déchiffrer
- la clef privée : clef qui sert à déchiffrer un message chiffré avec la clef publique
Dans cet article, je vous propose de découvrir les bases mathématiques qui se cachent derrière les algorithmes de cryptographie asymétriques utilisés aujourd’hui.
Dans cette première partie nous étudierons l’algorithme RSA qui se base sur le problème de factorisation d’un entier en nombres premiers.
Les entiers relatifs
L’ensemble des entiers naturels est l’ensemble mathématique le plus simple qui existe puisqu’il se compose des nombres :
\(1, 2, 3, …, 10, 11, … \)
Sur cet ensemble de nombre, on peut réaliser un certain nombre d’opération comme l’addition, la soustraction, etc. Mais l’opération qui nous intéresse le plus dans le cas de la cryptographie est la division euclidienne.
Division Euclidienne
La division Euclidienne est l’opération qui pour deux entiers (\(a\) et \(b\)) associe deux autres entiers : le quotient (\(q\)) et le reste (\(r\)) tel que :
\(a=b*q+r, r<q\)
Par exemple :
$$10\div 3 \text{ donne } 10=3*3+1$$
Propriétés
De cette opération, on peut définir un certain nombre de propriété sur les entiers :
- La divisibilité : un entier \(a\) et divisible par un entier \(b\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul.
Il existe alors un entier k tel que :
$$ a= k*b $$
Par exemple 6 est divisible par 2 et 3. (Mais aussi 1 et 6)
- Le PGCD : le plus grand diviseur commun entre deux entiers naturels est le plus grand entier qui les divise.
Par exemple 10 et 30 ont pour diviseurs communs : 1, 2, 5 et 10. Donc 10 est leur PGCD.
- Un nombre premier : un entier qui n’est divisible que par 1 et lui-même
Par exemple : \(2,3,5,7,11,13,17, …\)
- La factorisation en facteurs premiers : tout entier naturel positif admet une décomposition unique en facteurs premiers.
C’est à dire :
$$ n=\Pi_{i=0}^{n}p_i^{k_i}$$
Avec les \(p_i\), des nombres premiers.
Par exemple : $$147=3*7*7 \\861=3*7*41 \\ 25=5*5$$
- La congruence : deux entier sont congrus modulo \(n\) si leur différence est divisible par \(n\)
C’est à dire : $$a=b+kn$$
On note alors : $$a \equiv b \mod{n}$$
Par exemple : $$26 \equiv 12 \mod{7}$$ Car : $$26-12=14=2*7$$
- L’inverse modulaire : l’inverse modulaire modulo \(n\) d’un entier \(a\) est l’entier \(a^{-1}\) tel que :$$a*a^{-1}=1\mod{n}$$
L’inverse modulaire se calcule grâce à l’algorithme d’Euclide étendu :
- On commence par chercher le PGCD de \(a\) et \(n\)
- On étend l’algorithme
Par exemple : l’inverse modulaire de 66 modulo 17.
Pour commencer : \(66=15\mod{17}\)
On applique l’algorithme d’Euclide pour trouver le PGCD (faire des divisions euclidienne successives jusqu’à ce que le reste soit 1) : \(17=15*1+2 \\ 15=2*7+1\)
Puis on étend l’algorithme : \(1=15-2*7\\1=15-7*(17-15)\\1=15*(1+7)-7*17\\1=15*8-17*7\)
On en déduit :
$$15*8=1\mod{17}$$
RSA
Le chiffrement RSA pour Rivest, Shamir et Adleman est basé sur le problème de factorisation d’entiers par deux nombres premiers.
Le chiffrement se base sur le calcul de \(n=p*q\), avec \(p\) et \(q\) deux nombres premiers très grands. Le calcul de \(n\) se fait simplement, mais il est difficile de retrouver \(p\) et \(q\) uniquement à partir de \(n\).
Pour générer une paire de clef RSA il faut :
- Générer deux nombres premiers \(p\) et \(q\)
- Calculer \(n=p*q\)
- Choisir un entier \(e\) premier avec \(\Phi(n)=(p-1)(q-1)\)
- Calculer \(d\) l’inverse de \(e\) modulo \(\Phi(n)\)
La clef publique est alors : \((n,e)\)
La clef privée est : \((p,q,d)\)
L’opération de chiffrement d’un message m : $$E_K : m \rightarrow c=m^e\mod{n}$$
L’opération de déchiffrement : $$E_K^{-1}:c\rightarrow m = c^d \mod{n}$$
Exemple d’utilisation
Un notebook Jupyter contenant les différents algorithmes utilisés se trouve dans : https://github.com/ArthyD/BlogRessources/blob/main/Cryptographie/rsa.ipynb
On commence par générer la paire de clef :