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


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


4.        Теперь вычисляется f'' умножением каждого компонента f'

на w по модулю m;

f'' = f'w

(mod m)

5.        И наконец, проводится случайная перестановка P элементов f''

для получения открытого ключа f.

Теперь А раскрывает ключ f и держит в секрете f', m, w и P.

Когда пользователь B хочет послать А сообщение (битовый вектор) x, он вычисляет S = fx и посылает это вычисленное S. Если данная система является стойкой, тогда для внешнего наблюдателя С вычисление x по S и публичному ключу f будет эквивалентно решению задачи рюкзака в общем случае. Допустим, что предположение о стойкости верно. В этом случае, хотя С не может расшифровать сообщение, А может это сделать, применяя секретные значения, которые она использовала при вычислении f.

Пользователь А может вычислить S’=f'x, так что она сможет решить задачу рюкзака в случае супервозрастающей последовательности. Вычисление S’ производится следующим образом.

Таким образом, A просто умножает S на мультипликативное обратное w по модулю m, а затем решает задачу рюкзака в случае супервозрастающей последовательности f, и теперь она сможет прочитать сообщение.

При получении ключа мы начинаем с супервозрастающей последовательности и затем скрываем имеющуюся в ней структуру. Другими словами, построенная последовательность выглядит так, что в ней нет никакой структуры. Но система может быть сделана еще более стойкой (или, по крайней мере, так будет казаться) путем повторения этого процесса скрытия структуры. Если мы выберем другие m и w, тогда мы сможем построить новый открытый ключ, который не может быть построен с использованием единственной пары (m,

w). Мы можем повторять это снова и снова, и система выглядит все более и более стойкой с каждой итерацией.

В 1982 г Эди Шамир открыл атаку на криптосистему, использующую одну итерацию. Это оказалось началом падения систем, основанных на задаче рюкзака.

Допустим, что перестановка не применяется, так что f'' = f. Тогда для любого i




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



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