Vous avez dit cryptographie ?

Pour ceux qui n’ont pas pu assister à la conférence d’Emmanuel Cepa, voici tout ce que vous avez toujours voulu savoir sur la cryptographie sans jamais avoir osé le demander !

copperh
Opération Copperhead – Jean Harambat – Dargaud – 2018

Emmanuel Cepa est professeur de mathématiques à l’université d’Orléans. Le thème de sa conférence était la cryptographie, c’est-à-dire l’art, la science du codage des messages. Comme Emmanuel Cepa l’annonçait en préambule : « L’histoire de la cryptographie est celle d’un combat sans merci entre ceux qui ont quelque chose à cacher et ceux qui aimeraient bien découvrir ce qu’on leur cache. » (Revue Tangente n°26, 2006). La conférence a commencé par quelques considérations sur les nombres premiers : 2, 3, 5, 7, 11 …etc. Les nombres premiers sont les nombres entiers naturels ne possédant pour diviseurs que 1 et eux-mêmes. Elle s’est conclue par ces mêmes nombres premiers à la base des codages actuels et qui permettent de coder tous nos secrets, de nos codes de cartes bancaires à notre carte SIM, en passant par les transactions diverses qui s’effectuent sur internet.

La conférence s’est appuyée sur l’histoire.

Elle a commencé par le code César, du nom de l’empereur romain, qui consiste en un décalage, d’une ou plusieurs lettres de l’alphabet, des lettres du message qu’on veut coder. A chaque lettre du message initial correspond une seule lettre du message codé. C’est ce qu’on appelle un procédé mono-alphabétique. Pour pouvoir coder toutes les lettres, il faut envisager l’alphabet comme une horloge : après le Z revient le A.

Capture1bis

Le rang du A est donc 0, mais aussi 26, 52, 78… etc. Celui du B est 1, mais aussi 27, 53, 79 …etc. On peut ainsi coder « ORQJWHPSV MH PH VXLV FRXFKH GH ERQQH KHXUH. » la première phrase du plus célèbre des romans français du XXème siècle*.

Le codage affine est du même type : il s’appuie non sur un décalage – on dit une translation en mathématiques – mais sur une transformation basée sur une fonction affine (du type x ® mx+p, x étant le rang de la lettre à coder). Par exemple, à un rang x on associe le rang 3x + 5. Si le rang obtenu dépasse 25, on poursuit en faisant un tour de l’horloge. La place 0 correspond à A et la place 25 à Z. La place 26 sera à nouveau pour le A … etc. On associe en fait à un rang le reste de sa division par 26 de 3x+5 pour coder. Pour décoder, il faut appliquer une autre fonction affine, celle qui à y=3x+5 associe 9y + 7. En effet : 9y + 7 = 9(3x + 5) + 7 = 27x + 45 + 7 = 27x + 52, or en faisant 27x sur l’horloge, on retombe  toujours sur x (vous pouvez essayer !), et ajouter 52 revient à effectuer deux tours d’horloge et à retomber au même endroit, donc sur x.

Les codages mono-alphabétiques ont été « cassés » par le mathématicien arabe Al-Kindi au IXème siècle de notre ère. Voici sa méthode : à chaque lettre à coder correspond une seule lettre codée, et comme chaque lettre possède une certaine fréquence dans chaque langue (la lettre la plus fréquente en français, par exemple, est le E, avec environ 15%, suivie du A…etc.), il suffit de connaître la langue du message, de faire une analyse des fréquences des lettres du message codé et de les ordonner pour leur faire correspondre les lettres de l’alphabet et ainsi décoder le message qui n’est alors plus secret. En cas de doute, le sens ou la grammaire peuvent aider à prendre les bonnes décisions quant au décodage. La méthode d’Al-Kindi était si efficace qu’elle permettait de décrypter tous les messages suffisamment longs issus de codages mono-alphabétiques. Or, imaginer un codage non mono-alphabétique est difficile : si à une lettre à coder ne correspond plus une seule lettre codée, comment arriver à décrypter le message ? Question difficile.

