Российский стандарт цифровой подписи: эволюция, современность и перспективы

Предыстория

Теоретическое решение задачи аутентификации автора цифрового сообщения предложили в 1976 г. американские математики У. Диффи и М. Хеллман в знаменитой статье [2]. Одна из первых практических реализаций схемы цифровой подписи [11] была предложена Р. Ривестом, А. Шамиром и Л. Адлеманом в 1977 г. Эта схема, основанная на предположении о сложности задачи факторизации целых чисел и известная как RSA, получила широчайшее распространение.

В 1984 г. в своей работе [4] Т. Эль-Гамаль предложил изящную конструкцию цифровой подписи с использованием хеш-функции и рандомизацией (см. рис. 1). Всего в обобщенной схеме Эль-Гамаля существует 12 вариантов уравнения подписи и соответствующего ему уравнения проверки. Один из вариантов схемы, где G - подгруппа простого порядка q группы (Z/pZ)*, lpl=1024, lql=160, h=SHA1, стал национальным стандартом США (DSA) в 1991 г.

Отметим, что существуют и другие схемы подписи: например схема Шнорра, NTRUsign, ESIGN. Часть из них принята в качестве национальных и отраслевых стандартов, однако по распространенности они уступают схемам RSA и DSA.

Как подделывают подпись

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

• найти сообщение M, такое, что h(M)=h(M₀) для некоторого сообщения Mo, подпись которого известна (задача построения второго прообраза для используемой в схеме хеш-функции);
• найти сообщения M, M₀, такие, что подпись M₀ известна или может быть получена от владельца секретного ключа и при этом h(M)=h(M₀) (задача построения коллизии хеш-функции);
• определить ключ выработки подписи по ключу проверки и параметрам схемы.

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

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

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

Например, задача компрометации схемы RSA может быть сведена к решению задачи факторизации целых чисел: по N=pq определить p, q. Для криптоанализа схемы Эль-Гамаля необходимо решить задачу дискретного логарифмирования в циклической группе G=<g>: по элементу группы y найти число x, такое, что gx=y.

На момент публикации системы RSA задача факторизации считалась "экстремально" сложной. Так, в оригинальной статье [11] предлагался пример - открытый ключ длиной 429 бит, а время, необходимое для его компрометации известными в то время методами, оценивалось авторами величиной в несколько квадриллионов лет! Однако уже в 1994 г. соответствующий секретный ключ был определен при помощи нового варианта метода квадратичного решета, а появившийся затем метод решета числового поля позволяет в настоящее время успешно раскладывать на множители числа длиной 768 бит [8].

При этом теоретическая трудоемкость факторизации числа N простейшим методом - перебором всех возможных делителей - равна O (N^1/2) операций, а трудоемкость оптимального варианта метода решета числового поля оценивается субэкспоненциальной функцией

LN(s,c)=exp[(c+o(1 ))(lgN)^s (lglgN)^(1-s)],

где s=1/3, c=1.923, которая асимптотически растет быстрее любой полиномиальной функции (т.е. произвольного многочлена от lgN), но медленнее любой функции вида f(N)=N^t, t>0.

Вслед за развитием методов криптоанализа менялись и требования к параметрам стойкости схемы RSA. Так, считавшиеся стойкими на заре ее внедрения 512-битовые ключи быстро уступили место 1024битовым, а в настоящее время минимально допустимой длиной ключа считается 3072 бит.

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

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

Цифровая подпись в России. История и принципы синтеза

К 1994 г. экономические преобразования и интенсивное развитие цифровых коммуникационных сетей в России потребовали создания собственной схемы цифровой подписи. Следуя сложившейся в среде отечественных криптографов традиции по использованию проверенных и хорошо зарекомендовавших себя синтезных решений, в качестве национального стандарта ГОСТ Р 34.10-94 был принят вариант обобщенной схемы Эль-Гамаля, реализованный в подгруппе мультипликативной группы конечного простого поля. Характеристика поля p имела размер около 1024 бит, порядок подгруппы - размер 256 бит, использовалась хеш-функция с длиной хеш-кода 256 бит, определенная в ГОСТ Р 34.11-94, а уравнение подписи соответствует {u,v,w}={s,r,h(M)}.

Методы дискретного логарифмирования, известные на начало 1990-х гг., позволяли считать такой выбор параметров обоснованным. Однако в дальнейшем метод решета числового поля, разработанный для факторизации, был адаптирован для логарифмирования в конечных полях, при этом, как показано в работах зарубежных специалистов (Д. Вебер [15], А. Жу, Р. Лерсье [6]) и отечественных ученых (Д.В. Матюхин [18], И.А. Семаев [13]), теоретическая оценка его трудоемкости сохраняется. Рекордный размер решенной задачи составляет 596 бит. Еще более впечатляющих успехов добились исследователи задачи логарифмирования в полях малой характеристики GF(Q), Q=pⁿ, понизив теоретическую оценку трудоемкости до L_Q(1/4,c) [7] и решив задачи размером 1279 бит [9] для простого n и 6168 бит для составного n.

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

