Современные методы цифровой подписи

Архив

Суть цифровой подписи состоит в том, что для гарантированного подтверждения подлинности информации, содержащейся в электронном документе, а также для возможности неопровержимо доказать третьей стороне (партнеру, арбитру, суду и т. п.), что электронный документ был составлен именно конкретным лицом или по его поручению и именно в том виде, в котором он предъявлен, автору документа предлагается выбрать свое индивидуальное число (называемое обычно индивидуальным ключом [1], паролем, кодом и т. д.) и каждый раз для "цифрового подписывания" сворачивать (замешивать) этот свой индивидуальный ключ, хранимый в секрете от всех, с содержимым конкретного электронного документа. Результат такого "сворачивания" - другое число - может быть назван цифровой подписью данного автора под данным конкретным документом.

Постановка задачи

Для практического воплощения этой идеи требовалось найти конкретные и конструктивные ответы на следующие вопросы:

- Как "замесить" содержание документа с индивидуальным ключом пользователя, чтобы они стали неразделимы?

- Как проверить, что содержание подписываемого документа и индивидуальный ключ пользователя подлинные, не зная заранее ни того, ни другого?

- Как обеспечить возможность многократного использования автором одного и того же индивидуального ключа для цифрового подписывания большого числа электронных документов?

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

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

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

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

Рассмотрим эти ответы подробнее. Основная идея Диффи и Хеллмана состояла в том, чтобы искать ответы на первые четыре вопроса (математические) из списка по следующей схеме:

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

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

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

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

Самым сложным из этих условий является, конечно же, гарантирование невозможности восстановления ключа подписывания по ключу проверки и любому количеству подписанных электронных документов. На сегодня лучший из предложенных способов его выполнения состоит в том, чтобы использовать такие процедуры подписывания и проверки, что практическое восстановление ключей подписи по ключам проверки требует решения известной сложной вычислительной задачи [2]. Поскольку задача является общеизвестно сложной (если ее до сих пор не научились решать за обозримое время), то есть надежда, что ее не сумеют решить быстро и в ближайшем будущем.

Практический результат двадцатилетних научных поисков таких задач оказался до некоторой степени парадоксальным: при всем многообразии известных сложных вычислительных задач практически применимой оказалась одна - так называемая задача дискретного логарифмирования. В простейшем варианте ее можно сформулировать так. Если заданы три больших целых положительных числа a, n, x, то, располагая даже несложными вычислительными устройствами типа карманного калькулятора или просто карандашом и бумагой, можно довольно быстро вычислить число a^x как результат умножения числа a на себя x раз, а затем и остаток от деления этого числа нацело на n, записываемый как b = a^x mod n. Задача же дискретного логарифмирования состоит в том, чтобы по заданным числам a, b, n, таким, что b = a^x mod n, найти x.

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

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

Далее, если взломщик располагает вычислительной системой общей мощностью, скажем, 1 миллиард (10⁹) операций в секунду, а это мощность современного суперкомпьютера типа Cray-3, то

- за сутки непрерывной работы такой системы может быть решена задача сложностью около 100 триллионов (или 10¹⁴) операций,

- за месяц - около 3.10¹⁵,

- за год - около 3.10¹⁶,

- за десять лет - около 3.10¹⁷,

- за тридцать лет - около 10¹⁸ операций.

Таким образом, даже если допустить, что потенциальный взломщик цифровой подписи располагает вычислительной системой, эквивалентной по мощности тысяче (10³) суперкомпьютеров типа Cray-3, на выполнение вычислений объемом 10²¹ операций ему потребовалось бы не менее тридцати лет непрерывной работы системы, а значит, цифровая подпись с надежностью не менее 10²¹ может считаться практически неподделываемой.

В этом месте автору обычно задают вопрос: "А что, если специальным службам известны более быстрые методы решения задачи фальсификации цифровых подписей?" В настоящее время ответ на него оказывается довольно простым. Если вы боитесь, что обычно предлагаемого при длине ключей 64 байта запаса надежности в 10¹⁸-10²¹ недостаточно, применяйте алгоритмы с более длинными ключами. Современные процессоры класса Intel 486 и Pentium позволяют за доли секунды вычислять и проверять цифровые подписи с ключами длиной до 512 байт, а стойкость большинства широко применяемых методов цифровой подписи при такой длине ключей заведомо превосходит все разумные требования (более чем 10⁵⁰) [3]. Итак, мы видим, что современные общепризнанные принципы построения системы цифровой подписи просты и изящны:

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

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

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

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

Алгоритмы: американские разработки

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

Для удобства оценки основных свойств того или иного алгоритма мы будем сравнивать его основные характеристики:

- длину ключей,
- длину цифровой подписи,
- сложность (время) вычисления,
- сложность (время) проверки подлинности цифровой подписи,

