Электронные цифровые подписи

RSA-криптосистема с открытым ключом

В 1978 г. трое ученых (Ривест, Шамир и Адлеман) разработали

систему шифрования с открытыми ключами RSA (Rivest, Shamir, Adleman).

Этот метод состоит в следующем.

1. Случайно выбираются два очень больших простых числа р и q.

2. Вычисляются два произведения n = p ⋅ q и m = (p – 1) ⋅ (q – 1).

3. Выбирается случайное целое число Е, не имеющее общих

сомножителей с m.

4. Находится D, такое, что DE = 1 по модулю m.

5. Исходный текст X разбивается на блоки таким образом, чтобы

0 < Х < n.

6. Для шифрования сообщения необходимо вычислить C = XE по

модулю n.

7. Для дешифрирования вычисляется Х = СD по модулю n.

Таким образом, чтобы зашифровать сообщение, необходимо знать

пару чисел (Е, n), а чтобы дешифрировать – пару чисел (D, n). Первая

пара – это открытый ключ, а вторая – закрытый.

Зная открытый ключ (Е, n), можно вычислить значение закрытого

ключа D. Н еобходимым п ромежут очным действием в эт ом

преобразовании является нахождение чисел р и q, для чего нужно

разложить на простые множители очень большое число n, а на это

требуется очень много времени. Именно с огромной вычислительной

сложностью разложения большого числа на простые множители связана

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

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

200-значного числа, понадобится 4 миллиарда лет работы компьютера

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

что в настоящее время активно ведутся работы по совершенствованию

методов разложения больших чисел, поэтому в алгоритме RSA стараются

применять числа длиной более 200 десятичных разрядов.

Программная реализация криптоалгоритмов типа RSA значительно

сложнее и менее производительна, чем реализация классических

криптоалгоритмов типа DES. Вследствие сложности реализации

операций модульной арифметики криптоалгоритм RSA часто используют

только для шифрования небольших объемов информации, например,

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

а основную часть пересылаемой информации шифруют с помощью

симметричных алгоритмов.

В таблице 5 приведены некоторые сравнительные характеристики

классического криптоалгоритма DES и криптоалгоритма RSA. (таблица)(45)

Цифровая подпись (ЦП) представляет собой строку данных, которая

зависит от некоторого секретного параметра (ключа), известного только

подписывающему лицу, и от содержания подписываемого сообщения,

представленного в цифровом виде. Таким образом, цифровая подпись

связывает сообщение с некоторым порождающим или подписывающим

его объектом.

Задача цифровой подписи состоит в том, чтобы обеспечить защиту

электронного документа не только от подделки п осторонним

злоумышленником, но и от действий недобросовестных участников

информационного обмена. Требования, предъявляемые к цифровой

подписи, можно сформулировать следующим образом:

1. Цифровая подпись доказывает, что подписавший согласен с

содержанием документа.

2. Она является неотъемлемой частью документа и не может быть

перенесена на другой документ.

3. После того как документ подписан, его невозможно изменить.

4. От подписи нельзя отказаться, то есть подписавший не сможет

впоследствии утверждать, что документ подписан без его ведома.

Изложим основные идеи, на которых основан механизм цифровой

подписи.

Пусть по-прежнему преобразования Е и D обладают

перечисленными ранее свойствами и, кроме того, преобразование D

сложно обратить, то есть, зная D и х, трудно найти у такое, что D(y) = x.

Для того чтобы наладить обмен подписанными электронными

сообщениями, необходимо передать получателю сообщений ключ

расшифрования, а ключ зашифрования держать в секрете (рис. 4).(45)

Чтобы подтвердить подлинность сообщения х абонент А должен

отправить вместе с ним значение E1(x), полученное в результате

шифрования сообщения на своем секретном ключе. Это значение и

является цифровой подписью х. Абонент В, получив пару х, Е1(х),

применяет преобразование D1 и убеждается в том, что D1(E1(x)) = x. Если

А держит преобразование Е1 в секрете, то никто кроме него не сможет

подобрать такое у, чтобы D1(y) совпадало с х.

Нетрудно заметить, что описанный выше механизм цифровой

подписи может обеспечивать проверку подлинности документов даже

более надежно, чем обычная подпись под бумажным документом.

Очевидно, однако, что цифровая подпись не является полным аналогом

обычной подписи. Так, например, возможность постановки подписи

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

передана или утеряна. Что касается цифровой подписи, то секретный

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

передан другому лицу, а также потерян или украден.

Еще одна особенность цифровой подписи заключается в том, что

она не связана с единственным экземпляром документа. Уничтожив

подписанный экземпляр бумажного документа, можно быть уверенным,

что второго точно такого больше нет. Что касается уничтожения

электронного документа с цифровой подписью, то это ни о чем не

говорит, так как может существовать неограниченное количество ничем

не отличающихся копий этого документа.

Рассмотрим теперь некоторые особенности реализации алгоритмов

цифровой подписи. Прежде всего отметим, что описанный выше

механизм выработки цифровой подписи не всегда пригоден для

практического применения, так как преобразования, обладающие

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

