Le solitaire de Bruce Schneier

Chapitre: X. Chiffres polyalphabétiques Prérequis: Masque jetable

Le texte ci-dessous est un extrait de la présentation de Bruce Schneier (voir photo ci-contre), l'inventeur de la méthode.

Chiffrer avec Solitaire

Solitaire est un chiffrement de flux avec retour des sorties (OFB). Il est parfois appelé générateur de clef (en vocabulaire militaire). L'idée de base est que Solitaire génère un flux, souvent appelé "flux de clefs" contenant des nombres de 1 à 26. Pour chiffrer, il faut générer le même nombre de clefs de chiffrement que de lettres à chiffrer. Puis, il faut les ajouter modulo 26 aux lettres du texte clair, lettre par lettre, afin de créer le texte chiffré. Pour déchiffrer, il faut générer le même flux de clefs, et soustraire modulo 26, chaque lettre clef du flux chiffré afin de récupérer le texte en clair (ne vous inquiétez pas, je vais expliquer le "modulo" dans un instant).

Par exemple, pour chiffrer le premier message Solitaire mentionné dans la nouvelle de Stephenson, "DO NOT USE PC":

  1. Séparer le message à chiffrer en groupes de cinq lettres (il n'y a rien de magique ici, les groupes de cinq lettres sont une tradition en cryptographie). Utiliser des "X" afin de remplir le dernier groupe s'il comporte moins de cinq lettres. Ainsi, avec la phrase "DO NOT USE PC" le texte à chiffrer devient:

    DONOT USEPC

  2. Utiliser Solitaire pour générer un flux de dix lettres (les détails sont plus bas). Imaginons qu'elles soient:

    KDWUP ONOWT

  3. Convertir les lettres du message en chiffres, A=1, B=2, etc.

    4 15 14 15 20 21 19 5 16 3

  4. Convertir de manière similaire les lettres du flux de clefs:

    11 4 23 21 16 15 14 15 23 20

  5. Ajouter les nombres entre eux, modulo 26 (cela signifie que si la somme est supérieure à 26, on retire 26 du chiffre). Par exemple, 1+1=2, 26+1=27 et 27-26=1 donc 26+1 modulo 26 = 1.

    15 19 11 10 10 10 7 20 13 23

  6. Convertir les nombres en lettres:

    OSKJJ JGTMW

Déchiffrer avec Solitaire

L'idée de base est que celui qui reçoit le message chiffrer doit produire le même flux de lettres de chiffrement, puis soustraire les lettres de ce flux à celles du texte chiffré.

  1. Prendre le message chiffré et le placer en groupe de cinq lettres (il devrait déjà se trouver dans cette forme à la réception).

    OSKJJ JGTMW

  2. Utiliser Solitaire pour générer le flux de lettres clefs, au nombre de dix. Si le destinataire utilise la même "clef" que l'émetteur, alors ce flux sera identique:

    KDWUP ONOWT

  3. Convertir les lettres du message chiffré en chiffres, selon leur position dans l'alphabet:

    15 19 11 10 10 10 7 20 13 23

  4. Convertir les lettres du flux de manière identique:

    11 4 23 21 16 15 14 15 23 20

  5. Soustraire les nombres du flux de clef des nombres du message chiffré, modulo 26. Par exemple: 22-1= 21, 1-22=5 (c'est facile, si le premier chiffre est inférieur ou égal au second, on ajoute 26 au premier nombre avant de réaliser la soustraction, ainsi 1-22 modulo 26 devient 27-22=5).

    4 15 14 15 20 21 19 5 16 3

  6. Convertir les nombres en lettres:

    DONOT USEPC

Comme vous le voyez, le déchiffrement est identique au chiffrement, excepté qu'il s'agit ici d'une soustraction.

Génération des lettres du flux de clefs

C'est ici que se trouve le cœur de Solitaire. Les descriptions ci-dessus sur le chiffrement et le déchiffrement fonctionnent pour tout chiffrement de flux avec retour des sorties, et c'est ainsi que fonctionne RC4. Le mode OFB du DES fonctionne de la même manière. Cette section est ici spécifique à Solitaire, et explique comment ce dernier génère les lettres de son flux de clefs.
Solitaire génère son flux en utilisant un jeu de cartes. Vous pouvez imaginer un jeu de 54 cartes (n'oubliez pas les deux jokers) comme une permutation de 54 éléments. Il y a 54! combinaisons, soit environ 2,3 * 10^71 ordres de cartes possibles. Encore mieux: il y a 52 cartes dans un jeu (sans le jokers) et 26 lettres dans l'alphabet. Ce genre de coïncidence est trop bon pour l'ignorer.
Pour être utilisé dans Solitaire, le jeu de cartes doit contenir 52 cartes, et deux jokers. Ces derniers doivent pouvoir être différenciés (ce qui est commun, celui que je possède a deux cartes joker différentes, la première dispose d'une petite étoile, et la seconde une étoile plus grosse). Appelons le premier joker A, et le second B. Généralement, il y a un élément graphique sur les jokers qui est identique, mais alors de taille différente. Le joker "B sera celui qui a l'élément graphique le plus "gros", ce qui sera facile à retenir. Si cela vous est plus facile, vous pouvez écrire un gros A sur l'un des jokers, mais si la police secrète vous arrête, ils voudront savoir pourquoi.
Pour initialiser le jeu, prenez le dans votre main, face vers vous. Vous devez placer les cartes dans la configuration qui correspond à la clef (nous parlerons de la clef plus tard, c'est une chose différente du flux de clefs). Vous êtes maintenant prêt à générer une chaîne de lettres aléatoire.

Voici comment produire un caractère. Ceci forme Solitaire:

  1. Trouvez le joker A. Déplacez-le d'une carte vers le bas (c'est à dire, échangez-le avec la carte qui se trouve en-dessous de lui). Si le joker A est la dernière carte du jeu, déplacez-le au sommet du jeu.

  2. Trouvez le joker B. Déplacez-le de deux cartes vers le bas. Si le joker B est la dernière carte du jeu, placez le joker B sous la deuxième carte du jeu. Si le joker B est l'avant-dernière carte, placez-le juste sous la première carte du jeu (imaginez que le jeu de cartes est comme une boucle de cartes).
    Vous ne devez pas vous tromper dans l'ordre de ces deux étapes. Avec la paresse, vous aurez envie de juste déplacer les jokers à mesure que vous les rencontrez. Ceci n'est pas gênant, sauf s'ils sont très proches l'un de l'autre.
    Si le jeu de cartes ressemble à ceci avant la première étape: A 7 2 B 9 4 1, à la fin de la seconde étape, il ressemblera à ceci: 7 A 2 9 4 B 1.
    Et si le jeu est ainsi avant la première étape: 3 A B 8 9 6, à la fin de la seconde étape, il devient: 3 A 8 B 9 6.
    Si vous avez un doute, n'oubliez pas que le joker A doit être déplacé avant le joker B. Et soyez attentif lorsque les jokers se trouvent vers le bas du jeu. Si le joker est la dernière carte, imaginez qu'il s'agit de la première carte lorsque vous commencez à compter.

  3. Coupez trois fois le jeu. Echangez les cartes au-dessus du premier joker avec les cartes en-dessous du second joker. Si le jeu est: 2 4 6 B 5 8 7 1 A 3 9, alors après les trois coupes il devient: 3 9 B 5 8 7 1 A 2 4 6.
    Le "premier" joker est le premier rencontré dans le jeu depuis le haut, suivi par le "second" joker, toujours à partir du haut du jeu. Ignorez les appellations "joker A" et "joker B" pour cette étape.
    Souvenez-vous que les jokers et les cartes qui se trouvent entre les deux ne se déplacent pas: ce sont les cartes autour qui se déplacent. C'est assez facile à faire à la main.S'il n'y a pas de cartes au-dessus de l'une de trois sections (parce que les jokers sont adjacents, ou si un joker se trouve comme première carte et l'autre comme dernière carte) alors continuez l'algorithme sans rien faire à cette étape. Si le jeu ressemble à ceci: B 5 8 7 1 A 3 9, après la triple coupe il devient: 3 9 B 5 8 7 1 A
    Un jeu qui ressemble à: B 5 8 7 1 A n'est pas changé par cette étape.

  4. Réalisez une coupe comptée. Regardez la dernière carte. Convertissez la carte en un chiffre compris entre 1 et 53 (utilisez l'ordre de suite du Bridge: trèfles, carreaux, cœurs et piques. Si la carte est un trèfle, prenez la valeur indiquée. Si la carte est un carreau, prenez sa valeur plus 13, si la carte est un cœur, prenez sa valeur plus 26 et si la carte est un pique, prenez sa valeur plus 39. Chaque joker vaut 53). Comptez ce chiffre à partir de la première carte du jeu (je compte de 1 à 13 puis je recommence autant de fois que requis, c'est plus facile). Coupez après la dernière carte que vous aurez comptée, et laissez la dernière carte au bas. Si le jeu ressemble à: 7 ... cartes .. 4 5 ... cartes ... 8 9 et que la neuvième carte était le 4, la coupe produit le résultat suivant: 5 ... cartes ... 8 7 ... cartes ... 4 9.
    La raison pour laquelle la dernière carte est laissée en place est de rendre l'étape réversible. Ceci est particulièrement important pour l'analyse mathématique de la sécurité.
    Un jeu avec un joker comme dernière carte sera inchangé par cette étape.
    Ne vous trompez pas dans le sens lorsque vous comptez les cartes à partir du haut. La manière correcte de compter est de passer chaque carte, une à la fois, d'une main vers l'autre. N'utilisez pas de table ou de piles de cartes.

  5. Trouvez la carte de sortie. Pour ce faire, regardez la première carte du jeu. Convertissez la carte en un chiffre de 1 à 53 comme à l'étape (4). Comptez ce nombre de cartes à partir du haut, en comptant la première carte du jeu bien entendu. Quand vous arrivez à la carte en question, après avoir compté, notez son nom sur un bout de papier: ne retirez pas la carte du jeu (si vous tombez sur un joker, ne notez rien du tout et recommencez à l'étape 1). Voici la première carte sortie. Notez bien que cette étape ne modifie pas l'état du jeu de cartes.

  6. Convertissez la carte sortie en un chiffre. Comme précédemment, utiliser l'ordre des suites du Bridge pour les ordonner. Du plus bas au plus haut nous avons les trèfles, carreaux, cœurs et piques. Les trèfles A à K vont de 1 à 13, les carreaux A à K vont de 14 à 26, les cœurs de A à K vont de 1 à 13 et les piques de A à K vont de 1 à 13 (nous avons seulement besoin d'aller de 1 à 26 et non pas de 1 à 52, car nous voulons obtenir des lettres).

Voici donc comment utiliser Solitaire pour chiffrer un caractère. Vous pouvez l'utiliser pour créer autant de chiffres d'un flux de clefs que requis; il vous suffit de répéter les six étapes, pour chaque caractère à obtenir en sortie. N'oubliez pas que vous aurez besoin d'une lettre en sortie pour chaque lettre du message à chiffrer.

Faire du jeu une clef

Avant de pouvoir commencer à produire vos cartes en sortie, vous devez faire du jeu de cartes une clef. C'est probablement l'étape la plus importante de toute l'opération, et c'est sur cette étape que repose toute la sécurité du système. Solitaire est aussi sûr que la clef. Cela signifie que la manière la plus facile de casser Solitaire est de devenir exactement quelle clef est utilisée pour communiquer. Si vous n'avez pas une bonne clef, rien de ce qui va suivre ne sera utile. Voici quelques suggestions pour procéder à l'échange de la clef.

  1. Mélangez un jeu, au hasard. Puis, classez le second exactement de la même manière. Une clef aléatoire est ce qu'il y a de mieux. Chaque partie dispose d'un jeu complet. Comme la majorité des gens ne savent pas mélanger correctement un jeu, mélangez-le six fois de suite. Ne faites pas la moindre erreur entre les deux jeux de cartes. Aussi, n'oubliez pas que la clef est un danger pour la sécurité tant qu'elle existe: si une police vous arrête et trouve le jeu, elle pourra en copier l'ordre des cartes.

  2. Utiliser un ordre de bridge. Une description de jeu sur papier vous revient à une clef d'environ 95 bits. Soyez d'accord entre les parties sur une manière de prendre le diagramme du Bridge et de le convertir en un ordre de jeu. Puis, soyez d'accord sur comment placer les jokers au sein du jeu de cartes (par exemple, placer le premier joker après la première carte mentionnée dans un texte échangé, et le second joker après la seconde carte mentionnée).
    Faites attention: la police secrète peut trouver votre ordre de bridge et en copier l'ordre. Vous pouvez vous accorder sur une manière particulière d'utiliser les colonnes, par exemple utiliser la colonne Bridge correspondant au numéro du jour où le message a été chiffré, ou quelque chose de similaire. Vous pouvez aussi utiliser des mots clefs du site Internet du New York Times et utilisez la colonne Bridge du jour de parution d'un article dont vous donnez les mots clefs. Si les mots clefs sont interceptés, ils ressembleront à une phrase passe. Et choisissez votre méthode pour convertir les colonnes bridge en ordres de jeu; n'oubliez pas que la police secrète a aussi lu tous les livres de Neal Stephenson...

  3. Utilisez une phrase passe pour ordonner le jeu. Cette méthode utilise l'algorithme Solitaire pour créer un ordre initial de jeu. Aussi bien celui qui envoie le message, que celui qui le reçoit connaissent la phrase passe (par exemple: "CLE SECRETE"). Commencez avec un jeu disposant d'un ordre précis; de la plus basse carte à la plus haute, dans l'ordre des suites du Bridge, suivies par le joker A puis B. Réalisez l'opération du Solitaire sur le jeu de cartes, mais au lieu de réaliser l'étape 5, faire un autre comptage en fonction de la lettre de la phrase passe (3 pour notre exemple). En d'autres mots, faites une nouvelle fois l'étape 4, en utilisant 3 comme chiffre de coupe au lieu de la dernière carte. N'oubliez pas de placer les cartes du haut au-dessus de la dernière carte du jeu, comme avant.

Répétez les cinq étapes de l'algorithme du Solitaire pour chaque caractère de la clef. La seconde fois que vous réaliser l'algorithme, comptez avec la seconde lettre de la clef, etc. Utilisez les deux dernières lettres pour placer les jokers. Si l'avant-dernier caractère est un G (un 7), placez le joker A après la carte numéro 7. Si le dernier caractère est un T (un 20), placez le joker B après la carte numéro 20.

N'oubliez pas qu'il y a en moyenne 1.5 bits d'aléatoire par caractère. Pour un message, cela signifie que vous aurez besoin d'au moins 64 caractères pour rendre le système sûr; je vous recommande 80 caractères, par précaution. Je suis désolé, mais avec une clef plus courte, vous n'aurez pas de sécurité.

Exemples de sortie

Voici un exemple de données pour vous entraîner à Solitaire:

Exemple 1

Commencez par un jeu de cartes sans clef: trèfles de A à K, carreaux de A à K, cœurs de A à K et piques de A à K, avec les jokers A et B (vous pouvez y penser comme allant de 1 à 52, A et B).

Voici comment générer les deux premières sorties. Le jeu initial est: 1 2 3 4 ... 52 A B
Après la première étape (déplacement du joker A): 1 2 3 4 ... 52 B A
Après la seconde étape (déplacement du joker B): 1 B 2 3 4 ... 52 A
Après la troisième étape (la triple coupe): B 2 3 4 ... 52 A 1
Après la quatrième étape (la coupe comptée): 2 3 4 ... 52 A B 1
La dernière carte est un 1, ce qui signifie que nous devons couper une carte. Souvenez-vous que le 1 n'est pas déplacé et le B se place donc une carte avant la fin du jeu, au-dessus du 1.

La cinquième étape ne change pas le jeu, mais produit une carte en sortie. La première carte est un 2, et nous comptons donc deux cartes, jusqu'au 4. La première sortie du solitaire est donc un 4 (et bien entendu, vous ne devez pas retirer cette carte du jeu. Vous laissez le 4 en place, et vous notez un 4 quelque part ailleurs).

Pour produire la seconde sortie de Solitaire, recommencez les cinq étapes.

Première étape: 2 3 4 ... 49 50 51 52 B A 1
Etape 2: 2 3 4 ... 49 50 51 52 A 1 B
Etape 3: A 1 B 2 3 4 ... 49 50 51 52
Etape 4: 51 A 1 B 2 3 4 ... 49 50 52
La dernière carte est un 52, nous comptons donc 52 cartes jusqu'au 51. Nous coupons la carte seule, le 51 avec le reste du jeu. N'oubliez pas: le 52 n'est pas déplacé.

L'étape 5 produit la carte en sortie. La première carte est un 51. Nous comptons 51 cartes, et nous tombons sur 49, qui est la seconde carte en sortie (à nouveau, nous ne retirons pas la carte du jeu).

Les premières dix sorties sont: 4 49 10 (53) 24 8 51 44 6 4 33. Nous passons le 53, bien entendu. Je ne l'ai placé qu'à fins de démonstration.

Si le texte clair est: AAAAA AAAAA, alors il devient: EXKYI ZSGEH.


Exemple 2

En utilisant la troisième méthode de création du jeu clef, avec la clef "FOO,", les quinze premières sorties sont: 8 19 7 25 20 (53) 9 8 22 32 43 5 26 17 (53) 38 48
Et si le texte en clair n'est composé que des lettres A, nous obtenons le texte chiffré: ITHZU JIWGR FARMW


Exemple 3

En utilisant la troisième méthode et la clef "CRYPTONOMICON", le message "SOLITAIRE" est chiffré pour devenir: KIRAK SFJAN

N'oubliez pas que des X seront utilisés pour remplir le dernier groupe de caractères, afin qu'il fasse bien cinq caractères.


Programme javascript

Le programme javascript ci-dessous va vous permettre de vous familiariser avec ce système.

Pour chiffrer ou déchiffrer un message avec la méthode du Solitaire, suivez les instructions suivantes :

  1. Le premier pas consiste à former son jeu de départ. Pour cela, on entre un mot-Clef et en pressant "Clef". ou on clique "Mélange" pour un ordre des cartes aléatoire.
    Pour entrer les cartes manuellement, écrire les valeurs des cartes séparées par une virgule dans le champ "Ordre des cartes" ; si la carte est un trèfle, entrer la valeur de la carte (de 1 à 13); si c'est un carreau, ajouter 13 à la valuer de la carte: pour un coeur, ajouter 26 et pour un pique ajouter 39. Entrer 53 pour le joker A et 54 pour le joker B.
  2. Ensuite, entrer la longueur du message. Si vous n'êtes pas sûr de la longueur, entrer un nombre plus grand.
  3. Cliquer "Générer la clef". Elle apparaitra dans le champ "Flux de clefs".
  4. Pour finir, entrer soit le texte clair, soit le texte chiffré. Choisir chiffrer ou déchiffrer, puis cliquer "Enclencher le processus "

Utliser uniquement des lettres majuscules et ne pas mettre d'espace (au besoin prétraitez le texte).

Mot-clef

Ordre selon la clef ou Mélange aléatoire

Ordre des cartes

Longueur du message:
Générer la clef

Flux de clefs

Texte clair

Texte chiffré

Chiffrer    Déchiffrer    Enclencher le processus


Références


Didier Müller, 10.2.09