Полный курс лекций 2009-го года (1130357), страница 80

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

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

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

Чтобы защититься от чтения почты, 64-разрядного ключа вполне достаточно. Для засекречиваниягосударственных документов потребуется ключ в 128 или даже 256 разрядов.С точки зрения криптоаналитика проблема дешифровки возникает в трех вариантах:§есть только шифрограмма§есть шифрограмма и само сообщение§есть фрагменты исходного сообщения и их шифрограммы7.1.1.1. Шифрование замещениемВсе приемы шифрования исторически делились на шифрование замещением и шифрованиеперестановкой.Шифрование замещением состоит в том, что буква или группа букв замещается другой буквой илигруппой букв. Например, шифр Юлия Цезаря состоял в замене каждой буквы третьей следующей за ней валфавите.абвгдеёжзийклмнопрстуфхцчшщъыьэюягдеёжзийклмнопрстуфхцчшщъыьэюяабвпришёл увидел победилтулыио целжзо тсдзжлоЭто так называемое моноалфавитное замещение, где ключом является 33-буквенная строка,соответствующая алфавиту.

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

Затем найти устойчивыебуквосочетания, и т.д. Поэтому значение имеют дополнительные сведения, на каком языке написаноисходное сообщение, его длина. Чем длиннее сообщение, тем представительнее выборка для его анализапо частоте встречаемости букв и буквосочетаний.7.1.1.2. Шифрование перестановкойШифрование перестановкой состоит в изменении порядка букв без изменения самих букв.

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

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

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

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

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

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

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

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

Алгоритмы с секретными ключамиСовременная криптология использует те же идеи, что и раньше. Однако акценты расставлены иначе.Если раньше алгоритм был прост, а вся сложность заключалась в ключе, то теперь, наоборот, стараютсяалгоритм делать как можно изощреннее. Его стараются делать таким, чтобы, если криптоаналитик получилкак угодно много зашифрованного текста, он не смог ничего сделать.Рисунок 7-4. Основные составляющие шифрования: (а) P-схема; (b) S-схема;(c) РезультатПерестановка и замещение реализуются простыми схемами, показанными на рисунке 7-4. P- и Sсхемы могут объединяться в сложные каскады.

В этом случае выход становится очень сложной функциейвхода. На этом рисунке Р-схема выполняет перестановку над словом из 8 разрядов. Схема S действуетнесколько сложнее, выполняя операцию замещения. Она кодирует трехразрядное слово одной из 8 линийна выходе, устанавливая ее в 1. Затем схема Р переставляет эти 8 разрядов, после чего S-схема выполняетзамещение 8 на 3.7.1.3.1. Алгоритм DESВ январе 1977 правительство США приняло стандарт в области шифрования (Data EncryptionStandard), созданный на базе разработки фирмы IBM.

Разница между этими разработками состояла в том,что DES предполагал 56-разрядный ключ, а у IBM он 128-разрядный. На рисунке 7-5 показана схемаэтого алгоритма.Рисунок 7-5. Стандарт DES: а) Общая схема; b) Действие одной итерацииАлгоритм состоит из 19 этапов. На первом этапе исходный текст разбивается на блоки по 64 биткаждый.

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

Список файлов лекций