фиксированной длины. Можно, конечно, подписывать документ по

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

документов может потребовать слишком много времени и, кроме того,

значительно вырастет их объем.

Чтобы обойти данную проблему, подписывают не само сообщение,

а значение хэш-функции от него. Функция хэширования (хэш-

функция) – преобразования, которые отображают строки переменной

длины во множество строк фиксированной длины, как правило, меньшей,

чем у исходных строк. Значение хэш-функции h от сообщения х будем

называть хэш-кодом и обозначать h(x).

Таким образом, чтобы подписать документ х, необходимо сначала

вычислить его хэш-код h(x), а затем преобразовать его с помощью

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

пара x, E(h(x)). Хэш-функция h, с помощью которой определяется хэш-

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

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

значения h(x) и D(E(h(x))) и сравнить их между собой.

Очевидно, что не любая функция, отображающая сообщение

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

использована в алгоритме цифровой подписи. Рассмотрим, например,

функцию s, значением которой является сумма по модулю 2 всех байтов

сообщения. В этом случае несложно для заданного сообщения х

подобрать сообщение у, для которого s(y) = s(x). Следовательно,

перехватив подлинное сообщение х и его цифровую подпись E(s(x)),

злоумышленник может подменить его сообщением у, используя в

качестве цифровой подписи E(s(x)) = E(s(y)).

Перечислим требования, которым должна удовлетворять хэш-

функция, пригодная для использования в алгоритме цифровой

подписи.

1. Хэш -функция должна имет ь возмож ност ь обрабатывать

сообщения произвольной длины.

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

фиксированной длины.

3. Вычисление хэш-функции от заданного сообщения должно

производиться относительно быстро.

4. Обратная операция, то есть нахождение сообщения х, имеющего

заданный хэш-код, должна быть трудно выполнимой.

Из последнего т ребования вытекает, что для имеющегося

сообщения х сложно найти несовпадающее с ним сообщение у такое,

что h(y) = h(x) (наличие такой пары называют коллизией). Следовательно,

перехватив сообщение х с цифровой подписью E(h(x)), злоумышленник

не сможет подобрать другое сообщение, имеющее ту же цифровую

подпись.

Функции, удовлетворяющие требованиям 1–4, называют слабыми

хэш-функциями.

Чтобы функцию h(x) можно было назвать сильной, необходимо

выполнение следующего дополнительного условия:

5. Очень сложно подобрать пару сообщений х, у таких, что h(x) =

= h(y).

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

имеется алгоритм подбора сообщений с совпадающими хэш-кодами.

Пусть х, у такие, что h(x) = h(y). Вполне возможно, что одно из этих

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

злоумышленнику. Например, в первом содержится указание о переводе

100 долл. в благотворительный фонд, а во втором 100 000 долл. на счет

злоумышленника. Тогда злоумышленник может каким-либо образом

добиться подписания безобидного сообщения х, а затем использовать

полученную цифровую подпись E(h(x)) для подтверждения сообщения

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

Российский стандарт на хэш -функцию (ГОСТ Р 34.11-94)

удовлетворяет требованиям, предъявляемым к сильной хэш-функции.

Длина хэш-кода согласно этому стандарту составляет 256 бит.

Если имеется необходимость в обеспечении и целостности, и

сек ретности сообщения, то ц елесообразно сначала подписать

сообщение, а затем уже зашифровать его вместе с подписью. При такой

последовательности действий удастся избежать подписывания “кота в

мешке”, каким является зашифрованное сообщение. Кроме того, будет

скрыта цифровая подпись, по которой можно установить автора

сообщения. Здесь уместна аналогия с письмом. Роль подписи под

письмом берет на себя цифровая подпись, а шифрование обеспечивает

секретность послания вместо конверта. Естественно, что в этом случае

необходимо иметь две пары открытых и секретных ключей: одну

использовать для генерации цифровой подписи, а вторую для

шифрования (либо для пересылки ключа симметричной криптосистемы,

используемой для шифрования сообщения).

Следует отметить, что приведенная схема построения алгоритма

цифровой подписи на основе системы шифрования с открытым ключом,

хотя и удобна для изложения основных идей, но не отражает всего

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

шифрования и цифровой подписи RSA (Rivest, Shamir, Adleman) хорошо

соответствует данной схеме. А Российский стандарт цифровой подписи

– ГОСТ Р 34.10-94 не совсем точно укладывается в приведенную схему.

Здесь также имеется секретный ключ для выработки цифровой подписи

и открытый ключ для ее проверки. Однако процесс получения цифровой

подписи не является шифрованием.

Одной из основных проблем, связанных с использованием

криптосистем с открытым ключом, является проблема обеспечения

достоверности передаваемых открытых ключей. Представим себе, что

некий злоумышленник С подменил открытый ключ абонента А, во время

его передачи абоненту В, на свой открытый ключ. В этом случае он

сможет расшифровывать все сообщения абонента В, предназначенные

для А. Аналогичная атака на цифровую подпись приведет к тому, что

сообщения, подписанные злоумышленником, будут считаться

подлинными, а настоящие сообщения – ложными.

Дата добавления: 2014-12-24