Arithmétique et cryptographie

Où on va

Un message chiffré n'est qu'une suite de nombres. Derrière cette évidence se cache la question qui fonde toute la sécurité informatique : comment fabriquer une opération facile dans un sens et pratiquement impossible dans l'autre ? La réponse ne vient ni de l'analyse ni de la géométrie, mais de l'arithmétique des entiers, celle qu'on croit avoir laissée au collège. Ce chapitre la reprend depuis la divisibilité et va jusqu'à casser, pour de vrai, deux messages chiffrés.

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 ?

Trois raisons, et la troisième est décisive

1. Une machine ne manipule que des entiers. Un « nombre à virgule » est un entier accompagné d'un exposant, sur un nombre fini de bits. 0,1 + 0,2 ne vaut pas 0,3 en flottant, et 1/3 n'a pas d'écriture exacte.
2. L'arithmétique est plus difficile que le calcul réel, pas plus simple. Dans ℝ, toute équation ax = b avec a ≠ 0 a une solution ; dans ℤ, 3x = 5 n'en a aucune. Cette contrainte supplémentaire rend l'existence des solutions imprévisible.
3. Cette imprévisibilité est exactement ce qu'on cherche. Elle permet de construire des opérations faciles dans un sens et hors d'atteinte dans l'autre, même quand l'adversaire connaît la méthode, et même quand il possède une partie de la clé.

Divisibilité et division euclidienne

Définitions

$a$ divise $b$ , noté a | b, s'il existe un entier $k$ tel que $b = ka$ .

Division euclidienne : pour $a$ entier et $b$ entier non nul, il existe un unique couple $(q, r)$ tel que $a = bq + r$ avec $0 \leq r < |b|$ .

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$ .

Le reste est toujours positif, en Python

-17 // 5 vaut -4 et -17 % 5 vaut 3, ce qui respecte -17 = 5×(-4) + 3 avec 0 ≤ 3 < 5. En C ou en Java, -17 % 5 vaut -2 : le langage tronque vers zéro au lieu d'arrondir vers le bas.
En cryptographie, où tout est modulaire, cette différence transforme un chiffrement correct en chiffrement faux. C'est un piège classique du portage d'un algorithme d'un langage à l'autre.

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.

Algorithme d'Euclide

Il repose sur une seule observation : $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, a \operatorname{mod} b)$ . On remplace le couple par un couple plus petit jusqu'à obtenir un reste nul ; le dernier reste non nul est le pgcd.

C'est un des plus vieux algorithmes connus, et il reste remarquablement rapide : sa complexité est en $O(\log(\min(a, b)))$ . Sur des nombres de 600 chiffres, il termine en quelques microsecondes.

Euclide étendu et Bézout

Théorème de Bézout

Pour tous entiers $a$ et $b$ non nuls, il existe des entiers $u$ et $v$ tels que :

$au + bv = \operatorname{pgcd}(a, b)$

En particulier, $a$ et $b$ sont premiers entre eux si et seulement si il existe u, v avec $au + bv = 1$ .

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.

main.py

Sortie

>_ Prêt à exécuter…

Congruences : calculer modulo n

Définition

$a \equiv b [n]$ («  $a$ congru à $b$ modulo $n$  ») signifie que $n$ divise $a - b$ , autrement dit que $a$ et $b$ ont le même reste dans la division par $n$ .

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.

Le produit de deux nombres non nuls peut être nul

Modulo 6 : 2 × 3 = 6 ≡ 0. Ni 2 ni 3 n'est nul, et pourtant leur produit l'est. On ne peut donc pas « simplifier par 2 » comme on le ferait dans ℝ.
Ce phénomène disparaît quand n est premier : modulo un nombre premier, tout élément non nul est inversible et le produit de deux non-nuls n'est jamais nul. C'est la raison profonde pour laquelle la cryptographie travaille modulo des nombres premiers, ou modulo un produit de deux premiers dont elle contrôle la structure.

L'inverse modulaire

Définition

L'inverse de $a$ modulo $n$ est l'entier $x$ tel que $ax \equiv 1 [n]$ . Il existe si et seulement si $\operatorname{pgcd}(a, n) = 1$ , et on l'obtient par Euclide étendu : de $au + nv = 1$ on tire $au \equiv 1 [n]$ , donc $x = u \operatorname{mod} n$ .

main.py

Sortie

>_ Prêt à exécuter…

Nombres premiers

Définition

Un entier $p \geq 2$ est premier s'il admet exactement deux diviseurs positifs distincts : 1 et lui-même.

1 n'est pas premier, et ce n'est pas une convention arbitraire

