Современная прикладная криптография (стр. 20 )

4. Алгоритм подписи Q, который вырабатывает значение

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

5. Алгоритм проверки подписи, который проверяет правильность подписи к сообщению M с использованием открытого ключа .

Для криптографа важно определить, какими возможностями может располагать злоумышленник при атаке на схему цифровой подписи и оценивать ее стойкость, исходя из этого.

По возможности доступа к информации о схеме выделяют три класса методов атаки.

1. Методы атаки только по открытому ключу (key-only attack). В этом случае предполагается, что злоумышленник знает только открытый ключ схемы подписи и имеет возможность проверки правильности подписей сообщений, которые у него окажутся.

2. Методы атаки по открытому ключу и сообщениям (message attacks). В этом случае злоумышленник знает открытый ключ подписывающего и может наблюдать случайные пары (сообщение/подпись).

3. Методы атаки по выбранным сообщениям (chosen-message attack. В этом случае злоумышленник может получить подписи к сообщениям выбранным им лично (как в случае с нотариусом). Выбор этих сообщений может зависеть от ранее полученных подписей.

Различают несколько уровней по степени раскрытия схемы подписей.

1. Эпизодическое подделывание (Existential forgery). Злоумышленник подделывает подпись одного сообщения, не обязательно им выбранного. Сообщение это может быть или случайным, или не имеющим смысла.

2. Выборочное подделывание (Selective forgery). Злоумышленник подделывает подпись некоторого сообщения, по своему выбору.

3. Универсальное подделывание (Universal forgery). Злоумышленник может подделывать подписи к любому сообщению, но без знания секретного ключа подписи. Он может найти функционально эквивалентный алгоритм подписи.

4. Полное раскрытие схемы подписи (Total break).

Злоумышленник может вычислить секретный ключ подписывающего.

2.8. Схема цифровой подписи Эль Гамаля

В 1985 г. Эль Гамаль (El Gamal) предложил схему цифровой подписи, основанную на сложности решения задачи дискретного логарифмирования [115]. В той же работе содержится и описание криптосистемы открытого шифрования.

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

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

Секретная информация подписывающего пользователя A состоит из двух частей:

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

2. - разовый секретный ключ подписи, конкретного сообщения, НОД .

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

1. - открытый ключ подписи, вычисляется и сообщается всем проверяющим подпись пользователя а.

2. - составляет правую из двух частей (r, s) подписи.

Подписываемое сообщение должно быть представлено числом M из интервала [0,р-1]. (Далее в качестве M будет также рассматриваться значение функции хэширования Н от сообщения.)

Процедура подписи сообщения M следующая.

1. Пользователь а выбирает случайное число из интервала таким образом, чтобы выполнялось условие НОД

2. Вычисляет, то есть число, удовлетворяющее сравнению . Именно для разрешимости этого сравнения при выборе наложено ограничение его временной простоты C(p-l).

3. Вычисляет первую часть подписи .

4. Вычисляет вторую часть подписи по формуле

.

На этом процедура выработки подписи (r, s) к сообщению M заканчивается, и эти данные сообщаются всем проверяющим подпись.

Процедура проверки данных , , такова (черта над буквами поставлена потому, что поступившие на проверку данные могут не совпадать с оригинальными).

1.По полученным данным ,, и имеющемуся у проверяющего открытому ключу подписывающего вычисляются величины и .

2. В случае выполнения равенства =, считается, что , , и подпись верная.

Для объяснения схемы подписи рассмотрим проверяемое сравнение , решением которого и являются числа r и s. После подстановки значений и r оно примет вид

По свойствам сравнений (*) последнее сравнение эквивалентно сравнению по модулю (p-l) вида

).

Именно из этого сравнения подписывающий вычисляет величину .

Стойкость метода зависит во многом от сложности вычисления дискретных алгоритмов в GF(р). Так, с этой задачей злоумышленник сталкивается при определении секретного ключа из наблюдаемых данных M, r и s, так как из известного ему соотношения следует или . В случае, если ему удастся найти , то это будет полное вскрытие схемы цифровой подписи, и злоумышленник может выдавать себя за пользователя A. Отсюда следует, что нужно очень осторожно выбирать простое число р, чтобы не выбрать такое, для которого разработаны противником или известны быстрые методы вычисления дискретных логарифмов. (Например, в силу метода Полига-Хеллмана, когда (p-l) имеет только "маленькие" делители [35].)

В случае, если злоумышленник получил в свое распоряжение N наборов данных , (), то он сталкивается с решением системы из N сравнений от N+1 неизвестного , ,…,, которая является неопределенной и имеет экспоненциальное число решений. Но в случае повторения какого-нибудь разового ключа , долговременный ключ может быть определен из этой системы однозначно.

Может оказаться более простым, чем нахождение дискретных логарифмов, способ нахождения злоумышленником пары (r, s) из соотношения, но пока такого способа не известно.