Forum de mathématiques - Bibm@th.net

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

la république de Saint-Marin

Mon cher freddy,

Il y a une anecdote que je voudrais te faire connaître, à toi personnellement, même si c'est un peu confidentiel. Mais je connais ta parfaite discrétion, notre inaltérable amitié, ton inflexible loyauté : je sais que ça n'ira pas plus loin.

Donc, voici l'affaire :

Le 1er avril 1.95. , la femme de ménage de l'attaché militaire de la République de Saint-Marin à Paris trouva, dans la corbeille à papier de celui-ci un brouillon ainsi libellé :

« Rejewski fonda sa stratégie sur le fait que la répétition nuit à la sécurité puisqu'elle entraîne des schémas exploitables par l'adversaire. La répétition la plus évidente de toutes étant celle du groupe-clef ».

Comme c'était les services secrets français qui arrondissaient ses fins de mois, cette dame s'empressa de leur transmettre le document.

Tu t'en souviens sans doute, cette trouvaille intervenait dans un climat politique international extrêmement tendu : les visées expansionnistes de cette république suscitait une vive inquiétude dans toutes les capitales européennes. Bon nombres d'indices étaient des plus inquiétants :

- les capitaines-régents avaient fermé leur frontière,
- un avion saint-marinais avait violé l'espace aérien croate,
- un cryptologue connu, résidant dans ce pays, venait de publier sur Internet un site, étudiant « D'autres rotors pour Enigma », preuve que dans le domaine cryptologique des études étaient activement menées,
- enfin, une épidémie de grippe particulièrement contagieuse avait ravagé ce pays et on se demandait si le gouvernement saint-marinais n'avait pas entrepris des recherches sur les armes bactériologiques.

Bref, l'anxiété était à son comble dans toute l'Europe : le Liechtenstein avait rappelé des réservistes et la très pacifique Principauté de Monaco avait ressorti son canon du hangar où il rouillait depuis des siècles. Malheureusement, un tir d'essai le fit exploser, tuant cinq personnes, dont trois habitués du casino....

Tout ceci t'explique pourquoi le message intercepté offrait un intérêt particulier : d'une part, il confirmait des recherches cryptologiques suspectes, d'autre part, si on le rapprochait d'un cryptogramme correspondant, on pourrait sans doute en déduire des informations utiles sur la cryptographie san-marinaise.

On avait pu savoir que ce pays utilisait la double transposition. On entreprit donc de rechercher, parmi les nombreux cryptogrammes interceptés, celui qui, long de 175 lettres (longueur du texte clair), présenterait les mêmes fréquences.

On n'en trouva aucun !

Heureusement, je veillais ! Je repérai un cryptogramme de 180 lettres dans lequel les fréquences de 21 des lettres de l'alphabet étaient identiques à celles du texte clair en question, alors que les cinq autres (I, N, O, P, T) avaient une fréquence supérieure d'une unité. Je compris tout de suite : le « point » figurant dans le texte clair avait été transcrit en toutes lettres dans le cryptogramme.

Ce cryptogramme était le suivant :

    5        10       15       20       25       30
MNEKR    ESONE    QIITA    ANQXR    RTPTE    TAURS

    35       40       45       50       55       60
SEOTS    PEAID    UFTEA    LDWEC    AULRI    ERCTR

    65       70       75       80       85       90
ASRFU    IPOBI    TRUSA    IEGAH    ETEEN    NDIND

    95      100      105      110      115      120    
PGUIL    ETEEI    EPELS    NETRA    OAAUT    DOELL

   125      130      135      140      145      150
NTJAV    UPLEE    RLEEE    UEIOL    IUVEI    TPPSL

   155      160      165      170      175      180
SSAEC    TTELA    ELTLS    RDFSO    IACIE    ILEDS

 

Grâce à moi, le rapprochement clair-crypto était fait.

Restait à trouver les deux clés de transposition utilisées.

A partir de là, je vais protéger un peu mon exposé.

▼solution

On retint d'abord comme vraisemblable l'hypothèse que les clés de transposition utilisées devaient comporter entre 10 et 20 nombres.  Il serait toujours temps, en cas d'échec, de s'orienter vers des longueurs moins vraisemblables. D'autre part, les chiffreurs san-marinais étant certainement compétents, on pouvait en déduire deux choses :

1) les deux tableaux de transposition n'étaient certainement pas des rectangles parfaits : c'est une règle élémentaire. Ce qui excluait les clés de longueur 10, 12, 15, 18, 20.

2) on avait certainement utilisé des clés différentes pour chacun des deux tableaux de transposition.

