Forum de mathématiques - Bibm@th.net

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Double transpo et force brute

Salut à tous,

Je suis entrain de cogiter sur la possibilité d'un crypto en double transposition que je puisse vous soumettre pour décryptement.  Comme je l'ai déjà dit cent fois, la difficulté n'est pas de faire un crypto, mais d'introduire le ver dans le fruit, c'est à dire de ménager un cheminement qui permettra à un petit futé (s'il y en a un ? …) de décrypter le message, parce que, s'il n'y en a pas, ça sera encore à moi de me farcir un exposé de la solution : comme disait de Gaulle alors que, vêtu d'un survêtement, il prenait le train pour les jeux olympiques de Rome : « Dans ce pays, si je ne fais pas tout moi-même... » (rendons à César ce qui est à César : c'est de Jacques Faizant).

Comme vous le savez tous (soyons charitable...) avec un crypto en double transposition, pris isolément, sans aucun indice, sans accident de chiffrement, sans aucune circonstance favorable, les chances du décrypteur sont pratiquement nulles.

C'est pourquoi, au temps où ce procédé était en usage, la solution consistait pour un service de décryptement à surveiller, avec cette même inlassable patience (qui m'émerveille toujours) du chat qui, les yeux fixés sur une taupinière, attend pendant des heures un frémissement du sol, à surveiller (disait-je) tout le trafic d'un réseau jusqu'à ce qu' apparaisse enfin l'accident de chiffrement tant attendu (maladresse d'un chiffreur, rechiffrement imprudemment réalisé, coïncidence malheureuse, usage de messages stéréotypés, etc...) qui permettra d' ouvrir enfin une brèche .

J'en étais là de mes réflexions lorsqu'une question m'a sauté à l'esprit : avec la fantastique puissance des ordinateurs dont dispose un service comme la N.S.A., serait-il possible de résoudre  une double transposition par la force brute ?

Imaginons un service de chiffre utilisant des clés de transposition de longueur allant de 10 à 20.

Nombre de clés de transposition de chaque longueur :
clés de 10 : factorielle 10 : …..........................3 628 800
clés de 11 : factorielle 11 : …........................39 916 800
clés de 12 : factorielle 12 : …......................479 001 600
clés de 13 : factorielle 13 : …...................6 227 020 800
clés de 14 : factorielle 14 : ….................87 178 291 200
clés de 15 : factorielle 15 : …...........1 307 674 368 000
clés de 16 : factorielle 16 : ….........20 922 789 888 000
clés de 17 : factorielle 17 : ….......355 687 428 096 000
clés de 18 : factorielle 18 : …....6 402 373 705 728 000
clés de 19 : factorielle 19 : ...121 645 100 408 832 000
clés de 20 : factorielle 20 : 2 432 902 008 176 640 000

TOTAL :................................. : 2 561 327 494 111 411 200

La seconde transposition pouvant, elle aussi se faire avec le même nombre de clés, le nombre total de possibilités de chiffrement serait d'environ : 10 puissance 38.

Alors, je vous le demande, ô informaticiens émérites, mathématiciens ayant bac + n, (le « n » étant si grand qu'ils passent directement de la fac à la maison de retraite) : qu'en pensez-vous ?

P.S. Il faudrait aussi que le logiciel comporte un dispositif permettant d'isoler, dès son apparition, parmi toutes ces solutions,  la seule et unique qui donnerait un texte clair, mais je suppose que cela ne doit pas poser de problème.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Double transpo et force brute

Bonsoir,

Ami nerosson, quel plaisir de vous lire à nouveau.

Quand j'ai proposé, il y a un an, un message "avec transposition, sans indice", gielev s'est essayé, puis en novembre GeorgeL a décrypté en "30 secondes" de calcul !

Le "défi" est sans doute tenable même avec une "double transposition"
Mais les programmes utilisés par GeorgeL sont surement hors de notre portée…et très "professionnels"

A+

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Double transpo et force brute

Salut à tous,

@Totomm,

Si j'ai bonne mémoire, il s'agissait d'une transposition simple ?

La double transposition, c'est une autre affaire.

GeorgeL

Invité

Re : Double transpo et force brute

Bonsoir

A la suite du developpement de la methode pour simple transposition, j'ai aussi travaille sur la double transposition. Il y a 2 mois environ j'ai enfin reussi a briser le defi Double Transposition publie par Klaus Schmeh en 2007 dans

http://scienceblogs.de/klausis-krypto-k … challenge/

article en Allemand, et en Anglais aussi dans

https://www.mysterytwisterc3.org/en/cha … nsposition

Les cles etaient de longueur entre 20 et 25.

La methode est assez generale (a) pour cles numeriques aleatoires jusqu'a 18-20 de longueur, (2) cles un peu plus longues mais dans des cas faciles (3) pour cles qui sont des expressions/phrases contenus dans un dictionaire (comme dans le cas de Schmeh, ou j'avais utilise le fameux N-Gram database de Google).

Un peu plus de details dans cet article en Anglais

http://www.haaretz.com/news/national/.premium-1.565074

Si quelqu'un s'interesse au cote algorithmes et informatique je peut donner plus de details en mail prive (y compris une copie de l'article qui sera publie en Avril dans Cryptologia).

George

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Double transpo et force brute

Salut à tous,

@GeorgeL

Pour moi, le plus gros de l'intérêt que je porte à la cryptanalyse concerne le travail, tel que je l'ai appris et un peu pratiqué :  une cervelle, du papier, un crayon.

Je me souviens même que dans les premiers temps où je fréquentais ce site, j'avais lancé une vigoureuse charge contre les logiciels de cryptanalyse, qu'on n'a qu' à lancer et qui font le travail à votre place.

Ces cryptologues-là me font penser à un sportif qui voudrait gagner le Marathon, mais au volant d'une Ferrari !

Je crois même (horresco referens !) avoir quelque peu taillé des croupières à notre Grand Chef Fred sur ce sujet, dans une discussion intitulée "La prière du cryptanalyste", qui doit encore traîner par là quelque part. Il ne parait pas m'en avoir voulu !

Par ailleurs, je lis rarement la littérature étrangère sur ce sujet :
a) pour l' allemand : 95 % insuffisance linguistique, 10 % paresse,
b) pour l' anglais : 95 % paresse.

