Анализ алгоритмов электронной цифровой подписи

 

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

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

 

2 Обзор алгоритмов ЭЦП

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

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

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

Более надежный и удобный для реализации на персональных компьютерах ЭЦП алгоритм был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем и получил название El Gamal Signature Algorithm (EGSA).

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

Алгоритм цифровой подписи Digital Signature Algorithm (DSA) предложен в 1991г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритма ЭЦП EGSA. По сравнению с алгоритмом ЭЦП EGSA алгоритм DSA имеет ряд преимуществ: сокращен объем памяти и время вычисления подписи. Недостатком же является необходимость при подписывании и проверке подписи выполнять сложные операции деления по модулю большого числа.

Российский стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. Различие между этими стандартами заключается в использовании параметров ЭЦП разного порядка, что приводит к получению более безопасной подписи при использовании российского стандарта.

Алгоритмы цифровых подписей Elliptic Curve Digital Signature Algorithm (ECDSA) и ГОСТ Р 34.10-2001 являются усовершенствованием цифровых подписей DSA и ГОСТ Р 34.10-94 соответственно. Эти алгоритмы построены на базе математического аппарата эллиптических кривых над простым полем Галуа.

 

3 Анализ надежности российского стандарта ЭЦП ГОСТ Р 34.10-2001

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

Надежность цифровой подписи определяется стойкостью к криптоаналитическим атакам двух ее компонент: хэш-функции и самого алгоритма ЭЦП.

Стойкая схема цифровой подписи должна использовать хэш-функцию, обладающую следующими свойствами:

Оценим вероятность взлома хэш-функции.

Для лобовой атаки на однонаправленные хэш-функции используют два метода. Первый направлен на взлом второго свойства, т.е. по известному значению хэш-функции H(M) противник хочет создать другой документ M’, такой, что H(M’) = H(M). Другой метод изящнее, он направлен на взлом третьего свойства: противник хочет найти два случайных сообщения M и M’, таких, что H(M) = H(M’).