при условии, что уровень стойкости подписи по отношению к любым методам фальсификации не ниже 10²¹. За "базовую" длину ключей и длину самой цифровой подписи примем 64 байта.

RSA - первый алгоритм цифровой подписи, который был разработан в 1977 году в Массачусетском технологическом институте. RSA основывается на том, что задача дискретного логарифмирования при выборе целого параметра n в виде произведения двух различных простых чисел примерно равных по порядку величины (то есть n = pq) становится не менее сложной, чем разложение n на эти простые множители, а последняя задача давно (еще со времен Архимеда и Евклида) известна в математике как сложная.

По современным оценкам сложность задачи разложения на простые множители при целых числах n из 64 байт составляет порядка 10¹⁷-10¹⁸ операций, то есть находится где-то на грани досягаемости для серьезного взломщика. Поэтому обычно в системах цифровой подписи на основе алгоритма RSA применяют более длинные целые числа n (обычно от 75 до 128 байт). Это приводит к увеличению длины цифровой подписи относительно 64-байтного варианта примерно на 20-100% (в данном случае ее длина совпадает с длиной записи числа n), а также от 70% до 800% увеличивает время вычислений при подписывании и проверке.

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

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

EGSA. Существенным шагом вперед был алгоритм цифровой подписи, предложенный в 1984 году [4] Тагиром Эль Гамалем (Tahir ElGamal). В этом алгоритме целое число n полагается равным специально выбранному большому простому числу p, по модулю которого и производятся все вычисления. Такой выбор позволяет повысить стойкость подписи при ключах длиной 64 байта примерно в 1000 раз, то есть при такой длине ключей обеспечивается уровень стойкости порядка 10²¹. Правда, при этом длина самой цифровой подписи увеличивается в два раза и составляет 128 байт.

Главная "заслуга" алгоритма Эль Гамаля в том, что он послужил основой для принятия нескольких стандартов цифровой подписи, в том числе национального стандарта США DSS, введенного в действие 1 декабря 1994 года, и государственного стандарта РФ ГОСТ Р 34.10, введенного с 1 января 1995 года.

DSA. В 1991 году Национальный институт стандартов и технологий США разработал на основе алгоритма Эль Гамаля и представил на рассмотрение Конгресса новый алгоритм цифровой подписи, получивший название Digital Signature Algorithm (DSA). Алгоритм DSA, ставший в дальнейшем основой национального стандарта США на цифровую подпись, имеет ряд преимуществ перед RSA:

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

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

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

Главным мотивом для принятия в 1994 году в США национального стандарта цифровой подписи (DSS) на основе алгоритма Эль Гамаля послужили эти преимущества, а также соображения, связанные с возможностью его реализации любым разработчиком свободно, не заключая коммерческих лицензионных соглашений с держателем патента компанией RSA Data Security. Свою роль сыграла и возможность свободного безлицензионного экспорта такой технологии из США: технологию цифровой подписи RSA можно "обернуть", поменяв местами процедуры подписывания и проверки, и получить готовый метод шифрования информации с открытыми ключами, а технологии шифрования информации при экспорте из США требуют получения специального разрешения Госдепартамента, который согласовывает решения по вопросам экспорта криптографии с Агентством национальной безопасности (АНБ) - главной криптографической службой США, выступавшей и продолжающей категорически выступать против экспорта криптографических технологий вообще [5].

Такое решение отнюдь не было очевидным, поскольку RSA, как наиболее известный алгоритм цифровой подписи и шифрования с открытым ключом, был гораздо шире распространен, практически опробован во многих странах и признан в качестве стандарта de facto большинством разработчиков операционных систем, сетевых технологий и прикладного программного обеспечения. Его популярность объясняется, во-первых, тем, что он появился на восемь лет раньше, во-вторых, значительно более широкой известностью в научных кругах как самого алгоритма, так и его авторов, и наконец, успешным бизнесом держателя патента - компании RSA Data Security (Эль Гамаль был в 1994-95 гг. ее сотрудником).

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

По сравнению с оригинальным алгоритмом Эль Гамаля метод DSA имеет одно важное преимущество: при заданном в стандарте уровне стойкости числа, участвующие в вычислении подписи, имеют длину 20 байт, сокращая общую длину подписи до 40 байт. Поскольку большинство операций при вычислении подписи и ее проверке также производится по модулю из 20 байт, сокращается время вычисления подписи и объем используемой памяти. В алгоритме Эль Гамаля длина подписи при таком уровне стойкости была бы равна 128 байт.

