Pirson heširanje

Pirson heširanje je heš funkcija dizajnirana za brzo izvršavanje na procesorima sa 8-bitnim registrima. S obzirom da se ulaz sastoji od određenog broja bitova, kao izlaz se proizvodi jedan bajt koji strogo zavisi od svakog bita ulaza. Njegova implementacija zahteva samo nekoliko instrukcija, plus dodatnih 256 bajta za adresnu tabelu koja sadrži permutacije vrednosti od 0 do 255.

Ova heš funkcija je CBC-MAC koja koristi 8-bitni nasumični blok cifara koji je implementiran pomoću tabele permutacija. 8-bitni blok cifara ima zanemarljivu kriptografsku sigurnost, pa Pirson heš funkcija nije kriptografski jaka, ali nudi sledeće pogodnosti:

• Veoma je jednostavna
• Izvršava se veoma brzo na procesorima sa ograničenim resursima
• Ne postoji određena klasa ulaza za koju će kolizije imati veću verovatnoću pojavljivanja
• Uzevši u obzir mali, privilegovani set ulaza (npr. ključne reči koje koristi kompajler), tabela permutacija može biti prilagođena da ulazi daju jasne heš vrednosti, proizvodeći ono što se zove savršena heš funkcija.

Jedan od njegovih nedostataka u poređenju sa drugim algoritmima za heširanje dizajniranih za 8-bitne procesore je predložena 256-bajtna adresna tabela, koja može biti izuzetno velika za mali mikrokontroler sa programskom memorijom veličine nekoliko stotina bajtova. Zaobilaženje ove tabele je korišćenje jednostavne funkcije permutacija umesto tabele smeštene u memoriji. Međutim, korišćenje isuviše jednostavne funkcije, kao što je T[i] = 255-i delimično umanjuje upotrebljivost same heš funkcije zato što će anagrami rezultovati istom heš vrednošću; koristeći isuviše kompleksnu funkciju, sa druge strane, uticaće negativno na brzinu.

Algoritam se može opisati u sledećem pseudokodu, koji računa heš poruku C korišćenjem tabele permutacija T:

h := 0
for each c in C loop
  index := h xor c
  h := T[index]
end loop
return h

Implementacija za generisanje 64-bitnih (16 heksadekadnih bajtova) heš funkcija u jeziku Ce

   unsigned char xPear16(unsigned char *x, int len) {
      int h, i, j;
      unsigned char ch, hex[20]="";

      struct { // to store h values
         int a;
      } hh[8];
      struct { // 256 values 0-255 in any (random) order suffices
         int a;
      } T[256] = {
       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
      };

      ch=x[0]; // save first byte
      for (j=0; j<8; j++) {
         // standard Pearson hash (output is h)
         h=0;
         for (i=0; i<len; i++) {
            h=T[h ^ x[i]].a;
         }
         hh[j].a=h; // store result
         x[0]=x[0]+1; // increment first data byte by 1
      }
      x[0]=ch; // restore first byte
      // concatenate the 8 stored values of h
      wsprintf(hex,"%02X%02X%02X%02X%02X%02X%02X%02X",
         hh[0].a, hh[1].a,
         hh[2].a, hh[3].a,
         hh[4].a, hh[5].a,
         hh[6].a, hh[7].a);
      return hex; // output 64-bit 16 hex bytes hash
   }

Za datu nisku ili deo podataka, Pirsonov originalni algoritam proizvodi samo 8-bitni bajt ili celobrojnu vrednost, 0-255. Ali algoritam omogućava veoma lako generisanje, heš tabele proizvoljne dužine. Shema koja je korišćena iznad je veoma jednostavna implementacija algoritma. Kao što je Pirson primetio: promena bilo kog bita u niski izaziva da algoritam kreira kompletno nov drugačiji heš (0-255). U kodu iznad, nakon svakog završetka unutrašnje petlje, prvi bajt niske se inkrementira za jedan x[0]=x[0]+1

Svaki put kada je tako jednostavna promena na prvom bajtu napravljena, različita Pirsonova heš funkcija h, je generisana. hPearl16 gradi 16 heksadekadnih bajtova heš tabele tako što nadovezuje serije 8-bitnih Pirsonovih heš funkcija. Umesto da proizvode vrednost od 0 do 255, on generiše vrednost od 0 do 18.446.744,073,709,551,615.

Pirsonov algoritam može biti napravljen za generisanje heš tabela proizvoljne dužine, jednostavnim dodavanjem jedinice na prvi bajt niske, ponovnim izračunavanjem heš funkcije h za nisku i nadovezivanjem rezultata. Isto takva logika može se iskoristiti za pravljenje 32-bitnih ili 128-bitnih heš funkcija.