Nets2010 (1131259), страница 51

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

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

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

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

Это так называемое моноалфавитное замещение, где ключом является 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).

Рисунок 7-7. Поблочная передача зашифрованного текста

Для устранения второго недостатка используется т.н. обратная связь по шифру (рисунок 7-8). На рисунке 7-8 (а) показана ситуация, когда первые 10 байт текста уже были закодированы, а последние 8 из них сохранены в сдвиговом регистре. Когда поступает очередной байт, выбирается самый левый байт 64-разрядного шифра, и над ними выполняется EXCLUSIVE OR, результат посылается по линии как шифр байта. Этот шифрованный байт посылается в сдвиговый регистр, а левый байт выталкивается из регистра. На стороне получателя над поступившим байтом выполняют ту же самую операцию. Этот алгоритм работает хорошо, пока оба сдвиговых 64-разрядных регистра одинаковы. Если при передаче шифрованного байта произойдет однобитовая ошибка, то пока испорченный байт не вытолкнут из регистра, расшифрованный текст пойдет с ошибкой. После этого ошибка исчезнет. Таким образом, одна битовая ошибка приведет к порче 64 бит текста. Этот алгоритм также предполагает наличие некоторого инициирующего блока, который обеспечивает работу алгоритма, пока все 8 правых байт не поступили.

Рисунок 7-8. Обратная связь по шифру

Раскрытие DES.

В 1977 году Диффи и Хеллман из Стэнфорда опубликовали проект машины стоимостью в 20 миллионов долларов, которая вскрывала DES. Достаточно было подать на вход этой машине небольшой фрагмент зашифрованного текста и соответствующий фрагмент исходного текста, как эта машина в течение дня находила ключ шифра. Существует много способов атаковать шифр. Все они основаны на распараллеливании перебора множества возможных ключей. Например, 140000 человек, вооруженных компьютерами, способными выполнять 250000 шифрований с секунду, смогут перебрать пространство 7х1016 ключей за месяц.

Основной вывод - DES не является надежным шифром и его нельзя использовать для ответственных документов. Удвоение длины ключа до 112 бит кардинально меняет ситуацию. Теперь, если использовать даже миллиард аппаратных дешифраторов, выполняющих по миллиард операций в секунду, потребуется 100 миллионов лет, чтобы перебрать пространство из 1016х1016 112-разрядных ключей. Эти рассуждения наталкивают на идею увеличения длины ключа за счет двукратного применения DES с разными ключами К1 и К2.

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

Ci = EK2(EK1(Pi )); DK2(Ci) = EK1(Pi)

В этом случае можно предложить следующую процедуру взлома:

1. Вычислить все возможные применения функции Е к шифруемому тексту.

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

1. Отсортировать полученные таблицы и искать совпадающие строки.

1. Полученная пара номеров строк – пара ключей.

1. Проверить эту пару на совпадение шифрования; если неудачный результат, продолжить с шага 1.

Тройное шифрование совершенно меняет дело. На рисунке 7-9 показана модификация схемы шифрования с двумя ключами в три этапа - EDE-схема. Ее никому еще не удалось вскрыть. Она была положена в основу международного стандарта. Здесь может возникнуть два вопроса. Первый: почему в этой схеме используются 2, а не 3 ключа. Второй: почему используется схема EDE, а не EEE? Ответ на первый вопрос состоит в том, что двух ключей более чем достаточно для большинства применений. Использование схемы EDE вместо ЕЕЕ связано с особенностями организации алгоритма DES.

Рисунок 7-9. Тройное шифрование с помощью алгоритма DES

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

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