Криптографическая защита информации. Яковлев А.В - 58 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

он вычисляет S = fx и посылает это вычисленное S. Если данная система
является стойкой, тогда для внешнего наблюдателя С вычисление х по S и
публичному ключу f будет эквивалентно решению задачи рюкзака в общем
случае. Допустим, что предположение о стойкости верно. В этом случае,
хотя С не может расшифровать сообщение, А может это сделать, применяя
секретные значения, которые он использовал при вычислении f.
Пользователь А может вычислить S'= f’x, так что она сможет решить
задачу рюкзака в случае супервозрастающей последовательности. Вычис-
ление S' производится следующим образом:
=
′
=
′
=
′
=
′
∑
∑
−
mxfwwmxfxfS
i
i
ii
i
i
modmod
1
.modmod
11
mSwmxwfw
i
i
i
−−
=
∑
Таким образом, А просто умножает S на мультипликативное обратное
w по модулю т, а затем решает задачу рюкзака в случае супервозрастаю-
щей последовательности f ′, и теперь сможет прочитать сообщение.
В 1982 г. Э. Шамир открыл атаку на криптосистему, использующую
одну итерацию, что привело к отказу от систем, основанных на "задаче
рюкзака".
В 1986 г. Бен-Цион Хор предложил криптосистему, на сегодняшний
день единственную, не использующую модульное умножение для скрытия
простой задачи укладки рюкзака. Это также единственная си-стема, осно-
ванная на задаче укладки рюкзака, которая не раскрыта.
Во-первых, что любая супервозрастающая последовательность должна
расти экспоненциально, поскольку минимальная супервозра-стающая по-
следовательность – это степени двойки. Во-вторых, отметим, что причина,
по которой используются супервозрастающие последовательности, заклю-
чается в том, что любая h-элементная сумма из нее уникальна. Другими
словами, если представить последовательность в виде вектора f, функция
скалярного произведения f на битовый вектор х будет однозначна и поэто-
му может быть обращена. Но оказывается возможным построить последо-
вательность, растущую только полиномиально, но сохраняющую свойство
единственности h-элементных сумм. Конструкция такой последовательно-
сти была опубликована в 1962 г.
Пусть GF(p) – поле целых чисел по модулю простого числа р, и GF(p
h
)
– расширение степени h основного поля. Также пусть 1 – вектор, все эле-
менты которого равны единице.
Построим последовательность длины р такую, что для любого i от 0 до
р – 1
1 ≤ а
i
≤ p
h
– 1,
и для каждых различных х, у, таких, что х × 1 = у × 1 = h, x × a и у × а также
должны быть различны. Можно представить векторы х и у как битовые.
Далее построение проводится довольно просто. Во-первых, выберем t
– алгебраический элемент степени h над GF(p), т.е. минимальный много-
член с коэффициентами из GF(p), корнем которого является t, имеет сте-
пень h. Далее выберем g – мультипликативный генератор (примитивный
элемент) поля GF(p
h
), т.е. для каждого элемента х из GF(p
h
) (кроме нуля)
существует некоторое i, такое, что g в степени i будет равно х.
Теперь рассмотрим аддитивный сдвиг GF(p), т.е. множество
.)(}10{)(
h
pGFpiitpGFt ⊂−≤≤+=+
Пусть каждый элемент вектора а будет логарифмом по основанию g
соответствующего элемента из t + GF(p):
.)1(log
+
=
tа
gi
При этом каждый элемент а будет лежать в заданном диапазоне, по-
скольку g порождает GF(p, h). Теперь пусть есть различные х и у, такие что
х × 1 = у × 1 = h, но х × а = у × а. Тогда, возводя g в степень х × а и у × а,
получим:

Страницы