Сравнительный анализ алгоритмов электронной цифровой подписи (RSA, ELGAMAL, DSA)

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

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

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

- Контроль целостности;

- Защиту от изменений (подделки) документа;

- Невозможность отказа от авторства;

- Доказательное подтверждение авторства документа.

Все эти свойства ЭЦП позволяют использовать её для организации юридически значимого электронного документооборота.

Схемы построения электронной цифровой подписи

Существует несколько схем построения цифровой подписи:

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

- На основе алгоритмов асимметричного шифрования. На данный момент такие схемы ЭЦП наиболее распространены и находят широкое применение.

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

Поскольку подписываемые документы, как правило, достаточно большого объёма, в схемах ЭЦП зачастую подпись ставится не на сам документ, а на его хеш. Хешем называется битовая строка фиксированной длины, полученная путем преобразования входного массива данных произвольной длины.

Использование хеш-функций даёт следующие преимущества:

- уменьшение вычислительной сложности;

- отсутствие проблем с совместимостью;

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

Симметричная схема

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

Асимметричная схема

Асимметричные схемы ЭЦП относятся к криптосистемам с открытым ключом. В схемах цифровой подписи подписывание производится с применением закрытого ключа, а проверка - с применением открытого.

Рис 1. Схема подписи и ее проверки с применением хеш-функции

Общепризнанная схема цифровой подписи охватывает три процесса:

- Генерация ключевой пары. При помощи алгоритма генерации ключа выбирается закрытый ключ, далее вычисляется соответствующий ему открытый ключ;

- Формирование подписи. Для заданного электронного документа с помощью закрытого ключа вычисляется подпись;

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

Обзор наиболее распространенных алгоритмов ЭЦП

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

- задача факторизации больших целых чисел;

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

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman)

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

Алгоритм создания открытого и секретного ключей RSA

Алгоритм цифровой подписи сообщений

Предположим, что стороне A нужно отправить стороне B сообщение pt = 15, подтвержденное цифровой подписью.

Алгоритм отправителя

Алгоритм получателя

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

- При вычислении модуля n, ключей e и d для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение.

- Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 1018, необходимо использовать при вычислениях n, d и e целые числа, не менее 2512 каждое, что требует больших вычислительных затрат, превышающих на 20-30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.

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

Elgamal (схема Эль-Гамаля)

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

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

Алгоритм создания открытого и секретного ключей Elgamal

Алгоритм цифровой подписи сообщений

Предположим, что стороне A нужно отправить стороне B сообщение pt = 15, подтвержденное цифровой подписью.

Алгоритм отправителя

Алгоритм получателя

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

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

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

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

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

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

Алгоритм цифровой подписи сообщений

Предположим, что стороне A нужно отправить стороне B сообщение pt = 15, подтвержденное цифровой подписью.

Алгоритм создания открытого и секретного ключей DSA

Алгоритм отправителя

Алгоритм получателя

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

1) При любом допустимом уровне стойкости, т.е. при любой паре чисел g и p (от 512 до 1024 бит), числа q, x, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.

2) Большинство операций с числами k, r, s, x при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.

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

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

Сравнение алгоритмов ЭЦП

ЛИТЕРАТУРА

1. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. – М.: Радио и связь, 2001. – 376 с.

2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М., 2002 – 816 с.