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


Криптосистемы Меркля-Хеллмана и Хора-Ривеста - часть 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 г. Бен-Цион Хор предложил криптосистему, на сегодняшний день единственную, не использующую модульное умножение для скрытия простой задачи укладки рюкзака. Это также единственная система, основанная на задаче укладки рюкзака, которая не раскрыта.




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



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