hash MD5 en C, pas facile !

Version imprimable

Bonjour à tous, je me suis lancé dans un projet. Je voudrais hasher un message de N caractères en MD5.
J'ai trouvé le pseudo code sur wiki.
Le problème est que je n epossède pas assez de connaissances pour coder ma source. (j ai pas envie de trouver une source non comprise sur le net)

Je vous poste:

1) Le pseudo code
2) La source avec étape du pseudo code.

1)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
MD5 peut s'écrire sous cette forme en pseudo-code
 
//Note: Toutes les variables sont sur 32 bits
 
//Définir r comme suit : 
var int[64] r, k
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}
 
//MD5 utilise des sinus d'entiers pour ses constantes:
pour i de 0 à 63 faire
    k[i] := floor(abs(sin(i + 1)) × 2^32)
fin pour
 
//Préparation des variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476
 
//Préparation du message (padding) :
ajouter "1" bit au message
ajouter "0" bits jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
ajouter la taille du message codée en 64-bit little-endian au message
 
//Découpage en blocs de 512 bits:
pour chaque bloc de 512 bits du message
    subdiviser en 16 mots de 32 bits en little-endian w[i], 0 ≤ i ≤ 15
 
    //initialiser les valeurs de hachage:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3
 
    //pour principale:
    pour i de 0 à 63 faire
        si 0 ≤ i ≤ 15 alors
            f := (b et c) ou ((non b) et d)
            g := i
        sinon si 16 ≤ i ≤ 31 alors
                  f := (d et b) ou ((non d) et c)
                  g := (5×i + 1) mod 16
              sinon si 32 ≤ i ≤ 47 alors
                        f := b xor c xor d
                        g := (3×i + 5) mod 16
                    sinon si 48 ≤ i ≤ 63 alors
                              f := c xor (b ou (non d))
                              g := (7×i) mod 16
                          fin si
                    fin si
              fin si
        fin si
 
        var int temp := d
        d := c
        c := b
        b := ((a + f + k[i] + w[g]) leftrotate r[i]) + b
        a := temp
    fin pour
 
    //ajouter le résultat au bloc précédent:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d
fin pour
 
var int empreinte := h0 concaténer h1 concaténer h2 concaténer h3 //(en little-endian)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
main()
{
      int i;     // boucle diverses
      int f,g;   // variable boucle principale
      int k[64]; // recoit les sinus d'entier de la formule: k[i]=(sin(i + 1))*(pow(2,32))
 
      int r[64]={7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22,
                 5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
                 4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,
                 6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21}; // constentes
 
 
      //MD5 utilise des sinus d'entiers pour ses constantes:
      for(i=0;i<64;i++)
      {
                      k[i]=(sin(i + 1))*(pow(2,32));
      }
 
      //Préparation des variables:
      int h0 = 0x67452301;
      int h1 = 0xEFCDAB89;
      int h2 = 0x98BADCFE;
      int h3 = 0x10325476;
 
      //Préparation du message (padding) :
      //ajouter "1" bit au message
      //ajouter "0" bits jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
      //ajouter la taille du message codée en 64-bit little-endian au message
 
      //Découpage en blocs de 512 bits:
      //pour chaque bloc de 512 bits du message subdiviser en 16 mots de 32 bits en little-endian w[i], 0 <= i <= 15
 
      //initialiser les valeurs de hachage:
      int a = h0;
      int b = h1;
      int c = h2;
      int d = h3;
 
      //pour principale:
      for(i=0;i<64;i++)
      {
                       if ((i>=0)&&(i<=15))
                          {
                          f=( (b&c) | ( (!b)& d ) );
                          g=i;
                          }
                          else if ((i>=16)&&(i<=31))
                               {
                               f=(d&b) | ((!d)& c); 
                               g=((5*i)+1)%16;
                               }
                               else if ((i>=32)&& (i<=47))
                               {
                               f= b^c^d;
                               g=((3*i)+5)%16;
                               }
                                    else if ((i>=48)&& (i<=63))
                                    {
                                    f= c^( b | (!d) );
                                    g=(7*i)%16;
                                    }
 
      int temp=d;
      d=c;
      c=b;
      // ? b=((a + f + k[i] + w[g]) << r[i]) + b;
      a=temp;                 
      }
 
      //ajouter le résultat au bloc précédent:
      h0=h0 + a;
      h1=h1 + b; 
      h2=h2 + c;
      h3=h3 + d;                    
 
      //FIN : pour chaque bloc de 512 bits du message subdiviser en 16 mots de 32 bits en little-endian w[i], 0 <= i <= 15
 
      //int empreinte = h0 "concaténer" h1 "concaténer" h2 "concaténer" h3 //(en little-endian)
      printf("%x",h0);
      printf("%x",h1);
      printf("%x",h2);
      printf("%x\n",h3);
 
      getch();
      return(0);
}