Les longueurs de clés retenues étaient donc : 11, 13 , 14, 16, 17, 19. Ce qui donne 6 x 5 = 30 combinaisons différentes de deux clés.

Le chef du bureau de décryptement procéda méthodiquement : il répartit entre chacun de ses six subordonnés les six hypothèses possibles concernant la longueur de clé du premier tableau.

J'héritai du nombre 11. Ce qui donnait, pour le premier tableau la configuration suivante :

     1  2  3  4  5  6  7  8  9  10 11

1    R  E  J  E  W  S  K  I  F  O  N
2    D  A  S  A  S  T  R  A  T  E  G
3    I  E  S  U  R  L  E  F  A  I  T
4    Q  U  E  L  A  R  E  P  E  T  I
5    T  I  O  N  N  U  I  T  A  L  A
6    S  E  C  U  R  I  T  E  P  U  I
7    S  Q  U  E  L  L  E  E  N  T  R
8    A  I  N  E  D  E  S  S  C  H  E
9    M  A  S  E  X  P  L  O  I  T  A
10   B  L  E  S  P  A  R  L  A  D  V
11   E  R  S  A  I  R  E  P  O  I  N
12   T  O  R  L  A  R  E  P  E  T  I
13   T  I  O  N  L  A  P  L  U  S  E
14   V  I  D  E  N  T  E  D  E  T  O
15   U  T  E  S  E  T  A  I  T  C  E
16   L  L  E  D  U  G  R  O  U  P  E
17   C  L  E  F

J'insiste sur un point : la numérotation figurant au-dessus du tableau sert seulement à exprimer commodément le rang de chaque colonne. Elle n'a rien à voir avec la clé numérique, pour l'instant inconnue.

Le nombre-clé 1 (encore inconnu) du premier tableau désigne une colonne qui a été recopiée dans la ligne 1 du deuxième tableau. Donc les lettres de cette colonne (au minimum les 13 premières, puisque 13 est la longueur de clé minimum du second tableau)) deviennent des têtes de colonne dans le tableau 2. Le M qui débute le crypto est forcément une tête de colonne du tableau 2. Or, il n'y a qu'un seul M dans le crypto et, dans le tableau 1, il se trouve dans la colonne de rang 1. C'est donc cette colonne qui a été relevée en premier : Dans le tableau 1, la colonne de rang 1 est de clé 1.

Dans cette colonne, il y a un Q, qui est donc, lui aussi une tête de colonne du tableau 2. Or, il y a deux Q dans le crypto, qui ont rang 11 et 18.

Donc,si l'on retient le Q de rang 11, il faut admettre une colonne de 10, ce qui implique deux hypothèses pour le tableau 2 :

1) une clé de 17 ( 7 colonnes de 10 et 10 colonnes de 11)
2) une clé de 19 (9 colonnes de 10 et 10 colonnes de 9).

Si l'on retient le Q de rang 18, on est conduit à deux hypothèses:

2) une colonne de 17, ce qui impliquerait une clé plus courte que 11, ce qui n'entre pas dans le cadre de notre hypothèse de départ.

3) deux colonnes totalisant ensemble 17 lettres (1 colonne de 9 et 1 colonne de 8), ce qui impliquerait une clé plus longue que 19, ce qui n'entre pas non plus dans notre hypothèse de départ.

Donc, on retient comme tête de colonne (dans le tableau 2) le Q de rang 10 dans le crypto. Alors,  clé de 17 ou clé de 19 ?

le B de rang 69 dans le crypto (lui aussi unique dans le crypto) est aussi tête de colonne (il est en 10ème position dans la colonne 1 du tableau 1).Or, dans le crypto, du Q (inclus) au B (exclu)on a 58 lettres, ce qui est incompatible avec une clé de 17.

Le tableau 2 a donc une clé de 19.

Reportons-nous au tableau 1. Si M est tête de colonne du tableau 2, il faut compter (dans le tabeau 1) 19 lettres en colonne pour avoir la lettre N qui, dans le tableau 2, se trouve sous le M (voir crypto). Si, dans le tableau 1, à partir du M, on compte 19 lettres, on arrive à la ligne 11 du tableau 1. Cette ligne ne comporte qu'un N, dans la colonne de rang 11, dont le nombre-clé est donc 2. Il suffit de raisonner de la même façon pour trouver la colonne de nombre-clé 3, puis celle de nombre-clé 4, etc.... Avec toutefois une réserve : quand on aboutit dans une ligne où il y a plusieurs fois la lettre cherchée, on a une incertitude. J'obtiens ainsi la clé incomplète ci après :

1    9    11    8    10    6    5   ?    ?   ?    2

