31009-1 (Цифровая подпись), страница 2

m0 m1 m2 . . . . . . m{b-1}

Следующие пять этапов выполняются для подсчета Message Digest сообщения.

Этап 1. Присоединение заполняющих (дополнительных) битов.

Сообщение расширяется так, чтобы его длина (в битах) совпадала с 448, по модулю 512. Дополнение всегда выполняется, даже если длина сообщения - уже совпадает с 448 по модулю 512. Дополнение выполняется следующим образом: одиночный "1" бит добавляется к сообщению, и далее "0" биты добавляются так что длина в битах заполняемого сообщения соответствует 448 по модулю 512. В общем случае, минимум один бит и максимум 512 бит добавляется.

Этап 2. Добавление длины

64-битное представление входной последовательности b (длина сообщения перед расширением дополнительными битами) присоединяется к результату предыдущего этапа. Маловероятно, что длина b будет больше, чем 2⁶⁴ поэтому и используется 64-х разрядная величина для хранения длины b. (Эти биты добавляются как два 32-х разрядных слова, младшее заносится первым).

В этом месте окончательное сообщение(после выполнения первого и второго этапов) имеет длину, кратную 512 битам, т. е. сообщение имеет длину, которая точно кратна 16-ти словам. Последовательность М[0 . . . . N-1] является словами окончательного сообщения, где N кратно 16.

Этап 3. Инициализация MD буфера.

Буфер на 4-е слова (A, B, C, D) используется для подсчета Message Digest. Каждое из A, B, C, D является 32-х битным регистром. Эти регистры инициализируются следующими шестнадцатиричными значениями, где первым следует самый младший байт:

word A: 01 23 45 67

word B: 89 ab cd ef

word C: fe dc ba 98

word D: 76 54 32 10

Программисты из RSA Data Security, Inc. , дабы не утруждать себя и остальных людей по поводу происхождения этих чисел, просто назвали их магическими константами.

Этап 4. Обработка сообщения в блоках по 16 слов.

Сначала определяются четыре вспомагательных функции каждая из которых имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.

F(X, Y, Z) = XY v not(X) Z

G(X, Y, Z) = XZ v Y not(Z)

H(X, Y, Z) = X xor Y xor Z

I(X, Y, Z) = Y xor (X v not(Z))

В каждой битовой позиции функция F действует как условный опреатор : если X то Y иначе Z. Функция F могла бы определяться с использованием операцию + вместо v, так как выражение XY and not(X)Z никогда не будет иметь 1 в одинаковых битовых позициях.

Если биты X, Y и Z независимы и несмещены(??), то каждый бит после выполнения F(X, Y, Z) будет независим и несмещен.

Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для нахождения выходного значения от входных битов X, Y и Z, тем же способом, что если биты X, Y и Z независимы и несмещены, то каждый бит после выполнения вышеуказанных функций будет независим и несмещен. Обратите внимание, что функция H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е. функцией контроля четности входных значений). Далее на этом этапе происходит четыре цикла, в которых происходит трансформация битов сообщения при помощи вышеуказанных

функций, функций циклического сдвига, и таблицы константных значений.

Этап 5. Вывод

В результате выполнения предыдущих этапов Message Digest производит на выходе числа A, B, C, D, общая длина которых 128 бит.

Резюме

Алгоритм получает на входе сообщение произвольной длины и после обработки на выходе получаем 128-битный "отпечаток" или "Message Digest". Предполагается, что вычислительная трудоемкость нахождения двух сообщений, имеющих одинаковые Message Digest очень велика. MD5 алгоритм предназначен для приложений, формирующих цифровые сигнатуры, в которых большой файл должен быть "сжат" безопасным способом перед зашифровкой открытым (или секретным)ключом в некоторой криптосистеме с открытым ключом, такой как RSA.

MD5 алгоритм является расширением алгоритма MD4.

MD5 алгоритм полностью разработан для быстрой работы на 32-х разрядных машинах. К тому же алгоритм не требует каких-либо больших подстановочных таблиц; обеспечивается компактная кодировка.

