Cryptage et décryptage :communiquer
en toute sécurité
Jean-Louis Nicolas

Dans le monde actuel, où les télécommunications occupent une placecruciale, la cryptographie est un enjeu majeur.
Elle est aussi devenue une science complexe, qui ne peut se passer
de mathématiciens de haut niveau.

en mars 2000, un gros
titre avait fait la une desjournaux : « Alerte à lasécurité des cartes bancaires ». Que s’était-ilpassé? En France, le secretdes cartes à puce était protégé depuis 1985 grâce àune méthode de cryptagefaisant intervenir un grandnombre N, constitué de 97
chiffres. Ce nombre N doitêtre le produit de deux
grands nombres premiers,c’est-à-dire de nombresqui, comme 7 ou 19, nesont divisibles que par 1 et Payer avec sa carte de crédit, faire des achats sur Internet : les méthodes cryptographiques, qui mettent en jeu de belles mathématiques, sont indispensables à la sécurité de ces opérations.
par eux-mêmes. Le secret (Photo : Getty Images.)d’une carte bancaire est
constitué précisément par ce couple de méthodes mathématiques, la taille desnombres premiers ; les calculer à partir de N nombres N dont on peut calculer les facteursétait pratiquement impossible dans la décen- premiers en un temps raisonnable a dépassénie 1980. Mais avec l’augmentation de la puis- la centaine de chiffres dans les dernières
sance des ordinateurs et l’amélioration des années du siècle (le record actuel, 158 chiffres,16

L’explosion des mathématiques

date de janvier 2002). Un informaticien astucieux, Serge Humpich, avait ainsi pu trouverles deux nombres premiers ultra-secrets dont
le produit vaut N et les avait utilisés pour fabriquer de fausses cartes. Alors, pour garantir lasécurité de nos petits rectangles de plastique,l’organisme de gestion des cartes bancaires aaussitôt construit de nouveaux nombres N,
nettement plus grands.

l’un des pères de l’informatique théorique,qui a apporté une contribution essentielle àce décryptage.

La cryptographie moderne,
au croisement 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 des personnes
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é du cadre strictement diplomatique ou militaire pour investir des pansentiers de l’univers des communications civiles:
procédures d’authentification, transactions
bancaires, commerce électronique, protectionde sites et fichiers informatiques, etc.
La cryptographie a connu beaucoupd’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 faitde 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 sait aujourd’hui, le déchiffrage par les Alliés des messages codés par les fameuses machines allemandes Enigma a joué un rôle déterminantdans ce conflit. Or c’est un éminent mathématicien britannique, Alan Turing, par ailleursDans les années 1970, la cryptographie aconnu une petite révolution : l’invention de lacryptographie à « clé publique », avec laméthode RSA. De quoi s’agit-il ? Jusque-là, lescorrespondants voulant échanger des messages secrets devaient partager une clé secrète,et le risque d’interception de cette clé par l’ennemi était grand. Le protocole RSA, nommé
ainsi d’après ses trois inventeurs (Ronald Rivest,Adi Shamir et Leonard Adleman), résout ceproblème. Cette méthode utilise deux clés :une clé de cryptage publique — elle peut êtreconnue de tous — et une clé de décryptage,qui reste secrè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, voire plus), mais
qu’il est extrêmement difficile de retrouver
les facteurs premiers p et q d’un grand nombre
N = p x q lorsque l’on connaît seulement
N. Schématiquement, la connaissance 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, leprotocole RSA deviendrait caduc. Mais il sepourrait 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.
Les méthodes qui, comme le protocole
RSA, font intervenir de la théorie des nombresélaborée, apportent une grande leçon : desCryptage et décryptage …

17

recherches mathématiques (sur les nombrespremiers notamment) tout à fait désintéressées peuvent se révéler, des années ou desdécennies plus tard, cruciales pour telle ou
telle application ; et ce de 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 étaitun fervent pacifiste, se targuait de travailler
dans un domaine parfaitement pur, l’arithmétique, et de n’avoir rien fait qui puisse êtreconsidéré comme « utile ». Ses travaux étaientpeut-être « inutiles » à son époque. C’est fauxaujourd’hui.

Courbes elliptiques : la géométrie
algébrique au service des agents
secrets
Et cela ne concerne pas uniquement lathéorie des nombres. D’autres domaines desmathématiques, auparavant considéréscomme dépourvus d’applications, contribuent
à la science du cryptage. Des méthodes cryptographiques prometteuses et fondées sur desprincipes voisins de ceux du protocole RSA
sont apparues au cours des dernières années.
Il en est ainsi de la méthode dite du logarithme
discret. Celle-ci a servi à son tour à concevoir
des méthodes qui s’appuient sur les propriétés des courbes elliptiques. Il ne s’agit pas decourbes ayant la forme d’une ellipse, mais decourbes dont l’étude a débuté au XIXe siècle
pour résoudre le problème difficile du calcul
du périmètre d’une ellipse. Ces courbes, dont
les coordonnées (x, y) de leurs points vérifientune équation de la forme y2 = x3 + 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é-Le graphe de la courbe elliptique d’équation y2 = x3 + 1.
Les courbes elliptiques ont une propriété remarquable: on peut « additionner » leurs points 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.

trique appropriée, il est possible de définir
une addition entre les points d’une courbe
elliptique. 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.
Une autre direction s’est révélée récemment. Au congrès international des mathématiciens à Berlin en 1998, Peter Shor, deslaboratoires AT & T, obtenait le prix Nevanlinna

L’explosion des mathématiques

18
pour ses travaux sur la cryptographie quantique. Que signifie ce terme ? Il y a quelquesannées, des physiciens et des mathématiciens
ont imaginé qu’il serait un jour possible deréaliser un ordinateur quantique, c’est-à-diredont le fonctionnement exploiterait les lois
bizarres de la physique quantique, celles qui
règnent dans le monde de l’infiniment petit.
Or on s’est rendu compte qu’un tel ordinateur, s’il était réalisable, serait capable de factoriser très vite de grands nombres et rendrait
ainsi inefficace la méthode RSA. Des recherches
visant la réalisation concrète d’un ordinateur
quantique ont d’ailleurs été publiées trèsrécemment, dans la revue britannique Nature(cf. dernière référence ci-dessous). D’un autre
côté, des chercheurs ont élaboré des protocoles de cryptographie quantique, c’est-à-diredes méthodes de cryptage utilisant des objets(photons, atomes,...) obéissant aux lois quantiques. Ces protocoles quantiques pourraient
garantir une sécurité infaillible. Tout cela està l’étude et risque de devenir opérationnel
dans quelques années…
Jean-Louis Nicolas
Institut Girard Desargues, Mathématiques,Université Claude-Bernard (Lyon 1)

Quelques références :• D. Kahn, La guerre des codes secrets(Interéditions, 1980).
• J. Stern, La science du secret (Odile Jacob, 1998).
• S. Singh, Histoire des codes secrets (J.-C.
Lattès, 1999).
• J.-P. Delahaye, Merveilleux nombres premiers(Belin/Pour la Science, 2000).
• D. Stinson, Cryptographie, théorie et pratique(Vuibert, 2001).
• L. M. K. Vandersypen et al., « Experimental realization of Shor’s quantum factoring algorithm using
nuclear magnetic resonance », Nature, vol. 414, pp.
883-887 (20 décembre 2001).