1 (1131253), страница 48

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

Текст из файла (страница 48)

Обычное шифрование.

Стандартная схема шифрования такова (см. рисунок 7-2). Исходный текст, называемый также открытым текстом (plain text), обрабатывают специальной функцией со специальным параметром, называемым ключом. В результате этой обработки получают так называемый шифр-текст (ciphertext), или криптограмму. Злоумышленник аккуратно копирует все шифр-тексты. Однако, в отличие от получателя, у него нет ключа, и он не может быстро прочесть сообщение. Иногда злоумышленник может не только копировать сообщение, но позже отправлять свои, имитируя настоящего отправителя, чьи сообщения он копировал. Такого злоумышленника называют активным. Искусство создания шифра называют криптографией, а вскрытия – криптоанализом. Обе эти дисциплины образуют криптологию.

Рисунок 7-2. Схема шифрования

Основное правило шифрования - криптоаналитик знает основные приемы шифрования. Другими словами, создавать шифр, предполагая, что какие-то приемы шифрования криптоаналитик не знает, было бы самонадеянностью и непростительной ошибкой. Смена метода шифрования, его создание, тестирование, внедрение - всегда сопровождаются огромными затратами. Эти организационные моменты всегда являлись точками уязвимости любого шифра. Людей, отвечающих за применение и использование шифра всегда мучили вопросы, типа: как часто надо менять шифр? Как определить, что шифр уже вскрыт?

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

Основа секретности – ключ. Его длина – один из основных вопросов разработки. Рассмотрим, как пример, комбинационный цифровой замок. Все знают, что его ключ – последовательность цифр. Для замка из двух цифр надо перебрать 100 комбинаций, для 3 – 1000, и т.д. Длина ключа определяет объем работы, который надо проделать криптоаналитику, чтобы вскрыть шифр. Этот объем растет экспоненциально в зависимости от длины ключа. Секретность достигается не за счет сложности алгоритма, а за счет длины ключа. Чтобы защититься от чтения почты, 64-разрядного ключа вполне достаточно. Для засекречивания государственных документов потребуется ключ в 128 или даже 256 разрядов.

С точки зрения криптоаналитика проблема дешифровки возникает в трех вариантах:

• есть только шифрограмма

• есть шифрограмма и само сообщение

• есть фрагменты исходного сообщения и их шифрограммы

Шифрование замещением.

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

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

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

пришёл увидел победил

тулыио целжзо тсдзжло

Это так называемое моноалфавитное замещение, где ключом является 33-буквенная строка, соответствующая алфавиту. Здесь возможно 33!=4х1033 ключей. Даже если на применение одного ключа компьютер будет тратить 1 мксек., то на расшифровку уйдет около 1013 лет.

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

Шифрование перестановкой.

Шифрование перестановкой состоит в изменении порядка букв без изменения самих букв. Один из таких методов – шифрование по столбцам. Выбираем ключ – последовательность неповторяющихся символов. Символы в этой последовательности нумеруются в соответствии с их местом в алфавите. Номер один получает буква, расположенная ближе всего к началу алфавита, номер два, следующая за ней и т.д. Чем ближе к началу алфавита символ, тем меньше его номер. Шифруемый текст размещается по строкам. Длина строки – длина ключа. Получаем массив. Столбцы нумеруются в соответствии с номером символа в ключе. Каждому столбцу соответствует символ ключа, который имеет определенный номер. Упорядочим столбцы по возрастанию этих номеров. Все символы первого столбца выписываются первыми, затем символы второго и т.д. (рисунок 7-3). Этот метод можно усовершенствовать многими способами.

Рисунок 7-3. Шифрование перестановкой

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

Построить нераскрываемый шифр достаточно просто. Выберем случайным образом битовую строку – это будет ключ. Текст представим как битовую строку. Разделим эту строку по длине ключа. Выполним над полученными фрагментами строки операцию «исключающее ИЛИ» (EXCLUSIVE OR). Полученные фрагменты объединим в строку. Новая строка и есть криптограмма.

Этот метод, называемый методом одноразовой подложки, имеет ряд недостатков. Трудно запомнить ключ. Его где-то надо записать или носить с собой. Это делает метод уязвимым. Например, набор одноразовых подложек можно записать на CD и закамуфлировать под запись последних хитов. Объем шифруемых данных по этому методу ограничен длиной ключа. Метод также очень чувствителен к потере символов при передаче. Правда, используя возможности компьютеров, этот метод вполне можно применять в ряде случаев.

