Algorithme md5 problème de congruence

[Jehutyy]

Bonjour,
je viens vous demandez de l'aide car je me suis mis en tête de faire une implémentation en c de l'algorithme de md5.
Mon problème est que je bloque dès le début à cause de la congruence.

Dans la RFC il y est écrit qu'un nombre x de bit doit être ajouter à un mot jusqu'à ce que (taille_du_mot_en bit) = 448 mod 512 .

Bon déjà j'ai un gros soucis car je n'ai jamais appris ce qu'était une congruence, donc je me suis un peu penché sur la question mais je ne comprend toujours pas comment faire.

Par exemple, si mon mot en entrée est un mot de 32 bits. Comment vérifier que 32 est congru à 448 mod 512 ?

bien cordialement
jehutyy

[Rockleader]

On dit que deux entiers relatifs a et b son congrus modulo n ( n;)N* ) et l'on écrit a;)b [n] si et seulement si a et b ont le même reste dans la division par n

En gros:

32 est congru à 448 mod 512 si reste de la division 32/512 == reste de la division de 448/512


Par exemple:

18;)23 [5] car 18 et 23 ont tous les deux 3 comme reste dans la division par 5

Pour plus d'infos: http://www.maths-cours.fr/terminale-s/divisibilite-congruences

[Jehutyy]

Merci beaucoup, j'ai écrit un petit programme de test en python pour trouver des nombres congruents :

Code: Tout sélectionner

 for i in range(1, 100000):
                   if( i % 512 == 448 % 512):
                         print(i)


Et j'obtiens ceci (partie du résultat seulement):
448
960
1472
1984
2496
3008
3520
4032
4544
5056
5568
6080
6592
7104
7616
8128
8640
9152
9664
10176
10688
11200
11712
12224
12736
13248
13760
14272

Peut on en déduire qu'on ne peut calculer une congruence qu'a condition que a soit superieur à b dans l'équation a = b mod x ?

[Rockleader]

C'est un peu loin les congruences pour moi donc je suis plus très sur des propriétés, mais une chose est sûre, à partir du moment ou tu trouves la première

448 dans ton cas..tu n'as même pas besoin de faire tes calculs de modulo il parait évident que tous tes nombres congru modulo 512 seront de la forme

448+512*n


Et non je pense que tu pourras toujours calculé ta congruence.

TU peux très bien dire 448=448[512]

[Ben314]

Un nombre "congru à 448 modulo 512", ça veut bêtement dire de la forme 512k+448 avec k entier, soit encore 512(k+1)-64 (donc en fait, ça veut dire que l'algo demande de "réserver" 64 bits à la fin et qu'en ajoutant ces 64 bits, ça fasse un multiple de 512).

Donc, si au départ ton mot fait B bits, tu calcule le reste R de la division de B+63 par 512 : tu as donc B+63=512Q+R et pour que B+64 fasse un multiple de 512, il suffit d'ajouter X=511-R bits (compris entre 0 et 511)

[Jehutyy]

Bon ba merci beaucoup de vos réponses, c'est un peu velu mais au moins je sais dans quel direction aller.