48

с ∆ = 5/8.

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

Поясним это на примере. Для этого рассмотрим схему 3-раундового

DES.

PL P PR

Kr(1)

Y(1) Х(1)f(1)

Kr(2)

Y(2) Х(2)f(2)

Kr(3)

			Y(3)				Х(3)
				f(3)
	С L						С R

Рис. 1. Схема 3-х раундов DES.

Эффективными линейными статистическими аналогами 1-ой и 3-ей итераций являются уравнения

Y (1)[2,8,14,24] X (1)[17] = K (1)[26],

Y (3)[2,8,14,24] X (3)[17] = K (3)[26],

каждое из которых выполняется с вероятностью 316 .

	Учитывая,	что	X (1) = PR , X (3) = СL , Y (1) = PL X (2),
Yr	(3) = СR Xr	(2),	после сложения этих уравнений получим

49

( PR СL )[17] ( PL СR )[2,8,14,24] = ( K (1) K (3))[26].

(12)

По лемме 1 ∆ =

5

5

=

25

и это уравнение выполняется с вероятностью

8

64

1− ∆

8

р =

=

39

.

128

2

Найти биты ключа K (1) K (3) можно, решая уравнение (12) с ис-

пользованием следующего алгоритма.

Алгоритм.

Пусть N-число всех открытых текстов и Т-число откры-

тых текстов, для которых левая часть (11) равна 0.

Если Т > N/2, то

Kr (1) Kr

(3) = 0, p > 1/ 2.

1, p < 1/ 2

Если Т < N/2, то

1, p > 1/ 2

K (1) K (3) =

.

0, p < 1/ 2

Успех алгоритма возрастает с ростом N и ∆ =|1 − 2 p |. Вероятность ус-

пеха определяется следующей леммой.

Лемма 2. Пусть N –число открытых текстов и р - вероятность выполнения линейного уравнения (2). Предположим, что ∆ =|1 − 2 p | →0 . Тогда

вероятность успеха алгоритма имеет вид

	∞
P →	∫ϕ(x)dx ,
−	N ∆
где					x2
	1			e−
ϕ(x) =					2	.				(13)
	2π
Числовые вычисления (13) сведены в таблице 3.
N			1				1	1	1	∆2
				16∆2			8∆2	4∆2	2
Русп		0,841					0,921	0,977	0,998

Таблица 3.

50

2.10. Дифференциальный криптоанализ.

Пусть некоторый блочный шифратор с длиной блока N строится по схеме.

Y(1) = X(2)

Y(2)

X(r)

Х(1)

f

f

Y(r),

f

Z(1)

Z(2)

Z(r )

Рис. 1

где

=

(Z(1),

Z(2),…,Z(r)) получается

по некоторой схеме из Z 0 , или

Z

независимо и равновероятно выбирается для каждого цикла. Пусть Х(1) и

Х* (1) – пара открытых текстов. Рассмотрим следующие разности:

∆Х(1) = Х(1) - Х* (1),

∆Y(i) = Y(i) - Y* (i).

Если мы знаем открытый и шифрованный текст в одном i-ом цикле DES, то несложно определить часть ключа Z(i), которая используется в i-ом цикле (идея Шеннона о суперпозиции простых шифров для получения

сложного шифра). Но, если мы знаем ∆ Х(i), Y(i) и Y* (i), то задача становится более сложной, но также решается, если решается предыдущая задача.

Определение 1. Преобразование f называется криптографически слабым, если по ∆ Y(r-1), Y(r) и Y* (r) для некоторого (малого) числа пар (Х(1), Х* (1)) можно найти (хотя бы часть) Z(r).

Идея дифференциального криптоанализа [Biham 93] заключается в том, чтобы найти такие ∆ Х(1), что при случайном равновероятном выборе

	Х(1), Z(1),	Z(2),…Z(r-1) с	вероятностью		более	1
						2N
	∆ Y(r-1).
	Определение 2. Пара		(α,	β) возможных значений
	(∆ Х(1), ∆ Y(i)) называется дифференциалом i-ого цикла.
	Тогда	дифференциальный		криптоанализ	описывается
	моделью.

появится

вектора

следующей

51

Y(1) = X(2)

Y(2)

X(r)

Х(1)

f

f

f

Y(r),

Z(1)

Z(2)

Z(r )

Y* (1) = X* (2)

Y* (2)

X* (r)

Х* (1)

f

f

Y* (r).

f

Рис. 2

Пусть f определяет операции в ∆ и f криптографически слаба. Тогда возможна следующая атака.

