Compte rendu de la séance du 26 mars de l’atelier « Protégeons nos vies numériques »

Jeudi dernier a eu lieu la deuxième séance de la série « Protégeons nos vies numériques ». Lors de cette séance nous avons vu, comme prévu, certains méthodes de chiffrement utilisés au XXe siècle et jusqu’à nos jours. La séance était encore animée par Philippe Guillot et Iro Bartzia.

Philippe a commence par un petit récapitulatif sur ce qui a changé dans les méthodes de chiffrement entre la fin du moyen âge et aujourd’hui. Ce qui a certes le plus d’impact est le fait que le chiffrement s’appuie désormais sur des du calcul et non plus des manipulations le la langue écrite, comme les permutations des lettres et/ou de leur place dans le texte.

Un événement déclencheur du développement rapide des méthodes de chiffrement auprès du public au cours du XXe siècle a été la demande de l’administration américaine d’un standard de chiffrement pour les communication non classifiées, notamment pour les échanges d’affaire. Après la fin de la 2e guerre mondiale il est devenu clair que la force d’un chiffre ne réside pas dans le secret de l’algorithme. Même si un algorithme est connu de tous, seul le détenteur de la clé secrète doit être capable de déchiffrer un message.

Une des réponses à cette demande fut celle de Horst Feistel qui était à l’époque employé chez IBM. Ce dernier a proposé son algorithme et celui-ci a finalement été accepté comme standard sous le nom de Data Encryption Standard (DES). L’agence de sécurité américaine NSA a cependant imposé des modifications non négligeables, consistant à raccourcir la taille de la clé et à le renforcer contre les attaques de type différentiel. A cette époque, seule la NSA disposait des moyens de calculs suffisant pour que la force brutale vienne à bout des 56 symboles binaires qui composaient la clé secrète du DES.

Lors de la séance nous avons vu une variante simplifiée du schéma de Feistel et avons effectué quelques exercices d’entraînement au déchiffrement avec ce schéma simplifié.

Philippe et Iro ont par la suite mentionné les principes qu’avaient énoncés Shannon pour qu’un chiffre soit sûr : la confusion (un caractère du texte secret doit dépendre de manière la plus complexe possible de plusieurs caractères du message) et la diffusion (le changement d’un caractère du message en clair doit provoquer changement sur l’ensemble du texte chiffré). A ce principe on peut ajouter un principe ajouté par la suite : une instance de la fonction de chiffrement ne doit pas être discernable d’une permutation aléatoire.

Nous avons vu par la suite quelques principes de base de la cryptographie asymétrique. Les présentateurs nous ont parlé des fonctions à sens unique et de l’algorithme Diffie-Hellman.

Nous avons mis en pratique et sur papier le chiffrement à clé publique en utilisant la méthode du « sac à dos ». Cette méthode utilise une suite super-croissante de 5 nombres (car 25 = 32 > 26 lettres), c’est-à-dire une suite de nombres où chaque terme est supérieur au double du précédent. La suite que nous avons utilisé pour nos exemples a été : 1 3 7 17 35. Ces nombres sont utilisés pour multiplier les 0 et les 1 d’une représentation binaire des lettres.

Chaque lettre de A à Z est encodée comme une suite binaire avec au moins deux 1. Par exemple le A est codé par 00011, le B par 00101, le I par 01101, le M par 10010, et ainsi de suite. Pour chiffrer la lettre A par exemple, nous regardons où le chiffre 1 apparaît dans l’encodage de A et nous faisons la somme de des nombres de la suite super croissante situés à ces positions. Ainsi A, dont les 1 sont aux deux dernières positions devient 17 + 35 = 52, car 17 et 35 sont les nombres situés aux deux dernières positions de la suite super croissante. Le B devient égale à 7 + 35 = 42 et le M = 1 + 17 = 18.

