В схеме RSA, p показывает свой идентификатор вычислением корней по модулю n, что требует (неявного) знания разложения n на множители; предполагается, что только p знает его. В этой схеме каждый процесс использует свой модуль.
14.2.5 Схема Подписи Фиата-Шамира
Более тонкое использование трудности нахождения (квадратных) корней сделано в схеме Фиата и Шамира [FS86]. В RSA схеме процесс подписывает сообщение, показывая, что он способен вычислять корни по модулю своего общего ключа, а способность вычислять корни возможно требует знания разложения на множители. В схеме Фиата-Шамира процессы используют общий модуль n, разложение на множители которого известно только доверенному центру. Процессу p даются квадратные корни некоторых специфических чисел (в зависимости от идентификатора p), и подпись p для М обеспечивает доказательство того, что подписывающий знает эти квадратные корни, но не раскрывая их.
Преимущество схемы Фиата-Шамира над RSA схемой - более низкая арифметическая сложность и отсутствие отдельного общего ключа для каждого процесса. Недостаток - потребность в доверенном источнике, который выдает секретные ключи. Как упоминалось прежде, схема использует большое целое число n, произведение двух больших простых чисел, известных только центру. Кроме того имеется односторонняя псевдо-случайная функция f, отображающая строки на ; эта функция известна и может быть вычислена каждым процессом, но обратная функция не может быть вычислена.
Секретные и общие ключи. В качестве секретного ключа p даны квадратные корни с по k чисел по модулю n, а именно , где . можно считать общими ключами p, но поскольку они могут быть вычислены из идентификатора p, их не нужно хранить. Чтобы избежать технических неудобств, мы предположим, что эти k чисел - квадратичные остатк по модулю n. Квадратные корни могут быть вычислены центром, который знает множители n.
Подписавание сообщений: первая попытка. Подпись p неявно доказывает, что подписывающий знает корни , то есть, может выдать число s такой, что . Такое число - , но посылка самого раскрыла бы секретный ключ; чтобы избежать раскрытия ключа, схема использует следующую идею. Процесс p выбирает произвольное число r и вычисляет . Теперь p - единственный процесс, который может выдать число y, удовлетворяющее , а именно, . Таким образом, p может показывать свое знание без их раскрытия, посылая пару (x, y), удовлетворяющую . Так как p не посылает число r, вычислить из этой пары не возможно без вычисления квадратного корня.
Но имеются две проблемы с подписями, состоящими из таких пар. Во-первых, любой может произвести такую пару, жульничая следующим образом: сначала выбрать y, и впоследствии вычислить . Во-вторых, подпись не зависит от сообщения, так что процесс, получивший подписанное сообщение от p, может скопировать подпись на любое поддельное сообщение. Трудный вопрос этой схемы подписи - сделать так, чтобы p показывал знание корня произведения из подмножества , где подмножество зависит от сообщения и произвольного числа. Шифрование сообщения и произвольного числа с помощью f не дает подделывающему сначала выбрать y. Чтобы подписать сообщение М, p действует следующим образом.
(1) P выбирает произвольное число r и вычисляет .
(2) P вычисляет f (М, x), назовем первые k бит с по .
(3) P вычисляет .
Подпись состоит из кортежа (,..., , y).
Чтобы проверить подпись (,..., , y) процесса p для сообщения М, надо действовать следующим образом.
(1) Вычислить и
(2) Вычислить f (М, z) и проверить, что первые k бит - по .
Если подпись истинна, значение z, вычисленное на первом шаге проверки равняется значению x, используемому в подписывании и следовательно первые k бит f (М, z) равны ... .
Подделка и заключительное решение. Мы рассмотрим теперь стратегию подделывающего для получения подписи согласно вышеупомянутой схеме без знания .
(1) Выбрать k произвольных бит ... .
(2) Выбрать произвольное число y и вычислить
(3) Вычислить f (М, x) и посмотреть, равняются ли первые k бит значениям ... , выбранным ранее. Если это так, то (,..., , y) - подделанная подпись для сообщения M.
Поскольку вероятность равенства в шаге (3) может быть принята , подделка становится успешной после ожидаемого числа испытаний.
При k = 72 и принятым временем секунд для опробования одного выбора , ожидаемое время подделки (с этой стратегией) - секунд или 1,5 миллиона лет, что делает схему вполне безопасной. Однако, каждый процесс должен хранить k корней, и если k должен быть ограничен из-за ограничений пространства, ожидаемое время подделки может быть неудовлетворительно. Мы покажем сейчас как изменить схему, чтобы использовать k корней, и получать ожидаемое время подделки для выбранного целого числа t. Идея состоит в том, чтобы использовать первые kt бит f-результата, чтобы определить t подмножеств от , и заставить p показывать свое знание t этих произведений. Чтобы подписать сообщение М, p действует следующим образом.
(1) p выбирает произвольные ,..., и вычисляет .
(2) p вычисляет f (М, , ..., ); назовем первые kt бит . ( и ).
(3) p вычисляет для . Подпись состоит из (, ..., , , ..., ).
Чтобы проверить подпись (, ..., , , ..., ) процесса p для сообщения М, надо действуовать следующим образом.
(1) Вычислить и .
(2) Вычислить f (М, , ..., ), и проверить, что первые kt бит - , ..., .
Подделывающий, пытающийся произвести действительную подпись с той же самой стратегией, что приведена выше, теперь имеет вероятность успеха в третьем шаге , что означает ожидаемое число испытаний . Фиат и Шамир показывают в своей работе, что если разложение n на множители не оказывается простым, то существенно лучшего алгоритма подделки не существует, следовательно схему можно сделать произвольно безопасной, выбирая k и t достаточно большими.
В этом и предыдущем разделе было показано, что в синхронных системах существуют детерминированные решения для проблемы Византийского вещания. Максимальная способность восстановления таких решений - t < N/3, если не используется проверка подлинности (Раздел 14.1), и неограничена, если она используется (этот раздел). Во всех решениях, представленных здесь, синхронность была смоделирована с помощью (довольно сильных) предположений модели импульса; отказоустойчивая реализация модели импульса обсуждается в Разделе 14.3.
Проблема расстрельной команды. В дополнение к принятию модели импульса, второе предположение, лежащее в основе всех решений, представленных до сих пор - то, что импульс, в котором вещание начинается, известен всем процессам (и пронумерован 1 для удобства). Если априори дело обстоит не так, возникает проблема старта алгоритма одновременно, после того, как один или более процессов (спонтанно) инициируют запрос просьбу о выполнении алгоритма вещания. Запрос может исходить от командующего (после вычисления результата, который должен быть объявлен всем процессам) или от помощников (понимающих, что им всем нужна информация, хранящаяся у командующего). Эта проблема изучается в литературе как проблема расстрельной команды. В этой проблеме, один или более процессов инициируют (запрос), но не обязательно в одном и том же импульсе, и процессы могут стрелять. Требования:
(1) Обоснованность. Никакой корректный процесс не стреляет, если никакой процесс не инициировал.
(2) Одновременность. Если любой корректный процесс стреляет, тогда все корректные процессы стреляют в том же самом импульсе.
(3) Завершение. Если корректный процесс инициирует, то все корректные процессы стреляют в течение конечного числа импульсов.
Действительно, имея решение для проблемы расстрельной команды, не нужно заранее соглашаться о первом импульсе вещания; процессы, запрашивающие вещание, инициируют алгоритм расстрельной команды, и вещание начинается в импульсе следующем за стрельбой. Методы, используемые в решениях проблемы Византийского-вещания и проблемы расстрельной команды, могут быть объединены, чтобы получить протоколы, более эффективные по времени, которые решают проблему вещания непосредственно в отсутствии априорного соглашения о первом импульсе.
Временная сложность и рано останавливающиеся протоколы. В этой главе мы представили протоколы, использующие t + 1 или 2t + 3 импульсов, или раундов связи. Фишером и Линчем [FL82] показано, что t + 1 раундов связи - оптимальное число для t-устойчивых протоколов согласия, и результат был расширен, чтобы охватить протоколы с установлением подлинности, Долевом и Стронгом [DS83].
Тонкий момент в этих доказательствах - то, что в использованных сценариях процесс должен отказывать в каждом из импульсов с 1 по t, поэтому нижние границы в худшем случае - число фактических сбоев в течение выполнения. Так как в большинстве выполнений фактическое число сбоев намного ниже способности восстановления, изучалось существование протоколов, которые могут достигать соглашения ранее в тех выполнении, которые имеют маленькое число сбоев. Протоколы вещания с таким свойством называются рано останавливающимися. Долев, Райсчук и Стронг [DRS82] продемонстрировали нижнюю границу в f + 2 раунда для любого протокола в выполнении с f сбоями. Обсуждение нескольких рано останавливающихся протоколов вещания и согласия есть в [BGP92].
Рано останавливающиеся протоколы принимают решение в течение нескольких импульсов после того, как корректные процессы заключают, что был импульс без новых сбоев. Однако, нельзя гарантировать, что все корректные процессы достигают этого заключения в одном и том же импульсе. (Если, конечно, они не достигают его в импульсе t + 1; так как самое большее t процессов отказывают, среди первых t + 1 имеется один раунд, в котором никакого нового сбоя не происходит.) Как следствие, рано останавливающиеся протоколы не удовлетворяет одновременности. Коун и Дворк показали [CD91], что, чтобы достигнуть одновременности, в выполнении, где никаких сбоев не происходит, необходимо также t + 1 раунд, даже для рандомизированных протоколов и в (очень слабый) модели аварий. Это означает, что протоколам с установлением подлинности также нужно t + 1 импульсов для одновременного соглашения.