Le solitaire de Bruce Schneier
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":
- 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
- Utiliser Solitaire pour générer un flux de dix lettres (les
détails sont plus bas). Imaginons qu'elles soient:
KDWUP ONOWT
- Convertir les lettres du message en chiffres, A=1, B=2, etc.
4 15 14 15 20 21 19 5 16 3
- Convertir de manière similaire les lettres du flux de clefs:
11 4 23 21 16 15 14 15 23 20
- 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
- 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é.
- 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
- 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
- Convertir les lettres du message chiffré en chiffres, selon leur
position dans l'alphabet:
15 19 11 10 10 10 7 20 13 23
- Convertir les lettres du flux de manière identique:
11 4 23 21 16 15 14 15 23 20
- 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
- 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:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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...
- 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.
Exercice
Programmation
Ecrivez
un programme Python qui chiffre et déchiffre un texte en utilisant Solitaire.
Vidéo
Références
Didier
Müller, 15.3.24
