Описанные гибридные методы шифрования и цифровой подписи сочетают в себе эффективность алгоритмов с симметричным ключом и свойство независимости от дополнительных секретных каналов для передачи ключей, присущее алгоритмам с открытым ключом. Криптографическая стойкость конкретного гибридного метода определяется стойкостью слабейшего звена в цепи, состоящей из алгоритмов с симметричным и с открытым ключом, выбранных для его реализации.
Система RSA
В 1978 г. Р.Ривест, А.Шамир и Л.Адлеман [RSA78] создали первую криптосистему с открытым ключом для шифрования и цифровой подписи, получившую название RSA (по первым буквам фамилий авторов). Система описывается в терминах элементарной теории чисел. Ее надежность обуславливается практической неразрешимостью задачи разложения большого натурального числа на простые множители. Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита - безусловно надежным. Длина подписи в системе RSA совпадает с длиной ключа.
Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, а также задачи разложения на множители к классу NP-полных задач, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов.
Проект DSS
В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], см. также [S94], с.304-314), описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота.
Предлагаемый алгоритм DSA, имеет, как и RSA, теоретико-числовой характер, и основан на криптографической системе Эль-Гамаля [E85] в варианте Шнорра [S89]. Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит.
С момента опубликования проект получил много критических отзывов (см., напр., [R92]), многие из которых были учтены при его доработке. Одним из главных аргументов против DSA является то, что, в отличие от общей задачи вычисления дискретного логарифма, ее частный случай, использованный в данной схеме, мало изучен и, возможно, имеет существенно меньшую сложность вскрытия. Кроме того, стандарт не специфицирует способ получения псевдослучайных чисел, используемых при формировании цифровой подписи, и не указывает на то, что этот элемент алгоритма является одним из самых критичных по криптографической стойкости.
Функции DSA ограничены только цифровой подписью, система принципиально не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи.
Вместе с проектом DSS опубликован проект стандарта SHS (Secure Hash Standard), описывающий однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования вместе с DSA (см. [S94], с.333-336). Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе.
Российский стандарт цифровой подписи
В 1993 г. в России были изданы два государственных стандарта “Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма” и “Функция хэширования”, под общим заголовком “Информационная технология. Криптографическая защита информации”.
Стандарт “Процедуры выработки и проверки электронной цифровой подписи...” во многом схож со своим американским аналогом DSS. Для формирования и проверки цифровой подписи в нем используется тот же алгоритм Эль-Гамаля и Шнорра, что и в DSS, с незначительными модификациями. Имеется две альтернативных длины ключа, 512 и 1024 бит; длина подписи составляет 512 бит.
Для генерации ключей предложен ряд новых алгоритмов. Ключи, получаемые при помощи этих алгоритмов, имеют специальный вид, что потенциально может упростить задачу вскрытия системы по сравнению с DSS. Критика DSS, связанная с недостаточно разработанным теоретическим обоснованием алгоритма, в случае росийского стандарта несколько смягчается тем, что элемент ключа q выбирается более длинным, чем в DSA. Критика. связанная с отсутствием спецификации на способ получения псевдослучайных чисел, остается в силе.
Как и DSS, российский стандарт определяет только алгоритм цифровой подписи, но не шифрования. Быстродействие обоих алгоритмов приблизительно совпадает.
Стандарт “Функция хэширования” предназначен для использования вместе со стандартом “Процедуры выработки и проверки цифровой подписи” и представляет собой оригинальный алгоритм, основанный на методе шифрования с симметричным ключом ГОСТ 28147. Стандарт не содержит криптографического обоснования выбранного алгоритма и не корректирует ГОСТ 28147 в части заполнения узлов замены.
Несмотря на указанные недостатки, система, описанная в российском стандарте, применима во многих областях, особенно для коммерческих приложений.
Программная криптографическая система ТерКрипт
Санкт-петербургским МГП “ТЕРКОМ” разработана криптографическая система ТерКрипт, представляющая собой комплекс программ на языке C стандарта ANSI. Система реализует в полном объеме алгоритмы DES, ГОСТ 28147, RSA, DSS/SHS и российских криптографических стандартов. Алгоритмы реализованы на основе общих процедур теории чисел, использующих современные теоретико-числовые методы для достижения максимальной эффективности. Имеется специальная версия системы, оптимизированная для работы на персональных компьютерах IBM AT 286, 386, 486.
Литература
[BFS91] Th.Beth, M.Frisch, G.J. Simmons (eds.) Public-Key Cryptography: State of the Art and Future Directions. E.I.S.S. Workshop - Oberwolfach, Germany, July 1991 - Final Report. Lecture Notes in Computer Science, V.578.
[DH76] W.Diffie, M.Hellman. New Directions in Cryptography. IEEE Trans. Inform. Theory, IT-22, No.6 (1976), pp.644-654.
[DSS92] The Digital Signature Standard Proposed by NIST. CACM, V.35 (1992), No.7, pp.36-40.
[E85] T.ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Inform. Theory, IT-31 (1985), pp.469-472.
[R92] Responses to NIST’s Proposal. CACM, V.35 (1992), No.7, pp 41-54.
[RSA78] R.L.Rivest, A.Shamir, L.Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM, V.21 (1978), No.2, pp.120-126.
[S94] B.Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C. John Wiley & Sons, Inc., 1994.
[S89] C.P.Schnorr. Efficient Identification and Signatures for Smart Cards. Advances in Cryptology: Proceedings of Crypto’89, G.Brassard (ed). Lecture Notes in Computer Science, V.435, pp.239-251.