Le secret des couleurs : algorithmes et cryptographie dans le projet de Karel Martens

par faironniers Stefan et Pierre-Yves

Projet d’article pour le livre « Couleurs sur la plage » chez ÉDITIONS NON STANDARD

Contexte

La Faironnerie ABC est un laboratoire de fabrication numérique, adossé à l’université Le Havre Normandie, qui rassemble et mixe des enseignants-chercheurs en informatique et en mathématiques, des étudiants de masters scientifiques et quelques autres passionnés de l’informatique, de l’électronique et de la fabrication numérique, autour de projets collectifs et collaboratifs. C’est un lieu de partage des connaissances, un outil d’expérimentation pédagogique et pratique, qui propose ponctuellement des ateliers d’initiation ouverts à un plus large public extérieur. Nous définissons cet espace réparti entre différents bâtiments du campus comme « une localisation physique de l’utopie ».

Les sciences occupent une place importante dans le travail de création de Karel Martens : symétrie, effets optiques ou cinétiques, et contraintes mathématiques traversent régulièrement le processus de conception de ses œuvres. Dès l’élaboration du projet, Karel Martens avait ainsi précisé que la distribution de son motif dans le champ des cabanes nécessiterait un traitement scientifique des règles du jeu définies au préalable. Couleurs sur la plage aurait pu être réalisé sur la base des seules décisions du designer au prix d’un travail considérable, ou reposer sur une allocation aléatoire des motifs. Mais le travail de Karel Martens obéit souvent à un double principe : emprunter le chemin de la complexité pour aboutir aux formes les plus simples et traiter dans une continuité totale processus et formes finales.

De façon à ancrer toujours plus fortement ce projet sur son territoire, Karel Martens a souhaité par ailleurs que cette collaboration scientifique puisse s’appuyer sur des compétences de l’université Le Havre Normandie, qui avait présenté et défendu ce projet auprès de Jean Blaise, commissaire désigné par la Ville pour l’événement Un été au Havre 2017.

C’est à ce titre que nous avons été sollicités par Pierre-Yves Cachard, car la Faironnerie ABC travaille depuis deux ans avec la bibliothèque universitaire sur des projets d’installations proposant à un large public des expériences sensibles à partir de phénomènes scientifiques singuliers (bioluminescence, cinétique, marche aléatoire, solides de Platon, etc.). Il faut reconnaître que cette proposition de contribution s’accordait idéalement avec les pratiques et les aspirations de la Faironnerie. Nous partageons certains de nos équipements et projets avec l’Ecole Supérieure d’Art et Design Rouen Le Havre (ESADHaR), et les points de contact entre art et sciences nous passionnent.

A l’issue de la présentation des règles du jeu, nous avons d’abord défini ensemble le périmètre de notre contribution, en deux volets :

  • le développement d’un algorithme de distribution des bandes de couleur sur les cabanes ;
  • des outils de visualisation 2D / 3D et de génération automatique de documents.

Modèle

À chaque face de cabane sont appliquées deux bandes verticales de couleur et de largeur spécifiques. Les 10 couleurs et les 6 largeurs choisies par l’artiste produisent donc 60 bandes différentes possibles. Les faces « invisibles » et les cabanes qui ne participent pas au projet ont une couleur virtuelle dans notre modèle, car l’atlas devait produire un état « idéal » : cas où toutes les cabanes participent au projet et où l’ensemble des faces des cabanes pourrait être peintes1.

Pour réfléchir et communiquer sur le modèle nous avons très vite adopté une représentation aplatie en deux dimensions.

Représentation aplatie

Représentation d’une cabane avec 8 bandes numérotées. À noter que les informaticiens comptent toujours à partir de 0.

