Arithmétique et cryptographie

Pourquoi de l'arithmétique au XXI^e siècle

L'objection est naturelle : on dispose des réels, des complexes, des vecteurs, pourquoi revenir aux entiers ?

Divisibilité et division euclidienne

L'unicité du couple $(q, r)$ est ce qui rend tout le reste possible. En Python, a // b donne $q$ et a % b donne $r$ : ce sont les opérateurs de division entière et de reste du parcours Python.

PGCD et algorithme d'Euclide

Le pgcd est le plus grand entier divisant $a$ et $b$ ; le ppcm le plus petit multiple commun positif. Ils sont liés par $\operatorname{pgcd}(a, b) \times \operatorname{ppcm}(a, b) = |ab|$.

Deux entiers sont premiers entre eux si leur pgcd vaut 1. Ce n'est pas la même chose qu'être premiers : 8 et 9 sont premiers entre eux, et aucun des deux n'est premier.

Cette observation se démontre en trois lignes, et il vaut la peine de les suivre : sans elle, l'algorithme n'est qu'une recette.

Le point de départ est la division euclidienne $a = bq + r$, récrite $r = a - bq$.

Soit $d$ un diviseur commun à $a$ et à $b$. Il divise alors $a - bq$, c'est-à-dire $r$ : tout diviseur commun de $a$ et $b$ est aussi un diviseur commun de $b$ et $r$.

Réciproquement, soit $d$ un diviseur commun à $b$ et à $r$. Il divise $bq + r$, c'est-à-dire $a$ : tout diviseur commun de $b$ et $r$ est aussi un diviseur commun de $a$ et $b$.

Les deux couples ont donc exactement les mêmes diviseurs communs, et en particulier le même plus grand. Remplacer $(a, b)$ par $(b, r)$ ne perd rien, et fait strictement décroître le second terme : c'est ce qui garantit à la fois la justesse et la terminaison.

C'est un des plus vieux algorithmes connus, et il reste remarquablement rapide : le nombre de divisions est en $O(\log(\min(a, b)))$, c'est-à-dire proportionnel au nombre de chiffres. La notation est celle de l'analyse d'algorithmes, abordée dans le parcours Algorithmique. Sur des nombres de 600 chiffres, l'algorithme pose un peu plus d'un millier de divisions et termine en une fraction de milliseconde.

Euclide étendu et Bézout

L'algorithme d'Euclide étendu calcule ce couple $(u, v)$ en même temps que le pgcd. Ce n'est pas une curiosité théorique : c'est exactement ce qui permettra de calculer une clé privée RSA.

Le code ci-dessous le fait en trois lignes, mais il faut savoir le dérouler à la main. C'est le seul moyen de comprendre d'où sortent $u$ et $v$, et ce calcul revient dans tout le chapitre.

Congruences : calculer modulo $n$

Beaucoup de questions ne demandent pas un résultat, seulement un reste. L'heure qu'il sera dans 50 heures, le jour de la semaine dans 100 jours, la case d'une table de hachage, la lettre obtenue après un décalage de l'alphabet. Dans tous ces cas, le quotient ne sert à rien. Calculer le résultat exact puis prendre son reste est un détour coûteux. Les congruences sont le langage qui permet de travailler directement sur les restes, sans jamais quitter les petits nombres.

La notation se lit à voix haute en deux morceaux : le symbole $\equiv$ se dit « est congru à », et le $[n]$ se dit « modulo $n$ ». Ce $[n]$ porte sur toute l'égalité, jamais sur le seul membre de droite. D'autres ouvrages écrivent $a \equiv b \pmod n$ : c'est la même chose.

Ce que la définition écarte : $\equiv$ n'est pas $=$. Deux nombres congrus restent deux nombres différents, et rien n'autorise à remplacer l'un par l'autre hors d'un calcul modulo $n$.

Travailler modulo $n$, c'est compter sur une horloge : passé $n - 1$, on revient à zéro. Toute l'étrangeté de l'arithmétique modulaire vient de là, et elle cesse d'être étrange dès qu'on voit le cercle.

Ce qu'il faut y voir : une case du cadran ne porte pas un nombre, elle porte une infinité de nombres, ceux qui laissent le même reste. La vérification tient en deux soustractions : $41 - 15 = 26$ et $15 - (-11) = 26$, tous deux multiples de 26. Une congruence se contrôle toujours ainsi, en soustrayant.