Il n'a qu'un seul diviseur, pas deux. Surtout, l'admettre détruirait le théorème fondamental de l'arithmétique : tout entier ≥ 2 se décompose de façon unique en produit de facteurs premiers. Si 1 était premier, 6 = 2×3 = 1×2×3 = 1×1×2×3 donnerait une infinité de décompositions. C'est l'unicité qui compte, et c'est elle qu'on protège.

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$ .

main.py

Sortie

>_ Prêt à exécuter…

Familles remarquables

Trois familles au programme

Mersenne : Mₚ = 2ᵖ − 1. Pour que $M_p$ soit premier, il faut que $p$ le soit, mais cela ne suffit pas : $M_{11} = 2047 = 23 \times 89$ . Les plus grands premiers connus sont des nombres de Mersenne, parce qu'il existe un test de primalité spécifique et très rapide pour cette forme.

Fermat : $F_n = 2^(2^n) + 1$ . Fermat conjecturait qu'ils étaient tous premiers ; c'est vrai pour $F_0$ à $F_4$ (3, 5, 17, 257, 65537), et Euler a réfuté la conjecture en factorisant F₅ = 4 294 967 297 = 641 × 6 700 417.

Sophie Germain : $p$ est un premier de Sophie Germain si $2p + 1$ est aussi premier. Les premiers sont 2, 3, 5, 11, 23, 29, 41… Ils sont recherchés en cryptographie parce qu'ils produisent des groupes à la structure bien maîtrisée.

« Une puissance de 2 plus 1 est-elle première ? »

Presque jamais. Si 2ᵐ + 1 est premier, alors m est nécessairement une puissance de 2, c'est-à-dire qu'on est dans la famille de Fermat. Et même là, on ne connaît que cinq nombres de Fermat premiers, tous découverts avant 1640.
La raison est algébrique : si m a un facteur impair k, alors 2^(m/k) + 1 divise 2ᵐ + 1. Exemple : 2⁶ + 1 = 65 = 5 × 13, avec 5 = 2² + 1.

main.py

Sortie

>_ Prêt à exécuter…

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.

main.py

Sortie

>_ Prêt à exécuter…

Ce que « difficile » veut dire, et ne veut pas dire

Il n'est pas démontré que factoriser est intrinsèquement difficile : c'est une difficulté constatée, pas prouvée. Un algorithme efficace pourrait exister et n'avoir pas été trouvé, c'est le sens de la question « un nouveau théorème pourrait-il ruiner l'économie mondiale ? ».
On sait en revanche que l'algorithme de Shor factorise en temps polynomial sur un ordinateur quantique. La menace n'est pas théorique, elle est technologique, et elle motive la cryptographie post-quantique, qui repose sur d'autres problèmes difficiles, pas sur la factorisation.

Euler et Fermat

Indicatrice d'Euler

$\varphi (n)$ est le nombre d'entiers de 1 à $n$ premiers avec $n$ .

$\varphi (p) = p - 1$ si $p$ est premier ;
$\varphi (pq) = (p - 1)(q - 1)$ si $p$ et $q$ sont deux premiers distincts.

Deux théorèmes

Petit théorème de Fermat : si $p$ est premier et ne divise pas $a$ , alors $a^(p-1) \equiv 1 [p]$ .

Théorème d'Euler, qui le généralise : si $\operatorname{pgcd}(a, n) = 1$ , alors $a^{\varphi} (n) \equiv 1 [n]$ .

C'est ce second théorème, et lui seul, qui fait fonctionner RSA.

φ(N) = N − 1 est faux dès que N n'est pas premier

On rencontre cette formule dans des corrigés de RSA, et elle y est fausse par construction : si N était premier, φ(N) = N − 1 serait calculable par tout le monde, la clé privée s'en déduirait immédiatement, et le chiffrement n'aurait aucun intérêt.
Toute la sécurité de RSA tient à ce que φ(N) = (P−1)(Q−1) exige de connaître P et Q, donc de savoir factoriser N.

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.

$a^13 = a^8 \times a^4 \times a^1$ , trois multiplications au lieu de douze, en suivant l'écriture binaire de l'exposant $13 = 1101_2$ .

main.py

Sortie

>_ Prêt à exécuter…

Coder, chiffrer, hacher

Trois mots qu'on confond, trois opérations différentes.

Les distinguer

Coder (ou encoder) : représenter une information dans un autre alphabet. ASCII, UTF-8, base64. Réversible, sans secret, ce n'est pas de la sécurité.

Chiffrer : rendre une information incompréhensible sans la clé. Réversible avec la clé. (« Crypter » n'existe pas en français ; « décrypter » si, c'est lire sans la clé, donc casser.)

Hacher : produire une empreinte de taille fixe. Irréversible, et sans clé. Sert à l'intégrité et au stockage des mots de passe.

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.

Le premier parchemin

