Fonctions de hachage en haskell pur

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonsoir à tous, ou plutôt bon matin, vu l'heure. Bref.

Mon grand chéri du moment, parmi les nombreux langages de programmation que compte le monde, c'est le haskell. Et je m'efforce de d'améliorer ma maîtrise de la bête. Pour ce faire, je me suis attaché à coder dans ce beau langage la fonction de hachage SHA-1. Entendons-nous bien : il existe sur hackage un certain nombre d'implémentations de cette fonction dans divers modules, mais sauf erreur de ma part, il s'agit systématiquement de bindings vers l'implémentation en C. C'est moche, quoi. Moi j'ai fait du code pur, au sens de haskell, bien sûr.

Bref, voilà le résultat : si vous avez quelque connaissance en haskell, je suis preneur de toute remarque. Comme à mon habitude, le code est lourdement commenté. Cela étant, je ne décris pas l'algorithme en lui-même, je laisse cette tâche à la spécification officielle, qui est fort bien expliquée sur Wikipédia.

  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
import Data.Char
import Data.Bits

-- La fonction sha1 principale
-- ===========================
--
-- Se contente de faire appel à sha1num et de lui donner sa représentation héxadécimale
sha1 :: [Char] -> [Char]
sha1 m = hd $ sha1num m
    where hd (a, b, c, d, e) = (hexadecimare 8 a) ++ (hexadecimare 8 b) ++ (hexadecimare 8 c) ++ (hexadecimare 8 d) ++ (hexadecimare 8 e)

