Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 27

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 126 >> Следующая


Рис. 8

86
Классификация шифров

§ 3.1. Математическая модель шифра замены

Определим модель ЛА = (X,K,Y,E,D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: XaA*, У с = л, |i?| = /w. Здесь и далее С*

обозначает множество слов конечной длины в алфавите С .

Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в шифртексте, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из А * и В * соответственно.

Пусть U = {wlv..,w^} —множество возможных шифрве-

личин, V = (V1 — множество возможных шифробо-

значений. Эти множества должны быть такими, чтобы любые тексты X є Х,у є Y можно было представить словами из

U*9V* соответственно. Требование однозначности расшифрования влечет неравенства N >п, M >т, M > N.

Для определения правила зашифрования Ek (х) в общем

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

Поскольку M > N, множество V можно представить в

N

виде объединения V = непересекающихся непустых

/=1

подмножеств F(/). Рассмотрим произвольное семейство, состоящее из г таких разбиений множества V :
fлава З

и соответствующее семейство биекций

<pa-и {V",...,V^),

для которых q)a (и,) = Fj0, і = I, N.

Рассмотрим также произвольное отображение ц/ : К х N —> N*, где Nr = {1, 2,..., г}, такое, что для любых к є К, І є N

y/(k,l) = a\k\..af\ а(к) є Nf, j = Tj. (I)

Назовем последовательность у/{к91) распределителем, отвечающим данным значениям к є K9 / є N .

Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть

хеХ,х = X1...X19 х GU9I = I9V9 кеК и y/(k,l) = a\k)...a\k). Тогда Ek О) = у, где у = ух...у,,

yje<pa(k)(Xj),j = l,l. (2)

В качестве у j можно выбрать любой элемент множества ф (*)(jt ). Всякий раз при шифровании этот выбор можно

a j J

производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, так как Fj0 П^7) = 0 при ІФ j.

88
Классификация шифров

§ 3.2. Классификация шифров замены

Если ключ зашифрования совпадает с ключом расшифрования: Jc3 = &р , то (как уже указывалось в гл. 2) такие шифры

называют симметричными, если же к3 Ф кр — асимметричными.

В связи с указанным различием в использовании ключей сделаем еще один шаг в классификации (см. рис. 9).

Рис. 9

Отметим также, что в приведенном определении правило зашифрования Ek (х) является, вообще говоря, многозначной функцией. Выбор ее значений представляет собой некоторую проблему, которая делает многозначные функции Ек(х) не

слишком удобными для использования. Избавиться от этой проблемы позволяет использование однозначных функций, что приводит к естественному разделению всех шифров замены на однозначные и многозначные замены (называемых также в литературе омофонами) (см. рис. 10).

Для однозначных шифров замены справедливо свойство:
І лава З

для многозначных шифров замены:

За,/:|Гв(,)|>1.

Рис. 10

Исторически известный шифр — пропорциональной замены представляет собой пример шифра многозначной замены, шифр гаммирования — пример шифра однозначной замены. Далее мы будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. Итак, далее M = N и <pa(ut) = І = I9M .

Заметим, что правило зашифрования Ek естественно “рассматривается как” отображение, Ek :?/*-> V *.

В силу инъективности (по к) отображения Ek и того, что M=M. введенные в общем случае отображения (ра являются биекциями (ра :U <-> V, определенными равенствами

90
Классификация шифров

Cpa(Ul)- va\ і = I,N9 a = I,г . Число таких биекций не превосходит NI

Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле (2) включение следует заменить равенством

У j =tPa^(Xj), J = 1,1. (2’)

Введем еще ряд определений.

Если для некоторого числа q є N выполняются включения V, є B4, і — I9N, то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае — шифром разнозначной замены (см. рис. 11).

Рис. 11

В подавляющем большинстве случаев используются шифры замены, для которых U є Ap , для некоторого р є N . При р = 1 говорят о поточных шифрах замены, при р > 1 — о блочных шифрах замены (см. рис. \2).

91
І лава J

Рис. 12

Относительно деления шифров на поточные и блочные подробнее CM. в гл. 8.

Следующее определение. В случае г = I шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае — многоалфавитным шифром замены (см. рис. 13).

Рис. 13

Ограничиваясь наиболее важными классами шифров замены и исторически известными классами шифров перестановки, сведем результаты классификации в схему, изображенную на рис. 14.
Предыдущая << 1 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed