Полный курс лекций 2009-го года (1130357), страница 81
Текст из файла (страница 81)
Над каждым блоком выполняется перестановка. Последний этап является инверсией первойперестановки. Предпоследний этап состоит в обмене местами 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. Достаточно было подать на вход этой машине небольшойфрагмент зашифрованного текста и соответствующий фрагмент исходного текста, как эта машина втечение дня находила ключ шифра.
Существует много способов атаковать шифр. Все они основаны нараспараллеливании перебора множества возможных ключей. Например, 140 000 человек, вооруженныхкомпьютерами, способными выполнять 250 000 шифрований с секунду, смогут перебрать пространство7 х 1016 ключей за месяц.Основной вывод - DES не является надежным шифром и его нельзя использовать для ответственныхдокументов. Удвоение длины ключа до 112 бит кардинально меняет ситуацию. Теперь, если использоватьдаже миллиард аппаратных дешифраторов, выполняющих по миллиард операций в секунду, потребуется100 миллионов лет, чтобы перебрать пространство из 1016 х 1016 112-разрядных ключей.
Эти рассуждениянаталкивают на идею увеличения длины ключа за счет двукратного применения DES с разными ключамиК1 и К2.Однако в 1981 году Хеллман и Меркл обнаружили, что простое использование двух ключей не даетнадежной схемы. Дело в том, что применение дешифрации к зашифрованному тексту дает шифр, которыйполучается после применения первого ключа к исходному тексту. Эту мысль поясняют следующиеформулы:Ci = EK2(EK1(Pi )); DK2(Ci) = EK1(Pi)В этом случае можно предложить следующую процедуру взлома:1.Вычислить все возможные применения функции Е к шифруемому тексту.2.Вычислить все возможные дешифрации зашифрованного текста однократным применениемдешифрирующей функции.3.Отсортировать полученные таблицы и искать совпадающие строки.4.Полученная пара номеров строк – пара ключей.5.Проверить эту пару на совпадение шифрования; если неудачный результат, продолжить с шага 1.Тройное шифрование совершенно меняет дело.
На рисунке 7-9 показана модификация схемышифрования с двумя ключами в три этапа - EDE-схема. Ее никому еще не удалось вскрыть. Она былаположена в основу международного стандарта. Здесь может возникнуть два вопроса. Первый: почему вэтой схеме используются 2, а не 3 ключа. Второй: почему используется схема EDE, а не EEE? Ответ напервый вопрос состоит в том, что двух ключей более чем достаточно для большинства применений.Использование схемы EDE вместо ЕЕЕ связано с особенностями организации алгоритма DES.Рисунок 7-9.
Тройное шифрование с помощью алгоритма DESНадо отметить, что было предложено много других алгоритмов шифрования.Хорошо известным является международный алгоритм шифрования данных IDEA. Он был разработанспециалистами из Швейцарии, и в нем используют 128-разрядный ключ. Подобно DES, этот алгоритмразбивает исходный текст на 64-разрядные блоки, над которыми производят определенные итерации,каждая из которых имеет параметры.
В результате на выходе получают 64-разрядный блок, как показанона рисунке 7-10 (а). На каждой итерации значение каждого выходного бита зависит от всех входныхбитов, поэтому достаточно 8 итераций, а не 19, как в DES.Рисунок 7-10. (а) IDEA; (б) Подробности одной итерацииПодробности одной итерации показаны на рисунке 7-10 (б). На каждой итерации используются тритипа операций над целыми числами без знака: исключающее ИЛИ, сложение по модулю 216 и умножениепо модулю 216 + 1.Выбор именно этих операций связан с тем, что они не подчиняются распределительному исочетательному законам, что усложняет криптоанализ.
Из 128-разрядного ключа формируют 52 подключапо 16 разрядов: по 6 для каждой из 8 итераций и 4 для последней, финальной стадии. Для реализацииэтого алгоритма была создана специальная микросхема, обеспечивающая скорость шифрования 177Мбит/сек.7.1.4. Алгоритмы с открытыми ключамиИдея алгоритмов шифрования с открытыми ключами была предложена в 1976 году Диффи иХеллманом и состоит в следующем. Пусть у нас есть алгоритмы Е и D, которые удовлетворяют следующимтребованиям:§D(E(P))=P§Чрезвычайно трудно получить D из E.§Е нельзя вскрыть через анализ исходных текстов.Алгоритм шифрования Е и его ключ публикуют или помещают так, чтобы каждый мог их получить,алгоритм D также публикуют, чтобы подвергнуть его изучению, а вот ключи к последнему хранят всекрете.
В этом случае взаимодействие двух абонентов А и В будет выглядеть следующим образом. Пусть Ахочет послать В сообщение Р. А шифрует EВ(P), зная алгоритм и открытый ключ для шифрования. В,получив EВ(P), использует DВ с секретным ключом, т.е. вычисляет DВ(EВ(P))=P. Никто не прочтет P кроме Aи B, т.к. по условию алгоритм EВ не раскрываем по условию, а DВ не выводим из EВ.Примером такого алгоритма является алгоритм RSA, предложенный Ривестом, Шамиром и Адлеманомв 1978 году. Общая схема этого алгоритма такова:1.Выберем два больших (больше 10100) простых числа p и q.2.Вычислим n = p х q и z = (p - 1) х (q - 1 ).3.Выберем d, относительно простое к z.4.Вычислим e такое, что e х d = 1 mod z.Разбиваем исходный текст на блоки Р так, чтобы каждый блок, как число не превосходил n.
Дляэтого выбираем наибольшее k такое, чтобы P = 2k < n. Вычисляем С = Pe(mod n), чтобы зашифроватьсообщение P. Для расшифровки вычисляем P = Cd(mod n).Для шифрования нам нужны (e, n) – это открытый ключ, для расшифровки (d, n) – это закрытыйключ. Можно доказать, что для любого Р в указанном выше диапазоне функции шифрования идешифрования взаимообратные. Безопасность этого метода основана на высокой вычислительнойсложности операции разложения на множители больших чисел.
Так, например, разложение на множители200-разрядного числа потребует 4 миллиардов лет.Рисунок 7-11. Пример использования алгоритма RSAНа рисунке 7-11 дан простой учебный пример применения RSA алгоритма для p = 3, q = 11, n = 33,z = 20, d = 7, откуда e = 3.Один из основных недостатков алгоритма RSA – он работает медленно.7.1.5. Протоколы установления подлинностиПротоколы установления подлинности (аутентификации) позволяют процессу убедиться, что онвзаимодействует с тем, с кем должен, а не с тем, кто лишь представляется таковым.Очень часто путают проверку прав на выполнение тех или иных операций с аутентификацией.
(Впервом случае имеем авторизацию.) Аутентификация отвечает на вопрос: как убедиться, что вывзаимодействуете именно с нужным процессом. Если, например, к серверу процесс обратился с запросомудалить файл x.old и объявил себя процессом Вася, то сервер должен убедиться, что перед нимдействительно Вася и что Вася имеет право делать то, что просит. Ключевым конечно является первыйвопрос, ответ на второй вопрос – это дело просмотра таблицы.Общая схема всех протоколов аутентификации такова: сторона А и сторона В начинаютобмениваться сообщениями между собой или с Центром раздачи ключей (ЦРК). ЦРК - всегда надежныйпартнер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
