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


Криптосистемы Меркля-Хеллмана и Хора-Ривеста - часть 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, содержащих единицы.

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

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




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