-- La fonction sha1 numérique
-- ==========================
--
-- Les étapes suivantes sont appliquées dans l'ordre :
--   1. `farcire` rembourre le message qui a alors une longueur multiple de 512 bits.
--   2. `separareN` découpe le message rembourré en tronçons de 512 bits et en fait une liste.
--   3. `separareM` découpe un tronçon en "mots" de 32 bits et en fait une liste.
--   4. `genereW` transforme une liste de 16 mots en une liste de 80 W selon l'algorithme défini dans la spécification.
--   5. À l'issue du `map`, on a donc une liste contenant les listes de 80 W associées à chaque tronçon de 512 bits.
--   6. `statuereH` pose le quintuple contenant les 5 H de départ.
--   7. `sha1nucleus` applique la série de transformations et rotations qui consituent le cœur de SHA-1 aux 80 W d'un
--         même tronçon, à partir d'un quintuple de base.
--   8. Le pli gère l'addition modulo (2^32) du résultat de `sha1nucleus` au quintuple précédent et s'assure que le
--         résultat d'un tronçon serve de base au tronçon suivant.
sha1num :: [Char] -> (Integer, Integer, Integer, Integer, Integer)
sha1num m = foldl (\x y -> addere32 x $ sha1nucleus x y) statuereH (map (genereW . separareM) (separareN $ farcire m))
    where 
          -- Fonction de bourrage
          -- `numerisare` transforme une chaîne de caractères en un grand nombre par le biais du code ASCII de chaque
          --   caractère, multiplié à la puissance adéquate de (2^8)=256.
          -- `farsura` détermine combien de 0 ajouter au résultat de `numerisare`*2+1 pour atteindre une longueur
          --   multiple de 512 bits.
          -- Il ne reste plus alors qu'à faire une simple addition de la longueur en bits pour qu'elle se retrouve,
          --   en gros-boutiste, à la toute fin du nombre.
          -- Les nombreux appels à `toInteger` sont nécessaires car GHC préférerait travailler en Int et tronque les résultats.
          farcire m = ((numerisare m)*2+1) * (2^(farsura $ 8*length m)) + toInteger (8*length m)
              where farsura l
                      | l `mod` 512 < 448 = 511 - (l `mod` 512)
                      | otherwise = 1023 - (l `mod` 512)
                    numerisare m
                      | m == [] = 0
                      | otherwise = foldl1 (\x y -> 256*x+y) (map (toInteger . ord) m)
          -- Sans difficulté, utilise la fonction de division euclidienne et de modulo pour individualiser les tronçons
          --   de 512 bits et en faire un tableau.
          separareN x
            | x == 0 = []
            | otherwise = (separareN $ x `div` (2^512)) ++ [x `mod` (2^512)]
          -- Le fonctionnement général est le même mais en s'assurant que l'on obtienne 16 "mots" par tronçon, d'où
          --   l'utilisation de `replicate`.
          separareM x = (replicate (16 - (length $ separareMbis x)) 0) ++ (separareMbis x)
              where separareMbis x
                      | x == 0 = []
                      | otherwise = (separareMbis $ x `div` (2^32)) ++ [x `mod` (2^32)]
          -- Fonction de génération des W à partir des 16 "mots" de départ
          -- L'utilisation de `iterate` qui génère une liste de chacune des étapes de la création progressive
          --   de la liste des W est, étonnamment, considérablement plus rapide qu'une fonction récursive. La
          --   64e étape est celle à laquelle nous désirons arriver.
          -- La fonction `sha1nucleus` a besoin de savoir où elle en est dans le pli pour choisir la fonction
          --   non-linéaire f_t et la constante K_t, c'est pourquoi on renvoie une liste de paires (W_t, t).
          genereW xs = zip ((iterate (iteranda) xs) !! 64) [0..79]
              where iteranda xs = xs ++ [rotl 1 ((w3 xs) `xor` (w8 xs) `xor` (w14 xs) `xor` (w16 xs))]
                      where w3 xs = (xs !! (length xs - 3))
                            w8 xs = (xs !! (length xs - 8))
                            w14 xs = (xs !! (length xs - 14))
                            w16 xs = (xs !! (length xs - 16))
          -- Un simple quintuple contenant les valeurs de départ définies par la spécification.
          statuereH = (0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0)
          -- Le cœur de SHA-1
          -- 
          -- La fonction consiste à "fondre" tous les W dans le quintuple de départ, au moyen d'une même série
          --   d'opérations qui mélangent le contenu dans tous les sens. Ces opérations étant à peu près les mêmes
          --   à chaque étape, un pli est particulièrement efficace.
          -- `miscere` est simplement un moyen de raccourcir la définition de `functio` dont la première partie
          --   est particulièrement complexe.
          -- `variabilis` correspond à f_t, la fonction qui varie en fonction du tour où l'on est.
          -- `constans` au contraire est la série de constantes K_t.
          -- Dans les deux cas, il n'y a que 4 valeurs possibles, les t étant regroupés en 4 groupes : le (t `div` 20)
          --   sert à raccourcir l'écriture.
          -- `optio`, `paritas` et `majoritas` sont des fonctions utilisées par d'autres algorithmes de hachage, que
          --   l'on pourra au besoin extraire et "globaliser".
          -- Dans `optio`, la partie après le OU logique est normalement ((NON x) ET Z) mais la fonction `complement`
          --   de Data.Bits donne des résultats surprenants avec les Integer et fausse totalement le calcul. Le
          --   substitut utilisé ici a exactement la même table de vérité.
          sha1nucleus initium xs = foldl (functio) initium xs
              where functio (a, b, c, d, e) (w, t) = (miscere a b c d e w t, a, (rotl 30 b), c, d)
                      where miscere a b c d e w t = ((rotl 5 a) + (variabilis (t `div` 20) b c d) + e + (constans !! (t `div` 20)) + w) `mod` (2^32)
                            variabilis t
                              | t == 0 = optio
                              | t == 1 || t == 3 = paritas
                              | t == 2 = majoritas
                            optio x y z = (x .&. y) .|. ((x `xor` z) .&. z)
                            paritas x y z = x `xor` y `xor` z
                            majoritas x y z = (x .&. y) .|. (x .&. z) .|. (y .&. z)
                            constans = [0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6]
          -- La fonction qui additionne terme à terme et modulo 2^32 deux quintuples.
          addere32 (a, b, c, d, e) (f, g, h, i, j) = ((a+f) ` mod` (2^32), (b+g) ` mod` (2^32), (c+h) ` mod` (2^32), (d+i) ` mod` (2^32), (e+j) ` mod` (2^32))