В математической статистике известен стандартный парадокс «дней рождений», который заключается в следующем (Лапонина О.Р. Криптографические основы безопасности // www.INTUIT.ru): сколько человек должно собраться в одной комнате, чтобы с вероятностью 1/2 хотя бы у одного из них был общий с вами день рождения? Ответ – 253. А сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был общий день рождения? Ответ поразителен – 23.Обнаружение кого-нибудь с точно заданным днем рождения аналогично первому методу атаки, а обнаружение двух человек с произвольным, но одинаковым днем рождения аналогично второму методу. Вторая атака широко известна как атака на основе парадокса “дней рождений” [2].

Предположим, что однонаправленная хэш-функция надежна и лучший метод ее вскрытия – лобовой. Выход этой хэш-функции – m-разрядное число. Тогда количество выходных значений хэш-функции H равно .

Обозначим – вероятность того, что для конкретного значения X и хотя бы для одного из значений , …, , выполнялось равенство H(X) = H(Y).

Каким должно быть число k, чтобы вероятность была больше 0,5?

Для одного Y вероятность того, что H(X) = H(Y), равна . Соответственно, вероятность того, что , равна . Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. . Следовательно, вероятность, по крайней мере, одного совпадения равна . Приравняв к 0,5, получим .

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

Теперь рассмотрим следующую задачу: обозначим – вероятность того, что в множестве из r элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно r, чтобы была больше 0,5?

Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно . Всего возможных способов выбора элементов равно . Вероятность того, что дублей нет, равна . Вероятность того, что есть дубли, соответственно равна . Приравняв к 0,5, из (2) получим . Если хэш-код имеет длину m бит, т.е. принимает значений, то .

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

Оценим, насколько успешными на практике могут быть атаки, основанные на двух описанных выше методах. Пусть одна MIPS (Million Instruction Per Second) машина хэширует миллион сообщений в секунду. При таких условиях число хэш-значений, вычисленных одной MIPS машиной за один год составляет .

В таблице 1 приведена оценка вероятности взлома хэш-функции для двух рассмотренных методов атаки при различных значениях длины выходного хэш-значения.

Таблица 1

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

Рис. 1 – Вероятность взлома хэш-функции

Из графика (рис. 1) видно, что при одинаковой длине хэш-значения сообщения вероятность взлома хэш-функции первым методом намного ниже, чем при взломе хэш-функции методом, основанном на парадоксе “дней рождений”. Так, при 256-битном хэше, вероятность взлома первым методом равно 1,73 × 10^–77, а при втором – 2,94 × 10^–39.

Таким образом, чтобы обеспечить требуемую вероятность взлома хэш-функции необходимо использовать большую длину хэш-значения сообщения. Так, например, при требовании обеспечить вероятность взлома не более 10^–30, необходимо использовать не 128-битное, а 256-битное значение хэш-функции.

Также можно сделать вывод, что при одинаковой длине хэш-значения сообщения на взлом хэш-функции H(M) методом поиска документа M’, такого, что H(M’) = H(M), потребуется гораздо меньше времени, чем при взломе хэш-функции методом, основанном на парадоксе “дней рождений”. Так, при 256-битном хэше, продолжительность взлома первым методом равна 1,8 × 10⁶³ MIPS-лет, а при втором – 1,1 × 10²⁵ MIPS-лет.

Таким образом, чтобы обезопасить хэш-функцию от взлома на определенное количество лет необходимо использовать большую длину хэш-значения сообщения. Так, при требовании обеспечить стойкость к взлому хэш-функции в течение 1,1 × 10²⁵ MIPS-лет, необходимо использовать не 128-битное, а 256-битное значение хэш-функции.

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

Российский стандарт хэш-функции ГОСТ Р 34.11-94 использует 256-битное хэш-значение сообщения, что позволяет утверждать, что при современных вычислительных мощностях его вскрытие вычислительно невозможно. Другими словами, для взлома хэш-функции ГОСТ Р 34.11-94 вторым, более эффективным методом, потребуется 1,1 × 10²⁵ MIPS-лет.

Как уже отмечалось выше, надежность цифровой подписи определяется стойкостью к криптоаналитическим атакам алгоритма ЭЦП.

Выясним какую криптостойкость обеспечивают российские стандарты.

Стойкость стандарта ГОСТ Р 34.10-94 основана на сложности решения частной задачи дискретного логарифмирования в простом поле GF(p). Задача эта формулируется следующим образом (Ливак Е.Н Электронная цифровая подпись // http://mf.grsu.by/Kafedry/kaf001/academic_process/umo/074/lec_07/):

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

Методами решения частной задачи дискретного логарифмирования являются также r- и l-метод Полларда и некоторые близкие методы, требующие для ее решения выполнения порядка операций умножения в поле GF(p).

Стойкость нового российского стандарта ГОСТ Р 34.10-2001 основана на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Эта задача формулируется следующим образом:

В настоящее время наиболее быстрыми алгоритмами решения задачи дискретного логарифмирования в группе точек эллиптической кривой при правильном выборе параметров считаются r-метод и l-метод Полларда (Бондаренко М.Ф., Горбенко И.Д., Качко Е.Г., Свинарев А.В., Григоренко Т.А. Сущность и результаты исследований свойств перспективных стандартов цифровой подписи X9.62-1998 и распределения ключей X9.63-199X на эллиптических кривых // www.bezpeka.com). Так для улучшенного r-метода Полларда вычислительная сложность оценивается как .

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

Таблица 2 – Трудоемкость взлома российских стандартов ЭЦП

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

Рис. 2 – Трудоемкость взлома ЭЦП

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

Из графика (рис. 2) видно, что, при одинаковом порядке параметров q и p, взлом нового российского стандарта, использующего вычисления в группе точек эллиптической кривой, потребует выполнения большего числа операций, чем взлом старого стандарта, который базируется на использовании несимметричных криптографических преобразований, выполняемых в кольцах. Так, при 256-разрядных q и p, трудоемкость взлома нового стандарта составляет 3,02 × 10³⁸, а старого – 1,12 × 10¹⁴.

Также из графика (рис. 2) видно, что для обеспечения трудоемкость взлома ЭЦП, например, 10³⁰ операций в ГОСТ Р 34.10-94 необходимо использовать 1536-разрядное p, а в ГОСТ Р 34.10-2001 достаточно использовать 256-разрядное q.

Основываясь на полученных оценках, можно сделать вывод, что схема ЭЦП ГОСТ Р 34.10-2001, базирующаяся на математическом аппарате эллиптических кривых, является более стойкой по сравнению со схемой ЭЦП ГОСТ Р 34.10-94, основанной на сложности решения задачи дискретного логарифмирования в простом поле. Другими словами в новом российском стандарте ЭЦП можно использовать меньшую длину ключа, чем в старом, без понижения безопасности всей системы.

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

 

4 Учебный программный комплекс

Развитие вычислительной техники и рост компьютеризации учебных заведений открывает сегодня возможности широкомасштабного внедрения информационных технологий в учебный процесс. В данной работе был разработан учебный программный комплекс, позволяющий получить теоретическую информацию по хэш-функции и ЭЦП, а также практические навыки работы с российскими стандартами хэш-функции ГОСТ Р 34.11-94 и ЭЦП ГОСТ Р 34.10-2001.

Программа содержит следующие функциональные блоки:

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

Меню учебного программного комплекса состоит из трех пунктов: вычисления, справка и выход.

Пункт меню “Вычисления” содержит следующие опции:

Пункт меню “Справка” содержит следующие опции:

Данный учебный программный комплекс может быть использован для проведения лабораторных работ для студентов специальности 075600 “Информационная безопасность телекоммуникационных систем ” по дисциплинам “Программно-аппаратные средства обеспечения информационной безопасности” и “Криптографические методы защиты информации”.

 

ЛИТЕРАТУРА