Что означает корректность ЭЦП?

Как известно, алгоритм проверки ЭЦП принимает на вход документ X, его подпись S и открытый ключ Q подписавшейся стороны. Алгоритм состоит в проверке определенного равенства, в котором задействованы X, S, Q и долговременные параметры алгоритма.

Например, в схеме ЭЦП Шнорра долговременными параметрами являются алгебраическая группа (аддитивная) и некоторый ее элемент G. Открытый ключ Q определяется как d-кратное G, где d -- это личный ключ. Проверочное равенство в схеме Шнорра имеет вид:

φ(X, S0Q + S1G) = S0

где S0, S1 – целые числа – части подписи S; φ – функция хэширования. Элементы G и φ выбираются так, что противнику, который не знает d, вычислительно трудно решить проверочное уравнение относительно S0, S1 при заданном X.

Алгоритм проверки ЭЦП возвращает ответ ДА, если проверочное равенство выполняется, и НЕТ в противном случае. Как интерпретировать ответ алгоритма? На примере схемы Шнорра, ДА интуитивно означает, что подпись действительно создана владельцем личного ключа и подписан действительно документ X.

Подобную интерпретацию ответа ДА можно встретить в некоторых стандартах ЭЦП:

При совпадении значений W и U принимается решение о том, что ЭЦП была создана с помощью личного ключа подписи х, связанного с открытым ключом проверки подписи у, а также ЭЦП и последовательность М не были изменены с момента их создания (отечественный стандарт СТБ 1176.2-99).

При совпадении значений r и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения (российский стандарт ГОСТ Р 34.10-94).

If v = r', then the signature is verified and the verifier can have high confidence that the received message was sent by the party holding the secret key x corresponding to y (американский стандарт FIPS 186-1).

Верна ли данная интерпретация? НЕТ. Дело в том, что проверочное уравнение можно решать не только относительно S, но и относительно Q. Оказывается, что для многих схем ЭЦП противник может изменить одновременно S и Q, не нарушив проверочное равенство.

Например, в случае схемы Шнорра противник выбирает целое с, строит Q* = Q + cG и заменяет S = (S0, S1) на S* = (S0, S1 – cS0). Тройка (X, S*, Q*), также как и (X, S, Q), удовлетворяет проверочному равенству.

Угроза от атак по одновременной замене S и Q не очень ясна. Например, для практической реализации атаки на схему Шнорра противнику требуется заверить открытый ключ Q* в удостоверяющем центре. В правильно спроектированной системе управления открытыми ключами заверение предполагает проверку знания противником личного ключа, соответствующего Q*. Но этот ключ противнику неизвестен.

Тем не менее, существование атак, требует, по крайней мере, корректировки интерпретации ответа ДА алгоритма проверки ЭЦП. В новых криптографических стандартах РБ, РФ и США ответ трактуется более осторожно:

В ГОСТ Р 34.10-2001 (РФ) подпись просто «принимается».

В СТБ П 34.101.45-2011 (РБ) подпись объявляется корректной. В вводной части стандарта объясняется, что «при правильном управлении ключами корректность проверяемой подписи означает, что она была выработана владельцем личного ключа и после этого сообщение не изменялось».

В FIPS 186-3 (США) подпись объявляется корректной (verified), но не действительной (valid). Корректная подпись признается действительной только при выполнении определенных гарантий (assurances), связанных с управлением ключами.

Интересно, что известны атаки на распространенные схемы ЭЦП, в которых проверочное уравнение решается относительно Q и долговременных параметров при фиксированных X и S. Но это уже другая история.

Новости
24.02.2020
План семинара весна 2020
20.10.2019
План семинара осень 2019
01.10.2019
XII Международная научная конференция
18.04.2019
Школа по компьютерным наукам
18.04.2019
Computer Science Summer
01.04.2019
AgatCTF-2019
07.03.2019
CDAM’2019
04.03.2019
План семинара весна 2019
12.09.2018
План семинара осень 2018