Plusieurs siècles ont passé avant que le premier codage non-mono-alphabétique voit le jour. Il est le fruit des réflexions d’un diplomate français du XVIème siècle appelé Vigenere**. L’idée fut d’utiliser un mot-clé pour coder et décoder un message. Prenons, par exemple, le mot-clé GARE. Imaginons que nous voulions coder DUHAMEL DU MONCEAU. Emmanuel Cepa a utilisé un autre exemple, mais le principe est le même. On écrit sous chacune des lettres du message le mot-clé GARE autant de fois qu’il le faut à la suite :

Capture2bis

Comme pour le codage César, on décale ensuite les lettres à coder, mais cette fois, d’une lettre à l’autre, le décalage change : Le rang du G étant 6, celui du A étant 0, celui du R étant 17 et celui du E étant 4, on augmente le rang de la lettre de 6, 0, 17 et 4 si la lettre à coder est située au-dessus d’un G, d’un A, d’un R ou d’un E, respectivement :

Capture3bis
A noter que les rangs 28, 26 et 31 dépassant 25, on effectue un tour d’horloge (on calcule le reste de la division par 26) et on obtient les rangs 2, 0 et 5 correspondant aux lettres C, A et F, respectivement. Le message DUHAMEL DU MONCEAU est donc codé JUYESEC HA MFRIERY. Le codage n’est plus mono-alphabétique : en effet, le D du message initial est codé une fois J et ensuite H. De même, la lettre Y, du message codé, code une fois un H et une autre fois un U ! Pourtant, pour décoder le message, il suffit de faire l’opération inverse : à partir des lettres codées, il suffit d’effectuer un décalage de -6, -0, -17 ou -4 suivant qu’elle est surmontée d’un G, d’un A, d’un R ou d’un E pour obtenir le rang de la lettre du message initial.

Le message codé dépend du mot-clé : connaissant le mot-clé, vous pouvez coder mais aussi décoder un message. Sans le mot-clé, il est par contre très difficile, voire impossible, de décoder un message secret. La méthode d’Al-Kindi est ici inopérante : le codage n’est pas mono-alphabétique. Mais, si vous voulez que votre message reste secret, votre mot-clé doit l’être aussi. Si on connaît le mot-clé, on connaît le procédé de codage, et on peut en déduire le procédé de décodage. Votre clé doit rester secrète. Il est même conseillé d’en changer régulièrement si on veut réduire les chances que vos messages secrets soient décodés. Un tel procédé est dit à clé secrète. C’est le cas de tous les procédés de codage depuis l’antiquité.

Emmanuel Cepa est ensuite passé au codage par la machine ENIGMA, machine utilisée par le régime nazi durant la deuxième guerre mondiale. Elle se présentait comme une machine à écrire, mais la lettre tapée n’était pas la lettre imprimée. Entre les deux, trois rotors connectés rendaient le codage indéchiffrable. C’est tout au moins ce que pensaient les nazis et les scientifiques à leur service. Le nombre de possibilités était effectivement énorme, de l’ordre de 1016, et la position initiale étant changée toutes les 24 heures, la probabilité de déchiffrer un message aussi complexe en aussi peu de temps quasi-nulle. En Angleterre, une équipe de mathématiciens et de logiciens, placée sous  l’autorité d’Alan Turing, fut montée dans le plus grand secret, avec pour mission de craquer le code ENIGMA. Cette aventure est narrée dans le film Imitation game (2014). En utilisant les bulletins météo de l’armée allemande et certains messages récurrents, cette équipe réussit à diminuer le nombre de possibilités, au point de réussir à craquer la machine ENIGMA en utilisant une machine, appelée depuis « machine de Turing », précurseur des ordinateurs. Cette réussite fut tenue secrète pendant la guerre mais aussi longtemps après. Elle a permis aux alliés contre les nazis de prendre un ascendant certain : tous les messages secrets allemands étaient décodés sans qu’ils le sachent. Elle a permis, entre autres, d’organiser le débarquement en Normandie plus tôt que ce n’aurait été le cas sans elle.

enigmabis
La machine Enigma – © CIA Museum Libre de droits

Malgré sa sophistication, le procédé de la machine ENIGMA était encore et toujours un procédé à clé secrète. La connaissance du procédé a permis à Turing et son équipe de décoder tous ses messages. Il a fallu attendre les années 1970 pour que voie le jour le premier procédé de codage à clé publique de l’histoire : le codage RSA, du nom des mathématiciens Rivest, Shamir et Adleman qui l’ont inventé, au MIT,  dans l’état du Massachussetts aux États-Unis, en 1977.