Le choix des bandes sur chaque cabane était déjà soumis à quelques contraintes définies par Karel Martens. Tout d’abord les 8 bandes devaient utiliser 8 couleurs différentes. Étant donné que nous disposions de seulement 6 largeurs pour 8 bandes, il y avait obligatoirement par contre des bandes de la même largeur. Pour minimiser ces répétitions, il a été convenu que chacune des 6 largeurs serait donc utilisée une ou deux fois par cabane. Cela signifiait que 4 largeurs apparaîtraient une fois et 2 largeurs deux fois. Enfin, ces doublons ne devaient pas être sur la même face, c’est-à-dire les paires de bandes 0-1, 2-3, 4-5 et 6-7 ne devaient pas avoir la même largeur.

Un peu de combinatoire

La première demande de Karel Martens portait sur l’absence de répétition dans l’Atlas complet : était-il possible de faire en sorte que chaque cabane soit unique tout en respectant les contraintes de distribution énumérées ci-dessus ? Avec quelques arguments simples on en fit très vite la démonstration.

On peut choisir n’importe laquelle parmi les 10 couleurs pour la bande 0. Quand la couleur de la bande 0 est fixée, il nous reste 9 choix pour la bande 1 et ainsi de suite. On a donc

choix de couleurs possibles pour une cabane. Pour les largeurs le raisonnement est légèrement plus compliqué, mais il n’est pas très difficile de montrer qu’il y a 112 320 choix de largeurs. En combinant chaque choix de couleurs avec chaque choix de largeurs on obtient donc quelques 203 milliards de cabanes uniques ! Si on mettait toutes ces cabanes l’une à côté de l’autre sans laisser de la place pour le passage, elles couvriraient une surface équivalente à celle de l’Inde. Et si on les empilait les unes sur les autres, la hauteur de la tour ainsi obtenue serait égale à 2,7 fois la distance de la Terre au Soleil. Nous avions donc au départ beaucoup (trop) de choix possibles pour nos 713 cabanes.

Pour introduire encore plus de diversité, nous avons alors proposé à Karel Martens d’ajouter une contrainte supplémentaire : deux bandes visibles côte à côte ne devaient avoir ni la même couleur, ni la même largeur.

Deux cabanes voisines

Deux cabanes voisines A e B sur la même rangée. Les bandes A1 et B0 n’ont pas la même couleur ni la même largeur. Idem pour B5 et A4.

Cela a réduit ainsi un peu le nombre de choix possibles mais nous restions tout de même dans le même ordre de grandeur.

Un message caché

Nous nous sommes donc très vite concentrés sur la conception du système de distribution, dans l’objectif de raconter une histoire à travers ce principe de double allocation (couleur/largeur). Nous avons décidé de cacher un message que seul un œil (très) averti pourrait voir, tout en gardant l’apparence aléatoire de la coloration. Et à l’occasion des 500 ans du Havre, quel meilleur message que le décret de fondation du port signé par François Ier ? Un choix métaphorique et circonstancié, mais qui rejoint au final, nous l’avons appris depuis, une autre caractéristique du travail de Karel Martens : imprimer sur le passé.

La « traduction » de ce texte en séquence de bandes colorées posait toutefois deux problèmes. Tout d’abord il est trop court. Pour s’en rendre compte, mesurons l’information en bits. Un bit est l’unité de mesure de base de l’information. C’est l’unité la plus simple dans un système de numération qui ne peut prendre que deux valeurs souvent notées par 0 et 1. En répondant par « oui » ou par « non » à une question ou en annonçant le résultat d’un tir à pile ou face, on transmet un bit d’information. Avec 2 bits nous avons 4 valeurs possibles : 00, 01, 10 et 11. Avec 3 bits le nombre de valeurs possibles est 8 et ainsi de suite. Avec \(n\) bits on peut représenter \(2^n\) valeurs différentes. En décrivant une bande on transmet un peu moins de 6 bits d’information car il y a 60 bandes possibles (10 couleurs \(\times\) 6 largeurs) et c’est un peu moins de \(2^6=64\).

