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

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

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

φ(X, S₀Q + S₁G) = S₀

где S₀, S₁ – целые числа – части подписи S; φ – функция хэширования. Элементы G и φ выбираются так, что противнику, который не знает d, вычислительно трудно решить проверочное уравнение относительно S₀, S₁ при заданном 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 = (S₀, S₁) на S* = (S₀, S₁ – cS₀). Тройка (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. Но это уже другая история.