WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«имени первого Президента России Б. Н. Ельцина Н. Р. Спиричева АЛГОРИТМЫ БЛОЧНОЙ КРИПТОГРАФИИ Рекомендовано методическим советом УрФУ в качестве учебно-методического пособия для ...»

Министерство образования и науки Российской Федерации

Уральский федеральный университет

имени первого Президента России Б. Н. Ельцина

Н. Р. Спиричева

АЛГОРИТМЫ БЛОЧНОЙ КРИПТОГРАФИИ

Рекомендовано методическим советом УрФУ

в качестве учебно-методического пособия для студентов,

обучающихся по программе бакалавриата по направлению

подготовки 230100 «Информатика и вычислительная техника»

Екатеринбург

Издательство Уральского университета

УДК 004.056.55(075.8) ББК 32.973-018.2я73 С72

Рецензенты:

кафедра ОПД ТС УрТИСИ ФГОБУ ВПО «СибГУТИ» (протокол № 3 от 16.11.11 г.; заместитель завкафедрой Н. В. Будылдина);

начальник управления инновационных информационных технологий ГБОУ ВПО УГМА Минздравсоцразвития России Е. М. Подкорытов Научный редактор - проф., д-р техн. наук JI. Г. Доросинский Спиричева, Н. Р .

С72 Алгоритмы блочной криптографии учебно-методическое пособие / Н. Р. Спиричева. - Екатеринбург : Изд-во Урал, ун-та, 2 0 1 3.-7 8, [2] с .

ISBN 978-5-7996-0934-4 Учебно-методическое пособие посвящено описанию наиболее популярных блочных симметричных и асимметричных алгоритмов криптографической защиты информации. Рассмотрены проблемы идентификации и проверки подлинности сообщения. Отдельная глава посвящена функциям хеширования. В приложениях приведены задания к лабораторным работам .

Предназначено для студентов технических специальностей .



Библиогр.: 8 назв. Рис. 28. Табл. 5. Прил. 2 .

УДК 004.056.55(075.8) ББК 32.973-018.2я73 © Уральский федеральный ISBN 978-5-7996-0934-4 университет, 2013

1. БЛОЧНЫЕ ШИФРЫ Клод Шеннон в ряде своих основополагающих работ по теории шифрования сформулировал условия стойкости современного блоч­ ного шифра. Такой шифр должен обладать свойствами перемеши­ вания и рассеивания:

- рассеивание - это свойство шифра, при котором один символ (бит) исходного текста влияет на несколько символов (битов) шифро­ текста, оптимально - на все символы в пределах одного блока. Если данное условие выполняется, то при шифровании двух блоков дан­ ных с минимальными отличиями между ними должны получаться совершенно непохожие друг на друга блоки шифротекста. Точно такая же картина должна иметь место и для зависимости шифро­ текста от ключа: один символ (бит) ключа должен влиять на несколько символов (битов) шифротекста;

- перемешивание - это свойство шифра скрывать зависимости между символами исходного текста и шифротекста. Если шифр достаточно хорошо "перемешивает” биты исходного текста, то соответствующий шифротекст не содержит никаких статистических и тем более функциональных закономерностей для стороннего наблю­ дателя, обладающего лишь ограниченными вычислительными ресур­ сами .

1.1. Общие сведения о блочных шифрах Характерной особенностью блочных криптоалгоритмов является тот факт, что в ходе своей работы они осуществляют преобразование блока входной информации фиксированной длины и получают результирующий блок той же длины, но недоступный для прочтения сторонним лицам, не владеющим ключом. Таким образом, схему работы блочного шифра можно описать функциями Z = EnCrypt(X} Key) и X = DeCrypt(Z} Key) .

Ключ Key является параметром блочного криптоалгоритма и представляет собой некоторый блок двоичной информации фикси­ рованного размера. Исходный X и зашифрованный Z блоки данных также имеют фиксированную разрядность, равную между собой, но необязательно равную длине ключа .



Блочные шифры являются основой, на которой реализованы практически все криптосистемы. Методика создания цепочек из зашифрованных блочными алгоритмами байтов позволяет шифровать ими пакеты информации неограниченной длины. Такое свойство блочных шифров, как быстрота работы, используется асимметрич­ ными криптоалгоритмами, медлительными по своей природе .

Отсутствие статистической корреляции между битами выходного потока блочного шифра важно для вычисления контрольных сумм пакетов данных и для хеширования паролей .

Представленные в табл. 1.1 разработки всемирно признаны стойкими алгоритмами, и публикаций об универсальных методах их взлома в средствах массовой информации на момент создания материала не встречалось .

Таблица 1.1 Характеристики стойких криптоалгоритмов

–  –  –

Криптоалгоритм именуется идеально стойким, если зашифро­ ванный блок данных можно прочесть только перебрав все возможные ключи, пока сообщение не окажется осмысленным. Поскольку по теории вероятности искомый ключ будет найден с вероятностью 1 / 2 после перебора половины всех ключей, постольку на взлом идеально стойкого криптоалгоритма с ключом длиной N потребуется в среднем 2(Л ) проверок. Таким образом, в общем случае стойкость блочного М шифра зависит только от длины ключа и возрастает экспоненциально с ее ростом. Даже предположив, что перебор ключей производится на специально созданной многопроцессорной системе, в которой благо­ даря диагональному параллелизму на проверку 1 ключа уходит только 1 такт, то на взлом 128-битного ключа современной технике потребуется не менее 1021 лет. Естественно, все сказанное относится только к идеально стойким шифрам, которыми, например, являются приведенные в табл. 1. 1 алгоритмы .

Кроме этого условия к идеально стойким криптоалгоритмам применяется еще одно очень важное требование, которому они должны обязательно соответствовать. При известных исходном и зашифрованном значениях блока ключ, которым произведено преобразование, можно узнать также только по полному перебору .

Ситуации, в которых постороннему наблюдателю известна часть исходного текста, встречаются нередко. Это могут быть стандартные надписи в электронных бланках, фиксированные заголовки форматов файлов, регулярно встречающиеся в тексте длинные слова или последовательности байт. В свете данной проблемы описанное выше требование не является ничем чрезмерным и так же строго выполняется стойкими криптоалгоритмами, как и первое .

Таким образом, следующие условия накладываются на функцию стойкого блочного шифра Z = EnCrypt(X, Key):

1) функция EnCrypt должна быть обратимой;

2 ) не должно существовать иных методов прочтения сообщения X по известному блоку Z, кроме как метод полного перебора ключей Key,

3) не должно существовать иных методов определения, каким ключом Key было произведено преобразование известного сообщения X в сообщение Z, кроме как метод полного перебора ключей .





Рассмотрим методы, с помощью которых разработчики блочных криптоалгоритмов добиваются одновременного выполнения этих трех условий с очень большой долей достоверности .

Все действия, производимые над данным блочным крипто­ алгоритмом, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Так, например, 32-битный блок данных можно интерпретировать как число из диапазона 0-4'294'967'295. Кроме того, блок, разрядность которого обычно является "степенью двойки", можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (рассмотренный выше 32-битный блок можно также представить в виде 2 независимых чисел из диапазона 0-65535 или в виде 4 независимых чисел из диапазона 0-255). Над этими числами блочным криптоалгоритмом и производятся по определенной схеме действия, представленные в табл. 1. 2 (первый столбец - условные обозначения данных действий на графических схемах алгоритмов) .

Таблица 1.2 Основные операции в блочных криптоалгоритмах

–  –  –

3) получаемое из независимой части блока (например, Х 2' = X 2+ F ( X x)) .

Последний вариант используется в схеме, названной по имени ее создателя сетью Фейштеля (нем. Feistel) .

Последовательность выполняемых над блоком операций, комби­ нации перечисленных выше вариантов F, сами функции F и составляют ’’ноу-хау" каждого конкретного блочного криптоалго­ ритма .

Характерным признаком блочных алгоритмов является много­ кратное и косвенное использование материала ключа. Это диктуется, в первую очередь, требованием невозможности обратного декоди­ рования в отношении ключа при известных исходном и зашифро­ ванном текстах. Для решения данной задачи в приведенных выше преобразованиях чаще всего используется не само значение ключа или его части, а некоторая, иногда необратимая (небиективная) функция от материала ключа. Более того, в подобных преобразова­ ниях один и тот же блок или элемент ключа используется много­ кратно. Это позволяет при выполнении условия обратимости функции относительно величины X сделать функцию необратимой относительно ключа Key .

Поскольку операция зашифровки или расшифровки отдельного блока в процессе кодирования пакета информации выполняется многократно (иногда до сотен тысяч раз), а значение ключа и, следовательно, функций Vt(Key) остается неизменным, постольку иногда становится целесообразно заранее однократно вычислить дан­ ные значения и хранить их в оперативной памяти совместно с ключом. Так как эти значения зависят только от ключа, то они в криптографии называются материалом ключа. Необходимо отметить, что данная операция никоим образом не изменяет ни длину ключа, ни криптостойкость алгоритма в целом. Здесь происходит лишь опти­ мизация скорости вычислений путем кэширования (англ. caching) промежуточных результатов. Описанные действия встречаются во многих блочных криптоалгоритмах и носят название расширение ключа (англ. key scheduling) .

1.2. Сеть Фейштеля Сеть Фейштеля является дальнейшей модификацией описанного выше метода смешивания текущей части шифруемого блока с результатом некоторой функции, вычисленной от другой незави­ симой части того же блока. Эта методика получила широкое распро­ странение, поскольку обеспечивает выполнение требования о много­ кратном использовании материала ключа и исходного блока информации .

Классическая сеть Фейштеля имеет структуру, представленную на рис. 1.1 .

–  –  –

Независимые потоки информации, появляющиеся из исходного блока, называются ветвями сети. В классической схеме их две .

Величины V, именуются параметрами сети, обычно это функции от материала ключа. Функция F является образующей. Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Фейштеля. Оптимальное число раундов К - 8-32. Важно то, что увеличение количества раундов значительно увеличивает крипто­ стойкость любого блочного шифра к криптоанализу. Возможно, эта особенность и повлияла на столь активное распространение сети Фейштеля - ведь при обнаружении, скажем, какого-либо слабого места в алгоритме почти всегда достаточно увеличить количество раундов на 4-8, не переписывая сам алгоритм. Часто количество раундов не фиксируется разработчиками алгоритма, они лишь указывают разумные пределы (обязательно нижний и не всегда верхний) данного параметра .

Возникает вопрос об обратимости данной схемы. Сеть Фейштеля обладает тем свойством, что даже если в качестве образующей функции F будет использовано необратимое преобра­ зование, то и в таком случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Фейштеля не нужно вычислять функцию F 1 .

Нетрудно заметить, что сеть Фейштеля симметрична. Использо­ вание операции XOR, обратимой своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Фейштеля, но с инверсным порядком параметров Vh Заметим, что для обратимости сети Фейштеля не имеет значение, является ли число раундов четным или нечетным. В большинстве схем, в которых оба вышеперечисленные условия (операция XOR и уничтожение последнего обмена) сохранены, прямое и обратное преобразование производится одной и той же процедурой, которой в качестве параметра передается вектор величин F, либо в исходном, либо в инверсном порядке .

Сеть Фейштеля можно сделать и абсолютно симметричной, то есть выполняющей функции шифрования и дешифрования с помощью одного и того же набора операций. Математическим языком это записывается как "Функция EnCrypt тождественно равна функции DeCrypt". Если мы рассмотрим граф состояний крипто­ алгоритма, на котором точками отмечены блоки входной и выходной информации, то при каком-то фиксированном ключе для класси­ ческой сети Фейштеля мы будем иметь картину, изображенную на рис .

1.2, я, а во втором случае каждая пара точек получит уникальную связь на рис. 1.2, б. Модификация сети Фейштеля, обладающая подобными свойствами, приведена на рис. 1.3. Как видим, основная ее хитрость в повторном использовании данных ключа в обратном порядке во второй половине цикла. Необходимо отметить, что именно из-за этой недостаточно исследованной специфики такой схемы (то есть потенциальной возможности ослабления зашифрован­ ного текста обратными преобразованиями) ее используют в крипто­ алгоритмах с большой осторожностью .

повторить (г-2) раэ повторить (Г-2) рвв В современных алгоритмах обычно применяют модификацию сети Фейштеля для большего числа ветвей. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более битов) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации, обрабатываемые процессорами, на сегодняшний день это байт и двойное машинное слово в 32 бита. Поэтому все чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4 ветвями .

