Продолжим. Алгоритмы ЭЦП делятся на два больших класса:
♦ обычные цифровые подписи;
♦ цифровые подписи с восстановлением документа.
Обычные цифровые подписи необходимо пристыковывать к подписываемому документу. К этому классу относятся, например, алгоритмы, основанные на эллиптических кривых (ECDSA, ГОСТ Р34.10-2001, ДСТУ 4145-2002). Цифровые подписи с восстановлением документа содержат в себе подписываемый документ: в процессе проверки подписи автоматически вычисляется и тело документа. К этому классу относится один из самых популярных алгоритмов – RSA, который мы рассмотрим в конце раздела.
Следует различать электронную цифровую подпись и код аутентичности сообщения, несмотря на схожесть решаемых задач (обеспечение целостности документа и невозможности отказа от авторства). Алгоритмы ЭЦП относятся к классу асимметричных алгоритмов, в то время как коды аутентичности вычисляются по симметричным схемам.
Можно сказать, что цифровая подпись обеспечивает следующие виды защиты.
♦ Удостоверение источника документа. В зависимости от деталей определения документа могут быть подписаны такие поля, как "автор", "внесенные изменения", "метка времени" и т. д.
♦ Защита от изменений документа. При любом случайном или преднамеренном изменении документа (или подписи) изменится хэш, и, следовательно, подпись станет недействительной.
♦ Невозможность отказа от авторства. Поскольку создать корректную подпись можно, лишь зная закрытый ключ, а он известен только владельцу, то владелец не может отказаться от своей подписи под документом.
Совершенно очевидно, что ЭЦП вовсе не совершенна. Возможны следующие угрозы цифровой подписи, при которых злоумышленник может:
♦ подделать подпись для выбранного им документа;
♦ подобрать документ к данной подписи, чтобы подпись к нему подходила;
♦ подделать подпись для хоть какого-нибудь документа;
♦ подменить открытый ключ (см. подразд. "Управление ключами" разд. 2.2) на свой собственный, выдавая себя за владельца;
♦ обманом заставить владельца подписать какой-либо документ, например, используя протокол слепой подписи;
♦ подписать любой документ от имени владельца ключа, если закрытый ключ уже украден.
При использовании надежной хэш-функции вычислительно сложно создать поддельный документ с таким же хэшем, как и у подлинного. Однако эти угрозы могут реализоваться из-за слабостей конкретных алгоритмов хэширования, подписи или ошибок в их реализациях.
RSA как фундамент ЭЦП
Не секрет, что наибольшую популярность среди криптоалгоритмов цифровой подписи приобрела RSA (применяется при создании цифровых подписей с восстановлением документа).
На начало 2001 года криптосистема RSA являлась наиболее широко используемой асимметричной криптосистемой (криптосистемой открытого ключа) и зачастую называется стандартом де факто. Вне зависимости от официальных стандартов существование такого стандарта чрезвычайно важно для развития электронной коммерции и вообще экономики. Единая система открытого ключа допускает обмен документами с электронно-цифровыми подписями между пользователями различных государств, приминяющими различное программное обеспечение на различных платформах; такая возможность насущно необходима для развития электронной коммерции.
Распространение системы RSA дошло до такой степени, что ее учитывают при создании новых стандартов. Первым при разработке стандартов цифровых подписей в 1997 году был разработан стандарт ANSI X9.30, поддерживающий Digital Signature Standard (стандарт цифровой подписи). Годом позже был введен ANSI X9.31, в котором сделан акцент на цифровые подписи RSA, что отвечает фактически сложившейся ситуации, в частности для финансовых учреждений.
До недавнего времени главным препятствием для замены бумажного документооборота электронным были недостатки защищенной аутентификации (установления подлинности); почти везде контракты, чеки, официальные письма, юридические документы все еще выполняются на бумаге.
Появление цифровой подписи на основе RSA сделало осуществление электронных операций достаточно безопасным и надежным.
Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. Как было уже сказано выше, в этом алгоритме используется два ключа – открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое количество субъектов (N) должно общаться по схеме "все-со-всеми". В случае симметричной схемы шифрования каждый из субъектов каким-то образом должен доставить свои ключи всем остальным участникам обмена, при этом суммарное количество используемых ключей будет достаточно велико при большом значении N. Применение асимметричного алгоритма требует лишь рассылки открытых ключей всеми участниками, суммарное количество ключей равно N.
Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M) , и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n = pq и число d, c (d, p – 1) = (d, q – 1) = 1 (один из возможных способов выполнить это условие – выбрать d больше, чем p/2 и q/2). Шифрование производится по формуле: f(M) = Md х mod n, где M и f(M) оба < n – 1 . Оно может быть вычислено за разумное время, даже если M, d и n содержат весьма большое количество знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. Если dc ≡ (p_1)1, тогда (Md)e ≡ p1.
Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.
Аналогично (Md)e ≡ qM, если dc ≡ (q_1)1. е удовлетворяет этим двум условиям, если cd ≡ (p_1)(q_1)1. Мы можем позволить е = x, когда x является решением уравнения dx + (p – 1)(q – 1)y = 1.
Так как (Md)e – M делимо на p и q, оно делимо и на pq. Следовательно, мы можем определить M, зная Md, вычислив его значение в степени е и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, нельзя было вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором приблизительно 1050 комбинаций. Данная проблема изучается уже около 100 лет.
Теоретически можно предположить, что возможно выполнение операции f-l без вычисления p и q. Но в любом случае задача эта непроста, и разработчики считают ее трудно факторизуемой.
Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M и хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно – надо знать все возможные значения Mi.
Проясним использование алгоритма RSA на конкретном примере. Выберем два простых числа p = 7; q = l7 (на практике эти числа во много раз длиннее). В этом случае n = pq будет равно ll9. Теперь необходимо выбрать е. Выберем е = 5. Следующий шаг связан с формированием числа d, так чтобы de = 1 х mod [(p – 1)(q – 1)]. d = 77 (использован расширенный алгоритм Евклида). d – секретный ключ, а е и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать, представляется M = 19. С = Me х mod n. Получаем зашифрованный текст C = 66. Этот "текст" может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М = Cd х mod n и C = 66. В результате получается M = 19.
На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату.
Возможно ли взломать ЭЦП?
Взлом ЭЦП фактически сводится к взлому алгоритма шифрования. В данном случае возможные варианты взлома мы рассмотрим на примере алгоритма RSA.
Существует несколько способов взлома RSA. Наиболее эффективная атака – найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель) нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n. Безопасность RSA зависит от разложения на сомножители (факторинга), что является трудной задачей, не имеющей эффективных способов решения.
Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот: можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.
