Décrypter vigenere avec ou sans la clef

Commenter

Contenu du snippet

permet de déchiffrer un fichier texte en connaissant ou non la clef de chiffrement. très bon exercice d'algo.

Source / Exemple : 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

#define CAPACITE 1000  //taille maxi de la chaine à étudier, peut être porté jusqu'à 4 milliards sans problème. (4 milliards : 5000 livres de Zola)
  

typedef unsigned long ul;

ul PROFONDEUR=20; //profondeur de recherche - longueur maxi de la clef à trouver - est modifié par le 3ème argument de la ligne de commande
// PORFONDEUR peut aller jusqu'à 999,999,999 (c'est déjà de la bonne clef).
char * alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";

//fonction qui compte le nombre d'occurence d'une lettre donnée dans une chaine donnée
ul comptage(char c, char * chaine)
{
ul nb=0;              
ul i,l=strlen(chaine);
for (i=0; i<l;i++)
    if (chaine[i]==c) nb++;

return nb;
}

//renvoie la position de c dans chaine. -1 si inexistant
ul pos(char c,char * chaine)
{
ul i=0,l=strlen(chaine);
while ((c!=chaine[i]) && (i<l))
    i++;
if (i==l) return -1;
     else return i;
}

//fonction de majuscule de lettre
unsigned char upcase(unsigned char c)
{
if ((c>=97)&&(c<=122))
    return c-32;

switch(c)
    {
    case 'à':
    case 'â':
    case 134: case 142: case 143:
    case 'ä': return 'A';
    case 'é': case 144:
    case 'è':
    case 'ê':
    case 'ë': return 'E';
    case 'ì':
    case 'î':
    case 'ï': return 'I';
    case 'ô': case 153:
    case 'ö':
    case 'ò': return 'O';
    case 'ù': case 154:
    case 'ü': return 'U';
    case 'ç': 
    case 155: return 'C';
    case 'ñ': 
    case 165: return 'N';
    case 152: return 'Y';
    default: return c;
    }
}

//fonction de majuscules de chaine
char * upcase_string(char * chaine)
{
ul l=strlen(chaine),i;
char * chaine2=(char*)malloc((l+1)*sizeof(char));
for(i=0; i<l; i++)
    chaine2[i]=upcase(chaine[i]);
       
return chaine2;
}

//fonction de lecture de chaine de caractère dans un fichier 'nom_fichier'
char * lecture(char *nom_fichier)
{
FILE *fichier=fopen(nom_fichier,"r");
if (fichier==NULL) return "\0";

ul i=0;
char *chaine=(char*)calloc(CAPACITE,sizeof(char));

while ((i<CAPACITE) && (fread(&chaine[i],1,sizeof(char),fichier)))
    i++;
 
fclose(fichier);       
return chaine;
}

//procédure d'écriture d'une chaine dans un fichier
void enregistrer(char *chaine, char *nom_fichier)
{
FILE *fichier=fopen(nom_fichier,"w");
if (fichier==NULL) 
    {printf("nom de fichier de sortie invalide");
     return;
    }     

fwrite(chaine,sizeof(char), strlen(chaine),fichier);
fclose(fichier);
return;
}

// fonction de nettoyage
char * nettoyage(char *sale)
{
char *chaine2=(char*)calloc(CAPACITE,sizeof(char));
char *autorise="ABCDEFGHIJKLMNOPQRSTUVWXYZ .,;:!?'()-\"";
ul i,j=0,l=strlen(sale);
  
for (i=0; i<l; i++)    //on n'accepte que les caractères présents dans autorise
    if (pos(sale[i],autorise)!=-1)
           {chaine2[j]=sale[i];
            j++;
           } 
      
return chaine2;
}

//fonction qui retire toute le ponctuation
char * deponctuation(char *chaine)
{
char * chaine2=(char*)calloc(strlen(chaine),sizeof(char));
ul i,j=0, l=strlen(chaine);

for (i=0; i<l; i++)
    if (pos(chaine[i], ",.;: ?!()'\"")==-1)
        {chaine2[j]=chaine[i];
         j++;
        }

return chaine2;
}