Самый простой принцип ее модификации изображен на рис. 1.4, а .

Для более быстрого перемешивания информации между ветвями (основная проблема сети Фейштеля с большим количеством ветвей) применяется две модифицированные схемы, называемые "type-2" и "type-З". Они изображены на рис. 1.4, б и 1.4, в .

–  –  –

Сеть Фейштеля надежно зарекомендовала себя как крипто­ стойкая схема произведения преобразований, и ее можно найти практически в любом современном блочном шифре. Незначительные модификации касаются обычно дополнительных начальных и конеч­ ных преобразований (англ. - whitening) шифруемого блока. Подобные преобразования, выполняемые обычно также "исключающим ИЛИ" или сложением, имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейштеля, определяется на 95 % функцией F и правилом вычисления V, из ключа. Эти функции и являются объектом исследований специалистов в области криптографии .

1.3. Шифр взбивания. Стандарт DES Система шифрования DES была разработана IBM под именем Lucifer в 1976 году. В ней применялся ключ длиной 56 битов .

В стандарте DES применены перестановки специального вида, что и наводило на мысль об известных Агентству национальной безопас­ ности США (АНБ) слабых местах системы. Однако принцип этого шифрования прошел самую широкую апробацию. Нарекания вызы­ вали лишь выбранные длины блока в 64 бита и ключа в 56 битов, что недостаточно для задач национальной безопасности. Свое развитие DES получил в ГОСТ 28147-89, который увеличил длину ключа до 256 битов и допустил произвольные перестановки .

С увеличением числа взбиваний порча единственного бита в шифровке делает нечитаемой половину текста, что обусловлено побайтовой перестановкой. Если бы перестановка была побитовой, то из-за ошибки в единственном бите весь текст перестал бы читаться .

Шифр DES принят федеральным стандартом США. Он хорош для многих коммерческих приложений, но недостаточно стоек к атакам аналитиков. Например, 16-кратный DES был взломан А. Шамиром с помощью дифференциального криптоанализа и М. Матсуи с помощью линейного криптоанализа. Серьезную практи­ ческую атаку на DES осуществил Мишель Винер. Все вышесказанное означает, что DES нельзя использовать для серьезных приложений .

Для исправления такого положения некоторые коммерсанты исполь­ зуют так называемый "тройной DES", шифруя сообщение трижды двумя различными ключами. Это увеличивает реальную длину ключа до 112 битов, но такой метод медленнее обычного DES в три раза .

Схемы алгоритма DES см. на рис. 1.5-1.7 и в матрицах на с. 13-17 .

–  –  –

Эти восемь блоков путем копирования крайних элементов преобразуются в восемь блоков из шести символов:

*/.4 */,? */.3 */,1 *-,31 * /.0

–  –  –

Матрица начальной перестановки IP Матрица обратной перестановки IP'1 Пример того, как соотносятся элементы первой строки матрицы IP'1 элементами матрицы IP приведен ниже .

–  –  –

Шаг 2. На /-й циклической итерации 48 разрядов ключа (klfi, кц,, 4 7 ) поразрядно суммируются (по модулю 2 ) с полученными выше 48 разрядами данных .

Шаг 3. На вход блока подстановки (S'-бокс) подается j -й блок из шести символов ( 0 у 8 ), S[/] имеет шестиразрядный вход и четырехразрядный выход и представляет собой четыре преобразо­ вания из Z2,4 в Z24; два крайних разряда входного блока служат для выборки одного из этих преобразований. Каждая из восьми подстано­ вок 5[0], 5X1], 5X7] осуществляется с использованием четырех строк и 16 столбцов матрицы с элементами (0, 1, 15}. Каждый из массивов размерностью 4x16 определяет подстановку на множестве Z2 4 следующим образом. Если входом является блок из шести символов (z0, Z], z2, zj, z4, z 5), то две крайние позиции (z0, z5) интерпретируются как двоичное представление целых чисел из набора {0, 1, 2,3} .

Эти целые определяют номер строки (0-3). Оставшиеся четыре символа (zb z2, z3, z4) интерпретируются как двоичное представление целых чисел из набора {0, 1,..., 15} и служат для определения столбца в массиве (0-15). Таким образом, входной блок (0, 0,1,0,1, 1) соответствует строке 1 и столбцу 5 .

Шаг 4. Составляющие выход 5-бокса 32 разряда подаются на вход блока проволочной коммутации (Р-бокс) .

Шаг 5. Компоненты правого входного 32-разрядного блока X, преобразованного в Д Х ), поразрядно суммируются по модулю 2 с компонентами левого входного 32-разрядного блока X .

На каждой итерации используется 48-разрядный ключ (ki0, kl U к, 47). Поскольку входным ключом DES является 56-разрядный блок к = (kjfi, кц,..., Л,55), то каждый его разряд используется многократно .

Какой именно из ключей используется на /-й циклической итерации, определяется списком ключей. Для описания списка ключей введены дополнительные элементы .

Ключ определяется по следующему алгоритму:

- производится начальная перестановка РС-1 ключа 56-разрядного ключа пользователя к = (Л,0, кц,..., к ц 5). Получаемый в результате 56-разрядный блок рассматривается как два 28-разрядных блока - левый С0 и правый 0;

- производится левый циклический сдвиг блоков Со и D0 s[l] раз для получения блоков С] и Д ;

- из сцепления блоков (Си D\) выбираются 48 разрядов с помощью перестановки PC-2. Эти разряды используются на первой итерации;

- используемые на /-й циклической итерации разряды ключа определяются методом индукции. Для получения блоков С/ и Д нужно произвести левый циклический сдвиг ф '] раз блоков С,_1 и Д_, .

Инверсией DES (обеспечивающей расшифровывание зашифро­ ванных посредством DES данных) является D E S '1=1РЛ х лл х я* х... х п * х л Пб х IPРасшифровывание зашифрованного посредством DES текста осуществляется с использованием тех же блоков благодаря обрати­ мости преобразования .

Таков общий алгоритм DES. Проанализируем его эффектив­ ность .

1.3.2. Анализ эффективности алгоритма Поскольку длина блоков исходного текста равна 64, постольку поддержка каталогов частот использования блоков является для злоумышленника задачей, выходящей за пределы современных технических возможностей .

Однако алгоритм DES, являясь первым опытом стандарта шифрования, имеет ряд недостатков. За время, прошедшее после создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки постоянно снижается. В 1998 году была построена машина стои­ мостью около 100 О О долларов, способная по занной паре И с х о д ­ О ный текст, шифрованный текст восстановить ключ за среднее время в 3 суток. Таким образом, DES при его использовании стандартным образом, уже стал далеко не оптимальным выбором для удовлет­ ворения требованиям скрытности данных .

Было выдвинуто большое количество предложений по усовер­ шенствованию DES, которые отчасти компенсируют указанные недостатки. Мы рассмотрим два из них .

Наиболее широко известным предложением по усилению DES является так называемый "тройной DES", один из алгоритмов которого определяется формулой E D E \mki (х) = DESkз [ D E V 1 (DEStl (х))], то есть ключ для EDE3 имеет длину 56 • 3 = 168 битов, шифрование 64-битового блока осуществляется шифрованием с одним подклю­ чом, расшифовыванием с другим и затем шифрованием с третьим .

