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

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

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

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

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

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

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

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

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

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

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

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