Discussion :

[Sir Caedes]

Bonjour,

je m'interrogeais seulement sur la fiabilité, et la sécurité qu'offre l'algorithme que je m'apprete à vous décrire.

Le cryptage et le decryptage s'effectue à partir d'une clé privée (composée de lettres).

On a un texte de base, par exemple le mot MAISON.
on prend le code ascii de la premiere lettre (M) auquel on ajoute celui de la premiere lettre de la clé.
On fait de même pour la lettre A , on ajoute a son code ascii celui de la deuxieme lettre de la clé.
etc etc... Lorsqu'on est arrivé a la derniere lettre de la clé, on recommence à partir de la premiere lettre de la clé, et ce jusqu'a ce qu'on soit arrivé au bout de la chaine à crypter.

J'espere que cette description fut assez claire. Je voudrai savoir quelles sont les faiblesses d'un tel cryptage, les "moyens" de le casser, et s'il s'agit là d'un bon algorithme.

Merci

[Albus]

Salut,
Je penses que tu n'es pas le premier à avoir trouvé cet algorithme. D'ailleurs il ressemble assez à celui de Vigénère.

L'algo de Vigénère est un bon algorithme à clef privée, tout comme le tient, sa principale faiblesse réside dans le choix de la clef: le fait de connaitre la taille de celle-ci permet de déchiffrer un message rapidement (dans ce cas, on peut utiliser une table de fréquence d'apparition des caractères et faire des probas pour en déduire la clef privée). De plus, l'algo est très simple donc une attaque par "bute-force" serait relativement rapide par rapport à un autre algo (le RC5 par exemple).

A mon avis le seul moyen de casser un tel algorithme est le "brute-force" avec ou sans dictionnaire.

Donc évite d'utiliser un mot de passe petit et avec que des lettres. A ta place, je choisirais un mot de passe d'au moins 512 bits (si tu veux quelque chose de sécurisé) et qui utiliserait n'importe quel caractère ASCII.

Sinon essaye d'améliorer la complexité de ton algo pour le rendre plus lent.

[kaisse]

En gros tu nous demande si le chiffrement de Vigenere est sur. Comme tu devais t'en douter la réponse est ... pas du tout.
Trés simple à casser pour peu que le texte chiffré soit pas trop court.

Tout d'abord il faut retrouver la longueur de la clé. Si ta clé fais x lettres, alors deux motifs identiques espacés de x lettres (ou 2x ou n'importe quel multiple de x) auront exactement le meme codage. Exemple, si ta clé fait 5 lettres, et si on a le texte suivant
ABCDEABCUIABCHY, alors les trois fois, ton ABC sera codé de la meme maniere.
Donc on va utiliser cette propriété, mais dans l'autre sens en fait. Si, dans le texte chiffré, on a le meme motif plusieurs fois, il se peut que cela corresponde au meme motif en clair. Ce n'est pas trés vrai pour un motif de seulement 2 lettres, qui peut etre généré plusieurs fois sur des motifs différents à des endroits différents de la clé. Par contre à partir de 3 lettres identiques, ca devient beaucoup plus probable. Donc on va chercher le motif de 3 lettres qui apparait le plus souvent dans le texte chiffré. Ensuite, on va calculer toutes les distances qui séparent ces motifs deux à deux. Donc en supposant que tous ces motifs sont identiques dans le texte en clair, ca veut dire que toutes ces distances sont des multiples de x, la longueur de la clé.
Donc on sait que la longueur de la clé est diviseur de toutes les distances calculées. Donc on va supposer que la clé est de longueur le plus grand diviseur commun des distances. Si ca ne marche pas on essaiera avec d'autres diviseurs, ou en ignorant un des motifs dans le calcul des distances ...

