Программные продукты и системы

Данная работа посвящена распределенной схеме подписи RSA, которая определяется процедурой разделения секретного ключа RSA среди участников системы и процедурой совместной постановки подписи подгруппой участников. Одним из важнейших свойств распределенных схем подписи является отсутствие интерактивности процедуры выдачи новой проекции без дилера. Для интерактивного протокола предполагается обмен данными между действующими участниками, что является существенным недостатком, так как растет объем трафика в системе, повышается расход энергии и требуется синхронизация действий узлов. Другим важным свойством распределенных схем подписи является возможность независимой работы участников коалиции при постановке подписи. Данное свойство при изменении состава участников коалиции позволяет не перезапускать протокол постановки подписи, что приводит к сокращению задержки при постановке подписи. Еще одним свойством распределенных схем подписи является возможность самоорганизации, то есть должна быть предусмотрена возможность работы системы без участия дилера после этапа инициализации.

В существующих работах, посвященных распределенной подписи RSA, можно выделить три основных подхода к распределению секретного ключа RSA.

При первом подходе подразумевается, что секретный ключ  распределяется по схеме разделения секрета Шамира над кольцом  (или ), где  (или ) не опубликованы. Отсутствие информации о  (или ) делает невозможной работу системы без участия доверенного дилера.

При втором подходе предполагается наличие дополнительного уровня в схеме разделения секрета. При этом сначала секрет разделяется между n узлами аддитивно, а потом каждая полученная проекция распределяется при помощи пороговой схемы. Подобные схемы интерактивны и неработоспособны без дилера.

При третьем подходе предполагается разделение секретного ключа d над известным кольцом  вместо  или . Но такое разделение для подписи RSA приводит к уязвимости распределенной схемы. Кроме того, данный подход не предполагает возможности независимой работы участников коалиции при постановке подписи.

Таким образом, каждая из упомянутых ранее схем имеет некоторые функциональные ограничения и не отвечает по крайней мере одному из следующих требований:

-    процедура постановки подписи должна обеспечивать независимость действий участников коалиции;

-    система должна обладать свойством самоорганизации, то есть после инициализации не нуждаться в участии дилера;

-    процедура выдачи проекции секрета без дилера должна быть неинтерактивна.

В большинстве известных работ рассматривается схема разделения секрета Шамира. В схеме Шамира предполагается заданным полином , в котором  – секрет;  – случайные значения; P – простое число. Каждый участник протокола получает проекцию секрета в виде , где id – идентификатор участника. Любая коалиция K из t участников сможет восстановить секрет , используя интерполяцию по Лагранжу:  ), где  – коэффициенты Лагранжа.

Чтобы использовать схему Шамира для распределенной подписи RSA, необходимо выбрать секрет S и модуль P. Для распределенной подписи RSA секретом является секретный ключ d. Относительно модуля P имеется две возможности: либо сделать его публичным, например P=N, либо секретным, положив  или . Если P всем известно (например модуль RSA), это приведет к утечке информации и взаимозависимости действий участников коалиции во время выполнения процедуры постановки распределенной подписи. Если P – секретное значение (например  или ), то это приведет к невозможности самоорганизации системы. Следовательно, для устранения вышеуказанных недостатков необходимо отказаться от использования модуля P. Однако процедура выдачи проекций без дилера остается интерактивной. Кроме того, отказ от P приводит к росту размера проекций, а следовательно, и к сложности постановки подписи. Для размера проекции секрета R легко получить верхнюю оценку: , где N –модуль RSA; t – размер коалиции; k – длина идентификатора узла.

Опишем схему разделения секрета, для которой процедура выдачи проекции без дилера становится неинтерактивной, а размер проекции секретного ключа, используемой для постановки подписи, не превышает .

Введем в рассмотрение простое число  и будем вычислять проекции секрета по формуле:

.

При таком задании функции разделения секрета нельзя использовать интерполяцию по Лагранжу. Вместо этого необходимо решать систему линейных уравнений.

Для восстановления секрета каждый участник коалиции u вычисляет значение своей функции в точке x=0, получая   в точке . При этом . Имея t значений данной функции, можно восстановить секрет, решив следующую систему уравнений:

, где

.

Для выдачи проекции новому участнику без дилера каждый участник коалиции u вычисляет значение своей функции в точке , получая   в точке . Проекция секрета  для нового абонента находится из системы уравнений:

.

На основе описанной модифицированной схемы разделения секрета можно предложить следующую схему распределенной подписи RSA.

1.        Инициализация схемы.

(a)     Дилер генерирует простое число .

(b)     Дилер генерирует публичный ключ RSA  и  – простое число и вычисляет секретный ключ .

(c)      Дилер генерирует функцию

, где , а коэффициенты  выбраны случайным образом с соблюдением условия .

(d)     Каждый узел u в качестве проекции секретного ключа получает функцию  .

2.        Распределенная постановка подписи.

(a)     Выбирается коалиция K из t участников. Каждый участник коалиции вычисляет частичную подпись по формуле , где m – значение хэш-функции от подписываемого сообщения и .

(b)     После получения t частичных подписей сборщик подписи составляет матрицу G для членов коалиции K и обращает ее над полем рациональных чисел.

(c)      Сборщик подписи вычисляет , где  – наименьшее общее кратное знаменателей всех элементов матрицы .

(d)     Используя матрицу , он вычисляет:

.

(e)      Сборщик находит x,y такие, что .

(f)      Подпись вычисляется как  .

3.        Выдача проекции ключа новому узлу.

(a)     Для получения проекции секретного ключа новый узел u должен найти коалицию K из t уже проинициализированных узлов и сообщить им свое .

(b)     Каждый участник коалиции u вычисляет значение своей функции в точке , получая   в точке , и посылает его новому узлу.

(c)      Новый узел находит свою проекцию секрета , решая систему уравнений:

.

Таким образом, выдача проекции секретного ключа новому узлу не требует участия дилера и является неинтерактивной.

В заключение отметим, что предложенная схема распределенной подписи RSA обладает следующими достоинствами: действия участников коалиции при постановке подписи независимы, протокол выдачи проекций секретного ключа неинтерактивен и не требует участия дилера после инициализации системы.