Forum de mathématiques - Bibm@th.net

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Le Playfair

Dans un forum consacré à la cryptologie, il serait dommage de ne pas consacrer une discussion au célèbre procédé Playfair.

Contrairement à ce que son nom pourrait faire penser, ce procédé fut inventé par Charles Wheatstone, plus connu pour l'invention d'un pont qui n'a jamais enjambé aucun cours d'eau. Wheatstone et Playfair étaient amis et, si le procédé fut découvert par le premier, ce sont les efforts du second pour le faire connaître et apprécier qui aboutirent à son adoption par l'armée britannique qui l'utilisa notamment au cours de la guerre de Crimée et de la guerre des Boers.

D'une conception extrêmement simple, ce procédé n'en est pas moins passablement coriace. Cela tient au fait qu'il s' agit d'un procédé bigrammatique dans lequel deux lettres claires successives sont chiffrées ensemble par deux lettres cryptographiques. Il en résulte que les fréquences littérales ne sont d'aucun secours, les fréquences bigrammatiques présentant beaucoup moins d'intérêt.

La clé de chiffrement est constituée par un carré de 25 contenant un alphabet incohérent d'où l'on a exclu une lettre (en français, généralement le W, dans d'autres langues le J).

En voici un exemple (à gauche, le tableau de transposition montre comment l'alphabet du carré de 25 a été formé à partir du mot-clé « Baudelaire »):

Le processus de chiffrement est le suivant : pour chaque bigramme clair, on recherche la position des deux lettres qui le composent. On peut alors se trouver en présence de quatre cas différents :

Premier cas : les deux lettres ne se trouvent ni dans la même ligne, ni dans la même colonne.

On considère les deux lettres claires comme les angles opposés d'un rectangle. On prend alors comme bigramme cryptographique les deux lettres situées aux deux autres angles de ce rectangle, les premières lettres de chacun de ces deux bigrammes étant sur la même ligne.

Exemple :

« la » clair sera chiffré « IC »                       IMPORTANT : CHIFFREMENT RECI-
« ic » clair sera chiffré « LA »                       PROQUE ENTRE «LA» ET «IC», DE
« al » clair sera chiffré « CI »                       MÊME QU'ENTRE «AL» ET «CI».
« ci » clair sera chiffré « AL »

Deuxième cas : les deux lettres se trouvent dans la même ligne.

Chacune des lettres du bigramme cryptographique sera prise à droite de chacune des lettres du bigramme clair, la dernière lettre de la ligne du tableau étant censée être suivie de la première lettre de la même ligne.

Exemple :

« de » clair sera chiffré « HJ »                                         IMPORTANT : LORSQUE L' ENSEM
« hj » clair sera chiffré « SD »                                         BLE FORME PAR UN BIGRAMME
« je » clair sera chiffré « DJ »                                         CLAIR ET LE BIGRAMME CRYP-
« hs » clair sera chiffré « SE »                                         TO CORRESPONDANT («je» «DJ»
                                                                                    OU «hs» «SE») NE COMPORTERA
QUE TROIS LETTRES DIFFERENTES, ON PEUT EN DEDUIRE QUE CES TROIS LETTRES SONT
CONSECUTIVES DANS LA LIGNE DU CARRE DE 25 (ETANT ENTENDU QUE, DANS CE TABLEAU,
LA PREMIERE LETTRE DE LA LIGNE SUIT LA DERNIERE).

Troisième cas : les deux lettres se trouvent dans la même colonne.

Chacune des lettres du bigramme cryptographique sera prise en dessous de chacune des lettres du bigramme clair, la dernière lettre de la colonne du tableau étant censée être suivie de la première lettre de la même colonne.

Exemple :

« ai » clair sera chiffré « QY »                                     IMPORTANT : LORSQUE L'ENSEM-
« qy » clair sera chiffré « JA »                                     BLE FORME PAR UN BIGRAMME
« yi » clair sera chiffré « AY »                                     CLAIR ET LE BIGRAMME CRYP-
« qj » clair sera chiffré « JI »                                      TO CORRESPONDANT («YI»«AY»
                                                                                OU «QJ»«JI») NE COMPORTERA
QUE TROIS LETTRES DIFFERENTES, ON PEUT EN DEDUIRE QUE CES TROIS LETTRES
SONT CONSECUTIVES DANS LA COLONNE DU CARRE DE 25 (ETANT ENTENDU QUE, DANS
CE TABLEAU, LA PREMIERE LETTRE DE LA COLONNE SUIT LA DERNIERE).

 

Quatrième cas : les deux lettres sont identiques.

Ce cas sera purement et simplement éliminé par l'un des deux artifices suivants :
a) si cela ne compromet pas le sens du clair, on supprime l'une des deux lettres identiques,
b) on les sépare par une lettre rare (en général le K).

