Solitaire (chiffrement)

Solitaire est un algorithme de chiffrement que l'on peut réaliser avec les mains en utilisant un jeu de cartes et inventé par Bruce Schneier, sur la demande de Neal Stephenson pour son roman de science-fiction Cryptonomicon.

Un des buts de ce système est de pouvoir être utilisé dans un environnement totalitaire, où la possession d'un jeu de cartes est bien moins incriminante que celle d'un ordinateur muni de système de chiffrement^[1].

Paul Crowley a montré en 1999 que la probabilité que deux sorties successives du texte codé soient identiques est plus proche de 1/22.5 que de 1/26 comme on pourrait s'y attendre^[2].

Chiffrement et déchiffrement

L'algorithme génère une suite de valeurs (la clé) qui sont combinées au message pour soit le coder soit le décoder. Chaque valeur de cette suite est utilisée pour un caractère du message. Ainsi, la clé est de la longueur du message.

Le principe de chiffrement est le suivant :

1. Pas de ponctuation, et pas de casse (autrement dit, soit le message est en majuscule, soit en minuscule)
2. Convertir chaque lettre du message en sa valeur numérique correspondante (A=1, B=2..., Z=26). Pour rendre la chose plus ardue on peut prendre n'importe quelle bijection de A, B, C..., Z dans 1, 2..., 26.
3. Pour chiffrer, ajouter chaque valeur de la clé à sa valeur correspondante dans le message, en recommençant à 1 si la valeur dépasse 26 (28 = 2 par exemple)
4. Pour déchiffrer, soustraire chaque valeur de la clé à sa valeur correspondante dans le texte chiffré, en recommençant à 26 si la valeur est strictement inférieure à 1.

Génération de la clé

Pour générer la clé, il faut posséder un jeu de cartes et deux jokers. Pour des raisons de simplicité, seulement deux familles de cartes (sur les quatre) seront utilisées dans la suite. À chaque carte on attribue une valeur : de 1 à 13 pour la première famille (de l'as au roi) et de 14 à 26 pour la seconde (de l'as au roi aussi). Les jokers sont numérotés 27 et 28. Par exemple le valet de la première famille vaut 11 et le 2 de la seconde vaut 15.

On considère que le paquet est une liste circulaire, c'est-à-dire qu'après la dernière carte se trouve la première.

1. Mélanger le jeu. C'est la partie la plus importante car pour un arrangement initial donné, la clé est unique. Ainsi, il suffit que les correspondants aient un jeu de cartes dans le même ordre pour pouvoir communiquer. Une des meilleures façons est de mélanger le jeu parfaitement aléatoirement, quoiqu'on puisse utiliser beaucoup d'autres méthodes. Dans notre exemple, on place les cartes de 3 en 3, modulo 28. Ainsi, on a au départ :
   • 1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26
2. Localiser et faire descendre le premier joker (le 27) d'un rang, c'est-à-dire l'échanger avec la carte qui est sous celui-ci. Ici, on obtient :
   • 1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
3. Localiser et faire descendre le second joker (le 28) de deux rangs.
   • 1 4 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
4. Couper le jeu en trois parties : la première (notée 1) comporte toutes les cartes jusqu'au joker le plus haut (qui n'est pas forcément le 27) est échangée avec la troisième qui comporte toutes les cartes du joker le plus bas à la fin du jeu.
   • 5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 6
5. Regarder la valeur de la carte sous le paquet. Si c'est un joker prendre la valeur 27 (quel que soit le joker). Notons cette valeur n. Prendre les n premières cartes du paquet et les placer juste avant la dernière carte.
   • 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
6. Regarder la valeur de la carte sur le paquet, disons p. Compter p cartes après la première. La p-ième carte sera la prochaine valeur de la clé. Dans notre exemple, ce serait 11. Cette étape ne modifie pas le paquet.
7. Recommencer à partir de l'étape 2 autant de fois que nécessaire.

Références

1. Bruce Schneier, « Solitaire », mai 1999 (consulté le 2006)
2. Paul Crowley, « Problems with Bruce Schneier's "Solitaire" », 1999 (consulté le 30 mai 2007)

Lien externe

• L'algorithme Solitaire sur le site de Bruce Schneier.

• Portail de la cryptologie