//fonction qui remet la ponctuation d'après le modèle de chaine2
char * reponctuation(char *chaine, char *chaine2)
{
ul i,j=0,l=strlen(chaine2);
char *chaine3=(char*)calloc(CAPACITE, sizeof(char));

//on parcourt les 2 chaines et on intercale une car de poncutation si besoin est
for (i=0; i<=l; i++)
    if (pos(chaine2[i]," .,;:!?'()-\"")==-1)
        {chaine3[i]=chaine[j]; 
         j++;
        }
        else 
        chaine3[i]=chaine2[i];

return chaine3;
}

//fonction qui retourne la clé
// calcul des écarts minis entre tous les décalages possibles et les occurences théoriques
char * crack(char * chiffre)
{
float occurences[56]={0.0942,0.0102,0.0264,0.0339,0.1587,0.0095,0.0104,0.0077,0.0841,0.0089,0,0.0534,0.0324,0.0715,0.0514,0.0286,0.0106,0.0646,0.0790,0.0726,0.0624,0.0215,0,0.003,0.0024,0.0032,0.0942,0.0102,0.0264,0.0339,0.1587,0.0095,0.0104,0.0077,0.0841,0.0089,0,0.0534,0.0324,0.0715,0.0514,0.0286,0.0106,0.0646,0.0790,0.0726,0.0624,0.0215,0,0.003,0.0024,0.0032};
//                       a      b      c     d      e      f       g     h      i      j    k    l     m      n      o      p       q     r      s      t      u      v    w   x      y     z  |||  a      b      c     d      e       f      g      h      i      j   k    l      m      n     o       p     q      r       s      t      u      v   w    x     y     z   
char * clef;
char * separe[PROFONDEUR];
//char * alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
ul i,j,k,l,m=strlen(chiffre),decalage,position;
float pourcent[26][26],  //pourcentage des 26 lettres pour tous les décalages
      difference[26][PROFONDEUR],  //différence pour chaque décalage et pour chaque longueur de clef
      difference_mini;
struct {float decalage;
        char * cle;
       } solution; 

solution.decalage=999;
solution.cle=(char*)calloc(PROFONDEUR, sizeof(char));

for (l=1; l<PROFONDEUR; l++)  //pour chaque longueur de clef, trouver le décalage mini et la meilleure clef
{
printf("#"); //barre de progression très design
clef=(char*)calloc(PROFONDEUR, sizeof(char));  //initialisation
     for (i=0; i<PROFONDEUR; i++)
         separe[i]=(char*)calloc(strlen(chiffre), sizeof(char));  //initialisation à ""
             
              
     // dispatching des lettres
     for (i=0; i<m;i++)
         separe[i%l]=strncat(separe[i%l],chiffre+i, 1);         
         
  
     for (i=0; i<l; i++)   // pour chaque séparé
         { 
         position=0;
         difference_mini=999;
         for (decalage=0; decalage<26; decalage++)  //pour chaque décalage
              {
              difference[decalage][l]=0;  
              for (k=0; k<26; k++) //calcul de la différence pour chaque lettre
                  {
                  pourcent[k][decalage]=(float)comptage(alphabet[k+decalage], separe[i])/(float)strlen(separe[i]);
                  difference[decalage][l]+=fabs(pourcent[k][decalage]-occurences[k]);
                  }
             
              //recherche pour un l donné du décalage mini
              if (difference[decalage][l]<difference_mini)
                  {
                  difference_mini=difference[decalage][l];        
                  position=decalage;
                  }
              }
         clef=strncat(clef,alphabet+position, 1);
         }        
               
     //calcul du mini de toutes les clés
     if (difference_mini<solution.decalage)
          {
          solution.decalage=difference_mini;
          solution.cle=clef;
          }
}            
   
return solution.cle;
}