La congruence est compatible avec l'addition et la multiplication : si $a \equiv b$ et $c \equiv d$, alors $a + c \equiv b + d$ et $ac \equiv bd$. On peut donc réduire à chaque étape d'un calcul, ce qui évite de manipuler des nombres gigantesques.

L'inverse modulaire

Cette condition sur le pgcd n'est pas une clause technique : elle se voit. Avancer de $a$ en $a$ sur le cadran revient à parcourir les multiples de $a$, et deux cas seulement se présentent.

Ce qu'il faut suivre du regard, c'est le tracé : tant qu'il n'est pas refermé, il reste des cases à visiter. Le second cas est l'exact opposé, avec un pas qui partage un diviseur avec 26.

Le tracé se referme immédiatement, et la case 1 n'a jamais été touchée : c'est cela, ne pas être inversible. Une case jamais atteinte, c'est une information définitivement perdue.

Vérification

1.Deux nombres premiers entre eux sont…

deux nombres dont le pgcd vaut 1, premiers ou nondeux nombres premiersdeux nombres impairs

2.Le théorème de Bézout garantit l'existence de u et v tels que au + bv = pgcd(a, b). À quoi cela sert-il concrètement ?

À tester si un nombre est premierÀ factoriser un grand nombreÀ calculer un inverse modulaire, donc une clé privée RSA

3.La remontée d'Euclide produit presque toujours un coefficient négatif. Est-ce une erreur ?

Non, c'est inévitable : deux termes positifs dépassant 1 ne peuvent pas totaliser 1Non, mais il faut alors recommencer dans l'autre sensOui, cela signale une faute de signe

4.Calculer a mod n quand a est négatif, en Python et en C, donne…

des résultats différents : Python rend un reste positif, C garde le signe du dividendele même résultat dans les deux langagesune erreur en Python

Nombres premiers

Le crible d'Ératosthène

Pour lister tous les premiers jusqu'à $N$ : on écrit les entiers de 2 à $N$, on garde le plus petit non barré, on barre tous ses multiples, on recommence. On peut s'arrêter dès que le carré du candidat dépasse $N$.

Familles remarquables

Factoriser est difficile, et tout repose là-dessus

Multiplier deux nombres premiers de 300 chiffres prend une fraction de microseconde. Retrouver ces deux facteurs à partir du produit est, à ce jour, hors de portée de toute machine existante.

C'est l'asymétrie fondamentale sur laquelle RSA est bâti : une opération immédiate dans un sens, sans méthode praticable dans l'autre.

Euler et Fermat

La section sur l'inverse modulaire a laissé une question ouverte. Un élément est inversible modulo $n$ quand son pgcd avec $n$ vaut 1 : combien y en a-t-il ? La réponse détermine le nombre d'exposants publics utilisables dans RSA, et elle porte un nom.

La lettre $\varphi$ se lit « phi », et $\varphi(n)$ se dit « phi de $n$ ». Elle compte donc les entiers de l'intervalle $[1 ; n]$ dont le pgcd avec $n$ vaut 1, c'est-à-dire exactement les éléments inversibles modulo $n$. Sur $n = 12$ : les candidats sont 1, 5, 7 et 11, et aucun autre, car tous les autres partagent un 2 ou un 3 avec 12. Donc $\varphi(12) = 4$.

La première égalité est immédiate : si $p$ est premier, tous les entiers de 1 à $p - 1$ lui sont premiers, et seul $p$ ne l'est pas.

La seconde se compte, et ce décompte mérite d'être fait une fois, parce que c'est lui qui fixe la taille de l'espace des clés RSA.

Parmi les $pq$ entiers de 1 à $pq$, un entier n'est pas premier avec $pq$ exactement lorsqu'il est multiple de $p$ ou multiple de $q$. Il y a $q$ multiples de $p$ (à savoir $p, 2p, \dots, qp$) et $p$ multiples de $q$. Le seul entier compté deux fois est $pq$ lui-même, qui est multiple des deux.

Le nombre d'entiers à retirer vaut donc $p + q - 1$, et il reste

$\varphi (pq) = pq - p - q + 1 = (p - 1)(q - 1)$

En clair : élever un nombre à la puissance $\varphi(n)$ ramène toujours à 1, à la seule condition que ce nombre n'ait aucun facteur commun avec $n$. C'est une remise à zéro garantie. Dépasser cet exposant ne fait que recommencer le même tour, ce qui revient à dire que seul le reste de l'exposant modulo $\varphi(n)$ compte.