Цифровая подпись на практике Описанный в статье класс примитивов цифровой подписи (в качестве таких примитивов выступают алгоритм формирования подписи и алгоритм проверки подписи), вообще говоря, позволяет подписать текст (и любые другие данные, представимые в форме числа) любого размера. Однако на практике - по соображениям удобства реализации и производительности - бывает полезно ограничить размер объекта, к которому применяются эти преобразования, некоторой фиксированной, известной заранее величиной. Поэтому практически используемые (и стандартизуемые) протоколы цифровой подписи включают еще один примитив, называемый криптостойким хэшированием. Хэширующей функцией (или хэшем, или функцией расстановки, как иногда называют такие функции в отечественной литературе) называется функция, преобразующая число произвольной длины в число фиксированной длины, обычно - с равномерным распределением результата по множеству возможных значений, чтобы минимизировать так называемые коллизии - одинаковый результат функции, примененной к различным аргументам. К криптостойкому хэшированию предъявляется дополнительное требование: эта функция должна быть труднообратимой, чтобы по известному ее значению было трудно найти соответствующие аргументы. Самый распространенный метод хэширования - применение к объекту стойкого блочного шифра в особом режиме. Поскольку блочное шифрование - симметричный (одноключевой) примитив, а сама цифровая подпись - асимметричный, такой протокол в целом называют гибридным. Протокол в целом выглядит таким образом. А - Сторона А генерирует хэш от подписываемого объекта. Б - Сторона А применяет примитив формирования подписи к результату хэширования. В - Сторона А передает объект и подпись стороне Б. Г - Сторона Б генерирует хэш от полученного объекта. Д - Сторона Б применяет примитив проверки подписи к результату хэширования и полученной подписи. Анализ стойкости гибридных протоколов более сложен, чем анализ стойкости примитива подписи, поскольку атака (попытка подделки подписи) может осуществляться как на примитив подписи, так и на примитив хэширования. Если мы сформируем отдельный объект из результата хэширования и подписи, окажется, что он обладает интересными свойствами: третья сторона, не видя некого исходного объекта, может засвидетельствовать, что этот самый объект был подписан обладателем определенного ключа. Это может быть полезным, например, для нотариального подтверждения времени подписания определенного документа конфиденциального содержания. - М.О.

Алгоритмы: российские разработки

Нотариус. В 1991 году самым распространенным персональным компьютером в СССР был AT/286 12 МГц, и мы в своих ранних алгоритмических разработках должны были максимально упростить лучшие из известных тогда алгоритмов цифровой подписи, чтобы их программная реализация позволяла вычислять и проверять подпись под электронными документами за разумное время, скажем, 1-2 секунды, при размере документа до 10 Кбайт. Упрощения, конечно, не должны были снижать стойкости алгоритма.

Первым результатом нашей работы был созданный в конце 1992 года аналог алгоритма Эль Гамаля "Нотариус-1". Главное отличие "Нотариус-1" состояло в том, что вместо обычной операции умножения целых чисел по модулю большого простого p, как это делается у Эль Гамаля, в нем использовалась похожая операция, которая, обеспечивая точно такой же уровень стойкости, что и умножение по модулю простого числа, гораздо эффективнее выполнялась на распространенных процессорах Intel, Motorola и др.

Затем аналогичным образом был усовершенствован алгоритм DSA, который послужил основой для алгоритма цифровой подписи, названного "Нотариус-D". Реализация этого алгоритма на процессоре Intel 486DX4/100 позволила довести время подписывания электронного документа объемом 1 Кбайт вместе с предварительной обработкой перед подписыванием (так называемым хэшированием) до 0,014 с, а время проверки подписи - до 0,027 с. Для документа объемом 100 Кбайт время подписывания составляет 0,124 с., время проверки - 0,138 с. Длина подписи 40 байт, стойкость - 10²¹.

Совместное использование наших идей и идей немецкого криптографа Клауса Шнорра (Klaus Shnohrr), предоставившего нам право использования своего алгоритма на территории стран СНГ, привело к разработке в 1996 году усовершенствованного алгоритма "Нотариус-S", который при сохранении стойкости подписи позволил сократить ее длину еще на 32,5%. Для базового варианта с ключами из 64 байт длина подписи сократилась относительно DSA и "Нотариуса-D" с 40 до 27 байт. Соответственно уменьшилось время вычисления и проверки подписи.

Эти алгоритмические разработки позволили нам предложить пользователю широкий выбор программ с длинами цифровой подписи от 16 до 63 байт и уровнями стойкости соответственно от 10¹⁴ (или несколько дней работы сети из нескольких десятков персональных компьютеров) до 10⁵⁴ (или более 100 млрд. лет непрерывной работы любой мыслимой вычислительной системы обозримого будущего).

Автор надеется, что детальные технические характеристики "Нотариус-S", DSA и ГОСТ 34.10, приведенные в табл. 1., дадут читателю возможность оценить основные качества алгоритмов без дальнейших пространных комментариев. Пояснений требуют лишь графы, посвященные алгоритму ГОСТ 34.10.

