Hashingul Pearson este o funcție hash concepută pentru a rula rapid pe procesoare cu un registru de 8 biți . Având în vedere o intrare de orice număr de octeți, returnează un singur octet ca ieșire, care este foarte dependent de fiecare octet al intrării. Implementarea sa necesită doar câteva instrucțiuni, precum și un tabel de căutare de 256 de octeți , care conține o permutare a valorilor de la 0 la 255. [1] [2]
Această funcție hash este CBC-MAC , care utilizează un cifr de substituție de 8 biți , implementat printr- un tabel de substituție . Un cifr de 8 biți are o putere criptografică mică , așa că funcția hash a lui Pearson nu este nici criptografică, dar este utilă pentru implementarea tabelelor hash sau verificarea integrității datelor, având următoarele avantaje:
Unul dintre dezavantajele sale, în comparație cu alți algoritmi hash proiectați pentru procesoare pe 8 biți, este tabelul de căutare de 256 de biți propus, care poate fi prea mare pentru un microcontroler mic cu memorie de program de ordinul a câteva sute de octeți. O soluție pentru aceasta este să utilizați o funcție simplă de permutare în loc de un tabel stocat în memoria programului. Cu toate acestea, utilizarea unei funcții prea simplă, cum ar fi T[i] = 255-i, este incomod de utilizat ca funcție hash, deoarece anagramele vor avea ca rezultat aceeași valoare hash; pe de altă parte, o funcție prea complexă va avea un impact negativ asupra vitezei. Utilizarea unei funcții mai degrabă decât a unui tabel vă permite, de asemenea, să extindeți dimensiunea blocului. Astfel de funcții, desigur, trebuie să fie bijective , ca și variantele lor tabulare.
Algoritmul poate fi descris prin următorul pseudocod , care calculează hash-ul mesajului C folosind tabelul de permutare T:
h := 0 pentru fiecare c din C bucla h := T[h xor c] bucla de sfârșit returnare hO variabilă hash hpoate fi inițializată în diferite moduri, cum ar fi lungimea șirului de intrare C modulo 256; în special, această soluție este utilizată în implementarea Python .
Parametrul tablenecesită o listă amestecată pseudo-aleatorie în intervalul [0..255]. Poate fi generat cu ușurință cu o funcție încorporată range și utilizat random.shufflepentru permutare:
de la import aleatoriu amestecat example_table = listă ( interval ( 0 , 256 )) amestecare ( example_table ) def hash8 ( mesaj , tabel ): hash = len ( mesaj ) % 256 pentru i în mesaj : hash = tabel [( hash + ord ( i )) % 256 ] return hashImplementarea generării hash pe 64 de biți în limbaj C.
void Pearson16 ( const unsigned char * x , size_t len , char * hex , size_t hexlen ) { dimensiune_t i ; dimensiunea_t j ; nesemnat char h ; nesemnat char hh [ 8 ]; static const unsigned char T [ 256 ] = { // 0-255 amestecat în orice ordine (aleatorie) este suficient 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 , // 15 , 43 , 119 , 224 , 71 , 122 , 142 , 42 , 160 , 104 , 48 , 247 , 103 , 15 , 11 , 138 , 239 // 16 }; pentru ( j = 0 ; j < 8 ; ++ j ) { h = T [( x [ 0 ] + j ) % 256 ]; pentru ( 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 ]); }Schema folosită mai sus este o implementare foarte simplă a algoritmului cu o extensie simplă pentru a genera un hash mai lung de 8 biți. Această extensie conține o buclă exterioară (adică toate liniile de instrucțiuni care includ o variabilă j) și o matrice hh.
Pentru un șir dat sau o bucată de date, algoritmul original al lui Pearson produce doar o ieșire de 8 biți, un întreg [0..255]. Cu toate acestea, algoritmul face extrem de ușor generarea unui hash de orice lungime. După cum a subliniat Pearson, schimbarea oricărui bit dintr-un șir face ca algoritmul său să producă un hash complet diferit. În codul de mai sus, după fiecare finalizare a buclei interioare, primul octet al șirului este mărit cu unul (fără a schimba șirul în sine).
De fiecare dată când se efectuează o simplă modificare a primului octet de date, este generat un hash Pearson diferit, în variabila h. Funcția Ccreează un hash de caractere hexazecimale prin concatenarea unui număr de hash-uri Pearson de 8 biți (colectate în variabila hh). În loc să returneze o valoare de la 0 la 255, această funcție generează o valoare de la 0 la 18446744073709551615 (= 264 - 1).
Acest exemplu arată că algoritmul lui Pearson poate fi folosit pentru a genera hashe-uri de orice lungime dorită prin concatenarea unei secvențe de valori hash de 8 biți, fiecare calculată pur și simplu prin modificarea ușoară a șirului de fiecare dată când funcția hash este calculată. Deci aceeași logică de bază poate fi aplicată pentru a genera hashe-uri de 32 sau 128 de biți.