 |
Получить сообщения импульса 1.
|
|
|
|
Помощник p действует следующим образом.
if от g в импульсе 1 было получено cообщение < value, x>
then else
Объявить другим помощникам, действуя как командующий
в в следующем импульсе
(t+1): получить сообщения импульса t + 1.
Командующий останавливается на.
Для помощника p:
Для каждого помощника q в встречается решение.
:= решение в;
Алгоритм 14.3 Вещание (N, t) (ДЛЯ t> 0).
Лемма 14.2 (Завершение) Если Broadcast(N, t) начинается в импульсе 1, каждый процесс принимает решение в импульсе t+1.
Доказательство. Так как протокол рекурсивен, его свойства доказываются с использованием рекурсии по t.
В алгоритме Broadcast(N, 0) (Алгоритм 14.2), каждый процесс принимает решение в импульсе 1.
В алгоритме Broadcast(N, t) помощники начинают рекурсивные обращения алгоритма, Broadcast(N-1, t-1), в импульсе 2. Если алгоритм начат в импульсе 1, он принимает решение в импульсе t (это - гипотеза индукции), следовательно если он начат в импульсе 2, все вложенные вызовы принимают решение в импульсе t + 1. В одном том же импульсе принимается решение в Broadcast(N, t). o
Чтобы доказывать зависимость (также индукцией) предполагается, что командующий корректен, следовательно все t сбойных процесса находятся среди N-1 помощников. Так как t < (N - l) /3 не всегда выполняется, простую индукцию использовать нельзя, и мы рассуждаем, используя фактическое число неисправностей, обозначенное f.
Лемма 14.3 (Зависимость) Если командующий корректен, если имеется f сбойных процессов, и если N > 2f+t, то все корректные процессы останавливаются на входе командующего.
Доказательство. В алгоритме Broadcast(N, 0) если командующий корректен, все корректные процессы, останавливаются на значении входа генерала.
|
|
|
Теперь предположим, что лемма справедлива для Broadcast(N-1, t-1). Так как командующий корректен, он посылает свой вход всем помощникам в импульсе 1, так что каждый корректный помощник q выбирает. Теперь N > 2f + t означает (N - 1) > 2f + (t - 1), поэтому гипотеза индукции применяется к вложенным вызовам, даже если теперь все f сбойных процесса находятся среди помощников. Таким образом, для корректных помощников p и q, решение p в Broadcast(N-1, t-1) равняется, то есть,. Но, поскольку строгое большинство помощников корректно (N > 2f + t), процесс p завершится с, в котором большинство значений равняется. Следовательно, применение major к p выдает нужное значение. o
Лемма 14.4 (Соглашение) Все корректные процессы останавливается на одном и том же значении.
Доказательство. Так как зависимость означает соглашение в выполнениях, в которых командующий является корректным, мы теперь сконцентрируемся на случае, когда командующий сбойный. Но тогда самое большее t-l помощников сбойные, что означает, что вложенные вызовы функционируют в пределах своих способностей восстановления!
Действительно, t < N/3 означает t - 1 < (N - 1) / 3, следовательно, вложенные вызовы удовлетворяют соглашению. Таким образом, все корректные помощники остановятся на одном и том же значении для каждого помощника q во вложенном вызове. Таким образом, каждый корректный помощник вычисляет точно такой же вектор W в импульсе t + 1, что означает, что применение major дает тот же самый результат в каждом корректном процессе. o
Теорема 14.5 Протокол Broadcast(N, t) (Алгоритм 14.2/14.3) - t-Византийско-устойчивый протокол вещания при t < N/3.
Доказательство. Завершение было показано в Лемме 14.2, зависимость в Лемме 14.3, и соглашение в Лемме 14.4. o
|
|
|
Протокол Broadcast принимает решение в (t + 1)-ом импульсе, что является оптимальным; см. Подраздел 14.2.6. К сожалению, его сложность по сообщениям экспоненциальная; см. Упражнение 14.1.
14.1.3 Полиномиальный Алгоритм Вещания
В этом разделе мы представляем Византийский алгоритм вещания Долева и других [DFF+82], который использует только полиномиальное число сообщений и бит. Временная сложность выше, чем у предыдущего протокола; алгоритм требует 2t+3 импульса для достижения решения. В следующем описании будет предполагаться, что N = 3t + 1, и позже будет обсужден случай N > 3t + 1.
Алгоритм использует два порога, L = t + 1 и H = 2t + 1. Эти числа выбираются так, что (1) каждое множество из L процессов содержит по крайней мере один корректный процесс, (2) каждое множество из H процессов содержит по крайней мере L корректных процессов, и (3) имеется по крайней мере H корректных процессов. Обратите внимание, что предположение необходимо и достаточно для выбора L и H, удовлетворяющих этим трем свойствам.
Алгоритм обменивается сообщениями типа < bm, v>, где v или значение 1, или имя процесса (bm обозначает “broadcast message”, “вещать сообщение”.) Процесс p содержит двухмерную булеву таблицу R, где истинен тогда и только тогда, когда p получил сообщение < bm, v> от процесса q. Первоначально все элементы таблицы ложны, и мы полагаем, что таблица обновляется в фазе получения каждого импульса (это не показано в Алгоритме 14.4). Заметьте, что монотонна в импульсах, то есть, если становится истинным в некотором импульсе, он остается истиной в более поздних импульсах. Кроме того, так как только корректные процессы “выкрикивают” сообщения, для корректных p, q, и r в конце каждого импульса имеем:.
В отличие от протокола Broadcast предыдущего подраздела, протокол Долева и других является асимметричным в значениях 0 и 1. Решение 0 - значение по умолчанию и выбирается, если в обмене было недостаточно много сообщений. Если командующий имеет вход 1, он будет “выкрикивать” сообщения < bm, 1>, и получение достаточно большого количества отраженных сообщений, типа < bm, q>, заставляет процесс принять решение 1.
|
|
|
В алгоритме уместны три типа действия: инициирование, поддержка и подтверждение.
(1) Поддержка. Процесс p поддерживает процесс q в импульсе i, если в более ранних импульсах p получил достаточно доказательств, что q послал сообщения < bm, 1>; если дело обстоит так, p пошлет < bm, q> сообщения в импульсе i. Процесс p прямо поддерживает q, если p получил сообщение < bm, 1> от q. Процесс p косвенно поддерживает q, если p получил сообщение < bm, q> по крайней мере от L процессов. Множество процессов, поддерживаемых p, определяется неявно из
(*прямая*)
(*косвенная*)
Порог для становления косвенным поддерживающим означает, что если корректный процесс поддерживает процесс q, то q послал по крайней мере одно сообщение < bm, 1>. Действительно, предположим, что некоторый корректный процесс поддерживает q, пусть i - первый импульс, в котором это происходит. Так как косвенная поддержка q требует получения по крайней мере одного сообщения < bm, q> от корректного процесса в более раннем импульсе, первая поддержка корректным процессом процесса q - прямая. Прямая поддержка корректным процессом означает, что этот процесс получил сообщение < bm, 1> от q.
(2) Подтверждение. Процесс p подтверждает процесс q после получения сообщения < bm, q> от H процессов, то есть,
Выбор порогов означает, что, если корректный процесс p подтверждает q, то все корректные процессы подтверждают q самое большее одним импульсом позже. Действительно, предположим, что p подтверждает q после импульса i. Процесс p получил сообщения < bm, q> от H процессов, включая (выбором порогов) по крайней мере L корректных поддерживающих для q. Корректные поддерживающие для q посылают сообщение < bm, q> всем процессам, что означает, что в импульсе i все корректные процессы получают по крайней мере L сообщений < bm, q> и поддерживают q в импульсе i + 1. Таким образом, в импульсе i + 1 все корректные процессы посылают < bm, q>, и поскольку число корректных процессов по крайней мере H, каждый корректный процесс получает достаточную поддержку, чтобы подтвердить q.
|
|
|
(3) Инициирование. Процесс p инициирует, когда у него есть достаточно доказательств того, что окончательное значения решения будет 1. После инициирования, процесс p посылает сообщения < bm, 1>. Инициирование может быть вызвано тремя типами доказательств, а именно (1) p - командующий и, (2) p получает < bm, 1> от командующего в импульсе 1, или (3) p подтвердил достаточно много помощников в конце последнего импульса. Последняя возможность в частности требует некоторого внимания, так как число подтвержденных помощников, которое является "достаточным" увеличивается в течение выполнения, и подтвержденный командующий не идет в счет для этого правила. В первых трех импульсах L помощников должны быть подтверждены, чтобы инициировать, но начиная с импульса 4 порог увеличивается через каждые два импульса. Таким образом, инициирование согласно правилу (3) требует, чтобы к концу импульса i, помощников было подтверждено. Запись в алгоритме обозначает множество подтвержденных помощников, то есть,. Инициирование процессом p представляется булевой переменной.
Если корректный помощник r инициирует в конце импульса i, все корректные процессы подтверждают r в конце импульса i + 2. Действительно, r “выкрикивает” < bm, 1> в импульсе i + 1, поэтому все корректные процессы (прямо) поддерживают r в импульсе i + 2, так что каждый процесс получает по крайней мере H сообщений < bm, q> в этом импульсе.
Алгоритм продолжается в течение 2t + 3 импульсов; если процесс p подтвердил по крайней мере H процессов (здесь считает командующий) к концу того импульса, p принимает решение 1, иначе p принимает решение 0. См. Алгоритм 14.4.
var : boolean init false
: boolean init if then true else false;
Импульс i: (* Фаза посылки *)
if then shout< bm, 1>;
forall do shout< bm, q>;
получить все сообщения импульса i;
(*обновление состояния*)
if i = 1 and then;
if then;
if i = 2t + 3 then (*принять решение*)
if then else
Алгоритм 14.4 Протокол с надежным вещанием.
Командующий, являющийся единственным процессом, который может самостоятельно предписать инициирования (в других процессах) занимает мощное положение в алгоритме. Легко заметить, что, если командующий корректно инициирует, начинается лавина сообщений, которая заставляет все корректные процессы подтвердить H процессов и остановиться на значении 1. К тому же если он не инициирует, то нет "критической массы" сообщений, которая ведет к инициированию любого корректного процесса.
Лемма 14.6 Алгоритм 14.4 удовлетворяет завершению (и одновременности) и зависимости.
Доказательство. Из алгоритма видно, что все корректные процессы принимают решение в конце импульса 2t + 3, что показывает завершение и одновременность. Чтобы показать зависимость, мы предположим, что командующий корректен.
|
|
|
Если командующий корректен и имеет вход 1, он “выкрикивает” сообщение < bm, 1> в импульсе 1, заставляя каждый корректный процесс q инициировать. Следовательно, каждый корректный процесс q “выкрикивает” < bm, 1> в импульсе 2, так что к концу импульса 2 каждый корректный процесс p поддерживает все другие корректные процессы. Это означает, что в импульсе 3 каждый корректный p “выкрикивает” < bm, q> для каждого корректного q, так что в конце импульса 3 каждый корректный процесс получает < bm, q> от каждого другого корректного процесса, заставляя его подтвердить q. Таким образом с конца раунда 3 каждый корректный процесс подтвердил H процессов, что означает, что окончательное решение будет 1. (Командующий поддерживается и подтверждается всеми корректными процессами одним импульсом ранее других процессов.)
Если командующий корректен и имеет вход 0, он не “выкрикивает” < bm, 1> в импульсе 1, чего не делает и никакой другой корректный процесс. Предположим, что никакой корректный процесс не инициировал в импульсах с 1 по i-1; тогда никакой корректный процесс не посылает < bm, 1> в импульсе i. В конце импульса i никакой корректный процесс не поддерживает и не подтверждает никакого корректного процесса, так как, как мы видели ранее, это подразумевает, что последний процесс послал сообщение < bm, 1>. Следовательно, никакой корректный процесс не инициирует в конце импульса i. Отсюда следует, что никакой корректный процесс не инициирует вообще. Это означает, что никакой корректный процесс никогда не подтверждает корректный процесс, так что никакой корректный процесс не подтверждает более t процессов, и решение в конечном импульсе - 0. o
Мы продолжим доказательством соглашения, и будем предполагать в следующих леммах, что командующий сбойный. Достаточная "критическая масса" сообщений, ведущая неизбежно к 1-решению, создается инициированием L корректных процессов, когда имеется по крайней мере четыре импульса.
Лемма 14.7 Если L корректных процессов инициируют к концу импульса i, i < 2t, то все корректные процессы останавливаются на значении 1.
Доказательство. Пусть i - первый импульс, в конце которого по крайней мере L корректных процессов инициируют, и пусть А обозначает множество корректных процессов, которые инициировали в конце импульса i. Все процессы в A - помощники, так как командующий сбойный. В конце импульса i + 2 все корректные процессы подтвердили помощников в А; мы покажем, что в это время все корректные процессы инициируют.
Случай i = 1: Все корректные процессы подтвердили помощников из А к концу импульса 3, и инициируют, так как.
Случай: По крайней мере один процесс, допустим r, из А инициировал в импульсе i, так как он подтвердил Th(i) помощников (инициирование с помощью получения < bm, 1> от командующего возможно только в импульсе 1). Эти Th(i) помощников подтверждены всеми корректными процессами в конце импульса i + l, но r не принадлежит к этим Th(i) подтвержденным помощникам, так как r впервые посылает сообщения < bm, 1> в импульсе i + 1. Однако, все корректные процессы подтвердят r к концу импульса i + 2; таким образом они подтвердили по крайней мере Th(i) + 1 помощников в конце раунда i + 2. В заключение, так как Th(i+2)= Th(i)+1, все корректные процессы инициируют.
Теперь, поскольку все корректные процессы инициируют к концу раунда i + 2, они подтверждены (всеми корректными процессами) в конце раунда i + 4, следовательно все корректные процессы подтвердили по крайней мере H помощников. Поскольку предполагалось, что i < 2t,, так что все корректные процессы останавливаются на значении 1. o
Для любого корректного процесса, чтобы остановиться на 1, необходима "лавина", состоящая из инициирования по крайней мере L на корректных процессов. Действительно, 1-решение требует подтверждения по крайней мере H процессов, включая L корректных, что эти корректные процессы инициировали. Вопрос в том может ли Византийский заговор откладывать начало лавины достаточно долго, чтобы вызвать 1-решение в некоторых корректных процессах, без навязывания его в общем согласно Лемме 14.7. Конечно, ответ - нет, так как имеется ограничение на то, как долго заговор может откладывать лавину, и число импульсов, 2t + 3, выбрано точно так, чтобы предотвратить это. Причина - возрастающий порог для требуемого числа подтвержденных процессов; в более поздних импульсах он становится настолько высок, что уже стало необходимо L инициированных корректных помощников, чтобы инициировать следующий корректный процесс.
Лемма 14.8 Предположим, что по крайней мере L корректных процессов инициируют в течение алгоритма, и пусть i - первый импульс, в конце которого инициируют L корректных процессов. Тогда i < 2t.
Доказательство. Чтобы инициировать в импульсе 2t или выше, корректный процесс должен подтвердить по крайней мере Th(2t) = L + (t-1) помощников. Так как командующий сбойный, то есть самое большее t-1 сбойных помощников, поэтому по крайней мере L корректных помощников должны были быть подтверждены, что показывает, что уже, в более раннем импульсе, L корректных процессов, должно быть, инициировали. o
Теорема 14.9 Алгоритм вещания Долева и других (Алгоритм 14.4) - t-Византийско-устойчивый протокол вещания.
Доказательство. Завершение (и одновременность также) и зависимость показаны в Лемме 14.6. Чтобы показать соглашение, предположим, что имеется корректный процесс, который останавливается на значении 1. Мы заметили, что это означает, что по крайней мере L корректных процессов инициировали. По Лемме 14.8, впервые это случалось в импульсе i < 2t. Но тогда по Лемме 14.7, все корректные процессы останавливаются на значении 1. o
Чтобы облегчить представление алгоритма, было сделано предположение, что процессы повторяют в каждом раунде сообщения, которые они посылали в более ранних раундах. Поскольку корректные процессы записывают сообщения, полученные в более ранних раундах, это не нужно, поэтому достаточно послать каждое сообщение только. Таким образом, каждый корректный процесс посылает каждое из N+1 возможных сообщений другому процессу самое большее один раз, что ограничивает сложность по сообщениям величиной. Так как имеется только N+1 различных сообщений, каждое сообщения должно содержать только O (log N) бит.
Если число процессов превышает 3t + 1, для выполнения алгоритма выбирается совокупность 3t активных помощников. (Выбор выполняется статически, например, выбирая 3t процессов, чьи имена следуют за g в порядке имен процессов. Командующий и активные помощники сообщают пассивным помощникам о своем решении, и пассивные помощники останавливаются на значении, которое они получают от более t процессов. Сложность по сообщениям этого послойного подхода -, и разрядная сложность -.
14.2 Протоколы с Установлением Подлинности
Злонамеренное поведение, рассматриваемое до сих пор включало неправильную пересылку информации в дополнение к посылке неправильной информации о собственном состоянии процесса. К счастью, это чрезвычайно злонамеренное поведение Византийских процессов может быть ограничено с помощью криптографических средств, которые сделали бы Теорему 14.1 недействительной. Действительно, в сценариях, используемых в ее доказательстве, сбойные процессы посылали бы сообщения как в сценарии 1, получив только сообщения сценария 0.
В этом разделе предполагается наличие средства для цифровой подписи и установления подлинности сообщений. Процесс p, посылающий сообщение М, добавляет к этому сообщению некоторую дополнительную информацию, которая называется цифровой подписью p для сообщения М. В отличие от рукописных подписей, цифровая подпись зависит от М, что делает бесполезным копирование подписи в другие сообщения. Схема подписи удовлетворяет следующим свойствам.
(1) Если p корректен, только p может правдоподобно вычислить. Это вычисление - подпись сообщения M.
(2) Каждый процесс может эффективно проверять (имея p, М и S). Эта проверка - установление подлинности сообщения M.
Схемы подписи основаны на частных и общих ключах. Первое предположение не исключает того, что Византийские процессы могут открыть свои секретные ключи друг другу, что позволяет одному Византийскому процессу подделать подпись другого. Предполагается, что только корректные процессы хранят свои частные ключи в секрете.
Мы изучим реализацию схем подписи в Подразделах с 14.2.2 по 14.2.5. В следующем подразделе, сообщение < msg >, подписанное процессом p, то есть, пара, содержащая < msg > и, обозначается < msg >: p.
14.2.1 Протокол Высокой Степени Восстановления
Эффективный Византийский алгоритм вещания, использующий полиномиально много сообщений и t+1 импульсов, был предложен Долевом и Стронгом [DS83]. Установление подлинности, используемое в этом протоколе, разрешает неограниченную способность восстановления. Мы заметим, тем не менее, что могут отказать не более N процессов (из N), и N процессов отказывают, все требования примитивно удовлетворяются; следовательно пусть t < N. Их протокол основан на более раннем, предложенном Лампортом, Шостаком и Пизом [LSP82], который является экспоненциальным по числу сообщений. Мы представляем сначала последний протокол.
В импульсе 1 командующий “выкрикивает” сообщение < value, >: g, содержащее свой (подписанный) вход.
В импульсах со 2 по t + l процессы подписывают и пересылают сообщения, которые они получили в предыдущем импульсе; следовательно, сообщение, которым обмениваются в импульсе i, содержит i подписей. Сообщение < value, v>: g::...: называется действительным (имеющим силу) для получающего процесса p, если справедливо следующее.
(1) Все i подписей корректны.
(2) i подписей от i различных процессов.
(3) p не встречается в списке подписей.
В течение алгоритма, процесс p содержит множество значений, содержащихся в действительных сообщениях, полученных p; первоначально это множество пусто, и значение каждого действительного сообщения вставляется в него.
Сообщения, пересылаемые в импульсе i - в точности те действительные сообщения, полученные в предыдущем импульсе. В конце импульса t + 1, процесс p принимает решение основанное на. Если состоит из одиночного элемента {v}, p принимает решение v, иначе p принимает решение значения по умолчанию (например, 0). Чтобы сэкономить на числе сообщений, p пересылает сообщение < value, v>: g: :...:: p только процессам, не встречающимся в списке g,,...,. Эта модификация не имеет никакого влияния на поведение алгоритма, так как для процессов в списке сообщение не действительно.
Теорема 14.10 Алгоритм Лампорт, Шостака и Пиза - корректный Византийский алгоритм вещания при t < N, использующий t + 1 импульс.
Доказательство. Все процессы принимают решение в импульсе t + 1, что подразумевает и завершение и одновременность алгоритма.
Если командующий корректен и имеет вход v, все процессы получают его сообщение < value, >: g в импульсе 1, так что все корректные процессы включают v в W. Никакое другое значение не вставляется в W, так как никакое другое значение никогда не подписывается командующим. Следовательно, в импульсе t + 1 все процессы имеют W = {v} и останавливаются на v, что означает зависимость.
Чтобы показать соглашение, мы получим, что для корректных процессов p и q, в конце импульса t + 1. Предположим, в конце импульса t + 1, и пусть i - импульс, в котором p вставил v в Wp, по получении сообщения < value, v>: g::...:.
Случай 1: Если q встречается в g,,...,, то q сам видел значение v и вставил его в.
Случай 2: Если q не встречается в последовательности g,,..., и, то p пересылает сообщение < value, v>: g::...: : p процессу q в импульсе i + i, так что q утверждает (придает силу) v самое позднее в импульсе i + 1.
Случай 3: Если q не встречается в последовательности g,,...,, и i = t + 1, заметьте, что сообщение, полученное p, было подписано t + l последовательными процессами, включая по крайней мере один корректный процесс. Этот процесс переслал сообщение всем другим процессам, включая q, так что q видит v.
Так как к концу импульса t + 1, p и q принимают одинаковое решение. o
Завершить алгоритм ранее импульса t + 1 невозможно. Во всех импульсах до t, корректный процесс мог бы получать сообщения, созданные и пересланные только сбойными процессами, и не посланные другим корректным процессам, что могло бы вести к противоречивым решениям.
Промежуточный результат предыдущего алгоритма, а именно соглашение о множестве значений среди всех корректных процессов, более сильное, чем необходимо для достижения соглашения об одиночном значении; Это было замечено Долевом и Стронгом [DS83], которые предложили более эффективную модификацию. Фактически достаточно, что в конце импульса t + 1, или (a) для каждого корректного p множество - один и тот же одиночный элемент, или (b) ни для какого корректного p множество не является одиночным элементом. В первом случае все процессы принимают решение v, в последнем случае они все принимают решение 0 (или, если желательно изменить алгоритм таким образом, они принимают решение "командующий сбойный").
Алгоритмом Долева и Стронга достигается более слабое требование на множества W. Вместо того, чтобы передавать каждое действительное сообщение, процесс p пересылает самое большее два сообщения, а именно одно сообщение с первым и одно сообщение со вторым значением, принятым p. Полное описание алгоритма оставлено читателю.
Теорема 14.11 Алгоритм Долева и Стронга, описанный выше - протокол Византийского-вещания, использующий t + 1 импульс и самое большее сообщений.
Доказательство. Завершение и одновременность доказываются, как в предыдущем протоколе, так как каждый корректный процесс принимает решение в конце импульса t + 1. Зависимость выводится так же, как в предыдущем протоколе. Если g правильно “выкрикивает” v в первом импульсе, все корректные процессы принимают v в этом импульсе, и никакое другое значение никогда не принимается; следовательно, все корректные процессы останавливаются на v. Заявленная сложность по сообщениям следует из факта, что каждый (корректный) процесс “выкрикивает” самое большее два сообщения.
Чтобы показать соглашение, мы покажем, что для корректных процессов p и q, и удовлетворяют в конце импульса t + 1 следующему.
(1) Если, то.
(2) Если, то.
Для (1): Предположим, что p принял значение v после получения сообщения < value, v>: g::...: в импульсе i, и рассуждаем как в доказательстве Теоремы 14.10:
Случай 1: Если q встречается среди g,,...,, q точно принял v.
Случай 2: Если q не встречается среди g,,...,, и,, то p пересылает значение процессу q, который примет его в этом случае.
Случай 3: Если q не встречается и i = t + 1, по крайней мере один из процессов, который подписал сообщение, допустим r, корректен. Процесс r также переслал значение v процессу q, что значит, что v находится в.
Для (2): Предположим, что в конце алгоритма, и пусть w - второе значение, принятое p. Снова подобным рассуждением можно показать, что, что означает, что. (Равенство и не может быть получено, так как процесс p не будет пересылать свое третье принятое значение или более поздние.)
Доказав (1) и (2), предположим, что корректный процесс p останавливается на, то есть. Затем, из (1), v содержится во всех для корректного q, но, следовательно, не шире одиночного элемента {v}; иначе - не одиночный элемент, из (2). Следовательно, каждый корректный процесс q также останавливается на v. Далее, предположим, что корректный процесс p останавливается на значении по умолчанию, так как - не одиночный элемент. Если пуст, каждый корректный q имеет пустой по (1) и если, то по (2); следовательно, q также останавливается на значении по умолчанию.
o
Долев и Стронг в дальнейшем улучшили алгоритм и получили алгоритм, который решает проблему Византийского-вещания за то же самое число импульсов и всего за О(Nt) сообщений.
14.2.2 Реализация Цифровых Подписей
Так как подпись p должна представлять собой достаточное доказательство того, что p - создатель сообщения, подпись должна состоять из некоторой формы информации, которая
(1) Может быть эффективно вычислена процессом p (подписана);
(2) Не может быть эффективно вычислена любым другим процессом, отличным от p (подделана).
Мы должны немедленно отметить, что, для большинства схем подписи, использующихся сегодня, второе требование не доказано до такой степени, что показана экспоненциальная трудность проблемы подделки. Обычно, проблема подделки, как показывают, связана (или иногда эквивалентна) с некоторой вычислительной проблемой, которая изучалась в течение длительного времени в отсутствие знания о ее полиномиальной разрешимости. Например, подделывание подписей в схеме Фиата-Шамира требует разлагать на множители большие целых числа; так как последняя задача (предположительно) в вычислительном отношении очень сложна, первая, должно быть, также сложна в вычислительном отношении.
Были предложены схемы подписи, основанные на различных, как предполагается, трудных проблемах, типа вычисления дискретного логарифма, разложения на множители больших чисел, проблемы рюкзака. Требования (1) и (2) подразумевают, что процесс p должен иметь вычислительное "преимущество" над другими процессами; это преимущество - некоторая секретная информация во владении p, секретный (или частный) ключ p. Таким образом, вычисление эффективно, когда секретный ключ известен, но (предположительно) трудно без этой информации. Ясно, что если p удается хранить свой ключ в тайне, то только p может с легкостью вычислять.
Все процессы должны уметь проверять подписи, то есть, имея сообщение М и подпись S, должно быть возможно эффективно проверить, что S действительно был вычислен из М с помощью секретного ключа p. Эта проверка требует, чтобы была раскрыта некоторая информация о секретном ключе p; эта информация - общий ключ p. Общий ключ должен позволять проверку подписи, но нужно, чтобы его быть невозможно или по крайней мере в вычислительном отношении трудно использовать для вычисления секретного ключа p или подделки подписей.
Наиболее успешные схемы подписи, предложенные до настоящего времени, основаны на вычислениях из теории чисел в арифметических кольцах по модулю больших чисел. Базисные арифметические операции добавления, умножения, и возведения в степень могут выполняться в этих кольцах за полиномиальное время от длины модуля (в битах). Деление возможно, если знаменатель и модуль взаимно просты (то есть, не имеют общих простых делителей), и может также выполняться за полиномиальное время. Так как подписание и проверка требуют вычислений над сообщением, М интерпретируется как большое число.
14.2.3 Схема Подписи ЭльГамаля
Схема подписи ЭльГамаля [EIG85] основана на функции теории чисел под названием дискретный логарифм. Для большого простого числа P, группа по умножению по модулю P, обозначаемая, содержит P-1 элементов и чвлчется циклической. Последнее означает, что можно выбрать такой элемент, что P-1 чисел
все различны и следовательно, перечисляют все элементы. Такое g называется генератором, или также ïåðâîîáðàçíûм êîðíем по модулю P. Генератор не уникален; обычно их много. Имея фиксированное P и генератор g, для каждого имеется уникальное целое число i по модулю P-1 такое, что (равенство в). Это i называется дискретным логарифмом (иногда индексом) x. В отличие от вышеупомянутых базисных арифметических операций, вычислять дискретный логарифм не просто. Это - хорошо-изученная проблема, для которой до настоящего времени не найдено эффективное общее решение, но также не была доказана ее труднорешаемость; см. [0dl84] для краткого обзора результатов.
Схема подписи ЭльГамаля [EIG85] основана на трудности вычисления дискретных логарифмов. Процессы совместно используют большое простое число P и ïåðâîîáðàçíûй êîðень g из. Процесс p выбирает в качестве своего секретного ключа число d, случайно между 1 и P - 2, и общий ключ p - число; заметьте, что d - дискретный логарифм e. Подпись p можно эффективно вычислить, зная логарифм e, и следовательно она формирует неявное доказательство того, что подписывающий знает d.
Действительная подпись для сообщения М - пара (r, s), удовлетворяющая. Такую пару p легко найдет с помощью секретного ключа d. Процесс p выбирает произвольное число a, взаимно простое с P-1, и вычисляет
и
Эти числа действительно удовлетворяют
(Все равенства в.) Действительность подписи S = (r, s) для сообщения М легко проверить, проверяя на равенство.
Алгоритмы для дискретного логарифма. Так как секретный ключ p, d, равняется дискретному логарифму общего ключа, e, схема раскрыта, если можно эффективно вычислять дискретные логарифмы по модулю P. До настоящего времени, не известно эффективного алгоритма, чтобы делать это в общем случае или подделывать подписи любым другим способом.
Общий алгоритм для вычисления дискретных логарифмов был представлен Одлыжко [0dl84]. Его сложность имеет тот же порядок, как у хорощо известных алгоритмов для разложения на множители целых чисел, столь же больших как P. Алгоритм сначала вычисляет несколько таблиц, используя только P и g, и, во второй фазе, вычисляет логарифмы для данных чисел. Если Q самый большой простой множитель P-1, время для первой фазы и размер таблиц имеют порядок Q; следовательно, желательно выбрать P такой, что P-1 имеет большой простой множитель. Вторая фаза, подсчет логарифмов, может выполняться в течении секунд даже на очень маломощных компьютерах. Следовательно, необходимо менять P и g достаточно часто, допустим каждый месяц, так, чтобы таблицы для конкретного P устаревали до их завершения.
Рандомизированное подписывание (подписывание с уравниванием вероятностей). Рандомизация в процедуре подписывания делает каждую из различных подписей[1] для данного сообщения одинаково вероятным результатом процедуры подписывания. Таким образом, один и тот же документ, подписанный дважды, почти обязательно произведет две различных действительных подписи. Рандомизация необходима в процедуре подписывания; если p подписывает два сообщения, пользуясь одним и тем же значением a, из подписей можно вычислить секретный ключ p; см. Упражнение 14.6.
14.2.4 Схема Подписи RSA
Если n - большое число, произведение двух простых чисел P и Q, то очень трудно вычислить квадратный корень и корни более высоких порядков по модулю n, если не известно разложение на множители. Возможность вычисления квадратных корней можно использовать, чтобы найти множители n (см. Упражнение 14.7), что показывает, что вычисление квадратных корней является таким же трудным, как и разложение на множители.
В схеме подписи Ривеста, Шамира и Эйдлмана [RSA78], общий ключ p - большое число n, разложение которого на множители p знает, и показатель степени e. Подпись p для сообщения М - e-й корень М по модулю n, который легко проверить, пользуясь возведением в степень. Этот корень более высокого порядка находится p также с использованием возведения в степень; при генерации своего ключа p вычисляет число d такое, что, что означает, что, то есть, - e-й корень М. Секретный ключ p состоит только из номера d, то есть, p не должен запоминать разложение на множители n.
В схеме RSA, p показывает свой идентификатор вычислением корней по модулю n, что требует (неявного) знания разложения n на множители; предполагается, что только p знает его. В этой схеме каждый процесс использует свой модуль.
14.2.5 Схема Подписи Фиата-Шамира
Более тонкое использование трудности нахождения (квадратных) корней сделано в схеме Фиата и Шамира [FS86]. В RSA схеме процесс подписывает сообщение, показывая, что он способен вычислять корни по модулю своего общего ключа, а способность вычислять корни возможно требует знания разложения на множители. В схеме Фиата-Шамира процессы используют общий модуль n, разложение на множители которого известно только доверенному центру. Процессу p даются квадратные корни некоторых специфических чисел (в зависимости от идентифика
|
|
|
