Введение к работе
Актуальность работы Сенсорные сети представляют собой новое семейство беспроводных сетей со своими задачами и особенностями. Они используются для таких задач как мониторинг окружающей среды и среды естественного обитания, контроль производственных процессов, регулирование дорожного движения, охрана объектов и т.д. Обычно сенсорная сеть состоит из множества сенсоров, которые помещены в контролируемую среду. Каждый сенсор оснащен специальным датчиком, который позволяет совершить необходимые измерения параметров окружающей среды, и передатчиком для передачи этих данных на базовую станцию. При этом ресурсы сенсора сильно ограничены, прежде всего, небольшой емкостью его батарейки, а значит, передача дапных напрямую к базовой станции энергетически невыгодна. Использование агрегации в сенсорной сети позволяет значительно повысить экономичность и живучесть этой сети. В том случае, когда базовой станции требуется определить интегральную характеристику для какого-либо участка сети, один из узлов этого участка назначается агрегатором. Агрегатор собирает с остальных узлов этого участка частные значения определяемой характеристики, вычисляет агрегатную функцию (среднее, минимум, максимум и т.д.) и передает это значение базовой станции. При этом общие затраты на передачу информации существенно ниже, чем при отсутствии агрегатора. Однако, при ошибках в работе сенсоров требуются специальные надежные алгоритмы агрегации. Например, в присутствии злоумышленника, способного захватывать узлы и менять их функциональность, захват агрегатора полностью разрушает функцию агрегации, т.к. захваченный агрегатор может отправить на базовую станцию фиктивный отчет. Для решения этой проблемы можно использовать специальные криптографические процедуры, которые позволят базовой станции с большой вероятностью определить некорректный результат агрегации. В таком случае агрегация будет называться надежной. Понятно, что обеспечение надежности требует от агрегатора передачи на базовую станцию каких-то дополнительных данных, объем которых при заданной надежности должен быть минимизирован. В известных протоколах надежной агрегации объем дополнительных данных достаточно высок, что обуславливает дальнейший интерес к разработке протоколов надежной агрегации.
Для обеспечения работы протокола надежной агрегации в сети также должен быть реализован протокол управления ключами. При этом решения, используемые в классических сетях, в силу ограниченности сенсоров и невозможности использования инфраструктуры не могут быть применены для сенсорных сетей. Протоколы, специально разработанные для сенсорных сетей, также обладают недостатками, главный из которых - большое количество ключей, хранимых каждым сенсором.
При разработке надежного метода агрегации данных также необходимо решить задачу фильтрации фиктивных пакетов внутри сети. Это означает, что узлы, задействованные в передаче финального отчета на базовую станцию, должны иметь возможность определить, является ли пакет фиктив-
иым или нет. Наличие такого механизма позволит существенно уменьшить потребление энергий на передачу фиктивных пакетов в сети. Решение задачи фильтрации пакетов может быть основано на схеме распределенной подписи RSA.
Цель работы состоит в разработке и исследовании протоколов надежной агрегации данных в сенсорных сетях.
Для достижения поставленной цели в работе решались следующие основные задачи:
исследование методов надежной агрегации данных в сенсорных сетях;
разработка нового протокола надежной агрегации;
исследование и разработка протокола управления ключами в сенсорных сетях;
исследование и разработка схемы распределенной подписи RSA.
Методы исследования: для решения поставленных задач в работе
используются методы теории чисел, комбинаторного анализа, алгебры и теории сложности алгоритмов.
Научной новизной обладают следующие результаты работы:
» протокол надежной агрегации данных для сенсорных сетей;
в нротокол управления ключами в сенсорных сетях;
« схема распределенной подписи RSA с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участии дилера.
Практическая ценность данной работы определяется тем, что предложенный метод надежной агрегации способствует как снижению объема передаваемых данных внутри сети, так и повышению надежности получаемых данных.
Результаты работы использовались в разработках ООО «Техноком» и в учебном процессе Санкт-Петербургского государственного политехнического университета.
Апробация результатов работы. Основные положения и результаты диссертации докладывались и обсуждались на VI, VII, X научных сессиях аспирантов ГУАП (г. Санкт-Петербург 2003, 2004, 2007), а также на семинарах кафедры «Безопасности информационных систем» ГУАП и кафедры «Распределенных вычислений и компьютерных сетей» СПбГПУ. Зарегистрированы программные разработки в отраслевом фонде алгоритмов и программ: регистрационный номер Гос. ФАП 50200601950, 2006 г.; регистрационный номер Гос. ФАП 50200601951, 2006 г.
Публикации. По теме диссертации опубликовано 8 печатных работ, в том числе 2 статьи в рецензируемом журнале по перечню ВАК.
Основные положения, выносимые на защиту:
-
протокол надежной агрегации данных в сенсорных сетях, позволяющий снизить объем передаваемых данных внутри сети и повысить надежность полученного результата;
-
протокол управления ключами в больших сенсорных сетях, позволяющий уменьшить количество хранимых ключей;
3. схема распределенной подписи RSA с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участия дилера.
Структура работы. Диссертационная работа изложена на 122 странице и состоит из введения, 3-х глав с выводами, заключения и списка использованных источников литературы, включающего 59 наименований. Основное содержание работы включает 16 рисунков и 5 таблиц.
Во введении обоснована актуальность темы диссертации, сформулированы цели диссертационной работы и основные задачи, основные положения, выносимые на защиту, кратко изложено содержание работы по разделам.
Первый раздел посвящен методам надежной агрегации данных в сенсорных сетях. В подразделе 1.1 приводится постановка задачи надежной агрегации. В подразделе 1.2 приводится обзор известных протоколов надежной агрегации. Подраздел 1.3 содержит описание разработанного протокола надежной агрегации, анализ которого приводится в подразделе 1.4.
В современном мире беспроводные сенсорные сети помогают решать множество задач, связанных с мониторингом различных процессов и территорий. Сенсорные сети состоят из множества сенсоров, распределенных но исследуемой поверхности, и базовой станции, с помощью которой осуществляется контроль и управление сетью. Сенсоры являются автономными устройствами, обладают низкопроизводительным процессором, небольшим объемом памяти и маломощным передатчиком. Задачей каждого сенсора является сбор определенной информации и последующая ее передача на базовую станцию.
Использование агрегации в сенсорной сети позволяет значительно повысить экономичность и живучесть сети. В том случае, когда базовой станции требуется определить интегральную характеристику для какого-либо участка сети, один из узлов этого участка назначается агрегатором. Он собирает с остальных узлов этого участка частные значения определяемой характеристики, вычисляет агрегатную функцию от них (среднее, минимум, максимум и т.д.) и передает это значение базовой станции. При этом общие затраты на передачу информации существенно ниже, чем при отсутствии агрегатора. Если количество сенсоров в сети достаточно велико, сеть обычно разбивается на кластеры и агрегация выполняется в каждом кластере независимо.
Так как часто сенсорные сети разворачиваются на открытой и легкодоступной территории, необходимо использовать специальные процедуры для защиты передаваемой информации от возможных случайных или преднамеренных искажений. Обеспечение надежности агрегированного результата наиболее важно, так как его искажение может привести к более сильному искажению информации о контролируемых параметрах, чем искажение данных отдельных сенсоров.
Защита передаваемой информации от преднамеренных искажений требует использования методов аутентификации передаваемых сообщений. Для этого используются коды проверки подлинности сообщений (МАС-коды).
Это требует наличия протокола управления ключами.
Известны два способа обеспечения надежной агрегации. Первый основан на распределенности процесса агрегации путем вовлечения в него дополнительных сенсоров. Второй способ основан на усложнении протокола взаимодействия между базовой станцией и агрегатором. В рамках этого протокола агрегатор должен доказать базовой станции корректность представленного результата.
Так в рамках первого подхода известна схема, основанная на использовании древовидной маршрутизации. Корнем дерева является базовая станция. Направление агрегации - от листьев к корню. При этом в каждом узле вычисляется агрегатная функция от значений, полученных от потомков, и вычисленное значение вместе со значениями аргументов передается узлу-родителю. В этом случае узел-родитель может проверить правильность агрегации, выполненной дочерними узлами. Однако, данная схема не обладает достаточной надежностью: в частности, результат агрегации может оказаться некорректным при неправильной работе двух соседних узлов в дереве. Более того, в данном протоколе ограничено число вычисляемых функций агрегации, например, невозможно вычислить медиану.
Другое решение основано на использовании так называемых узлов-свидетелей, которые фактически дублируют действия агрегатора. Если результат агрегации, полученный свидетелями, совпадает' с результатом агрегатора, то они подписывают результат. После этого агрегатор отправляет результат и подписи свидетелей на базовую станцию. Недостатком данного решения является то, что объем передаваемых сенсорами данных линейно возрастает при увеличении числа узлов-свидетелей.
В рамках второго подхода известен протокол, основная идея которого заключается в следующем. Агрегатор собирает от сенсоров данные, вычисляет агрегированное значение, подписывает его и отправляет базовой станции. После этого между агрегатором и базовой станцией выполняется интерактивный протокол доказательства корректности вычислений. Недостатком данного решения является передача большого объема данных между агрегатором и базовой станцией.
Для достижения надежной агрегации предлагается протокол, основанный на распределенной верификации результата агрегации. В протоколе участвуют следующие стороны: базовая станция (BS), агрегатор (А), сенсоры (Sj), и t узлов-верификаторов (Vi). Агрегатор и верификаторы - это обычные сенсоры, выбираемые базовой станцией внутри кластера случайным образом. Периодически базовая станция переназначает агрегатора и верификаторов.
Протокол состоит из трех этапов: вычисление результата агрегации, проверка полученного результата t узлами-верификаторами и отправка результата агрегации вместе с подписями верификаторов базовой станции.
На первом этапе все сенсоры отправляют свои данные агрегатору:
Sj -+ A : {datdj, MAC(I
pa Sj и агрегатора А. Агрегатор собирает все данные, проверяет их подлинность, используя соответствующие МАС-коды, и вычисляет результат агрегации.
На втором этапе производится распределенная проверка результата агрегации, состоящая из двух шагов.
1). Агрегатор предоставляет верификаторам все собранные данные:
А -* Verifiers : {D, MAC(KVi,a, D),..., MAC(KVt,A, >)}>
где D — {datai,..., doto„}.
2). Каждый верификатор Vj (і = 1, t) анализирует соответствующее значение кода проверки подлинности в полученном пакете. Если MAC правильный, верификатор случайным образом выбирает к сенсоров и запрашивает у них данные. Каждый сенсор Sj, получив запрос от Vj, высылает ответ:
Sj ~* Vi : {datajjMACiKsjy^dataj)}.
После того как верификатор Vj проверил подлинность МАС от сенсора Sj, он сравнивает соответствующие данные, полученные от агрегатора и от сенсора. Если эти значения различаются, то верификатор высылает базовой станции предупреждающее сообщение. Если во время верификации узел Vi не находит несоответствия данных, то он подписывает результат агрегации ключом, общим с базовой станцией:
V, - A : {SNVi,MAC(KVi,A,SNVi)},
где SNvi — MAC{Kvubs,AR) и AR - результат агрегации.
На третьем этапе агрегатор собирает подписи от всех узов-верификаторов, формирует отчет, подписывает его и отправляет на базовую станцию:
A~*BS: {AR, SNVl ... SNVt MAC{Ka,bs, AR)}.
Для проверки полученного отчета базовая станция вычисляет все подписи, объединяет их, используя операцию XOR, и сравнивает вычисленное значение с полученным. Если отличий нет, то результат пршшмается и считается правильным.
Для данного протокола можно определить вероятность принятия базовой станцией искаженного результата агрегации:
р**-т->-(%в+(1-%й)'У-
где п - количество сенсоров в кластере, t - количество узлов-верификаторов, к - количество запросов от каждого узла-верификатора, т — количество
Таблица 1. Сравнение коммуникационных издержек в различных протоколах надежной агрегации
искаженных отчетов в пакете, предоставленном верификаторам для проверки, р - вероятность некорректной работы узла-верификатора.
В таблице 1 показано сравнение коммуникационных издержек для разработанного и известных протоколов. Сравнение производилось для кластера из ста узлов, с вероятностью некорректной работы узла-верификатора 0,1 и с вероятностью принятия базовой станцией искаженного результата агрегации, меньшей или равной 0,05. В пакете, отправляемом сенсором, данные занимают два байта, а код проверки подлинности - десять байт. Сравнение коммуникационных издержек показывает существенное преимущество разработанного протокола в сравнении с известными.
Второй раздел посвящен протоколам управления ключами в сенсорных сетях. В подразделе 2.1 рассматриваются особенности сенсорных сетей с точки зрения протокола управления ключами. В подразделе 2.2 приводится обзор известных протоколов управления ключами. Подраздел 2.3 содержит описание предлагаемого протокола управления ключами в сенсорных сетях. Анализ этого протокола приводится в подразделе 2.4.
Для обеспечения работы протокола надежной агрегации в сети также должен быть реализован протокол управления ключами. Он должен обеспечить наличие парных ключей между базовой станцией и всеми сенсорами, а также между всеми сенсорами одного кластера.
Сенсорные сети обладают рядом особенностей, значительно усложняющих разработку протокола управления ключами.
1). Малый объем доступной памяти у сенсоров. Это означает, что количество ключей, хранимых каждым сенсором, должно быть минимизировано.
2), В сети нет надежных узлов, кроме базовой станции, однако, ее ис-
пользование в рамках протокола управления ключами приводит к существенному росту энергетических затрат и, следовательно, значительно уменьшает срок службы сети.
3). Нет априорной информации о соседних узлах. Часто развертывание сети производится путем случайного разбрасывания сенсоров (например, с самолета), а, следовательно, знание о будущих соседях до развертывания сети отсутствует. Однако, даже в случае развертывания сети вручную большое количество узлов делает затруднительным определение собственного положения и множества соседей для каждого отдельного узла.
4). В сети должен быть предусмотрен метод добавления новых сенсоров. При этом для уже существующих в сети сенсоров необходимо минимизировать количество новых ключей и энергетические затраты на их получение.
Данные особенности сенсорных сетей привели к тому, что в настоящее время практически все решения для протокола управления ключами основаны на использовании схемы предварительной раздачи ключей, в рамках которой ключи предустанавливаются на сенсоры до развертывания сети. Однако, отсутствие априорной информации о соседних узлах нриводит к раздаче большого числа ключей и существенно уменьшает стойкость системы к компрометации ключей.
Существенно более эффективный подход был предложен в протоколе LEAP. Авторы использовали два допущения: ключи не могут быть скомпрометированы в течение первых Tmin секунд после добавления сенсора в сети и все узлы в сети неподвижны. В рамках данного протокола на все сенсоры предустанавливается один и тот же мастер ключ К і- При добавлении нового узла и в сеть он вычисляет свой индивидуальный ключ как Ки — f{Ki,idu), где / - односторонняя функция, находит все сенсоры в своем кластере и для каждого сенсора v, принадлежащего кластеру, вычисляет парный ключ как Kuv = f(Kv,u). Узел v также вычисляет ключ Kuv независимо от узла и. По истечении времени Tmin мастер ключ Ki стирается. Данное решение обладает идеальной стойкостью к компрометации ключей, но при этом количество ключей, хранимых каждым узлом, линейно зависит от количества сенсоров в кластере этого узла. Это делаег данное решение неприемлемым для кластеров большого размера.
Уменьшение количества ключей может быть достигнуто за счет использования тех же допущений, что и в схемах предварительной раздачи ключей.
1). Один и тот же ключ может принадлежать более чем двум узлам.
2). Два узла могут иметь более одного общего ключа.
Кроме того, должно выполняться следующее условие; узлы, не являющиеся непосредственными соседями, не должны иметь общих ключей.
Такая схема раздачи ключей может быть рассчитана при наличии информации о местоположении всех сенсоров. Однако, в сенсорной сети положение сенсоров до развертывания сети неизвестно и, следовательно, такая схема может быть выработана динамически только после установки сенсоров. Фактически, это означает распределение протокола выдачи ключей между всеми узлами в сети.
Каждый узел и использует свое множество ключей Kf, которое состоит из двух подмножеств:
1). Подмножество предустановленных ключей Kf = {Kf}. Это подмножество может быть сгенерировано непосредственно самим узлом или предустановлено перед добавлением узла в сеть.
2). Подмножество собранных ключей Kf — {Kf}. Это подмножество формируется из ключей, присланных соседними узлами.
После того как узел и выполнил с узлом v взаимную аутентификацию и установил начальное соединение, он посылает узлу v случайно выбранное подмножество (оно может быть пустым) своих предустановленных ключей Kfn получает в свою очередь часть подмножества предустановленных ключей узла V. Полученные ключи каждый узел сохраняет в своем подмножестве собранных ключей.
Таким образом, каждый узел и получает некоторое подмножество ключей из множества (J Kf, где Nn - соседи узла и. Это множество может
быть интерпретировано как некоторый локальный общий пул ключей. Соответственно, парный ключ двух узлов uuv может быть получен из пересечения их множеств ключей Kf П Kf.
Таким образом, предлагаемый метод позволяет динамически распределить ключи так, чтобы узлы, расположенные далеко друг от друга, не имели общих ключей. Это свойство и обеспечивает уменьшение количества хранимых ключей до O(log(n)), где п — количество сенсоров в кластере.
В третьем разделе рассматривается задача фильтрации пакетов на основе распределенной подписи. В подразделе 3.1 приводится описание подхода к фильтрации пакетов на базе распределенной подписи и формулируются требования к схеме распределенной подписи. В подразделе 3.2 приводится описание примитивов, используемых для организации распределенной подписи. В подразделе 3.3 приводится обзор известных схем распределенной подписи RSA. В подразделе 3.4 предлагается модификация схемы разделения секрета, предложенной Шамиром, позволяющая обеспечить выполнение всех свойств, требуемых от схемы распределенной подписи. В подразделе 3,5 описана предлагаемая схема распределенной подписи и приведен ее анализ.
Использование только симметричных алгоритмов при аутентификации передаваемых от сенсоров к базовой станции данных имеет свои недостатки. Так, например, проверку подлинности финального отчета, посылаемого агрегатором на базовую станцию, может выполнить только сама базовая
станция. Это означает, что любой захваченный сенсор может вбрасывать в сеть фиктивные пакеты, которые будут отбрасываться базовой станцией, но при этом будут расходоваться ресурсы узлов, задействованных в передаче фиктивного пакета.
Для сенсорных сетей с более мощными узлами решение данной проблемы может быть основано на использовании распределенной асимметричной подписи. Такая подпись предполагает распределение секретного ключа асимметричного алгоритма цифровой подписи с помощью пороговой схемы разделения секрета между всеми участниками схемы и наличие протокола, позволяющего любой коалиции из заданного числа участников распреде-леино вычислить цифровую подпись для заданного сообщения. Применительно к задаче фильтрации фиктивных пакетов в сенсорных сетях алгоритм распределенной асимметричной подписи может быть использован следующим образом. Дилер выбирает и распределяет между всеми сенсорами секретный ключ выбранного алгоритма цифровой подписи. Кроме того, все сенсоры инициализируются открытым ключом. Отправляя результат агрегации на базовую станцию, его подписывают заданное количество сенсоров с помощью протокола распределенной подписи. При этом каждый сенсор, ретранслирующий данный пакет, используя открытый ключ, в состоянии проверить подпись. Если подпись не прошла проверку, пакет выбрасывается.
Для эффективной работы системы протокол распределенной подписи должен обладать рядом свойств. Одним из важнейших свойств распределенных схем подписи является возможность независимой' работы участников коалиции при постановке подписи. Данное свойство позволяет при изменении состава участников коалиции не перезапускать протокол постановки подписи, что приводит к сокращению задержки при постановке подписи. Еще одним свойством распределенных схем подписи является возможность самоорганизации, то есть должна быть предусмотрена возможность работы системы без участия дилера после этапа инициализации. При этом важным свойством является отсутствие интерактивности процедуры выдачи новой проекции без дилера. Для интерактивного протокола предполагается обмен данными между действующими участниками, что является существенным недостатком, так как растет объем трафика в системе, повышается расход энергии и требуется синхронизация действий сенсоров.
Распределенная схема цифровой подписи с описанными выше свойствами может' быть легко построена на основе цифровой подписи ЭльГамаля или DSS. В отличие от этих цифровых подписей, для цифровой подписи RSA в настоящий момент не известны схемы распределенной подписи с вышеперечисленными свойствами. Однако, цифровая подпись RSA обладает важным свойством, которым не обладают подписи ЭльГамаля и DSS - для подписи RSA процедура проверка подписи может быть значительно ускорена, если правильно выбрать значение открытого ключа. Это свойство обеспечивает значительное преимущество распределенной подписи RSA при использовании ее в сенсорных сетях.
Постановка задачи формулируется следующим образом. Модель сети
предполагает наличие п узлов и злоумышленника. Также предполагается, что существует доверенный дилер, который инициализирует схему: для этого он выбирает секретный шпон RSA и безопасно распределяет этот ключ среди узлов, обеспечивая (*,п)-порошвую схему, после чего его участие не требуется. Будем считать, что злоумышленник может захватить s
Так как атакующий взламывает многократную схему подписи, од может осуществить атаку по выбранному сообщению (chosen-message attack, CM А), то есть он может запросить кого-нибудь из п участников запустить протокол подішси для любого сообщения, которое выберет. Цель атакующего - либо подделать подпись для сообщения, которое он но просил подписать, либо сорвать подписание чужого сообщения другими участниками.
Распределенная схема подписи RSA должна позволять успешно противостоять действиям злоумышленника и для нее должны выполняться следующие свойства.
1). Процедура постановки подписи должна обеспечивать независимость действий участников коалиции.
2). Система должна обладать свойством самоорганизации, то есть после инициализации не нуждаться в участии дилера.
3). Процедура выдачи проекции секрета без дилера должна быть неинтерактивна.
В существующих работах, посвященных распределенной подписи RSA, можно выделить три основных подхода к распределению секретного ключа RSA.
При первом подходе подразумевается, что секретный ключ d распределяется по схеме разделения секрета Шамира над кольцом Д^(л/) (или Zx{N))> гДе Ф(Ю (или КЩ) не опубликованы. Отсутствие информации о 4>(N) (или X(N)) делает невозможной работу системы без участия доверенного дилера.
При втором подходе предполагается наличие дополнительного уровня в схеме разделения секрета. При этом, сначала секрет разделяется между п узлами аддитивно, а потом каждая полученная проекция распределяется при помощи пороговой схемы. Подобные схемы интерактивны и неработоспособны без дилера.
При третьем подходе предполагается разделение секретного ключа d над известным кольцом Z^ вместо 2ф(щ или ZX(n)- Но такое разделение для подписи RSA приводит к уязвимости распределенной схемы. Кроме того, данный подход не предполагает возможности независимой работы участников коалиции при постановке подписи.
Таким образом, каждый из упомянутых ранее подходов имеет некоторые функциональные ограничения и не обеспечивает выполнение по крайней мере одного из сформулированных выше свойств.
Одним из компонентов распределенной схемы подписи является схема разделения секрета. В частности, может быть использована схема Ша-мира. В ней предполагается заданным полином f(x) — fo + fix + ... + /(_іж4-1 mod Р, в котором /0 = S - секрет, /і,—,/t-i - случайные значения, а Р - простое число. Каждый участник протокола получает проекцию секрета в виде ss = f(id), где id - идентификатор участника. Любая коалиция К- из t участников сможет восстановить секрет /о = / (0), используя интерполяцию по Лаграижу: /(0) = J2 ssuZu(0)(modP), где 1и(х) - коэф-
«єк фициенты Лагранжа.
Чтобы использовать схему Шамира для распределенной подписи RSA, необходимо выбрать секрет S и модуль Р. Для распределенной подписи RSA секретом является секретный ключ й. Относительно модуля Р имеется две возможности: либо сделать его публичным, например Р = N, либо сделать его секретным, положив Р —
Для устранения вышеуказанных недостатков необходимо отказаться от использования модуля Р. Однако, процедура выдачи проекций без дилера остается интерактивной. Кроме того, отказ от Р приводит к росту размера проекций, а следовательно и сложности постановки подписи. Для размера проекции секрета R легко получить верхнюю оценку: R < log(N)+(t—l)k+ 1, где N - модуль RSA, t - размер коалиции, к - длина идентификатора пользователя.
Например, при длине идентификатора участника к = 48 бит и размере коалиции t = 10 размер проекции не будет превосходить log(N) + 48 (і -1) +1 « 1500 бит, что означает увеличение сложности постановки подписей приблизительно в полтора раза.
Чтобы избавиться от интерактивпости в процедуре выдачи новой проекции без дилера и снизить размер используемых для подписи проекций секрета, предлагается модифицировать схему разделения секрета следующим образом.
Вводится в рассмотрение простое число Q > max(idj). Проекции секрета вычисляются по формуле:
t-i t-i f(x, V)=Y,Y, Мх* mod W mod Q)-
is=0 i=0
При таком задании функции разделения секрета нельзя использовать
интерполяцию ло Лагранжу. Вместо этого необходимо решать систему линейных уравнений.
Для восстановления секрета каждый участник коалиции и вычисляет значение своей функции в точке х - О, получая f{0,idu) = /0 + Д(-Q) + . - + /f (У* mod Q) в точке у = idu. При этом /о = /о,о- Имея t значений дайной функции, можно восстановить секрет, решив следуюіцую систему уравнений:
/о
= G
/() /()
. /()
G =
{x^fmodQ (x^YmodQ ... ( )t_1 mod Q (xh) mod Q (xh)1 mod Q ... ()^1 mod Q
()0 mod Q ()1 mod Q ... ()4-1 mod Q
Для выдачи проекции новому участнику без дилера каждый участник коалиции и вычисляет значение своей функции в точке х = idnew, получая f{idneW)idu) = sncw{idu) = sQ+si(y mod Q) + .. .+st_i(j/t_1 mod Q) в точке у = idu.
so si
4-і
Проекция секрета (so, зі,..., St_i) для нового абонента находится из системы уравнений:
o\xit)
Для предложенной схемы разделения секрета справедливо следующее утверждение.
Утверждение 2 Для модифицированной схемы разделения секрета верно, что:
-
схема является пороговой и безопасной;
-
процедура выдачи проекции в схеме неинтерактивна и не требует присутствия дилера;
-
процедура выдачи проекции в схеме безопасна;
-
размеры используемой для подписи части проекции в схеме ограничены сверху величиной log(N) + k -1-t.
На основе предложенной модифицированной схемы разделения секрета разработана следующая распределенная схема подписи RSA.
1. Инициализация схемы
-
Дилер генерирует простое число Q > max(idj).
-
Дилер генерирует публичный ключ RSA N=pqze>Q- простое число и вычисляет секретный ключ d ; ed = 1 mod Ф(Ы).
-
Дилер генерирует функцию
t-i t-i
f(*,y) = ЕЕ № mod W mod Q)>
i=0 j-0
где /o,o = d| е. коэффициенты Д.,- Є . выбраны случайным образом с соблюдением условия Д.,- = /^.
(d) Каждый узел и в качестве проекции секретного ключа получает
функцию
su(z) = f{x,idu).
2. Распределенная постановка подписи
(a) Выбирается коалиция К. из t участников. Каждый участішк ко
алиции вычисляет частичную подпись по формуле
Su(m)=m4'"(0)modIV,
где т - значение хэш-функции от нодписываемого сообщения и и К.
-
После получения t частичных подписей сборщик подписи составляет матрицу G для членов коалиции К, и обращает ее над полем рациональных чисел.
-
Сборщик подписи вычисляет G' = X-G~l, где А - наименьшее общее кратное знаменателей всех элементов матрицы G~l. После этого он вычисляет:
S'(m) = I П {SuM)Y'lJ ) mod N-
(d) Используя расширенный алгоритм Евклида, сборщик находит
такие х, у, что
хХ + уе — 1.
(e) Подпись вычисляется как S(m) ~ ((S'(m))x mv) mod N.
3. Выдача проекции ключа новому пользователю
(а) Для получения проекции секретного ключа новый узел и должен найти коалицию /С из t уже нроинициализироваипых узлов и
Сообщить ИМ СВОЄ idnew
-
Каждый участник коалиции и вычисляет значение своей функции в точке х - idnaW) получая f(idnBUI,idu) = snew(idu) = so + si{y mod Q)+ ... + st-iiy1'1 mod Q) в точке у = idu.
-
Новый узел находит свою проекцию секрета (яо,«і, ...,st_i) из системы уравнений:
Таким образом, выдачи проекции секретного ключа новому узлу не требует участия дилера и является пеинтерактивиой.
Для предложенной схемы показано, что она позволяет генерировать корректную подпись RSA. Кроме того, справедливо следующее утверждение.
Утверждение 3 Предложенная -распределенная схема подписи столь же безопасна, как и RSA.
Таким образом, предложенная схема распределенной подписи RSA, в отличие от известных схем, обладает следующими достоинствами: действия участников коалиции при постановке подписи независимы, протокол выдачи проекций секретного ключа неинтерактивен и не требует участия дилера после инициализации системы.
В заключении сформулированы основные результаты диссертационной работы.