1.	Выбираем дифференциал (r-1) – го цикла (α, β), для которого
вероятность Р(∆ Y(r-1) = β ∆ Х(1) = α) большая.
2.	Случайно выбираем Х(1) и подбираем Х* (1), чтобы
∆ Х(1) = α.	Пусть известны Y(r) и Y* (r).
3.	Делаем предположение, что ∆ Y(r-1) = β и, зная Y(r) и Y* (r),
находим Z(r ).
4.	Повторяем 2 и 3 пока один (частичный) ключ не начнет
появляться чаще других. Это и будет Z(r ).
5.	Повторяем 1-4 до нахождения полного ключа.

2.11. Метод коллизий для хэш-функций.

Для контроля целостности сообщений, передаваемых по каналу связи, используется следующий метод. Пусть А = {a1,...,a m } - алфавит, А* - множество слов конечной длины в алфавите А. Пусть определена функция

Н: А* → Аl , которая обладает тем свойством, что значения функции Н на словах, которые даже при отличии друг от друга только в одном знаке дают значительно отличающиеся хэш значения. Тогда, получив на приемном конце сообщение и его хэш, можно вычислить значение хэш от сообщения, сравнить с полученным хэш по каналу связи, и подтвердить или опровергнуть, что сообщение не искажено.

Если функция Н зависит также от ключа k K, то помимо проверки целостности добавление значения хэш к сообщению подтверждает истинность сообщения. Такой способ подтверждения истинности называется кодом аутентификации (Message Autentification Code - MAC).

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

52

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

преобразует слово из Аl в слово из Аl и каждый определен на Аl . Первый алгоритм известен всем, а второй - только владельцу В. Обладание алгоритмом D B однозначно (юридически) определяет корреспондента В.

Считаем, что ЕB и D B удовлетворяют соотношениям α Аl

ЕB D B (α) = α, D B ЕB (α) = α.

Тогда электронной подписью документа М А* называется

С = D B (Н(М)).

Проверка подписи под документом М возможна любым лицом, у которого есть ЕB . Для этого проверяющий вычисляет Н(М) (Н( ) - известна

всем, М проверяющий получает вместе с подписью С ). Второй шаг проверки - вычисление

ЕB (С) = ЕB D B ( Н(М)) = Н(М).

Если вычисленное значение хэш от М совпало с результатом применения алгоритмов ЕB к С, то подпись В считается подтвержденной (даже в суде).

Свойства хэш-функций.

1. Если М ≠ М’ хотя бы в одном знаке, то Н( М) ≠ Н(М’) примерно на половине знаков.

Это свойство отмечалось выше. Отметим также, что могут найтись такие М ≠ М’, что Н( М) = Н(М’), но выбор таких М и М’ случайно маловероятен, а подбор труден.

2. Для произвольной строки α Аl трудно подобрать М А* такое, что Н( М) = α.

3. Н( М) вычисляется быстро.

Выполнить п. 1)-3) не просто. В РФ принят стандарт ГОСТ 3411.94 на хэш. Длина хэш 256 бит.

Построение хэш.

Обычно хэш Н( ) строится следующим образом.

1) Выбирается			функция h: Аl × Аl → Аl , удовлетворяющая
свойствам 1-3.
Например, когда длина хэш была 64 бита, то брали следующую схему
	X			Y

53

DES

ключ

Z

Рис. 1

z = h(x,y) = DES y (x).

2) α А* , α = α1...αt ,

где длина блока αi равна l, а блок αt дополнен до блока длины l(если это необходимо). Н(α ) вычисляется по следующему алгоритму.

β1 = h(α1,α2 )

β2 =h(β1,α3 )

βt−1 =h(βt−2 ,αt ).

Основная атака на хэш - это метод коллизий. Пусть В - мошенник, а D - лицо, подвергающееся атаке. В готовит два документа М и М’ так, что документ М пользователь D охотно подпишет, а В заинтересован в подписи D под документом М’. Тогда, подписав у D документ М, В получает подпись С = D B (Н(М)). Если М’ выбрано так, что Н( М) = Н(М’),

то В предъявляет суду (М’, С). Судья убеждается, что подпись под М’ принадлежит D. тогда атака удалась.

Каким образом можно выбрать два таких сообщения? По свойству 2 подбор осуществить сложно.

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

В выбирает два нужных сообщения М и М’, при этом D может подписать сообщение М, но не подпишет сообщение М’. Варьируя в сообщениях интервалами, шрифтами, форматами и т.п., В получает n пар вариантов М и М’ без изменения их смысла. И, следовательно, n пар соответствующих им хэш-функций.

H(M1)		H(M1' )
H(M 2 )		H(M '2 )			(1)
H(M n )		H(M 'n )
Затем,		просматривая все	пары, ищет	совпадения.	Сообщения
M1,…,Мn	отличаются слабо, а их хэш-функции отличаются				значительно,
так что	мы	можем считать,	что значения	хэш-функций	выбираются