Le message chiffré est 9153787770964, décalé de $K = 4$ . On applique le décalage inverse, chiffre par chiffre :

chiffre clair = (chiffre chiffré − 4) mod 10

$9 \to 5$ , $1 \to 7$ (car $1 - 4 = -3 \equiv 7 [10]$ ), $5 \to 1$ , $3 \to 9$ , $7 \to 3$ , $8 \to 4$ …

On obtient 5719343336520, treize chiffres qu'on regroupe au format de coordonnées : 57°19'34.3"N, 3°36'52.0"W, quelque part dans les Highlands.

Compte les chiffres avant de découper

Le format visé consomme 2+2+2+1 chiffres pour la latitude et 1+2+2+1 pour la longitude, soit treize exactement. Si ton message chiffré n'en a que douze, c'est qu'un chiffre s'est perdu à la recopie, et aucun découpage ne tombera juste. Vérifier la longueur attendue avant de déchiffrer évite de chercher l'erreur dans le mauvais endroit.

main.py

Sortie

>_ Prêt à exécuter…

Pourquoi ce chiffrement ne vaut rien

L'espace des clés compte dix possibilités. Les essayer toutes prend une microseconde. Et sur du texte, même un alphabet de substitution quelconque, fort de 26! clés soit plus de 4 × 10²⁶, tombe en quelques secondes : il préserve les fréquences.

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é.

main.py

Sortie

>_ Prêt à exécuter…

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

Deux familles

Symétrique : la même clé chiffre et déchiffre. Rapide, adapté aux gros volumes. Standard actuel : AES. Problème : il faut avoir transmis la clé au préalable, par un canal sûr.

Asymétrique : deux clés liées mathématiquement. La clé publique chiffre et se diffuse à tous ; la clé privée déchiffre et ne quitte jamais son propriétaire. Standard historique : RSA. Lent, mais résout le problème de l'échange de clé.

En pratique, les deux ensemble

Une connexion HTTPS commence par de l'asymétrique pour convenir d'une clé de session, puis bascule en symétrique pour toute la suite. On paie le coût du chiffrement lent une seule fois, au début, et l'on obtient la rapidité d'AES avec la souplesse de RSA. C'est la réponse à « comment envoyer un message confidentiel sans avoir échangé de code secret au préalable ».

Le principe de Kerckhoffs

La sécurité d'un système ne doit reposer que sur le secret de la clé, jamais sur celui de l'algorithme. AES et RSA sont entièrement publics, spécifiés, et attaqués par la communauté depuis des décennies, c'est ce qui fonde la confiance qu'on leur accorde. Un algorithme secret est un algorithme que personne n'a pu casser publiquement, ce qui n'est pas la même chose.

RSA, pas à pas

L'algorithme complet

Génération des clés

Choisir deux grands premiers $P$ et $Q$ , et poser $N = PQ$ .
Calculer $\varphi (N) = (P - 1)(Q - 1)$ .
Choisir $E$ premier avec $\varphi (N)$ .
Calculer $D = E^{-1} \operatorname{mod} \varphi (N)$ par Euclide étendu.

Clé publique : $(N, E)$ . Clé privée : $(N, D)$ . On détruit $P$ , $Q$ et $\varphi (N)$ .

Chiffrement : $C = M^E \operatorname{mod} N$ Déchiffrement : $M = C^D \operatorname{mod} N$

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 (M^{\varphi} (N))^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]$ . ∎

Où est le secret

Tout le monde connaît N et E. Pour trouver D, il faut φ(N) ; pour φ(N), il faut P et Q ; pour P et Q, il faut factoriser N. Toute la sécurité de RSA tient à ce dernier maillon, et à rien d'autre.

Le second parchemin

Prenons une clé publique jouet : $N = 3233$ , $E = 17$ , et une liste de blocs chiffrés. Déroulons.

main.py

Sortie

>_ Prêt à exécuter…

Ce RSA-là est cassé, et pour une raison instructive

Chiffrer caractère par caractère avec la même clé donne toujours le même bloc pour le même caractère. Dans la liste ci-dessus, 1992 apparaît sept fois : c'est l'espace, et le message clair compte exactement sept espaces. On vient donc de reconstruire, sans le vouloir, un chiffrement mono-alphabétique, cassable par analyse de fréquence sans jamais factoriser N.
Le vrai RSA chiffre des blocs de la taille de N (2048 bits) et ajoute un remplissage aléatoire (OAEP) : deux chiffrements du même message donnent alors deux résultats différents. Sans remplissage, RSA est déterministe, donc faible, un algorithme correct mal employé ne protège rien.

Vérification rapidesans note, on peut se reprendre

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

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

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

Confidentialité, authentification, intégrité

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

Trois propriétés distinctes

