[Ge0]

Salut à tous.
Il y a peu de temps, je me suis penché sur le format PNG par curiosité (je ne sais pas si ça me permettra de résoudre des épreuves, mais enfin, on verra bien).

Lien de la documentation sur le format : http://www.w3.org/TR/REC-png.pdf

Il y a un code C qui permet de générer le code CRC (sur 4 octets) :

Code:

/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];
/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;
/* Make the table for a fast CRC. */
void make_crc_table(void)
{
	unsigned long c;
	int n, k;
	for (n = 0; n < 256; n++) {
		c = (unsigned long) n;
		for (k = 0; k < 8; k++) {
			if (c & 1)
			     c = 0xedb88320L ^ (c >> 1);
			else
			     c = c >> 1;
		}
		crc_table[n] = c;
	}
	crc_table_computed = 1;
}
/* Update a running CRC with the bytes buf[0..len-1]-the CRC
should be initialized to all 1’s, and the transmitted value
is the 1’s complement of the final running CRC (see the
crc() routine below)). */
unsigned long update_crc(unsigned long crc, unsigned char *buf, int len)
{
	unsigned long c = crc;
	int n;
	if (!crc_table_computed)
	        make_crc_table();
	for (n = 0; n < len; n++) {
		c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
	}
	return c;
}
/* Return the CRC of the bytes buf[0..len-1]. */
unsigned long crc(unsigned char *buf, int len)
{
	return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
}

Malgré avoir tenté de comprendre les grandes lignes sur l'algorithme, je ne sais pas d'où vient le "0xedb88320L" dans la fonction void make_crc_table(void). A quoi une telle constante peut-elle correspondre ?

Si ce message se révèle être un spoil trop abusif pour une quelconque épreuve (si tel est le cas, je ne saurai pas laquelle) alors merci de supprimer ce message.

Par ailleurs, si quelqu'un a des explications claires sur cet algorithme dans l'ensemble, je suis preneur.

Bonne journée.

[Iansus]

C'est une supposition, mais à mon avis, une constante était nécessaire, et elle a donc été choisie au pif.
Comme pour le MD5, tu as un tableau d'initialisation nécessaire, et je n'ai toujours pas compris pourquoi ce sont telles valeurs et pas d'autres :

Code:

/* Round 1 */
  FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
  FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
  FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
  FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
  FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
  FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
  FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
  FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
  FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
  FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
  FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
  FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
  FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
  FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
  FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
  FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */

 /* Round 2 */
  GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
  GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
  GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
  GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
  GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
  GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
  GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
  GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
  GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
  GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
  GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */

  GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
  GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
  GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
  GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
  GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */

  /* Round 3 */
  HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
  HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
  HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
  HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
  HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
  HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
  HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
  HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
  HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
  HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
  HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
  HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
  HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
  HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
  HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
  HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */

  /* Round 4 */
  II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
  II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
  II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
  II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
  II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
  II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
  II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
  II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
  II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
  II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
  II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
  II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
  II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
  II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
  II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
  II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */

Après, peut-être que je me trompe...

[Lanselius]

Salut !

Les algorithmes CRC sont très documentés sur le web. Tu trouveras sur developpez.com un descriptif très précis et en français du principe de fonctionnement.

http://dvsoft.developpez.com/Articles/CRC/

Pour ce qui est de la variable mystérieuse valant "edb88320", elle n'a pas du tout été choisie au pif par le concepteur. Voilà un paragraphe explicatif :

There are many C examples of this code around, and they include the
   --  magic constant EDB88320 without comment. This constant has my vote for
   --  obscure constant of the year.  It is not the CRC polynomical.
   --  Just because it bugs me to see it undocumented, here is the derivation.
   --  The CRC polynomial is stated in the standard to be::
   --  x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1
   --  If you set a bit for each non-zero x exponent, NUMBERING FROM THE LEFT,
   --  STARTING AT 1 (as hardware designers used to do in the old days before
   --  most current programmers were born) you'd get:
   --     1101 1011 0111 0001 0000 0110 0100 0001 (DB710641)
   --  This *IS* the CRC polynomial.
   --  But C programmers want to squeze the last cycle out of their
   --  code, so instead of XORing with this obvious constant, and then
   --  shifting, and setting the high order bit, they shift, and then XOR with
   --  a shifted constant with the high order bit set..
   --  So the C programmer needs the real CRC constant shifted right one bit
   --  with the high order bit set (since CRC's shift in one bits) so what they
   --  use is:
   --     1110 1101 1011 1000 1000 0011 0010 0000 (EDB88320)
   --  Which is the constant you find in the reference C code.

Source : http://www.cc.utah.edu/~nahaj/ada/crc/png_crc_table_generator.adb.html

J'en profite pour t'avertir qu'il existe différentes versions de CRC32. L'algorithme est le même, seule le polynome change. Méfie toi donc en cherchant de la documentation et ne t'inquiète pas si tu trouves des images différentes avec d'autres sources.

Enfin, pour éclairer Iansus, MD5 utilise bien des "constantes" de départ à partir desquelles il fabrique l'image renvoyée. Il y en a de deux types :
 - Les quatre constantes qui forment l'image "par défaut", avant toute modification. On les trouve en page 3 de la RFC

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

Le choix est évident. Il s'agit d'avoir une représentation égale de chaque chiffre.
On trouve d'aillleurs dans d'autres versions :

a = 0x67452301; b = 0xEFCDAB89; c = 0x98BADCFE; d = 0x10325476;

Ce qui montre bien que c'est cette représentation égale qui importe, car seule

l'ordre des chiffres a changée.
Mais MD5 utilise aussi un tableau de 44 entiers auquel il applique des fonctions trigonométriques. C'est la partie que tu as cité dans ton post. En réalité, ces constantes ne sont pas si grandes au départ. Voilà leur vraie valeur de départ, tel que l'algorithme a été conçu :

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}

Et encore, si on observe, on voit qu'il y a des répétitions de séquences. En réalité, les seules constantes de départ sont {7, 12, 17, 22}{5, 9, 14, 20} {4, 11, 16, 23}{6, 10, 15, 21}

Soit dans un autre ordre : {4,5,6,7}{9,10,11,12}{14,15,16,17} et {20,21,22,23}
Rien de bien mystérieux en fait 

Si Iansus n'as pas la même chose dans sa source, c'est simplement que son implémentation contient les constantes après certaines opérations fixes. Les calculs ont été fait à part et les résultats inscrits directement dans la source, pour un léger gain de rapidité 

J'avais complètement décortiqué le fonctionnement de md5() il y a pas mal de temps, je crois que je vais essayer de retrouver mes notes pour les partager ici.

J'espère que les liens t'aideront et que c'est maintenant un peu plus clair 

[Ge0]

Je crois que je suis servi & que j'aie tout ce dont j'ai besoin. C'est on ne peut plus clair.

Merci infiniment, Lanselius.