De ces deux méthodes, on choisira toujours celle qui est le moins susceptible d' entrainer une ambiguïté pour le déchiffreur.

Exemple :
Suivant comment se présente le découpage en bigrammes clairs :
a) le mot « assassinat » sera découpé comme suit : « as  sa  si  na  t_ » ou « _a  sa  si  na  t_ ».
b) l' expression « il ira à Annecy » sera découpée comme suit : « il  ir  ak  ak  an  ne  cy » ou « _i  li  ra  ak  an  ne  cy ».

Remarquons que, pour une lettre initiale donnée, un bigramme clair a :
a) 16 chances sur 24 d' appartenir au premier cas,
b) 4 chances sur 24 d' appartenir au deuxième cas,
c) 4 chances sur 24 d' appartenir au troisième cas.

Je voudrais proposer maintenant aux cryptanalystes amateurs der décrypter le cryptogramme suivant, chiffré en Playfair, de reconstituer le carré de 25 correspondant et de trouver le mot-clé qui a servi à confectionner l' alphabet qui y est contenu.

JYKCY   SSK FS   UCFBK   CYSPJ   UCKUO   NXVXV   XVESV   LECCT   CTCTH   TUZEC   VXKXV   OKHOX   TFQAB   TNJPU    FSAKX   VAKKG    FKAKC   KCKJP   KG

A cet effet, je leur fournis les indications suivantes :

a) Bien que je n'aie rien fait pour cela, les fréquences des bigrammes clairs se trouvent éloignées de celles fournies par les statistiques. De toutes façons, les fréquences bigrammatiques sont à manier avec des pincettes et n' offrent pas grand intérêt dans le décryptement proposé,

b) l'objet du message est un voyage familial à Madagascar. Je précise cependant, pour éviter les déconvenues, qu' il est inutile d' y chercher les mots « voyage » et « familial ». Ils n'y figurent pas, mais n'en constituent pas moins un indice précieux,

c) mot probable : « Tamatave »,

d) Je souligne que les chances de succès seront beaucoup plus grandes si l'on mène de front le décryptement et la reconstitution du carré de 25,

e) l'alphabet contenu dans le carré de 25 a été formé de la manière classique suivante : on écrit sur une ligne le mot-clé, dont on aura éliminé les répétitions de lettres. Sous cette première ligne, on écrit, en lignes successives de même longueur que la première toutes les autres lettres de l'alphabet, dans leur ordre alphabétique. Ensuite, on relève cet alphabet par colonnes successives de gauche à droite et on le reporte, par lignes horizontales dans le carré de 25. Le carré de 25 figurant à titre d'exemple au début de cette discussion a été réalisé de cette manière à partir du mot-clé « Baudelaire ».

N.B. 1 – Je me permets de suggérer à ceux dont les travaux seraient couronnés de succès de l' annoncer sans publier leur résultat, afin de laisser à des concurrents éventuels la possibilité de poursuivre leurs recherches. Il leur est toujours possible de m'adresser un mail personnel (mention « E-mail ») pour authentifier leur résultat.

N.B. 2 – J'ai constaté une fois de plus au cours de ce travail, qu'il m'était bien plus facile de réaliser un cryptogramme qui, pris isolément, soit  PRATIQUEMENT indécryptable, que de faire un cryptogramme comportant une ou plusieurs « entrées » permettant à un cryptanalyste d' aboutir dans ses recherches.

Dernière modification par nerosson (07-07-2010 17:48:05)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Le Playfair

