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


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


fi є f'iw mod m

По определению модульной конгруэнтности должен существовать вектор k, такой что для любого i

ufimki = f'i

где u – это мультипликативное обратное к w по модулю m (напомним, что мы выбирали m и w взаимно простыми, так что это обратное существует). После этого в результате деления получаем:

Поскольку m очень велико, выражение справа будет очень маленьким, поэтому покомпонентное частное k

и f близко к u/m. Подставляя вместо i 1 и вычитая из первоначального уравнения, получим:

Поскольку обе величины справа положительны и вычитаемое очень мало, мы можем записать:

Также заметим, что поскольку f'

супервозрастающая, каждый элемент должен быть меньше половины следующего, поэтому для любого i имеем:

f'i

< m Ч 2i–n

Далее мы можем записать:

После несложных преобразований получаем:

|ki

Ч f1 – k1 Ч fi| < f1 Ч 2i–n

Оказывается, что поскольку f открыт, всего лишь несколько этих неравенств (три или четыре) однозначно определяют k. Эти неравенства относятся к области целочисленного программирования, поэтому k

можно быстро найти, например, с помощью алгоритма Ленстры. А если мы знаем k, то мы можем легко раскрыть систему.

Допустим, что мы выполним перестановку f до опубликования, т.е. P не является идентичной. Поскольку нам нужны только первые 3 или 4 элемента k, мы можем просто перебрать все варианты, количество которых определяется третьей или четвертой степенью размерности k.

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

В 1986 г. Бен-Цион Хор предложил криптосистему, на сегодняшний день единственную, не использующую модульное умножение для скрытия простой задачи укладки рюкзака. Это также единственная система, основанная на задаче укладки рюкзака, которая не раскрыта.




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