Основная угроза раскрытия текста при криптоанализе состоит в высокой избыточности естественного языка. Например, частотные характеристики встречаемости букв, устойчивые буквосочетания, приветствия и т.д. В связи с этим Шеннон предложил два основных криптографических метода: рассеивание и перемешивание.

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

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

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

Два основных принципа шифрования.

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

Эта избыточность позволит нам отличить нормально зашифрованное сообщение от подсунутого. Пример - уволенный сотрудник, который может напосылать ложных сообщений, если он знает структуру служебных сообщений в компании. Избыточность позволит обнаружить подделку. Например, если в заказах на поставку после имени заказчика стоит 3 байтовое поле заказа (2 байта – код продукта и 1 байт количество), зашифрованное с помощью ключа, то злоумышленник, прихватив с работы справочник заказчиков, может устроить компании «веселую жизнь». Для этого он сгенерирует от имени заказчиков из справочника заявки, где последние 3 байта - случайные числа. Если же длину заявки сделать не 3, а, например, 12 байтов, где первые 9 байтов - 0, и шифровать эту избыточную запись, то уже случайными числами здесь обойтись трудно, и подделку легко распознать.

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

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

Алгоритмы с секретными ключами.

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

Рисунок 7-4. Основные составляющие шифрования: (а) P-схема; (b) S-схема; (c) Результат

Перестановка и замещение реализуются простыми схемами, показанными на рисунке 7-4. P- и S-схемы могут объединяться в сложные каскады. В этом случае выход становится очень сложной функцией входа. На этом рисунке Р-схема выполняет перестановку над словом из 8 разрядов. Схема S действует несколько сложнее, выполняя операцию замещения. Она кодирует трехразрядное слово одной из 8 линий на выходе, устанавливая ее в 1. Затем схема Р переставляет эти 8 разрядов, после чего S-схема выполняет замещение 8 на 3.

Алгоритм DES.

В январе 1977 правительство США приняло стандарт в области шифрования (Data Encryption Standard), созданный на базе разработки фирмы IBM. Разница между этими разработками состояла в том, что DES предполагал 56-разрядный ключ, а у IBM он 128-разрядный. На рисунке 7-5 показана схема этого алгоритма.

Рисунок 7-5. Стандарт DES: а) Общая схема; b) Действие одной итерации

Алгоритм состоит из 19 этапов. На первом этапе исходный текст разбивается на блоки по 64 бит каждый. Над каждым блоком выполняется перестановка. Последний этап является инверсией первой перестановки. Предпоследний этап состоит в обмене местами 32 самых левых битов с 32 самыми правыми битами.

Из исходного ключа с помощью специального преобразования строят 16 частных ключей для каждого промежуточного этапа алгоритма со второго по семнадцатый.

Все промежуточные этапы схожи. У них два входа по 32 бита. Правые 32 бита входа копируют на выход, как левые 32 бита. Над каждым битом из правых 32 битов выполняется преобразование, которое состоит из EXCLUSIVE OR с соответствующим левым битом и значением специальной функции над правым битом и частным ключом данного этапа. Вся сложность алгоритма заключена в этой функции.

Функция состоит из четырех шагов. На первом строят 48-разрядный номер Е как расширение 32-разрядного Ri-1 в соответствии с определенными правилами дублирования и перестановки. Над полученным номером и ключом данного шага выполняется операция EXCLUSIVE OR – это второй шаг. Результат разбивается на 8 групп по 6 бит в каждой. Каждая группа пропускается через свой S-box с четырьмя выходами каждый. На последнем шаге 8х4 бит пропускаются через P-box.

На каждой из 16 итераций используется свой ключ. До начала итераций к исходному ключу применяют 56-разрядную перестановку. Перед каждой итерацией ключ разбивают на две части по 28 разрядов каждая. Каждую часть циклически сдвигают влево на число разрядов, равное номеру итерации. Ki получают как 48-разрядную выборку из 56-разрядного ключа, полученного циклическими сдвигами с дополнительной перестановкой.

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

Второй недостаток – для начала шифрования надо иметь сразу весь 64-разрядный блок исходного текста. Это не совсем удобно, когда приходится иметь дело с интерактивными приложениями.

Первый недостаток устраняется модификацией алгоритма DES, в которой очередной блок исходного текста через операцию EXCLUSIVE OR смешивается с шифром предыдущего блока. Для первого блока используется специальный инициирующий блок, который передается вместе с шифром (рисунок 7-7).

Характеристики

Список файлов ответов (шпаргалок)