Partie 2 : Un problème de cryptographie

Une petite histoire

Pour préparer les questions du présent challenge, les membres de l'équipe ont l'habitude de se communiquer leurs réflexions par e-mail ; on n'en attendait pas moins d'eux ! Mais les messages risquent toujours de traîner sur les ordinateurs du club ; aussi, pour garantir une certaine sécurité, un système de cryptage à clef variable a été mis en place.

Les messages sont envoyés avec une date (celle du jour ?) comme rubrique "objet". Un petit algorithme connu des seuls responsables leur permet de calculer le numéro d’une page lexicale du « Petit Larousse de Poche 2002 » (leur compétence plus que relative en orthographe les a incités à réaliser cet investissement) ; la clef est la première entrée dans la page qui comporte au moins 6 caractères. Le code est un « code de Vigenère » ; le tableau des caractères est reproduit ci-dessous (avec leur décalage associé).

0
à

1
á

2
â

3
ã

4
ä

5
å

6
æ

7
ç

8
è

9
é

10
ê

11
ë

12
ì

13
í

14
î

15
ï

16
ð

17
ñ

18
ò

19
ó

20
ô

21
õ

22
ö

23
÷

24
ø

25
ù

26
ú

27
û

28
ü

29
ý

30
þ

31
ÿ

32

33
!

34
"

35
#

36
$

37
%

38
&

39
'

40
(

41
)

42
*

43
+

44
,

45
-

46
.

47
/

48
0

49
1

50
2

51
3

52
4

53
5

54
6

55
7

56
8

57
9

58
:

59
;

60
<

61
=

62
>

63
?

64
@

65
A

66
B

67
C

68
D

69
E

70
F

71
G

72
H

73
I

74
J

75
K

76
L

77
M

78
N

79
O

80
P

81
Q

82
R

83
S

84
T

85
U

86
V

87
W

88
X

89
Y

90
Z

91
[

92
\

93
]

94
^

95
_

96
°

97
a

98
b

99
c

100
d

101
e

102
f

103
g

104
h

105
i

106
j

107
k

108
l

109
m

110
n

111
o

112
p

113
q

114
r

115
s

116
t

117
u

118
v

119
w

120
x

121
y

122
z

123
{

124
|

125
}

126
~

127
§


On remarquera que ce tableau permet, contrairement aux systèmes classiques à faible nombre de caractères, de communiquer des textes propres (avec caractères accentués et ponctuation). Ce sont des fichiers de textes formatés par paragraphes qui sont transmis : l'application du code est réinitialisé à chaque nouveau paragraphe.

Mais les contraintes du média ont impliqué un transcodage à la norme ISO latin (celle de Windows) : le message donné par un éditeur (p.ex. Bloc-Note de Windows) est au préalable transcrit selon la norme du tableau de codage, puis codé, et retranscrit dans le système ISO.

2.1. Un logiciel de cryptage.

Comme tout cela se fait automatiquement, l’opération est totalement transparente ! Un petit logiciel, doté d’un éditeur, fonctionnant sous Windows (VIGENERE.EXE) réalise facilement ces opérations. (Sur le site du challenge).

travail demandé.

On demande de décrire les routines d’encodage et de décodage. On peut le faire en pseudo-code ou sous forme de routines dans un langage standard (Basic, Pascal, C ou Ada) ; il n’y a aucune contrainte d’interface (nous utilisons la communication des fichiers par le presse-papiers car avec l’éditeur intégré, il ne reste pas de trace, sous forme de fichier enregistré, du message en clair) ; on peut supposer comme acquise la présence du “texte” dans un tableau de caractères.

2.2. Ce qui devait arriver est arrivé !