Je suis un peu surpris qu'un logiciel puisse, en quelques minutes et les doigts dans le nez, décrypter une double transposition.

Je te soumets donc, ci-après, un cryptogramme en double transposition, classique et honnête, mais sans ver dans le fruit (ou s'il y en a un, je ne l'ai pas vu). Le texte clair est français, comme tu pourras le voir au premier coup d' oeil sur les fréquences.

NUTRS  SQTQS  IXIRP  COSRC  TEUEP  SETXI  RVELN  OIFII  STIVR  ETOEI
ECEPS  PNTOE  EHSVU  VTERT  USTVN  ENAOI  ASTEU  HAPAO  ESGER  ENLEI
SNNSE  NLCLU  ESBTU  QAEEI  PQINS  EITUT  NELYT  OVNUN  RTTAX  RESOL
ESLVE  NCUPT  UAEEP  PSIEE  UASUS  MTCES  EESEE  ASESL  GSRSM  UUEIE
NJBAE  SIUEO  TCOEC  MCETC  REAIE  AFCOL  TVTYN  RETDR  NNEML  NQERE
UOOXN

Bonne chance (je m'adresse, bien entendu, au logiciel !).

GeorgeL

Invité

Re : Double transpo et force brute

Bonjour Nerosson

Je suis d'accord mais seulement partiellement:
- Utiliser un programme ecrit par quelqu'un d'autre n'a aucun interet.
- Developper un programme en se basant sur une technique deja publiee allieurs n'as aussi tres peut d'interet.
- Mais developper ses propres techniques et l'implementation d'un tel logiciel est TRES passionnant!.

Pour ne pas commencer un trop grand project de recherche a l'aveugle, quelques petites questions:

1) Les rectangles sont complets? Un des deux rectanges est complet?
2) Peut-on assumer des limites pour les longueurs des cles? par example, 10-15?
3) Les cles sont elles des phrases/mots/expressions ou des cles numeriques aleatoires?

Merci

George

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Double transpo et force brute

Salut à tous,

@GeorgeL

Respectons les principes de Kherkhoffs.

a) le procédé est connu : double transposition,

b) il n'y a pas de rectangle complet : c'est toujours la première recommandation qu'on fait à un chiffreur appelé à travailler sur la transposition à tableau.