C'est ce second théorème, et lui seul, qui fait fonctionner RSA : c'est lui qui fera disparaître le facteur parasite au moment du déchiffrement.

L'exponentiation modulaire rapide

Calculer $a^d \operatorname{mod} n$ avec $d$ de 600 chiffres semble impossible. Ça ne l'est pas, grâce à une idée simple : élever au carré plutôt que multiplier une fois de plus.

Pour $a^{13}$, l'écriture binaire de l'exposant, $13 = 1101_2 = 8 + 4 + 1$, donne $a^{13} = a^8 \times a^4 \times a$. Trois élévations au carré successives fournissent $a^2$, $a^4$ et $a^8$, puis deux multiplications les assemblent : cinq multiplications au lieu de douze. L'écart devient vertigineux sur un grand exposant, dont le coût ne croît plus qu'avec le nombre de chiffres.

Le même calcul en entier, avec les nombres du RSA de la fin du chapitre : $65^{17} \bmod 3233$. L'exposant s'écrit $17 = 10001_2 = 16 + 1$, donc $65^{17} = 65^{16} \times 65$. Quatre élévations au carré suffisent, chacune réduite modulo 3233 avant la suivante :

$65^2 = 4\,225 \equiv 992$, puis $992^2 = 984\,064 \equiv 1\,232$, puis $1\,232^2 = 1\,517\,824 \equiv 1\,547$, puis $1\,547^2 = 2\,393\,209 \equiv 789$. Donc $65^{16} \equiv 789 \ [3233]$.

Il ne reste qu'une multiplication : $789 \times 65 = 51\,285 = 15 \times 3233 + 2790$, d'où $65^{17} \equiv \mathbf{2790} \ [3233]$. Cinq opérations au total, et aucun nombre intermédiaire de plus de sept chiffres, alors que $65^{17}$ écrit en entier en compterait trente et un. Réduire à chaque étape est ce qui rend le calcul possible.

Coder, chiffrer, hacher

L'outillage arithmétique est complet : il peut maintenant servir. Avant d'en faire un système de chiffrement, il faut lever une confusion de vocabulaire qui fausse ensuite tous les raisonnements de sécurité. Trois mots qu'on confond, trois opérations différentes.

Chiffrement mono-alphabétique

Chaque symbole est remplacé par un autre, toujours le même. Le chiffre de César est le cas le plus simple : un décalage constant.

L'analyse de fréquence

En français, le $e$ représente environ 15 % des lettres, loin devant tous les autres. Un chiffrement mono-alphabétique déplace cette signature sans la détruire : la lettre la plus fréquente du texte chiffré est presque sûrement un $e$ chiffré.

Le chiffre de Vigenère répond à cette attaque en utilisant plusieurs alphabets, pilotés par un mot-clé : une même lettre claire devient des lettres chiffrées différentes selon sa position. Les fréquences sont lissées, mais l'attaque de Kasiski retrouve la longueur de la clé en repérant les motifs répétés, et ramène le problème à autant de chiffres de César.

Symétrique et asymétrique

RSA, pas à pas

La figure ci-dessous déroule ces quatre étapes. Cliquer sur chacune montre à quoi elle sert et, surtout, ce que devient sa valeur : publiée, gardée, ou détruite. C'est cette répartition qui fait toute la sécurité, et elle disparaît dans une liste à puces.

PQEmessage

1. 1.Deux premiersN = P × Q = 61 × 53 = 3233public
2. 2.L'indicatriceφ(N) = (P−1)(Q−1) = 60 × 52 = 3120détruit
3. 3.L'exposant publicpgcd(E, φ(N)) = pgcd(17, 3120) = 1public
4. 4.L'exposant privéD = E⁻¹ mod φ(N) = 17⁻¹ mod 3120 = 2753privé

message65^17 mod 3233→clé publiquechiffré2790^2753 mod 3233→clé privéedéchiffré65

Les deux exposants sont énormes et pourtant instantanés : l'exponentiation rapide remplace 17 multiplications par 4 mises au carré.

Ce qui circule : N = 3233 et E = 17. Pour en tirer D, il faut φ(N) ; pour φ(N), il faut P et Q ; pour P et Q, il faut factoriser N.

