Pearson hashing er en hash-funktion designet til at køre hurtigt på processorer med et 8-bit register . Givet et input på et hvilket som helst antal bytes, returnerer det en enkelt byte som output, hvilket er meget afhængigt af hver byte i inputtet. Dens implementering kræver kun nogle få instruktioner, samt en 256-byte opslagstabel , der indeholder en permutation af værdier fra 0 til 255. [1] [2]
Denne hash-funktion er CBC-MAC , som bruger en 8-bit substitutions-chiffer , implementeret gennem en substitutionstabel . En 8-bit chiffer har ringe kryptografisk styrke , så Pearsons hash-funktion er heller ikke kryptografisk, men den er nyttig til implementering af hashtabeller eller kontrol af dataintegritet, med følgende fordele:
En af dens ulemper sammenlignet med andre hash-algoritmer designet til 8-bit processorer er den foreslåede 256-byte opslagstabel, som kan være for stor til en lille mikrocontroller med programhukommelse i størrelsesordenen flere hundrede bytes. En løsning på dette er at bruge en simpel permutationsfunktion i stedet for en tabel gemt i programhukommelsen. Det er imidlertid ubelejligt at bruge en funktion, der er for enkel, såsom T[i] = 255-i, som en hash-funktion, fordi anagrammer vil resultere i den samme hashværdi; på den anden side vil en funktion, der er for kompleks, have en negativ indflydelse på hastigheden. Ved at bruge en funktion frem for en tabel kan du også udvide blokstørrelsen. Sådanne funktioner skal selvfølgelig være bijektive , ligesom deres tabelvarianter.
Algoritmen kan beskrives med følgende pseudokode , som beregner meddelelsens hash C ved hjælp af permutationstabellen T:
h := 0 for hver c i C -løkke h := T[h xor c] endeløkke retur hEn hash-variabel hkan initialiseres på forskellige måder, såsom længden af inputstrengen C modulo 256; specifikt bruges denne løsning i Python- implementeringen .
Parameteren tablekræver en pseudo-tilfældig blandet liste i området [0..255]. Det kan nemt genereres med en indbygget funktion range og bruges random.shuffletil permutation:
fra tilfældig import shuffle eksempeltabel = liste ( område ( 0 , 256 )) bland ( eksempeltabel ) def hash8 ( besked , tabel ): hash = len ( besked ) % 256 for i i besked : hash = tabel [( hash + ord ( i )) % 256 ] returner hashImplementering af 64-bit hash-generering i C -sprog .
void Pearson16 ( konst usigneret char * x , size_t len , char * hex , size_t hexlen ) { size_t i ; størrelse_t j ; usigneret char h ; usigneret char hh [ 8 ]; statisk konstant usigneret tegn T [ 256 ] = { // 0-255 blandet i enhver (tilfældig) rækkefølge er tilstrækkeligt 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 , 110 , // . 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 ]); }Skemaet brugt ovenfor er en meget simpel implementering af algoritmen med en simpel udvidelse til at generere en hash længere end 8 bit. Denne udvidelse indeholder en ydre sløjfe (dvs. alle linjer med udsagn, der indeholder en variabel j) og et array hh.
For en given streng eller et stykke data producerer Pearsons originale algoritme kun et 8-bit output, et heltal [0..255]. Algoritmen gør det dog ekstremt nemt at generere en hash af enhver længde. Som Pearson påpegede, vil ændring af en hvilken som helst bit i en streng få hans algoritme til at producere en helt anden hash. I koden ovenfor, efter hver fuldførelse af den indre løkke, øges den første byte af strengen med én (uden at ændre selve strengen).
Hver gang en simpel ændring af den første byte af data udføres, genereres en anden Pearson-hash i variablen h. Funktionen Copretter en hash af hexadecimale tegn ved at sammenkæde et antal 8-bit Pearson hashes (samlet i variablen hh). I stedet for at returnere en værdi fra 0 til 255, genererer denne funktion en værdi fra 0 til 18446744073709551615 (= 264 - 1).
Dette eksempel viser, at Pearsons algoritme kan bruges til at generere hashes af enhver ønsket længde ved at sammenkæde en sekvens af 8-bit hashværdier, hver enkelt beregnet ved at ændre strengen en smule, hver gang hashfunktionen beregnes. Så den samme grundlæggende logik kan anvendes til at generere 32 eller 128 bit hashes.