Avant de partir en vacances, Jean a envoyé à Didier, un message pour lui communiquer le travail à faire ; et ce qui devait arriver est arrivé ! Didier est au local du club, il a laissé son dictionnaire à l’atelier et c'est dimanche ; et les autres membres du groupe ne sont pas joignables. Le voilà donc bloqué ; Jean devait revenir sur les épreuves suivantes : programmation, pentaminos, Monte-Carlo, problème du chien) ; il devait donner les limites de leur cahier des charges, de façon que lui, Didier, puisse faire la première maquette des pages du questionnaire. Et à la dernière réunion, ils avaient dit que l'on pourrait ajouter un peu de cryptage, comme dans le challenge 2002 !

question.

Didier dispose de la source du logiciel VIGENERE.EXE et du compilateur. Après un moment de réflexion, il se dit que tout n’est pas perdu ; et qu’en ajoutant quelques lignes de code au logiciel il doit être en mesure avec un peu de patience, de retrouver la clef perdue ! Quelle a été l’idée de Didier ? Pouvez-vous retrouver cette clef et restituer en clair le message reçu donné dans la copie d’écran (et pour plus de précision en téléchargement, comme fichier de texte : DIDIER.TXT). .

CXcgóRtäRa\éQdaRtVOQóUShóx°VFaiNaõWT/TS[Z[Ob§PãMPZÿéXZ
óexIO_óMSõYX}EMUfN§õ_TâäU^bRaõ_^vMDUXUa#ó2tPVUó\cgó[tW
á\XWbV§X}STìX\bõ_T/TMaféR^YUxGJXX$îcb]/TB_ó]SX[]xUVQ§N
\ió*/MMìfN§V\c/QkYXé^ahb/WJYcUSõddtäDQ_^WõfdáäMQóV]jiT
|IO§óMcõVPåEMUX[îYXï{ëBZarSõWTáRJteNîýZTâXJ[aéRüh]täQU
_N÷õ§PxWáU_égõYPäXáaaNîVfcäGFìcXcgó[xQJ§X[îaXïãIN\féZZ
óatGIQeLVZ!

CXcgó[6IYQeLWXXïâYSì_NîX[XtRíì\Uî[TdãäSQaX\XXa/dáXúRR~
XïàYFìaXchóPåMPZféSjóS6SCX\PSgóo/YOì_RahTVtäEQóUOõV^äV
CQóñQüXbãäU^bYîiXRwRJ]hN÷#ó?pVáObWbgXû/HBZféZZóRpLJQeé
RZfïrLB^ZNa!óX{äGMhM§Vó[xQJ§X[îaXb/TSU§Rb^iTâò

ERScóStäQMe]WXh[xISìf^§õ_T/1PZgNû8Ta{SíìfJc[ó§äIáXú^b^
_XâEUUbWîYúd}äUMUUSjeïtWUìc[w[|apFMQ!é>VeïrSO§eNî_úPxä
QQa\wõsïäRáQkN§X\RtäEQóL§nccpKFìXWîYXdçäUQ§Yaõ-ïsëVZXé
^Vec;äFZó[SeeT}EO§óW]ieT/PPS\LWZ_ï7JBO\USþ.ï°YJ_óN\õTY
~YUMa]îjaT/VFO[N§X[T/HFìVUS[ó÷{IáX\_§ZóStä4UaPVõW^}RFì
_Jîhb[äXJ[aé)õWT/PèMf]cXXû/TB_ó]§}fïãIDTaR_jXû/QPUa\îV
_xpXPUeNîfhT/PèQkN§X\Rtäóü#û÷#ó

BWîVeaxZFìTR\h\ïïäOQóMSbT]sISìd^õjaT/FPZaNîg\VäIV^óR\[
ba|EUUd^S!óbpRTìó]SX[]xGJ§|é^VecxGVX\q§ZÿïuEJ_TKZZóPåI
Dì_NaõV^|TJXT]Sjeb/YTaXUaõûxåIO§hNZaX\tRUìfXchó3^7êúó2
ZõYPäXá]hNîihï°Vj\T[Shó[tWáYTZcZgctWá\b^§õ_P/TS[VQO^aT
/VjaaR]c!

 

bonnes pages du texte de Singh


Autour de 1460, alors qu'il se promenait dans les jardins du Vatican, Alberti tomba sur son ami Leonardo Dato, le secrétaire pontifical, qui souleva dans la conversation quelques points délicats de cryptographie. Cette discussion fortuite décida Alberti à écrire un essai sur le sujet, esquissant ce qu’il pensait être une nouvelle forme de codage. Jusque-là, un chiffrage par substitution ne mettait en oeuvre qu'un seul alphabet chiffré pour crypter un message. Alberti proposa d'utiliser deux ou plusieurs alphabets chiffrés en passant de l'un à l'autre au cours du chiffrement, et par là, de semer la confusion chez des cryptanalystes potentiels.

alphabet ordinaire  a b c d e f g h i j k 1 m n o p q r s t u v w x y z
alphabet chiffré 1  F Z B V K I X A Y M E P L S D H J O R G N Q C U T W
alphabet chiffré 2  G O X B F W T M Q 1 L A P Z J D E S V Y C R K U H N

Nous avons ici deux alphabets chiffrés, et nous pouvons crypter un message en les alternant. Pour crypter hello, nous changerions la première lettre h pour A, selon le premier alphabet chiffré, mais la seconde lettre e, selon le second alphabet, deviendrait F. Pour coder la troisième lettre, nous retournons au premier alphabet chiffré, et pour la quatrième au second. Cela fait que le premier l est codé P, tandis que le second est codé A. La lettre finale o devient D d'après le premier alphabet. Le message chiffré complet est donc AFPAD. L'avantage crucial du système d'Alberti est que la même lettre dans le texte original n'apparaît pas nécessairement comme la même lettre dans le texte chiffré.

Bien qu'il ait effectué, ce faisant, la percée la plus significative dans le cryptage depuis plus de mille ans, Alberti échoua à développer son concept en un système complet. Cette tâche devait revenir à plusieurs chercheurs qui travaillèrent sur ses idées après lui : Jean Trithème, un abbé allemand né en 1462, Giovanni Porta, un savant italien né en 1535, et Blaise de Vigenère, diplomate français né en 1523.

Vigenère se familiarisa avec les écrits de ces auteurs à Rome où, âgé de vingt-six ans, il passa deux années en mission diplomatique. Initialement, son intérêt pour la cryptographie était purement pratique, et lié à son activité diplomatique. Une dizaine d'années plus tard, Vigenère considéra qu'il avait mis de côté assez d'argent pour abandonner la carrière et se consacrer à l'étude. C'est seulement à ce moment qu'il examina en détail les idées d'Alberti, Trithème et Porta, tramant grâce à elles un nouveau chiffre, cohérent et puissant.

Bien qu'Alberti, Trithème et Porta en aient fourni les bases, c'est du nom de Vigenère que ce chiffre nouveau fut baptisé, en l'honneur de l'homme qui lui donna sa forme finale. Sa force réside dans l'utilisation non pas d'un, mais de 26 alphabets codés distincts pour crypter un message. La première étape consiste à construire un carré de Vigenère, tel que montré sur le tableau (…), fait de l'alphabet clair suivi de 26 alphabets chiffrés, chacun d'eux étant décalé d'une lettre supplémentaire par rapport au précédent. Ainsi, la ligne 1 est un alphabet ayant un décalage de César d'une unité, la ligne 2 un décalage de deux unités, et ainsi de suite. La ligne supérieure du carré, en minuscules, est l'alphabet clair, et vous pouvez en chiffrer chaque lettre selon l'un quelconque des 26 alphabets chiffrés. Par exemple, si le numéro 2 est choisi, la lettre a est chiffrée C, mais si l'on choisit le 12, alors le a est transcrit M.

Si l'expéditeur n'utilisait qu'un seul de ces alphabets pour chiffrer le message tout entier, ce serait l'application simple du chiffre de César, c'est-à-dire une forme très faible de cryptage, aisément déchiffrée par un intercepteur ennemi. Mais, le chiffre de Vigenère impose d'utiliser une ligne différente du carré de Vigenère pour crypter chaque lettre. Plus précisément, l'expéditeur pourrait encrypter la première lettre selon la ligne 5, la deuxième selon la ligne 14, la troisième selon la ligne 21, et ainsi de suite.

Pour débrouiller le message, il est important que le destinataire ait connaissance de la ligne choisie pour chiffrer chaque lettre, et donc il doit y avoir un système convenu de passage de l'une à l'autre. Cet accord est obtenu grâce à un mot-clef. Pour voir comment on utilise une clef afin de crypter un bref message, chiffrons la phrase « appeler nord troupes ville », en utilisant « ROUGE » comme mot-clef.

Tout d'abord, le mot-clef est épelé bien clairement au-dessus du message, et répété en boucle de sorte que chaque lettre du message soit associée à une lettre de la clef. Le texte crypté est alors construit comme suit. Pour chiffrer la première lettre, a, commencez par identifier la lettre de la clef placée juste au-dessus, à savoir R, qui détermine une ligne particulière du carré de Vigenère. La ligne commençant par R est la ligne 17, et c'est elle qui va définir l'alphabet à utiliser pour substituer une lettre à la lettre originale a. À partir de là, on repère la colonne commençant par a et l'on voit qu'elle coupe la ligne 17 sur R.

Mot-clef R O U G E R O U G E R O U G E R O U G E R O U
Clair    a p p e 1 e r n o r d t r o u p e s v i 1 1 e
Crypté   R D J K P V F H U V U H L U Y G S M B M C Z Y

Pour crypter la deuxième lettre du message, on recommence. La lettre-clef placée au-dessus de p est le 0 si bien que le codage va utiliser cette fois la ligne 14 du tableau, celle qui commence par la lettre 0 précisément. La colonne p coupe cette ligne sur la lettre D qui est donc la lettre codée correspondant à p du texte en clair. Le mot-clef, par chacune de ses lettres, définit un alphabet chiffré particulier du tableau de Vigenère, et puisqu'il est formé de cinq lettres, l'expéditeur crypte son message en faisant tourner toujours les cinq mêmes lignes du tableau. Donc, pour la sixième lettre du message, on revient à la première lettre de la clef. Un mot-clef plus long ou une phrase-clef feraient intervenir un plus grand nombre de lignes dans la procédure et augmenteraient la complexité du chiffre. Le tableau (…) montre un carré de Vigenère, où les cinq alphabets cryptés définis par la clef ROUGE ont été surlignés.

Le grand avantage du chiffre de Vigenère est qu'il est inattaquable par l'analyse des fréquences décrite dans le chapitre 1. Par exemple, un cryptanalyste appliquant cette technique commencera généralement par identifier la lettre la plus fréquente dans le texte chiffré : dans le cas présent, la lettre U qui apparaît trois fois est mise successivement pour un o ou un d, mais jamais pour un e. C'est un premier problème. Par ailleurs, une même lettre apparaissant à plusieurs reprises dans le texte chiffré, alors qu'elle remplace des lettres différentes du texte clair engendre une ambiguïté terrible pour le cryptanalyste. Dans l'autre sens, mais également troublantes, sont les représentations chiffrées différentes de la même lettre du texte clair. Par exemple, une lettre doublée comme 11 dans ville est chiffrée CZ.

Non content d'être invulnérable à l'analyse de fréquences, le chiffre de Vigenère possède un nombre immense de clefs. L'expéditeur et le destinataire peuvent convenir d'un mot quelconque du dictionnaire, ou même forger des mots. Le cryptanalyste sera incapable de déchiffrer le message en cherchant toutes les clefs possibles, simplement parce que le nombre d'options est trop grand.

clair a b c d e f g h i j k l m n o p q r s t u v w x y z

 1    B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

 2    C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

 3    D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

 4    E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

 5    F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

 6    G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

 7    H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

 8    I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

 9    J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

10    K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

11    L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

12    M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

13    N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

14    O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

15    P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

16    Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

17    R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

18    S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

19    T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

20    U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

21    V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

22    W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

23    X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

24    Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

25    Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

26    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z