Cryptage et décryptage :communiquer
en toute sécurité
Jean-Louis Nicolas, professeur à l’Université Claude Bernard Lyon 1Christophe Delaunay, professeur à l’Université de Franche-Comté

La sécurisation de nos cartes bleues, ainsi que d’autres procédés de cryptages utilisés couramment, se basent sur l’impossibilité, en pratique, de factoriser de très grands nombres. Ce type de cryptage pourrait cependantêtre détrôné par d’autres méthodes, sa fiabilité étant sans cesse remise enquestion par les progrès de l’informatique.

1 et par eux-mêmes. Le secret d’une cartebancaire est constitué précisément par ce
couple de nombres premiers ; les calculerà partir de N était pratiquement impossible

En mars 2000, un gros titre avait fait la unedes journaux : « Alerte à la sécurité descartes bancaires ». Que s’était-il passé ? EnFrance, le secret des cartes à puce était protégé depuis 1985 grâce à une méthode decryptage faisant intervenir un grand nombre
N, constitué de 97 chiffres. Ce nombre Ndoit être le produit de deux grands nombres
premiers, c’est-à-dire de nombres qui,comme 7 ou 19, ne sont divisibles que pardans la décennie 1980. Mais avec l’augmentation de la puissance des ordinateurs
et l’amélioration des méthodes mathématiques, la taille des nombres N dont on
peut calculer les facteurs premiers en untemps raisonnable a dépassé la centaine
de chiffres dans les années 1990 (le recordactuel, obtenu en décembre 2009, est lafactorisation d’un nombre de 232 chiffres).
Ainsi, un informaticien astucieux, SergeHumpich, avait pu trouver les deux nombres
premiers ultra-secrets dont le produit valait
le nombre N d’alors. Pour garantir la sécurité de nos petits rectangles de plastique,l’organisme de gestion des cartes ban-Cryptage et décryptage : communiquer en toute sécurité – 83

caires avait été obligé de construire aussitôt
de nouveaux nombres N, nettement plus
grands. La page web de Paul Zimmerman(voir les références en fin d’article) offre unemise à jour des différents records de factorisation des entiers.

La taille des nombres N dont on
peut calculer les facteurs premiers en un temps raisonnablea dépassé la centaine de chiffres
dans les années 1990.

La cryptographie moderne, aucroisement des mathématiques
et de l’informatique
Cette péripétie illustre l’importance considérable que revêt aujourd’hui la science ducryptage, c’est-à-dire du codage de messages en vue de les rendre illisibles par despersonnes indiscrètes. Crypter et décrypter des messages secrets est une activité

vieille de plusieurs siècles, voire millénaires.
Et cette activité a largement débordé ducadre strictement diplomatique ou militairepour investir des pans entiers de l’univers
des communications civiles : procéduresd’authentification, transactions bancaires,commerce électronique, protection de sites
et fichiers informatiques, etc.
La cryptographie a connu beaucoup d’avancées au cours des dernières décennies.
Ce faisant, elle est devenue une science
complexe, où les progrès sont généralement le fait de spécialistes ayant reçu une
formation poussée en mathématiques et en
informatique.
Cette spécialisation s’est manifestée dès
la Deuxième guerre mondiale. On le saitaujourd’hui, le déchiffrage par les Alliésdes messages codés par les fameusesmachines allemandes Enigma a joué unrôle déterminant dans ce conflit. Or c’est unéminent mathématicien britannique, AlanTuring, par ailleurs l’un des pères de l’informatique théorique, qui a apporté une contribution essentielle à ce décryptage.
Dans les années 1970, la cryptographie aconnu une petite révolution : l’invention dela cryptographie à « clé publique », avec laméthode RSA. De quoi s’agit-il ? Jusque-là,les correspondants voulant échanger desmessages secrets devaient partager uneclé secrète, et le risque d’interception decette clé par l’ennemi était grand. Le protocole RSA, nommé ainsi d’après ses trois
inventeurs (Ronald Rivest, Adi Shamir etLeonard Adleman), résout ce problème.
Cette méthode utilise deux clés : une clé de84 – Mathématiques, l’explosion continue

cryptage publique – elle peut être connue
de tous – et une clé de décryptage, qui restesecrète. Elle est fondée sur le principe (utilisé par la suite pour protéger les cartes bancaires, comme on l’a vu plus haut) qu’il est
possible de construire de grands nombres
premiers (de cent, mille chiffres, voireplus), mais qu’il est extrêmement difficile
de retrouver les facteurs premiers p et qd’un grand nombre N = p x q lorsque l’on
connaît seulement N. Schématiquement, laconnaissance de N revient à celle de la clé
publique de cryptage, tandis que la connaissance de p et q revient à celle de la clé
secrète de décryptage.
Évidemment, si quelqu’un trouvait une
méthode pour décomposer rapidement enleurs facteurs premiers de grands nombres,le protocole RSA deviendrait caduc. Mais il
se pourrait aussi que les mathématiciens
prouvent qu’une telle méthode n’existe pas,ce qui renforcerait la sécurité du protocole
RSA. Ce sont là des sujets de recherche
décisifs.

dans un domaine parfaitement pur, l’arithmétique, et de n’avoir rien fait qui puisseêtre considéré comme « utile ». Ses travauxétaient peut-être « inutiles » à son époque.
C’est faux aujourd’hui.

