Шифры и их классификация

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

Принято различать криптоалгоритмы по степени доказуемости их безопасности. Существуют:

· безусловно стойкие (теоретически недешифруемые (ТНДШ));

· практически стойкие системы (для которых существует единственное правильное решение, но для его вычисления потребуется нереализуемо большое количество операций и(или) памяти (ПНДШ))

o доказуемо стойкие;

o предположительно стойкие криптоалгоритмы (практически недешифруемые).

Безопасность безусловно стойких криптоалгоритмов основана на доказанных теоремах о невозможности раскрытия ключа. Примером безусловно стойкого криптоалгоритма является система с разовым использованием ключей (шифр Вернама) или система квантовой криптографии, основанная на квантовомеханическом принципе неопределенности. Стойкость доказуемо стойких криптоалгоритмов определяется сложностью решения хорошо известной математической задачи, которую пытались решить многие математики и которая является общепризнанно сложной. Примером может служить система Диффи-Хеллмана или Ривеста-Шамира-Аделмана, основанные на сложностях соответственно дискретного логарифмирования и разложения целого числа на множители. Предположительно стойкие криптоалгоритмы основаны на сложности решения частной математической задачи, которая не сводится к хорошо известным задачам и которую пытались решить один или несколько человек. Примерами могут быть криптоалгоритмы ГОСТ 28147-89, DES, FEAL.

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

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

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

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

· По размеру обрабатываемого (шифруемого) блока - блочные и поточные;

· По виду обрабатываемого сигнала – дискретные и аналоговые;

· По типу засекречиваемых сообщений – для засекречивания телеграфных, речевых, факсимильных сообщений или передачи данных

· По типу связи межу процессом шифрования и расшифрования – линейного и предварительного шифрования;

· По виду синхронизации между процессом шифрования и расшифрования- автономные, с каналом синхронизации и полуавтономные;

· …….

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

Если ключ зашифрования совпадает с ключом расшифрования: , то такие шифры называют симметричными, если же — асимметричными.

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

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

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

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

.

Рис. 10

Исторически известный шифр пропорциональной замены представляет собой пример шифра многозначной замены, шифр гаммирования – пример шифра однозначной замены. Далее мы будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. Итак, далее и .

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

В силу инъективности (по ) отображения и того, что , введенные в общем случае отображения являются биекциями , определенными равенствами , . Число таких биекций не превосходит .

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

(2')

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

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

В подавляющем большинстве случаев используются шифры замены, для которых , для некоторого . При говорят о поточных шифрах замены, при — о блочных шифрах замены:

Следующее определение. В случае шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены:

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

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

Далее мы рассмотрим свойства большинства из указанных на схеме классов шифров.

Рис. 14

Модели шифров

В любую систему шифрования (засекречивания) входят три объекта:

1. множество исходных сообщений { x_i }, с распределением вероятностей { p(x_i) }, i = 1,A^L;

где – A^L – множество декартовых степеней сообщений длины L составленных из элементов алфавита А.

2. множество ключей шифра { k_j } с распределением вероятностей { p (k_j)}, j = 1,S;

3. множество криптограмм { y_j }, порождаемых взаимодействием случайно выбранного сообщения и ключей.

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

y_i = f(x_i,k_i) - шифрование (засекречивание)

x_i = d(y_j, k_j) - расшифрование (рассекречивание).

Например, такой функцией может быть булева функция неравнозначности, (сложения по модулю 2), Y_i = X_i Å K_i X_i = Y_i Å K_j

Заметим, если K_i шифрования и K_j расшифрования удовлетворяют K_i = K_j,то система называется симметричной.

В операторной форме Y _i = X _{i *} Q _i - шифрование, X _i = Y _{i *} Q _i^-1 - расшифрование.

С помощью таблицы соответствия между парами x_i, k_i и шифрованными сообщениями y_i:

Таблица 1

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

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

Используя графическое представление СШ введем некоторые понятия:

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

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

Если одно и то же сообщение может быть преобразовано в криптограмму разными ключами, то такие ключи называются эквивалентными см. x₁ k¢₁₁ и k₁₁. В СШ со строго неэквивалентными ключами не может быть параллельных ребер, т.е. точки соединяются только одним ребром.

Остановимся более подробно на алгебраической модели шифров.

Пусть — конечные множества возможных открытых текстов, ключей и шифрованных текстов соответственно; — правило зашифрования на ключе . Множество обозначим через , а множество — через . Пусть — правило расшифрования на ключе , и — это множество .

Здесь и далее мы будем предполагать, что если представляется в виде , где — ключ зашифрования, а — ключ расшифрования (причем ), то понимается как функция , а — как функция .

Определение 1. Шифром (шифрсистемой) назовем совокупность введенных множеств, для которых выполняются следующие свойства:

1) для любых и выполняется равенство

;

2) .

Неформально, шифр — это совокупность множеств возможных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифртекстов (то, во что шифруется), правил зашифрования и правил расшифрования.

Отметим, что условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент может быть представлен в виде для подходящих элементов и . Отметим также, что в общем случае утверждение “для любых и выполняется равенство ” является неверным.

Легко проверить, что из условия 1) следует свойство инъективности функции . Другими словами, если , причем , то при любом выполняется неравенство .

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

Введем теперь вероятностную модель шифра. Следуя К.Шеннону, определим априорные распределения вероятностей на множествах и соответственно. Тем самым для любого определена вероятность и для любого — вероятность , причем выполняются равенства

и .

В тех случаях, когда нам требуется знание распределений и , мы будем пользоваться вероятностной моделью , состоящей из пяти множеств, связанных условиями 1) и 2) определения 1, и двух вероятностных распределений: = ().

Забегая вперед, отметим, что вероятностные характеристики шифров используются лишь в криптоанализе — разделе криптографии, посвященном решению задач вскрытия (или взлома) шифров.

В большинстве случаев множества и представляют собой объединения декартовых степеней некоторых множеств и соответственно, так что для некоторых натуральных и

.

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

Поиск по сайту: