[C] Cryptographie | Implémentation du chiffre de Vernam

[EpicOut]

Bonjour, Bonsoir


Aujourd'hui je vais vous présenter mon implémentation en C du chiffre de Vernam ou l'opération XOR qui découle de ce chiffrement, j'y ai vraiment mis du plaisir à le faire, pour une fois :-), c'est une implémentation relativement simple, relativement oui, j'en ai chier pour en venir à bout.

Donc pour présenter le chiffrement de Vernam c'est un algorithme de chiffrement tout bête qui est "incassable", "inviolable", que ce soit par bruteforce ou autre techniques version grand-maître du cryptanalyste.
On part du fait qu'il est impossible de trouver les additions qui ont formés une somme d'un entier:

? + ? = 100 | Où le premier point d'interrogation est le message original, et l'autre point d'interrogation, le masque jetable/clé, et 100 le message chiffré. Comment est-ce possible ? C'est effectivement impossible de retrouver le message original du fait que toute les possibilités sont possiblement possibles:

50+50 ; 51+49 ; 52+48 ; 53+47 ; etc...

Plutôt bête non ? :-)

Mais cependant on peut pas laisser un tel algorithme nous passer entre les doigts sans lui donner quelques (légers) désavantages.

-Le masque/clé doit faire la même taille que le message original (oui, le chiffre de vernam est une opération bit à bit).

-La clé doit être choisit aléatoirement.

-Le masque/clé ne doit servir uniquement qu'une fois

Et si on respecte scrupuleusement toutes ces conditions, on a le droit à une sécurité absolue, il parait.

J'vous fait un exemple en live avec de l'ascii (non-étendu, de 0 à 127):

On va prendre le chiffre à chiffrer M=1337 et la clé aléatoire (à 100%) C=FAAG , si on additionne ça (avec les correspondances décimales):

49|51|51|55
+
70|65|65|71
___________
119|116|116|126 , ce qui donne en ASCII: wtt~

Et s'il venait que votre addition dépasse la table ascii, auquel vous auriez une addition comme ceci:

49|51|51|105
+
70|65|65|71
___________
119|116|116|176

Ne vous inquiétez pas, nul besoin d'utiliser ascii étendu qui va jusqu'à 255, vous avez juste besoin de faire un modulo (ou une soustraction) du nombre maximum de caractères ascii ou de la norme sur laquelle vous travaillez, (si ça avait été du base64, un modulo 64 tout simplement) et en non étendu c'est 128, donc ça fait:

176%128 = 48

Maintenant place au code de mon implémentation, je doute qu'il soit digne d'un ingénieur informatique, donc n'hésitez pas à critiquer ou à me poser des questions si ça vous chagrine.

Code C :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
/**Implémentation personnelle du chiffre de vernam**/
 
int generate_mask(int len_c,unsigned char *mask)
{
    srand (time(NULL));
    int i;
    for(i=0;i<len_c;++i)
        mask[i]=rand()% 255 + 1;   // clé aléatoire comprise entre 1 et 255, ascii étendu, d'où les unsigned char, les signed ne vont que jusqu'à +127 (ascii non étendu)
                                  //  je pars de 1 et pas de 0, parce qu'en ASCII, le 0 vaut NULL et si jme tape ça dans ma string, le C va penser que mon string est trop court ( :-) )                  
 
    mask[len_c]='\0';
 
    return 0;
}
 
 
int generate_encryption(unsigned char *cipher,unsigned char *mask,unsigned char *crypted,int len_c)
{
 
    int i;
    for(i=0;i<len_c;++i)
       {
           if( (mask[i]+cipher[i]) > 255 ) // Le résultat de l'addition est-il plus grand que la table ?
                crypted[i]=(mask[i]+cipher[i]) % 255; // si oui je fais un modulo
           else
                crypted[i]=mask[i]+cipher[i]; // sinon je mets ça dans crypted sans modulo
       }
 
    crypted[len_c]='\0';
 
    return 0;
}
 