Courbes elliptiques :la géométrie algébriqueau service des agents secrets
Et cela ne concerne pas uniquement lathéorie des nombres. D’autres domainesdes mathématiques, auparavant considérés comme dépourvus d’applications,contribuent à la science du cryptage. Des
méthodes cryptographiques prometteuses
et fondées sur des principes voisins de ceux
du protocole RSA sont apparues au cours
des dernières années. Il en est ainsi de laméthode dite du logarithme discret. Celle-cia servi à son tour à concevoir des méthodes
qui s’appuient sur les propriétés des courbes
elliptiques. Il ne s’agit pas de courbes ayant
la forme d’une ellipse, mais de courbes dontl’étude a débuté au xixe siècle pour résoudre

Les méthodes qui, comme le protocole
RSA, font intervenir de la théorie desnombres élaborée, apportent une grandeleçon : des recherches mathématiques (surles nombres premiers notamment) tout à
fait désintéressées peuvent se révéler, desannées ou des décennies plus tard, cruciales pour telle ou telle application ; et cede manière imprévisible.
Dans son livre L’apologie d’un mathématicien, le grand théoricien des nombres britannique G. H. Hardy (1877-1947), qui était
un fervent pacifiste, se targuait de travailler

Cryptage et décryptage : communiquer en toute sécurité – 85

le problème difficile du calcul du périmètred’une ellipse. Ces courbes, dont les coordonnées (x, y ) de leurs points vérifient uneéquation de la forme y 2 = x 3 + ax + b, ont
d’intéressantes propriétés – dont l’étude fait
partie de la géométrie algébrique, très vaste
domaine des mathématiques actuelles. Parexemple, à l’aide d’une construction géométrique appropriée, il est possible de définir
une addition entre les points d’une courbe
elliptique (voir figure ci-dessous).

Plus généralement, les objets géométriques que sont les courbes elliptiques possèdent des propriétés arithmétiques – quel’on continue d’explorer – susceptibles derendre service à la cryptographie. C’est ainsiqu’a été développée une méthode cryptographique intitulée logarithme discret sur lescourbes elliptiques. De façon anecdotique,les courbes elliptiques fournissent aussi une
méthode originale pour factoriser les entiers(cependant, des méthodes bien plus techniques sont nécessaires pour obtenir lesrecords actuels).

Les objets géométriques que sontles courbes elliptiques possèdent
des propriétés arithmétiquessusceptibles de rendre service à
la cryptographie.

L’ordinateur quantique : l’outil
de demain ?

Le graphe de la courbe elliptiqued’équation y2 = x 3 + 1. Les courbes
elliptiques ont une propriété remarquable : on peut « additionner » leurspoints selon le procédé représenté
sur le dessin. L’« addition » ainsi définie respecte les lois arithmétiques
attendues, telles que (P1 + P2) + P3 =P1 + (P2 + P3). Certaines méthodes modernes de cryptographie font appel aux
courbes elliptiques et à leurs propriétés
algébriques.

86 – Mathématiques, l’explosion continue

Une autre direction, totalement différente,
est apparue assez récemment. Il s’agit dela cryptographie quantique. Que signifie ceterme ? Il y a quelques années, des physiciens et des mathématiciens ont imaginé
qu’il serait un jour possible de réaliser unordinateur quantique, c’est-à-dire dont lefonctionnement exploiterait les lois bizarresde la physique quantique, celles qui règnent
dans le monde infiniment petit. Or, on s’estrendu compte qu’un tel ordinateur, s’il était
réalisable, serait capable de factoriser trèsvite de grands nombres et rendrait ainsi
totalement inefficace la méthode RSA(dans ce contexte, lors du congrès international des mathématiciens à Berlin en 1998,

Peter Shor, des laboratoires AT & T, obtenait
le prix Nevanlinna pour ses travaux sur lafactorisation à l’aide des ordinateurs quantiques). Des recherches visant la réalisation
concrète d’un ordinateur quantique ont d’ailleurs été publiées dans la revue britannique
Nature (cf. référence ci-dessous). D’un autre
côté, des chercheurs ont élaboré des protocoles de cryptographie quantique, c’està-dire des méthodes de cryptage utilisantdes objets (photons, atomes…) obéissant
aux lois de la physique quantique. Ces protocoles quantiques garantissent (du moinsthéoriquement) une sécurité infaillible. Toutcela est à l’étude et risque de devenir opérationnel dans un futur proche (par exemple,un câble de communication quantiquereliant la ville de Genève à Lausanne fonctionne déjà depuis plusieurs années…).

Pour aller plus loin
La page web de Paul Zimmerman sur les records de factorisation des entiers :www.loria.fr/~zimmerma/records/factor.html
Kahn D., (1980). La guerre des codes secrets (Interéditions).
Stern J., (Jacob O. 1998). La science dusecret.
Singh S., (Lattès J.-C., 1999) Histoire descodes secrets.
Delahaye J.-P., (2000). Merveilleux nombres
premiers (Belin/Pour la Science).
Stinson D. (Vuibert, 2001). Cryptographie,théorie et pratique.
Vandersypen L. M. K., et al., (2001) Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic
resonance, Nature, vol. 414, p. 883-887.

Cryptage et décryptage : communiquer en toute sécurité – 87