-- Il n'est pas garanti que les fonctions de décalage et de rotation de
--   Data.Bits fonctionnent selon nos besoins, en raison de la taille
--   variable des Integer. On a préféré les réécrire.
rotl s n = ((shl s n) .|. (shr (32-s) n)) `mod` (2^32)
rotr s n = ((shl (32-s) n) .|. (shr s n)) `mod` (2^32)
shl s n = n * (2^s)
shr s n = n `div` (2^s)

-- Cette fonction transforme un entier `decim` en sa représentation héxadécimale
--   sur `long` caractères. Le "truc" pour obtenir une longueur fixe est le même que
--   que celui utilisé dans la fonction `separareM` ci-dessus.
hexadecimare :: Int -> Integer -> [Char]
hexadecimare long decim = (replicate (long - (length $ hex decim)) '0') ++ (hex decim)
    where hex d
            | d == 0 = []
            | otherwise = (hex $ d `div` 16) ++ [hexs !! (fromIntegral $ d `mod` 16)]
          hexs = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']

Si le titre est assez général, c'est que j'envisage de passer ensuite à d'autres fonctions de hachage, en particulier SHA-2 et MD5 dont le fonctionnement est très proche de celui-ci, au point que l'on peut peut-être factoriser du code de l'une à l'autre. À voir.

PS : désolé, le code est assez large, il faut faire défiler pour voir la fin. :-/

Édité par Dominus Carnufex

#JeSuisGrimur #OnVautMieuxQueÇa

+0 -0

Je poste deux remarques histoire de ne pas laisser ce topic vide, mais globalement j'aime bien ton code et je cherche plus à lancer la discussion qu'à critiquer. :)

Pour la présentation, en général je préfère faire de nombreuses petites fonctions « toplevel » plutôt que de gros where. À mon humble avis, une fonction devrait prendre 6 à 10 lignes de code, tous let et where compris. Cela permet, entre autres, de placer tous les commentaires concernant une fonction avant celle-ci, et donc de voir toute la fonction (et son commentaire) d'un coup.

Ensuite, il suffit de ne pas exporter les helper functions pour éviter de polluer l'espace de noms.

Deuxième idée : pourquoi hacher des [Char] ? Perso, j'aurais tendance à utiliser des ByteString, voire une variante non-paresseuse de ByteString. Vu l'utilisation que l'on fait (en général) d'un hash comme SHA1, je ne pense pas que ça pose de problème aux utilisateurs de ta bibliothèque. Et l'évaluation stricte ferait probablement gagner en performances, dans ce cas (sauf si le compilateur s'en est déjà aperçu avant nous).

D'ailleurs, as-tu mesuré les performances d'un tel code ? Ce serait intéressant de comparer avec d'autres implémentations.

Bonne journée ! GuilOooo

Canis Lupus pour vous servir

+0 -0
Auteur du sujet

Merci pour l'intérêt porté. ^^

Pour la présentation, comme tu l'as dit, c'est une affaire de goûts, donc je ne vais pas épiloguer.

Pour le ByteString, je n'avais pas envie d'introduire une dépendance supplémentaire qui m'obligeait à utiliser un espace de nom particulier. Mais je n'avais pas prêté attention au fait qu'un Char peut contenir n'importe quel caractère Unicode y compris sur plusieurs octets, donc la fonction sera erronée pour des caractères chinois ou autres. Je corrigerai.

Je n'ai pas fait de mesure de performance en bonne et due forme, je me suis simplement assuré que la génération du hash était instantanée.

#JeSuisGrimur #OnVautMieuxQueÇa

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte