Coder une fonction MD5 a partir du pseudo code.

Version imprimable

Bonsoir à tous,

Depuis quelques jours, j'essaye de coder une fonction pour obtenir le MD5 d'une petit chaine de caractére ; je me suis basé sur le pseudo code disponible sur wikipédia : http://fr.wikipedia.org/wiki/Md5.

En Balise quote le pseudo-code et en balise code ce que j'ai "codé"

Selon le pseudo code, toute les variables sont sur 32 bits et sur mon systéme sizeof (int) = 4

Tout d'abord voici les 4 fonctions principales :

http://upload.wikimedia.org/math/a/1...4bd3c8b4f7.png
http://upload.wikimedia.org/math/b/8...3f1fd2d559.png
http://upload.wikimedia.org/math/c/0...110144fe28.png
http://upload.wikimedia.org/math/8/1...59ac1da577.png
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int func_f (int b, int c, int d) { return ((b & c)|((~b) & d)); } int func_g (int b, int c, int d) { return ((b & d)|(c & (~d))); } int func_h (int b, int c, int d) { return b^c^d; } int func_i (int b, int c, int d) { return c ^ (b | (~d)); }
Citation:

var entier[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

Pour le tableau k, j'ai "fixé" les valeurs.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 unsigned 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}; unsigned int k[64] = { 74957514, 149892196, 224781220, 299601773, 374331064, 448946331, 523424844, 597743917, //0-7 671880911,745813244, 819518394, 892973912, 966157421, 1039046629, 1111629334, 1183853428, //8-15 1255726910, 1327217884, 1398304576, 1468965330, 1539178623, 1608923067, 1678177418, 1746920580, //16-23 1815131612, 1882789738, 1949874349, 2016365008, 2082241463, 2147483648, 2212071687, 2275985909, //24-31 2339206843, 2401715232, 2463492035, 2524518435, 2584775842, 2644245901, 2702910498, 2760751761, //32-39 2817752073, 2873894071, 2929160652, 2983534983, 3037000499, 3089540917, 3141140230, 3191782721, //40-47 3241452965, 3290135830, 3337816488, 3384480415, 3430113397, 3474701532, 3518231240, 3560689261, //48-55 3602062661, 3642338838, 3681505523, 3719550786, 3756463038, 3792231035, 3826843881, 3860291034};//56-63
Citation:

var entier h0 := 0x67452301
var entier h1 := 0xEFCDAB89
var entier h2 := 0x98BADCFE
var entier h3 := 0x10325476
Code:

1 2 unsigned int h[4] = {0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476};
Citation:

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
Code:

1 2 3 4 5 6 7 unsigned long long message_size = strlen(message); unsigned long long nbr_paquet = (message_size/56)+1; malloced_data = calloc(1,((56*nbr_paquet)+sizeof(long long int))); memcpy(malloced_data,message,message_size); memcpy(malloced_data+message_size,&add_1,1); memcpy(malloced_data+56*nbr_paquet,&message_size,sizeof(long long int));
Citation:

pour chaque bloc de 512 bits du message
subdiviser en 16 mots de 32 bits en little-endian w[i], 0 ≤ i ≤ 15
Code:

1 2 3 4 5 for (j = 0 ; j < nbr_paquet ; j++){ for (i = 0 ; i < 16 ; i++){ memcpy(&w[i],(malloced_data+(j*512))+(i*4),4);} //reste du code de la boucle principale
Citation:

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 entier temp := d
d := c
c := b
b := ((a + f + k[i] + w[g]) leftrotate r[i]) + b
a := temp
fin pour
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 for (i = 0 ; i < 64 ; i++){ if ( (i>= 0) | ( i<=15)){ f = func_f(b, c, d); g = i;} else if ((i>= 16) | ( i<=31)){ f = func_g (b, c, d); g = (5*i + 1)%16;} else if ((i>= 32) | ( i<=47)){ f = func_h(b, c, d); g = (3*i + 5)%16;} else{ f = func_i(b, c, d); g = (7*i)%16;} temp = d; d = c; c = b; b = ROTATE_LEFT (a + f + k[i] + w[g], r[i]) + b; a = temp;}
Citation:

//ajouter le résultat au bloc précédent:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
Code:

1 2 3 4 5 h[0] += a; h[1] += b; h[2] += c; h[3] += d;
Voici le code complet : http://pastebin.com/fjL3GJMK

Le souci, est que le hash est faux et en plus si on exécute le programme 2 fois sur le même mot le hash diffère à chaque fois.

Auriez vous une idée, est ce un souci d'algo ou de "codage" ?

Merci d'avance.

Bonne soirée

EDIT : J'ai vu plusieurs de mes erreurs, ca m'apprendra à ne pas faire de break ...

Je corrige ca dans les jours à venir :)

08/03/2011, 06h31
Sve@r
Citation:
Envoyé par geek-59600

//ajouter le résultat au bloc précédent:

Code:

1 2 3 4 h[0] += a; h[1] += b; h[2] += c; h[3] += d;

Voici le code complet : http://pastebin.com/fjL3GJMK

Le souci, est que le hash est faux et en plus si on exécute le programme 2 fois sur le même mot le hash diffère à chaque fois.

Auriez vous une idée, est ce un souci d'algo ou de "codage" ?
Salut
"ajouter" le résultat au bloc précédent signifie concaténer et non additionner...

Je me permet d'émettre une réserve, en effet j'ai vu dans plusieurs code sur le MD5 que c'est bien une addition qui est réalisé .

Pour le moment j'en suis la :

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
 
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
 
int func_f (int b, int c, int d);
int func_g (int b, int c, int d);
int func_h (int b, int c, int d);
int func_i (int b, int c, int d);
 
int main (int argc,char* argv[])
  {  
  unsigned long long int puissance_2_32 = 0x100000000;
    char* message = "1";
    char* malloced_data = NULL;
    char  add_1 = 128;
  char  result[33] = {0};
 
    unsigned long long message_size = (unsigned long long)strlen(message);
    unsigned long long nbr_paquet = (message_size/56)+1;
 
    unsigned int a, b, c, d, f, g, temp, i = 0, j = 0;
 
  unsigned int w[16] = {0};
 
    unsigned 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};
 
  int k[64];
 
    int h[4] = {0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476};
 
  for (i = 0 ; i < 64 ; i++)
   k[i] = (unsigned int) floor((fabs(sin(i + 1)))*puissance_2_32);
 
    malloced_data = calloc(1,((56*nbr_paquet)+sizeof(long long int)));
 
    if (malloced_data == NULL){
     printf ("!calloc \n");
     return -1;}
 
    memcpy(malloced_data,message,message_size);
 
   memcpy(malloced_data+message_size,&add_1,1);
   memcpy(malloced_data+56*nbr_paquet,&message_size,sizeof(long long int));
 
 
  for (i = 0 ; i < 64 ; i++){
   if (i%16 == 0)
    {
     printf ("\n");
    }
   if (i%4 == 0)
    {
     printf ("\t");
    }
  printf ("%02x",(unsigned char)malloced_data[i]);} 
  printf ("\n");
 
 
  for (j = 0 ; j < nbr_paquet ; j++){
   printf ("PAQUET no %d \n",j);
 
   for (i = 0 ; i < 16 ; i++){
    memcpy(&w[i],(malloced_data+(64*j)+ (i*4)),4);}  
 
   a = h[0];
   b = h[1];
   c = h[2];
   d = h[3];
 
   for (i = 0 ; i < 64 ; i++){
    if ( (i>= 0) && ( i<=15)){
     f = func_f(b, c, d);
     g = i;}
 
    else if ((i>= 16) && ( i<=31)){
     f = func_g (b, c, d);
     g = (5*i + 1)%16;}
 
    else if ((i>= 32) && ( i<=47)){
     f = func_h(b, c, d);
     g = (3*i + 5)%16;}
 
    else{
     f = func_i(b, c, d);
     g = (7*i)%16;}
 
    temp = d;
    d = c;
    c = b;
    b = ROTATE_LEFT (a + f + k[i] + w[g], r[i]) + b; 
    a = temp;}
 
   h[0] += a;
   h[1] += b;
   h[2] += c;
   h[3] += d;}
 
   printf ("Message original : %s \n",message);
 
   printf ("Hash : ");
   printf ("%02x",h[0]);
   printf ("%02x",h[1]);
   printf ("%02x",h[2]);
   printf ("%02x\n",h[3]);
 
   free(malloced_data);
 
    return 0;
  }
 
int func_f (int b, int c, int d)
 {
  return ((b & c)|((~b) & d));
 }
 
int func_g (int b, int c, int d)
 {
  return ((b & d)|(c & (~d)));
 }
 
int func_h (int b, int c, int d)
 {
  return b^c^d;
 }
 
int func_i (int b, int c, int d)
 {
  return c ^ (b | (~d));
 }

Mais le hash est toujours mauvais, auriez vous une solution ?

15/03/2011, 15h11
ram-0000

Une suggestion : copier/coller le code disponible dans la RFC 1321. Celui ci il marche et il a été validé.
15/03/2011, 18h25
geek-59600

Bonsoir,

J'ai déja lu la RFC, le souci n'étant pas d'obtenir une fonction mais bien de la "refaire" j'suis du genre à réinventer la roue bien que ca ne serve à rien je le reconnais j'aime bien comprendre le fond de la chose.

Je me suis basé sur le pseudo-code dispo cependant j'arrive pas a un résultat correct ; je pense comparer plusieurs code que j'ai trouvé afin de comprendre mon erreur.

Bonne soirée.