Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
bt = (а~1)2 modn , / = Iv..,т.
Алгоритм вычисления цифровой подписи для сообщения Mсостоит в выполнении следующих действий:
1. Выбрать случайное число г, \ <г<п-\.
2. Вычислить и-г2 mod п.
3. Вычислить h(M,u) = s = (Sl9S2I-ISm) .
т
4. Вычислить / = V]~J я,' mod п.
/=і
5. Подписью для сообщения M положить пару (s, t).
371
І лава 14
Алгоритм проверки подписи состоит в выполнении следующих действий:
1. По открытому ключу bx,b2,...,bm modп и значению t вычислить
т
^ = b?1 mod п •
/=і
2. Вычислить /?(М, w) = Si.
3. Проверить равенство s = s'.
Достоинствами описанной схемы являются возможность выработки цифровых подписей для нескольких различных сообщений с использованием одного секретного ключа, а также сравнительная простота алгоритмов вычисления и проверки подписи. Например, для схемы цифровой подписи, основанной на алгоритме RSA, соответствующие алгоритмы требуют выполнения значительно большего числа умножений. Попытка компрометации этой схемы сталкивается с необходимостью решения сложной задачи нахождения квадратных корней по модулю п.
Недостатком схемы является большая длина ключа, которая определяется числом т. Если двоичная запись числа п содержит / знаков, то длина секретного ключа составляет ml бит, а открытого ключа — (т +1)/ бит. При этом необходимо учитывать, что для обеспечения достаточной стойкости данной схемы цифровой подписи числа Iwm должны иметь в своей двоичной записи несколько сотен бит.
§ 14.4. Цифровая подпись Эль-Гамаля
Схема цифровой подписи Эль-Гамаля основана на сложности другой задачи — вычисления значения логарифма в конечном поле (см. также § 11.2).
Пусть р — простое число и a — примитивный элемент поля Z . Выберем случайное число а в интервале
372
цифровые подписи
\ < а < р - 2 и вычислим значение P = аа mod р . Число а
является секретным ключом, а набор (р, а, /3) — открытым ключом.
Подпись для сообщения M вычисляется с помощью следующего алгоритма:
1. Выбрать случайное целое число г, 1 < г < р - 2 .
2. Вычислить у = ar mod р .
3. Для х = М вычислить S = (х - ay)r~x mod(p - 1).
4. Подписью для сообщения M положить пару (у, S).
Алгоритм проверки подписи заключается в проверке
сравнения Prу8 = ах (mod р). Если оно верно, то подпись принимается, если нет, то отвергается.
Основным достоинством такой схемы цифровой подписи является возможность выработки цифровых подписей для большого числа сообщений с использованием одного секретного ключа. При этом попытка компрометации схемы сталкивается с необходимостью решения сложной математической задачи, связанной с нахождением решений показательных уравнений, в частности — с нахождением значения логарифма в поле Zp.
Сделаем два замечания.
Первое касается выбора числа г. Оно должно уничтожаться сразу после вычисления подписи. Действительно, зная число г и значение подписи, легко вычислить секретный ключ а:
а = (х- rS)y~x mod(p -1).
Поэтому подпись может быть полностью скомпрометирована. Кроме того, число г должно быть действительно случайным и не должно повторяться для различных подписей, полученных при одном значении секретного ключа. В противном случае также можно вычислить секретный ключ а.
373
Глава 14
Второе замечание связано с тем, что реально при вычислении подписи на шаге 3 алгоритма в качестве х целесообразнее использовать свертку х = h(M), а не само сообщение М. Это защищает схему подписи от возможности подбора сообщений с известным значением подписи. Существует несколько способов такого подбора. Например, если выбрать случайно числа /, у, удовлетворяющие условиям 0 < і < р — 1, О < j < р -1, (j, р -1) = 1, и положить
у = al f3J mod р9 8 =-уГх mod(р -1), х = -yij~x mod(р -1),
то легко убедиться в том, что пара (у,8) является верной цифровой подписью для сообщения M = X .
Схема цифровой подписи Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам схем подписи. В их основе лежит проверка сравнения вида
aAj3B =rc (mod р),
в котором тройка (A9BfC) совпадает с одной из перестановок чисел +х, ±8 и ±у при некотором выборе знаков. Например, исходная схема Эль-Гамаля получается при A = Jс, B =-у и
C = S. На базе схем подписи из этого семейства построены и стандарты цифровой подписи США и России. Так, в американском стандарте DSS (Digital Signature Standard) используются значения А = х, В = у и C = S9 а в российском стандарте — значения A = -X9B = S и С = у.
Еще одним достоинством схемы Эль-Гамаля является возможность уменьшения длины подписи путем замены пары
374
цифровые подписи
чисел (/, S) на пару чисел (у mod q, 5 mod q), где q является некоторым простым делителем числа р -1 . При этом проверочное равенство по модулю р следует заменить на модифицированное равенство по модулю q:
(aAfiB mod p)modq = yc mod q.
Именно так сделано в американском стандарте цифровой подписи DSS.
§ 14.5. Одноразовые цифровые подписи
Рассмотренные системы цифровой подписи, основанные на сложности задач разложения целых чисел на множители, вычисления квадратного корня или логарифмирования в конечных полях, имеют один потенциальный недостаток. Он состоит в возможности построения новых эффективных алгоритмов для решения этих математических задач. Поэтому в реальных схемах длину ключа выбирают с определенным превышением необходимой величины для обеспечения достаточного запаса стойкости. Это, в свою очередь, значительно усложняет алгоритмы вычисления и проверки подписи. Поэтому представляется весьма привлекательной задача построения схем цифровой подписи на основе симметричных систем шифрования, свободных от подобных недостатков.