(Причина, по которой вторым шагом является DESk{ Y а не DESk2,, является обратимость DES: если выбрать К = к, к, к, то EDE3K = DESk .

Причина использования DES три раза вместо двух заключается в существовании атаки "встреча в середине" на двойной DES.) Недостаток тройного DES состоит в том, что он гораздо медленнее, чем сам DES: его скорость составляет ровно одну треть исходной. При использовании EDEэ в режиме сцепления блоков это замедление скажется как на аппаратном, так и на программном уровне (даже если попытаться компенсировать его дополнительной аппаратной частью). Во многих случаях такое падение производи­ тельности неприемлемо .

В 1984 году Рон Ривест предложил расширение DES, которое назвали DESX (DES extended), свободное от недостатков тройного DES .

D E SX определяется как DESki и, и = к2 Ф DESk {к\ ф х) .

то есть ключ DESX К = к, кь кг состоит из 54 + 64 + 64 = 184 битов и включает в себя три различных подключа: ключ "DES" к, предвари­ тельный "зашумляющий" ключ к\ и завершающий "зашумляющий" ключ к2 .

Для шифрования блока сообщения мы складываем его поразрядно по модулю 2 с к\, шифруем его алгоритмом DES с ключом к и вновь поразрядно складываем его по модулю 2 с к2 .

Таким образом, затраты D ESX на шифрование блока всего на две операции сложения по модулю 2 больше, чем затраты исходного алгоритма .

В отношении DESX замечательно то, что две операции "исключающее ИЛИ" делают шифр гораздо менее уязвимым по отношению к перебору ключей. Кроме того, DESX затрудняет получение даже одной пары х„ DESX/feip- в том случае, когда злоумышленник организует атаку на шифр по выбранному исход­ ному тексту, получая множество пар Рр D E S ^ P ^ .

DESX предназначался для увеличения защищенности DES от перебора ключей и сохранения его стойкости к другим возможным атакам. Однако D ESX в действительности также увеличивает стой­ кость против дифференциального и линейного криптоанализа, увели­ чивая требуемое количество проб с выбранным исходным текстом до величины, превышающей 26.

Дальнейшее увеличение стойкости против этих атак может быть достигнуто заменой в DESX операции "исключающее ИЛИ" на сложение DES - РЕР* * 2 = к2 + DESk (кх + х), где сложение определяется следующим образом:

L.R + L'.R' = (L oL).(R oR), |1|= |Л |= |11= |Л '|= 32 .

Здесь о обозначает сложение по модулю 232 .

Описанное выше не означает, что невозможно построить машину, раскрывающую D E SX за приемлемое время. Но оно подразу­ мевает, что такая машина должна использовать какую-либо ради­ кально новую идею. Это не может быть машина, реализующая перебор ключей в общепринятом смысле .

Таким образом, практически во всех отношениях DESX оказы­ вается лучше DES. Данный алгоритм прост, совместим с DES, эффек­ тивно реализуем аппаратно, может использовать существующее аппаратное обеспечение DES и увеличивает стойкость к атакам, основанным на переборе ключей. Однако употребляется лишь похожий на DES алгоритм IDEA - Improved Proposed Encryption Standard - улучшенный стандарт шифрования. Он отличается длиной ключа в 128 битов и смещением операций разных алгебраических групп для блоков длиной 64 бита. Алгоритм IDEA разработан в Цюрихе Джеймсом Мэсси и опубли-кован в 1990 году. В отличие от алгоритмов FEAL, REDOC-II, LOKI, он выдержал множество атак криптографов Англии, Германии, Израиля. Этот алгоритм считается более стойким, чем традиционный DES .



1.4. Отечественный стандарт шифрования данных В нашей стране установлен единый алгоритм криптографи­ ческого преобразования данных для систем обработки информации в сетях ЭВМ, в отдельных вычислительных комплексах и ЭВМ, который определяется ГОСТ 28147-89. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптогра­ фическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах и ЭВМ .

Этот алгоритм криптографического преобразования данных предназначен для аппаратной и программной реализации, удовлет­ воряет криптографическим требованиям и не накладывает ограниче­ ний на степень секретности защищаемой информации. Алгоритм шифрования данных представляет собой 64-битовый блочный алго­ ритм с 256-битовым ключом .

При описании алгоритма используются следующие обозначе­ ния: L и R - последовательности битов; LR - конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L; © - операция побитового сложения по модулю 2 ; * - операция сложения по модулю 2 3 2 двух 32-разрядных двоичных чисел; * ' - операция сложения двух 32-разрядных чисел по модулю |2 3 2 - 1 | .

Два целых числа а, Ь, где 0 a, b 2 3 1 - 1, а = (а32, а 31, аъ а х), Ь = (Ь32, b3i,..., b2, 6,),представленные в двоичном виде, то есть a= + а}1 •2 30 +... + *2 *+ йр b ~ b}2' 23 + | *2Э +...

+ -21+ 6р суммируются по модулю 2 3 2 (операция *) по следующему правилу:

а * b = а + Ь, если а + Ь 2, a * b = a + b - 2 32, если а + b 2 32 .

Правила суммирования чисел по модулю |232- 1|:

а * ’Ъ = а + Ь, если а + b 2 3 2 - 1, а * ’ b = а + b - 2 32, если а + b 2 32- 1 .

Алгоритм предусматривает четыре режима работы:

- шифрование данных в режиме простой замены;

- то же в режиме гаммирования;

- гаммирования с обратной связью;

- выработка имитовставки .

–  –  –

1 4г-номер_ разряда _N\ Аналогично данному расшифровываются остальные блоки зашифрованных данных .

Если алгоритм шифровки в режиме простой замены 64-битового блока Т0 обозначить через А, то А(Т0) = А [ а ф 1 Ь(0)] = [*(32), *(32)]= Гш .

Следует иметь в виду, что режим простой замены допустимо использовать для шифрования данных только в редких случаях - при выработке ключа и зашифровывании его с обеспечением имитозащиты для передачи по каналам связи или для хранения в памяти ЭВМ .

–  –  –

Стойкость режима СВС равна стойкости блочного шифра, лежа­ щего в его основе. Кроме того, структура исходного текста скрыва­ ется за счет сложения предыдущего блока шифрованного текста с очередным блоком открытого текста. Стойкость шифрованного текста увеличивается, поскольку становится невозможной прямая манипуляция исходным текстом, кроме как путем удаления блоков из начала или конца шифрованного текста .

Скорость шифрования равна скорости работы блочного шифра, но простого способа распараллеливания процесса шифрования не существует, хотя расшифровывание может проводиться параллельно .

В режиме обратной связи по шифрованному тексту (CFB) предыдущий блок шифрованного текста шифруется еще раз, и для получения очередного блока шифрованного текста результат склады­ вается поразрядно по модулю 2 с блоком исходного текста. Для начала процесса шифрования также используется начальный вектор (см. рис. 1.1 2 ) .

Стойкость режима CFB равна стойкости блочного шифра, лежащего в его основе, и структура исходного текста скрывается за счет использования операции сложения по модулю 2. Манипули­ рование исходным текстом путем удаления блоков из начала или конца шифрованного текста становится невозможным. Если в режиме CFB два блока шифрованного текста идентичны друг другу, то результаты их шифрования на следующем шаге также будут иден­ тичны, что создает возможность утечки информации об исходном тексте .

Скорость шифрования равна скорости работы блочного шифра, и простого способа распараллеливания процесса шифрования не существует. Этот режим в точности соответствует режиму гаммиро­ вания с обратной связью алгоритма ГОСТ 28147-89 .

–  –  –

Рис. 1.12. Режим обратной связи по шифрованному тексту Режим обратной связи по выходу (OFB) подобен режиму CFB за исключением того, что величины, складываемые по модулю 2 с бло­ ками исходного текста, генерируются независимо от исходного или шифрованного текста (см. рис. 1.13). Для начала процесса шифро­ вания также используется начальный вектор. Режим OFB обладает следующим преимуществом перед режимом CFB любые битовые ошибки, возникшие в процессе передачи, не влияют на расшифро­ вывание последующих блоков. Однако возможна простая манипу­ ляция исходным текстом путем изменения шифрованного текста .

Хотя в этом случае простого способа распараллеливания процесса шифрования также не существует, время можно сэкономить, выработав ключевую последовательность заранее .

–  –  –

2. НОВЫЙ КРИПТОСТАНДАРТ

БЛОЧНОГО ШИФРОВАНИЯ США

2.1. Общие сведения о конкурсе AES В 80-х годах XX века в США был принят стандарт симметричного криптоалгоритма для внутреннего применения DES (Data Encryption Standard), который получил достаточно широкое распространение. Однако этот стандарт полностью неприемлем для использования по двум причинам:

1) длина его ключа составляет 56 битов, что чрезвычайно мало на современном этапе развития ЭВМ;

2 ) при разработке алгоритм был ориентирован на аппаратную реализацию, то есть содержал операции, выполняемые на микро­ процессорах за неприемлимо большое время (такие как перестановка битов внутри машинного слова по определенной схеме) .

В связи с этим Американский институт стандартизации N IST National Institute o f Standards & Technology - принял решение об объявление в 1997 году конкурса на новый стандарт симметричного криптоалгоритма. Были учтены основные недостатки шифрапредшественника и к разработке привлечены самые крупные центры по криптологии со всего мира. Тем самым победитель этого кон­ курса, названного AES - Advanced Encryption Standard, станет факти­ чески мировым криптостандартом на ближайшие 1 0 - 2 0 лет .

Требования, предъявленные к алгоритмам-кандидитам на AES в 1998 году, были предельно просты:

1 ) алгоритм должен быть симметричным;

–  –  –

3) иметь длину блока 128 битов;

4) поддерживать три длины ключа - 128, 192 и 256 битов .

Дополнительно к этим требованиям кандидатам рекомендо­ валось:

1 ) использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);

2) ориентироваться на 32-разрядные процессоры;

3) не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии само­ стоятельно провести независимый криптоанализ алгоритма и убедиться в том, что в нем не заложено каких-либо незадокументированных возможностей .

На первом этапе в оргкомитет соревнования поступило 15 заявок из совершенно разных уголков мира. В течение 2 лет специалисты комитета, исследуя самостоятельно, а также изучая публикации других исследователей, выбрали 5 лучших. Алгоритмыфиналисты приведены в табл. 2. 1 .

Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа .

О своем выборе NIST объявил 2 октября 2000 года победителем конкурса стал бельгийский алгоритм RIJNDAEL .

С этого момента с алгоритма-победителя сняты все патентные ограничения - его можно будет использовать в любой криптопрограмме без отчисления каких-либо средств создателю .

Рассмотрим основные (рабочие) части алгоритмов победителей первого этапа .

Таблица 2.1 Алгоритмы-финалисты конкурса NIST

–  –  –

2.1.1. Шифр MARS Шифр состоит из трех видов операций, которые повторяются сначала в прямом, а затем в инверсном порядке. На первом шаге идет классическое входное забеливание: ко всем байтам исходного текста добавляются байты из материала ключа .

Второй ш а г - прямое перемешивание - однотипная операция, имеющая структуру сети Фейштеля, повторяется 8 раз. Однако на этом шаге не производится добавление материала ключа. Цель данного преобразования - тщательная рандомизация данных и повышение стойкости шифра к некоторым видам атак (рис. 2.1 ) .

Третий шаг - собственно шифрование. В нем используется сеть Фейштеля третьего типа с 4 ветвями, то есть значения трех функций, вычисленных от одной ветви, накладываются соответственно на три других, затем идет перестановка слов. Эта операция также повторя­ ется 8 раз. Именно на третьем этапе происходит смешивание текста с основной (большей) частью материала ключа. Сами функции, накладываемые на ветви, изображены на рис. 2.2. Таким образом, в алгоритме MARS использованы практически все виды операций, применяемых в криптографических преобразованиях: сложение, "исключающее ИЛИ", сдвиг на фиксированное число битов, сдвиг на переменное число битов, умножение и табличные подстановки .

