Pearson hash je hašovací funkce navržená pro rychlý běh na procesorech s 8bitovým registrem . Daný vstup o libovolném počtu bajtů vrací jeden bajt jako výstup, který je vysoce závislý na každém bajtu vstupu. Jeho implementace vyžaduje pouze několik instrukcí a také 256bajtovou vyhledávací tabulku obsahující permutaci hodnot od 0 do 255. [1] [2]
Tato hashovací funkce je CBC-MAC , která používá 8bitovou substituční šifru implementovanou prostřednictvím substituční tabulky . 8bitová šifra má malou kryptografickou sílu , takže Pearsonova hašovací funkce také není kryptografická, ale je užitečná pro implementaci hašovacích tabulek nebo kontrolu integrity dat, přičemž má následující výhody:
Jednou z jeho nevýhod oproti jiným hashovacím algoritmům určeným pro 8bitové procesory je navržená 256bajtová vyhledávací tabulka, která může být pro malý mikrokontrolér s programovou pamětí v řádu několika set bytů příliš velká. Řešením je použití jednoduché permutační funkce namísto tabulky uložené v paměti programu. Použití příliš jednoduché funkce, jako je například T[i] = 255-i, je však nepohodlné pro použití jako hashovací funkce, protože anagramy budou mít za následek stejnou hodnotu hash; na druhou stranu příliš složitá funkce bude mít negativní dopad na rychlost. Použití funkce namísto tabulky také umožňuje rozšířit velikost bloku. Takové funkce samozřejmě musí být bijektivní , stejně jako jejich tabulkové varianty.
Algoritmus lze popsat následujícím pseudokódem , který vypočítá hash zprávy C pomocí permutační tabulky T:
h := 0 pro každé c ve smyčce C h := T[h xor c] konec smyčky návrat hHash proměnná hmůže být inicializována různými způsoby, jako je délka vstupního řetězce C modulo 256; konkrétně se toto řešení používá v implementaci Pythonu .
Parametr tablevyžaduje pseudonáhodný zamíchaný seznam v rozsahu [0..255]. Lze jej snadno vygenerovat pomocí vestavěné funkce range a použít random.shufflepro permutaci:
z náhodného náhodného importu example_table = seznam ( rozsah ( 0 , 256 )) zamíchat ( example_table ) def hash8 ( zpráva , tabulka ): hash = len ( zpráva ) % 256 pro i ve zprávě : hash = tabulka [( hash + ord ( i )) % 256 ] return hashImplementace 64bitového generování hashů v jazyce C .
void Pearson16 ( const unsigned char * x , size_t len , char * hex , size_t hexlen ) { velikost_t i ; velikost_t j ; unsigned char h ; unsigned char hh [ 8 ]; static const unsigned char T [ 256 ] = { // 0-255 zamíchané v libovolném (náhodném) pořadí stačí 98 , 6 , 85 , 150 , 36 , 23 , 112 , 164 , 135 , 207 , 169 , 5 , 26 , 64 , 165 , 219 , // 1 61 , 20 , 68 , 89 , 130 , 63 , 52 , 102 , 24 , 229 , 132 , 245 , 80 , 216 , 195 , 115 , // 2 90 , 168 , 156 , 203 , 177 , 120 , 2 , 190 , 188 , 7 , 100 , 185 , 174 , 243 , 162 , 10 , // 3 237 , 18 , 253 , 225 , 8 , 208 , 172 , 244 , 255 , 126 , 101 , 79 , 145 , 235 , 228 , 121 , // 4 123 , 251 , 67 , 250 , 161 , 0 , 107 , 97 , 241 , 111 , 181 , 82 , 249 , 33 , 69 , 55 , // 5 59 , 153 , 29 , 9 , 213 , 167 , 84 , 93 , 30 , 46 , 94 , 75 , 151 , 114 , 73 , 222 , // 6 197 , 96 , 210 , 45 , 16 , 227 , 248 , 202 , 51 , 152 , 252 , 125 , 81 , 206 , 215 , 186 , // 7 39 , 158 , 178 , 187 , 131 , 136 , 1 , 49 , 50 , 17 , 141 , 91 , 47 , 129 , 60 , 99 , // 8 154 , 35 , 86 , 171 , 105 , 34 , 38 , 200 , 147 , 58 , 77 , 118 , 173 , 246 , 76 , 254 , // 9 133 , 232 , 196 , 144 , 198 , 124 , 53 , 4 , 108 , 74 , 223 , 234 , 134 , 230 , 157 , 139 , // 10 189 , 205 , 199 , 128 , 176 , 19 , 211 , 236 , 127 , 192 , 231 , 70 , 233 , 88 , 146 , 44 , // 11 183 , 201 , 22 , 83 , 13 , 214 , 116 , 109 , 159 , 32 , 95 , 226 , 140 , 220 , 57 , 12 , // 12 221 , 31 , 209 , 182 , 143 , 92 , 149 , 184 , 148 , 62 , 113 , 65 , 37 , 27 , 106 , 166 , // 13 3 , 14 , 204 , 72 , 21 , 41 , 56 , 66 , 28 , 193 , 40 , 217 , 25 , 54 , 179 , 117 , // 14 238 , 87 , 240 , 155 , 180 , 170 , 242 , 212 , 191 , 163 , 78 , 218 , 137 , 194 , 175 , 115 , // 43 , 119 , 224 , 71 , 122 , 142 , 42 , 160 , 104 , 48 , 247 , 103 , 15 , 11 , 138 , 239 // 16 }; for ( j = 0 ; j < 8 ; ++ j ) { h = T [( x [ 0 ] + j ) % 256 ]; for ( i = 1 ; i < len ; ++ i ) { h = T [ h ^ x [ i ]]; } hh [ j ] = h ; } snprintf ( hex , hexlen , "%02X%02X%02X%02X%02X%02X%02X%02X" , hh [ 0 ], hh [ 1 ], hh [ 2 ], hh [ 3 ], hh [ 4 ], hh [ 5 ], hh [ 6 ], hh [ 7 ]); }Výše použité schéma je velmi jednoduchou implementací algoritmu s jednoduchým rozšířením pro generování hashe delšího než 8 bitů. Toto rozšíření obsahuje vnější smyčku (tj. všechny řádky příkazů, které obsahují proměnnou j) a pole hh.
Pro daný řetězec nebo část dat vytváří původní Pearsonův algoritmus pouze 8bitový výstup, celé číslo [0..255]. Algoritmus však velmi usnadňuje generování hash libovolné délky. Jak zdůraznil Pearson, změna libovolného bitu v řetězci způsobí, že jeho algoritmus vytvoří úplně jiný hash. Ve výše uvedeném kódu se po každém dokončení vnitřní smyčky první bajt řetězce zvětší o jeden (beze změny samotného řetězce).
Pokaždé, když se provede jednoduchá změna prvního bajtu dat, vygeneruje se jiný Pearsonův hash v proměnné h. Funkce Cvytvoří hash hexadecimálních znaků zřetězením počtu 8bitových Pearsonových hashů (shromážděných v proměnné hh). Namísto vracení hodnoty od 0 do 255 tato funkce vygeneruje hodnotu od 0 do 18446744073709551615 (= 264 - 1).
Tento příklad ukazuje, že Pearsonův algoritmus lze použít ke generování hashů libovolné požadované délky zřetězením posloupnosti 8bitových hodnot hash, z nichž každá se vypočítá jednoduše mírnou úpravou řetězce pokaždé, když se vypočítá hashovací funkce. Takže stejnou základní logiku lze použít pro generování 32 nebo 128 bitových hashů.