Ici, 56 divisions suffisent, un ordinateur les fait en une fraction de seconde. Sur une clé réelle, N compte 600 chiffres et c'est cette seule étape qui devient impossible : toutes les autres restent aussi rapides qu'ici.

Trois choses se lisent sur cette figure, et chacune se retient mieux qu'une phrase de conclusion.

• $\varphi(N)$ est détruit. C'est la seule des cinq valeurs à ne finir ni dans la clé publique ni dans la privée. Elle est pourtant celle qui les relie : qui la connaît calcule $D$ en une ligne.
• $E$ doit être premier avec $\varphi(N)$, sinon il n'a pas d'inverse et la quatrième étape n'a rien à calculer. Ce n'est pas une précaution, c'est une condition d'existence.
• L'aller-retour referme la boucle parce que $ED \equiv 1 \ [\varphi(N)]$, et pour aucune autre raison. Changer $D$ d'une unité suffit à ne plus rien retrouver.

Pourquoi ça marche

Par construction $ED \equiv 1 \ [\varphi(N)]$, donc $ED = 1 + k\varphi(N)$ pour un entier $k$. Alors :

$C^D = (M^E)^D = M^{ED} = M^{1 + k\varphi(N)} = M \times \left(M^{\varphi(N)}\right)^k$

Et le théorème d'Euler donne $M^{\varphi(N)} \equiv 1 \ [N]$, d'où $C^D \equiv M \times 1^k \equiv M \ [N]$. ∎

Le théorème d'Euler suppose $M$ premier avec $N$, c'est-à-dire non multiple de $P$ ni de $Q$. C'est le cas de presque tous les messages, et le cas restant fonctionne aussi, par un raisonnement séparé modulo $P$ puis modulo $Q$.

Trois lignes, et tout le chapitre y passe : la division euclidienne pour obtenir $D$, les congruences pour réduire, l'indicatrice d'Euler pour faire disparaître le facteur parasite. Rien n'y est superflu, et retirer une seule des quatre étapes de la génération casse la démonstration.

Le second parchemin

Un message a été intercepté : une liste de blocs chiffrés avec la clé publique jouet $N = 3233$, $E = 17$. Le programme ci-dessous mène l'attaque de bout en bout : factoriser $N$, en déduire $D$, déchiffrer.

1.Sur quoi repose la sécurité de RSA ?

Sur le secret de l'algorithmeSur la longueur du messageSur la difficulté de factoriser un grand entier

2.Chiffrer avec la clé publique du destinataire assure…

la confidentialité : lui seul peut déchiffrerl'authentification de l'expéditeurl'intégrité du message

3.Pourquoi calcule-t-on les puissances par exponentiation rapide ?

Parce que le résultat est plus précisParce que le modulo l'exigeParce que le nombre de multiplications passe de l'exposant à son logarithme

4.Que devient φ(N) une fois la clé générée ?

Il est publié avec NIl est détruit : le connaître suffirait à recalculer la clé privéeIl est conservé avec la clé privée

5.Hacher un message assure…

la confidentialitél'intégrité : toute modification change l'empreintel'authentification de l'expéditeur

Confidentialité, authentification, intégrité

Chiffrer ne répond qu'à une question sur trois.

Les deux premières se confondent tant qu'on n'a pas vu quelle clé sert à quoi, et dans quel sens. Les deux schémas ci-dessous se lisent en trois secondes et règlent la question.

Pour la confidentialité, Alice chiffre avec la clé publique de Bob. Elle est publique : n'importe qui peut donc écrire à Bob, ce qui est voulu. Seul Bob possède la privée correspondante, donc lui seul peut lire.

Ce qu'il faut regarder sur ce schéma : à qui appartiennent les deux clés citées. Les deux sont à Bob. Alice ne détient aucun secret, et pourtant elle chiffre : c'est là toute la nouveauté de l'asymétrique. Seule la flèche du milieu traverse le réseau, et ce qu'elle transporte ne se lit pas sans la clé privée, qui n'a jamais circulé.

Pour l'authentification, tout s'inverse. Alice signe avec sa propre clé privée, que personne d'autre ne possède. N'importe qui vérifie avec sa clé publique, et cette vérification prouve que le message vient bien d'elle.

Même lecture, et la comparaison des deux schémas donne la règle : ici, les deux clés citées appartiennent à Alice, l'expéditrice. Le message lui-même circule en clair ; ce qui est chiffré, c'est son empreinte. Personne d'autre qu'Alice ne peut produire cette signature, mais tout le monde peut la vérifier, puisque la clé publique est publique.

