GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Projet fonction de hachage, complément pour le C ======

<WRAP tip>Il faut lire la [[nsi:tds:cryptographie:hash|fiche principale]]. Il ne s'agit ici que d'un complément.</WRAP>

===== Les types =====

L'algorithme fait un grand usage de mot de 4 octets. C'est le type ''unsigned long''.

On utiliser aussi des octets simples. C'est le type ''unsigned char''.

Les autre entiers comme les indices peuvent utiliser le type ''int'' de base.

===== Les constantes =====

L'algorithme utilise beaucoup de valeurs prédéfinies que l'on peut stocker dans des tableaux. Par exemple pour les valeurs ''K'' :

<code c>
const unsigned long K[] = {0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};
</code>

===== Les calculs =====

On n'a pas à se soucier de l'addition : puisque nous faisons des additions sur des mots de 4 octets, si une addition dépasse la capacité, on n'aura pas d'erreur, on fait simplement un tour de cadran ce qui revient à faire un modulo.

On a besoin d'une fonction de rotation. Voici une possibilité :

<code c>
unsigned long roll_left(unsigned long w, int r)
{
    // w décalé tournée à gauche de r bits
    unsigned  mask1 = (1 << r) - 1;
    return ((w >> (32 - r) & mask1) | ((w << r) & ~mask1));
}
</code>

Autrement on dispose des opérateurs ET : ''%%&%%'', OU : ''%%|%%'', NON : ''%%~%%'' et OU-EX : ''%%^%%''.

Le modulo s'écrit ''%%%%%'' comme en Python.

===== Conversions long - byte =====

On a vu dans la fiche principale que l'on devait faire des conversions entre :
  * des octets (bytes) car c'est ainsi qu'on lit les données entrantes, qu'il s'agisse d'un texte ou d'un fichier,
  * et des mots de 32 bits car c'est l'unité de calcul adoptée dans l'algorithme.

Nous avons vu aussi que la conversion se faisait en //Little Endian//.

Je propose de procéder ainsi :

<code c>
// Les octets sont contenus dans le tableau c
// c contient 4 char (octet)
// c[0] contient l'octet de poids faible,
// c[3] l'octet de poids fort
unsigned long char_to_long(const unsigned char* c)
{
    // en little indian
    unsigned long w = 0;
    unsigned long s = 0;
    for (short i=0; i<4; i++){
        w += c[i]<<s;
        s += 8;
    }
    return w;
}

// Cette autre fonction crée le tableau c
// à partir du mot w de 4 octets (type long)
// Comme souvent en C, on crée le tableau avant
// l'appel à la fonction et on fournit le tableau
// de sorte que la fonction remplit le tableau c
// Ici encore, c[3] contient le poids fort.

void long_to_char(unsigned long w, unsigned char* c)
{
    // en little indian
    c[3] = (w & 0xff000000)>>24;
    c[2] = (w & 0x00ff0000)>>16;
    c[1] = (w & 0x0000ff00)>>8;
    c[0] = (w & 0x000000ff);
}
</code>

On peut faire plus simple en utilisant le mot-clé ''union'' :

<code c>
union {
  unsigned long w;
  unsigned char c[4];
} mot;
</code>

Dans ce cas, le tableau ''c'' et l'entier ''w'' occupent le même espace mémoire si bien que modifier l'un modifie l'autre. ''c[0]'' correspond à l'octet de poids faible de ''w'' et ''c[3]'' correspond à l'octet de poids fort. Par exemple :

<code c>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    union {
      unsigned long w;
      unsigned char c[4];
    } mot;
    mot.w = 0x45893612;
    printf("%02x\n", mot.c[1]);
    return 0;
}
</code>

Ce code affiche ''36'', ce qui correspond, en hexadécimal, au contenu de ''%%c[1]%%'', c'est à dire l'octet numéro 1 en partant de la droite dans ''w = 0x45893612''.

On peut même définir le type ''Mot'' pour que tout nos mots de 32 bits aient la même structure. Ce code à le même effet que le précédent.

<code c>
#include <stdio.h>
#include <stdlib.h>

typedef union {
    unsigned long w;
    unsigned char c[4];
} Mot;

int main(void) {
    Mot mot;
    mot.w = 0x45893612;
    printf("%02x\n", mot.c[1]);
    return 0;
}
</code>

===== modules =====

Le module ''string.h'' contient les fonctions :
  * ''strlen'' donnant la taille d'une chaîne de texte,
  * ''strcat'' qui permet de concaténer des chaînes de caractères

On pourra notamment, à la fin, quand on aura calculer les 4 ''unsigned long'' ''h[0]''...''h[1]'' :

<code c>
const char* h_to_hex_str(const unsigned long* h) {
    // chaque h[i] représente 4 octets,
    // l'ensemble des 4 représente donc 16 octets,
    // chaque octet est représenté par deux symboles en hexadécimal
    // donc 32 symboles.
    // En C, une chaîne doit se finir par '\0', soit un 33e symbole.
    char str[33];
    strcpy(str, ""); // initialisation de str
    unsigned char c[4];
    for (int i=0; i<4; i++){
        // on travaille sur h[i] qui produit 8 caractères
        char* s[8]; // chaîne pour les 8 symboles de h[q]
        long_to_char(h[q], c); // conversion long -> char, little endian
        sprintf(s, "%02x%02x%02x%02x", c[0], c[1], c[2], c[3]);
        // la fonction sprintf permet d'écrire directement dans la chaîne s
        strcat(str, s); // on concatène s au bout de str
    }
    return str;
}
</code>

<WRAP tip>Cela fonctionne sur replit mais je ne peux pas le reproduire sur un compilateur chez moi. Suivant le compilateur il peut y avoir des variations. Il existe des versions plus récentes plus tolérantes. On est parfois obligé, comme c'est expliqué [[nsi:langages:c:malloc|ici]], de créer l'objet contenant la réponse avant (ici la chaîne de texte) et de la transmettre à la fonction pour que celle-ci la modifie.</WRAP>