Во второй части операции шифрования повторяются, но в обратном порядке: сначала шифрование, затем перемешивание и, наконец, забеливание. При этом во вторые варианты всех операций внесены некоторые изменения таким образом, чтобы криптоалгоритм в целом стал абсолютно симметричным, то есть в алгоритме MARS для любого X выполняется выражение EnCrypt[EnCrypt(X)J = X обратное шифрование (8 раундов) обратное перемешивание (8 раундов) выходное забеливание ЕО Е1 Е2 ЕЗ

–  –  –

2.1.3. Шифр Serpent Алгоритм разработан группой ученых из нескольких исследова­ тельских центров мира. Алгоритм представляет собой сеть Фейштеля для четырех ветвей смешанного типа: 2 четные ветви все вместе изменяют значения нечетных, затем меняются местами. В качестве криптопреобразований используются только исключающее "ИЛИ", табличные подстановки и битовые сдвиги. Алгоритм состоит из 32 раундов. Сами раунды составлены таким образом, что добавление к ветвями материала ключа на первом и последнем раундах образует входное и выходное забеливание (рис. 2.4) .

повтор (г-1)раз

–  –  –

2.1.4. Шифр TwoFish Алгоритм разработан команией Counterpain Security Systems, возглавляемой Брюсом Шнайером (англ. Bruce Schneier) .

Предыдущая программная разработка этой фирмы, называвшаяся BlowFish, являлась и до сих пор является признанным криптостойким алгоритмом .

В алгоритме TwoFish разработчики оставили некоторые удачные решения из проекта-предшественника, кроме этого произвели тщательные исследования по перемешиванию данных в сети Фейштеля. Алгоритм представляет собой сеть Фейштеля смешанного типа (рис. 2.5): первая и вторая ветвь на нечетных раундах производят модификацию третьей и четвертой, на четных раундах ситуация меняется на противоположную. В алгоритме используется криптопреобразование Адамара (англ. Pseudo-Hadamar Transform) - обрати­ мое арифметическое сложение первого потока со вторым, а затем второго с первым .

Рис. 2.5. TwoFish Единственным нарицанием, поступившим в адрес TwoFish от независимых исследователей, является тот факт, что при расширении материала ключа в алгоритме используется сам же алгоритм. Двойное применение блочного шифра довольно сильно усложняет его анализ на предмет наличия слабых ключей или незадокументированных замаскированных связей между входными и выходными данными .

–  –  –

3.1. Концепция криптосистемы с открытым ключом Эффективными системами криптографической защиты данных являются асимметричные криптосистемы, называемые также крипто­ системами с открытым ключом. В таких системах для зашифровывания данных используется один ключ, а для расшифровывания другой (отсюда и название —асимметричные). Первый ключ является открытым и может быть опубликован и использован всеми пользова­ телями системы, которые зашифровывают данные. Расшифровывание данных с помощью открытого ключа невозможно .

Для расшифровывания данных получатель зашифрованной информации использует второй ключ, который является секретным .

Разумеется, ключ расшифровывания не может быть определен из ключа зашифровывания .

Обобщенная схема асимметричной криптосистемы с открытым ключом показана на рис. 3.1. В этой криптосистеме применяют два различных ключа: Кв - открытый ключ получателя Я, которым будет шифровать отправитель А; кв — секретный ключ получателя В .

Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ Кв по незащищенному каналу). Значения ключей Кв и кв зависят от начального состояния генератора ключей .

Рис. 3.1. Обобщенная схем а асимметричной криптосистемы с открытым ключом Раскрытие секретного ключа кв по известному открытому ключу Кв должно быть вычислительно неразрешимой задачей .

Характерные особенности асимметричных криптосистем таковы: открытый ключ К в и криптограмма С могут быть отправлены по незащищенным каналам, таким образом, противнику известны Кв и С; алгоритмы шифрования и расшифровывания (Ев: М — С, DB: С — М) являются открытыми .

»

Защита информации в асимметричной криптосистеме основана на секретности ключа Кв .

Выполнение следующих требований, сформулированных У. Диффи и М.

Хеллман, обеспечивает безопасность асимметричной криптосистемы:

1) вычисление пары ключей (Кв, кв) получателем В на основе начального условия должно быть простым;

2) отправитель А, зная открытый ключ Кв и сообщение М, может легко вычислить криптограмму

С = Ет (М) = Е ^М ) :

3) получатель В, используя секретный ключ кв и криптограмму С, может легко восстановить исходное сообщение М = D uiC ) = Ds(C) = DB[ E m \ \

4) противник, зная открытый ключ Кв, при попытке вычислить секретный ключ кв наталкивается на непреодолимую проблему;

5) противник, зная пару (Кв, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую проблему .

3.2. Однонаправленные функции Концепция асимметричных криптографических систем с откры­ тым ключом основывается на применении однонаправленных функ­ ций. Неформально однонаправленную функцию можно определить следующим образом .

Пусть Х н Y - некоторые произвольные множества. Функция f: X —* Y является однонаправленной, если для всех х е X можно легко вычислить функцию y = f( x ),y * Y .

В то же время для большинства y e Y достаточно сложно получить значение х е Х, такое, что f(x) - у (при этом полагают, что существует по крайней мере одно такое значение х) .

Основным критерием отнесения функции / к классу однонаправ­ ленных функций является отсутствие эффективных алгоритмов обратного преобразования Y —*X .

В качестве примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача - вычисление произведе­ ния двух очень больших целых чисел Р и Q, то есть нахождение значения N = PQ, является относительно несложной задачей для ЭВМ .

Обратная задача — разложение на множители большого целого числа, то есть нахождение делителей Р и Q большого целого числа N = PQ, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N ~ 2 Ш и Р ~ Q для разложения числа N потребуется около 1 0 2 3 операций, то есть задача практически неразрешима на современ­ ных ЭВМ .

Следующий характерный пример однонаправленной функции это модульная экспонента с фиксированными основанием и модулем .

Пусть А и N - целые числа, такие, что 1 А N.

Определим множество ZN:

Z * = { 0,1,2,...,Л М } .

Тогда модульная экспонента с основанием А по модулю N представ­ ляет собой функцию I a,n : Zn —*Zn, Г лА х) = Л х 1 Л0, где х - целое число, 1 х N - 1 .

Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции/) ^ (х). Если у = Ах, то естес­ твенно записать х = log^(y). Поэтому задачу обращения функ­ ции / а,ь ) называют задачей нахождения дискретного логарифма, А или задачей дискретного логарифмирования .

Задача дискретного логарифмирования формулируется следую­ щим образом. Для известных целых A, N, у найти целое число х, такое, что Лд(гшх1 N) - у .

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

По современным оценкам теории чисел, при целых числах А ~ 2664 и N ~ 2Ш решение задачи дискретного логарифмирования (нахождение показателя степени х для известного у) потребует около Коопераций, то есть эта задача имеет в 1 0 3 раз большую вычисли­ тельную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрас­ тает .

Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма вычисления дискретного лога­ рифма за приемлемое время. Исходя из этого модульная экспонента отнесена к однонаправленным функциям условно, что не мешает с успехом применять ее на практике .

Важным классом функций, используемых при построении криптосистем с открытым ключом, являются так называемые одно­ направленные функции с "потайным ходом" (с лазейкой). Дадим определение такой функции. Функция f:X -+ Y относится к классу однонаправленных функций с "потайным ходом" в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен "потайной ход" (секретное число, строка или другая информация, ассоциирующаяся с данной функцией) .

В качестве примера однонаправленной функции с "потайным ходом" можно указать используемую в криптосистеме RSA модуль­ ную экспоненту с фиксированными модулем и показателем степени .

Переменное основание модульной экспоненты используется для указания числового значения сообщения M либо криптограммы С .

–  –  –

Действия пользователя^:

1 ) представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0-32. Пусть буква А представляется как число 1, буква В - как число 2, буква С - как число 3. Тогда сообще­ ние САВ можно представить как последовательность чисел 312, то есть М\ = 3,М 2 = 1, А/з = 2;

2 ) шифрует текст, представленный в виде последовательности

–  –  –

3.3.2. Безопасность и быстродействие криптосистемы RSA Безопасность алгоритма RSA базируется на трудности решения задачи факторизации больших чисел, являющихся произведениями двух больших простых чисел. Действительно, криптостойкость алго­ ритма RSA определяется тем, что после формирования секретного ключа кв и открытого ключа Кв "стираются" значения простых чисел Р и Q, и тогда исключительно трудно определить секретный ключ кв по открытому ключу Кв, поскольку для этого необходимо решить задачу нахождения делителей P a Q модуля N .

Разложение величины N на простые множители Р и Q позволяет вычислить функцию ф (N) - (Р - 1)(0 - 1) и затем определить секретное значение кв, используя уравнение Кв кв = l[mod ф (N)] .