MD5 Message Digest алгоритм прост в использовании, и обеспечивает получение 128-ми битного "отпечатка" или Message Digest сообщения произвольной длины.

Предполагается, что сложность нахождения двух сообщений, которые произведут одинаковые Message Digest является порядка 2 в 64 степени операций, и сложность построения сообщения по некоторому известному Message Digest является порядка 2 в 128 степени операций.

Примеры исходного кода для реализации MD5.

Макросы

F, G, H, I

Данные макросы определяют четыре вспомогательных функции, каждая из которых имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.

#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))

#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))

#define H(x, y, z) ((x) ^ (y) ^ (z))

#define I(x, y, z) ((y) ^ ((x) | (~z)))

В каждой битовой позиции функция F действует как условный оператор : если X то Y иначе Z. Если биты X, Y и Z независимы и несмещены (??), то каждый бит после выполнения F(X, Y, Z) будет независим и несмещен.

Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для нахождения выходного значения от входных битов X, Y и Z, тем же способом, что если

биты X, Y и Z независимы и несмещены, то каждый бит после выполнения вышеуказанных функций будет независим и несмещен. Следует обратить внимание, что функция H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е. функцией контроля четности входных значений).

FF, GG, HH, II

Данные макросы определяют четыре вспомагательных функции, которые на входе получают семь 32-х разрядных параметров, а на выходе получаем одну 32-х разрядную величину.

Эти фунции используются в функции Transform() для битовых преобразований.

Функции работают следующим образом:

1. В выходной параметр записывается сумма соответствующей функции (для FF() это F(), для GG() это G(), для HH() это H(), для II() это I()) от 2-го, 3-го и 4-го параметров с 5-м и 7-м параметрами.

2. Производится циклический сдвиг влево выходного параметра на количество бит, указанное в 6-м входном параметре.

3. Производится приращение выходного параметра на величину, указанную во 2-м входном параметре.

#define FF(a, b, c, d, x, s, ac) /

{(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); /

(a) = ROTATE_LEFT ((a), (s)); /

(a) += (b); /

}

#define GG(a, b, c, d, x, s, ac) /

{(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); /

(a) = ROTATE_LEFT ((a), (s)); /

(a) += (b); /

}

#define HH(a, b, c, d, x, s, ac) /

{(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); /

(a) = ROTATE_LEFT ((a), (s)); /

(a) += (b); /

}

#define II(a, b, c, d, x, s, ac) /

{(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); /

(a) = ROTATE_LEFT ((a), (s)); /

(a) += (b); /

}

Сразу можно отметить, что входные параметры вышеуказанных функций представляют собой следующие значения:

register UINT4 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; Как видно регистровые переменные a, b, c, d типа UINT4 инициализируются значениями временного буфера buf[4] содержащемся в основной структуре Message Digest MD5_CTX. Пятый параметр x всегда инициализируется символом из входного буфера in[64] также находящемся в структуре MD5_CTX.

Параметр s равен одной из шестнадцати констант, определенных в функции Transform().

А вот самый последний параметр ас равен одной из 64-х "таинственных констант". Разработчики из RSA Data Security, Inc. предлагают вам расположить эти константы в "little-endian" порядке, расшифровать при помощи DES и вы получите ТАЙНЫЕ ПОСЛАНИЯ. (вот только DESовый ключик они не указали).

ROTATE_LEFT

Данный макрос сдвигает x влево на n бит.

#define ROTATE_LEFT(x, n) (((x) <> (32-(n))))

Если n > 32, то результат равен нулю.

Функции

void MD5Init ( MD5_CTX *mdContext)

Функция MD5Init(MD5_CTX *mdContext) выполняет инициализацию некоторых полей структуры Message Digest MD5_CTX В качестве параметра функция получает указатель на структуру MD5_CTX.

