Partie 2 : cryptographie

 

le code de Vigenère.

L'emploi du code de Vigenère pour l'encodage (ou le décodage) passe par les étapes suivantes :

1. encodage d'une ligne selon le code donné par le tableau ;

2. codage proprement dit (il s'agit d'un calcul de somme modulo 128)

3. restitution de la ligne codée selon le code usuel de Windows.

On suppose évidemment que les seuls caractères utilisés sont ceux du tableau donné dans l'énoncé. On peut par ailleurs légitimement supposer que les fichiers de texte utilisés sont structurés en lignes par les deux caractères traditionnels (iso 10 et iso 13). L'usage de fichier texte ne pose alors aucun problème...

 

1. principe du codage

Le principe de codage est donné ci-dessous sur un exemple :

message

1

.

p

r

i

n

c

i

p

e

 

d

u

 

c

o

d

e

CR

LF

code I

49

46

112

114

105

110

99

105

112

101

32

100

117

32

99

111

100

101

 

 

clef

p

a

p

y

p

a

p

y

p

a

p

y

p

a

p

y

p

a

 

 

code I

112

97

112

121

112

97

112

121

112

97

112

121

112

97

112

121

112

97

 

 

somme

33

15

96

107

89

79

83

98

96

70

16

93

101

1

83

104

84

70

 

 

encodage

!

ï

§

k

Y

O

S

b

§

F

ð

]

e

á

S

h

T

F

 

 

  

 soit le message : 1.principe du code et l'encodage : !ï§kYOSb§Fð]eáShTF

Pour réaliser simplement l'encodages et l'inverser, il est pratique de disposer de deux tableaux :

  

var Encode : array [0..127] of char ;

Decode : array [#32..#255] of integer ;

{ les tableaux Encode et Decode font le passage de la norme ISO à la norme retenue pour l'encryptage}

  

procedure FaireTabEncodeDecode ;

{------------------------------}

var i : integer ; c : char;

begin

  for i := 0 to 31 do Encode[i] := chr(224+i);

  for i := 32 to 126 do Encode[i] := chr(i);

  Encode [127] := #176;Encode [96] := #167 ;

  for c := #32 to #126 do Decode [c] := ord (c) ;

  for c := #224 to #255 do Decode [c] := ord (c)-224 ;

  Decode [#176] := 127; Decode [#171] := 34; Decode [#187] := 34 ;

  Decode [#167] := 96 ;

end;

2. Retrouver la clef.

Si on dispose de l'encodage et du message, il est facile de retrouver la clef en reconstituant le tableau ci-dessus à partir de la première et de la dernière ligne. On a là le principe du cassage du code !

On peut objecter que l'on ne dispose que du code ! Mais en fait on a beaucoup plus de renseignements et ils sont de quatre ordres :

1. on sait que la clef comporte au moins 6 caractères ;

2. que la clef est entièrement faite de minuscules, éventuellement accentuées ;

3. l'objet même du message est connu : on sait qu'il y sera questions de la finalisation des questions précises du challenge ; on peut donc s'attendre à y voir apparaître certains mots comme pentamino, Monte-Carlo, programmation, cryptographie, maquette, cahier des charges ... (peut-être pas tous, ou avec un pluriel...)

4. En ce qui concerne les deux premiers paragraphes, les 5 premiers caractères sont identiques. On peut alors penser qu'en début de phrase (et de message) on va trouver une préposition, ou un pronom ... un mot commun de quatre lettres (Pour, Sans, Dans, Chez, Nous, Vous, Donc...) suivi d'un espace (le cinquième caractère du troisième paragraphe est lui aussi ó)

Pour retrouver la clef, à partir d'un des mots présumés présents comme message, on essaie donc de reconstituer cette clef par "différence". La grosse inconnue est que l'on ne sait pas quelle place occupe le mot supposé présent dans le message réel ; il faut itérer les essais en le plaçant en rang 1, 2, 3 etc. ; ce qui est facilement automatisable. On s'arrête lorsque la suite résultante n'est formée que de voyelles ; on y cherche alors un mot du lexique possible (avec une symétrie circulaire : par exemple oïdalsinusoï pour sinusoïdal) , ou au moins une partie d'un mot du lexique : le choix est alors très restreint.

Une recherche de même type peut être menée en posant que chaque paragraphe se termine par un point ; on obtient 4 lettres de la clef et leur position relative. Le travail peut êtr fait à la main!

Pour illustrer ceci, voici comment on pourrait rechercher le mot principe dans le code ci-dessus, avec une clef faite de voyelles seulement :

encodage

!

ï

§

k

Y

O

S

b

§

F

ð

]

e

á

S

h

T

F

 

 

somme

33

15

96

107

89

79

83

98

96

70

16

93

101

1

83

104

84

70

 

 

essai 1

p

r

i

n

c

i

p

e

 

 

 

 

 

 

 

 

 

 

 

 

 

112

114

105

110

99

105

112

101

 

 

 

 

 

 

 

 

 

 

 

 

 

49

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-79
49

inutile de continuer : 1 ne peut être dans la clef

clef ?

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

essai 2

 

p

r

i

n

c

i

p

e

 

 

 

 

 

 

 

 

 

 

 

 

 

112

114

105

110

99

105

112

101

 

 

 

 

 

 

 

 

 

 

 

 

 

-97
31

-18 110

2

-21 107

-20 108

-22 106

-14 114

-5 123

 

 

 

 

 

 

 

 

 

 

 

clef ?

 

ÿ

n

â

k

l

j

r

{

pas de mot du lexique

essai 3

 

 

p

r

i

n

c

i

p

e

 

 

 

 

 

 

 

 

 

 

 

 

 

112

114

105

110

99

105

112

101

 

 

 

 

 

 

 

 

 

 

diff.

 

 

-16

112

-7

122

-16 112

-31 97

-16 112

-7 121

-16 112

-31 97

 

 

 

 

 

 

 

 

 

 

clef ?

 

 

p

y

p

a

p

y

p

a

mot du lexique : papy

3. Logiciel.

Une version d'encodage/écodage a été proposée en ligne ; pour disposer du système de recherche ; il suffit de l'appeler avec le paramètre sin (PVIGENERE.EXE sin), en minuscules.

Le source de notre réalisation est téléchargeable. Ici également, une grosse partie du code est consacrée à l'interface. La solution est donnée en Pascal (Delphi; fichier de texte d'extension .pas) dont l'écriture des algorithmes est aisément transférabble dans tout langage structuré.

téléchargement :

 

le mot clef était sinusoïdal et le message :


Pour ce qui concerne les épreuves de programmation, je viens de finaliser les trois logiciels. Celui sur les pentaminos est le plus difficile; non pas techniquement ; il serait même plus simple que celui sur le mouvement du cavalier de l'année dernière (gestion d'une pile) mais il y faut une astuce pour limiter le temps le recherche.


Pour l'exercice sur le chien, il faut renoncer à l'idée que nous avions eu d'obliger à un lissage de la courbe (c'est trop technique). Par contre, dans le cahier des charges, il faudra limiter les primitives.


Rien de particulier sur le Monte-Carlo, sauf que l'utilisation d'un tableur est préférable. Par contre j'ai pensé à un exercice de cryptage en deux temps : d'une part, en reprenant notre logiciel (facile); puis en ajoutant une recherche de clef (le livre de Singh donne la solution ; de l'astuce, pas très technique, moins aléatoire que l'exercice 2002).


On arrive ainsi à ne demander qu'une bonne rigueur informatique, sans technicité particulière, faisable avec les compilateurs usuels (éventuellement sous DOS). Il faut que tu prépares les maquettes pour la prochaine réunion.