Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
порционально отношению Это объясняет широко ис-
у = Ek (х) . Легко видеть, что сумма
yeY
совпадает с
числом клеток этой таблицы, откуда следует (25). Из (25) следует очевидное неравенство
ра, для которого рИМ =
= J-J-, что и требуется.
и
185
І лава /
пользуемый для имитозащиты способ введения избыточности в передаваемое сообщение, например, дополнительных “добавок” к передаваемому сообщению типа аутентификаторов или имитовставок.
Утверадение 2. Для шифра Yb с равновероятными ключами имеет место достижимая оценка
ІХІ-1
Pnom -
Доказательство. Пусть К(у,у') = К(у)г>К(у'). Тогда, в силу условия равновероятности ключей, из (24) получаем:
„ ,„„fed ™
ад ¦
Несложно заметить, что выполняется соотношение
?1^,/)1 = (1^1-1)-1*?-)!, (28)
у\(у'*у)
из которого (поскольку сумма в левой части равенства содержит |Г| -1 слагаемых), следует неравенство
\к(у,у'І 'И-1
шах ------Tj- > V-т—. (29)
\К(у] |У|-1
В силу (27)
\К(у)\ •
186
Надежность шифров
Отсюда и из (29) получаем требуемое неравенство. Остается доказать его достижимость. Для этого построим соответствующий пример.
Попытаемся построить шифр удовлетворяющий условиям
|ВД| = |*</)|. Yv,/Є г,
\К(У\,УгІ= К(У\.У2), Vyuy2ZY. <30)
Согласно (25) и (28) для такого шифра выполняются соотношения
f м-IjcooH-vW
||ад| • (М -1) = \К(у,У )| • (|У| -1), Vy, у е г,
из которых сразу получаем искомое равенство
\К(У,У') IM-I
Р“т |ВД| и-г
Таблицу зашифрования шифра, удовлетворяющего условиям (30), можно построить с помощью так называемых ортогональных латинских квадратов.
Два латинских квадрата размером п х п, составленные из элементов множества 1, 2,..., п. называются ортогональными, если при их совмещении друг с другом получается таблица, содержащая (в своих клетках) все п возможных (упорядоченных) пар чисел i,j є I, п.
Известно [Хол70], что перестановкой строк и столбцов любой латинский квадрат можно привести к виду, в котором в первом столбце числа 1, 2,...,п идут в возрастающем порядке.
187
І лава 7
Такой латинский квадрат называется полунормсишзованным. Известно также [Хол70], что любую пару ортогональных латинских квадратов можно привести перестановкой строк и столбцов к паре полунормализованных латинских квадратов.
Рассмотрим теперь таблицу чисел размером 2п х (п -1), полученную из пары полунормализованных латинских квадратов размером п х п наложением друг на друга и вычеркиванием получившегося первого столбца. При этом 2п строк образуются графически из полученного прямоугольника, если
ГО
каждую составляющую его пару (/,/) записать в виде
У)
Можно заметить, что ее можно использовать в качестве таблицы зашифрования искомого шифра. Гак, для и = 3 соответствующий пример изображен на рис. 22-24.
1 2 3
2 3 1
3 1 2
1 3 2
2 1 3
3 2 1
Рис. 22. Полунормализованные ортогональные латинские квадраты
0,1) (2,3) (3,2)
(2,2) (3,1) (1,3)
(3,3) (1,2) (2,1)
Рис. 23. Наложение латинских квадратов
В данном примере |К(у)\ = 4, \К(у,у' )| = 2. Построенный таким образом шифр Xe имеет следующие параметры: |х| = п -1, |г| = п, (А-] = 2п. Поэтому для него
188
Надежность шифров
П-2
Pnom і
П-I
Х\ X2
2 3
Ic2 3 2
къ 3 I
К I 3
К I 2
К 2 I
Рис. 24. Таблица зашифрования
Для доказательства утверждения 2 остается добавить, что имеет место следующее утверждение [Хол70]: для всякого п > 6 существует пара ортогональных латинских квадратов порядка п.
Утверждение доказано.
Итак, вероятность навязывания рн для шифра с равновероятными ключами удовлетворяет неравенству
Поэтому для надежной защиты от подмены или навязывания необходимо, чтобы число |Г| значительно превосходило чис-
ло \х\.
Возникает естественный вопрос, как определить совершенную имитостойкость (то есть теоретически наилучшую
189
І лава /
защиту от имитации или подмены), достижимую при данной величине |У| множества допустимых криптограмм и при произвольном распределении P(K) на множестве ключей. Чтобы ответить на этот вопрос, приведем более тонкую оценку для вероятности рим , известную как граница Симмонса.
Обозначим через I(Y9K) взаимную информацию между Y и К [Сим88], то есть величину, определяемую формулой
тогда справедливо следующее.
Утверждение 3. Имеет место достижимая оценка
Доказательство. Обозначим через S(y9k) индикатор события dk (у) є X :
Тогда для данного ключа к є К криптограмма у будет принята как допустимая лишь в том случае, когда д(у9к) = 1.
Согласно формуле полной вероятности вероятность р(у — доп) того, что у окажется допустимой криптограммой, равна
I(YtK) = H(Y)-H(YjK),
(31)
IoёРии>-I(YiK).
(32)
dk(y)eX,
dk(y)*X.
р(у - доп) = Y р(к) • Р(У - доп/к),
кеК
а поскольку 190
Надежность шифров
то
р(у-доп/к) = J1, ^Д) = 1’
[О, S (у, к) = О,
р(у -доп) = Y4^iy, к) -р(к). (33)
кеК
Представим вероятность р(у) в виде РІУ) = Y P(k) -Piyf к) =Y р(к) • р(у/k)-S(y,k). (34)
кєК кєК