salut à tous !
Ouaaahhh un Playfair !
Vous aurez cependant remarqué dans le crypto de Nerosson la répétition XVXVXV suivie de très près de CTCTCT...
ça ne doit pas être fortuit tout ça ;)
Autre chose à l'intention de tous ceux qui s'attaqueraient/ront à ce crypto.
Une fois un carré de 25 trouvé il faut savoir que tout carré de 25 obtenu à partir du précédent par rotation de lignes et/ou de colonnes donne le même résultat. C'est une chose qu'il faut garder à l'esprit pour pouvoir trouver le mot-clé qui a servi à la construction du carré (c'est aussi quelque chose que Nerosson a omis de préciser dans sa présentation du système).
Enfin compte tenu de la manière dont le carré a été construit, "classiquement", tel que Nerosson l'a présenté, on peut parfois (pas toujours, donc peut-être pas ici) se faire une idée du "bas" du tableau. C'est comme ça que j'ai décrypté mon premier Playfair en utilisant une technique que j'ai appelée à l'époque "empiler des cubes"...
A l'heure où j'écris ces lignes je suis loin de la solution... Plutôt que "d'empiler des cubes" je vais essayer d'utiliser le mot probable qu'il nous donne...
A suivre...
gielev

Dernière modification par gielev (11-07-2010 06:52:14)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le Playfair

Salut, Gielev,

D' accord en ce qui concerne les carrés déduits de permutations circulaires, j' admets que çà peut compliquer sérieusement la recherche du mot clé. Bien que je n'aie pas fouillé sérieusement le problème, il me semble cependant que la succession alphabétique dans les colonnes du tableau de transposition des lettres qui n'appartiennent pas au mot-clé devrait permettre de retrouver le carré original. Je crois cependant que, si tu trouves un carré de 25 permettant de déchiffrer le message, sans pour autant retrouver le mot-clé, personne ne pourra contester ton succès (auquel je crois, parce qu'avec tous les éléments que j'ai fournis, le problème ne m'a pas paru particulièrement difficile). Mais, comme l'a fait remarquer un jour avec raison Yoshi, mon avis sur ce point peut être biaisé par le fait que je suis l'auteur du problème.

Par contre, pour ce qui concerne les avantages que pourrait apporter la construction classique de l' alphabet, je te rappelle qu'il y a deux manières classiques de construire un alphabet incohérent : une mauvaise et une moins mauvaise. La bonne (pas classique) consistant à remplir le carré de façon totalement aléatoire.

Lors de l'utilisation de l' "ADFGX" par les Allemands en 1917, les Français n' ont trouvé aucune règle de fabrication dans les alphabets qu'ils avaient reconstitués. On pense que les Allemands les construisaient de façon aléatoire ou qu'ils utilisaient une méthode complexe qui n'était pas décelable.

Concernant les deux méthodes classiques, la première est vraiment nulle : elle consiste à ranger dans l'ordre alphabétique toutes les lettres qui ne figurent pas dans le mot clé. Exemple :

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

Il est bien évident que si on place un tel alphabet dans un carré de 25, la majorité des lettres seront rangées dans l'ordre alphabétique et que la séquence "X, Y, Z" se retrouvera presque toujours en fin de tableau, ce qui constituerait une aide précieuse pour le décrypteur.

Mais si tu veux bien jeter un coup d'oeil à l'exemple que j'ai donné au début de mon post précédent, tu verras que cette faiblesse n'existe pas.

Bon courage.

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Le Playfair

salut à tous,
je viens d'envoyer à Nerosson la solution de son crypto "Playfair".
Je l'ai résolu grâce au mot probable qu'il nous a donné, ainsi que d'un autre que j'ai trouvé en examinant le crypto (je m'apperçois à la fin qu'il y en aurait eu un troisième).
Cela m'a permis de placer de façon univoque les uns par rapport aux autres, 4 bigrammes (sur les 5  que j'avais) dans le carré de 25.
Par tâtonnements et en examinant le texte clair obtenu j'ai alors pu progressivement trouver le reste du carré ainsi que le texte clair.
Je n'ai cependant pas la clé de construction de ce carré. Comme je l'ai indiqué dans mon message précédent cela sera délicat à trouver car le carré de 25 que j'ai trouvé n'est pas le seul qui permette le décryptage...
Quoiqu'il en soit je dirais que le crypto est accessible à tout amateur...
Bonne chance !
gielev