{

/* Обнуление полей, которые будут содержать длину сообщения */

mdContext->i[0] = mdContext->i[1] = (UINT4)0;

/* Загрузка магических констант инициализации. */

mdContext->buf[0] = (UINT4)0x67452301L;

mdContext->buf[1] = (UINT4)0xefcdab89L;

mdContext->buf[2] = (UINT4)0x98badcfeL;

mdContext->buf[3] = (UINT4)0x10325476L;

}

void MD5Update (register MD5_CTX *mdContext, unsigned char *inBuf, unsigned int inLen)

Данная функция обрабатывает содержимое структуры MD5_CTX.

В качестве параметров функция получает:

Указатель mdContext на структуру MD5_CTX;

Cимвольный буфер inBuf[], который содержит символы исходного сообщения, чей Message Digest мы подсчитываем; Длину inLen передаваемого буфера.

Вначале подсчитывается целочисленная величина mdi:

mdi = (int)((mdContext->i[0] >> 3) & 0x3F);

Эта величина равна длине сообщения в байтах по модулю 64. Длина сообщения в битах хранится в структуре MD5_CTX в буфере i[0. . 1].

Длина сообщения в битах заносится в буфер i[0. . 1] следующим образом:

mdContext->i[0] += ((UINT4)inLen << 3);

mdContext->i[1] += ((UINT4)inLen >> 29);

Следующий участок кода выполняет следующие действия:

while (inLen--)

{

/* добавляем новый символ в буфер, инкрементируя mdi */

mdContext->in[mdi++] = *inBuf++;

/* Если необходимо выполняем преобразование */

if (mdi == 0x40)

{

for (i = 0, ii = 0; i < 16; i++, ii += 4)

in[i] = (((UINT4)mdContext->in[ii+3]) << 24) |

(((UINT4)mdContext->in[ii+2]) << 16) |

(((UINT4)mdContext->in[ii+1]) << 8) |

((UINT4)mdContext->in[ii]);

Transform (mdContext->buf, in);

mdi = 0;

}

}

Пока уменьшаемая на 1 длина переданного в функцию сообщения не станет равной нулю выполняем следующие действия:

Заносим новый символ из входного буфера функции в 64-х байтный буфер структуры MD5_CTX, увеличивая при этом переменную mdi на 1. Если mdi равна 64, то преобразуем

однобайтные символы буфера in[] структуры MD5_CTX в 4-х байтные величины типа UINT4, заносим в промежуточный буфер на 16 величин типа UINT4, и далее передаем функции Transform(). Присваиваем переменной mdi 0.

void MD5Final (MD5_CTX *mdContext)

Функция завершает вычисление Message Digest и заносит полученное значение в структуре MD5_CTX в символьный буфер digest[0. . . 15].

Входным параметром функции является указатель на структуру MD5_CTX.

Основные моменты:

Расширение сообщения дополнительными заполняющими символами из таблицы PADDING[]

/* Подсчет длины сообщения в байтах по модулю 64 */

mdi = (int)((mdContext->i[0] >> 3) & 0x3F);

/* Расширить до 56 по модулю 64 */

padLen = (mdi < 56) ? (56 - mdi) : (120 - mdi);

MD5Update(mdContext, PADDING, padLen);

Присоединение битов длины и вызов функции Transform().

in[14] = mdContext->i[0];

in[15] = mdContext->i[1];

for (i = 0, ii = 0; i < 14; i++, ii += 4)

in[i] = (((UINT4)mdContext->in[ii+3]) << 24) |

(((UINT4)mdContext->in[ii+2]) << 16) |

(((UINT4)mdContext->in[ii+1]) << 8) |

((UINT4)mdContext->in[ii]);

Transform (mdContext->buf, in);

Сохранение буфера в digest(т. е. получение окончательного Message Digest):

for (i = 0, ii = 0; i < 4; i++, ii += 4)

{

mdContext->digest[ii] = (unsigned char)(mdContext->buf[i] & 0xFF);

mdContext->digest[ii+1] = (unsigned char)((mdContext->buf[i] >> 8) & 0xFF);

mdContext->digest[ii+2] = (unsigned char)((mdContext->buf[i] >> 16) & 0xFF);

mdContext->digest[ii+3] = (unsigned char)((mdContext->buf[i] >> 24) & 0xFF);

}