Другим возможным способом атаки на алгоритм RSA является непосредственное вычисление или подбор значения функции Ф(Л0 = (Р - 1X0 - 1)- Если установлено значение ф (N), то сомножители Р и 0 вычисляются достаточно просто.

В самом деле, пусть x = P + Q = N -1 - d (N ), у = ( Р - 0 ) 2 = (Р + 0 Г - 4 К Зная (N ), можно определить х и затем у ; зная х а у, можно р определить числа Р и 0 из следующих соотношений:

= \ ( * + 4 у ), е = \ ( х - ^ ) .

р Однако данная атака не проще задачи факторизации модуля N .

Задача факторизации является трудноразрешимой задачей для боль­ ших значений модуля N .

Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа Р и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р. Райвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного вре­ мени. Однако этот прогноз не оправдался из-за сравнительно быстрого развития компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации .

Была сделана попытка расчета оценок безопасных длин ключей асимметричных криптосистем на ближайшие 2 0 лет на основе прогноза развития компьютеров и их вычислительной мощности, а также возможного совершенствования алгоритмов факторизации. Эти оценки (табл. 3.1) даны для трех групп пользователей (индивидуаль­ ные пользователи, корпорации и государственные организации) в соответствии с различием требований к их информационной безопас­ ности. Конечно, данные оценки следует рассматривать как сугубо приблизительные, как возможную тенденцию изменения безопасной длины ключей асимметричных криптосистем со временем .

Таблица 3.1 Оценка длин ключей для асимметричных криптосистем, биты

–  –  –

1536 Т 2048 [2015 У’ Г.... 2048 Криптосистемы RSA реализуются как аппаратным, так и программным путем .

Для аппаратной реализации операций зашифровывания и расшифровывания RSA разработаны специальные процессоры. Эти процессоры, реализованные на сверхбольших интегральных схемах (СБИС), позволяют выполнять операции RSA, связанные с возведе­ нием больших чисел в колоссально большую степень по модулю N, за относительно короткое время. И все же аппаратная реализация RSA примерно в 1 0 0 0 раз медленнее аппаратной реализации симметрич­ ного криптоалгоритма DES .

Одна из самых быстрых аппаратных реализации RSA с модулем 512 битов на сверхбольшой интегральной схеме имеет быстро­ действие 64 Кбит/с. Лучшими из серийно выпускаемых СБИС являются процессоры фирмы CYLINK, выполняющие 1024-битовое шифрование RSA .

Программная реализация RSA примерно в 100 раз медленнее программной реализации DES. С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема RSA никогда не достигнет быстродействия симметричных криптосистем .

Следует отметить, что малое быстродействие криптосистем RSA ограничивает область их применения, но не перечеркивает их ценность .

3.4. Схема шифрования Полига-Хеллмана Схема шифрования Полига-Хеллмана сходна со схемой шифрования RSA. Она запатентована в США и Канаде. Схема представляет собой несимметричный алгоритм, поскольку исполь­ зуются различные ключи для шифрования и расшифровывания .

Однако эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифровывания легко выво­ дятся один из другого. Оба ключа (шифрования и расшифровывания) нужно держать в секрете .

Аналогично схеме RSA криптограмма С и открытый текст Р определяются из соотношений:

С = Ре mod п, Р = С 1 mod п, где ed = 1 (по модулю некоторого составного числа) .

В отличие от алгоритма RSA, в этой схеме число п не определяется через два больших простых числа; число и должно оставаться частью секретного ключа. Если кто-либо узнает значения е и и, он сможет вычислить значение d .

Не зная значений е или d, противник будет вынужден вычислять значение е = log р С (mod и), что является трудной задачей .

3.5. Схема шифрования Эль Гамаля Схема Эль Гамаля, предложенная в 1985 году, может быть использована как для шифрования, так и для цифровых подписей .

Безопасность схемы Эль Гамаля обусловлена сложностью вычисле­ ния дискретных логарифмов в конечном поле .

Для того чтобы генерировать пару ключей (открытый ключ секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G Р. Числа Р и G могут быть распространены среди группы пользователей. Затем выбирают случайное целое число X, причем Х Р. Число X является секретным ключом и должно храниться в секрете. Далее вычисляют Y= G* mod Р. Число Y является открытым ключом .

Для того чтобы зашифровать сообщение М, выбирают случай­ ное целое число К, 1 К (Р - 1), такое, что числа К и (Р - 1) являются взаимно простыми. Затем вычисляют значения а = G*modP, b = YK M m od P .

Пара чисел (а, Ь) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М .

Для того чтобы расшифровывать шифртекст (а, Ь), вычисляют М = W m o d Р. (3.5) Поскольку Ь/с? YKМ/с? G ^M /G ™ М (mod Р), то соотношение (3.5) справедливо .

Пример. Выберем Р = 11, G = 2, секретный ключ X = 8 .

Вычислим У = (j^ m o d Р = 28mod 11 = 256 mod 11 = 3 .

Итак, открытый ключ Y= 3 .

Пусть сообщение М = 5. Выберем некоторое случайное число К = 9. Убедимся, чтоН О Д ( К,Р - 1)= 1. Действительно, Н О Д(9,10) = 1 .

Вычислим пару чисел а и Ь:

а = GxmodP = 29 mod 11 = 512 mod 11 = 6 .

b = YxMmodP = 39 mod 11 = 196 835 mod 11 = 9 .

Получим шифртекст (a, b) = (6,9) .

Выполним расшифровывание этого шифртекста.

Вычисляем сообщение М, используя секретный ключ X:

М = bh/m odP = 9/Z»8modl 1 .

Выражение М = 9/6*modl 1 можно представить в виде b*M9 mod 1 1, или 1 679 616 М 9 mod 11 .

Решая данное выражение, находим М = 5 .

В реальных схемах шифрования необходимо использовать в качестве модуля Р большое целое простое число, имеющее в двоич­ ном представлении длину 5121-1024 битов .

3.6. Комбинированный метод шифрования Главным достоинством криптосистем с открытым ключом явля­ ется их потенциально высокая безопасность: нет необходимости ни передавать, ни сообщать кому бы то ни было значения секретных ключей, ни убеждаться в их подлинности. В симметричных крипто­ системах существует опасность раскрытия секретного ключа во время передачи .

Однако алгоритмы, лежащие в основе криптосистем с открытым ключом, имеют следующие недостатки:

1 ) генерация новых секретных и открытых ключей основана на генерации новых больших простых чисел, а проверка простоты чисел занимает много процессорного времени;

2 ) процедуры шифрования и расшифровывания, связанные с возведением в степень многозначного числа, достаточно громоздки .

Из-за данных недостатков быстродействие криптосистем с открытым ключом обычно в сотни и более раз меньше быстро­ действия симметричных криптосистем с секретным ключом .

Комбинированный (гибридный) метод шифрования позволяет сочетать преимущества высокой секретности, предоставляемые асимметричными криптосистемами с открытым ключом, с преиму­ ществами высокой скорости работы, присущими симметричным криптосистемам с секретным ключом. При таком подходе крипто­ система с открытым ключом применяется для шифрования, передачи и последующего расшифровывания только секретного ключа симмет­ ричной криптосистемы. Симметричная же криптосистема применя­ ется для шифрования и передачи исходного открытого текста .

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

Если пользователь А хочет передать зашифрованное комбини­ рованным методом сообщение М пользователю В, то порядок его действий будет таков .

1. Создать (например, сгенерировать случайным образом) симмет­ ричный ключ, называемый в этом методе сеансовым ключом Ks .

2. Зашифровать сообщение М на сеансовом ключе Ks .

3. Зашифровать сеансовый ключ Ks на открытом ключе Кв пользователя В и своем секретном ключе кл .

4. Передать по открытому каналу связи в адрес пользователя В зашифрованное сообщение вместе с зашифрованным сеансовым ключом .

Действия пользователя В при получении зашифрованного сообщения и зашифрованного сеансового ключа должны быть обрат­ ными действиямпользователя А:

1 ) расшифровать на своем секретном ключе кв и открытом ключе Кл пользователя А сеансовый ключ Ks;

2) с помощью полученного сеансового ключа Ks расшифровать и прочитать сообщение М При использовании комбинированного метода шифрования можно быть уверенным в том, что только пользователь В сможет правильно расшифровать ключ Ks и прочитать сообщение М .

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

В табличных выводах 3.3. приведены распространенные длины ключей симметричных и асимметричных криптосистем, для которых трудность атаки полного перебора примерно равна трудности факто­ ризации соответствующих модулей асимметричных криптосистем .

–  –  –

Комбинированный метод шифрования допускает возможность выполнения процедуры аутентификации - проверки подлинности передаваемого сообщения. Для этого пользователь А на основе функции хеширования сообщения и своего секретного ключа Kjx с помощью известного алгоритма электронной цифровой подписи (ЭЦП) генерирует свою подпись и записывает ее, например, в конец передаваемого файла .

Пользователь В, прочитав принятое сообщение, может убедиться в подлинности цифровой подписи абонента А. Используя тот же алгоритм ЭЦП и результат хеширования принятого сообщения, пользователь В проверяет полученную подпись. Комбини­ рованный метод шифрования является наиболее рациональным, объединяет в себе высокое быстродействие симметричного шифрова­ ния и высокую криптостойкость, гарантируемую системами с откры­ тым ключом .

4. ИДЕНТИФИКАЦИЯ И ПРОВЕРКА ПОДЛИННОСТИ

4.1. Основные понятия С каждым объектом компьютерной системы (КС) связана некоторая информация, однозначно идентифицирующая его: число, строка символов, алгоритм, определяющий данный объект. Эту информацию называют идентификатором объекта. Если объект имеет некоторый идентификатор, зарегистрированный в сети, он называется законным (легальным) объектом; остальные объекты относятся к незаконным (нелегальным) .

Идентификация объекта - одна из функций подсистемы защиты. Эта функция выполняется в первую очередь, когда объект делает попытку войти в сеть. Если процедура идентификации завершается успешно, то данный объект считается законным для данной сети .

Следующий за идентификацией объекта шаг - его аутенти­ фикация (проверка подлинности объекта). Эта процедура устанав­ ливает, является ли данный объект именно таким, каким он себя объявляет. После того как объект идентифицирован и подтверждена его подлинность, можно установить сферу его действия и доступные ему ресурсы КС. Такую процедуру называют предоставлением полномочий (авторизация) .

Перечисленные три процедуры инициализации являются процедурами защиты и относятся к одному объекту КС .

При защите каналов передачи данных подтверждение подлин­ ности (аутентификация) объектов означает взаимное установление подлинности объектов, связывающихся между собой по линиям связи. Процедура подтверждения подлинности выполняется обычно в начале сеанса в процессе установления соединения абонентов .

Термин ’’соединение1 указывает на логическую связь (потенциально ’ двустороннюю) между двумя объектами сети. Цель данной процедуры - обеспечить уверенность в том, что соединение установ­ лено с законным объектом и вся информация дойдет до места назначения .

После того как соединение установлено, необходимо обеспечить выполнение требований защиты при обмене сообщениями:

а) получатель должен быть уверен в подлинности источника данных;

б) получатель должен быть уверен в подлинности передаваемых данных;

в) отправитель должен быть уверен в доставке данных получа­ телю;

г) отправитель должен быть уверен в подлинности доставлен­ ных данных .

Для выполнения требований (а) и (б) средством защиты явля­ ется цифровая подпись. Для выполнения требований (в) и (г) отправи­ тель должен получить уведомление о вручении с помощью удосто­ веряющей почты ( certified mail). Средством защиты в такой процедуре является цифровая подпись подтверждающего ответного сообщения, которое, в свою очередь, является доказательством пере­ сылки исходного сообщения .

Если эти четыре требования реализованы в КС, то гарантируется защита данных при их передаче по каналу связи и обеспечивается функция защиты, называемая функцией подтверждения (неоспо­ римости) передачи. В таком случае отправитель не может отрицать ни факта посылки сообщения, ни его содержания, а получатель не может отрицать ни факта получения сообщения, ни подлинности его содержания .

4.2. Идентификация и механизмы подтверждения подлинности пользователя Прежде чем получить доступ к КС, пользователь должен идентифицировать себя, а затем средства защиты сети должны подтвердить подлинность этого пользователя, то есть проверить, является ли данный пользователь действительно тем, за кого себя выдает. Компоненты механизма защиты легальных пользователей размещены на рабочей ЭВМ, к которой подключен пользователь через его терминал (или каким-либо иным способом). Поэтому процедуры идентификации, подтверждения подлинности и наделения полномочиями выполняются в начале сеанса на местной рабочей ЭВМ .

Когда пользователь начинает работу в КС, используя терминал, тогда система запрашивает его имя и идентификационный номер. В зависимости от ответов пользователя компьютерная система проводит его идентификацию. Затем система проверяет, является ли пользователь действительно тем, за кого он себя выдает. Для этого она запрашивает у пользователя пароль. Пароль - это лишь один из способов подтверждения подлинности пользователя .

Перечислим возможные способы подтверждения подлинности:

- предопределенная информация, находящаяся в распоряжении пользователя - пароль, персональный идентификационный номер, соглашение об использовании специальных закодированных фраз;

- элементы аппаратного обеспечения, находящиеся в распоря­ жении пользователя - ключи, магнитные карточки, микросхемы и тому подобное;

- характерные личные особенности пользователя - отпечатки пальцев, рисунок сетчатки глаза, тембр голоса и тому подобное;

- характерные приемы и черты поведения пользователя в режиме реального времени - особенности динамики и стиль работы на клавиатуре, приемы работы с манипулятором и тому подобное;

- навыки и знания пользователя, обусловленные образованием, культурой, обучением, воспитанием, привычками и тому подобным .

Традиционно каждый законный пользователь компьютерной системы получает идентификационный номер и (или) пароль .

В начале сеанса работы на терминале пользователь указывает свой идентификационный номер (идентификатор пользователя) системе, которая затем запрашивает у пользователя пароль .

Простейший метод подтверждения подлинности с использова­ нием пароля основан на сравнении представляемого пользователем пароля РА с исходным значением Р 'А хранящимся в компьютерном, центре (рис. 4.1). Поскольку пароль должен храниться в тайне, постольку его следует шифровать перед пересылкой по незащищен­ ному каналу. Если значения РА и Р'А совпадают, то пароль РА счита­ ется подлинным, а пользователь - законным. Если кто-нибудь, не имеющий полномочий для входа в систему, узнает каким-либо образом пароль и идентификационный номер законного пользова­ теля, то он получит доступ в систему .

