Основные характеристики криптосистем
Тип криптосистемы
|
Операции с битами или блоками
|
Зависимость от предыдущих знаков
|
Позиционная зависимость
|
Наличие симметрии функции шифрования
|
Поточного шифрования
|
Биты
|
Не зависит
|
Зависит
|
Симметричная
|
Блочного шифрования
|
Блоки
|
Не зависит
|
Не зависит
|
Симметричная или несимметричная
|
С обратной связью от шифртекста
|
Биты или блоки
|
Зависит
|
Не зависит
|
Симметричная
|
Поточное шифрование состоит в том, что биты открытого текста складываются по модулю 2 с битами псевдослучайной последовательности. К достоинствам поточных шифров относятся:
высокая скорость шифрования;
относительная простота реализации;
и отсутствие размножения ошибок.
Недостатком является необходимость передачи информации синхронизации перед заголовком сообщения, которая должна быть принята до расшифрования любого сообщения. Это обусловлено тем, что если два различных сообщения шифруются на одном и том же ключе, то для расшифрования этих сообщений требуется одна и та же псевдослучайная последовательность. Такое положение может создать угрозу криптостойкости системы. Поэтому часто используют дополнительный, случайно выбираемый ключ сообщения, который передается в начале сообщения и применяется для модификации ключа шифрования. В результате разные сообщения будут шифроваться с помощью различных последовательностей.
Поточные шифры широко применяются для шифрования преобразованных в цифровую форму речевых сигналов и цифровых данных, требующих оперативной доставки потребителю информации. До недавнего времени такие применения были преобладающими для данного метода шифрования. Это обусловлено, в частности, относительной простотой проектирования и реализации генераторов хороших шифрующих последовательностей. Но самым важным фактором, конечно, является отсутствие размножения ошибок в поточном шифре. Стандартным методом генерирования последовательностей для поточного шифрования является метод, применяемый в стандарте шифрования DES в режиме обратной связи по выходу (режим OFB).
При блочном шифровании открытый текст сначала разбивается на равные по длине блоки, затем применяется зависящая от ключа функция шифрования для преобразования блока открытого текста длиной m бит в блок шифртекста такой же длины. Достоинством блочного шифрования является то, что каждый бит блока шифртекста зависит от значений всех битов соответствующего блока открытого текста, и никакие два блока открытого текста не могут быть представлены одним и тем же блоком шифртекста. Алгоритм блочного шифрования может использоваться в различных режимах. Четыре режима шифрования алгоритма DES фактически применимы к любому блочному шифру:
режим прямого шифрования или шифрования с использованием электронной книги кодов ЕСВ (Electronic code Book);
шифрование со сцеплением блоков шифртекста СВС (Cipher block chaining);
шифрование с обратной связью по шифртексту СРВ (Cipher feedback);
шифрование с обратной связью по выходу OFB (Output feedback).
Основным достоинством прямого блочного шифрования ЕСВ является то, что в хорошо спроектированной системе блочного шифрования небольшие изменения в шифртексте вызывают большие и непредсказуемые изменения в соответствующем открытом тексте, и наоборот. Вместе с тем применение блочного шифра в данном режиме имеет серьезные недостатки. Первый из них заключается в том, что вследствие детерминированного характера шифрования при фиксированной длине блока 64 бита можно осуществить криптоанализ шифртекста "со словарем" в ограниченной форме. Это обусловлено тем, что идентичные блоки открытого текста длиной 64 бита в исходном сообщении представляются идентичными блоками шифртекста, что позволяет криптоаналитику сделать определенные выводы о содержании сообщения. Другой потенциальный недостаток этого шифра связан с размножением ошибок. Результатом изменения только одного бита в принятом блоке шифртекста будет неправильное расшифрование всего блока. Это, в свою очередь, приведет к появлению искаженных битов (от 1 до 64) в восстановленном блоке исходного текста.
Из-за отмеченных недостатков блочные шифры редко применяются в указанном режиме для шифрования длинных сообщений. Однако в финансовых учреждениях, где сообщения часто состоят из одного или двух блоков, блочные шифры широко используют в режиме прямого шифрования. Такое применение обычно связано с возможностью частой смены ключа шифрования, поэтому вероятность шифрования двух идентичных блоков открытого текста на одном и том же ключе очень мала.
Криптосистема с открытым ключом также является системой блочного шифрования и должна оперировать блоками довольно большой длины. Это обусловлено тем, что криптоаналитик знает открытый ключ шифрования и мог бы заранее вычислить и составить таблицу соответствия блоков открытого текста и шифртекста. Если длина блоков мала, например 30 бит, то число возможных блоков не слишком большое (при длине 30 бит это 2 = ~109 ), и может быть составлена полная таблица, позволяющая моментально расшифровать любое сообщение с использованием известного открытого ключа. Асимметричные криптосистемы с открытым ключом подробно разбираются в следующей главе.
Наиболее часто блочные шифры применяются в системах шифрования с обратной связью. Системы шифрования с обратной связью встречаются в различных практических вариантах. Как и при блочном шифровании, сообщения разбивают на ряд блоков, состоящих из m бит. Для преобразования этих блоков в блоки шифртекста, которые также состоят из m бит, используются специальные функции шифрования. Однако если в блочном шифре такая функция зависит только от ключа, то в блочных шифрах с обратной связью она зависит как от ключа, так и от одного или более предшествующих блоков шифртекста.
Практически важным шифром с обратной связью является шифр со сцеплением блоков шифртекста СВС. В этом случае m бит предыдущего шифртекста суммируются по модулю 2 со следующими m битами открытого текста, а затем применяется алгоритм блочного шифрования под управлением ключа для получения следующего блока шифртекста. Еще один вариант шифра с обратной связью получается из стандартного режима CFB алгоритма DES, т.е. режима с обратной связью по шифртексту.
Достоинством криптосистем блочного шифрования с обратной связью является возможность применения их для обнаружения манипуляций сообщениями, производимых активными перехватчиками. При этом используется факт размножения ошибок в таких шифрах, а также способность этих систем легко генерировать код аутентификации сообщений. Поэтому системы шифрования с обратной связью используют не только для шифрования сообщений, но и для их аутентификации. Криптосистемам блочного шифрования с обратной связью свойственны некоторые недостатки. Основным из них является размножение ошибок, так как один ошибочный бит при передаче может вызвать ряд ошибок в расшифрованном тексте. Другой недостаток связан с тем, что разработка и реализация систем шифрования с обратной связью часто оказываются более трудными, чем систем поточного шифрования,
На практике для шифрования длинных сообщений применяют поточные шифры или шифры с обратной связью. Выбор конкретного типа шифра зависит от назначения системы и предъявляемых к ней требований.
Рассмотрим для учебных целей следующий простой пример шифрования. Пусть открытый текст состоит из слова приветствия “Hi”. Согласно коду ASCII открытый текст будет содержать следующую двоичную последовательность: “0100011001101001”. В качестве алгоритма шифрования и дешифрования будем использовать поразрядное сложение текста по модулю 2 (операция XOR) с восьмиразрядным ключом “10010011”. Тогда шифрованный текст будет иметь вид: ”1101010111111010”. На приемной стороне этот же алгоритм повторится с тем же самым ключом и в результате будет получен исходный текст. Если нарушителю ключ неизвестен, но известен алгоритм, то он легко сможет его найти, применив 256 возможных комбинаций ключа к шифрованному тексту. Поэтому на самом деле в шифровальных устройствах ключи значительно длинее. Часто они содержат 64 бита. Таким образом, используя метод “проб и ошибок” нарушителю возможно придется проверить 264 комбинаций. Даже на сверхбыстродействующей специализированной машине, способной проверку каждого ключа произвести за одну микросекунду, среднеее время поиска правильного ключа составит 264/2 (мкс)=292271 (год). При 80- битовом ключе для перебора потребовалось бы время, превышающее возраст вселенной.
При шифровании с открытым ключом для шифрования и расшифровывания используются разные ключи, и знание одного из них не дает практической возможности определить другой. Поэтому ключ для шифрования может быть сделан общедоступным. Сейчас два метода шифрования с открытым ключом получили признание и закреплены в стандартах. Национальный институт стандартов и технологий США NIST (бывший ANSI) принял стандарт MD 20899, основанный на алгоритме Эль Гамаля, а на основе алгоритма RSA приняты стандарты ISO/IEC/DIS 9594-8 (МОС) и X.509 (МККТТ).
В шифрах с общим (открытым) ключом способность зашифровывать сообщения данным ключом отделяется от возможности дешифрования этих сообщений. Это достигается путем использования пар преобразований (Е, D), каждое из которых обратно другому, но ни одно из которых нельзя легко получить из другого. Такие односторонние преобразования используют один общий ключ Е и секретный ключ D. Процесс вычисления ключей выполняется приемником сообщений, который оставляет у себя тот ключ, который он будет затем использовать, т.е. секретный ключ. Другой ключ он высылает передатчику сообщений. Этот ключ можно назвать ключом общего пользования или общим ключом, поскольку нет риска в том, что он будет широко известен. Для двустороннего диалога партнеры должны обменяться своими ключами общего пользования. Перехватив такое сообщение, нарушитель может послать сообщение в адрес приемника. Чтобы этого не произошло, надо решить задачу аутентификации.
Итак, поскольку в системах с общим ключом кто угодно может передавать пользователю (i) сообщение, зашифрованное открытым ключом этого пользователя (Еi), то требуется некоторый дополнительный механизм для надежной идентификации отправителя. Эта проблема решается следующим образом: отправитель (j) должен шифровать свое сообщение своим секретным ключом (Dj), а затем открытым ключом предполагаемого получателя (Еi). Получатель затем может снять внешний слой шифрования, используя секретный ключ (Di), и завершить дешифрирование с помощью открытого ключа отправителя (Еj)..
В системах с общим ключом преобразования по шифрованию и дешифрованию обязательно должны легко вычисляться и быть взаимно обратными, а пары ключей (Еi, Di) должны легко генерироваться. Более того, требуется, что бы было невозможно ни вывести Di из Еi, ни обратить преобразование без соответствующих ключей.
Шифры перестановки
При шифровании перестановкой символы шифруемого текста переставляются по определенному правилу в пределах блока этого текста. Шифры перестановки являются самыми простыми и, вероятно, самыми древними шифрами.
Шифр перестановки “скитала”
Известно, что в V веке до нашей эры правители Спарты, наиболее воинственного из греческих государств, имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью скитала, первого простейшего криптографического устройства, реализующего метод простой перестановки.
Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения (рис. 1.). Затем снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположенными хаотично. Такой же результат можно получить, если буквы сообщения писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст.
Сообщение НАСТУПАЙТЕ при размещении его по окружности стержня по три буквы дает шифртекст: НУТАПЕСА_ТЙ
Рис.1. Шифр «скитала»
Для расшифрования такого шифртекста нужно не только знать правило шифрования, но и обладать ключом в виде стержня определенного диаметра. Зная только вид шифра, но не имея ключа, расшифровать сообщение было непросто. Шифр «скитала» многократно совершенствовался в последующие времена.
Шифрующие таблицы
С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. Наряду с традиционными применениями криптографии в политике, дипломатии и военном деле появляются и другие задачи — защита интеллектуальной собственности от преследований инквизиции или заимствований злоумышленников. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые в сущности задают правила перестановки букв в сообщении.
В качестве ключа в шифрующих таблицах используются:
размер таблицы;
слово или фраза, задающие перестановку;
особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром «скитала». Например, сообщение
ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ
записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан ниже. После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам
Т
|
Н
|
П
|
В
|
Е
|
Г
|
Л
|
Е
|
А
|
Р
|
А
|
Д
|
О
|
Н
|
Р
|
Т
|
И
|
Е
|
Ь
|
В
|
О
|
М
|
0
|
Б
|
Т
|
М
|
П
|
Ч
|
И
|
Р
|
Ы
|
С
|
О
|
О
|
Ь
|
Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение: ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ
Естественно, отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. Следует заметить, что объединение букв шифртекста в 5-буквенные группы не входит в ключ шифра и осуществляется для удобства записи не смыслового текста. При расшифровании действия выполняют в обратном порядке.
Несколько большей стойкостью к раскрытию обладает метод шифрования, называемый одиночной перестановкой по ключу. Этот метод отличается от предыдущего тем, что столбцы таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы.
Применим в качестве ключа, например, слово ПЕЛИКАН, а текст сообщения возьмем из предыдущего примера. Ниже показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица - заполнению после перестановки.
П
|
Е
|
Л
|
И
|
К
|
А
|
Н
|
|
А
|
Е
|
И
|
К
|
Л
|
Н
|
П
|
7
|
2
|
5
|
3
|
4
|
1
|
6
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Т
|
Н
|
П
|
В
|
Е
|
Г
|
Л
|
Г
|
Н
|
В
|
Е
|
П
|
Л
|
Т
|
Е
|
А
|
Р
|
А
|
Д
|
О
|
Н
|
О
|
А
|
А
|
Д
|
Р
|
Н
|
Е
|
Р
|
Т
|
И
|
Е
|
Ь
|
В
|
О
|
В
|
Т
|
Е
|
Ь
|
И
|
О
|
Р
|
М
|
0
|
Б
|
Т
|
М
|
П
|
Ч
|
П
|
О
|
Т
|
М
|
Б
|
Ч
|
М
|
И
|
Р
|
Ы
|
С
|
O0
|
О
|
Ь
|
О
|
Р
|
С
|
О
|
Ы
|
Ь
|
И
| К  люч
До перестановки После перестановки
В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, они бы были пронумерованы слева направо. В правой таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа.
При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение:
|