Dernière modification par gielev (11-07-2010 10:49:38)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le Playfair

Salut à tous,

Je confirme. Un grand bravo à Gielev ! ! !

Je vais attendre encore quelques jours, puis je publierai ma solution, qui, très probablement, est sensiblement identique à celle Gielev.

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le Playfair

Salut à tous,

Je donne ci-après la solution de l'exercice que j'avais proposé :

Le mot probable « Tamatave » peut se trouver découpé de deux façons :  -t  am  at  av  e-   ou bien :   ta  ma  ta  ve .

Cette dernière étant la plus avantageuse, je l'essaye en premier. On ne peut la situer qu'en un seul endroit :

AK   XV   AK   KG
ta    ma   ta    ve.

Je place ce mot et je reporte dans tout le crypto la traduction des bigrammes ainsi décryptés . D'autre part, dans deux de ces ensembles « bigramme crypto – bigramme clair », il y en a un qui se compose de trois lettres différentes (et non quatre) : « AK/ta ». ce qui prouve, si l'on veut bien se reporter à la description que j'ai faite du procédé, qu'on ne peut pas avoir affaire à un chiffrement du type rectangulaire, mais à un chiffrement du type « linéaire" ou « colonnaire". On doit donc avoir, dans le carré de chiffrement, la séquence « TAK » soit en ligne soit en colonne.

PREMIERE AMORCE DE DECRYPTEMENT /

JY   KC   YS   SK   FS   UC   FB   KC   YS   PJ   UC   KU

ON   XV   XV   XV   ES   VL   EC   CT   CT   CT   HT   UZ
       ma  ma   ma

EC   VX   KX   VO   KH   OX   TF   QA   BT   NJ   PU   FS

AK   XV   AK   KG   FK   AK   CK   CK   JP   KG   
ta    ma   ta    ve           ta                        ve

Si j'observe la séquence :

AK     CK     CK     JP     KG
ta                                 ve

Les données décryptées, plus le redoublement de « CK » me suggèrent « tananarive » et on peut alors faire l'hypothèse « tamatave et tananarive », d'où : FK = et.

D'autre part « XV = ma » (quatre lettres différentes) est probablement un chiffrement  du type rectangulaire :on peut alors en déduire « VX = am ». A partir de ce « am », on peut essayer : am  ad  ag  as  ca  r-.

En outre « ma  ma  ma » peut difficilement s'interpréter autrement que « ma  maman » (je rappelle : voyage familial)

SECONDE  PHASE  DE  DECRYPTEMENT

JY   KC   YS   SK   FS   UC   FB   KC   YS   PJ   UC   KU

ON   XV   XV   XV   ES   VL   EC   CT   CT   CT   HT   UZ
       ma  ma   ma   n

EC   VX   KX   VO   KH   OX   TF   QA   BT   NJ   PU   FS
       am   ad   ag    as    ca    r-

AK   XV   AK   KG   FK   AK   CK   CK   JP   KG   
ta    ma   ta    ve    et    ta    na    na    ri   ve

On a « CK = na » et « PJ = ir ». Pour chacun, quatre lettres différentes, donc forte probabilité d'un chiffrement du type rectangulaire, d'où « KC = an » et « PJ = ir ».

Toutes ce données autorisent une reconstitution partielle du carré de 25 :

    C   N
F  O   E   G
R  H   S
T  A    K   V
    X   D   M

Je précise que l'hypothèse « TAK » en colonne m'a conduit à une impasse dont l'exposé serait fastidieux et superflu. Je crois pouvoir en dispenser le lecteur, qui doit penser que c'est déjà bien assez « austère » comme ça !

Outre les équivalences indiquées ci dessus, la reconstitution partielle du carré de 25 me permet d'enrichir mon décryptement.

TROISIEME PHASE DE DECRYPTEMENT

JY   KC   YS   SK   FS   UC   FB   KC   YS   PJ   UC   KU
      an           es   er                  an          ir

