Si l’on utilise des cryptosystèmes traditionnels, quiconque en sait assez pour coder un message en sait également assez pour décoder un message intercepté. En 1976, W. Diffie et M. Hellman ont proposé la cryptographie à clé publique, qui repose sur l’observation que les procédures de chiffrement et de déchiffrement n’ont pas besoin d’utiliser la même clé. Cela supprime l’exigence de garder secrète la clé de codage. La fonction de codage
\(f\) doit être relativement facile à calculer, mais
\(f^{-1}\) doit être extrêmement difficile à calculer sans information supplémentaire, de sorte que quelqu’un qui ne connaît que la clé de chiffrement ne peut pas trouver la clé de déchiffrement sans un calcul prohibitif. Il est intéressant de noter qu’à ce jour, aucun système n’a été proposé dont il soit prouvé qu’il est « à sens unique ; » c’est-à-dire que, pour tout cryptosystème à clé publique existant, il n’a jamais été démontré qu’il soit computationnellement prohibitif de décoder des messages avec seulement la connaissance de la clé de codage.
Sous-section 7.2.1 Le cryptosystème RSA
Le cryptosystème
RSA introduit par R. Rivest, A. Shamir, et L. Adleman en 1978, est fondé sur la difficulté de factoriser de grands nombres. Bien que trouver deux grands nombres premiers aléatoires et les multiplier ensemble ne soit pas une tâche difficile, factoriser un nombre de 150 chiffres qui est le produit de deux grands nombres premiers prendrait 100 millions d’ordinateurs fonctionnant à 10 millions d’instructions par seconde environ 50 millions d’années avec les algorithmes les plus rapides disponibles au début des années 1990. Bien que les algorithmes aient progressé, factoriser un nombre qui est le produit de deux grands nombres premiers reste computationnellement prohibitif.
Le cryptosystème
RSA fonctionne comme suit. Supposons que nous choisissions deux nombres premiers aléatoires de 150 chiffres
\(p\) et
\(q\text{.}\) Ensuite, nous calculons le produit
\(n= pq\) et également
\(\phi(n) = m = (p - 1)(q-1)\text{,}\) où
\(\phi\) est la fonction
\(\phi\) d’Euler. Nous choisissons alors des entiers
\(E\) aléatoires jusqu’à en trouver un qui soit premier avec
\(m\) ; c’est-à-dire que nous choisissons
\(E\) tel que
\(\gcd(E, m) = 1\text{.}\) En utilisant l’algorithme d’Euclide, nous pouvons trouver un nombre
\(D\) tel que
\(DE \equiv 1 \pmod{m}\text{.}\) Les nombres
\(n\) et
\(E\) sont ensuite rendus publics.
Supposons maintenant que la personne B (Bob) souhaite envoyer un message à la personne A (Alice) sur une ligne publique. Puisque
\(E\) et
\(n\) sont connus de tous, n’importe qui peut coder des messages. Bob commence par numériser le message selon un schéma convenu, par exemple
\(\text{A} = 00, \text{B} = 02, \ldots, \text{Z}= 25\text{.}\) Si nécessaire, il découpera le message en morceaux de sorte que chaque morceau soit un entier positif inférieur à
\(n\text{.}\) Supposons que
\(x\) est l’un de ces morceaux. Bob forme le nombre
\(y = x^E \mod n\) et envoie
\(y\) à Alice. Pour qu’Alice retrouve
\(x\text{,}\) il lui suffit de calculer
\(x = y^D \bmod n\text{.}\) Seule Alice connaît
\(D\text{.}\)
Exemple 7.2.1.
Avant d’explorer la théorie sous-jacente au cryptosystème
RSA ou de tenter d’utiliser de grands entiers, nous allons utiliser de petits entiers juste pour voir que le système fonctionne bien. Supposons que nous souhaitions envoyer un message qui, une fois numérisé, donne
\(25\text{.}\) Soit
\(p = 23\) et
\(q = 29\text{.}\) Alors
\begin{equation*}
n = pq = 667
\end{equation*}
et
\begin{equation*}
\phi(n) = m = (p - 1)(q - 1) = 616\text{.}
\end{equation*}
Nous pouvons prendre \(E = 487\text{,}\) puisque \(\gcd(616, 487) = 1\text{.}\) Le message codé est calculé comme
\begin{equation*}
25^{487} \bmod 667 = 169\text{.}
\end{equation*}
Ce calcul peut raisonnablement être effectué en utilisant la méthode des carrés répétés décrite dans le
Chapitre 4. En utilisant l’algorithme d’Euclide, nous déterminons que
\(191 E = 1 + 151 m\) ; donc la clé de déchiffrement est
\((n, D) = ( 667, 191)\text{.}\) Nous pouvons retrouver le message original en calculant
\begin{equation*}
169^{191} \bmod 667 = 25\text{.}
\end{equation*}
Examinons maintenant pourquoi le cryptosystème
RSA fonctionne. Nous savons que
\(DE \equiv 1 \pmod{ m}\) ; donc il existe un entier
\(k\) tel que
\begin{equation*}
DE = km + 1 = k \phi(n) + 1\text{.}
\end{equation*}
Il y a deux cas à considérer. Dans le premier cas, supposons que
\(\gcd(x, n) = 1\text{.}\) Alors par le
Théorème 6.3.2,
\begin{equation*}
y^D = (x^E)^D = x^{DE} = x^{km + 1} = (x^{\phi(n)})^k x = (1)^k x = x \bmod n\text{.}
\end{equation*}
Nous voyons donc qu’Alice retrouve le message original \(x\) en calculant \(y^D \bmod n\text{.}\)
Pour l’autre cas, supposons que
\(\gcd(x, n) \neq 1\text{.}\) Puisque
\(n = pq\) et
\(x \lt n\text{,}\) nous savons que
\(x\) est un multiple de
\(p\) ou un multiple de
\(q\text{,}\) mais pas les deux. Nous ne décrirons que la première possibilité, car la seconde est entièrement similaire. Il existe alors un entier
\(r\text{,}\) avec
\(r \lt q\) et
\(x = rp\text{.}\) Notons que
\(\gcd(x, q) = 1\) et que
\(m=\phi(n)=(p - 1)(q - 1)=\phi(p)\phi(q)\text{.}\) Alors, en utilisant le
Théorème 6.3.2, mais maintenant modulo
\(q\text{,}\)
\begin{equation*}
x^{km} = x^{k\phi(p)\phi(q)} = (x^{\phi(q)})^{k\phi(p)} = (1)^{k\phi(p)} = 1 \bmod q\text{.}
\end{equation*}
Donc il existe un entier \(t\) tel que \(x^{km}=1 + tq\text{.}\) Ainsi, Alice retrouve également le message dans ce cas,
\begin{equation*}
y^D = x^{km + 1} = x^{km} x = (1 + tq) x = x + tq(rp) = x + trn = x \bmod n\text{.}
\end{equation*}
Nous pouvons maintenant nous demander comment on pourrait briser le cryptosystème
RSA. Pour trouver
\(D\) à partir de
\(n\) et
\(E\text{,}\) il suffit de factoriser
\(n\) et de résoudre pour
\(D\) en utilisant l’algorithme d’Euclide. Si nous avions su que
\(667 = 23 \cdot 29\) dans l’
Exemple 7.2.1, nous aurions pu retrouver
\(D\text{.}\)
Sous-section 7.2.2 Vérification des messages
Il existe un problème de vérification des messages dans les cryptosystèmes à clé publique. Puisque la clé de codage est publique, n’importe qui a la possibilité d’envoyer un message codé. Si Alice reçoit un message de Bob, elle souhaiterait pouvoir vérifier que c’est bien Bob qui a envoyé le message. Supposons que la clé de chiffrement de Bob soit \((n', E')\) et sa clé de déchiffrement soit \((n', D')\text{.}\) De plus, supposons que la clé de chiffrement d’Alice soit \((n, E)\) et sa clé de déchiffrement \((n, D)\text{.}\) Puisque les clés de chiffrement sont des informations publiques, ils peuvent échanger des messages codés à leur convenance. Bob souhaite assurer à Alice que le message qu’il envoie est authentique. Avant d’envoyer le message \(x\) à Alice, Bob le déchiffre avec sa propre clé :
\begin{equation*}
x' = x ^{D'} \bmod n'\text{.}
\end{equation*}
N’importe qui peut transformer \(x'\) en \(x\) par chiffrement, mais seul Bob est capable de former \(x'\text{.}\) Bob chiffre ensuite \(x'\) avec la clé de chiffrement d’Alice pour former
\begin{equation*}
y' = {x'}^E \bmod n\text{,}
\end{equation*}
un message que seule Alice peut décoder. Alice décode le message puis chiffre le résultat avec la clé de Bob pour lire le message original, un message qui ne pouvait avoir été envoyé que par Bob.
Sous-section 7.2.3 Note historique
Le chiffrement de messages secrets remonte à la Grèce et à Rome antiques. Comme nous le savons, Jules César utilisait un simple code par décalage pour envoyer et recevoir des messages. Cependant, l’étude formelle du codage et du décodage des messages a probablement commencé avec les Arabes au XIV
\(^e\) siècle. Aux XV
\(^e\) et XVI
\(^e\) siècles, des mathématiciens tels qu’Alberti et Viète ont découvert que les cryptosystèmes monoalphabétiques n’offraient pas de véritable sécurité. Au XIX
\(^e\) siècle, F. W. Kasiski établit des méthodes pour briser les chiffres dans lesquels une lettre du texte chiffré peut représenter plus d’une lettre du message en clair, si la même clé était utilisée plusieurs fois. Cette découverte conduisit à l’utilisation de cryptosystèmes avec des clés utilisées une seule fois. La cryptographie fut placée sur des bases mathématiques solides par des personnes telles que W. Friedman et L. Hill au début du XX
\(^e\) siècle.
La période après la Première Guerre mondiale vit le développement de machines spécialisées pour chiffrer et déchiffrer les messages, et les mathématiciens furent très actifs en cryptographie durant la Seconde Guerre mondiale. Les efforts pour percer les cryptosystèmes des nations de l’Axe furent organisés en Angleterre et aux États-Unis par des mathématiciens éminents tels qu’Alan Turing et A. A. Albert. Les Alliés obtinrent un avantage considérable durant la Seconde Guerre mondiale en brisant les chiffres produits par la machine Enigma allemande et les chiffres japonais Purple.
Dans les années 1970, l’intérêt pour la cryptographie commerciale commença à se développer. Un besoin croissant de protéger les transactions bancaires, les données informatiques et le courrier électronique se fit sentir. Au début des années 1970,
IBM développa et mit en œuvre
LUZIFER, le précurseur du Data Encryption Standard (DES) du National Bureau of Standards.
Le concept de cryptosystème à clé publique, dû à Diffie et Hellman, est très récent (1976). Il fut développé ultérieurement par Rivest, Shamir et Adleman avec le cryptosystème
RSA (1978). On ne sait pas dans quelle mesure ces systèmes sont sécurisés. Le cryptosystème à sac à dos avec trappe, développé par Merkle et Hellman, a été brisé. La question de savoir si le système
RSA peut être brisé reste ouverte. En 1991, les laboratoires
RSA ont publié une liste de semi-premiers (nombres ayant exactement deux facteurs premiers) avec une récompense en argent pour quiconque serait capable de fournir une factorisation (
http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm). Bien que le défi ait pris fin en 2007, beaucoup de ces nombres n’ont pas encore été factorisés.
Il y a eu beaucoup de controverse autour de la recherche en cryptographie et de la cryptographie elle-même. En 1929, Henry Stimson, Secrétaire d’État sous Herbert Hoover, dissolut la Chambre Noire (la division de cryptographie du Département d’État) pour des raisons éthiques, affirmant que les « gentlemen ne lisent pas le courrier des autres. » Durant les deux dernières décennies du XX
\(^e\) siècle, la National Security Agency souhaitait garder secrètes les informations sur la cryptographie, tandis que la communauté académique se battait pour le droit de publier des recherches fondamentales. Actuellement, la recherche en cryptographie mathématique et en théorie computationnelle des nombres est très active, et les mathématiciens sont libres de publier leurs résultats dans ces domaines.