Nous avons vu qu’il y a environ 200 milliards de combinaisons de couleurs et de largeurs pour chaque cabane. Cela signifie que pour décrire une cabane nous avons besoin de 38 bits (\(2^{38}\) est proche de 200 milliards). Cela donne environ 27 000 bits pour toutes les 713 cabanes. Or, le décret de François Ier fait 3 354 caractères. En comptant les lettres, les espaces et les caractères de ponctuation nous avons environ \(2^5=32\) caractères différents. Un caractère porte donc 5 bits d’information ou environ 17 000 bits pour le document entier ce qui est inférieur aux 27 000 bits nécessaires pour décrire toutes les cabanes.

Même si le décret de François Ier était plus loquace, un deuxième problème se poserait. Certaines lettres comme ‘e’, ‘a’ et ‘i’ sont beaucoup plus fréquentes que d’autres comme ‘k’, ‘w’ et ‘z’. Cela introduirait forcément un biais et on verrait certaines bandes beaucoup plus souvent que d’autres. On perdra donc l’apparence aléatoire de la coloration.

Quand la cryptographie s’en mêle

Pour contourner ces deux problèmes, nous avons fait appel aux fonctions de hachage, une technique souvent utilisée en informatique et en cryptographie. Une fonction de hachage est une fonction particulière qui, à partir d’une donnée fournie à l’entrée, calcule une empreinte permettant d’identifier la donnée initiale. Ces fonctions ont des propriétés spécifiques selon les applications.

Une application typique en informatique est la recherche rapide de données. Imaginons un dictionnaire dans lequel les mots ne sont pas classés par ordre alphabétique et qui a plus de pages que d’articles. Une fonction de hachage calcule un numéro de page à partir d’un mot. Il est possible d’avoir des collisions (même numéro de page pour deux mots différents) mais notre fonction est conçue de façon à ce que ces collisions soient rares et on n’aura pas plus de 2-3 mots par page. Quand on veut chercher la définition d’un mot, on applique la fonction de hachage sur le mot et elle nous donne rapidement le numéro de la page à laquelle il faut chercher.

Les fonctions de hachage cryptographiques possèdent quelques propriétés spécifiques :

  • il est très difficile de trouver le message initial à partir de son empreinte ;
  • il est très difficile de trouver deux messages avec la même empreinte ;
  • le moindre changement dans un message change complètement son empreinte.

Par très difficile, on entend pratiquement impossible. La seule façon connue d’attaquer ces fonctions est la force brute : générer tous les messages possibles, calculer leurs empreintes et comparer avec l’empreinte donnée, ce qui demande un temps de calcul énorme se mesurant en années, voire en siècles.

Une application typique de ces fonctions est l’authentification par mot de passe. Pour des raisons de sécurité on ne stocke jamais les mots de passe en clair, on stocke leurs empreintes à la place. Pour identifier un utilisateur, l’ordinateur calcule l’empreinte du mot de passe qu’il lui fournit et la compare avec l’empreinte stockée. Les propriétés des fonctions de hachage rendent l’accès au système très difficile même pour un individu mal intentionné qui a réussi à voler les empreintes stockées.

Voici un exemple de deux messages et leurs empreintes :

"Le Havre 2017" -> 309c191c9d7206ddba9d2c6e1f418511
"Le Havre 2018" -> 0e767b20a48ac9c3c47b757484959c7c

Dans cet exemple, on utilise la fonction de hachage MD5 qui produit une empreinte de 128 bits à partir d’un message de taille quelconque. L’empreinte est écrite en hexadécimal : les bits sont regroupés quatre par quatre et chaque quadruplet est représenté par un chiffre (0-9) ou une lettre (a-f). On voit qu’en changeant un seul caractère dans le message on obtient une empreinte complètement différente. Cette différence est due à ce qu’on appelle effet avalanche, les changements se propagent rapidement pendant le calcul de l’empreinte et à la fin chaque bit de l’empreinte dépend de chaque bit du message.

