Реферат: Распределенные алгоритмы

(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 даются  квадратные корни некоторых специфических чисел (в зависимости от идентификатора 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 бит с  по .

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42