Иногда получатель не должен раскрывать исходную открытую форму пароля. В этом случае отправитель должен переслать вместо открытой формы пароля отображение пароля, получаемое с исполь­ зованием односторонней функции а(-) пароля. Это преобразование должно гарантировать невозможность раскрытия противником пароля по его отображению, так как противник наталкивается на неразрешимую числовую задачу .

(Пароль подлинный) Рис. 4.1. Схема простой аутентификации с помощью пароля

Функция а (•) может быть определена следующим образом:

а (Р )= Е Р(Ю), где Р - пароль отправителя; ЕР - процедура шифрования, выполня­ емая с использованием пароля Р в качестве ключа; IE — иденти­ фикатор отправителя .

Подобные описанной выше функции особенно удобны, если длина пароля и длина ключа одинаковы. В этом случае подтвержде­ ние подлинности с помощью пароля состоит из пересылки получа­ телю отображения а(Р) и сравнения его с предварительно вычислен­ ным и хранимым эквивалентом а'(Р) .

На практике пароли состоят только из нескольких букв для удобства их запоминания. Короткие пароли уязвимы для атаки полного перебора всех вариантов.

Для того чтобы предотвратить такую атаку, функцию а(Р) определяют следующим образом:

а(Р) = Epjc(ID), где К и I D - соответственно ключ и идентификатор отправителя .

Очевидно, значение а (Р) вычисляется заранее и хранится в виде а'(Р) в идентификационной таблице у получателя (рис. 4.2) .

Подтверждение подлинности состоит из сравнения двух отображений пароля а(Рj) и а'(Р^) и признания пароля РА, если эти отображения равны. Конечно, любой, кто получит доступ к идентификационной таблице, может незаконно изменить ее содержимое, не опасаясь, что эти действия будут обнаружены .

Рис. 4.2. Схема аутентификации с помощью пароля с использованием идентификационной таблицы

5. ХЕШ -ФУНКЦИИ

Хеш-функция предназначена для сжатия подписываемого доку­ мента М до нескольких десятков или сотен бит. Хеш-функция Л(») принимает в качестве аргумента сообщение (документ) М произволь­ ной длины и возвращает хеш-значение h(M) = Я фиксированной длины. Обычно хешированная информация является сжатым двоич­ ным представлением основного сообщения произвольной длины .

Следует отметить, что значение хеш-функции h(M) сложным образом зависит от документа М и не позволяет восстановить сам документ М .

Хеш-функция должна удовлетворять целому ряду условий:

- должна быть чувствительна к всевозможным изменениям в тексте М - вставкам, выбросам, перестановкам и тому подоб­ ному;

- должна обладать свойством необратимости, то есть задача подбора документа М', который обладал бы требуемым значе­ нием хеш-функции, должна быть вычислительно неразре­ шима;

- вероятность того, что значения хеш-функций двух различных документов (вне зависимости от их длины) совпадут, должна быть ничтожно мала .

Большинство хеш-функций строится на основе однонаправлен­ ной функции / • ), которая образует выходное значение длиной п при задании двух входных значений длиной п. Этими входами являются блок исходного текста М и хеш-значение предыдущего блока текста (рис.

5.1):

Н, =f(M h Ни ) .

Хеш-значение, вычисляемое при вводе последнего блока текста, становится хеш-значением всего сообщения М .

В результате однонаправленная хеш-функция всегда формирует выход фиксированной длины п (независимо от длины входного текста) .

М:

НI ;

Однонаправленная функция f

•f-1

Рис. 5.1. Построение однонаправленной хеш-функции

5.1. Алгоритм безопасного хеширования SHA Алгоритм безопасного хеширования SHA (Secure Hash Algorithm) разработан НИСТ и АНБ США в рамках стандарта безопасного хеширования SHS (Secure Hash Standard) в 1992 году .

Алгоритм хеширования SHA предназначен для использования сов­ местно с алгоритмом цифровой подписи DSA .

При вводе сообщения М произвольной длины менее 2м битов алгоритм SHA вырабатывает 160-битовое выходное сообщение, назы­ ваемое дайджестом сообщения MD (Message Digest). Затем этот дайд­ жест сообщения используется в качестве входа алгоритма DSA, который вычисляет цифровую подпись сообщения М. Формирование цифровой подписи для дайджеста сообщения, а не для самого сооб­ щения повышает эффективность процесса подписания, поскольку дайджест сообщения обычно намного короче самого сообщения .

Такой же дайджест сообщения должен вычисляться пользова­ телем, проверяющим полученную подпись, при этом в качестве входа в алгоритм SHA используется полученное сообщение М .

Алгоритм хеширования SHA назван безопасным, потому что он спроектирован таким образом, чтобы было вычислительно невоз­ можно восстановить сообщение, соответствующее данному дайд­ жесту, а также найти два различных сообщения, которые дадут одинаковый дайджест. Любое изменение сообщения при передаче с очень большой вероятностью вызовет изменение дайджеста, и приня­ тая цифровая подпись не пройдет проверку .

Рассмотрим подробнее работу алгоритма хеширования SHA .

Прежде всего исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Добавление битов выполняется следую­ щим образом: сначала добавляется единица, затем следует столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец добавляется 64-битовое представление длины исходного сообщения.

Инициализируется пять 32-битовых переменных в виде:

^=0x67452301 B = Q x E F C D A В%9 C =0x9& B A D C F E = 0 x 1 0 3 2 5 4 7 6 Е = 0 х С Ъ D 2 E \F Q Далее следует главный цикл алгоритма. В нем обрабатывается по 512 битов сообщения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные а, Ь, с, d, е:

а = А, b = В, с = С, d = D, е = Е .

Главный цикл содержит четыре цикла по 20 операций каждый .

Каждая операция реализует нелинейную функцию от трех из пяти переменных а, Ь, с, d, е, а затем производит сдвиг и сложение .

Алгоритм SHA имеет следующий набор нелинейных функций:

f ( X,Y,Z ) = ( X л У) v [ ( ^ л г ] д л я / = 0,..., 19, f (X, Y, Z) = Х © Y © Z для t = 20,..., 39, f (X, Y, Z) = (X a Y) v (X л Z) v (У л Z) для t = 40,..., 59, f ( X, Y,Z ) = X e Y ® Z д л я t = 60,..., 79, где t - номер операции .

В алгоритме используются также четыре константы:

К, = 0x5^827999 для t = 0,..., 19, К, = 0x6ED9EBA 1 для t = 20,..., 39, К, = 0x8FXBBCDC для / = 4 0,.., 59, К, = 0xCA62ClD6 для t = 60,..., 79 .

Блок сообщения преобразуется из шестнадцати 32-битовых слов (Мо,..., М |5) в восемьдесят 32-битовых слов (W0,..., W19 ) с помощью следующего алгоритма:

W, = М, для t = 0,..., 15, W, = (fV,_3 © W„%© W,.u © W,_l6) « 1 для / = 16,..., 79, где W, - t-й субблок расширенного сообщения; t - номер операции (для t = 1, 8 0 ) ; « S - циклический сдвиг влево на S бит .

С учетом введенных обозначений главный цикл из восьмидесяти операций можно описать так:

FOR t = 0 до 79 TEMP = {а « 5) +/ (Ь, с, d) + е + W, + К, е =d d =с с — (b « 30) b- а а = TEMP Схема выполнения одной операции показана на рис. 5.2 .

После окончания главного цикла значения а, Ь, с, d н е складываются с А, В, С, D и Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D и Е .

Поскольку алгоритм SHA выдает 160-битовое хеш-значение, постольку он более устойчив к атакам полного перебора и атакам "дня рождения", чем большинство других алгоритмов хеширования, формирующих 128-битовые хеш-значения .

5.2. Однонаправленные хеш-функции на основе симметричных блочных алгоритмов Однонаправленную хеш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее распространенный под­ ход состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в режиме СВС или СРВ с помощью фикси­ рованного ключа и некоторого вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хеш-значения сообщения М. При таком подходе не всегда возможно построить безопасную однонаправленную хеш-функцию, но всегда можно полу­ чить код аутентификации сообщения MAC {Message Authentication Code) .

Более безопасный вариант хеш-функции можно получить при помощи использования блока сообщения в качестве ключа, предыдущего хеш-значения - в качестве входа, а текущего хешзначения - в качестве выхода. Реальные хеш-функции проектируются еще более сложными. Длина блока обычно определяется длиной ключа, а длина хеш-значения совпадает с длиной блока .

А_______________________

–  –  –

Рис. 5.3. Обобщенная схема формирования хеш-функции Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые схемы хеширования проектируют так, чтобы хешзначение имело длину, равную двойной длине блока .

Если принять, что получаемая хеш-функция корректна, то безопасность схемы хеширования базируется на безопасности лежа­ щего в ее основе блочного алгоритма. Схема хеширования, у которой длина хеш-значения равна длине блока, показана на рис. 5.3.

Ее работа описывается выражениями:

Но —I», Н, = Еа(В) ФС, где / „ - некоторое случайное начальное значение; А, В и С могут принимать значения Мь Н.\ или быть константами .

Сообщение М разбивается на блоки М, принятой длины, которые обрабатываются поочередно .

Три различные переменные А, В и С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта является либо слабым, либо небезопасным. Первые четыре схемы хеши­ рования, являющиеся безопасными при всех атаках, приведены на рис. 5.4 .

–  –  –

5.3. Отечественный стандарт хеш-функции Российский стандарт ГОСТ Р 34.11-94 определяет алгоритм и процедуру вычисления хеш-функции для любых последователь­ ностей двоичных символов, применяемых в криптографических мето­ дах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя можно было бы использовать и другой блочный алгоритм шифрования с 64-бито­ вым блоком и 256-битовым ключом .

Данная хеш-функция формирует 256-битовое хеш-значение .

Функция сжатия Я, = / (Mh HiA) (оба операнда М, и Ям являются 256-битовыми величинами) определяется следующим образом:

1) генерируются 4 ключа шифрования K j,j = 1,..., 4, путем линейного смешивания М„ Н,л и некоторых констант С/,

