Основы современной криптографии


Криптосистемы Меркля-Хеллмана и Хора-Ривеста - часть 5


будет лежать в заданном диапазоне, поскольку g порождает GF(p,h). Теперь пусть у нас есть различные x и y, такие что x*1 = y*1 = h, но x*a = y*a. Тогда, возводя g

в степень x*a и y*a, получим:

Поэтому мы также можем записать

и далее

.

Теперь заметим, что произведение в обеих частях неравенства представляет собой приведенный многочлен от t степени h. Иными словами, если бы мы вычислили оба этих произведения и заменили значение t

формальным параметром, например, z, тогда старшим членом на каждой стороне был бы x в степени h с коэффициентом 1. Мы знаем, что если мы подставим значение t вместо z, то значения этих двух полиномов будут равны. Поэтому вычтем один из другого, старшие члены сократятся, и если мы подставим t, то получим 0. Мы получили полином степени h–1, корнем которого является t. Но это противоречит тому, что мы выбрали t алгебраическим элементом степени h. Таким образом, доказательство закончено и построение корректно.

Хор разработал метод использования данного построения в качестве основы криптосистемы. Кратко он заключается в следующем. Мы выбираем p

и h достаточно маленькими, чтобы мы могли вычислять дискретные логарифмы в GF(ph). Хор рекомендует p около 200, а h

около 25. Затем мы выбираем t и g как указано выше. Для каждого из них будет много вариантов, и мы можем просто произвести случайный выбор (В действительности, будет так много пар <t,g>, что очень большое количество пользователей могут использовать одинаковые p и h, и вероятность того, что два пользователя выберут одинаковые ключи, будет пренебрежимо мала.). Затем мы следуем конструкции Боуза-Чоула. Мы вычисляем логарифмы по основанию g от t+i для каждого i, это даст нам

a. Наконец, мы выбираем случайную перестановку a, которая и будет нашим ключом. Мы публикуем результат перестановки a вместе с p

и h. Величины t, g и использованная перестановка остаются в секрете.

Чтобы послать сообщение A, B просто берет свое сообщение и вычисляет S = x*a. В действительности, это не так уж и просто, поскольку сообщение должно быть длиной p бит и должно быть x*1 = h, но Хор представил довольно прямолинейный метод преобразования неограниченной битовой строки в несколько блоков, каждый из которых имеет требуемую форму. А получает S. Он возводит g в степень S и выражает результат в виде полинома от t степени h с коэффициентами из GF(p). Далее он вычисляет h корней этого полинома, затем применяет обратную подстановку и получает индексы элементов в x, содержащих единицы.

Интересно отметить, что если кто-либо откроет эффективный метод вычисления дискретных логарифмов, то такой алгоритм не только не поможет вскрыть эту систему, но и облегчит генерацию ключей, так как при этом мы должны вычислять дискретные логарифмы.

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




Начало  Назад  Вперед



Книжный магазин