Пирсон хеширање

Пирсон хеширање^[1]^[2] је хеш функција дизајнирана за брзо извршавање на процесорима са 8-битним регистрима. С обзиром да се улаз састоји од одређеног броја битова, као излаз се производи један бајт који строго зависи^[1] од сваког бита улаза. Његова имплементација захтева само неколико инструкција, плус додатних 256 бајта за адресну табелу која садржи пермутације вредности од 0 до 255.

Ова хеш функција је ЦБЦ-МАЦ која користи 8-битни насумични блок цифара који је имплементиран помоћу табеле пермутација. 8-битни блок цифара има занемарљиву криптографску сигурност, па Пирсон хеш функција није криптографски јака, али нуди следеће погодности:

Веома је једноставна
Извршава се веома брзо на процесорима са ограниченим ресурсима
Не постоји одређена класа улаза за коју ће колизије имати већу вероватноћу појављивања
Узевши у обзир мали, привилеговани сет улаза (нпр. кључне речи које користи компајлер), табела пермутација може бити прилагођена да улази дају јасне хеш вредности, производећи оно што се зове савршена хеш функција.

Један од његових недостатака у поређењу са другим алгоритмима за хеширање дизајнираних за 8-битне процесоре је предложена 256-бајтна адресна табела, која може бити изузетно велика за мали микроконтролер са програмском меморијом величине неколико стотина бајтова. Заобилажење ове табеле је коришћење једноставне функције пермутација уместо табеле смештене у меморији. Међутим, коришћење исувише једноставне функције, као што је T[i] = 255-i делимично умањује употребљивост саме хеш функције зато што ће анаграми резултовати истом хеш вредношћу; користећи исувише комплексну функцију, са друге стране, утицаће негативно на брзину.

Алгоритам се може описати у следећем псеудокоду, који рачуна хеш поруку Ц коришћењем табеле пермутација Т:

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

Имплементација за генерисање 64-битних (16 hексадекадних бајтова) хеш функција у језику Це

   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
   }

За дату ниску или део података, Пирсонов оригинални алгоритам производи само 8-битни бајт или целобројну вредност, 0-255. Али алгоритам омогућава веома лако генерисање, хеш табеле произвољне дужине. Схема која је коришћена изнад је веома једноставна имплементација алгоритма. Као што је Пирсон приметио: промена било ког бита у ниски изазива да алгоритам креира комплетно нов другачији хеш (0-255). У коду изнад, након сваког завршетка унутрашње петље, први бајт ниске се инкрементира за један x[0]=x[0]+1

Сваки пут када је тако једноставна промена на првом бајту направљена, различита Пирсонова хеш функција х, је генерисана. хПеарл16 гради 16 хексадекадних бајтова хеш табеле тако што надовезује серије 8-битних Пирсонових хеш функција. Уместо да производе вредност од 0 до 255, он генерише вредност од 0 до 18.446.744,073,709,551,615.

Пирсонов алгоритам може бити направљен за генерисање хеш табела произвољне дужине, једноставним додавањем јединице на први бајт ниске, поновним израчунавањем хеш функције х за ниску и надовезивањем резултата. Исто таква логика може се искористити за прављење 32-битних или 128-битних хеш функција.

Референце

^ ^а ^б Pearson, Peter K. (Јун 1990), „Fast Hashing of Variable-Length Text Strings”, Communications of the ACM, 33 (6): 677, doi:10.1145/78973.78978 Проверите вредност парамет(а)ра за датум: |date= (помоћ)
^ Online PDF file of the CACM paper Архивирано на сајту Wayback Machine (4. јул 2012).

[acmref-1] а ^б Pearson, Peter K. (Јун 1990), „Fast Hashing of Variable-Length Text Strings”, Communications of the ACM, 33 (6): 677, doi:10.1145/78973.78978 Проверите вредност парамет(а)ра за датум: |date= (помоћ)

[2] Online PDF file of the CACM paper Архивирано на сајту Wayback Machine (4. јул 2012).

[1]

[2]