М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко "КРИПТОГРАФИЯ В БАНКОВСКОМ ДЕЛЕ"

Геовикипедия
wiki.web.ru

Поиск

Главная страница

Конференции: Календарь / Материалы

Каталог ссылок

Словарь

Форумы

В помощь студенту

Последние поступления

Геология | Курсы лекций

Обсудить в форуме

Добавить новое сообщение

Вперед: 5.2.2 MD4 Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2 Методы построения криптографических хэш-функций Содержание Предметный указатель

5.2.1 -хэш

Алгоритм разработан фирмой Nippon Telephone & Telegraph. Впервые опубликован в 1990 году [MOI1], [MOI2].

-хэш использует блоки длиной 128 битов, размешивающую функцию, аналогичную функции алгоритма шифрования FEAL и вырабатывает блок хэш-кода длиной 128 битов. На вход пошаговой хэш-функции в качестве аргументов поступают очередной блок сообщения длиной 128 битов и хэш-код $h_{i-1}$ предыдущего шага также размером 128 битов. , где -- синхропосылка;

$h_i=g(M_i,h_{i-1})\oplus M_i\oplus h_{i-1}$ . Хэш-кодом всего сообщения объявляется хэш-код, получаемый в результате преобразования последнего блока текста.

Функция вначале меняет местами старшие и младшие части (по 64 бита каждая) хэш-кода предыдущего шага, покоординатно складывает полученное значение с величиной $1010\ldots1010$ (длина 128 битов) и текущим блоком текста . Полученная величина поступает на вход каскада из () преобразующих функций. Вторым аргументом каждой из преобразующих функций является хэш-код предыдущего шага, сложенный покоординатно с одной из восьми констант.

На рисунке 1 использованы следующие условные обозначения: EXG -- старшая и младшая части (по 64 бита каждая) входного блока меняются местами;

$V=1010\ldots1010$ (128 битов) в двоичной записи;

$V_j = \delta\mathbin\Vert A_{j1}\mathbin\Vert\delta\mathbin\Vert A_{j2}\mathbin\Vert\delta\mathbin\Vert A_{j3}\mathbin\Vert\delta\mathbin\Vert A_{j4}$ ; здесь $\mathbin\Vert$ обозначает конкатенацию бинарных строк;

$\delta=00\ldots00$ (24 бита) в двоичной записи;

$A_{jk}=4\times(j-1)+k$ (; $A_{jk}$ длиной 8 битов);

PS -- преобразующая функция.

Рис. 1

$\begin{figure}\unitlength 1.00mm \linethickness{0.4pt}\centerline{\begin{picture... ...} % end \put(96.43,2.49){\makebox(0,0)[cc]{$\oplus$}} \end{picture}}\end{figure}$

На рисунке 2 представлена схема преобразующей функции. Каждый из аргументов при этом разбивается на 4 блока по 32 бита каждый: $X=X_1\mathbin\Vert X_2\mathbin\Vert X_3\mathbin\Vert X_4$ , $P=P_1\mathbin\Vert P_2\mathbin\Vert P_3\mathbin\Vert P_4$ .

Рис. 2

$\begin{figure}\unitlength 0.80mm \linethickness{0.4pt}\centerline{\begin{picture... ...us$}} \put(147.59,70.66){\makebox(0,0)[cc]{$\oplus$}} \end{picture}}\end{figure}$

Схема вычисления функции представлена на рисунке 3.

Рис. 3

$\begin{figure}\unitlength 0.80mm \linethickness{0.4pt}\centerline{\begin{picture... ...lus$}} \put(39.33,79.67){\makebox(0,0)[cc]{$\oplus$}} \end{picture}}\end{figure}$

Функции и определяются аналогично таким же функциям криптографического алгоритма FEAL: левый циклический сдвиг на 2 бита $)\ ((a+b)\bmod256)$ ;

левый циклический сдвиг на 2 бита $)\ ((a+b+1)\bmod256)$ .

Результат действия преобразующей функции PS предыдущего шага становится входным аргументом очередной преобразующей функции PS. Процесс, показанный на рис. 1, завершается покоординатным суммированием по модулю 2 результата действия последней преобразующей функции PS, хэш-кода предыдущего шага и блока хэшируемого текста.

Известные результаты анализа

Ден Бур предложил способ построения коллизии для однораундовой схемы -хэша. Бихам и Шамир успешно применили дифференциальный метод [BiS2] для компрометации 6-раундовой схемы -хэша [BiS1], [Bi]. Более того, предложенный ими способ построения коллизий срабатывает для любого значения кратного трем и при этом для $N\leqslant12$ он оказывается эффективнее подхода основанного на "парадоксе дня рождения" (см. раздел 5.4). Для 6-раундовой схемы Бихам и Шамир указали явно несколько пар текстов, имеющих один и тот же хэш-код. Для 12-раундовой схемы сложность построения коллизий предложенным методом оценивается величиной $2^{56}$ операций (для сравнения: трудоемкость метода основанного на "парадоксе дня рождения" есть $2^{64}$ операций).

Михаил Анохин

Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