c) des décryptements antérieurs justifient les conjectures suivantes :
-  les longueurs de clés semblent varier entre 15 et 25,
-  les deux clés sont différentes pour une même double transposition,
-  ces clés numériques sont obtenues de la manière classique à partir de clé littérales : ( mots, expressions ou phrases
   cohérentes,  qui ne sont pas tronqué(e)s),
-  on n'observe pas de lien logique entre ces différentes clés littérales : ça serait une faiblesse évidente, que personne ne
   commettrait.

GeorgeL

Invité

Re : Double transpo et force brute

Bonsoir

Merci. Je renonce a ce defi, pour 2 raisons:

1) Je n'ai pas de bon dictionnaire de phrases/expressions en francais (comme celui de Google en anglais). Donc mon attaque a dictionnaire n'est pas pratique.
2) Mon algorithme generique ne marche que pour des cles de longueur ~18 et un texte d'au moins 500 lettres. Et comme Nerosson est un excellent cryptographe, pas d'aide non plus du cote rectangle complets.

Je ne suis pas au courrant de l'existence de methodes (manuelles ou logiciel) plus performantes que celles la, qui ont deja ete publiees.

Bonne chance a tous, si quelqu'un trouve une nouvelle methode pour resoudre ce defi, il pourra aussi facilement resoudre les derniers defis Double Transposition qui ont ete publies dans le site MisteryTwisterC3.

Si on veut considerer seulement des methodes manuelles, en general les seules cas abordables manuellement sont les cas de cles tres courtes (< 10) ou avec rectangles complets.

Merci,
George

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Double transpo et force brute

Salut à tous,

Voici le chiffrement qui a donné naissance au crypto proposé à GeorgeL:

1) Texte clair.

Les Egyptiens observent avec une extrême attention toutes les prescriptions religieuses, en particulier celles que je vous rapporte. Leur contrée n'est point infestée de bêtes farouches, les animaux qu'ils connaissent sont tous réputés sacrés, tant ceux qui vivent avec les hommes que ceux qui n'y vivent pas.

2) Premier tableau de transposition.

 P    R   O   T   E   C   T   I   O   N   A   N   T   I  V   I   R   U   S  
 11  12  09  15  03  02  16  04  10  07  01  08  17  05  19  06  13  18  14

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

3) Second tableau de transposition.

 L  E  S  E  S  P  I  O  N  S  S  O  N  T  P  A  R  M  I  N  O  U  S
 06 02 17 03 18 14 04 11 08 19 20 12 09 22 15 01 16 07 05 10 13 23 21

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

4) Cryptogramme.

NUTRS  SQTQS  IXIRP  COSRC  TEUEP  SETXI  RVELN  OIFII  STIVR  ETOEI
ECEPS  PNTOE  EHSVU  VTERT  USTVN  ENAOI  ASTEU  HAPAO  ESGER  ENLEI
SNNSE  NLCLU  ESBTU  QAEEI  PQINS  EITUT  NELYT  OVNUN  RTTAX  RESOL
ESLVE  NCUPT  UAEEP  PSIEE  UASUS  MTCES  EESEE  ASESL  GSRSM  UUEIE
NJBAE  SIUEO  TCOEC  MCETC  REAIE  AFCOL  TVTYN  RETDR  NNEML  NQERE
UOOXN

Il s'agit d'une transposition "normale", c'est à dire :

a) Sans "vers dans le fruit" (voir mon post 1)

2) Sans piège d'aucune sorte.

P.S.

Si on veut considerer seulement des methodes manuelles, en general les seuls cas abordables manuellement sont les cas de cles tres courtes (< 10) ou avec rectangles complets.

A mon avis, c'est un point de vue défendable, si l'on considère un crypto unique et sans anomalie.

Mais permettez-moi de vous parler d'un temps que les moins de soixante-dix ans ne peuvent pas connaître : je l'ai déjà dit : il s'agissait alors de surveiller un réseau en attendant avec patience l' "accident de chiffrement". Un rectangle parfait doit être considéré comme un accident de chiffrement rarissime. Quant à des clés de transposition de moins de dix, je ne crois pas en avoir jamais vu.

Dernière modification par nerosson (08-02-2014 17:22:20)

andredasilva

Invité

Re : Double transpo et force brute

[Edit] by Yoshi - Modérateur
Avant suppression voir http://www.bibmath.net/forums/viewtopic … 355#p50355

Dernière modification par yoshi (04-02-2015 16:08:49)