Mais l'identification de 8 des colonnes lève les incertitudes concernant les trois autres. Exemple : pour la colonne de nombre-clé 3, l'incertitude résultait de ce qu'il y avait trois E dans la ligne 14 du tableau 1. Mais maintenant deux de ces E sont dans des colonnes identifiées, et je peux identifier la colonne de nombre-clé 3.

La clé complète du tableau 1 est :

1    9    11    8    10    6    5    7    3    4    2.

Maintenant, en reportant dans les lignes du tableau 2 les colonnes du tableau 1 dans l'ordre de sa clé, je peux reconstituer le tableau 2 :

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

Il suffit de comparer ce tableau avec le crypto pour rétablir la clé numérique du tableau 2 :

3  10  19  2  7  4  17  14  1  8  15  13  11  16  5  18  6  12  9

Je vais essayer de rétablir les clés alphabétiques. Je commence par la plus longue, en espérant qu'elle sera plus facile. Comme je l'ai toujours soutenu, j'utilise seulement les lettres fréquentes,en ne perdant pas de vue que d'autres lettres seront manquantes. C'est une manière de faire qui n'a pas l'agrément de tout le monde.

3  10 19 2  7  4  17 14 1  8  15 13 11 16 5  18 6 12  9

I  O  U  E  N  L  T  S  A  N  S  R  O  S  L  T  L  O  N

Rien de bien clair! On peut faire plusieurs essais. Je vais retenir « LTLON » en remplaçant les deux L par I, ces deux lettres étant voisines dans l'ordre des fréquences.

3  10 19 2  7  4  17 14 1  8  15 13 11 16 5  18 6 12  9

I  O  U  E  N  L  T  S  A  N  S  R  O  S  I  T  I  O  N

La séquence « T  S  A  N  S  R  O  S  I  T  I  O  N » me permet de  deviner « TRANSPOSITION » et le « OU » de compléter ainsi « DOUBLETRANSPOSITION », qu'il ne reste qu' à vérifier :

3  10 19 2  7  4  17 14 1  8  15 13 11 16 5  18 6 12  9

D  O  U  B  L  E  T  R  A  N  S  P  O  S  I  T  I  O  N

Passons à la clé du tableau 1.

1   9   11   8   10   6   5   7   3   4   2

A   T   U    S   T    O   N   R   I   L   E

Ca ne me dit rien du tout. La recherche d'une clé alphabétique est souvent très difficile : on peut parfois y passer des heures. Je vais essayer de compléter avec des lettres de fréquence voisines et aussi des lettres un peu moins fréquentes :

1   9   11   8   10   6   5   7   3   4   2

A   R   T    O   S    N   L   O   H   I   E
B   S   U    P   T    O   N   R   I   L

On repère « PTOLO ». On essaye « CRYPTOLOGIE », d'autant plus vraisemblable qu'on a trouve une expression de la même " famille" pour le tableau 2.

1   9   11   8   10   6   5   7   3   4   2

C   R   Y    P   T    O   L   O   G   I   E

Ce travail, qui m'avait coûté beaucoup d'effort, se révéla sans utilité : en effet, la population Saint-marinaise, essentiellement accueillante, pacifique et laborieuse , au cours d'une révolution restée dans toute les mémoires sous le nom de « Révolution des Pissenlits », destitua ses capitaines-régents et les remplaça par deux hommes directement issus de l' Armée du Salut.

L' Europe, unanime et soulagée, dit « Ouf ! ».

Dernière modification par nerosson (30-03-2013 13:18:43)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : la république de Saint-Marin

Salut à tous,

Dans le cas où l'un des brillants cryptologues qui fréquentent ce site souhaiterait, en s'abstenant de prendre connaissance de ma solution, faire la même recherche que moi, il serait évidemment équitable qu'il dispose des mêmes éléments.

C'est pourquoi je précise que, étant censé faire partie d'une équipe, et le travail étant réparti entre chacun, je fus chargé uniquement  des recherches partant de l'hypothèse d'une clé de 11 pour le premier tableau.

Bon courage !

Dernière modification par nerosson (28-03-2013 14:50:27)

GeorgeL

Invité

Re : la république de Saint-Marin

Bonsoir

Un outil tres utile pour ce cas de cryptogramme double transposition avec texte clair connu:

http://cryptblog.de/doppelwuerfel/applet/calc.jar

C'est un allemand mais tres simple. Ca reconstruit la cle tres rapidement. C'est teste avec cette example. Ca marche tres bien.

En parallel je travaille sur un programme de Hill Climbing de solution sans texte clair, c'est un cas bien plus difficile, il faut en general un texte chiffre bien plus long que 180.

GeorgeL