Лекции 2010-го года (1130544), страница 81
Текст из файла (страница 81)
Если она соответствует частоте букв в языке, то этоозначает, что он имеет дело именно с перестановкой. Намек на порядок столбцов могутдать устойчивые буквосочетания в языке.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 правительство США приняло стандарт в области шифрования (DataEncryption 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 разряда получают на выходе. Это свойство можетиспользовать криптоаналитик. Одни и те же поля исходного текста попадут в одни и те жеместа шифра. Этим можно воспользоваться. Пример с премиями. Один сотрудник можетприписать себе премию другого, если знает взаимное расположение соответствующихполей в исходной записи.
Шифр ему знать ни к чему (рисунок 7-6).Рисунок 7-6. Открытый текст файла, зашифрованного алгоритмом DES в виде 16 блоковВторой недостаток – для начала шифрования надо иметь сразу весь 64-разрядный блокисходного текста. Это не совсем удобно, когда приходится иметь дело с интерактивнымиприложениями.Первый недостаток устраняется модификацией алгоритма DES, в которой очередной блокисходного текста через операцию EXCLUSIVE OR смешивается с шифром предыдущегоблока. Для первого блока используется специальный инициирующий блок, которыйпередается вместе с шифром (рисунок 7-7).Рисунок 7-7. Поблочная передача зашифрованного текстаДля устранения второго недостатка используется т.н.
обратная связь по шифру (рисунок7-8). На рисунке 7-8 (а) показана ситуация, когда первые 10 байт текста уже былизакодированы, а последние 8 из них сохранены в сдвиговом регистре. Когда поступаеточередной байт, выбирается самый левый байт 64-разрядного шифра, и над нимивыполняется EXCLUSIVE OR, результат посылается по линии как шифр байта.
Этотшифрованный байт посылается в сдвиговый регистр, а левый байт выталкивается изрегистра. На стороне получателя над поступившим байтом выполняют ту же самуюоперацию. Этот алгоритм работает хорошо, пока оба сдвиговых 64-разрядных регистраодинаковы. Если при передаче шифрованного байта произойдет однобитовая ошибка, топока испорченный байт не вытолкнут из регистра, расшифрованный текст пойдет сошибкой. После этого ошибка исчезнет. Таким образом, одна битовая ошибка приведет кпорче 64 бит текста.
Этот алгоритм также предполагает наличие некоторогоинициирующего блока, который обеспечивает работу алгоритма, пока все 8 правых байтне поступили.Рисунок 7-8. Обратная связь по шифру7.1.3.2. Раскрытие DESВ 1977 году Диффи и Хеллман из Стэнфорда опубликовали проект машины стоимостью в20 миллионов долларов, которая вскрывала DES. Достаточно было подать на вход этоймашине небольшой фрагмент зашифрованного текста и соответствующий фрагментисходного текста, как эта машина в течение дня находила ключ шифра. Существует многоспособов атаковать шифр. Все они основаны на распараллеливании перебора множествавозможных ключей.
Например, 140000 человек, вооруженных компьютерами,способными выполнять 250000 шифрований с секунду, смогут перебрать пространство7х1016 ключей за месяц.Основной вывод - DES не является надежным шифром и его нельзя использовать дляответственных документов. Удвоение длины ключа до 112 бит кардинально меняетситуацию. Теперь, если использовать даже миллиард аппаратных дешифраторов,выполняющих по миллиард операций в секунду, потребуется 100 миллионов лет, чтобыперебрать пространство из 1016х1016 112-разрядных ключей. Эти рассуждениянаталкивают на идею увеличения длины ключа за счет двукратного применения DES сразными ключами К1 и К2.Однако в 1981 году Хеллман и Меркл обнаружили, что простое использование двухключей не дает надежной схемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
