Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
разработали свои стандарты на основе DES. Банковские операции при розничной торговле включают транза к- ции между финансовыми организациями и отдельными личностями, а банковские операции при оптовой то р- говле включают транзакции между финансовыми организациями. Рабочая группа ANSI по безопасности финансовых организаций при розничной торговле разработала ста н- дарт для управления PIN-кодами и их безопасностью (ANSI X9.8) [53] и другой использующий DES стандарт для проверки подлинности финансовых сообщений о розничных продажах (ANSI X9.19) [56]. Эта группа ра з- работала и проект стандарта для безопасного распределения ключей (ANSI X9.2.4) [58]. Рабочая группа ANSI по безопасности финансовых организаций при оптовой торговле разработала свой со б- ственный набор стандартов для проверки подлинности сообщений (ANSI X9.9) [54], управления ключами (ANSIX9.17) [55, 1151], шифрования (ANSIX9.2.3) [57] и безопасной проверки подлинности личностей и узлов (ANSI X9.26) [59]. Американская ассоциация банкиров разрабатывает необязательные стандарты для финансовой индустрии. Они опубликовали стандарт, рекомендующий DES для шифрования [1], и другой стандарт для управления криптографическими ключами [2]. До появления в 1987 году Акта о компьютерной безопасности (Computer Security Act) the за разработку ф е- деральных стандартов в области телекоммуникаций отвечала Администрация общих служб (General Services Administration, CSA), а с этого момента ответственность перешла к NIST. CSA опубликовала три стандарта, использующих DES: два для требований к общей безопасности и возможности взаимодействия (Федеральный стандарт 1026 [662] и Федеральный стандарт 1027 [663]) и один для факс-аппаратов Group 3 (Федеральный стандарт 1028 [664]). Казначейство издало стратегические директивы, требующие, чтобы подлинность всех сообщений о переводе электронных финансов удостоверялась с помощью DES [468, 470]. Оно также разработало основанный на DES критерий, которому должны удовлетворять все устройства проверки подлинности [469]. ISO сначала проголосовала за введение DES, называемого в ее интерпретации DEA-1, в качестве междун а- родного стандарта, а затем приняла решение не заниматься стандартизацией криптографии. Однако в 1987 году группа ISO, занимающаяся международными стандартами в области оптовой торговли, применила DES в ме ж- дународном стандарте проверки подлинности [758] и для управления ключами [761]. DES также используется в качестве австралийского банковского стандарта [1497]. Проверка и сертификация оборудования DES Частью стандарта DES является проверка NIST реализаций DES. Эта проверка подтверждает, что реализ а- ция соответствует стандарту. До 1994 года NIST проверял только аппаратные и программно-аппаратные реал и- зации - пока стандарт запрещал программные реализации. На март 1995 года 73 различных реализации были признаны соответствующими стандарту. NIST также разработал программу сертификации устройств проверки подлинности на соответствие ANSI X9.9 и FIPS 113. На март 1995 года было сертифицировано 33 различных продукта. Казначейство использует свою собственную дополнительную процедуру сертификации. У NIST также есть программа проверки аппар а- туры на соответствие ANSI X9.17 для управления ключами при оптовой торговле [1151], На март 1995 года было сертифицировано четыре продукта. 1987 В стандарте DES было оговорено, что он будет пересматриваться каждые пять лет. В 1983 DES был повто р- но сертифицирован без всяких проблем. 6 марта 1987 года в Federal Register NBS попросило прокомментир о- вать предложение на следующие пять лет. NBS предложило на обсуждение следующие три альтернативы [1480, 1481]: вновь подтвердить стандарт на следующие пять лет, отказаться от стандарта или пересмотреть примен и- мость стандарта. NBS и NSA пересмотрели стандарт. В этот раз NSA было задействовано в большей степени. Благодаря по д- писанной Рейганом директиве NSDD-145 NSA получило право вето по отношению к деятельности NBS в обла с- ти криптографии. Первоначально NSA объявило, что оно не сертифицирует стандарт повторно. Проблема была не в том, что DES действительно был взломан, и даже не в том, что он, может быть, был взломан. По видим о- му, предполагалось, что он вот-вот будет взломан. Само по себе NSA предложило Программу коммерческой подписи COMSEC (Commercial COMSEC Endorsement Program, CCEP), которая по сути представляла собой набор алгоритмов для замены DES [85]. Эти разработанные NSA алгоритмы не были опубликованы и были доступны только в виде защищенных от взлома СБИС (см. раздел 25.1). Это предложение не было принято. Было отмечено, что DES широко используется в бизнесе (особенно в ф и- нансах), и что приемлемой альтернативы не существует. Отказ от стандарта оставил бы многие организации без защиты данных. После длительных споров DES был вновь утвержден в качестве правительственного стандарта США до 1992 года [1141]. NBS решило, что DES никогда больше не будет сертифицирован снова [1480]. 1993 Никогда не говори "никогда". В 1992 году альтернативы алгоритму DES все еще не было. NBS, называемый теперь NIST, снова в Federal Register предложило пр окомментировать DES [540]: Цель этого предложения состоит в том, чтобы объявить о предстоящем оценивании адекватности стандарта задаче защ и- ты компьютерных данных на современном уровне. Промышленности и широкой публике предлагаются три следующих вар и- анта решения для FIPS 46-1. Комментарии должны содержать стоимость (последствия) и преимущества этих вариа нтов: — Повторно принять стандарт на следующие пять (5) лет. Национальный институт стандартов и технологии продолжит сертификацию аппаратуры, реализующей стандарт. FIPS 46-1 будет и дальше оставаться единственным признанным м е- тодом защиты несекретных компьютерных данных. — Отказаться от стандарта. Национальный институт стандартов и технологии больше не будет поддерживать стандарт. Организации могут продолжать использовать существующую аппаратуру, реализующую стандарт. Заменяя DES, NIST издаст другие стандарты. — Пересмотреть положения стандарта о применимости и/или провести ревизию реализации. Такая ревизия должна включать изменения стандарта, позволяющие использовать как аппаратные, так программные и реализации DES, и с- пользовать DES итеративно в определенных приложениях, использовать альтернативные алгоритмы, признанные и зар е- гистрированные NIST. Срок принятия предложений истек 10 декабря 1992 года. Согласно Рэймонду Каммеру (Raymond Kammer), в то время директору NIST [812]: В прошлом году NIST формально предложило присылать комментарии по поводу повторной сертификации DES. Ра с- смотрев присланные предложения и другие технические источники, я собираюсь рекомендовать министру торговли, чтобы он повторно сертифицировал DES еще на пять лет. Я также собираюсь предложить министру, чтобы, объявляя о повторной сертификации, мы сформулировали наши намерения рассмотреть в течение этих пяти лет возможные альтернативы. Делая подобное заявление, мы надеемся дать людям возможность высказаться по поводу предстоящих технологических изменений. В то же время, нам нужно учитывать большое количество систем, использующих этот одобренный ста ндарт. Несмотря на то, что Управление оценки технологий ссылалось на слова работавшего в NIST Денниса Бра н- стида (Dennis Branstead) от том, что полезное время жизни DES закончится в конце 90-х [1191], алгоритм был сертифицирован повторно на следующие пять лет [1150]. Наконец было разрешено сертифицировать и пр о- граммные реализации DES. Хотелось бы знать, что случится в 1998 году? 12.2 Описание DES DES представляет собой блочный шифр, он шифрует данные 64-битовыми блоками. С одного конца алг о- ритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста. DES является симметричным алгоритмом: для шифрования и дешифрирования используются одинаковые алг о- ритм и ключ (за исключением небольших различий в использовании ключа). Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент вр е- мени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определ я- ется ключом. На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к те к- сту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз (см. 11-й). L 0 K 2 K 1 R 0 IP Открытый текст f L 1 =R 0 R 1 = L 0 ?f(R 0 ,K 1 ) f L 2 =R 1 R 2 = L 1 ?f(R 1 ,K 1 ) K 16 L 15 =R 14 R 15 = L 14 ?f(R 14 ,K 15 ) f L 16 =R 15 R 16 = L 15 ?f(R 15 ,K 16 ) IP -1 Шифротекст Рис. 12-1. DES. Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-х. Изобилие повторений в алгоритме делает его ид е- альным для реализации в специализированной микросхеме. Первоначальные программные реализации были довольно неуклюжи, но сегодняшние программы намного лучше. Схема алгоритма DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называ е- мых функцией f, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая полов и- ны объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первон а- чальной). На каждом этапе (см. 10-й) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Пр а- вая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется п о- средством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 н о- вых бита, и переставляется снова. Эти четыре операции и выполняются функцией f. Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая п о- ловина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES. Перестановка в P-блоке Сдвиг Сдвиг Ключ Ключ R i-1 L i-1 Перестановка с расширением Подстановка в S-блоке R i L i Перестановка со сжатием Рис. 12-2. Один этап DES. Если B i - это результат i-ой итерации, L i и R i - левая и правая половины B i , K i - 48-битовый ключ для этапа i, а f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как: L i = R i-1 R i = L i-1 ? f(R i-1 , K i ) Начальная перестановка Начальная перестановка выполняется еще до этапа 1, при этом входной блок переставляется, как показано в 11-й. Эту и все другие таблицы этой главы надо читать слева направо и сверху вниз. Например, начальная пер е- становка перемещает бит 58 в битовую позицию 1, бит 50 - в битовую позицию 2, бит 42 - в битовую позицию 3, и так далее. Табл. 12-1. Начальная перестановка 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7 Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES. (Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки да н- ных открытого текста и шифротекста в микросхему DES. Не забывайте, что DES появился раньше 16- и 32- битовых микропроцессорных шин.) Так как программная реализация этой многобитовой перестановки нелегка (в отличие от тривиальной аппаратной), во многих программных реализациях DES начальная и заключител ь- ные перестановки не используются. Хотя такой новый алгоритм не менее безопасен, чем DES, он не соответс т- вует стандарту DES и, поэтому, не может называться DES. Преобразования ключа Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в 10-й. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый подключ. Эти подключи, K i , определяются следующим образом. Табл. 12-2. Перестановка ключа 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4 Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвиг а- ются налево на один или два бита в зависимости от этапа. Этот сдвиг показан в 9-й. Табл. 12-3. Число битов сдвига ключа в зависимости от этапа Этап 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Число 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием (также называемая переставленным выбором) определена в 8-й. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбр а- сывается. Табл. 12-4. Перестановка со сжатием 14, 17, 11, 2,4, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 11, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 Из-за сдвига для каждого подключа используется отличное подмножество битов ключа. Каждый бит испол ь- зуется приблизительно в 14 из 16 подключей, хотя не все биты используются в точности одинаковое число раз. Перестановка с расширением Эта операция расширяет правую половину данных, R i , от 32 до 48 битов. Так как при этом не просто повт о- ряются определенные биты, но и изменяется их порядок, эта операция называется перестановкой с расшире- нием. У нее две задачи: привести размер правой половины в соответствие с ключом для операции XOR и пол у- чить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный криптографический смысл совсем в другом. За счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом. DES спроек- тирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита о т- крытого текста и каждого бита ключа. Перестановка с расширением показана на 9-й. Иногда она называется E-блоком (от expansion). Для каждого 4-битового входного блока первый и четвертый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким поз и- циям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока. 4 3 2 32 48 1 4 3 2 6 5 1 8 7 6 5 10 9 8 12 11 7 12 11 10 9 16 15 14 18 17 13 16 15 14 13 22 21 20 24 23 19 Рис. 12-3. Перестановка с расширением. Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок. Табл. 12-5. Перестановка с расширением 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12., 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1 Подстановка с помощью S-блоков После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, вт о- рой - S-блоком 2, и так далее. См. 8-й. 32-битовый выход 46-битовый вход S-блок 1 S-блок 2 S-блок 3 S-блок 4 S-блок 5 S-блок 6 S-блок 7 S-блок 8 Рис. 12-4. Подстановка - S-блоки. Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4- битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение. Все восемь S-блоков показаны в 6-й. Табл. 12-6. S-блоки S-блок 1: 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12., 5, 9, 0, 7, 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12., 11, 9, 5, 3, 8, |