Схема Диффи -- Хеллмана по составному модулю

В работе Шмуели [S] предлагается использовать в качестве модуля в схеме Диффи -- Хеллмана не простое, а составное число. и -- различные простые числа. Шмуели также доказал, что произвольный алгоритм , находящий с вероятностью, которая не является пренебрежимо малой, общий секретный ключ по данным модулю вышеуказанного вида, базе , являющейся случайным элементом нечетного порядка группы , и открытым ключам и , может быть преобразован в алгоритм факторизации (т. е. нахождения и ) с не пренебрежимо малой вероятностью. Однако этот результат (в виде, приведенном в [McC88]) не позволяет утверждать, что если полиномиален, то и полиномиален. Это можно утверждать, если и выбраны некоторым специальным образом. Но сложность задачи факторизации произведений простых чисел специального вида, вообще говоря, может быть ниже сложности общей задачи факторизации.

В той же работе [McC88] МакКарли, развивая подход Шмуели, построил протокол типа Диффи -- Хеллмана, в котором модуль есть произведение двух различных простых чисел специального (отличного от упомянутого при обсуждении результата Шмуели) вида, а база фиксирована (а именно, ), и доказал его стойкость против пассивного противника в предположении сложности факторизации . Однако это предположение, вообще говоря, может быть сильнее стандартного криптографического предположения о сложности общей задачи факторизации.

Дальнейшее развитие методов работы [McC88] привело к построению М. И. Анохиным (см. также [Ан]) следующего протокола типа Диффи -- Хеллмана, который мы приведем более подробно. В этом протоколе предполагается наличие центра доверия, который для обеспечения возможности выработки участниками A и B общего секретного ключа выполняет следующие действия:

1) выбирает различные большие простые числа и (например, так, что -- случайный элемент множества всех двухэлементных множеств простых чисел длины, равной параметру безопасности);

2) выбирает случайный элемент нечетного порядка в группе (например, выбрав и и вычислив (единственный) такой, что и ; здесь и таковы, что и , где и нечетны);

3) передает и участникам A и B (по каналу, открытому для прослушивания, но недоступному для изменения данных) или помещает их в сертифицированный справочник, сохраняя и в секрете.

После этого для выработки общего секретного ключа A и B выполняют следующий протокол:

1. A выбирает , вычисляет и посылает его B, сохраняя в секрете.

2. B выбирает , вычисляет и посылает его A, сохраняя в секрете.

3. A вычисляет .

4. B вычисляет . Очевидно, что .

К данному протоколу применим метод аутентификации участников, описанный в п. 1.1.

В работе [Ан] доказано, что в предположении отсутствия эффективных алгоритмов факторизации этот протокол является стойким (против пассивного противника). Подчеркнем, что простые множители и в этом протоколе могут быть выбраны произвольно, поэтому в отличие от вышеупомянутых результатов Шмуели и МакКарли здесь мы имеем стойкость при стандартном криптографическом предположении о сложности общей задачи факторизации. С другой стороны, в схеме МакКарли база фиксирована, тогда как стойкость данной схемы доказана для случая, когда противник имеет возможность выбирать базу . Отметим также, что знание (случайного элемента нечетного порядка в ) не облегчает факторизацию , так как, зная только , можно эффективно сгенерировать (с не пренебрежимо малой вероятностью) элемент, имеющий то же самое распределение, что и .

 

Вопросы:

1. Понятие криптографического протокола.

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

3. Протоколы идентификации и их классификация.

4. Связь стойкости протокола со стойкостью базовой криптографической системы.

5. Реализация протоколов идентификации на основе симметричных систем шифрования.

6. Реализация протоколов идентификации на основе асимметричных систем шифрования.