2) каждый ключ Kj используют для шифрования 64-битовых подслов h[ слова Ям в режиме простой замены Si = EKj{h;) .

Результирующая последовательность 54, S3, S2, S\ длиной 256 битов запоминается во временной переменной S .

Значение Я, является сложной линейной функцией смешивания S, М, и Ям .

При вычислении окончательного хеш-значения сообщения М учитываются значения трех связанных между собой переменных:

Н„ - хеш-значение последнего блока сообщения; Z - значение конт­ рольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения; L - длина сообщения.

Эти три переменные и допол­ ненный последний блок М ' сообщения объединяются в оконча­ тельное хеш-значение следующим образом:

H = f { Z Ф M \f [ L J ( M \ Н М Данная хеш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с алгоритмом российского стандарта электронной цифровой подписи .

5.4. Электронная цифровая подпись Технология применения системы электронной цифровой подписи предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом втайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и авторства подписи. Открытый ключ не позволяет вычислить секретный ключ .

Для генерации пары ключей (секретный и открытый) в алго­ ритмах ЭЦП, как и в асимметричных системах шифрования, исполь­ зуются разные математические схемы, основанные на применении однонаправленных функций. Эти схемы разделяются на две группы .

В основе такого разделения лежат известные сложные вычисли­ тельные задачи:

- факторизации (разложения на множители) больших целых чисел;

- дискретного логарифмирования .

5.5. Алгоритм цифровой подписи RSA Первой наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 году в Массачусетском технологическом инсти­ туте США .

Необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных доку­ ментов вычисляет два больших простых числа Р и Q, затем находит их произведение N = PQ и значение функции (N) = (Р — 1)(Q - 1) .

p

Далее отправитель вычисляет число Е из условий:

Е q(N), НОД [Е, ф (Л/)] = 1

- и число D из условий:

D N, E D = 1 [mod (АО] .

р Пара чисел (Е, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания .

Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис. 5.5 .

Допустим, что отправитель хочет подписать сообщение М перед его отправкой.

Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хеш-функции й() в целое число т:

т = h(M) .

Затем вычисляют цифровую подпись S под электронным доку' ментом М, используя хеш-значение т и секретный ключ D;

S = mD (mod N) .

Пара (А/, S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа Z) .

Приняв пару (А/, 5), получатель вычисляет хеш-значение сообщения А/ двумя разными способами.

Прежде всего он восстанав­ ливает хеш-значение т \ применяя криптографическое преобразова­ ние подписи S с использованием открытого ключа Е:

т' = 5^ (mod T ) .

V Кроме того, он находит результат хеширования принятого сообщения А/с помощью такой же хеш-функции А():

т = h(M) .

Получатель признает пару (А/, S) подлинной, если соблюдается равенство вычисленных значений, то есть S* (mod N) - h(M) .

Только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители. Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ Ц соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют идентификатором подписавшего .

Недостатки алгоритма цифровой подписи RSA .

1. При вычислении модуля N, ключей Е и D для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать подобную возмож­ ность даже теоретически .

2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, нацио­ нального стандарта США на шифрование информации (алгоритм DES), то есть 101, необходимо использовать при вычислениях N, D и Е целые числа не менее 25,2(или около 101 ) каждое, что требует больших вычислительных затрат, превышающих на 20-30 % вычис­ лительные затраты других алгоритмов цифровой подписи при сохра­ нении того же уровня криптостойкости .

3. Цифровая подпись RSA уязвима для так называемой мульти­ пликативной атаки. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа D сформи­ ровать подписи под теми документами, у которых результат хеши­ рования можно вычислить как произведение результатов хеширо­ вания уже подписанных документов .

Пример. Допустим, что злоумышленник может сконструировать три сообщения M h М2 и М3 у которых хеш-значения составляют ь тх = т2 = h(M2), т3 = h(M3), причем т3 = т х (mod N) .

т2 Допустим также, что для двух сообщений М х и М2 получены законные подписи S { = m xD (mod N ) n S 2 = m2 (mod N) .

В таком случае злоумышленник может легко вычислить подпись

S3 для документа М3, даже не зная секретного ключа D :

*$з = S X (mod N) .

S2 Действительно, Si S2 (mod N) = mxD m2 (mod N) = (mxm2)D(mod N) = m3D (mod N) = S3 .

Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 году американцем арабского происхождения Тахером Эль Гамалем .

В 1991 году НИСТ США обосновал перед комиссией конгресса США выбор алгоритма цифровой подписи Эль Гамаля в качестве основы для национального стандарта .

5.6. Алгоритм цифровой подписи Эль Г ам аля (EGSA) Название EGSA происходит от слов El Gamal Signature Algorithm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители боль­ шого целого числа, - задача дискретного логарифмирования. Более того, Эль Гамалю удалось избежать явной слабости алгоритма цифро­ вой подписи RSA, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа .

Рассмотрим подробнее алгоритм цифровой подписи Эль Гамаля .

Для того чтобы генерировать пару ключей (открытый ключ - секрет­ ный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (порядка Ю30 или 21024) и G (порядка 10154 или 2s'2), которые не являются секретными .

Отправитель выбирает случайное целое число X, 1 Х (Р - 1), и вычисляет Y = G* mod Р .

Число К является открытым ключом, используемым для про­ верки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов. Число X является секрет­ ным ключом отправителя для подписывания документов и должно храниться в секрете .

Для того чтобы подписать сообщение М, сначала отправитель хеширует его с помощью хеш-функции А() в целое число т:

т = h(M), \ т ( Р - \ )

- и генерирует случайное целое число К, 1 К (Р - 1), такое, что К и (Р - 1) являются взаимно простыми. Затем отправитель вычисляет целое число а:

a = GK mod Р

- и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа X целое число b из уравнения m = X a + K b [m od( Р - 1)] .

Пара чисел (а, Ь) образует цифровую подпись S, S = (a,b ), проставляемую под документом М. Тройка чисел (М, а, Ь) передается получателю, в то время как пара чисел (X, К) держится в секрете .

Приняв подписанное сообщение (М, а, V), получатель должен проверить, соответствует ли подпись S = (а, Ь) сообщению М. Для этого получатель сначала вычисляет по приня­ тому сообщению М число т = h (М), то есть хеширует принятое сообщение М. Затем получатель вычис­ ляет значение А = Г а ь (тодР) и признает сообщение М подлинным, если и только если A = G m(modP) .

Иначе говоря, получатель проверяет справедливость соотно­ шения Y3 аь (mod Р) = Gm (mod Р) .

Можно строго математически доказать, что последнее равенство будет выполняться тогда и только тогда, когда подпись S = (а, Ь) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно точно удостовериться, что отправителем сообщения М был облада­ тель именно данного секретного ключа X (без раскрытия самого ключа) и что отправитель подписал именно этот документ М .

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, которое должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ X отправителя .

Пример. Выберем числа 71 = 11, G = 2 и секретный ключ Х = 8 .

Вычисляем значение открытого ключа:

Y = (r mod Р = У = 2 8 mod 11=3 .

Предположим, что исходное сообщение М характеризуется хешзначением т = 5 .

Для того чтобы вычислить цифровую подпись для сообщения М, имеющего хеш-значение т = 5, сначала выберем случайное целое число К = 9. Убедимся, что числа К и (Р - 1) являются взаимно простыми. Действительно, НОД (9,10) = 1.

Далее вычисляем эле­ менты а и b подписи:

a = GK mod Р - 2 9 mod 11=6;

элемент b определяем, используя расширенный алгоритм Евклида:

т = Х а + Kb [mod(P - 1)] .

При т = 5,а = 6, Х = 8, К = 9, Р = 11 получаем 5 = (48 + 9b)(mod 10), или 9b = -43(mod 10) .

Решение: b = 3. Цифровая подпись представляет собой пару:

а = 6, Ь = 3. Далее отправитель передает подписанное сообщение .

Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хеш-значение для сообщения М:

т = 5,

- а затем вычисляет два числа:

1) Г а ь (mod Р) = З6 • 63 (mod 11) = 10 (mod 11);

2) Т (mod Р) = 25 (mod 11) = 10 (mod 11) .

Поскольку эти два целых числа равны, постольку принятое получателем сообщение признается подлинным .

Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а, Ь) .

В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сооб­ щению .

Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSA:

1) при заданном уровне стойкости алгоритма цифровой подписи целые числа, участвующие в вычислениях, имеют запись на 25 % короче, что уменьшает сложность вычислений почти в два раза и позволяет заметно сократить объем используемой памяти;

2) при выборе модуля Р достаточно проверить, что это число является простым и что у числа (Р - 1) имеется большой простой множитель (то есть всего два достаточно просто прове­ ряемых условия);

3) процедура формирования подписи по схеме Эль Гамаля не позволяет вычислять цифровые подписи под новыми сообще­ ниями без знания секретного ключа (как в RSA) .

Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSA. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления .

5.7. Алгоритм цифровой подписи DSA Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 году в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К. Шнорра .

Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р - простые числа, L битов каждое (512 L 1024); q - простое число длиной 160 битов (делитель числа (Р - 1)). Числа G, Р, q являются открытыми и могут быть общими для всех пользователей сети .

Отправитель выбирает случайное целое число X, 1 X q .

Число X является секретным ключом отправителя для формирования электронной цифровой подписи. Затем отправитель вычисляет значе­ ние У = G mod P .

Число У является открытым ключом для проверки подписи отправителя. Оно передается всем получателям документов .

Этот алгоритм также предусматривает использование односто­ ронней функции хеширования А(). В стандарте DSS определен алго­ ритм безопасного хеширования SHA (Secure Hash Algorithm) .

Для того чтобы подписать документ М, отправитель хеширует его в целое хеш-значение т, т = h(M), 1 m q, затем генерирует случайное целое число К, 1 К q, и вычисляет число г, г = (GK mod Р) mod q .

Далее отправитель вычисляет с помощью секретного ключа X целое число s :

s = [(т + rX)/K\ mod q .

Пара чисел г vis образует цифровую подпись 5 = (г, s) под документом М .

Таким образом, подписанное сообщение представляет собой тройку чисел [М, г, j]. Получатель подписанного сообщения [М, г, s] проверяет выполнение условий О r q,Q s q и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение w = (1/s) mod q, хеш-значение т - h(M) и числа U[ = (mw) mod q, и2 = (rw) mod q .

Далее получатель с помощью открытого ключа V вычисляет значение v = [ ( G “ - 1 х • 2) mod Р] mod q и проверяет выполнение условия v = г .

Если условие v = г выполняется, подпись S = (г, s) под документом М признается получателем подлинной. Можно строго математически доказать, что последнее равенство будет выполняться тогда и только тогда, когда подпись S = (г, s) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ У. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет данным секретным ключом X (без оглашения при этом значения ключа X) и что отправитель подписал данный документ М .

По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSA имеет следующие основные преимущества:

- при любом допустимом уровне стойкости, то есть при любой паре чисел G и Р (512-1024 бит), числа q, X, г, s имеют длину по 160 битов, что сокращает длину подписи до 320 битов;

- большинство операций с числами К, г, s, X при вычислении подписи производится по модулю числа q длиной 160 битов, что сокращает время вычисления подписи;

- при проверке подписи большинство операций с числами и/, и2, v, w также производится по модулю числа q длиной 160 битов, что сокращает объем памяти и время вычисления .

Недостатком алгоритма DSA является то, что при подписывании и проверке подписи необходимо выполнять сложные операции деле­ ния по модулю q:

s = [(m + гХУЩ (mod q), w = (1/s) (mod q), что не позволяет получать максимальное быстродействие .

Следует отметить, что реальное исполнение алгоритма DSA может быть ускорено с помощью выполнения предварительных вычислений. Поскольку значение г не зависит от сообщения М и его хеш-значения т, постольку можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения г. Можно также заранее вычислить обратные значения К 1для каждого из значений К. При поступлении сообщения М можно вычислить значение s для данных значений г и К 1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSA .

5.8. Отечественный стандарт цифровой подписи Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94 .

Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. В нем исполь­ зуются следующие параметры:

р - большое простое число длиной 509-512 битов либо 1020— 1024 бита;

q - простой сомножитель числа (р - 1), имеющий длину 254-256 битов;

а - любое число, меньшее (р - 1), причем такое, что aq mod р = 1;

х - некоторое число, меньшее q;

у = ах mod р .

В алгоритме используется однонаправленная хеш-функция Н(х) .

Стандарт ГОСТ Р 34.11-94 определяет хеш-функцию .

Первые три параметра- р, q и а - являются открытыми и могут быть общими для всех пользователей сети. Число jc является секрет­ ным ключом. Число у является открытым ключом. Чтобы подписать некоторое сообщение т, а затем проверить подпись, выполняются следующие шаги .

1. Пользователь А генерирует случайное число к, причем к q .

2. Пользователь А вычисляет значения г = (a mod р) mod р, s = [х х г + к {Н{т)}] mod р .

Если Н(т) mod q = 0, то значение Н(т) mod q принимают равным единице. Если г = 0, то выбирают другое значение к и начи­ нают снова .

Цифровая подпись представляет собой два числа:

г mod 2256 и s mod 2256 .

Пользователь А отправляет эти числа пользователю Л .

3. Пользователь В проверяет полученную подпись путем вычис­ ления v = Н(т)4'2 mod q, Zj = (s v) mod q, * 2 = [(q-r) v] mod q, u = [(ct1y 2) mod p] mod p .

Если u = r, то подпись считается верной .

Различие между этим алгоритмом и алгоритмом DSA заключа­ ется в том, что в DSA 5 = {к'1 (х х Г + [Я(т)])} mod q, а это приводит к другому уравнению верификации .

Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 битов. Западных криптографов вполне устраивает q длиной примерно 160 битов. Различие в значениях пара­ метра q является отражением стремления разработчиков отечествен­ ного стандарта к получению более безопасной подписи .

Российский стандарт вступил в действие с начала 1995 году .

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Вернер М. Основы кодирования / М. Вернер. 2-е изд. М.: Техно­ сфера, 2006 .

ГОСТ 28147-89. Система обработки информации. Защита крип­ тографическая. Алгоритм криптографического преобразования [Электрон, ресурс]. Режим доступа : http://protect.gost.ru/document .

aspx?control=7&id=139177 Дата обращения 03.07.2013 .

ГОСТ Р 34.10-94 .

Информационная технология. Криптогра­ фическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного крипто­ графического алгоритма [Электрон, ресурс].

Режим доступа :

http://vsegost.com/CataIog/46/46926.shtml Дата обращения 03.07.2013 .

ГОСТ Р 34.11-94 .

Информационная технология. Криптографи­ ческая защита информации. Функция хеширования [Электрон, ресурс]. Режим доступа http://protect.gost.ru/document/aspx?

control=7&id=l34550 Дата обращения 03.07.2013 .

Digital signature standart (DSS). FIPS PUB 190,1994, MAY 19 .

Зензин О. С. Стандарт криптографической защиты - AES (Advanced Encryption Standart) / О. С. Зензин, М. А. Иванов. М.

:

КУДИЦ-Образ, 2007 .

Смарт Н. Криптография / Н. Смарт. 2-е изд. М. : Техносфера, 2006 .

Фергюсон Н. Практическая криптография / Н. Фергюсон, Б. Шнаер. М.: Вильямс, 2005 .

П РИ Л О Ж ЕН И Я

–  –  –

Программная реализация симметричного алгоритма криптографической защиты информации Для выполнения лабораторных работ можно использовать любые языки и среды программирования, например, C++, С#, Delphi .

Задание Реализовать один из современных алгоритмов криптографи­ ческого преобразования данных (DES, ГОСТ, AES и другие) .

–  –  –

Программная реализация асимметричного алгоритма криптографической защиты информации Для выполнения лабораторных работ можно использовать любые языки и среды программирования, например, C++, С#, Delphi .

Задание Реализовать один из современных асимметричных алгоритмов криптографического преобразования данных (например, RSA, EGSA) или хеш-функцию .

–  –  –

1. БЛОЧНЫЕ ШИФРЫ

1.1. Общие сведения о блочных шифрах

1.2. Сеть Фейштеля

1.3. Шифр взбивания. Стандарт D ES

1.4. Отечественный стандарт шифрования данных

1.5. Режимы применения блочных шифров

2. НОВЫЙ КРИПТОСТАНДАРТ БЛОЧНОГО

ШИФРОВАНИЯ США

2.1. Общие сведения о конкурсе AES

2.2. Победитель AES - шифр RIJNDAEL

3. АССИМЕТРИЧНЫЕ КРИПТОСИСТЕМЫ

3.1. Концепция криптосистемы с открытым ключом

3.2. Однонаправленные функции

3.3. Криптосистема шифрования данных RSA

3.4. Схема шифрования Полига-Хеллмана

3.5. Схема шифрования Эль Гам аля

3.6. Комбинированный метод шифрования

4. ИДЕНТИФИКАЦИЯ И ПРОВЕРКА ПОДЛИННОСТИ 54

4.1. Основные понятия

4.2. Идентификация и механизмы подтверждения подлинности пользователя

5. ХЕШ-ФУНКЦИИ

5.1. Алгоритм безопасного хеширования SHA

5.2. Однонаправленные хеш-функции на основе симметричных блочных алгоритмов

5.3. Отечественный стандарт хеш-функции

5.4. Электронная цифровая подпись

5.5. Алгоритм цифровой подписи R S A

5.6. Алгоритм цифровой подписи Эль Гамаля (EGSA)............... 67

5.7. Алгоритм цифровой подписи D S A

5.8. Отечественный стандарт цифровой подписи

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЯ

Приложение 1. Задание к лабораторной работе № 1

Приложение 2. Задание к лабораторной работе № 2

Учебное издание С пиричева Наталия Рахматулловна

АЛГОРИТМЫ БЛОЧНОЙ КРИПТОГРАФИИ

Редактор И. В. Меркурьева Компьютерный набор Н. Р. Спиричевой Компьютерная верстка Т. С. Кринщиной Подписано в печать 10.09.2013. Формат 60x90 1/16 .

Бумага писчая. Плоская печать. Уел. печ. л. 5,0 .

Уч.-изд. л. 4,3. Тираж 50 экз. Заказ № 1859 .

Издательство Уральского университета Редакционно-издательский отдел ИПЦ УрФУ 620049, Екатеринбург, ул. С. Ковалевской, 5 Тел.: 8 (343) 375-48-25,375-46-85, 374-19-41 E-mail: rio@ustu.ru

–  –  –






Похожие работы:

«11.08.2016 ДИСТРИБУТИВ ОС GNU/LINUX НА БАЗЕ BUILDROOT ДЛЯ 1892ВМ14Я. РУКОВОДСТВО СИСТЕМНОГО ПРОГРАММИСТА Версия v2.0.1-14 11.08.2016 support@elvees.com, www.multicore.ru 11.08.2016 ОГЛАВЛЕНИЕ 1 О документе 3 2 Общи...»

«ЛЕКЦІЯ 12. БЕЗПЕКА В ГЛОБАЛЬНІЙ МЕРЕЖІ ІНТЕРНЕТ Навчальні питання: Организационная и физическая структура сети Интернет. 1. Угрозы безопасности функционированию сети Интернет. 2. Практическая реализация системы доменных имен. 3. Проблем...»

«Red Hat Linux. Секреты профессионала, Издательский дом Вильямс Опубликовано: 12th April 2013 Red Hat Linux. Секреты профессионала СКАЧАТЬ http://bit.ly/1lypxwx Linux для чайников, 5-е издание,,,,.. Программирование на языке C...»

«Санкт-Петербургский государственный университет Кафедра Системного Программирования Болотов Сергей Сергеевич Разработка компилятора для языка РуСи на платформу MIPS Бакалаврская работа Научный руководитель: д. ф.-м. н., профессор Терехов А. Н.Рецензент: Тиунова А. Е. Санкт-Петербург SAINT-PETERSBURG STATE UNIVERSITY Department of Sof...»

«УЧЕБНОЕ ПОСОБИЕ СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ 7-е издание Э. В. Фуфаев Д. Э. Фуфаев БАЗЫ ДАННЫХ СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ Э. В . ФУФАЕВ, Д. Э. ФУФАЕВ БАЗЫ ДАННЫХ Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов образовательных учреждений среднего профессионального образования 7-е изд...»

«CPU-95 ИНСТРУКЦИЯ ПО ПРОГРАММИРОВАНИЮ АБОНЕНТСКАЯ ПРОГРАММА ДОКУМЕНТ CPU-95 PI 4-08 НЕИСПОЛНЕНИЕ НАСТОЯЩЕЙ ИНСТРУКЦИИ МОЖЕТ ПРИВЕСТИ К НЕПРАВИЛЬНОЙ РАБОТЕ ДВИГАТЕЛЯ, В ВНИМАНИЕ: РЕЗУЛЬТАТЕ ЧЕГО ВОЗМОЖНО ТРАВМИРОВАНИЕ ОПЕРАТОРОВ ИЛИ ИНОГО НАХОДЯЩЕГОСЯ ПОБЛИЗОСТИ ПЕРСОНАЛА 1.0 ОПИСАНИЕ 1.1 Программа CPU...»

«СОДЕРЖАНИЕ ВВЕДЕНИЕ 1 МЕРЫ БЕЗОПАСНОСТИ 2 ОБЩИЕ ТРЕБОВАНИЯ 3 РАСПАКОВКА 4 МОНТАЖ ППР 4.1 Выбор типоразмера ППР 4.2 Требования к месту установки ППР 4.3 Монтаж 5 МОНТАЖ ТС 5.1 Требования к месту установки ТС 5.2 Монтаж 6 МОНТАЖ ДИД 7 МОНТАЖ ИВБ 7.1 Выбор места установки и монта...»

«4Н УДК 681.3 А.А. Никоненко Киевский национальный университет имени Т. Шевченко, г. Киев, Украина andrey.nikonenko@gmail.com Обзор баз знаний онтологического типа В статье рассматриваются вопросы построения, структурирования, описания, классификации и использования онтологических баз знаний. Приведен...»

«ФГБОУ ВО "Тюменский индустриальный университет" НАВИГАТОР ПОСТУПАЮЩЕМУ – 2018 Программы высшего образования (магистратура) Заочная форма обучения Институт геологии и нефтегазодобычи (ИГиН) Институт промышленных технологий и инжиниринга (ИПТИ) Институт сервиса и отраслевого управления (ИСОУ) Институт транспорта (ИТ) Инст...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего образования "ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ" Факультет математики и компьютерных наук Программа государственной итоговой аттестации Кафедра прикладной математики факультета...»

«68th IFLA Council and General Conference August 18-24, 2002 Code Number: 050-093-R Division Number: VII Professional Group: Education and Training Joint Meeting with: Meeting Number: 93 Simultaneous Interpretation: Стимулирование развития навыков – ЦИКН Ал...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.