Bon, et maintenant qu'on à la longueur de la clé qu'est ce qu'on fait ?
Et bien, la clé est de longueur x, donc on va prendre la premiere lettre puis une lettre sur x .. toutes ces lettres ont été codées avec la même lettre, la première de la clé. Donc chaque lettre aura un seul et unique codage. Donc, en faisant une analyse de fréquence toute conne, on peut retrouver le décalage. Par exemple, si tu trouves une majorité de h, on va supposer que ce sont les e, et donc le décalage est de 3 (lettre C). On reitere ca avec toutes les lettres jusqu'a la x-1 ieme, (avec toujours des decalages de x) pour trouver toute la clé.

Une méthode plus fine est utilisé en pratique à la place du calcul de fréquence: on calcule en fait un indice égale à la somme des carrés des fréquences des lettres. Cet indice est plus précis, si il est trop éloigné d'une certaine valeur alors ce n'est pas bon. C'est utile, puisque selon le découpage du texte, quand on prend une lettre toutes les x, il se peut qu'on ne prenne aucun 'e', ce qui gene le calcul de fréquence.

Cette cryptanalyse est tout à fait réalisable. J'ai implémenté des routines, qui m'ont permis de casser Vigenere pour tout texte d'environ 100 mots, avec des tailles de clés jusqu'à 20 caracractères. Le tout trés rapidement (j'enregistre les valeurs calculées dans un fichier, j'observe, j'essaie de déduire, je relance une routine avec mes hypothéses, jusqu'à obtenir le bono resultat, en moyenne ... 6 ou 7 minutes), sur un pc 300 MHZ. Je n'ai pas automatisé toutes les taches, juste le calcul de fréquence des triplets, et ensuite le calcul des indices pour tous les decalages de 1 à x, mais pas les déductions.

Tout est expliqué plus précisement dans l'ouvrage suivant:
Cryptographie: théorie et pratique de D. STINSON


EDIT
Donc en conclusion, c'est un trés mauvais algorithme de chiffrement. Comme il a été dit au dessus, si tu utilises les caracteres ascii au lieu du simple alphabet, ca complexifie un peu, mais pas assez. L'idéal est d'avoir une clé au moins aussi grande que ton texte, utilisable une seule fois, et qu'elle soit parfaitement aléatoire. A ces conditions tu as par contre un algorithme incassable (selon la théorie de Shannon). Mais n'espere pas trop, il est impossible d'avoir un générateur de bits parfaitement aléatoire, et il est trés couteux de génerer une clé aussi grande qu'un texte, même avec un générateur linéaire congruentiel.

Si tu veux chiffrer assez efficacement tes messages, recherche une implémentation gratuite de l'AES sur internet, ou alors télécharge GPG.

RE-EDIT
Au fait, "algorithme d'encryptage" ce n'est pas francais. Algorithme de cryptage si tu veux, algorithme de chiffrement étant plus juste.

[gangsoleil]

Un bon algorithme de cryptage ne doit pas consister dans son algorithme, ni dans la découverte d'une simple clef.
Si jamais tu souhaites lire un bon cours (à mon avis) sur la cryptographie (il parle du chiffrement de Vigenere), tu as celui de S. Natkin. Pour plus d'infos, sa page perso

[Sir Caedes]

merci pour vos réponses

En fait je suis débutant, et avant celui ci, le dernier crypteur que j'ai codé consistait en un simple décalage de caracteres ascii, donc je pense qu'il y a tout de même du mieux :p

m'enfin je vais me documenter sur le sujet


EDIT : sinon j'ai parlé d'une clé "texte" simple, mais on peut en fait utiliser une clé comportant n'importe quel caractere ascii

[davcha]

A une nuance près, l'algorithme de vernamm qui est incassable :p
C'est exactement l'algorithme que tu décris, à la différence près que la clef est de la même taille que le message à crypter.

[gangsoleil]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

l'algorithme de vernamm qui est incassable

Incassable peut être, mais encore faut-il qu'il existe un moyen infaillible de transporter la clef....
Et si tu as un moyen infaillible de transporter la clef, tu aurais pu envoyer un message en clair à la place

