Информация. ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ. В. Ф. Шаньгининформационная безопасность компьютерных систем
![]()
|
КРИПТОГРАФИЧЕСКИЕ АЛГОРИТМЫ Большинство средств защиты информации базируется на использовании криптографических шифров и процедур шифро вания/расшифрования. В соответствии со стандартом шифрова ния ГОСТ 28147—89 под шифром понимают совокупность обра тимых преобразований множества открытых данных на множе ство зашифрованных данных, задаваемых ключом и алгоритмом криптографического преобразования [10]. Существует множест во разных криптографических алгоритмов. Назначение этих ал горитмов — защита информации. Защищать же информацию приходится от разных угроз и разными способами. Чтобы обес печить надежную и адекватную защиту с помощью криптоалго ритма (КА), нужно понимать, какие бывают КА и какой тип ал горитма лучше приспособлен для решения конкретной задачи. 6.1. Классификация криптографических алгоритмов Известны несколько классификаций криптографических ал горитмов [50]. Одна из них подразделяет КА в зависимости от числа ключей, применяемых в конкретном алгоритме: • бесключевые КА — не используют в вычислениях никаких ключей; • одноключевые КА — работают с одним ключевым парамет ром (секретным ключом); • двухключевые КА — на различных стадиях работы в них применяются два ключевых параметра: секретный и откры тый ключи. Существуют более детальные классификации, одна из кото рых приведена на рис. 6.1. Рис. 6.1. Классификация криптоалгоритмов зашиты информации Охарактеризуем кратко основные типы КА. Хэширование — это метод криптозащиты, представляющий собой контрольное преобразование информации: из данных не ограниченного размера путем выполнения криптографических преобразований вычисляется хэш-значение фиксированной дли ны, однозначно соответствующее исходным данным. Симметричное шифрование использует один и тот же ключ как для зашифровывания, так и для расшифровывания инфор мации. Симметричное шифрование подразделяется на два вида: блочное и поточное, хотя следует отметить, что в некоторых клас сификациях они не разделяются и считается, что поточное шиф рование — это шифрование блоков единичной длины. Блочное шифрование характеризуется тем, что информация предварительно разбивается на блоки фиксированной длины (например, 64 или 128 бит). При этом в различных КА или даже в разных режимах работы одного и того же алгоритма блоки мо гут шифроваться как независимо друг от друга, так и «со сцепле нием», т. е. когда результат шифрования текущего блока данных зависит от значения предыдущего блока или от результата шиф рования предыдущего блока. Поточное шифрование применяется, прежде всего, тогда, ко гда информацию невозможно разбить на блоки — скажем, есть некий поток данных, каждый символ которых требуется зашиф ровать и отправить, не дожидаясь остальных данных, достаточ ных для формирования блока. Алгоритмы поточного шифрова ния шифруют данные побитно или посимвольно. Асимметричное шифрование характеризуется применением двух типов ключей: открытого — для зашифровывания инфор мации и секретного — для ее расшифровывания. Секретный и открытый ключи связаны между собой достаточно сложным со отношением. Электронная цифровая подпись (ЭЦП) используется для на дежного подтверждения целостности и авторства данных. 6.2. Симметричные алгоритмы шифрования 6 .2 .1 . О сновны е п о н я т и я В симметричных криптоалгоритмах для зашифровывания и расшифровывания сообщения используется один и тот же блок информации (ключ). Хотя алгоритм воздействия на передавае мые данные может быть известен посторонним лицам, но он за висит от секретного ключа, которым должны обладать только отправитель и получатель. Симметричные криптоалгоритмы вы полняют преобразование небольшого блока данных (1 бит либо 32—128 бит) в зависимости от секретного ключа таким образом, что прочесть исходное сообщение можно только зная этот сек ретный ключ. Симметричные криптосистемы позволяют на основе симмет ричных криптоалгоритмов кодировать и декодировать файлы произвольной длины. Характерная особенность симметричных блочных криптоал горитмов — преобразование блока входной информации фикси рованной длины и получение результирующего блока того же объема, но недоступного для прочтения сторонним лицам, не владеющим ключом. Схему работы симметричного блочного шифра можно описать функциями С= ЕК{М) и М = D ^C ), где М — исходный (открытый) блок данных, С — зашифрован ный блок данных. Ключ К является параметром симметричного блочного крип тоалгоритма и представляет собой блок двоичной информации фиксированного размера. Исходный М и зашифрованный С блоки данных также имеют фиксированную разрядность, рав ную между собой, но необязательно равную длине ключа К. Блочные шифры являются той основой, на которой реализо ваны практически все симметричные криптосистемы. Практиче ски все алгоритмы используют для преобразований определен ный набор обратимых математических преобразований. Методика создания цепочек из зашифрованных блочными алгоритмами байтов позволяет шифровать ими пакеты информа ции неограниченной длины. Отсутствие статистической корре ляции между битами выходного потока блочного шифра исполь зуется для вычисления контрольных сумм пакетов данных и в хэшировании паролей. На сегодняшний день разработано доста точно много стойких блочных шифров. Криптоалгоритм считается идеально стойким, если для про чтения зашифрованного блока данных необходим перебор всех возможных ключей до тех пор, пока расшифрованное сообще ние не окажется осмысленным. В общем случае стойкость блоч ного шифра зависит только от длины ключа и возрастает экспо ненциально с ее ростом. Идеально стойкие криптоалгоритмы должны удовлетворять еще одному важному требованию. Ключ, которым произведено это преобразование, при известных исход ном и зашифрованном значениях блока можно узнать только пу тем полного перебора его значений. 6 .2 .2 . Блочные алгоритмы ш иф рования данных Алгоритм шифрования данных DES (Data Encryption Standard) был опубликован в 1977 г. и остается пока распространенным блочным симметричным алгоритмом, используемым в системах защиты коммерческой информации. Алгоритм DES построен в соответствии с методологией сети Фейстеля и состоит из чередующейся последовательности пере становок и подстановок. Алгоритм DES осуществляет шифрова ние 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 — прове рочные биты для контроля на четность). Процесс шифрования заключается в начальной перестановке битов 64-битового блока, 16 циклах (раундах) шифрования и, наконец, в конечной перестановке битов (рис. 6.2). Рис. 6.2. Обобщенная схема шифрования в алгоритме DES Расшифровывание в DES является операцией, обратной шифрованию, и выполняется путем повторения операций шиф рования в обратной последовательности. Основные достоинства алгоритма DES: • используется только один ключ длиной 56 бит; • относительная простота алгоритма обеспечивает высокую скорость обработки; • зашифровав сообщение с помощью одного пакета про грамм, для расшифровки можно использовать любой дру гой пакет программ, соответствующий алгоритму DES; • криптостойкость алгоритма вполне достаточна для обеспе чения информационной безопасности большинства ком мерческих приложений. Современная микропроцессорная техника позволяет за дос таточно приемлемое время взламывать симметричные блочные шифры с длиной ключа 40 бит. Для такого взламывания исполь зуется метод полного перебора — тотального опробования всех возможных значений ключа (метод «грубой силы»). До недавне го времени DES считался относительно безопасным алгоритмом шифрования. Существует много способов комбинирования блочных алго ритмов для получения новых более стойких алгоритмов. Одним из таких способов является многократное шифрование — исполь зование блочного алгоритма несколько раз с разными ключами для шифрования одного и того же блока открытого текста. При трехкратном шифровании можно применить три различных ключа. Алгоритм 3-DES (Triple DES — тройной DES) используется в ситуациях, когда надежность алгоритма DES считается недос таточной. Сегодня все шире используются два современных крипто стойких алгоритма шифрования: отечественный стандарт шиф рования ГОСТ 28147—89 и новый криптостандарт США — AES (Advanced Encryption Standard). Стандарт шифрования ГОСТ 28147—89 предназначен для ап паратной и программной реализации, удовлетворяет криптогра фическим требованиям и не накладывает ограничений на сте пень секретности защищаемой информации. Алгоритм шифро вания данных, определяемый ГОСТ 28147—89, представляет собой 64-битовый блочный алгоритм с 256-битовым ключом. Данные, подлежащие зашифрованию, разбивают на 64-раз- рядные блоки. Эти блоки разбиваются на два субблока j V , и N2 по 32 бит (рис. 6.3). Субблок УѴ, обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применя ется логическая операция XOR — «исключающее или»), а затем Рис. 6.3. Схема алгоритма ГОСТ 28147—89 субблоки меняются местами. Данное преобразование выполня ется определенное число раз («раундов») — 16 или 32, в зависи мости от режима работы алгоритма. В каждом раунде выполняются две операции. Первая операция — наложение ключа. Содержимое суббло ка уѴ, складывается по модулю 232 с 32-битовой частью ключа Кх. Полный ключ шифрования представляется в виде конкатенации 32-битовых подключей: К0, К^, К2, К2, К4, К5, К6, К7. В процессе шифрования используется один из этих подключей — в зависи мости от номера раунда и режима работы алгоритма. Вторая операция — табличная замена. После наложения ключа субблок УѴ, разбивается на 8 частей по 4 бит, значение ка ждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый цик лический сдвиг субблока влево на 11 бит. Табличные замены. Блок подстановки 5-box (Substitution box) часто используются в современных алгоритмах шифрования, по этому стоит пояснить, как организуется подобная операция. Блок подстановки 5-Ьох состоит из восьми узлов замены (S-блоков замены) S2, ..., Sg с памятью 64 бит каждый. Посту пающий на блок подстановки S 32-битовый вектор разбивают на 8 последовательно идущих 4-битовых векторов, каждый из кото рых преобразуется в 4-битовый вектор соответствующим узлом замены. Каждый узел замены можно представить в виде табли цы-перестановки 16 4-битовых двоичных чисел в диапазо не 0000... 1111. Входной вектор указывает адрес строки в таблице, а число в этой строке является выходным вектором. Затем 4-би товые выходные векторы последовательно объединяют в 32-би- товый вектор. Узлы замены (таблицы-перестановки) представля ют собой ключевые элементы, которые являются общими для сети ЭВМ и редко изменяются. Эти узлы замены должны сохра няться в секрете. Алгоритм, определяемый ГОСТ 28147—89, предусматривает четыре режима работы: простой замены, гаммирования, гаммиро- вания с обратной связью и генерации имитоприставок. В них ис пользуется одно и то же описанное выше шифрующее преобра зование, но, поскольку назначение режимов различно, осущест вляется это преобразование в каждом из них по-разному. В режиме простой замены для зашифровывания каждого 64-битового блока информации выполняются 32 описанных выше раунда. При этом 32-битовые подключи используются в следующей последовательности: К0, Кх, К2, Кг, К4, К5, К6, К7, Ко, Кх и т. д. — в раундах с 1-го по 24-й; К-,, К6, К5, К4, К3, К2, Ки K q — в раундах с 25-го по 32-й. Расшифровывание в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей: К0, Кх, К2, К2, КЛ, К5, К6, К7 — в раундах с 1-го по 8-й; К7, К6, К5, К4, Къ, Кг, Кх, К0, К7, Кь и т. д. — в раундах с 9-го по 32-й. Все блоки шифруются независимо друг от друга, т. е. резуль тат зашифровывания каждого блока зависит только от его содер жимого (соответствующего блока исходного текста). При нали чии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающе гося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифро вания (очень часто реализуются многоключевые схемы, в кото рых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы — гаммирования и гаммирования с обратной связью. В режиме гаммирования каждый блок открытого текста по битно складывается по модулю 2 с блоком гаммы шифра разме ром 64 бит. Гамма шифра — это специальная последователь ность, которая получается в результате определенных операций с регистрами N x и N2 (рис. 6.9): 1. В регистры N x и N2 записывается их начальное заполне ние — 64-битовая величина, называемая синхропосылкой. 2. Выполняется зашифровывание содержимого регистров Nx и N2 ( в данном случае — синхропосылки) в режиме простой за мены. 3. Содержимое регистра Nx складывается по модулю (232 - 1) с константой С, = 224 + 2'6 + 28 + 24, а результат сложения записы вается в регистр А',. 4. Содержимое регистра N2 складывается по модулю 232 с константой С2 = 224 + 216 + 28 + 1, а результат сложения записыва ется в регистр N2. 5. Содержимое регистров N x и N2 подается на выход в качест ве 64-битового блока гаммы шифра (в данном случае N{ и N2 об разуют первый блок гаммы). Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифровывание или расшифровывание), выполня ется возврат к операции 2. Для расшифровывания гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR. Поскольку эта операция обратима, в случае правильно выработанной гаммы получается исходный текст (табл. 6.1). Таблица 6.1. Зашифровывание и расшифровывание в режиме гаммирования Операция Результат Исходный текст 100100 Гамма XOR 111000 Шифртекст = 011100 Гамма XOR 111000 Исходный текст = 100100 Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же ключ и то же значение синхропосылки, которые приме нялись при зашифровывании информации. В противном случае получить исходный текст из зашифрованного не удастся. В большинстве реализаций алгоритма ГОСТ 28147—89 син хропосылка не секретна, однако есть системы, где синхропосыл ка такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) уве личивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент. В режиме гаммирования с обратной связью для заполнения ре гистров Nx и N2, начиная со 2-го блока, используется не преды дущий блок гаммы, а результат зашифрования предыдущего бло ка открытого текста (рис. 6.4). Первый же блок в данном режиме генерируется полностью аналогично предыдущему. Рассматривая режим генерации имитоприставок, следует оп ределить понятие предмета генерации. Имитоприставка — это криптографическая контрольная сумма, вычисляемая с исполь- 9 - 3 3 4 8 Рис. 6.4. Выработка гаммы шифра в режиме гаммирования с обратной связью зованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выпол няются следующие операции: первый 64-битовый блок массива информации, для которого вычисляется имитоприставка, запи сывается в регистры N\ и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в Nx и УѴ 2. Цикл повторяется до последнего блока информации. Полу чившееся в результате этих преобразований 64-битовое содер жимое регистров N, и N2 или его часть и называется имитопри- ставкой. Размер имитоприставки выбирается, исходя из требуе мой достоверности сообщений: при длине имитоприставки г бит вероятность, что изменение сообщения останется незамечен ным, равна 2'г. Чаще всего используется 32-битовая имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных при меняются другие криптографические методы — в первую оче редь электронная цифровая подпись. При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровывании какой-либо информации и посылается вместе с шифртекстом. После расшифровывания вычисляется новое значение имитоприставки, которое сравнива ется с присланной. Если значения не совпадают, значит шифр- текст был искажен при передаче или при расшифровывании ис пользовались неверные ключи. Особенно полезна имитопри ставка для проверки правильности расшифровывания ключевой информации при использовании многоключевых схем. Алгоритм ГОСТ 28147—89 является очень стойким алгорит мом — в настоящее время для его раскрытия не предложено бо лее эффективных методов, чем упомянутый выше метод «грубой силы». Его высокая стойкость достигается в первую очередь за счет большой длины ключа — 256 бит. При использовании сек ретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет допол нительные биты. Кроме того, криптостойкость зависит от коли чества раундов преобразований, которых по ГОСТ 28147—89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов). Стандарт шифрования AES. В 1997 г. Американский институт стандартизации NIST (National Institute of Standards & Techno logy) объявил конкурс на новый стандарт симметричного крип тоалгоритма, названного AES (Advanced Encryption Standard). К его разработке были подключены самые крупные центры криптологии всего мира. Победитель этого соревнования факти чески становился мировым криптостандартом на ближайшие 10—20 лет. К криптоалгоритмам — кандидатам на новый стандарт AES — были предъявлены следующие требования: • алгоритм должен быть симметричным; • алгоритм должен быть блочным шифром; • алгоритм должен иметь длину блока 128 бит и поддержи вать три длины ключа: 128, 192 и 256 бит. Дополнительно разработчикам криптоалгоритмов рекомен довалось: • использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных ком пьютерах и серверах); • ориентироваться на 32-разрядные процессоры; • не усложнять без необходимости структуру шифра, для того чтобы все заинтересованные стороны были в состоянии са мостоятельно провести независимый криптоанализ алго ритма и убедиться, что в нем не заложено каких-либо недо кументированных возможностей. Итоги конкурса были подведены в октябре 2000 г. — победи телем был объявлен алгоритм Rijndael, разработанный двумя криптографами из Бельгии, Винсентом Риджменом (Vincent Rijmen) и Джоан Даймен (Joan Daemen). Алгоритм Rijndael стал новым стандартом шифрования данных AES [91, 92]. Алгоритм AES не похож на большинство известных алгорит мов симметричного шифрования, структура которых носит на звание «сеть Фейстеля» и аналогична российскому ГОСТ 28147—89. В отличие от отечественного стандарта шифрования, алгоритм AES представляет каждый блок обрабатываемых дан ных в виде двухмерного байтового массива размером 4 x 4 , 4 x 6 или 4 х 8 в зависимости от установленной длины блока (допуска ется использование нескольких фиксированных размеров шиф руемого блока информации). Далее на соответствующих этапах производятся преобразования либо над независимыми столбца ми, либо над независимыми строками, либо вообще над отдель ными байтами. Алгоритм AES состоит из определенного количества раундов (от 10 до 14 — это зависит от размера блока и длины ключа) и выполняет четыре преобразования: BS (ByteSub) — табличная замена каждого байта массива (рис. 6.5); SR (ShiftRow) — сдвиг строк массива (рис. 6.6). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное чис ло байт, зависящее от размера массива. Например, для массива размером 4 x 4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта; МС (MixColumn) — операция над независимыми столбцами массива (рис. 6.7), когда каждый столбец по определенному пра вилу умножается на фиксированную матрицу с(х); АК (AddRoundKey) — добавление ключа. Каждый бит масси ва складывается по модулю 2 с соответствующим битом ключа раунда, который в свою очередь определенным образом вычис ляется из ключа шифрования (рис. 6.8). о о СО а 01 а 02 а оз а іо а 13 с a ij а 20 < * а 23 а зо а 31 а 32 а зз Таблицы замен ^оо ^01 Ь02 Ь0 з Ью Ь2 о ^13 Ь2з L ьѵ ьзо Ь31 см -о ° ^зз Рис. 6.5. Преобразование BS (ByteSub) использует таблицу замен (подстановок) для обработки каждого байта массива State *00 Ьоі Ьо2 *03 *оо * о і *02 *03 Ью *11 Ь« Ьіз К *10 « Ів Ш Ш С ^и г^е в о н а ^б а й хШ ш *20 *21 Ь22 *23 *20 *21 Ьзо ь31 Ь32 *33 ш ш ш т ш *31 *32 Рис. 6.6. Преобразование SR (ShiftRow) циклически сдвигает три последних строки в массиве State аоо а( % >2 аоз а ю а а ѵ М t i l l 2 аіз 0) го о а: ** 2 а 23 азо а 12 азз ® С ( Х ) о о -О *( * 0 / 2 *03 *10 ь . * * : ^ 1 / : 2 *13 *20 2 *23 « 5 ? *30 *: 2 сосо -Q Рис. 6.7. Преобразование МС (MixColumn) поочередно обрабатывает столбцы массива State 0) о о а 01 0) о го а оз а ю а 11 а 12 а 13 а 20 а 21 а 22 а 23 CD ы о а 31 а 32 Ш ы со © ^00 ^01 CN Jc5 k Q3 ^10 ^11 /f12 ^13 ^20 /с21 k 22 k 23 ^30 ^31 k 32 k Z3 *00 *01 *02 *03 *10 *11 *12 *13 *20 *21 *22 *23 *30 *31 *32 *33 Рис. 6.8. Преобразование АК (AddRoundKey) производит сложение XOR каждого столбца массива State со словом из ключевого набора Эти преобразования воздействуют на массив State, который адресуется с помощью указателя 'state'. Преобразование Add RoundKey использует дополнительный указатель для адресации ключа раунда Round Key. Преобразование BS (ByteSub) является нелинейной байтовой подстановкой, которая воздействует независимо на каждый байт массива State, используя таблицу замен (подстановок) 5-Ьох. В каждом раунде (с некоторыми исключениями) над шиф руемыми данными поочередно выполняются перечисленные преобразования (рис. 6.9). Исключения касаются первого и по следнего раундов: перед первым раундом дополнительно выпол няется операция АК, а в последнем раунде отсутствует МС. Рис. 6.9. Раунд алгоритма AES В результате последовательность операций при зашифровы- вании выглядит так: АК, {BS, SR, МС, АК} (повторяется R - 1 раз), BS, SR, АК. Количество раундов шифрования R в алгоритме AES пере менное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров). Расшифровывание выполняется с помощью следующих об ратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровывании). Обратная операция к SR — это циклический сдвиг строк вправо, а не влево. Обратная операция для МС — умножение по тем же правилам на другую матрицу d(x), удовле творяющую условию с(х) d(x) = 1. Добавление ключа АК явля ется обратным самому себе, поскольку в нем используется толь ко операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что ис пользовалась при зашифровании. Все преобразования в шифре AES имеют строгое математи ческое обоснование. Сама структура и последовательность опе раций позволяют выполнять данный алгоритм эффективно как на 8-битных так и на 32-битных процессорах. В структуре алго ритма заложена возможность параллельного исполнения некото рых операций, что может поднять скорость шифрования на мно гопроцессорных рабочих станциях в 4 раза. Алгоритм AES стал новым стандартом шифрования данных благодаря ряду преимуществ перед другими алгоритмами. Преж де всего он обеспечивает высокую скорость шифрования на всех платформах: как при программной, так и при аппаратной реали зации. Кроме того, требования к ресурсам для его работы мини мальны, что важно при его использовании в устройствах, обла дающих ограниченными вычислительными возможностями. Недостатком алгоритма AES можно считать лишь его нетра диционную схему. Дело в том, что свойства алгоритмов, осно ванных на «сети Фейстеля», хорошо исследованы, a AES, в отли чие от них, может содержать скрытые уязвимости, которые мо гут обнаружиться только по прошествии какого-то времени с момента начала его широкого распространения. Для шифрования данных применяются и другие симметрич ные блочные криптоалгоритмы. Основные режимы работы блочного симметричного алгоритма Большинство блочных симметричных криптоалгоритмов не посредственно преобразуют 64-битовый входной открытый текст в 64-битовый выходной шифрованный текст, однако данные редко ограничиваются 64 разрядами. Чтобы воспользоваться блочным симметричным алгоритмом для решения разнообразных криптографических задач, разрабо таны четыре рабочих режима: • электронная кодовая книга ЕСВ (Electronic Code Book); • сцепление блоков шифра СВС (Cipher Block Chaining); • обратная связь по шифртексту CFB (Cipher Feed Back); • обратная связь по выходу OFB (Output Feed Back). Эти рабочие режимы первоначально были разработаны для блочного алгоритма DES, но в любом из этих режимов могут ра ботать и другие блочные криптоалгоритмы. 6.3. Асимметричные криптоалгоритмы Всего за 30 лет асимметричная криптография превратилась в одно из основных направлений криптологии и используется в ИТ так же часто, как и симметричные криптосистемы. 6 .3 .1 . Алгоритм ш иф рования RSA Криптоалгоритм RSA предложили в 1978 г. три автора: Р. Райвест (Rivest), А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Он стал первым алгоритмом с открытым ключом, кото рый может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи [62]. Надежность алгоритма RSA основывается на трудности фак торизации больших чисел и трудности вычисления дискретных логарифмов в конечном поле. В алгоритме RSA открытый ключ Кв, секретный ключ кв, со общение М и криптограмма С принадлежат множеству целых чисел ZN= {0, 1,2, ..., N - 1}, где N — модуль: N=PQ, а Р и Q — случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете. Множество ZN с операциями сложения и умножения по мо дулю N образует арифметику по модулю N. Открытый ключ К в выбирают случайным образом так, чтобы выполнялись условия: 1 < ^ < ф ( Л 0 , НОД (Кв, ф(Л0)=1; Ф(Ю = ( ^ - 1 ) ( 2 - 1 ) , где ф (У У ) — функция Эйлера. Функция Эйлера ф(N ) указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N. Второе из указанных выше условий означает, что открытый ключ Кв и функция Эйлера (p(N) должны быть взаимно простыми. Далее, используя расширенный алгоритм Евклида, вычисля ют секретный ключ кв, такой, что кв - Кв = \ (m ody{N )) или kB = K ; l(mod ( Р - 1)((2- 1)). Это можно осуществить, так как получатель В знает пару простых чисел (Р, Q) и может легко найти Заметим, что кв и N должны быть взаимно простыми. Открытый ключ Кв используют для шифрования данных, а секретный ключ кв — для расшифровывания. Процедура шифрования определяет криптограмму С через пару (Кв, М) в соответствии со следующей формулой: С = E Ki(M) = M K‘ (m odN). В качестве алгоритма быстрого вычисления значения С ис пользуют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N. Расшифровывание криптограммы С выполняют, используя пару (кв, С) по следующей формуле: М= Dki(C) = C k‘ (mod N). Криптоалгоритм RSA всесторонне исследован и признан стойким при достаточной длине ключей. В настоящее время длина ключа — 1024 бита — считается приемлемым вариантом. Некоторые авторы утверждают, что с ростом мощности про цессоров криптоалгоритм RSA потеряет стойкость к атаке пол ного перебора. Однако увеличение мощности процессоров по зволит применить более длинные ключи, что повышает стой кость RSA. В асимметричной криптосистеме RSA количество используе мых ключей связано с количеством абонентов линейной зависи мостью (в системе из N пользователей используются 2N клю чей), а не квадратичной, как в симметричных системах. Следует отметить, что быстродействие RSA существенно ниже быстродействия DES, а программная и аппаратная реали зация криптоалгоритма RSA гораздо сложнее, чем DES. Поэтому криптосистема RSA, как правило, используется при передаче не большого объема сообщений. 6 .3 .2 . Алгоритмы циф ровой подписи Стандарт цифровой подписи ГОСТ Р 34.10—94 — первый оте чественный стандарт цифровой подписи — вступил в действие с начала 1995 г. В нем используются следующие параметры: р — большое простое число длиной 509—512 бит либо 1020—1024 бит; q — простой сомножитель числа (р - 1), имеющий длину 254—256 бит; а — любое число, меньшее (/? — 1), причем такое, что flfrnod р = 1; х — некоторое число, меньшее q\ у= a*mod р. Кроме того, этот алгоритм использует однонаправленную хэш-функцию Н(х). ГОСТ Р 34.11—94 определяет хэш-функцию, основанную на использовании стандартного симметричного ал горитма ГОСТ 28147—89. Первые три параметра — р, q и а — являются открытыми и могут быть общими для всех пользователей сети. Число х — сек ретный ключ, число у — открытый ключ. Чтобы подписать некоторое сообщение т, а затем проверить подпись, выполняются следующие шаги. 1. Пользователь А генерирует случайное число к, причем k 2. Пользователь А вычисляет значения: г - (a*mod/>)mod q\ s= (x- r + k(H(m)))mod q. Если H{m)mod q = 0, то значение #(/«)mod q принимают рав ным единице. Если r= 0, то выбирают другое значение к и начи нают снова. Цифровая подпись представляет собой два числа: г mod 2Ъ6 и s mod 2256. Пользователь А отправляет эти числа пользователю В. 3. Пользователь В проверяет полученную подпись, вычисляя: ѵ = Н{т)чгmod q\ Zi = (s ■ v) mod q; Z 2 = ((q r ) v) mod q; u = ((az> y Zl) m odp) mod q. Если и = г, то подпись считается верной. Различие между этим алгоритмом и алгоритмом DSA заклю чается в том, что в DSA j= • г+ (Н(т))))mod q, что приводит к другому уравнению верификации. Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является стремлением разработчиков отечественно го стандарта к получению более безопасной подписи. Новый отечественный стандарт цифровой подписи ГОСТ Р 34.10—2001 был принят в 2001 г. Его принципиальное отличие от предыдущего ГОСТ Р 34.10—94 состоит в том, что все вычис ления при генерации и проверке ЭЦП в новом алгоритме произ водятся в группе точек эллиптической кривой, определенной над конечным полем FP. Принадлежность точки (пары чисел х и у) к данной группе определяется следующим соотношением: у 2 = х 3 + ах + b mod р, где модуль системы р является простым числом, большим 3, а коэффициенты а и b являются константами, удовлетворяющи ми следующим соотношениям: а<р, Ъ<р\ 4а3 + 27Ь2 * 0 mod р. Дальнейшие математические подробности можно найти в [17, 62]. Следует отметить, что принципы вычислений по данно му алгоритму аналогичны применяемым в ГОСТ Р 34.10—94. Сначала генерируется случайное число х, с его помощью вычис ляется г-частъ ЭЦП, затем вычисляется s-часть ЭЦП из /--части, значения х, значения секретного ключа и хэш-значения подпи сываемых данных. При проверке же подписи аналогичным образом проверяет ся соответствие определенным соотношениям г, s, открытого ключа и хэш-значения информации, подпись которой проверя ется. Подпись считается неверной, если соотношения не соблю даются. В перспективе криптосистемы на основе эллиптических кри вых, вероятно, вытеснят существующие алгоритмы ЭЦП, асим метричного шифрования и выработки ключей парной связи (ключ для шифрования информации между двумя конкретными пользователями вычисляется из секретного ключа отправителя информации и открытого ключа получателя). Алгоритмы на базе эллиптических кривых позволяют заметно сократить время вы числений без потерь криптостойкости или соответственно уве личить уровень защиты при тех же временных затратах. Отечественный стандарт хэширования ГОСТ Р 34.11— 94 Отечественным стандартом генерирования хэш-функции яв ляется алгоритм ГОСТ Р 34.11—94. Этот стандарт является обя зательным для применения в качестве алгоритма хэширования в государственных организациях РФ и ряде коммерческих органи заций. Коротко данный алгоритм хэширования можно описать следующим образом (рис. 6.10) [12]. входных данных Использование блока входных данных в качестве ключей шифрования Рис. 6.10. Хэширование по алгоритму ГОСТ Р 34.11—94 Шаг 1. Инициализация регистра хэш-значения. Если длина сообщения не превышает 256 бит — переход к шагу 3, если пре вышает — переход к шагу 2. Шаг 2. Итеративное вычисление хэш-значения блоков хэши руемых данных по 256 бит с использованием хранящегося в ре гистре хэш-значения предыдущего блока. Вычисление включает в себя следующие действия: • генерацию ключей шифрования на основе блока хэшируе мых данных; • зашифровывание хранящегося в регистре хэш-значения в виде четырех блоков по 64 бита по алгоритму ГОСТ 28147—89 в режиме простой замены; • перемешивание результата. Вычисление производится до тех пор, пока длина необрабо танных входных данных не станет меньше или равной 256 бит. В этом случае — переход к шагу 3. Шаг 3. Дополнение битовыми нулями необработанной час ти сообщения до 256 бит. Вычисление хэш-значения аналогич но шагу 2. В результате в регистре оказывается искомое хэш-значение. |