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.

Anna Karénine

Le lundi, c’est lecture !

Louise a aimé et nous en parle.

AKAnna Karénine, Léon Tolstoï, 1877.
À la fin du XIXe siècle, Léon Tolstoï écrit Anna Karénine. Cet auteur russe n’en est alors pas à son coup d’essai mais il écrit là un réel chef-d’œuvre. Durant environ 900 pages il décrit la bourgeoisie et les campagnes russes au travers de nombreux personnages. Le lecteur peut avoir au début quelques difficultés que nous verrons juste après. Cependant, nous verrons également que ce livre peut être grandement apprécié des bons lecteurs.

Premièrement, certains pourraient ouvrir le livre et le refermer trois chapitres plus tard. Cela peut être dû à la longueur de ce livre car selon les vitesses de lecture, 900 pages peuvent s’apparenter à plus de onze heures de lecture. Deuxième obstacle à surmonter, le nom des personnages. En effet, ils sont appelés soit par leurs prénoms légaux, soit par leurs surnoms, ou encore par leurs noms de famille. Ainsi, l’un deux est nommé tour à tour Stiva, Stépane Arcadiévitch, Oblonski, ou des mélanges de ces noms. Il est donc au début difficile de bien suivre et comprendre « qui est qui ». Cependant, si l’on s’accroche, on se rend compte que ce livre mérite d’être lu.

Ce livre est très intéressant. Les différents milieux et façons de vivre décrits pat Tolstoï sont extrêmement précis. Ainsi, lorsque Lévine est dans sa campagne et cherche à changer les façons de faire, on a vraiment l’impression d’être dans les champs à ses côtés et on comprend parfaitement le système dans lequel il vit et travaille. Autrement, les allées et venues d’Anna, Vronski, et Alexis Karénine à l’opéra ou chez leurs amis sont narrés avec une réelle précision qui font que, encore une fois, on a l’impression d’y être et on est réellement plongés dans l’histoire. Pour finir, le mariage de Kitty et Lévine est également un passage marquant car pendant plus de vingt pages à leurs côtés, on a réellement en tête le déroulement des cérémonies à cette époque. De plus, Tolstoï donne à ses différents personnages des traits très différents et notre avis à leur propos évolue sans cesse. Nous pouvons ainsi rencontrer Daria une mère exemplaire, Kitty sa sœur qui semble un peu « nunuche » au début mais à qui on s’attache finalement, Vronski un homme égoïste, Anna une femme passionnée mais qui évolue sans cesse, et de nombreux autres personnages. Ils sont tous différents mais on s’attache réellement à eux à force de détails sur leurs façons d’être et de penser. Pour finir, Tolstoï arrive à faire qu’en lisant son livre, on ne sente pas les pages passer. Pour cela, il nous présente de nombreux personnages et fait se mêler différentes intrigues. Ainsi, on passe rarement plusieurs chapitres à la suite sur une même personne, ce qui pourrait être ennuyeux. Par exemple, on observe trois couples très différents qui évoluent chacun à leur façon : Kitty et Lévine, Anna et les deux Aléxis, et Dolly et Stiva. De plus, les lieux changent et alternent entre Moscou, Saint Pétersbourg et les campagnes.
En somme, ce livre est à lire pour les lecteurs motivés, prêts à surmonter quelques difficultés. Mais une fois que l’on est plongé dans l’univers créé par Tolstoï, il est difficile de s’en détacher.
Louise – 2nde2

 

 

Envie d’être surpris ?

Les 13 et 14 février à Montargis (Tivoli) vous pourrez découvrir un ovni théâtral proposé par le Collectif Krumple.

Yokai, Remède au désespoir

Un terrain vide, sans mur ni frontière. De cet endroit posé au milieu de nulle part jaillit une bande de curieux personnages. Profitant de l’instant présent, ces esprits espiègles entrent en collision avec nos existences: Ils jouent à nous représenter le monde à leur manière. Enchevêtrement d’histoires drôles et grinçantes où se mêlent théâtre, danse, marionnette et magie, YŌKAI nous raconte une fable contemporaine sur l’entêtement vain, mais absolu, de vouloir être heureux.  (source : Collectif Krumple)

