4.2.8 О схемах, основанных на функциях с секретом

В данном подразделе мы приводим некоторые сведения [GMRiv] о стойкости схем электронной подписи, построенных на основе функций с секретом. В этом анализе предполагается, что подписывается само сообщение , а не значение какой-либо хэш-функции на этом сообщении.

Говоря неформально, функция называется функцией с секретом (trapdoor function), если она легко вычислима и существует некоторая информация, называемая секретом, знание которой позволяет легко инвертировать , но в то же время инвертирование без знания секрета является вычислительно трудной задачей (см. главу 14). Если имеется некоторая функция с секретом , то можно построить схему электронной подписи следующим образом. Пространством сообщений в этой схеме является . Роль открытого ключа играет функция , а секретного -- информация, позволяющая легко ее инвертировать. Подписью для произвольного сообщения является любой прообраз относительно . По предположению эти прообразы можно вычислять эффективно, лишь владея секретным ключом. Проверка же подписи для сообщения заключается в проверке равенства . По существу, такую схему можно получить из любой криптосистемы с открытым ключом, основанной на функции с секретом: отправитель подписывает сообщение, применяя к нему секретный алгоритм дешифрования, а получатель проверяет подпись, применяя к ней общедоступный алгоритм шифрования.

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

Схема RSA является нестойкой против селективной подделки на основе направленной атаки с выбором сообщений, так как для любых сообщений .

Схема Рабина является нестойкой против полного раскрытия на основе направленной атаки с выбором сообщений [GMRiv]. С другой стороны, доказано, что для противника, который может провести лишь атаку с известными сообщениями, селективная подделка столь же сложна, как задача факторизации целых чисел. При этом, правда, предполагается, что пространство сообщений не является "редким".