Pearson-hajautus on hash-toiminto , joka on suunniteltu toimimaan nopeasti prosessoreissa, joissa on 8-bittinen rekisteri . Kun syötetään mikä tahansa tavumäärä, se palauttaa yhden tavun lähtönä, joka riippuu suuresti jokaisesta syötteen tavusta. Sen toteuttaminen vaatii vain muutaman käskyn sekä 256-tavuisen hakutaulukon , joka sisältää arvojen permutoinnin välillä 0 - 255. [1] [2]
Tämä hash-funktio on CBC-MAC , joka käyttää 8-bittistä korvaussalausta , joka on toteutettu korvaustaulukon kautta . 8-bittisellä salauksella on vähän salausvoimakkuutta , joten Pearsonin hash-funktio ei myöskään ole kryptografinen, mutta se on hyödyllinen hash-taulukoiden toteuttamiseen tai tietojen eheyden tarkistamiseen, ja sillä on seuraavat edut:
Yksi sen haitoista muihin 8-bittisille prosessoreille suunniteltuihin hash-algoritmeihin verrattuna on ehdotettu 256-tavuinen hakutaulukko, joka voi olla liian suuri pienelle mikro-ohjaimelle, jossa on useita satoja tavuja ohjelmamuistilla. Kiertotapa tähän on käyttää yksinkertaista permutaatiofunktiota ohjelmamuistiin tallennetun taulukon sijaan. Liian yksinkertaisen funktion, kuten T[i] = 255-i, käyttäminen on kuitenkin hankalaa käyttää hash-funktiona, koska anagrammit johtavat samaan hash-arvoon; toisaalta liian monimutkainen toiminto vaikuttaa negatiivisesti nopeuteen. Voit myös laajentaa lohkon kokoa käyttämällä funktiota taulukon sijaan. Tällaisten funktioiden on tietysti oltava bijektiivisiä , kuten niiden taulukkomuunnelmat.
Algoritmi voidaan kuvata seuraavalla pseudokoodilla , joka laskee viestin hajautusarvon C permutaatiotaulukon T avulla:
h := 0 jokaiselle c :lle C - silmukassa h := T[h xor c] loppusilmukan paluu hHash-muuttuja hvoidaan alustaa eri tavoin, kuten syöttömerkkijonon pituus C modulo 256; erityisesti tätä ratkaisua käytetään Python -toteutuksessa .
Parametri tableedellyttää näennäissatunnaisesti sekoitettua luetteloa alueella [0..255]. Se voidaan helposti luoda sisäänrakennetulla funktiolla range ja käyttää random.shufflepermutaatioon:
satunnaisesta tuontisekoituksesta _ _ esimerkkitaulukko = lista ( alue ( 0 , 256 )) sekoitus ( esimerkkitaulukko ) def hash8 ( viesti , taulukko ): hash = len ( viesti ) % 256 for i viestissä : hash = taulukko [ ( hash + ord ( i )) % 256 ] return hash64-bittisen hash-luonnon toteutus C -kielellä .
void Pearson16 ( const unsigned char * x , size_t len , char * hex , size_t hexlen ) { koko_t i ; koko_t j ; unsigned char h ; unsigned char hh [ 8 ]; staattinen const etumerkitön merkki T [ 256 ] = { // 0-255 sekoitettuna missä tahansa (satunnaisessa) järjestyksessä riittää 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 ]); }Yllä käytetty menetelmä on hyvin yksinkertainen algoritmin toteutus, jossa on yksinkertainen laajennus yli 8 bitin pituisen tiivisteen generoimiseksi. Tämä laajennus sisältää ulomman silmukan (eli kaikki lauserivit, jotka sisältävät muuttujan j) ja taulukon hh.
Tietylle merkkijonolle tai datalle Pearsonin alkuperäinen algoritmi tuottaa vain 8-bittisen tulosteen, kokonaisluvun [0..255]. Algoritmin avulla on kuitenkin erittäin helppoa luoda minkä tahansa pituinen hash. Kuten Pearson huomautti, minkä tahansa bitin muuttaminen merkkijonossa saa hänen algoritminsa tuottamaan täysin erilaisen hashin. Yllä olevassa koodissa jokaisen sisäisen silmukan valmistumisen jälkeen merkkijonon ensimmäinen tavu kasvaa yhdellä (muuttamatta itse merkkijonoa).
Joka kerta kun suoritetaan yksinkertainen muutos datan ensimmäiseen tavuun, muuttujassa luodaan erilainen Pearson-tiiviste h. Funktio Cluo heksadesimaalimerkkien tiivisteen yhdistämällä useita 8-bittisiä Pearson-tiivisteitä (kerätty muuttujaan hh). Sen sijaan, että se palauttaisi arvon välillä 0 - 255, tämä funktio luo arvon välillä 0 - 18446744073709551615 (= 264 - 1).
Tämä esimerkki osoittaa, että Pearsonin algoritmia voidaan käyttää minkä tahansa pituisten tiivisteiden luomiseen yhdistämällä 8-bittisten hajautusarvojen sarja, joista jokainen lasketaan yksinkertaisesti muuttamalla merkkijonoa hieman joka kerta, kun hash-funktio lasketaan. Joten samaa peruslogiikkaa voidaan soveltaa 32- tai 128-bittisten hajautusten luomiseen.