int main(int argc, char *argv[])
{
if(argc == 2)
   {
    int len_c=strlen(argv[1]);
    unsigned char *mask=(unsigned char *)malloc(sizeof(char)*len_c+1);
    unsigned char *crypted=(unsigned char *)malloc(sizeof(char)*len_c+1);
 
 
    generate_mask(len_c,mask);
 
    generate_encryption((unsigned char *)argv[1],mask,crypted,len_c);
 
    printf("Message: %s\n Mask: %s\n Crypted: %s\n",argv[1],mask,crypted);
    free(mask);
    free(crypted);
   }
 
else
    fprintf(stderr,"Usage: ./<executable> <text to encrypt>");
}

[supersnail]

Well... pas mal tout ça (modulo quelques fautes d'orthographe et un "il parait" qui mériterait peut-être d'être plus détaillé).

Sinon quelques remarques concernant le code:

Déjà utiliser rand() pour des petits jeux OK, mais pour faire de la crypto, ce n'est pas le meilleur générateur aléatoire qu'il soit (i.e si quelqu'un retrouve la graine utilisée dans srand, cette personne pourra déchiffrer tout le message, par exemple). Dans ce cas, il vaudrait mieux lire la sortie de /dev/urandom (qui lui est plus compliqué à prédire que son petit frère rand()) et travailler avec

Ensuite (bon c'est de l'optimisation à 2 balles), plûtot que de faire une condition pour vérifier si la somme est < 255, autant directement faire le mod 256 (et peut-être utiliser des méthodes plus robustes que les manipulations de chaîne pour manipuler des données binaires, par exemple en transmettant la taille du masque avec le masque...)

Puis un dernier pour la route: memset c'est bon, mangez-en !

[b0fh]

Hello,

Jolie introduction !

Pour compléter ce qu'écrit supersnail: le type char implémente déja naturellement l'arithmétique modulo 256. C'est tout à fait possible de travailler modulo 255, ce qui permet d'éliminer les NULs, mais il faut le faire de manière cohérente, par exemple pour l'addition de a et b, il faut:

Code :

(((a - 1) + (b - 1)) % 255) + 1

Il faut le faire dans un type suffisamment grand pour que ça ne wrappe pas avant le modulo (donc 16 bits au moins.) C'est aussi beaucoup, beaucoup plus lent que l'arithmétique mod 256.

De cette manière on "projette" la plage effective 1-255 vers la plage 0-254, dans laquelle on utilise l'addition modulo 255.

C'est faux de dire que le type signed char ne va "que" jusqu'a 127: en fait, l'arithmétique de base (addition, soustraction et multiplication) se comporte exactement de la même manière pour les types signed et unsigned, par quelque magie mathématique. La preuve: les instructions asm sont les mêmes. Ce qui change, par contre, ce sont les opérations de comparaison (jump greater/jump lesser vs jump above/jump below). Mais si on utilise le fait que le débordement produit naturellement une arithmétique modulo 256, il n'y a pas besoin de faire de comparaisons pour implémenter cet algo.

Et sinon, amen pour la manipulation de données binaires avec une taille explicite.

[EpicOut]

Alors tout d'abord, merci pour les retours les gars !

Déjà utiliser rand() pour des petits jeux OK, mais pour faire de la crypto, ce n'est pas le meilleur générateur aléatoire qu'il soit (i.e si quelqu'un retrouve la graine utilisée dans srand, cette personne pourra déchiffrer tout le message, par exemple). Dans ce cas, il vaudrait mieux lire la sortie de /dev/urandom (qui lui est plus compliqué à prédire que son petit frère rand()) et travailler avec

Alors oui c'est vrai que /dev/urandom est plus "robuste", mais enfait mon programme se veut être "multiplateforme" étant donné que c'est que sur Linux, sur windows ou OSx on peut pas faire ça, je me demande si il y a une solution plus approprié ?

Et merci aussi à toi b0fh pour les infos croustillantes, je ne savais pas du tout que le modulo se faisait tout seul ou qu'on pouvait écrire la clé aléatoire différemment

[supersnail]

<troll>
Pourquoi faire de la crypto sur une passeoire ? Pour essayer de la transformer en casserole ? (ou en autobus)
</troll>

Sinon doit bien y avoir des fonctions de l'API Windows qui génère des nombres aléatoires "fiables" (ou pas en fait... c'est Windows :>)

Edit: cf http://blogs.msdn.com/b/michael_howard/a...53379.aspx pour des nombres aléatoires "sûrs" pour la crypto