ГОСТ 34.10. Стандарт на электронную подпись ГОСТ34.10 был опубликован Госстандартом РФ в мае 1994 года и вступил в действие с 1 января 1995 года. В предварительном варианте он был введен как ведомственный стандарт на цифровую подпись ЦБ РФ и использовался в этом качестве с сентября 1993 года по декабрь 1994 года. Алгоритмы вычисления и проверки подписи в ГОСТ 34.10 устроены аналогично алгоритму DSA, но хэширование выполняется другим, существенно более медленным способом. К сожалению, разработчики допустили целый ряд ошибок, которые есть даже в официальном тексте стандарта. Поэтому при реализации следует быть внимательным и не всегда следовать формальному тексту.

Сертификация и лицензирование

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

В США лаборатории, аккредитованные Национальным институтом стандартов и технологий, проводят тестирование процедуры порождения простых чисел, определяющих параметры алгоритма DSA, на основании опубликованных в тексте стандарта конкретных значений параметров и начальных установок процедуры генерации простых чисел; затем при тестовых значениях параметров алгоритма, тестовых индивидуальных ключах и тестовых рандомизирующих значениях подписывания производится вычисление и проверка цифровых подписей под тестовыми примерами электронных документов. Таких циклов тестирования может быть довольно много - до нескольких десятков тысяч. Результаты предъявляются лаборатории для сравнения с результатами работы эталонной программы на таких же значениях входных параметров, после чего дается заключение о соответствии данной реализации цифровой подписи стандарту. Подобным образом происходит сертификация программ цифровой подписи и в ряде западноевропейских стран.

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

Больше соответствующий мировой практике и более логичный подход проявляется при сертификации в рамках Гостехкомиссии РФ программ цифровой подписи в классе программных средств защиты информации от несанкционированного доступа и изменения. Согласно руководящим документам ГТК, программные или аппаратные средства, реализующие технологию цифровой подписи, могут быть объективно оценены на предмет соответствия конкретным официально опубликованным требованиям по степени защиты информации от несанкционированного изменения.

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

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

---

1 (обратно к тексту) - Единообразная терминология в области криптографии с открытым ключом не сформировалась еще не только в русскоязычной, но и в гораздо более обширной англоязычной литературе. Здесь "индивидуальный ключ подписывания" - то, что чаще всего называют private key ("закрытым ключом"), - число, известное только ассоциированному с ним пользователю ("владельцу", "держателю" ключа) и доступное только оборудованию или ПО, которому пользователь доверяет. Соответствующий "ключ проверки" - public key ("открытый ключ" - отсюда "криптография с открытым ключом") - может быть известен всем корреспондентам владельца соответствующего закрытого ключа или вообще доступен публично. - М.О.

2 (обратно к тексту) - "Сложная" здесь и далее означает не логическую сложность алгоритмизации решения задачи, а вычислительную сложность ("трудность", "трудоемкость") решения задачи при использовании лучшего известного алгоритма. - М.О.

3 (обратно к тексту) - Это рассуждение проведено при достаточно сильном допущении фиксированной вычислительной мощности. Если мы зафиксируем не вычислительную мощность, а бюджет злоумышленника, картина будет менее оптимистичной: закон Мура подсказывает, что мощности, которыми располагает злоумышленник, растут по экспоненте от времени. При разработке систем высокой (десятки лет) стойкости разумнее ориентироваться на термодинамические ограничения Вселенной. Выкладки оставляем заинтересованному читателю, заметив только, что эти ограничения распространяются на все возможные технологии детерминированных вычислений (в том числе самые экзотические, например биовычисления), но могут оказаться неприменимыми, если будет продемонстрирована реалистичность масштабных квантовых вычислений. - М.О.

4 (обратно к тексту) - В технической документации и маркетинговой литературе подпись "по Эль Гамалю" часто ошибочно именуют "подписью по Диффи-Хеллману". Хотя разработка Эль Гамаля использует аппарат, сформулированный в работах Диффи и Хеллмана, именно он первым показал, как практически использовать этот аппарат для формирования и проверки стойких цифровых подписей. - М.О.

5 (обратно к тексту) - Этот мотив, видимо, теряет свое значение с либерализацией экспортного режима властями США. В качестве курьеза стоит отметить, что большинство средств разработки, предназначенных "только для подписи" и реализующих алгоритм DSA, которые всегда свободно экспортировались из США, можно, немного подумав, легко использовать и для стойкого (хотя и не слишком эффективного с точки зрения производительности) шифрования.- М.О.

---

Анатолий Лебедев - президент компании "ЛАН Крипто" (www.lancrypto.com). Член Международной ассоциации криптологических исследований (IACR, www.iacr.org) и один из основателей Российской криптологической ассоциации (www.communiware.ru/ruscrypto), автор многочисленных научных и популярных работ в области информатики и криптологии.