J'ai des soucis dans les commentaire de la sources.

Merci d'avance.

25/12/2007, 21h17
ram-0000

En ce qui concerne MD5, je ne voie qu'une seule source fiable, c'est le RFC 1321 ici par exemple (http://www.faqs.org/rfcs/rfc1321.html)

Ce RFC est écrit par une une sommité en la matiere : Ronald L. Rivest et j'ai tendance à lui faire confiance. Désolé, c'est en anglais.

Il suffit de copier/coller le code contenu dans le RFC et de le compiler pour que cela marche (je l'ai déjà fait). Pour ce qui est de comprendre l'algorithme (et donc mettre des commentaires dans le code), il y a tout dans ce RFC aussi.
25/12/2007, 21h26
Skyounet

En ayant regardé le source fourni dans la RFC je doute que tu ais les capacités pour la coder toi-même.

Ca n'a rien de méchant hein, c'est juste au vue de ta phrase sur tes connaissances.
25/12/2007, 21h32
ram-0000

C'est clair qu'en lisant le code de la RFC, on voie par exemple que certaines constantes sont faites a partir de sinus

On va pouvoir mettre un beau commentaire "Cette constante est construite avec le sinus machin". Malheureusement, ce commentaire ne fait pas avancer le schmilblick dans la compréhension mathématique de l'algo.

Parce que expliquer pourquoi c'est un sinus et pas une tangente, c'est une autre histoire que je laisse aux théoriciens mathématiques
25/12/2007, 23h55
jack_x4

Je suis venu vous voir pour apprendre et terminer ma source. Votre redirection est tres explicite je vous en remercie.
Mais je recherche les connaissences des étapes du speudo-code que je n'ai pas su coder !

Merci.
25/12/2007, 23h59
Skyounet

Citation:

Envoyé par jack_x4

Je suis venu vous voir pour apprendre et terminer ma source. Votre redirection est tres explicite je vous en remercie.
Mais je recherche les connaissences des étapes du speudo-code que je n'ai pas su coder !

Merci.

Ben indique nous les lignes de l'algo que tu n'as pas su coder alors.
26/12/2007, 13h09
jack_x4

//Préparation du message (padding) :
ajouter "1" bit au message
ajouter "0" bits jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
ajouter la taille du message codée en 64-bit little-endian au message

//Découpage en blocs de 512 bits:
pour chaque bloc de 512 bits du message
subdiviser en 16 mots de 32 bits en little-endian w[i]

Dans la source :(http://www.faqs.org/rfcs/rfc1321.html)
DEC-cpp ne comprend pas # define (a)+=(b); \

Si l'erreur est dans cette portion du code

Code:

1
2
3
4
5
6
7
8
9
10
 
/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Rotation is separate from addition to prevent recomputation.
 */
#define FF(a, b, c, d, x, s, ac) { \
 (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 
 (a) += (b); \
 }

C'est parce que il y a un saut de ligne en trop juste avant

Code:

1
2
3
 
 (a) += (b); \
 }

03/03/2009, 16h39
Nico_stras
Si je ne m'abuse, il y a une erreur dans la RFC :

Code:

A.4 mddriver.c
Code:

1 2 3 #ifndef MD #define MD MD5 #endif
au lieu de
Code:

1 2 3 #ifndef MD #define MD 5 #endif
Erreur ou j'ai pas compris ...?

Merci
03/03/2009, 16h47
ram-0000
Citation:

Envoyé par Nico_stras

Si je ne m'abuse, il y a une erreur dans la RFC :

Une erreur dans un RFC ... allons allons.

Disons plutôt que tu as mal interpété un détail
Code:

1 2 3 #ifndef MD #define MD 5 #endif
Ce morceau de code, c'est pour fixer la version de MD. Il y a eu MD2 puis MD4 et maintenant MD5 (pour MD3, je ne sais pas).

Et par défaut, la version MD sera la version 5 (ce qui me parait très bien)
03/03/2009, 17h22
Nico_stras
J'ai bien compris l'utilité de ce bout de code.
Mais dans la suite, on a
Code:

1 2 3 #if MD == 5 #include "md5.h" #endif
Donc le code qui précède doit être
Code:

1 2 3 #ifndef MD #define MD 5 #endif
et non
Code:

1 2 3 #ifndef MD #define MD MD5 #endif
03/03/2009, 18h13
BainE

bonjour,

Citation:

The driver compiles for MD5 by default but can compile for MD2 or MD4
if the symbol MD is defined on the C compiler command line as 2 or 4.

c est bien comme ram a dit.
Par contre on defini MD a la compilation.

Citation:

Envoyé par jack_x4

//Préparation du message (padding) :
ajouter "1" bit au message
ajouter "0" bits jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
ajouter la taille du message codée en 64-bit little-endian au message

//Découpage en blocs de 512 bits:
pour chaque bloc de 512 bits du message
subdiviser en 16 mots de 32 bits en little-endian w[i]

Dans la source :(http://www.faqs.org/rfcs/rfc1321.html)
DEC-cpp ne comprend pas # define (a)+=(b); \

Alors c'est pas extrêmement compliqué :

Tout comme le SHA-1, le MD5 t'impose plusieurs choses !

La première est la taille des "BLOCKS" de données en entrée de l'algorithme :
blocks de maximum 56 (ou plus mais dans ce cas l'algo divise le block principale en sous-blocks) caractères, d'ou :

Citation:

bits jusqu'à ce que la taille du message en bits soit égale à 448

Prenons le cas ou ton message fais moins de 56 caractères, dans ce cas (l'algorithme travaillant sur un block de 64 caractère) va venir AJOUTER un '1' juste après tes caractères et REMPLIR le reste avec des '0'.

Voici un petit exemple :
Code:

1 2 3 4 5 6 7 8 9 10 //Données à l'entrée : ABCD0123456789 //(en hexa) //l'algorithme va rajouter le 1 et les 0 de la façon suivante : ABCD01234567898000000000000000000000...0000 //(jusqu'a avoir 448bit, ICI toujours en hexa bien sur)... //Et enfin a la fin de ces 448 bits il va ajouter la TAILLE INITIALE de tes //données ABCD01234567898000000000000000000000...000014//ajoute 14 car 14 //caractères
Si ton message fait exactement 56 caractères alors il ajoutera seulement la TAILLE du block...

Dans le cas maintenant ou ton block en entrée soit plus GRAND que 56 octets...L'algorithme va "découper" ce block en plusieur petit blocks d'une longueur de 64 octets.
Ces petits block ne seront pas "pre-traité" (pas d'ajout de bit 0 ou 1) SAUF le dernier (par contre si le block a une taille multiple de 64 octets alors le dernier petit block de 64 octets sera composé entierement d'un 1 suivit de 447 zero eux-même suivit de la taille de la donnée originale).

Voila pour le dit "PADDING".
Ensuite l'algorithme va devoir travailler avec ton message de 512 bits MAIS aucun type de données "normale" n'est capable de contenir cela alors il te disent de DIVISER TON BLOCK PRINCIPALE (512 bits) en petits block de 16bits.

Ainsi le travail est plus aisé et la manipulations des bits est plus faciles.

Bonne chance, j'espère t'avoir aidé et j'espère aussi ne pas trop m'être trompé :s

05/03/2009, 20h12
Invité

En utilisant OpenSSL : http://target0.be/code/md5
08/03/2009, 08h14
Melem

Citation:

Envoyé par Skyounet

En ayant regardé le source fourni dans la RFC je doute que tu ais les capacités pour la coder toi-même.

Ca n'a rien de méchant hein, c'est juste au vue de ta phrase sur tes connaissances.

Oui, la source fournie dans la RFC m'a aussi choqué, comme de nombreuses autres sources d'ailleurs. J'ai alors fait la mienne, que je trouve plus simple à comprendre, en me basant sur l'algorithme décrit dans cette même RFC. J'ai commenté la source pour permettre au lecteur de se repérer par rapport à l'algo.

Lien vers la source : [Article][C] La fonction MD5.