Confidentialité : personne d'autre ne peut lire. Chiffrer avec la clé publique du destinataire : lui seul possède la privée qui déchiffre.

Authentification, le destinataire sait qui a écrit. C'est la signature : l'expéditeur applique sa clé privée à l'empreinte du message ; n'importe qui vérifie avec sa clé publique. Les deux usages sont symétriques, et c'est la même mécanique employée dans l'autre sens.

Intégrité, le message n'a pas été modifié. C'est le rôle du hachage : on transmet l'empreinte, le destinataire la recalcule et compare.

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.

Diagramme de séquence

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.

Diagramme de séquence

La question qui tranche : à qui appartient la clé employée ?

Clé publique du destinataire : confidentialité. Beaucoup peuvent écrire, un seul peut lire.
Clé privée de l'expéditeur : authentification. Un seul peut écrire, beaucoup peuvent vérifier.
En pratique on fait les deux à la fois, en signant puis en chiffrant. Et l'on ne signe jamais le message entier, seulement son empreinte : c'est plus court, et cela apporte l'intégrité par la même opération.

L'intégrité, ailleurs qu'en cryptographie

La clé de contrôle du numéro de sécurité sociale, la dernière lettre d'un IBAN, le bit de parité d'une trame, les codes correcteurs d'erreurs : tous reposent sur une opération modulaire, et tous servent à détecter une altération. Ils ne protègent pas contre un adversaire, seulement contre l'erreur de saisie ou de transmission. C'est de l'intégrité accidentelle, pas de l'intégrité cryptographique.

main.py

Sortie

>_ Prêt à exécuter…

Pourquoi les clés s'allongent

La sécurité se mesure en bits : une clé de k bits offre 2ᵏ possibilités, et chaque bit ajouté double le travail de l'attaquant. Une clé de 56 bits (l'ancien DES) se casse aujourd'hui en quelques heures ; AES-256 est hors d'atteinte de toute attaque exhaustive concevable.
Pour RSA, ce n'est pas l'attaque exhaustive qui compte mais la factorisation : les progrès des algorithmes et du matériel ont fait passer la recommandation de 1024 à 2048, puis 3072 bits. C'est la même raison qui a fait grandir les clés Wi-Fi.

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 \equiv 48 [143]$ , puis $48 \times 9 = 432 \equiv$ $3 [143]$ .

Déchiffrement : $3^{103} \operatorname{mod} 143 = 9$ ✓ (à vérifier par pow(3, 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 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

Écris la division euclidienne sous la forme $a = bq + r$ avec $0 \leq r < b$ . Toutes les erreurs de signe viennent de son oubli.
Pose Euclide en colonnes, une division par ligne. Le dernier reste non nul est le pgcd.
Pour Bézout, remonte les égalités une à une sans jamais calculer les produits : c'est ce qui rend le calcul faisable à la main.
Réduis à chaque étape dans un calcul modulaire. Ne développe jamais une grande puissance.
Pour une puissance modulaire, procède par carrés successifs en suivant l'écriture binaire de l'exposant.
Pour RSA, déroule les quatre étapes dans l'ordre : $N$ , puis $\varphi (N)$ , puis $D$ , puis le déchiffrement. Contrôle $E \times D \operatorname{mod} \varphi (N) = 1$ avant de continuer.
Vérifie par l'aller-retour : rechiffre le message obtenu et compare au chiffré de départ.
Nomme la propriété visée : confidentialité, authentification ou intégrité. Chacune appelle un outil différent.

En résumé

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, v tels que $au + bv = \operatorname{pgcd}$ .
Bézout : $a$ et $b$ premiers entre eux ⟺ il existe u, 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ᵖ − 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. Sans clé, sans clé et réversible, sans clé et irréversible.
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 ? Il reste un dernier objet mathématique dans le bloc, et c'est celui qui modélise les relations plutôt que les nombres : la théorie des graphes, appliquée à la planification de tâches sur des serveurs.

Arithmétique et cryptographie

Ce que ce chapitre apporte

Pourquoi de l'arithmétique au XXIe siècle

Divisibilité et division euclidienne

PGCD et algorithme d'Euclide

Euclide étendu et Bézout

Congruences : calculer modulo n

L'inverse modulaire

Nombres premiers

Le crible d'Ératosthène

Familles remarquables

Factoriser est difficile, et tout repose là-dessus

Euler et Fermat

L'exponentiation modulaire rapide

Coder, chiffrer, hacher

Chiffrement mono-alphabétique

L'analyse de fréquence

Symétrique et asymétrique

RSA, pas à pas

Pourquoi ça marche

Le second parchemin

Confidentialité, authentification, intégrité

Exercices type

La méthode

En résumé

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

Congruences : calculer modulo n