Le codage RSA repose sur un principe simple : on connaît un nombre n. Toutes les opérations se font en effectuant la division par n et en calculant les restes. On n’est pas très loin du codage César. Le nombre n est connu de tous, c’est pourquoi on parle de clé publique. Mais son obtention est, elle, tenue secrète : n = p×q où p et q sont deux nombres premiers qui restent secrets. La connaissance de p et q permettrait de décoder les messages, mais, comme p et q sont très grands (de l’ordre de 100 chiffres chacun), les trouver à partir de n demande un temps extrêmement long avec les méthodes actuelles, y compris avec les ordinateurs les plus puissants ! C’est la complexité de cette décomposition du nombre n en le produit de p et q qui permet que n soit livré au public.

Le codage est le suivant. Avec p et q, on calcule le nombre m = (p-1) × (q-1). On choisit alors un nombre qu’on notera a, qui ne possède pas de diviseur commun avec m autre que 1 (on dit que m et a sont premiers entre eux). On calcule le nombre b tel que le nombre a×b possède un reste de 1 dans la division par m. Le nombre b est impossible à calculer sans connaître m et donc sans p et q. Ce nombre b reste secret. Le petit théorème de Fermat nous dit que pour tout nombre premier n le nombre an possède un reste valant a dans la division par n, pour tout entier naturel a<n. On utilise ce théorème pour coder un nombre x en un nombre y = x^a , sachant que le reste de la division de y^b par n sera notre x de départ. Autrement dit, connaissant y, on peut en déduire x car :

y^b = (x^a)^b  = x^(ab) = x  [n], le symbole [n] signifiant le reste de la division par n. On dit que y^b est congru à x modulo n. Les clés de codages n et a sont donc publiques. Malgré cela, la complexité de calcul de b fait qu’il reste secret, et sans b, il est impossible de décoder le nombre y.

La force du codage RSA réside dans le fait que la divulgation des clés de codage, n et a, ne fragilise pas le codage qu’elles ont permis. Qui ne possède pas b, ne peut rien décoder. Nul ne sait si demain des algorithmes puissants ne permettront pas de mettre ce codage en péril. Pour l’instant, son principe n’est pas en danger : pour sauvegarder son efficacité, il suffit de choisir p et q plus grands, ce qui est facile car on connaît des nombres premiers bien plus grands que ces nombres p et q. On les appelle des « monstres ».

En conclusion, les nombres premiers, qui sont, comme le dit Emmanuel Cepa, les premiers nombres, pour aussi simples qu’ils soient, sont emplis de mystère et nous permettent de réaliser des prouesses au service de tous. Les mathématiques, et, en particulier dans cet exemple, l’arithmétique, branche des mathématiques dont l’objet est l’étude des nombres entiers, jouent un rôle social prépondérant pour le monde d’aujourd’hui et pour le monde de demain. « Aujourd’hui, la cryptographie est omniprésente. Systèmes informatiques, terminaux de cartes bleues, téléphones mobiles sont équipés de protocoles de sécurité que défient les pirates des temps modernes. Sur ce champ de bataille, les armes sont mathématiques et la plus redoutable se nomme factorisation de grands nombres. ».

Christophe Martin

*« Longtemps, je me suis couché de bonne heure. » première phrase de A la recherche du temps perdu de Marcel Proust.

** Il semblerait que Vigenère n’ait pas été le premier à créer ce type de codage, mais que ce soit une idée initiale de Giovan Battista Bellaso, né à Brescia en 1505, duquel se serait inspiré Vigenère sans citer sa source. L’histoire, parfois injuste, lui donne raison puisqu’on retient son nom, y compris hors de France, alors que nul ne se souvient de celui de Bellaso.

Pour ceux qui voudraient aller plus loin, des ouvrages au CDI (cliquez sur les images pour avoir plus de détails) :

    tangente_180

stewart

secrets

turing

courrierinternational_1054campusS.J.

Une réflexion sur “Vous avez dit cryptographie ?

  1. Jeanty 5 mars 2020 / 18 06 18 03183

    Après avoir lu le compte rendu d Emma et comme nous aimons lire, nous avons envie de lire ce livre.

    Elle commente tellement bien et on sent chez elle tout le plaisir ressenti d avoir lu ce livre.
    Bravo Emma.

    J'aime

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s