[Franckintosh]

Salut,
Je penses que tu n'es pas le premier à avoir trouvé cet algorithme.

C'est exact j'avais déjà personnellement pensé cet algorithme il y a 6 ans.
Par contre je suis franchement étonné car la description correspond exactement à ce à quoi j'avais pensé à l'époque. Penserait on de la même façon ? :o

Pour kaisse : ta description/démonstration ne correspond pas tout à fait à l'algorithme décrit. En effet il ne s'agit pas de décaler les lettres par leur position dans l'alphabet (A=1, B=2...) mais par leur code ASCII, ce qui est beaucoup plus efficace car cela donne souvent des caractères non lettres.
Mais la conclusion est tout à fait vraie.

[kaisse]

Pour kaisse : ta description/démonstration ne correspond pas tout à fait à l'algorithme décrit. En effet il ne s'agit pas de décaler les lettres par leur position dans l'alphabet (A=1, B=2...) mais par leur code ASCII, ce qui est beaucoup plus efficace car cela donne souvent des caractères non lettres.
Mais la conclusion est tout à fait vraie.

Ce n'est pas beaucoup plus efficace. A la limite, c'est un petit peu plus efficace. Un texte a peu pres normal, meme ecrit avec l'ensemble des codes ascii, n'utilise en general que la moitie de ces codes, et le nombre de caracteres non alpha-numeriques est marginal (a part pour les espaces et quelques signes de poncutations). Cela dit il est vrai que le codage contiendra beaucoup de caracteres non alpha-numeriques, ce qui peut perturber. Qu'est-ce que cela change pour l'analyse ?

- Ca ne change rien pour trouver la longueur de la cle -> les triplets seront toujours presents aux memes endroits, mais ils ne seront plus les memes. Or ca ne change rien, que le triplet le plus present soit WWH ou %"~ , ce n'est toujours que la distance entre les occurences de ces triplets qui importe.

- Pour trouver les caracteres de la cle un a un: et bien au lieu de travailler modulo 26, on travaille modulo 256. Donc au pire cas, au lieu de traiter 26 decalages possibles pour chaque caractere de la cle, on en aura 256. Donc la complexite reste en O(x) avec x la longueur de la cle. Si on utilise l'analyse des frequences, ca ne change pas grand chose, 'e' reste le caractere le plus employe, et les codes ascii apparus, seront en quantites vraiment reduite, et donc pas plus signifiant que le nombre de 'w' dans un texte. Or on travaille en general avec les lettres les plus frequentes ('e' ou 'a' par exemple), donc ca ne perturbe pas l'analyse.

[Franckintosh]

Je ne dénonçais pas ta réflexion (qui est tout à fait juste et justifiée), je tenais juste à rectifier une erreur d'interprétation.

[Sir Caedes]

C'est exact j'avais déjà personnellement pensé cet algorithme il y a 6 ans.
Par contre je suis franchement étonné car la description correspond exactement à ce à quoi j'avais pensé à l'époque. Penserait on de la même façon ? :o

Pour kaisse : ta description/démonstration ne correspond pas tout à fait à l'algorithme décrit. En effet il ne s'agit pas de décaler les lettres par leur position dans l'alphabet (A=1, B=2...) mais par leur code ASCII, ce qui est beaucoup plus efficace car cela donne souvent des caractères non lettres.
Mais la conclusion est tout à fait vraie.

à vrai dire, je ne l'ai même pas imaginé, j'ai trouvé un site qui expliquait brevement cette méthode.
Et comme je cherchait un moyen simple d'associer un nombre à chaque caractere, je me suis dis que l'ascii était un bon moyen (il existe il me semble une table de vigenere qui à deux lettres associe une et même autre lettre). :p

[kaisse]

Je ne dénonçais pas ta réflexion (qui est tout à fait juste et justifiée), je tenais juste à rectifier une erreur d'interprétation.