Exercices type

Calculer $\operatorname{pgcd}(1071, 462)$ par l'algorithme d'Euclide, puis en déduire une relation de Bézout

$1071 = 2 \times 462 + 147$

$462 = 3 \times 147 + 21$

$147 = 7 \times 21 + 0$

Le dernier reste non nul est 21, donc $\operatorname{pgcd}(1071, 462) = 21$.

En remontant : $21 = 462 - 3 \times 147$ et $147 = 1071 - 2 \times 462$, d'où

$21 = 462 - 3(1071 - 2 \times 462) = 7 \times 462 - 3 \times 1071$

Vérification : $7 \times 462 - 3 \times 1071 = 3234 - 3213 = 21$ ✓

Résoudre $7x \equiv 1 [26]$

On cherche l'inverse de 7 modulo 26. Comme $\operatorname{pgcd}(7, 26) = 1$, il existe.

Euclide : $26 = 3 \times 7 + 5$, $7 = 1 \times 5 + 2$, $5 = 2 \times 2 + 1$.

En remontant : $1 = 5 - 2\times 2 = 5 - 2(7 - 5) = 3\times 5 - 2\times 7 = 3(26 - 3\times 7) - 2\times 7 = 3\times 26 - 11\times 7$.

Donc $-11 \times 7 \equiv 1 [26]$, soit $x \equiv -11 \equiv$ $15 [26]$.

Contrôle : $7 \times 15 = 105 = 4 \times 26 + 1$ ✓

Une clé secrète est-elle plus sûre qu'une clé publique ?

La question repose sur une confusion : ce ne sont pas deux options concurrentes, mais deux rôles différents dans le même système.

En asymétrique, la clé publique est faite pour être diffusée : la connaître ne permet pas de déchiffrer. La clé privée est l'unique secret. Il n'y a donc pas de comparaison de sûreté à établir.

La vraie différence est ailleurs : le chiffrement symétrique exige d'avoir transmis la clé au préalable par un canal sûr, problème insoluble à l'échelle d'internet. L'asymétrique le résout, au prix d'une lenteur qui le rend impraticable sur de gros volumes. D'où l'emploi conjoint des deux.

Avec $P = 11$, $Q = 13$, $E = 7$ : calculer $D$, puis chiffrer et déchiffrer $M = 9$

$N = 143$ et $\varphi (N) = 10 \times 12 = 120$.

$D = 7^{-1} \operatorname{mod} 120$. Euclide : $120 = 17 \times 7 + 1$, donc $1 = 120 - 17 \times 7$, d'où $D \equiv -17 \equiv$ $103 [120]$.

Chiffrement : $C = 9^7 \operatorname{mod} 143$. Par carrés successifs, $9^2 = 81$, $9^4 = 81^2 = 6561 = 45 \times 143 + 126$, donc $9^4 \equiv 126$. Puis $9^7 = 9^4 \times 9^2 \times 9 \equiv 126 \times 81 \times 9$. On réduit : $126 \times 81 = 10206 = 71 \times 143 + 53$, donc $10206 \equiv 53 [143]$, puis $53 \times 9 = 477 = 3 \times 143 + 48$, soit $C \equiv$ $48 [143]$.

Déchiffrement : $48^{103} \operatorname{mod} 143 = 9$ ✓ (à vérifier par pow(48, 103, 143)).

Est-ce que coder, c'est chiffrer ?

Non, et la confusion est dangereuse.

Coder change la représentation : ASCII, UTF-8, base64. L'opération est publique et sans clé, n'importe qui décode. Une chaîne en base64 n'est pas protégée, elle est simplement illisible à l'œil nu.

Chiffrer rend l'information inaccessible sans la clé. C'est le secret de la clé qui protège, pas l'obscurité du format.

Le message du second parchemin illustre les deux étapes : les caractères sont d'abord codés en ASCII (opération publique), puis les codes sont chiffrés par RSA (opération à clé). Seule la seconde apporte de la sécurité.

Un nouveau théorème mathématique pourrait-il ruiner l'économie mondiale du jour au lendemain ?

En théorie, oui. Un algorithme de factorisation en temps polynomial rendrait RSA lisible instantanément : signatures, certificats, transactions bancaires, mises à jour logicielles authentifiées.