Pour retrouver la lettre à partir de son codage, on utilise la propriété de super croissance. A quelle lettre correspond 45 ? Pour cela, on observe la suite super croissante dans l’ordre inverse, à partir du terme le plus grand et on se pose les questions suivantes : peut-on ôter 35 de 45 ? oui. Soustrayons 35 de 45 et plaçons un 1 en dernière position. 45-35=10. Peut-on ôter 17 de 10 ? non. plaçons un zéro avant le 1. Peut-on ôter 7 de 10 ? oui. Faisons le et plaçons un 1 en 3e position. Peut-on ôter 3 de 3 ? oui. Le chiffre précédent est 1. Enfin, peut-on ôter 1 de 0 ? Non, le dernier chiffre à placer est 0. Le codage binaire est finalement 01101, ce qui correspond à la lettre I.

Le problème avec cette suite est que tout le monde peut faire ces opérations et le codage n’a aucun secret. Pour rendre cette méthode secrète il faudrait utiliser une suite qui ne soit pas super croissante, de sorte que le déchiffrement oblige à explorer toutes les combinaisons, ce qui est impossible dès que le codage est assez long, par exemple 89 67 23 13 15. Il est tout aussi simple de chiffrer. Le A devient 13+15=28, le B devient 23+15=38, le M devient 89+13=102. Par contre retrouver la lettre à partir de son code devient bien plus compliqué. Comme la suite n’est pas super croissante, la méthode exposée ci-dessus ne marche plus. Il faudrait en pratique explorer toutes les combinaisons, ce qui peut être très long.

Heureusement, cette nouvelle suite n’a pas été crée au hasard. En multipliant le code par 9, et en ne retenant que les deux dernier chiffres, on retrouve les codes obtenus avec la suite super croissante ! Remarquons que 28 x 9 = 252, et 52 est justement le code de A avec la suite super croissante ! De même, 38 x 9 = 342, et 42 est le code de B avec la suite super croissante !

Ainsi, pour celui qui connaît le nombre magique par lequel il faut multiplier les codes, le décodage devient facile. Le concept de clé publique est mis en évidence. Tous peuvent chiffrer en utilisant la suite publique 89 67 23 13 15. Mais pour déchiffrer efficacement, il faut multiplier le code obtenu par le nombre secret 9 et utiliser le sac à dos super croissant.

Nous avons terminé par voir une représentation simple du chiffrement RSA. Le chiffrement RSA représente en fait du calcul modulo N. Nous avons pris modulo 33, car nous avons fait les calculs sur papier et donc faire du calcul modulo 33 est bien plus simple que d’autres (car entre autres 100 = 1 [mod 33]).

Pour les valeurs des lettres, nous avons pris leur place dans l’alphabet (A = 1, B = 2, M = 13). Pour chiffrer, il suffisait de lever la lettre à la puissance 7 (utiliser la clé publique) et pour déchiffrer – la lever à la puissance 3 (la clé privée). Les deux opérations se faisaient modulo 33.

Ainsi la lettre B est représenté comme 2. 27 = 128 = 29 [mod 33]. Pour l’opération inverse on fait 293 = 24389 = 2 [mod 33].

L’exposant 7 est public et tous peuvent chiffrer, mais l’exposant 3 est secret et seul son détenteur est capable en pratique de déchiffrer.

Lors de cette séance, à travers d’exemples simples nous avons pu mettre en pratique les algorithmes utilisés par les techniques de chiffrement contemporains, comment le chiffrement asymétrique. L’atelier était un peu différent de celui du 12 mars, dans la mesure où les techniques de chiffrement ont changé et les mathématiques sont à la base des techniques d’aujourd’hui. Cela a chauffé quelques neurones de plus, mais à la fin de la séance, le plaisir du travail accompli y était. Merci à Iro et Philippe d’avoir préparé et présenté ces deux séances qui nous ont permis d’affronter avec plus de sérénité les ateliers pratiques.

Leave a Reply

Your email address will not be published. Required fields are marked *