//fonction de déchiffrement d'une chaine upcasée avec une clef. TRES semblable à chiffrer
char * dechiffrer(char * chiffre, char * clef)
{
char * dechiffre= (char*)calloc(strlen(chiffre),sizeof(char));
//char * alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
ul i, l1=strlen(clef), l2=strlen(chiffre);

ul indice;

for (i=0; i<l2; i++)
    {
    indice=i%l1;
    //dechiffre[i]=alphabet[pos(chiffre[i], alphabet)-pos(clef[indice]+26, alphabet)];
    dechiffre=strncat(dechiffre, alphabet+pos(chiffre[i],alphabet)-pos(clef[indice],alphabet)+26,1);
    }

return dechiffre;
}

//fonction qui vérifie que l'argument est bien un nombre entier positif
int isentier (char *chaine)
{
char chiffres[10]="0123456789";
ul l=strlen(chaine),i;
for (i=0; i<l; i++)
    if (pos(chaine[i], chiffres)==-1)
        return 0;
//faut vraiment le vouloir pour planter le prog, mais bon, une petite vérif ne fait pas de mal
if (l>=10) return 0;  //on bloque la profondeur à 999,999,999 

return 1;   
}

//fonction qui vérifie la validité d'une clef : que des lettres.
int iskey(char *key)
{
ul i, l=strlen(key);
for (i=0; i<l; i++)
    if (pos(key[i], alphabet)==-1)
        return 0;

return 1;   
}

///////////////////////////////////////////////////////////////////
//
//          main
//          vérification des arguments de la ligne de commande
//
///////////////////////////////////////////////////////////////////

int main(int argc, char **argv) // vig_decrypt <in_file> <out_file> <key or depth>
{
    if (argc!=4)
        {
            printf("Utilisation : vig_decrypt <fichier d'entr%ce> <fichier de sortie> <CLEF ou profondeur de recherche>\n\n", 130);
            return 1;
        }        
    
    else //vérification des arguments
        {
            FILE *fichier=fopen(argv[1],"r");
            if (fichier==NULL) 
                 {printf("%s introuvable", argv[1]);
                  return 2;
                 }     
                 
                 //on laisse le fichier ouvert
                 
            //la vérification de argv[2] se fait lors de l'enregistrement, à la fin
            
            char *chiffre=nettoyage(upcase_string(lecture(argv[1])));
            
            if (isentier(argv[3]))
               {   
                   char *clef=(char*)malloc(PROFONDEUR*sizeof(char));
                   PROFONDEUR=atol(argv[3])+1;
                   clef=crack(deponctuation(chiffre));
                   enregistrer(reponctuation(dechiffrer(deponctuation(chiffre), clef), chiffre), argv[2]);                   
                   printf("clef trouv%ce : %s", 130, clef);
                   free(clef);
                   free(chiffre);
                   fclose(fichier); 
               } 
            else //cet argument est la clé de déchiffrement. il faut le vérifier
               {
                   if (iskey(argv[3]))        
                        {
                            enregistrer(reponctuation(dechiffrer(deponctuation(chiffre), argv[3]), chiffre), argv[2]);
                            free(chiffre);
                            fclose(fichier);
                        }
                            
                   else printf("clef ou profondeur de recherche invalide");                         
               }                
        }    
        
return 0;    
}

Conclusion :


// Chiffre de Vigenère (sous réserve de modification)
// Déchiffrement - en connaissant ou non la clef
//
// par khayyam
//
// utilisation : vig_decrypt.exe <in_file> <out_file> ABCD (il est nécesaire d'écrire la clé en majuscule)
// ./vig_decrypt <in_file> <out_file> ABCD
// ou
// vig_decrypt.exe <in_file> <out_file> 10
// ./vig_decrypt <in_file> <out_file> 10
//
// ce code peut poser des problèmes sous un environnement windows :
// un caractère supplémentaire peut être créé à la fin du fichier de sortie.
// mais sous unix, c'est impeccable.
//
//
//traduction en C d'un prog déjà écrit en Pascal
// ! cet algo se base sur une utilisation sensée des lettres en fonction de leur fréquence d'apparition
// donc si vous souhaitez déchiffrer "les zinzins zigzaguent à zanzibar" , vous n'arriverez à rien.
//
// ce programme n'est efficace et fiable qu'à partir de 50*longueur_de_la_cle caractères.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_khayyam)