Trois nuances, qui comptent. La difficulté de la factorisation n'est pas démontrée : personne n'a prouvé qu'un tel algorithme n'existe pas. Le déploiement ne serait pas instantané : la cryptographie symétrique (AES) n'est pas concernée, et la migration serait rapide mais pas immédiate. Et la menace la plus concrète n'est pas mathématique mais technologique, l'algorithme de Shor existe déjà, il attend un ordinateur quantique de taille suffisante.

C'est pourquoi la cryptographie post-quantique, fondée sur d'autres problèmes difficiles, est en cours de normalisation. Se préparer avant l'événement, plutôt qu'après.

La méthode

1. Écrire la division euclidienne sous la forme $a = bq + r$ avec $0 \leq r < b$. Toutes les erreurs de signe viennent de son oubli.
2. Poser Euclide en colonnes, une division par ligne. Le dernier reste non nul est le pgcd.
3. Pour Bézout, remonter les égalités une à une, en substituant les restes sans développer les produits : c'est ce qui rend le calcul faisable à la main.
4. Réduire à chaque étape dans un calcul modulaire. Ne jamais développer une grande puissance.
5. Pour une puissance modulaire, procéder par carrés successifs en suivant l'écriture binaire de l'exposant.
6. Pour RSA, dérouler les quatre étapes dans l'ordre : $N$, puis $\varphi (N)$, puis $D$, puis le déchiffrement. Contrôler $E \times D \operatorname{mod} \varphi (N) = 1$ avant de continuer.
7. Vérifier par l'aller-retour : rechiffrer le message obtenu et comparer au chiffré de départ.
8. Nommer la propriété visée : confidentialité, authentification ou intégrité. Chacune appelle un outil différent.

Synthèse

• Division euclidienne : $a = bq + r$, $0 \leq r < |b|$, couple unique. Attention au signe du reste selon le langage.
• Euclide : $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, a \operatorname{mod} b)$, en $O(\log n)$. Euclide étendu donne $u$ et $v$ tels que $au + bv = \operatorname{pgcd}$.
• Bézout : $a$ et $b$ premiers entre eux ⟺ il existe $u$ et $v$ avec $au + bv = 1$.
• Congruences : compatibles avec $+$ et $\times$, donc on réduit à chaque étape.
• Modulo un composé, un produit de non-nuls peut être nul. Modulo un premier, jamais.
• Inverse modulaire : existe ⟺ $\operatorname{pgcd}(a, n) = 1$, se calcule par Euclide étendu.
• 1 n'est pas premier : l'unicité de la décomposition en dépend.
• Crible d'Ératosthène : barrer les multiples à partir de $p^2$, s'arrêter à $\sqrt{N}$.
• Mersenne $2^p - 1$, Fermat $2^{2^n} + 1$, Sophie Germain $p$ et $2p + 1$.
• Factoriser est difficile : constaté, pas démontré. Shor le fait en quantique.
• $\varphi (p) = p - 1$, $\varphi (pq) = (p-1)(q-1)$. Jamais $\varphi (N) = N - 1$ pour un composé.
• Euler : $a^{\varphi(n)} \equiv 1 [n]$ si $\operatorname{pgcd}(a, n) = 1$. C'est ce qui fait fonctionner RSA.
• Exponentiation rapide : carrés successifs, $O(\log d)$ multiplications.
• Coder ≠ chiffrer ≠ hacher. Réversible sans clé, réversible avec la clé, irréversible et sans clé.
• Mono-alphabétique : cassé par les fréquences, quelle que soit la taille de l'espace des clés.
• Kerckhoffs : la sécurité repose sur la clé, jamais sur le secret de l'algorithme.
• RSA : $C = M^E \operatorname{mod} N$, $M = C^D \operatorname{mod} N$, avec $ED \equiv 1 [\varphi (N)]$. Déterministe sans remplissage, donc à ne jamais employer nu.
• Confidentialité (clé publique du destinataire), authentification (clé privée de l'expéditeur), intégrité (hachage).

Et ensuite

RSA tient sur un problème que personne ne sait résoudre vite. Le dernier chapitre prend le mouvement inverse : un problème réputé difficile en général, colorer un graphe, devient linéaire dès que les données ont la bonne structure. Graphes et coloration referme le parcours là-dessus : la difficulté n'est pas dans le problème seul, mais dans le couple problème-structure.