Ce qui nous intéresse dans les fonctions de hachage cryptographiques est leur capacité de produire des empreintes d’apparence aléatoire et le lien invisible à l’œil nu mais bien existant entre le message et son empreinte.

Il nous restait tout de même un dernier petit problème à régler. Les empreintes produites par les fonctions de hachage ont une taille fixe, typiquement entre 128 et 512 bits, mais comme nous avons pu le constater, la description d’une cabane nécessite 38 bits. Même en utilisant SHA-512 qui, comme son nom l’indique, produit une empreinte de 512 bits, c’est suffisant juste pour 13 cabanes. La solution fut donc de découper le texte en petits morceaux de quelques mots et d’associer chaque morceau à un groupe de cabanes. Les plus petits rangées ont un seul morceau de texte associé, les rangées de plus de 13 cabanes ont 2, voire 3 ou 4 morceaux associés en fonction du nombre de cabanes. On a calculé l’empreinte de chaque morceau et utilisé celle-ci pour déduire la coloration des cabanes associées. Ainsi, en partant de Sainte-Adresse, les promeneurs les mieux informés peuvent « lire » l’empreinte laissée par le décret de François Ier sur les couleurs de Karel Martens.

Empreinte transformée en bandes

Le début du texte est associé au premier groupe, épi 6. L’empreinte SHA-512 de ce ce premier morceau est transformée en couleurs et largeurs pour les cabanes.

Conclusion

Reconnaissons qu’un observateur se promenant sur la plage verra surtout une belle symphonie de couleurs d’aspect aléatoire sans aucun motif particulier apparent. En comptant les différents types de bandes utilisées, on se rend compte que les couleurs et les largeurs apparaissent avec des fréquences très proches. En calculant la quantité de peinture nécessaire, nous avons constaté que les surfaces couvertes par les différentes couleurs sont très proches, ce qui indique également une distribution uniforme des bandes.

Si notre promeneur connaît notre modèle, mais pas le texte qu’on a utilisé, il sera impossible pour lui de deviner ce texte. Mais s’il connaît à la fois notre technique et le texte que nous avons utilisé, il pourrait être en mesure de calculer l’empreinte du texte et de vérifier si les consignes de peinture ont été bien respectées.

L’une des conséquences bénéfiques de ce travail de modélisation est qu’il a permis d’accélérer et de faciliter la mise en œuvre de ce projet complexe : à partir des données collectées et la coloration générée, la Faironnerie a pu calculer aisément les litres de peinture à prévoir pour chaque couleur présente. Nous avons également généré l’Atlas souhaité par Karel Martens, ainsi que les guides de peinture : 598 pages essentielles, permettant de représenter à la fois toutes les couleurs à peindre, par ligne de cabane, mais aussi d’isoler chaque couleur dans une ligne de façon à rationaliser la mise en peinture.

L’unicité des cabanes n’est pas inclue explicitement dans le modèle. Nous avons compté sur le hasard et sur le très grand nombre de possibilités. Au final, toutes les cabanes sont uniques et même plus, aucune paire de cabanes ne partage le même ensemble de bandes (même sans prendre en compte leur ordre).

Travailler sur ce projet fut une expérience très intéressante et enrichissante pour les faironniers. Nous voudrions remercier Karel pour sa disponibilité et sa générosité qu’il a montré lors de nos nombreux échanges. Nous sommes très contents d’avoir mis nos connaissances scientifiques au service de l’art et très fiers d’avoir participé dans ce beau projet partagé avec la communauté des cabanistes, les peintres de l’AHAPS, du CFA Baie de Seine et du lycée Robert Schumann.

Liens

  1. Les cabanes sont distribuées en lignes et implantées de façon si serrée que cette proximité rend invisible les façades latérales de chacune des constructions, à l’exception bien sûr des cabanes situées à chaque extrémité d’une ligne. 

Nous contacter

Vous pouvez nous contacter à cette adresse ou utiliser le formulaire ci-dessous.