Обобщенная модель электронной цифровой подписи. Схема Диффи-Хеллмана, схема Эль-Гамаля. Общая схема цифровой подписи

Прежде всего стоит сказать, что система цифровой подписи использует криптоситемы, которые базируются на концепции открытого ключа. О них уже рассказывалось на страницах МК в статьях Владимира (Людена) Ю. Некрасова ╚Чтоб никто не догадался╩ и моей собственной ╚Открытый ключ к закрытой информации╩, поэтому в дальнейшем будем считать, что криптоситемы, базирующиеся на концепции открытого ключа, нам уже известны, и углубляться в них мы в дальнейшем не будем. Также следует сказать, что основной задачей систем цифровой подписи является обеспечение достоверности и конфиденциальности соответствующего сообщения.

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

Вероятностный алгоритм или система генерирования ключей. Каждый абонент А получает пару ключей (КА, КА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.

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

Аналогично криптосистемам системы цифровой подписи для обеспечения конфиденциальности сообщений допускают вероятностную модификацию. В вероятностных системах цифровой подписи алгоритм 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.