Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 06-08-2020 14:03:39
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Nouveau procédé de chiffrage à tester : CUBE
Bonjour,
Objet du post
Nouveau sur le forum, passionné (mais pas expert) par les techniques de chiffrage "classique", je voudrais vous soumettre un procédé original de chiffrage papier crayon de ma conception : CUBE.
L'idée étant d'avoir votre avis sur la sécurité, la technique, et des idées d'améliorations...
Je remercie d'avance ceux qui voudront bien se prêter au jeu, et qui auront le courage de finir ce petit pavé :)
Suivant les préconisations de @Rossignol tirées du Military Cryptanalytics, et allégées vous trouverez ci-dessous :
1) un crypto assez long (399 caractères)
2) une même phrase chiffrées de 3 façons différentes (40 caractères)
La description du procédé avec un exemple.
Je peux au besoin vous fournir autre chose mais ça reste du papier crayon donc ne n'irai pas jusqu’à chiffrer un livre entier^^
Textes chiffrés
/!\ à bien différencier 0 et O. Si besoin copier coller le texte dans une autre police.
1) Issu de la littérature française, comportant des lettres et 4 chiffres. Chiffré à partir d'un même sommet, donc de la façon la plus simple (voir description du procédé).
RSDBZ TATIJ GURFA CBBJ1 OHPT9 POMSR XGLZW CXDBV SCBSO 4TCM8 CBB7F HY2VR QFNBD DJS22 DIKSD ETCJ7 KKT3P VD9HN 0QRBT 39XL0 AVG05 RIIJ7 K2LOJ MNC3O 2CLJI LJM59 HUZND BSOVH C2DIA GC2CL 937JS NCDQM BBJ3E GGAGH AZQIK QN0QR ZH5FH YEBBJ KED3I PXW2S X9PTJ MRFVB 9D7PD RGEDH HBBBR EBXBS OCNEB XO9H7 AWXJA L7HY9 XOFER ZXDAX XCXDF 7RGRI 0XGRS BEVDJ PNFC3 0NDBS OJQSZ PGJ7Q 0HU4X CBDRB BDMEF K729Q NGNIZ TC3SQ 2BKVT C3HRA SCCTL 0WR0T 37HRW TIJMD ZPGAT CM8CA HQFGY F7QJM DGQI9 QNRS2 2L39P O2FQ
2) Issu de la littérature française (que des lettres).
OXN02 4NWA9 K9NFD 0WXL6 VN5UY JA7KP TUXMS FNWIX F9
=
VBNRS SXRFK W0KI2 6RTWL 3Q06F 96GUL W9JSS 3XRMF 34
=
HBQ80 Y727A 7DCFW 0Q729 O2CRK 8WZCV BB7CF O7B7U 07
Description du procédé de chiffrage
()=voir Notes
Prenez un cube (1), sur chacune des 6 faces tracer une grille ; pour l'exemple une grille de 2x2 fera l'affaire (2).
Dans chacune des 6 grilles disposer les lettres de l'alphabet utilisé (3).
Dans notre exemple A,B,C et D.
Choisissez un sommet du cube que l'on appellera sommet n°1 (4)
Ce sommet est entouré de 3 faces, et 3 cases touchent ce sommet. Dans notre exemple les lettre A,B et C figurent dans ces 3 cases.
Nous allons utiliser les cases dans l'ordre naturel des lettres A puis B puis C (5)
Admettons que nous voulons chiffrer le texte clair suivant : DCB
D sera lu sur la grille A
C sera lu sur la grille B
B sera lu sur la grille C
La lecture du texte chiffré se fait en retournant le cube (sommet opposé par symétrie centrale que l'on appellera sommet n°2).
On parcours donc 3 nouvelles faces du cube en utilisant le même principe avec les 3 lettres entourant le sommet.
Les lettres codés se trouvent à l'intersection des lettres claires situées sur les 3 autres faces.
Dans notre exemple :
C et B donnent A (sur la face A)
C et D donnent A (sur la face B)
D et B donnent C (sur la face C)
Le DCB a donc été chiffré en AAC.
Le déchiffrage s'effectue en suivant la même procédure, comme si on voulait chiffrer AAC depuis le sommet n°2.
Le texte clair sera lu en utilisant le somment n°1.
ainsi :
A et C donnent D (sur la face A)
A et A donnent C (sur la face B)
A et C donnent B (sur la face C)
On obtient bien DCB.
La suite du message peut être chiffrée en utilisant un autre couple de sommet et/ou un autre sens de parcours des faces (avec ABC on peux avoir ABC,BCA,CAB,CBA,BAC,ACB).
Les messages chiffrés ci-dessus utilisent des grilles 6x6.
Notes
(1) Devrait fonctionner aussi avec un pavé.
(2) Fonctionne aussi en 2D mais nécessite de reproduire 4 à 8 fois chaque face du cube (voir détail si dessous).
(3) On pourra utiliser un mot clef pour constituer une grille désordonnée. Moyennant une méthode il est possible de constituer un cube avec 6 mots clef.
(4) Les sommets pourront être numérotés 1 à 8 selon une méthode liée au point (3).
(5) Dans le cas ou les lettres sont A,B,B on pourra par exemple parcourir les cases depuis A dans le sens horaire. Dans le cas peu probable avec une grande grille ou les lettres seraient A,A,A on pourra par exemple utiliser les 3 lettres suivante en diagonale. Un autre sens de parcours peut également être utilisé.
Remarques
Cette procédure de chiffrage se veut une adaptation des chiffres type playfair, 2-3-4 carrés permettant de chiffrer des trigrammes au lieu de bigrammes, d'ou le passage "naturel" de 2D en 3D.
Il n'est pas aisé de remplacer le cube par une table en 2D, il faut pour cela reproduire les liens entre faces au minimum pour les 4 couples des sommets, si ce n'est les 8 pour avoir des tables équivalentes. La réalisation de ces tables à nécessité la réalisation un cube pour comprendre les liens 3D et les transposer en 2D (il ne suffit pas de faire le patron du cube).
L'analyse des fréquences doit être complexe étant donné qu'il doit y avoir 288 (8*6*6) façon de chiffrer un même trigramme, qui de toute façon a une occurrence faible. Sans aller jusqu’à 288 une simple variation de l'ordre d'utilisation des sommets devrait être suffisante.
2 trigrammes proches AAB et ABB auront au minimum 1 lettre en commun dans leur chiffre (parfois 2 parfois 3).
2 trigrammes proches ABC et BCA n'auront souvent rien en commun dans leur chiffre (parfois 1 lettre, parfois 2, parfois 3).
1 lettre peut-être chiffrée par elle même, de même pour un trigramme mais de façon très rare.
Une lettre chiffrée (ex: en position 1 dans le trigramme) peux traduire la présence dans le texte clair de n^2 bigrammes (n=largeur de la grille)
Chiffrer trois fois la même lettre n'est pas un problème.
Inutile de préciser qu'il est possible de construire un nombre... énorme ?... de cubes différents ne serait-ce qu'avec une grille 5x5 ou 6x6.
Considérations pratiques
On peut réaliser un cube (propre et solide) à faces interchangeables à partir de papier et d'un crayon uniquement.
Il faut seulement 12 petits rectangles identiques, 6 pour le cube et 6 pour les faces avec les grilles.
Pour la technique je vous invite à consulter la vidéo ci-dessous (issu l'excellente chaine youtube Micmaths):
Tuto cube papier
Si comme moi vous souhaitez vous faciliter la lecture du texte chiffré, vous pouvez utiliser des petits aimants, 2 pour chaque face (intérieur et extérieur cube) pour marquer le texte clair.
Avec ce système je code environs 3 lettres en 30s quand je prend mon temps.
Alors ! Qu'en pensez-vous ?
Edit 30/08/20 : correction du cryptogramme (QFNJG=>QFNBD KKTGP=>KKT3P BDS7F=>BDMEF)
Dernière modification par Enigmat (30-08-2020 12:53:58)
Hors ligne
#2 30-08-2020 13:01:05
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonjour,
Après avoir réalisé un programme en python permettant de chiffrer avec cette méthode (en cours de finalisation) je me suis aperçu de 3 erreurs dans le cryptogramme long :
QFNJG =>QFNBD
KKTGP =>KKT3P
BDS7F =>BDMEF
Les lettres étant chiffrées 3 par 3 cela n'impacte que 3 groupes de 3 lettres et ne compromet donc pas le reste du message.
Les corrections nécessaires ont été apportées dans le message précédent.
Cela signifie que je suis maintenant capable de vous fournir des messages chiffrés plus long facilement si besoin.
Dernière modification par Enigmat (30-08-2020 13:03:28)
Hors ligne
#3 26-10-2020 15:21:09
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonjour,
En version 2D voici ce que cela pourrait donner :
Dans cet example CLE =》LGW
On conserve les 288 façons de chiffrer le trigramme "CLE" (position des flèches bleue et rouge).
La question que je me pose est la suivante :
Ce procédé est-il suffisement robuste pour fonctionner avec 2 clefs ?
_Une clef pour définir les 6 carrés qui serait changée par exemple une fois par mois.
_Une clef pour définir une des 288 façons de chiffrer qui changerait par exemple tout les jours.
L'idée étant de réduire la taille de la clef à échanger régulièrement.
Ou peut être que la première clef est suffisante pour garantir la sécurité tant qu'elle n'est pas compromise...
Dans ce cas on réduit au minimum le nombre d'échange de clefs.
Des idées sur les façons d'attaquer un message chiffré avec un tel procédé ?
Dernière modification par Enigmat (26-10-2020 15:22:18)
Hors ligne
#4 29-10-2020 14:21:20
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonjour,
Autre question qui me passe par la tête : pensez-vous qu'ayant choisi une des 288 façons de chiffrer il soit possible de trouver une grille réversible ? Afin de chiffrer et déchiffrer de manière identique ?
CLE =》LGW
et
LGW =》CLE
Hors ligne
#5 15-11-2020 13:07:10
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Re : Nouveau procédé de chiffrage à tester : CUBE
Hors ligne
#6 08-12-2020 19:33:01
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonjour Enigmat,
Les chiffrements par trigrammes sont rares. On ne trouve rien dans la littérature cryptologique à part le chiffre de Hill (qui est plus généralement n-grammique). Klaus Schmeh avait proposé l'année dernière sur son blog un challenge pour le "Playfair for three", un chiffrement trigrammique (très compliqué) à partir d'un seul carré. Pas très costaud, le challenge à duré deux jours.
Le chiffre CUBE est bien plus coriace !
D'abord, l'espace des clés est énorme : 6 alphabets de 36 caractères donnent $(36!)^6$ possibilités. Comme on peut faire une permutation circulaire sur les lignes ou les colonnes de l'un des carrés et obtenir néanmoins le même chiffrement en effectuant les bonnes permutations sur les lignes et les colonnes des autres carrés, il y a $\frac{(36!)^6}{36}\approx 2^{823.4}$ clés indépendantes. Une sécurité de plus de 823 bits, c'est pas mal (mais bon...).
Les six alphabets ne sont pas équivalents. J'appelle alphabets primaires les trois alphabets sur lesquels on repère les trois lettres du trigramme clair et alphabets secondaires les trois alphabets sur lesquels on lit les trois lettres du trigramme du chiffré.
Si l'on connait les alphabets primaires, on peut facilement trouver les alphabets secondaires qui permettent le déchiffrement d'un message donné. Il suffit de déchiffrer le message en prenant trois alphabets secondaires quelconques : on obtient un cryptogramme intermédiaire qui est chiffré par une substitution polyalphabétique de période trois. Ceci est dû au fait que passer d'une lettre d'une face du cube à la lettre correspondante de la face opposée n'est qu'une substitution simple.
J'ai vérifié que, si le cryptogramme n'est pas trop court, un simple Hill Climbing avec 300 itérations était suffisant pour trouver les alphabets secondaires.
J'ai donc monté une attaque par recuit simulé sur les trois alphabets primaires : on modifie un, deux ou trois alphabets primaires, on détermine les alphabets secondaires qui assurent le score minimal et on compare ce score avec le meilleur score obtenu jusque là.
J'ai fait ces essais sur un grand cryptogramme de 3435 caractères pour être sûr d'avoir assez de données. Connaitre le texte clair permet de calculer le taux de coïncidence avec le texte décrypté à chaque étape et donc d'affuter l'algorithme.
Après de très longs calculs (plusieurs jours) j'ai obtenu presque le texte clair : 99,7% de caractères exacts.
Pour décrypter des cryptogrammes de plus en plus petits, j'ai remarqué qu'il était préférable d'optimiser d'abord avec une fonction score basée sur les monogrammes, puis sur les bigrammes,..., jusqu'aux hexagrammes !
Appliqué au deuxième cryptogramme, le script a donné après 12 heures de calculs :
alphabets :
['SVDWMK7ZR0CE3Y9JP62UQGBHNA5T4OFLI18X',
'L7UV8HPYCDSM3JIEB42AG9N56KFQZW1XR0OT',
'WO0P84YMQNR627ZLIEJHXBUT593SKC1DVFGA',
'09D48ZR3UIG2NJTVOHBMCY7LSFAQ1EW6XPK5',
'I6XWQDCAH52OZKRUT87Y3JFNBSEV1MLPG490',
'X60OW4GERJV5K13CNDHIYLUAMBQSZFP78T29']
TOUTESMESFELICITATIONSVOUSAVEZREUSSIACASSERUNCODE
PAPIERCRAZONAUQUELJENAVAISPASTROUVEDEFAILLESAPPAR
ENTESOUALORSJAVAITREMEDIEJEVOUSINVITEAMEFAIREPART
DESFAILLESQUEVOUSAVEZEXPLOITEESPAREMAILALADRESSES
UIVANTEMPEYZ9GMAILCOMCIDESSOUSLETEXTELITTERAIREQU
IVOUSASANSDOUTEFACILITELATACHELANNEEQ564FUTMARQUE
EPARUNEVENEMENTBIZARREUNPHENOMENEINEXPLIQUEETINEX
PLICABLEQUEPERSONNENASANSDOUTEOUBLIESANSPARLERDES
RUMEURSQUIAGITAIENTLESPOPULATIONSDESPORTSETSUREXC
ITAIENTLESPRITPUBLICALINTERIEURDESCONTINENTSLESGE
NSDEMERFURENTPARTICULIEREMENTEMUSLESNEGOCIANTSARM
ATEURSCAPITAINESDENAVIRESSKIPPERSETMASTERSDELEURO
PEETDELAMERIQUEOFFICIERSDESMARINESMILITAIRESDETOU
TPAZSETAPRESEUXLESGOUVERNEMENTSDESDIVERSETATSDESD
EUXCONTINENTSSEPREOCCUPERENTDECEFAITAUPLUSHAUTPOI
NTVINGTMILLESLIEUESSOUSLESMERSJUBESVERNEPOURETRES
URDAVOIRTOUTESLESLETTRESDELALPHABETPORTEZCEVIEUX4
HIS76AUJUGEBLONDQUIFUMEETCOMMEPOURLEMAILILVOUSFAU
DRATOUSLESCHIFFRESVOICILASUITEDEFIBONACCU22OY1Y32
EY296ZY3386Y301EW82Y9XX
On peut facilement obtenir le texte sauf les chiffres qui restent indéterminés. Le pangramme à la fin et la suite de Fibonacci n'apportent rien : on chiffre par trigrammes.
On a avec ce chiffre un phénomène contre-intuitif : il est quasiment impossible d'obtenir 100% du texte clair compte tenu du très grand nombre de clés possibles, mais on a aussi un très grand nombre de clés qui permettent d'obtenir plus de 90% du texte clair ce qui fait qu'on peut quand même le casser !
C'est la première fois que je vois ça.
Le premier cryptogramme est trop court pour être décrypté. Je pense que ce chiffre est sûr pour les messages de moins de 600 caractères.
Dernière remarque : si on sait, par exemple, que le chiffré FCU donne le clair TES, on a
FCx --> .E.
xCU --> ..S
FxU --> T..
où x est une lettre quelconque et les points des lettres indéterminées.
Le chiffre laisse fuiter de l'information sur d'autres trigrammes proches.
On peut utiliser cette remarque si une partie du texte clair est connue.
@+
Hors ligne
#7 09-12-2020 14:02:25
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonjour Rossignol,
Bravo pour cette belle démonstration de cryptanalyse ! Et merci d'avoir pris la peine de te pencher sur mon procédé.
Même si je ne m'attendais pas à ce que cette version "simple" soit incassable, c'est quand même impressionnant de voir que c'est possible alors cela fait des mois que j'essaie de trouver des failles exploitables sans succès.
Je vais me pencher dessus sérieusement pour bien tout comprendre.
Concernant le FC=T c'est effectivement un indice mais comme cela ne concerne que 1/3 du message et que sur ce même 1/3 le T=>FC est vrai une fois sur 36 je ne pensais pas que cela pouvait constituer une faille sérieuse.
C'est tout de même réconfortant de savoir que ce chiffre donne plus de fils à retordre en dessous de 600 caractères :)
Cette première étape étant franchie, je voudrais maintenant vous faire part de la version quasi définitive en 2D de ce chiffre, qui exploite toutes les possibilités de ce système.
Je ne pense pas que sa sécurité puisse être compromise par la cryptanalyse de la version "simple", mais peut-être que je me trompe.
(Je ne fournirai pas d'échantillons, car il vous faudra sans doute moins de temps que moi pour les constituer.)
Comme mentionné dans le 1er post il existe 288 façons de chiffrer ABC avec une même grille telle que la grille ci-dessous :
On pourra nommer les différents carrés de cette façon :
1 2 3
4 5
6
Pour choisir et indiquer laquelle des 288 façons utiliser je vous propose la table ci dessous qui peut être publique :
L'idée est de choisir de façon aléatoire ou pas (au "hasard") 1 chiffre entre 1 et 9, et 2 lettres de l'alphabet sauf A et E.
Par exemple : IZ1 (= I1Z = 1IZ)
Ce qui signifie que le clair sera écrit dans la section "1" en utilisant les tables dans l'ordre "I" soit 2-3-1 (graphiquement c'est plus intuitif).
Quand au trigramme crypté il sera lui en 7 (opposé du 1) et dans l'ordre "Z" soit 6-4-5
(Sur la version papier j'utilise 3 petits pions bleu pour le clair, 3 rouges pour le cryptogramme, et 2 jaunes pour indiquer le sens d'écriture et de lecture)
Bien sûr IZ1=PZ1=P1Z=G1C... soit 3x8x4x6x4x6=13824 indicateurs de clef pour 288 clef distinctes, soit 48 façons de chiffrer une clef.
Pour crypter un message connaissant la grille de chiffrage, il faut une clef initiale qui peut être liée à la grille ou à l'expéditeur par exemple W1V (qui correspond à l'image avec flèches rouges et bleues d'un post précédent). Qu'elle soit publique ou privé ne change pas grand chose.
Soit le texte : MESSAGESECRET à chiffrer => MES SAG ESE CRE T(YH)
1) On choisi "aléatoirement" une clef ex : XG4 qui servira à chiffrer le message, et l'on chiffre XG4 avec W1V, ce qui donne 6K4
2) On chiffre un nombre aléatoire de trigramme avec XG4 par exemple : MES SAG ESE => 5FN XJJ SMY
3) Puis on peut décider de changer de clef, par ex : 6SD => NP5
4) On chiffre CRE TYH avec 6SD => DBJ P0M
5) Soit XG4 MESS AG ESE 6SD CRE TYH => 6K4 5FN XJJ SMY NP5 DBJ P0M
Le déchiffrage se fait simplement connaissant la grille et W1V.
Si la version simple est relativement sûre en dessous de 200 trigrammes, avec cette méthode on peut par exemple utiliser 4 clefs pour un message de 200 trigrammes.
Ex : clef1 19 trig. clef2 62 trig. clef3 45 trig. clef4 74 trig.
Le nombre de découpage possible devrait rendre très complexe toute analyse statistique, et permettre changer de grille plus rarement (utile quand on ne peux pas retenir 6 "mots" clefs ou que l'on veut une clef très longue pour constituer la grille).
Avec cette méthode manuelle on doit pouvoir chiffrer 1 trigramme en 20s soit environ 100 caractères en 10 minutes.
Si la taille du clair est de 200 trigrammes le message chiffré en comportera environ 204 et ne sera donc que 2% plus long.
@+
Hors ligne
#8 10-12-2020 11:33:53
- Enigmat
- Membre
- Inscription : 06-08-2020
- Messages : 18
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonjour Rossignol,
Qu'est ce qui fait qu'il est si difficile de déterminer les chiffres, même en connaissant une suite de chiffres (fibonacci donnée) ? Le clair est connu et son emplacement dans le cryptogramme aussi.
Cela signifie t-il que si l'on code principalement des chiffres c'est impossible à casser ?
Dernière modification par Enigmat (10-12-2020 11:39:30)
Hors ligne
#9 10-12-2020 18:31:30
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
Re : Nouveau procédé de chiffrage à tester : CUBE
Bonsoir Enigmat,
La difficulté vient du fait qu'on chiffre avec des trigrammes : on n'a donc les équivalents que pour des groupes de 3 chiffres.
On sait simplement que
FIBONAC CI1 123 581 321 345 589 144 233 377 610 897
ce qui fait peu de trigrammes avec des chiffres, d'autant que certains trigrammes peuvent aussi contenir des lettres K0Q --> CI1
Le contexte permet de deviner que l'année est 18.. car l'action se passe au XIX-ième siècle. Mais est-ce 1823, 1857, 1861 ... ? Sans le texte de Jules Verne, on ne peut pas le savoir.
Le trigramme ENT est très fréquent en français, le trigramme KWX quasiment impossible.
Pour les chiffres, 589 est-il plus fréquent que 610 ?
@+
Hors ligne