void Transform(register UINT4 *buf, register UINT4 *in)

Данная функция является основным шагом в алгоритме MD5.

Входными параметрами являются указатель на буфер buf[] из структуры MD5_CTX и указатель на буфер in[], хранящем значения типа UINT4. Функция выполняет 4 цикла по 16 шагов в каждом. В каждом цикле используется одна из функций FF, GG, HH, II. Далее окончательный результат после 64-х преобразовательных итераций добавляется к содержимому буфера buf[].

Структура MD5_CTX

Структура MD5_CTX является основной структурой для формирования MessageDigest. Структура содержит следующие поля:

typedef struct

{

UINT4 i[2]; /* количество бит в сообщении по mod 2^64 */

UINT4 buf[4]; /* временный буфер */

unsigned char in[64]; /* входной буфер */

unsigned char digest[16]; /* содержит действительный Message Digest

после вызова MD5Final() */

} MD5_CTX;

Цифровая подпись и криптосистемы с ключом общего пользования.

Если использовать алгоритмы хэширования вместе с криптосистемами с ключом общего пользования, то можно создать цифровую подпись, гарантирующую подлинность полученного набора данных, аналогично тому, как рукописная подпись, подтверждает аутентичность напечатанного документа. Криптосистема с ключом общего пользования - это метод, позволяющий осуществлять кодирование и декодирование информации, с помощью двух исходных ключей: ключа общего пользования, свободно передаваемого всем желающим, и личного ключа, известного только его владельцу.

Смысл ключа и пароля примерно одинаков. Допустим, Том желает, чтобы Сэм мог отправить ему зашифрованный документ, и оба они не хотели бы рисковать, передавая пароль или ключ по линиям связи, так как в этом случае он может быть кем-то перехвачен. Тогда Том может передать Сэму свой ключ общего пользования (схема 1).

Используя этот ключ, Сэм шифрует документ и отправляет его Тому. Том дешифрует документ с помощью своего личного ключа. Это единственный ключ, с помощью которого можно восстановить документ, зашифрованный с применением ключа общего пользования, принадлежащего Тому. Тот факт, что ключ общего пользования Тома может стать кому-то известен, не имеет особого значения, потому что он абсолютно бесполезен для расшифровки документа. А личный ключ, известный одному лишь Тому, по открытым линиям связи не передавался; теоретически том хранит его только в собственной памяти и наоборот, работа других криптосистем с ключом общего пользования строится на обратном принципе: Сэм шифрует документ с помощью своего личного ключа и передает свой ключ общего пользования Тому, с помощью которого тот мог бы расшифровать этот документ. Существующие ныне криптосистемы с ключом общего пользования, такие, например, как система RSA (сокращение, составленное из первых букв фамилий трех создателей этого алгоритма), широко используются.

Как же осуществляется цифровая подпись? Рассмотрим еще один пример. Допустим, Сэм собирается отправить Тому контракт или номер своей кредитной карточки в цифровом виде. Для подтверждения подлинности этих документов Тому необходима цифровая подпись Сема. Сначала Сэм отправляет свой документ. Затем использует алгоритм хэширования для вычисления идентификатора этого документа, шифрует хэшированное значение с помощью своего личного ключа и отправляет его Тому. Это и есть цифровая подпись Сэма. Том с помощью того же алгоритма хэширования сначала вычисляет идентификатор принятого документа. Затем он расшифровывает значение, которое получил от Сэма, используя предоставленный Сэмом ключ общего пользования. Если два значения хэширования совпали, Том не только узнает, что этот документ подлинный, но и то, что подпись Сэма действительна. Понятно, что проведение коммерческих транзакций по такому сценарию значительно безопаснее, чем с использованием подписи от руки на бумаге, которую можно подделать. А если сведения, передаваемые Сэмом Тому, конфиденциальны (например, содержат номер кредитной карточки), то и их можно зашифровать так, чтобы прочитать их смог только Том.