Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Определение. Пусть G — конечная группа, Ь — элемент группы G я у — элемент группы G, являющийся степенью Ь. Любое целое число х, для которого Ьх = г/, называется дискретным логарифмом у по основанию Ь.
Пример 1. Возьмем G = F19 = (Z/19Z)* и порождающий элемент 2 в качестве b (см. пример 1 в § 11.1). Тогда дискретный логарифм числа 7 по основанию 2 равен 6.
Пример 2. Если а Є F9 есть корень уравнения X — X — 1 (см. пример 2 в §11. 1), то дискретный логарифм числа -1 по основанию а равен 4.
108
ГЛ. IV. ОТКРЫТЫЙ ключ
В конце раздела будет приведен краткий обзор известных алгоритмов решения задачи дискретного логарифмирования в конечных полях. Сначала же опишем несколько криптосистем с открытым ключом и систем специального назначения с открытым ключом, основанных на вычислительной сложности задачи дискретного логарифмирования в конечных полях.
Система Диффи—Хеллмана обмена ключами. Так как криптосистемы с открытым ключом значительно медленнее классических криптосистем (по крайней мере, при нынешнем состоянии науки и техники), то разумнее использовать их в качестве дополнения к классическим криптосистемам, с помощью которых и передаются сообщения. Зато процедуру согласования ключей классической криптосистемы можно очень эффективно реализовать с помощью системы с открытым ключом. Первая такая детально проработанная схема, предложенная Диффи и Хеллманом, основана на задаче дискретного логарифмирования.
Пусть ключом классической криптосистемы является большое случайно выбранное натуральное число (или набор таких чисел). Пусть, например, используется матричное аффинное преобразование пар биграмм (см. § III. 2)
где 0 ^ a,b,c,d,e, f < N и P — вектор-столбец, составленный из числовых эквивалентов двух соседних биграмм (составляющих вместе четырехбуквенный блок) открытого текста в TV-буквенном алфавите.
12
Выбрав случайно целое число к между 0 и TV , мы сразу определим а, 6, с, d, є, f как значения шести разрядов числа к в N -ичной системе счисления. (При этом надо проверить, что ad —be обратимо по модулю N , т. е. что это число не имеет общих множителей с TV; в противном случае выбирается новое к.)
Заметим, что выбор случайного целого в некотором интервале эквивалентен выбору случайного элемента большого конечного поля приблизительно такого же размера. Пусть, например, мы хотим выбрать случайное положительное к < TV12 и наше конечное поле простое и состоит из р элементов. Элементам поля Fp сопоставим, как обычно, целые от 0 до р — 1. Если полученное таким образом целое не
дг12 дг12
меньше TV , то приводим его по модулю 1У .
Если же наше поле имеет вид Fp/, то сначала выбирается Fp-базис этого поля. Таким образом, каждому элементу поля сопоставляется набор из / элементов поля Fp. Затем, рассматривая составляющие
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
109
набора как разряды целого числа, записанного в р-ичной системе счисления, получаем целое число, меньшее р*. Предупреждение. Эта
процедура устанавливает взаимно однозначное соответствие между Fp/ и Z/jt/z = {0,1,... ,р* - 1}. Эти два множества имеют совершенно различную структуру относительно операций сложения и умножения. Первое является полем, т.е. все р^ — 1 ненулевых элементов имеют обратные, а второе — кольцом, в котором это свойство нарушается
/-1 'ff \
для р из р элементов (для элементов, кратных р).
Теперь опишем метод построения случайного элемента большого конечного поля F9, разработанный Диффи и Хеллманом. Пусть значение q общеизвестно, т. е. все знают, из какого конечного поля выбирается ключ. Пусть, далее, д — некоторый фиксированный элемент F9, который также не является секретным. В идеале, д должен быть порождающим элементом группы F*. Однако в нашем случае в этом нет необходимости, так как описываемый ниже метод построения ключа дает только те элементы Fg, которые являются степенями элемента д. Если же мы хотим, чтобы случайный элемент мог принимать любые значения из F9, то д должен быть порождающим элементом.
Пусть два пользователя (Аида и Бернардо) хотят согласовать ключ - случайный элемент из F*, — посредством которого они будут зашифровывать переписку между собой. Аида выбирает случайное число а между 1 и q — 1, которое она держит в секрете, и вычисляет да Є F9, которое объявляет открыто. Бернардо делает то же самое: он случайно выбирает b и объявляет дЬ. В качестве секретного ключа используется даЬ. Оба пользователя могут вычислить этот ключ. Например, Аида знает д (это открытая информация) и свой собственный секретный ключ а. Однако посторонние знают только да и дЬ. Если для мультипликативной группы F* выполнено следующее предположение, то посторонние не смогут определить ключ.
Предположение Диффи-Хеллмана. Сложность вычисления даЬ по да и дЬ чрезвычайно велика.
Предположение Диффи-Хеллмана априори не слабее предположения о чрезвычайной сложности дискретного логарифмирования в конечной группе. Если бы можно было вычислять дискретные логарифмы, то, очевидно, предположение Диффи-Хеллмана было бы неверным. Некоторые считают, что справедливо и обратное, однако пока этот вопрос остается открытым. Другими словами, никто еще не предложил способ получения даЬ из да и дЪ без использования а и 6. Однако вполне возможно, что такой способ существует.