Эллиптическая кривая Е в краткой форме Вейерштрасса над конечным простым полем характеристики p>3 - это множество точек {(x,y)} - решений уравнения

y²=x³+ax+b (mod p),

к которому добавлена бесконечно удаленная точка O. Введя на этом множестве простой и изящный закон сложения, проиллюстрированный на рис. 2, 3, получим абелеву группу, где точка O служит нулем. Порядок этой группы оценивается теоремой Хассе:

lp+1-#EI< 2p^1/2,

он может быть точно вычислен при помощи достаточно эффективного алгоритма Шуфа-Элкиса-Аткина.

Эллиптические кривые связаны со многими задачами как теоретического (например, великая теорема Ферма), так и прикладного характера, их свойства интенсивно исследуются еще со времен Л. Эйлера. В 1986 г. американские криптографы Н. Коблиц и В. Миллер независимо предложили использовать группу точек эллиптической кривой для реализации асимметричных криптографических схем. Лучшим алгоритмом для решения задачи дискретного логарифмирования в этой группе является параллельный метод поиска коллизий [14], трудоемкость его в общем случае имеет экспоненциальную оценку O(#E)1/2 операций, а рекордный размер решенной задачи [16] составляет 113 бит. Поэтому переход от конечных полей к эллиптическим кривым позволяет при сохранении заданного уровня стойкости значительно уменьшить размеры параметров криптографической схемы.

Существуют, однако, "слабые" классы кривых (аномальные, суперсингулярные и кривые с малой MOV-степенью [10]), для которых задача логарифмирования может быть сведена к логарифмированию в некотором расширении поля GF(pl). Такие кривые легко выявляются и отбраковываются при создании криптографических схем.

Итак, с принятием второй редакции стандарта ГОСТ Р 34.10-2001 цифровая подпись была переведена на "эллиптические рельсы", при этом ее принципиальная схема была сохранена, равно как и используемая хеш-функция. Стойкость обновленной отечественной схемы цифровой подписи обеспечивалась выбором эллиптических кривых, имеющих простую подгруппу мощности q, где 2²⁵⁴<q<2²⁵⁶. Дополнительно на кривые накладывались требования, исключающие возможность сведения задачи дискретного логарифмирования на кривой к более простой задаче логарифмирования в конечном поле.

В 2010 г. правильность выбранного решения была подтверждена на весьма высоком уровне: отечественная схема вошла в международный стандарт ISO/IEC 14888-3 под названием EC-RDSA (Elliptic Curve Russian Digital Signature Algorithm).

Через десять лет настало время очередного обновления стандарта. Новая функция хеширования "Стрибог", определенная в стандарте ГОСТ Р 34.11-2012, имела два варианта длины хеш-кода: 256 и 512 бит. Поэтому третья редакция стандарта цифровой подписи ГОСТ Р 34.10-2012, введенная в действие с 1 января 2013 г., сохранила хорошо зарекомендовавшую себя схему и была дополнена возможностью использования эллиптических кривых с 2⁵⁰⁸<q<2⁵¹².

Современность и перспективы

Основным конкурентом отечественной схемы цифровой подписи в борьбе за умы пользователей и разработчиков является американский стандарт FIPS 186-4 (4 редакция). В силу исторически сложившихся обстоятельств именно схемы (см. таблицу), описанные в этом стандарте, получили наибольшее распространение.

Прежде всего напомним, что для анализа схем RSA и DSA известны субэкспоненциальные алгоритмы, поэтому в отечественной практике они не используются. Схема RSA, кроме того, имеет специфическую уязвимость: известны методы факторизации, позволяющие при наличии частичной информации о секретном ключе полностью восстановить его за полиномиальное время. Так, в течение 2012-2014 гг. появился цикл статей [2, 6, 13], показавших, что до 0,5% всех 1024-битовых ключей реализаций RSA, развернутых в реальном мире, могут быть скомпрометированы.

Кривые над полями характеристики 2, не используемые отечественным стандартом, имеют некоторые привлекательные особенности, прежде всего это возможность эффективной реализации. Однако новые теоретические разработки и практические рекорды позволяют предполагать, что в перспективе появится субэкспоненциальный алгоритм для логарифмирования на этих кривых. Даже АНБ США более не рекомендует использовать такие кривые.

Американский стандарт фиксирует 15 конкретных эллиптических кривых. Российский стандарт не содержит фиксированных кривых, но требует выполнения несложно проверяемых условий, обеспечивающих защиту от всех известных криптоаналитических атак. Конкретные параметры, используемые для облегчения взаимодействия реализаций разных производителей, содержатся в методических документах, выпускаемых ТК 26.

Отечественным ученым Н.Э. Варновским было построено теоретическое доказательство стойкости национальной схемы цифровой подписи в модели с защищенным модулем [17]. Для схем DSA и EC-DSA известны доказательства стойкости лишь в более слабых моделях случайного оракула и генерической группы.

Таким образом, заложенные в схему цифровой подписи ГОСТ Р 34.10-2012 синтезные решения обеспечивают уровень криптографической стойкости, достаточный для защиты данных в обозримом будущем (см. рис. 4).

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

Рассматривая эксплуатационные характеристики отечественной схемы, необходимо прежде всего упомянуть ее существенное превосходство над RSA. Так, при равном уровне стойкости (256 бит для ГОСТ Р 34.102012 и 3072 бит для RSA) проверка подписи в обеих схемах выполняется с одинаковой скоростью, а вот выработка подписи согласно ГОСТ (без учета хеширования) потребует в 40-120 раз меньше времени.

В качестве возможного подхода к оптимизации реализации отечественной схемы в статье экспертов ТК 26 [3] рассматривается использование современных алгоритмов вычисления кратной точки, а также альтернативных алгебраических моделей эллиптических кривых. Например, множество решений уравнения

ex²+y²=1+dx²y² (mod p)

при некоторых условиях на параметры e, d также задает эллиптическую кривую, которая называется скрученной кривой Эдвардса. Она обладает красивым и эффективным законом сложения, использование которого может дать прирост производительности до 25% по сравнению с кривыми в краткой форме Вейерштрасса. Специалистами ТК 26 подготовлены методические документы, регламентирующие возможность использования скрученных кривых Эдвардса в ГОСТ Р 34.10-2012.

Разработанная в [3] реализация позволила добиться на типовом 16-ядерном сервере с архитектурой x86-64 при частоте ЦП около 3 ГГц производительности в 4700-6000 операций выработки подписи и 30003700 проверок в секунду в зависимости от модели эллиптической кривой.

Реализация, представленная в [19], достигает на аналогичном сервере быстродействия в 3500 и 1900 операций выработки и проверки подписи соответственно, но учитывает требования по защите от атак с использованием побочных каналов, и в этом смысле указанный результат ближе к практике.

Таким образом, национальный стандарт цифровой подписи зарекомендовал себя как стойкая и производительная схема. Являясь частью семейства стандартов ГОСТ Р 34 "Криптографическая защита информации", он позволяет создавать надежные и эффективные решения в интересах самого требовательного пользователя - как частных лиц, так и всего государства.

Дополнительную информацию о схеме цифровой подписи, в том числе методические документы, регламентирующие особенности ее практического применения, можно найти на сайте Технического комитета по стандартизации ТК 26 (www.tc26.ru).

Литература

1. Bernstein D.J. et al. Factoring RSA keys from certified smart cards: Coppersmith in the wild. - 2013. - http://eprint.iacr.org/ 2013/599.
2. Diffie W., Hellman M. New directions in cryptography// IEEE Trans. Inform. Theory. - 1976. - 22. - P. 644-654.
3. Dygin D., Grebnev S. Efficient implementation of the GOST R 34.10 digital signature scheme using modern approaches to elliptic curve scalar multiplication // Мат. вопр. криптографии. - 2013. - 4. - 2. - P. 47-58.
4. ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // Advances in Cryptology - CRYPTO'84. - 1984. - P. 10-18.
5. Heninger N.et al. Mining your Ps and Qs: Detection of widespread weak keys in network devices // Proceedings of the 21st USENIX Security Symposium. - August, 2012.
6. Joux A., Lercier R. Improvements to the general number field sieve for discrete logarithms in prime fields // Math. Comp. - 2003. - 72. - 242. - P. 953-967.
7. Joux A. A new index calculus algorithm with complexity L(1/4) in small characteristic. - 2013. - http://eprint.iacr.org/2013/095.
8. Kleinjung T. et al. Factorization of a 768-bit RSA modulus. - 2010. - http://eprint.iacr.org/2010/006.
9. Kleinjung T. Discrete Logarithms in GF(2¹²⁷⁹). NMBRTHRY list.
10. Menezes A.J., Okamoto T., Vanstone S.A. Reducing elliptic curve logarithms to logarithms in a finite fields// IEEE Trans. Inf. Theory. - 1993. - 39. - P. 16391646.
11. Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Comm. ACM. - 1978. - 21. - 2. - P. 120-126.
12. Lenstra A.K.et al. Ron was wrong, Whit is right. - 2012. - http://eprint.iacr.org/2012/064.
13. Semaev I. A. A generalization of the number field sieve // Proc. Probabilistic Methods in Discrete Mathematics. - Utrecht-Tokyo: VSP. - 1997. - P. 45-63.
14. Van Oorschot P., Wiener M. Parallel collision search with cryptanalytic applications // J. Cryptology. - 1999. - 12. - 1. - P. 1-28.
15. Weber D. On the computation of discrete logarithms in finite prime fields: PhD thesis. - Saarbrucken, Univ. des Saarlandes. - 1997.
16. Wenger E., Wolfger P. Announcement: New 113-bit ECDLP record.
17. Варновский Н.П. Стойкость схем электронной подписи в модели с защищенным модулем // Дискретная математика. - 2008. - 20. - 3. - С. 147-159.
18. Матюхин Д.В. Об асимптотической сложности дискретного логарифмирования в поле GF(p) // Дискретная математика. - 2003. - 15. - 1. - С. 28-49.
19. Смышляев С.В., Алексеев Е.К., Агафьин С.С. Российская криптография: так ли все грустно? - PHDays V. - 2015.