АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2002 ГОД

Цифровая подпись

• Все журналы \ Номер 43/214 `2002 от 28.10.2002 \ Цифровая подпись

Роман БРЕЧКО rbrechko@ukr.net

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

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

Общая схема цифровой подписи

Прежде всего стоит сказать, что система цифровой подписи использует криптоситемы, которые базируются на концепции открытого ключа. О них уже рассказывалось на страницах МК в статьях Владимира (Людена) Ю. НЕКРАСОВА «Чтоб никто не догадался» (№ 51-52 (170-171)) и моей собственной «Открытый ключ к закрытой информации» (№ 12-13 (183-184)), поэтому в дальнейшем будем считать, что криптоситемы, базирующиеся на концепции открытого ключа, нам уже известны, и углубляться в них мы в дальнейшем не будем. Также следует сказать, что основной задачей систем цифровой подписи является обеспечение достоверности и конфиденциальности соответствующего сообщения.

Из чего же состоит такая система?

Вероятностный алгоритм или система генерирования ключей. Каждый абонент А получает пару ключей (КА, КА1), где КА — открытый ключ, а КА1 — тайный.

Алгоритм подписывания SIGN, который, используя сообщение М и тайный ключ КА1, выдает некоторое слово S = SIGN(M, KA1). Слово S называется подписью абонента А на сообщении М. В случае, если абонент А хочет послать сообщение М с заверением того, что оно послано именно им, то он отсылает пару (М, S).

Алгоритм проверки подписи CHECK, которым может воспользоваться любой желающий проверить факт, что подпись S на сообщении М принадлежит именно абоненту А — владельцу открытого ключа КА. Если CHECK(M, S, KA) = 1, то проверка подписи считается успешной.

Следует отметить, что для алгоритмов SIGN и CHECK для любого сообщения М и пары ключей КА и КА1 должно выполнятся условие CHECK(KA, M, SIGN(KA1, M)) = 1. Это соотношение определяет корректность системы цифровой подписи.

Надежность системы цифровой подписи обеспечивается тем, что только законный владелец тайного ключа КА1 может для сообщения М сделать такую подпись S, которая прошла бы проверку.

Предложенная схема цифровой подписи была развита американскими математиками Диффи и Гелманом. При этом они утверждают, что любую криптосистему с открытым ключом можно превратить в систему цифровой подписи следующим образом. Пускай Е и D — алгоритмы шифрования и дешифрования соответственно, К и К1 — открытый и тайный ключи. Тогда цифровая подпись ставится по такому правилу: SIGN(M, K1) = DK1(M), а проверку подписи нужно проводить следующим образом: если ЕК(S) = M, то CHECK(K, S) = 1, во всех других случаях CHECK(K, S) = 0.

Итак, рассмотрев общую схему построения цифровой подписи, приступим к описанию конкретных систем цифровой подписи.

Цифровая подпись на основе системы RSA

Напомним, что в криптосистеме RSA каждый абонент сети имеет в своем распоряжении пару ключей: открытый — числа n и e, которые общедоступны, и тайный — число d, который держится в тайне.

Пускай имеем двух абонентов А и В, тогда (ЕA, DA) и (ЕВ, DB) — их алгоритмы шифрования и дешифрования, для которых должно выполняться соотношение: ЕА(DA(M)) = DA(EA(M)) = M и ЕВ(DВ(M)) = DВ(EВ(M)) = M, где М — любое сообщение. Те же соотношения можно записать и в развернутом виде: (M^eA)^dA mod nA = (M^dA)^eA mod nA = M и (M^eВ)^dВ mod nВ = (M^dВ)^eВ mod nВ = M.

Итак, процесс подписывания в данном случае будет происходить следующим образом:

1. Абонент А считает EB(DA(M)) = C и отсылает зашифрованное сообщение С абоненту В.

2. Абонент В считает ЕА(DB(C)) = M.

Корректность данной системы цифровой подписи сводится к соотношению: ЕА(DB(C)) = ЕА(DB(EB(DA(M)))) = EА(DA(M)) = М.

Конфиденциальность этой системы обеспечивает надежность криптосистемы RSA.

Цифровая подпись в системе Эль Гамала

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

Рассмотрим цифровую подпись в системе Эль Гамала, которая базируется на той же идее, что и соответствующая криптосистема.

Процесс генерирования ключей начинается с выбора большого простого числа р, а также числа g (1 < g < p – 1), причем желательно чтобы число g имело достаточно большой порядок. Числа р и g, не будучи тайными, пребывают во всеобщем использовании абонентов сети. Каждый абонент выбирает случайное число а (1 < a < p – 1) и вычисляет h = g^a mod p. Открытым ключом в данном случае будут числа p, g и h, а тайным — число а.

Для того чтобы поставить свою подпись S на открытом сообщении М, абонент А должен выполнить следующие шаги:

1. Выбирается случайное число r (0 < r < q – 1).

2. Вычисляется S1 = g^r mod p.

3. Вычисляется r1 = r^(-1) mod (p –1).

4. Вычисляется S2 = (M – a*S1)*r1 mod (p – 1).

5. В качестве подписи S ставится пара чисел: S = (S1, S2).

Чтобы проверить правильность подписи, абонент В должен проверить выполнение следующего соотношения: g^M = (h^S1)*(S1^S2) mod p.

Система Шнорра

Прежде чем приступить к описанию этой системы цифровой подписи, рассмотрим несколько теоретических понятий. Итак, пускай некоторая функция f отображает сообщение М произвольной длины в виде слова с фиксированной длиной, например, в 128 бит. Если f вычисляется эффективно, то такая функция называется укорачивающей. Причем в системах цифровой подписи используются только такие функции f, при которых для любых сообщений М1 и М2 не выполняется равенство f(М1) = f(М2). Еще одной важной особенностью таких функций является то, что, имея образ М0 (М0 = f(M)), практически невозможно найти сообщение М.

Так вот, для чего все это рассказывается. В системах цифровой подписи целесообразно использовать не само сообщение М, а его укороченный вид f(M). Выигрыш здесь, по-моему, очевиден: алгоритм подписи SIGN постоянно реализуется на входах одинаковой длины, хотя длина сообщения может быть произвольной, т.е. сколь угодно большой. При этом следует отметить, что достоверность подписи не уменьшается.

Вариант укорачивающей функции с ключом называется кодом достоверности. Если f — укорачивающая функция с ключом K, то код достоверности сообщения М равен f(M, K). Тот факт, что значение функции f получено именно для сообщения М и ключа К, может проверить лишь человек, который знает тайный ключ.

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

Следует отметить, что каждую укорачивающую функцию можно преобразовать в функцию с ключом по такому правилу: f1(M, K) = f(M*K).

Примером укорачивающей функции может служить функция, которая строится на основе RSA-функций. На практике же используются более быстрые укорачивающие функции, например, функции MD5 и SHA.

Разобравшись с вышеприведенным теоретическим материалом, приступим к рассмотрению системы Шнорра, названной в честь ее разработчика Клауса Шнорра.

Начнем с процесса генерирования ключей. Выбираем такое большое простое число р, что р – 1 имеет достаточно большой простой делитель q (разработчиком системы рекомендуется выбирать р > 2^512, q > 2^140). Потом выбирают число h, которое удовлетворяет соотношению: h^q = 1 mod p. Числа p, q, h не являются тайными. Далее абонент А выбирает случайное число a, такое что: 1< a <q – 1. Теперь следует найти число V = (h^a)^(-1) mod p. Открытым ключом будет число V, для которого выполняется условие: (h^a)*V = 1 mod p. Тайным ключом выбирается число а.

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

1. Выбирается случайное число r (0 < r < q – 1).

2. Вычисляется х = h^r mod p.

3. Находится значение укорачивающей функции S1 = f(M*x), где М*х — слияние сообщения М и числа х в один текст.

4. Вычисляется S2 = (r + a*S1) mod q.

5. В качестве подписи S принимается пара: S = (S1, S2).

Для проверки подписи абонент В находит значение Z = (h^S1)*(V^S2) mod p и проверяет равность S1 = f(MZ).

Система DSA

Напоследок рассмотрим систему цифровой подписи DSA (Digital Signature Algorithm), вышедшую в свет еще в 1991 году и довольно-таки часто называемую DSS (Digital Signature Standart). Именно она применяется в качестве стандарта цифровой подписи.

Традиционно начнем с процесса генерирования ключей. Выбираем достаточно большое простое число р, такое что р – 1 имеет большой делитель q. Стандарт требует, чтобы числа р и q удовлетворяли условиям: 2^512 < p < 2^1024 и q > 2^160. Далее выбирается любое число h, порядок которого совпадает с порядком числа q. Как и в системе Шнорра, числа p, q, h не являются тайной и пребывают во всеобщем пользовании абонентов сети. Чтобы получить открытый и тайный ключи, абонент А выбирает случайное число а и вычисляет b = (h^a) mod p. Тайным ключом является число а, а открытым — число b.

Алгоритм подписи использует укорачивающую функцию f, в качестве которой стандарт рекомендует функцию SHA, являющуюся укорачивающей функцией длиной 160 бит.

Чтобы поставить свою подпись на сообщении М, абонент А должен проделать следующую процедуру:

1. Выбирается случайное число r (0 < r < q – 1).

2. Вычисляется r1 = r^(-1) mod q.

3. Вычисляется S1 = (h^r mod p) mod q.

4. Вычисляется S2 = (r1*(f(M) + a*S1)) mod q.

5. Подпись формируется как пара чисел: S = (S1, S2).

Для проверки подписи абонент В должен вычислить:

Успешным результатом проверки следует считать выполнение равенства Т = S1.

Итоги

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

Идёт загрузка...

Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:
Комментарий:
Введите символы или вычислите пример: * Обновить