Pas de problèmes Désolé si j'ai eu l'air de l'avoir pris comme une offense, je m'excuse aussi j'avais mal lu le premier message posté:

on prend le code ascii de la premiere lettre (M) auquel on ajoute celui de la premiere lettre de la clé.

Donc on est d'accord

[ledrougi]

Salut a tous
je reveille ce sujet, je suis en train de developper un source en java pour casser un chiffrement de Vigenere.
Le probleme que je rencontre n'est pas dans la programation, c plus sur la méthode d'utilisation, c plus sur l'algo derrière.
Je ne comprends pas bien ce que je dois faire pour trouver la longueur de la clé.

On va faire les choses bien :
DONNEES: texte chiffré de 3000 caractère en espagnol. (27 lettres ds l'alphabet)
RESULTAT: calcul des distances deux a deux dans l'ordre d'apparition dans le texte chiffré. Attention les yeux, ca donne ca:

• DWV, dist : 508 freq :2
  YDO, dist : 412 freq :2
  YDO, dist : 449 freq :3
  DOW, dist : 412 freq :2
  DPS, dist : 16 freq :2
  DPS, dist : 334 freq :3
  DPS, dist : 320 freq :4
  PSV, dist : 16 freq :2
  SVU, dist : 16 freq :2
  VUO, dist : 16 freq :2
  UOW, dist : 16 freq :2
  NBQ, dist : 832 freq :2
  BDC, dist : 388 freq :2
  DCS, dist : 388 freq :2
  CSJ, dist : 388 freq :2
  SJH, dist : 388 freq :2
  JHA, dist : 388 freq :2
  HAO, dist : 388 freq :2
  AOI, dist : 388 freq :2
  ISV, dist : 776 freq :2
  SVI, dist : 696 freq :2
  SVI, dist : 136 freq :3
  VIB, dist : 636 freq :2
  VIB, dist : 93 freq :3
  VIB, dist : 660 freq :4
  VIB, dist : 173 freq :5
  IBI, dist : 776 freq :2
  BIJ, dist : 776 freq :2
  BIJ, dist : 187 freq :3
  IJH, dist : 232 freq :2
  IJH, dist : 604 freq :3
  JHX, dist : 640 freq :2
  JHX, dist : 197 freq :3
  HXV, dist : 776 freq :2
  XVX, dist : 776 freq :2
  XLD, dist : 536 freq :2
  EMV, dist : 104 freq :2
  MVN, dist : 104 freq :2
  VNG, dist : 104 freq :2
  DKU, dist : 536 freq :2
  KUQ, dist : 4 freq :2
  UQS, dist : 888 freq :2
  QSK, dist : 172 freq :2
  QSK, dist : 505 freq :3
  SKW, dist : 172 freq :2
  KWA, dist : 172 freq :2
  XBB, dist : 580 freq :2
  XBB, dist : 165 freq :3
  GBU, dist : 860 freq :2
  BUN, dist : 576 freq :2
  VSZ, dist : 860 freq :2
  SZW, dist : 860 freq :2
  ZWB, dist : 860 freq :2
  ASM, dist : 340 freq :2
  BBL, dist : 620 freq :2
  BLC, dist : 56 freq :2
  OBL, dist : 52 freq :2
  OBL, dist : 522 freq :3
  BLY, dist : 444 freq :2
  LYS, dist : 444 freq :2
  YSZ, dist : 444 freq :2
  SZA, dist : 444 freq :2
  ZAN, dist : 444 freq :2
  ANR, dist : 444 freq :2
  NRB, dist : 444 freq :2
  RBD, dist : 172 freq :2
  RBD, dist : 410 freq :3
  BDX, dist : 444 freq :2
  DXU, dist : 444 freq :2
  XUF, dist : 444 freq :2
  UFU, dist : 444 freq :2
  FUJ, dist : 444 freq :2
  JSK, dist : 16 freq :2
  DJS, dist : 164 freq :2
  SUS, dist : 54 freq :2
  XEN, dist : 700 freq :2
  FVJ, dist : 116 freq :2
  FVJ, dist : 667 freq :3
  FVJ, dist : 132 freq :4
  FVJ, dist : 687 freq :5
  SKJ, dist : 500 freq :2
  KJD, dist : 500 freq :2
  JDS, dist : 332 freq :2
  JDS, dist : 332 freq :3
  ZKN, dist : 556 freq :2
  KNQ, dist : 556 freq :2
  NQB, dist : 227 freq :2
  NQB, dist : 277 freq :3
  AWT, dist : 352 freq :2
  WTO, dist : 352 freq :2
  TOB, dist : 16 freq :2
  WOI, dist : 800 freq :2
  OIN, dist : 800 freq :2
  NAF, dist : 84 freq :2
  OBF, dist : 16 freq :2
  BIX, dist : 384 freq :2
  BIX, dist : 389 freq :3
  VJK, dist : 657 freq :2
  UOP, dist : 40 freq :2
  HAW, dist : 106 freq :2
  AXL, dist : 16 freq :2
  AXL, dist : 630 freq :3
  SKV, dist : 428 freq :2
  KVQ, dist : 112 freq :2
  KVQ, dist : 771 freq :3
  KMN, dist : 368 freq :2
  MNA, dist : 16 freq :2
  MNA, dist : 716 freq :3
  MNA, dist : 76 freq :4
  OPM, dist : 76 freq :2
  PMN, dist : 624 freq :2
  SPM, dist : 28 freq :2
  SPM, dist : 538 freq :3
  SPM, dist : 100 freq :4
  SPM, dist : 794 freq :5
  ZJQ, dist : 104 freq :2
  QFS, dist : 216 freq :2
  MAD, dist : 44 freq :2
  JRB, dist : 492 freq :2
  PMQ, dist : 324 freq :2
  MQG, dist : 324 freq :2
  QGN, dist : 324 freq :2
  GNW, dist : 324 freq :2
  BFC, dist : 60 freq :2
  BFC, dist : 551 freq :3
  XVN, dist : 204 freq :2
  XVN, dist : 515 freq :3
  VNH, dist : 112 freq :2
  VNH, dist : 432 freq :3
  NHA, dist : 602 freq :2
  WBO, dist : 632 freq :2
  ADP, dist : 304 freq :2
  PSB, dist : 304 freq :2
  SBI, dist : 248 freq :2
  SBI, dist : 408 freq :3
  SBI, dist : 364 freq :4
  HIH, dist : 260 freq :2
  IHB, dist : 260 freq :2
  IHB, dist : 659 freq :3
  FHB, dist : 556 freq :2
  HBR, dist : 552 freq :2
  BRB, dist : 560 freq :2
  UBF, dist : 540 freq :2
  EQB, dist : 20 freq :2
  QBB, dist : 168 freq :2
  BFM, dist : 512 freq :2
  RAA, dist : 411 freq :2
  WYD, dist : 440 freq :2
  XKQ, dist : 256 freq :2
  NHR, dist : 92 freq :2
  SMD, dist : 136 freq :2
  YGM, dist : 272 freq :2
  GMI, dist : 272 freq :2
  MIX, dist : 272 freq :2
  IXG, dist : 272 freq :2
  XGZ, dist : 272 freq :2
  GZA, dist : 272 freq :2
  ZAX, dist : 272 freq :2
  AXB, dist : 272 freq :2
  DBX, dist : 312 freq :2
  SXU, dist : 184 freq :2
  XUJ, dist : 184 freq :2
  LSM, dist : 484 freq :2
  SMS, dist : 16 freq :2
  MSP, dist : 16 freq :2
  SPN, dist : 16 freq :2
  BQW, dist : 352 freq :2
  WXV, dist : 176 freq :2
  BEX, dist : 388 freq :2
  PMJ, dist : 320 freq :2
  LLO, dist : 184 freq :2
  ESB, dist : 172 freq :2
  UNH, dist : 68 freq :2
  JRM, dist : 248 freq :2
  MSI, dist : 284 freq :2
  SIS, dist : 196 freq :2
  SBS, dist : 192 freq :2
  BSP, dist : 288 freq :2
  FWV, dist : 68 freq :2
  FWV, dist : 891 freq :3
  WVS, dist : 312 freq :2
  WVI, dist : 36 freq :2
  WVI, dist : 776 freq :3
  XDJ, dist : 72 freq :2
  VJR, dist : 16 freq :2
  VJR, dist : 804 freq :3
  JRA, dist : 36 freq :2
  SPW, dist : 116 freq :2
  SPW, dist : 854 freq :3
  PWV, dist : 160 freq :2
  BUQ, dist : 36 freq :2
  NBN, dist : 56 freq :2
  IC pour p=3 : 5.3609103E-5

Voila, donc ca c mes données brut post-traitement.
J'explique qd mm, mais je pense que c evident :
"NBN, dist : 56 freq :2" signifie que le triplets NBN apparait 2 fois (freq=2). La distance séparant la première occurence de la deuxieme est de 56 caractères dans le message chiffrés (dist : 56).

A la fin, pour les connaisseurs, j'ai calculé l'IC (indice de coincidence), et c la que les problèmes commencent.
Pour le calcul d'IC, j'ai fait la somme des probabilités de tirer deux fois la mm lettre dans le texte. En fait, si n1 est le nbre de A et n la longueur du message, ma formule est :

• p(2 fois A)=[n1(n1-1)]/[n(n-1)]

et je trouve un IC comme ca :

• IC pour p=1 : 0.04474962

En fait, je comprends pas mes résultats.
Mon IC pour P=1 est differente de 0.074 (valeur de l'IC pour l'espagnol), donc ca veut dire que ma clé n'est pas monoalphabétique, c bien ca ?


En fait je ne suis mm pas sur d'avoir bien compris comment ce calcul cet IC. ce que je fais par exemple pour p=3, c'est que je decoupe en mot de 3 lettres le texte chiffrés, et je calcul la probabilité de tiré deux fois le mm triplet dans le texte. ça en fait :

• p(2 fois NBN)=(nbOccurenceNBN(nbOccurenceNBN - 1))/(n(n-1))

et ensuite je fais la somme des nombres trouvés pour tous les triplets. C faux ?

• IC pour p=2 : 7.8723376E-4
  IC pour p=3 : 5.3609103E-5
  IC pour p=4 : 1.1789559E-5
  IC pour p=5 : 4.8937823E-6
  IC pour p=6 : 1.3346678E-6
  IC pour p=7 : 2.2244461E-7
  IC pour p=8 : 0.0
  IC pour p=9 : 0.0
  IC pour p=10 : 0.0
  IC pour p=11 : 0.0
  IC pour p=12 : 0.0
  IC pour p=13 : 0.0
  IC pour p=14 : 0.0
  IC pour p=15 : 0.0
  IC pour p=16 : 0.0
  IC pour p=17 : 0.0
  IC pour p=18 : 0.0
  IC pour p=19 : 0.0
  IC pour p=20 : 0.0
  IC pour p=21 : 0.0
  IC pour p=22 : 0.0
  IC pour p=23 : 0.0
  IC pour p=24 : 0.0
  IC pour p=25 : 0.0

voila. Je suis completement perdu en fait.
Si quelqu'un pouvait m'aider... Je ne sais pas quoi faire pour trouver la longueur de la clé a partir de mes résultats.

merci d'avoir lu mon post jusque la ...
une remarque ou un commentaire ou mm voir une réponse, ce serait vraiment sympa !

[fsacpc]

[QUOTE=Albus;92639]Salut,

est ce que vous pouvez me donner un lien pour que je puisse comprendre l'algorithme de RC5, où si vous avez un application sous VB6 ca sera un plus