%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Cryptographie/Cryptographie|Accueil · Cryptographie]] > > | [[Code et Développement/Programmation/Cryptographie/05_Algorithme RSA\|← Algorithme RSA]] | | > |:---|---:| %% nav-fin %% # Tables de hachage ## Les fonctions de hachage cryptographique Une fonction de hachage calcule une **empreinte numérique** à partir d'une donnée. L'empreinte identifie rapidement la donnée d'origine. La donnée peut être de tout type et de toute taille : un texte, un livre, un film. L'empreinte a toujours la même taille. Une fonction de hachage cryptographique respecte plusieurs propriétés : - elle est **déterministe** : une même donnée donne toujours la même empreinte ; - elle se **calcule rapidement**, idéalement en un seul parcours de la donnée ; - elle est **à sens unique** : on ne peut pas retrouver la donnée à partir de l'empreinte ; - elle est **résistante aux collisions** : il est très difficile de trouver deux données différentes qui ont la même empreinte ; - elle produit un **effet avalanche** : une petite modification de la donnée change complètement l'empreinte. ## SHA-256 SHA-256 est une fonction de hachage très utilisée, notamment dans les chaînes de blocs comme celle du bitcoin. Elle produit une empreinte de 256 bits, écrite avec 64 chiffres hexadécimaux. Le module `hashlib` de la bibliothèque standard la fournit. ```python import hashlib print(hashlib.sha256(b'Camarade').hexdigest()) # b7d4e76a230a2383657622f6bb486688f956b485b65ee23af305e42d4d627d8d print(hashlib.sha256(b'Kamarade').hexdigest()) # 9b8753c509d0b9695d306a68bc94db3728c277b2e82ac09c3150c35d22548f4e ``` Une seule lettre change, et l'empreinte change entièrement. **À manipuler :** modifiez un caractère dans l'un des textes. Recopier le premier texte dans le second montre que la fonction est déterministe. ```sq-empreinte texte: Camarade autre: Kamarade ``` ## Chercher une valeur dans une liste Pour savoir si une valeur est dans une liste, Python la compare à chaque élément. ```python l = list(range(100)) print('x' in l) # False, après 100 comparaisons ``` Le nombre de comparaisons, et donc la durée de la recherche, augmente proportionnellement au nombre d'éléments. Une liste de 100 000 éléments demande jusqu'à 100 000 comparaisons. ## Les dictionnaires, des tables de hachage Le dictionnaire de Python est une **table de hachage**. Une fonction de hachage calcule, à partir de la clé, l'indice de la case où la valeur est rangée. La recherche n'a plus à parcourir les éléments : elle va directement à la case. Sa durée ne dépend pratiquement pas de la taille du dictionnaire. **À manipuler :** faites varier la taille et la position de la valeur cherchée. ```sq-recherche-liste-dict taille: 100 ``` ## Une fonction de hachage simple Cet exemple construit une table de hachage de 8 cases pour des noms de couleurs. On convertit d'abord le mot en entier. Chaque caractère a un code entre 0 et 255, donné par la fonction `ord`. Le mot est lu comme un nombre écrit en base 256. Pour le mot « blue » : 98 × 256³ + 108 × 256² + 117 × 256 + 101 = 1 651 275 109. ```python def str_to_int(x): """Renvoie l'entier associé au mot x, lu en base 256.""" n = 0 for i in range(len(x)): n = n + ord(x[i]) * 256 ** (len(x) - i - 1) return n print(str_to_int('blue')) # 1651275109 ``` L'indice de la case est le reste de la division par la taille de la table, ici 8. ```python def hachage(x): return str_to_int(x) % 8 print(hachage('red')) # 4 print(hachage('blue')) # 5 print(hachage('yellow')) # 7 print(hachage('purple')) # 5 ``` Cette fonction est à sens unique : l'indice 5 ne permet pas de retrouver le mot. ## Les collisions « blue » et « purple » donnent le même indice, 5. Deux clés différentes tombent dans la même case : c'est une **collision**. Deux méthodes résolvent les collisions : - le **chaînage** : chaque case contient une liste des couples clé-valeur qui y tombent ; - l'**adressage ouvert** : la clé en collision est rangée dans une autre case libre de la table. **À manipuler :** insérez les mots un par un. Les mots en collision sont chaînés dans leur case. ```sq-hachage taille: 8 mots: red, blue, yellow, purple ``` ## Hachage cryptographique et table de hachage La fonction modulo 8 de cette page sert seulement à ranger des données dans une table. Elle produit souvent des collisions, ce qui est acceptable pour une table. Une fonction de hachage cryptographique comme SHA-256 doit au contraire rendre les collisions pratiquement introuvables. Pour une table de hachage, la fonction doit se calculer rapidement : sinon, la table perd son intérêt face à une recherche dans une liste. ## Stocker les mots de passe Un site ne stocke pas les mots de passe en clair. Il stocke leur empreinte. À la connexion, il calcule l'empreinte du mot de passe saisi et la compare à l'empreinte stockée. Une fuite de la base ne révèle alors que des empreintes. Une empreinte SHA-256 seule ne suffit pas, pour deux raisons : - deux utilisateurs qui ont le même mot de passe ont la même empreinte ; - des tables précalculées associent les empreintes des mots de passe courants à ces mots de passe. On ajoute donc un **sel** : une valeur aléatoire propre à chaque utilisateur. Le sel est concaténé au mot de passe avant le hachage, puis stocké avec l'empreinte. Deux mots de passe identiques donnent alors deux empreintes différentes, et les tables précalculées ne servent plus. SHA-256 est rapide : un attaquant peut tester des milliards de mots de passe par seconde. Pour les mots de passe, on utilise des fonctions lentes à dessein, dont on règle le coût : PBKDF2, bcrypt, scrypt ou Argon2. ```python import hashlib import os sel = os.urandom(16) # 16 octets aléatoires, propres à cet utilisateur empreinte = hashlib.pbkdf2_hmac("sha256", "motdepasse".encode(), sel, 600_000) # On stocke sel et empreinte. Le mot de passe n'est jamais stocké. # À la connexion : même calcul avec le sel stocké, puis comparaison. essai = hashlib.pbkdf2_hmac("sha256", "motdepasse".encode(), sel, 600_000) print(essai == empreinte) # True ``` Le dernier argument, 600 000, est le nombre de répétitions du calcul. Il rend chaque essai plus long pour un attaquant. %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Cryptographie/Cryptographie|Accueil · Cryptographie]] > > | [[Code et Développement/Programmation/Cryptographie/05_Algorithme RSA\|← Algorithme RSA]] | | > |:---|---:| %% nav-fin %%