S.J.

 

 

Huckleberry Finn

Le lundi, c’est lecture !

Aujourd’hui, c’est Alistair qui présente une lecture qu’il a aimée.

M02253136042-largeMark Twain, Les aventures de Huckleberry Finn, 1884.
Les aventures de Huckleberry Finn est un livre de Mark Twain qui parle du jeune Huckleberry Finn et de son aventure avec Jim, ainsi que d’une multitude de personnages aussi fascinants que drôles.

Voici les deux raisons pour lesquelles je vous recommande ce livre.

Tout d’abord, il s’agit d’une histoire fascinante pour tout âge. L’une des principales raisons pour lesquelles je vous recommande cette œuvre de Mark Twain est que ce livre est adapté à tout âge grâce à une écriture peu complexe mais surtout à une histoire fascinante, drôle et intrigante. Pour résumer, c’est l’histoire d’un garçon réalisant un voyage vers la liberté en compagnie de Jim, le noir de Miss Watson. Huckleberry est, au début de l’histoire, pris en charge par  Miss Watson, ainsi que par une veuve, pour se faire « civiliser » après avoir gagné une fortune de 6000 dollars avec son ami Tom Sawyer – cette aventure nous est racontée dans le livre précédent, les Aventures de Tom Sawyer. Mais Huck se fait enlever par son père alcoolique.

Alors qu’il vit dans une cabane dans les bois avec celui-ci, il perd les habitudes que lui ont données la veuve et Miss Watson. Il va, un soir, s’échapper de la cabane alors que son père est parti, en créant une « fausse scène de crime » pour faire croire à son père qu’il s’est fait tuer par des brigands. Lors de son voyage sur un canoë au long de la rivière du Mississippi, il rencontre le noir de Miss Watson, Jim. Ils embarquent ensemble sur le chemin de la liberté. Lors de cette aventure, Huck va découvrir qu’il y a peut-être plus qu’un simple esclave à ses côtés, et que Jim peut être considéré comme un homme au lieu d’un « nègre » (terme employé dans le livre). C’est une histoire simple, captivante, qui peut être appréciée par tout le monde.

De plus, ce roman aborde le sujet de l’esclavage et du racisme. Les aventures de Huckleberry Finn est une œuvre qui est souvent travaillée dans les salles de classe des écoles (en particulier en Amérique) car il touche un sujet sensible : l’esclavage et le racisme. Dans l’introduction, on parle de la jeunesse de Mark Twain et de son opinion négative sur l’esclavage. Il raconte une scène à laquelle il a assisté : des noirs, les mains ligotées, furent embarqués de force sur des navires. Dans l’introduction, il est expliqué comment Twain a, au fur et à mesure, appris que les noirs n’étaient pas que de simples objets de commerce, mais des humains. Les expériences de l’auteur se reflètent à travers le personnage de Huckleberry, qui lui-même va apprendre que Jim est bien plus qu’un esclave. C’est une leçon importante qu’a à apporter le livre de Twain.

Ce livre comporte néanmoins un inconvénient, sans grande importance. Le seul et unique problème que j’ai relevé de cette œuvre est le fait que certaines informations importantes ou certains événements importants de l’histoire surgissent assez brusquement, notamment lorsque le personnage principal se fait enlever par son père. La manière très subite dont ce moment est raconté peut initialement laisser penser que c’est un événement moindre du livre, un détail qui n’a aucun impact sur l’histoire, mais ceci n’est pas le cas. L’enlèvement de Huck est important dans l’intrigue car c’est de là qu’il va avoir envie de s’enfuir. Mais il n’y a rien dans l’histoire qui prépare le lecteur pour cet événement, il n’y a pas de « build-up », et cela peut légèrement brusquer le lecteur.

Mais malgré cet inconvénient, le livre est très bon, je dirais même que c’est l’un des meilleurs que j’ai lu, et je vous le conseille grandement.
Alistair –  2nde2