ON   XV   XV   XV   ES   VL   EC   CT   CT   CT   HT   UZ
ec   ma   ma   ma  n            on      a     a     a    ra

EC   VX   KX   VO   KH   OX   TF   QA   BT   NJ   PU   FS
on   am   ad    ag    as    ca   r-                               er

AK   XV   AK   KG   FK   AK   CK   CK   JP   KG   
ta    ma   ta    ve    et    ta    na    na   ri     ve

La séquence claire  « - -ec ma maman e - -on - a - a » me suggère : « avec ma maman et mon papa » et la séquence claire « ara - - on a Madagascar » me suggère « par avion à Madagascar ». Ceci me permet d'en
enrichir le carré de 25 :

P  C  N
F  O  E  G
R  H  S
T   A  K  V  U
L   X  D  M

QUATRIEME PHASE DE DECRYPTEMENT

JY   KC   YS   SK   FS   UC   FB   KC   YS   PJ   UC   KU
      an           es    er   a            an           ir    a     av

ON   XV   XV   XV   ES   VL   EC   CT   CT   CT   HT   UZ
ec    ma  ma   ma   ne   tm   on   pa    pa   pa    ra   vi

EC   VX   KX   VO   KH   OX   TF   QA   BT   NJ   PU   FS
on   am   ad    ag   as    ca    r-                               er

AK   XV   AK   KG   FK   AK   CK   CK   JP   KG   
ta    ma   ta    ve    et    ta    na    na    ri   ve

Je complète la séquence « -esera- » en « je serai ».

Les équivalences « UZ = vi » et « UC = ai » me permettent de placer « Z » et « I » dans le carré :

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

J'ai également « YS = - j ». L'examen des possibilité offertes par le tableau me confirment qu'il s'agit d'un chiffrement rectangulaire, donc que « J » se trouve dans l'une des deux places de la ligne « RHS ». Dans ces conditions, avec trois autres lettres à placer, cela me fait douze tableaux possibles. Je vais donc achever mon travail par ce que l'on appelle (je crois) la « force brute ». Autrement dit je vais réaliser les douze tableaux, et il est bien évident qu'un seul me donnera un texte cohérent :

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

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

C'est le onzième carré qui me donne un texte clair :

JY   KC   YS   SK   FS   UC   FB   KC   YS   PJ   UC   KU
qu   an    dj    es   er    ai    gr    an    dj    ir    ai    av

ON   XV   XV   XV   ES   VL   EC   CT   CT   CT   HT   UZ
ec    ma   ma  ma   ne   tm   on   pa    pa   pa    ra    vi

EC   VX   KX   VO   KH   OX   TF   QA   BT   NJ   PU   FS
on   am   ad    ag   as    ca    rp    ou   rv    is     it    er

AK   XV   AK   KG   FK   AK   CK   CK   JP   KG   
ta    ma   ta    ve    et    ta    na    na   ri    ve

TEXTE  CLAIR :

Quand je serai grand, j''irai avec ma maman et mon papa par avion à Madagascar pour visiter Tamatave et Tananarive.

RECONSTITUTION DU MOT-CLE

Développons l'alphabet du carré de 25.

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

On remarque que la première lettre est suivie de « CNZ » : trois lettres placées par ordre alphabétique, puis le « I » est suivi des deux lettres « FO » : deux lettres rangées dans l'ordre alphabétique, et ainsi de suite jusqu'à la fin de l'alphabet : ceci révèle un tableau de transposition dont la première colonne se compose de quatre lettres, les suivantes se composant de trois lettres  :

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

Mot-clé : PIERRE  BAUD

Dernière modification par nerosson (17-07-2010 17:53:56)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Le Playfair

salut
J'ai mis en ligne sur mon site http://gielev.free.fr une solution détaillée avec le cheminement pour la construction du carré de 25.
C'est pas pour critiquer Nerosson mais en fait quand on a la solution ça paraît toujours plus évident.
En réalité j'ai dû procéder à des ajustements successifs du carré, les lignes ne prenant pas la bonne place de façon immédiate.
Le document sera utile aux néophytes en Playfair, qui y trouveront une façon de raisonner sur ce type de crypto...
Bonne lecture
gielev