Схема подписи Фиата — Шамира

Схема подписи Фиата — Шамира — это криптографический протокол, позволяющий одной стороне (подписывающему) доказать другой стороне (проверяющему), что она владеет секретным ключом, не раскрывая его, и тем самым создать цифровую подпись для сообщения. Схема была предложена Амосом Фиатом и Ади Шамиром в 1986 году и является одним из первых и наиболее известных примеров протокола с нулевым разглашением (zero-knowledge proof), адаптированного для создания цифровых подписей.

История

Разработка схемы Фиата — Шамира была мотивирована необходимостью создания эффективной и безопасной системы аутентификации и цифровой подписи, которая не требовала бы раскрытия секретного ключа. До этого момента большинство схем цифровой подписи, такие как RSA (1977 год) и Эль-Гамаля (1985 год), основывались на сложности разложения больших чисел на множители или дискретного логарифмирования, но не использовали концепцию нулевого разглашения.

Амос Фиат и Ади Шамир, работавшие в израильском исследовательском центре, представили свою схему в 1986 году на конференции CRYPTO. Их работа основывалась на идеях, заложенных в протоколе идентификации с нулевым разглашением, который ранее предложили Шафи Гольдвассер, Сильвио Микали и Чарльз Раккофф. Фиат и Шамир преобразовали этот интерактивный протокол идентификации в неинтерактивную цифровую подпись, используя хеш-функцию для замены случайных запросов проверяющего.

Основные принципы работы

Схема Фиата — Шамира базируется на сложности задачи извлечения квадратного корня по модулю составного числа. Безопасность схемы основана на предположении, что для составного числа n, являющегося произведением двух больших простых чисел, вычислить квадратный корень по модулю n без знания разложения n на множители практически невозможно.

Генерация ключей

1. Доверенный центр или сам подписывающий выбирает два больших простых числа p и q.
2. Вычисляется модуль n = p × q. Число n является открытым параметром системы.
3. Выбирается случайное число s, взаимно простое с n (то есть НОД(s, n) = 1). Число s является секретным ключом подписывающего.
4. Вычисляется открытый ключ v = s² mod n. Таким образом, v — это квадрат секретного ключа по модулю n.

Процесс подписания сообщения

Пусть M — подписываемое сообщение. Подписывающий, владеющий секретным ключом s, выполняет следующие шаги:

1. Выбор случайного числа: Подписывающий выбирает случайное число r, взаимно простое с n.
2. Вычисление первого элемента: Вычисляется значение x = r² mod n.
3. Вычисление запроса: С помощью криптографической хеш-функции H вычисляется значение e = H(M || x), где || обозначает конкатенацию (объединение) сообщения M и значения x. Это значение e является «запросом» (challenge), который в интерактивном протоколе задавал бы проверяющий. В неинтерактивной схеме он генерируется самим подписывающим.
4. Вычисление ответа: Подписывающий вычисляет значение y = r × s^e mod n.
5. Формирование подписи: Цифровой подписью для сообщения M является пара чисел (e, y).

Процесс проверки подписи

Проверяющий, имеющий открытый ключ v, сообщение M и подпись (e, y), выполняет следующие шаги:

1. Восстановление первого элемента: Вычисляется значение x' = y² × v^e mod n.
2. Вычисление ожидаемого запроса: Вычисляется значение e' = H(M || x').
3. Сравнение: Если e' = e, то подпись считается действительной. В противном случае подпись отвергается.

Правильность схемы доказывается следующим образом: x' = y² × v^e = (r × s^e)² × (s²)^e = r² × s^(2e) × s^(2e) = r² = x (все вычисления по модулю n). Таким образом, x' совпадает с x, и, следовательно, e' совпадает с e.

Свойства и безопасность

Схема Фиата — Шамира обладает рядом важных свойств:

• Нулевое разглашение (Zero-Knowledge): Протокол позволяет доказать знание секретного ключа s, не раскрывая его. Проверяющий не может извлечь из подписи никакой информации о s.
• Неинтерактивность: В отличие от оригинального протокола идентификации, схема подписи не требует обмена несколькими сообщениями между сторонами. Подпись создается подписывающим автономно и может быть проверена любой третьей стороной.
• Безопасность: Безопасность схемы основана на сложности задачи извлечения квадратного корня по модулю составного числа. Если злоумышленник сможет разложить n на множители, он сможет вычислить секретный ключ s и подделывать подписи. Однако при правильно выбранных больших простых числах (например, 1024 или 2048 бит) эта задача считается вычислительно неразрешимой.
• Эффективность: Процесс подписания и проверки включает в себя операции умножения и возведения в степень по модулю, что является относительно быстрым по сравнению с некоторыми другими схемами. Однако размер подписи (пара (e, y)) может быть больше, чем в схемах типа RSA.

Варианты и модификации

Схема Фиата — Шамира стала основой для множества последующих разработок:

• Схема Feige-Fiat-Shamir: Модификация, предложенная Ури Фейге, Амосом Фиатом и Ади Шамиром в 1988 году, которая использует несколько секретных и открытых ключей для повышения безопасности и эффективности.
• Схема Guillou-Quisquater: Обобщение схемы Фиата — Шамира, использующее возведение в произвольную степень вместо квадратного корня.
• Схема Schnorr: Другой известный протокол с нулевым разглашением, основанный на сложности дискретного логарифмирования, который также может быть преобразован в цифровую подпись.

Применение

Хотя схема Фиата — Шамира в чистом виде не получила столь широкого распространения, как RSA или ECDSA (на основе эллиптических кривых), она оказала значительное влияние на развитие криптографии:

• Смарт-карты: Первоначально схема была предложена для использования в смарт-картах, где требуется компактное и эффективное доказательство владения ключом без его раскрытия.
• Криптографические протоколы: Принципы, заложенные в схеме, используются в более сложных протоколах, таких как протоколы групповой подписи, слепой подписи и доказательства с нулевым разглашением.
• Образовательные цели: Схема Фиата — Шамира является классическим примером для изучения концепций нулевого разглашения и неинтерактивных доказательств в учебных курсах по криптографии.

Критика

Основным недостатком схемы Фиата — Шамира является то, что она не является детерминированной. Для каждого подписываемого сообщения необходимо генерировать новое случайное число r. Если случайное число будет скомпрометировано или использовано повторно для разных сообщений, это может привести к раскрытию секретного ключа. Кроме того, размер подписи может быть больше, чем в некоторых альтернативных схемах, что может быть критично для систем с ограниченной пропускной способностью.

Источники

1. Fiat, A., Shamir, A. (1986). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO '86. Lecture Notes in Computer Science, vol 263. Springer.
2. Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
3. Шнайер, Б. (2002). Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Триумф.