A Pearson -kivonat egy olyan hash-függvény , amelyet úgy terveztek, hogy gyorsan fusson 8 bites regiszterrel rendelkező processzorokon . Tetszőleges számú bájt bemenete esetén egyetlen bájtot ad vissza kimenetként, ami nagymértékben függ a bemenet minden egyes bájtjától. Megvalósítása mindössze néhány utasítást igényel, valamint egy 256 bájtos keresési táblázatot , amely 0 és 255 közötti értékek permutációját tartalmazza. [1] [2]
Ez a hash függvény a CBC-MAC , amely 8 bites helyettesítési titkosítást használ, helyettesítő táblán keresztül valósítva meg . A 8 bites titkosításnak kicsi a kriptográfiai erőssége , így a Pearson-féle hash függvény szintén nem kriptográfiai, de hasznos hash-táblázatok megvalósításához vagy az adatok integritásának ellenőrzéséhez, a következő előnyökkel:
Egyik hátránya a többi, 8 bites processzorokhoz tervezett hash algoritmushoz képest a javasolt 256 bájtos keresőtábla, amely túl nagy lehet egy kis, programmemóriával rendelkező mikrokontroller számára, több száz bájtos nagyságrendben. Ennek megoldása egy egyszerű permutációs függvény használata a programmemóriában tárolt táblázat helyett. Azonban egy túl egyszerű függvény, például T[i] = 255-i, használata kényelmetlen hash-függvényként, mert az anagrammák ugyanazt a hash értéket eredményezik; másrészt egy túl bonyolult függvény negatív hatással lesz a sebességre. Táblázat helyett függvény használata lehetővé teszi a blokk méretének bővítését is. Az ilyen függvényeknek természetesen bijektíveknek kell lenniük , akárcsak táblázatos változataik.
Az algoritmus a következő pszeudokóddal írható le , amely a C üzenetkivonatot a T permutációs tábla segítségével számítja ki:
h := 0 minden c -hez a C hurokban h := T[h xor c] end hurok return hEgy hash h-változó többféleképpen inicializálható, például a bemeneti karakterlánc hosszával C modulo 256; konkrétan ezt a megoldást a Python implementáció használja .
A paraméterhez pszeudo-véletlenszerűentable kevert lista szükséges a [0..255] tartományban. Könnyen előállítható egy beépített függvénnyel , és permutációra használható: rangerandom.shuffle
véletlenszerű importálási keverésből _ példa_tábla = lista ( tartomány ( 0 , 256 )) shuffle ( example_table ) def hash8 ( üzenet , táblázat ): hash = len ( üzenet ) % 256 for i in message : hash = táblázat [( hash + ord ( i )) % 256 ] return hash64 bites hash generálás megvalósítása C nyelven .
void Pearson16 ( const unsigned char * x , size_t len , char * hex , size_t hexlen ) { size_t i ; méret_t j ; unsigned char h ; előjel nélküli char hh [ 8 ]; static const unsigned char T [ 256 ] = { // A 0-255 bármilyen (véletlen) sorrendben megkeverve elegendő 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 ]); }A fent használt séma az algoritmus nagyon egyszerű megvalósítása egy egyszerű kiterjesztéssel, amely 8 bitnél hosszabb hash-t generál. Ez a kiterjesztés tartalmaz egy külső ciklust (vagyis az összes olyan utasítássort, amely változót tartalmaz j) és egy tömböt hh.
Egy adott karakterláncra vagy adatra Pearson eredeti algoritmusa csak egy 8 bites kimenetet, egy egész számot [0..255] állít elő. Az algoritmus azonban rendkívül egyszerűvé teszi bármilyen hosszúságú hash létrehozását. Ahogy Pearson rámutatott, a karakterlánc bármely bitjének megváltoztatása teljesen más hash-t eredményez az algoritmusában. A fenti kódban a belső ciklus minden egyes befejezése után a karakterlánc első bájtja eggyel nő (a karakterlánc megváltoztatása nélkül).
Minden alkalommal, amikor az adatok első bájtján egyszerű módosítást hajtanak végre, egy másik Pearson-kivonat generálódik a változóban h. A függvény Chexadecimális karakterekből egy hash-t hoz létre számos 8 bites Pearson-kivonat összefűzésével (a változóban gyűjtve hh). Ahelyett, hogy 0 és 255 közötti értéket adna vissza, ez a függvény 0 és 18446744073709551615 (= 264 - 1) közötti értéket generál .
Ez a példa azt mutatja, hogy a Pearson-algoritmus felhasználható tetszőleges hosszúságú hash-ek generálására 8 bites hash-értékek sorozatának összefűzésével, amelyek mindegyike egyszerűen a karakterlánc enyhe módosításával számítható ki a hash-függvény minden egyes kiszámításakor. Tehát ugyanaz az alapvető logika alkalmazható 32 vagy 128 bites hash létrehozására.