Интернет магазин китайских планшетных компьютеров

Компьютеры - MD2

MD2 — хэш-функция, разработанная Рональдом Ривестом в 1989 году, и описанная в RFC 1319. Размер хэша — 128 бит. Размер блока входных данных — 512 бит.

Алгоритм MD2

Предполагается, что на вход подано сообщение, состоящее из байт, хеш которого нам предстоит вычислить. Здесь — произвольное неотрицательное целое число; оно может быть нулем или сколь угодно большим. Запишем сообщение побайтово, в виде:

Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.

Шаг 1. Добавление недостающих бит.

Сообщение расширяется так, чтобы его длина в байтах по модулю 16 равнялась 0. Таким образом, в результате расширения длина сообщения становится кратной 16 байтам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.

Расширение производится следующим образом: i байт, равных i, добавляется к сообщению, так чтобы его длина в байтах стала равной 0 по модулю 16. В итоге, к сообщению добавляется как минимум 1 байт, и как максимум 16.

На этом этапе сообщение имеет длину в точности кратную 16 байтам. Пусть означает байты получившегося сообщения.

Шаг 2. Добавление контрольной суммы.

16-байтная контрольная сумма сообщения добавляется к результату предыдущего шага.

Этот шаг использует 256-байтную «случайную» перестановочную матрицу, состоящую из цифр числа пи:

  PI_SUBST = {
  41,  46,  67, 201, 162, 216, 124,   1,  61,  54,  84, 161, 236, 240,   6,  19,
  98, 167,   5, 243, 192, 199, 115, 140, 152, 147,  43, 217, 188,  76, 130, 202,
  30, 155,  87,  60, 253, 212, 224,  22, 103,  66, 111,  24, 138,  23, 229,  18,
 190,  78, 196, 214, 218, 158, 222,  73, 160, 251, 245, 142, 187,  47, 238, 122,
 169, 104, 121, 145,  21, 178,   7,  63, 148, 194,  16, 137,  11,  34,  95,  33,
 128, 127,  93, 154,  90, 144,  50,  39,  53,  62, 204, 231, 191, 247, 151,   3,
 255,  25,  48, 179,  72, 165, 181, 209, 215,  94, 146,  42, 172,  86, 170, 198,
  79, 184,  56, 210, 150, 164, 125, 182, 118, 252, 107, 226, 156, 116,   4, 241,
  69, 157, 112,  89, 100, 113, 135,  32, 134,  91, 207, 101, 230,  45, 168,   2,
  27,  96,  37, 173, 174, 176, 185, 246,  28,  70,  97, 105,  52,  64, 126,  15,
  85,  71, 163,  35, 221,  81, 175,  58, 195,  92, 249, 206, 186, 197, 234,  38,
  44,  83,  13, 110, 133,  40, 132,   9, 211, 223, 205, 244,  65, 129,  77,  82,
 106, 220,  55, 200, 108, 193, 171, 250,  36, 225, 123,   8,  12, 189, 177,  74,
 120, 136, 149, 139, 227,  99, 232, 109, 233, 203, 213, 254,  59,   0,  29,  57,
 242, 239, 183,  14, 102,  88, 208, 228, 166, 119, 114, 248, 235, 117,  75,  10,
  49,  68,  80, 180, 143, 237,  31,  26, 219, 153, 141,  51, 159,  17, 131,  20};

Пусть S означает i-ый элемент этой таблицы. Она будет приведена ниже. Контрольная сумма вычисляется следующим образом:

      /* Clear checksum. */
      For i = 0 to 15 do:
         Set C to 0.
      end /* of loop on i */
 
      Set L to 0.
 
      /* Process each 16-word block. */
      For i = 0 to N/16-1 do
 
         /* Checksum block i. */
         For j = 0 to 15 do
            Set c to M.
            Set C to C xor S.
            Set L to C.
          end /* of loop on j */
       end /* of loop on i */

16-байтная контрольная сумма добавляется к сообщению. Теперь сообщение можно записать в виде , где N1 = N + 16.

Шаг 3. Инициализация MD-буфера.

48-байтный буфер X используется для вычисления хеша. Он инициализируется нулями.

Шаг 4. Обработка сообщения блоками по 16 байт.

На этом шаге используется та же 256-байтная перестановочная матрица S, как и на шаге 2.

Производим следующие операции:

 
     /* Process each 16-word block. */
      For i = 0 to N1/16-1 do
 
         /* Copy block i into X. */
         For j = 0 to 15 do
            Set X to M.
            Set X to .
          end /* of loop on j */
 
         Set t to 0.
 
         /* Do 18 rounds. */
         For j = 0 to 17 do
 
            /* Round j. */
            For k = 0 to 47 do
               Set t and X to .
            end /* of loop on k */
 
            Set t to  modulo 256.
         end /* of loop on j */
 
      end /* of loop on i */

Шаг 5. Формирование хеша.

Хеш вычисляется как результат ; в начале идет байт X, а конце X.

На этом завершается описание алгоритма MD2. В RFC 1319 можно найти реализацию алгоритма на языке C.