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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

∑
−
=
1
0
p
i
ii
ax
g =
∑
−
=
1
0
p
i
ii
ay
g .
Это можно записать:
∏
−
=
1
0
)(
p
i
xa
ii
g =
∏
−
=
1
0
)(
p
i
ya
ii
g и
∏
−
=
+
1
0
)(
p
i
x
i
it =
∏
−
=
+
1
0
)(
p
i
y
i
it .
Теперь заметим, что произведение в обеих частях неравенства пред-
ставляет собой приведенный многочлен от t степени h. Иными словами,
если вычислить оба этих произведения и заменить значение t формальным
параметром z, тогда старшим членом на каждой стороне был бы х в степени
h с коэффициентом 1. Зная, что если подставить значение t вместо z, то
значения этих двух полиномов будут равны. Тогда вычтя один из другого,
старшие члены сократятся, и если подставить i, то получим 0. При этом
получим полином степени h – 1, корнем которого является t. Но это проти-
воречит тому, что выбранное t является алгебраическим элементом степени
h. Таким образом, доказательство закончено и построение корректно.
Хор Б.-Ц. разработал метод использования данного построения в каче-
стве основы криптосистемы. Выбирают р и h достаточно маленькими, что-
бы можно было вычислять дискретные логарифмы в GF(p
h
) (рекомендуется
p около 200, a h около 25), далее выбирают t и g. Для каждого из них будет
много вариантов, и можно просто произвести случайный выбор. (В дейст-
вительности, будет так много пар <t, g>, что очень большое количество
пользователей могут использовать одинаковые р и h, и вероятность того,
что два пользователя выберут одинаковые ключи, будет пренебрежимо
мала.). Затем, следуя конструкции Боуза–Чоула, вычисляют логарифмы по
основанию g от t + i для каждого i, что даст а. Наконец, выбирают случай-
ную перестановку а, которая и будет ключом. При этом о результатах пере-
становки а вместе с р и h извещают, а величины t, g и использованная пере-
становка остаются в секрете.
Чтобы послать сообщение А, В просто берет свое сообщение и вычис-
ляет S = х × а. В действительности, это не так уж и просто, поскольку со-
общение должно быть длиной p бит и должно быть х × 1 = h, но Хор Б.-Ц.
представил довольно прямолинейный метод преобразования неограничен-
ной битовой строки в несколько блоков, каждый из которых имеет требуе-
мую форму. А получает S. Он возводит g в степень S и выражает результат
в виде полинома от t степени h с коэффициентами из GF(p). Далее он вы-
числяет h корней этого полинома, затем применяет обратную подстановку
и получает индексы элементов в х, содержащих единицы.
Интересно отметить, что если кто-либо откроет эффективный метод
вычисления дискретных логарифмов, то такой алгоритм не только не по-
может вскрыть эту систему, но и облегчит генерацию ключей, так как при
этом необходимо вычислять дискретные логарифмы.
До настоящего времени не было опубликовано ни одного эффективно-
го метода вскрытия этой системы при знании только открытого ключа.
3.3.5. КРИПТОСИСТЕМЫ, ОСНОВАННЫЕ НА ЭЛЛИПТИЧЕСКИХ КРИ-
ВЫХ
Рассмотренная выше криптосистема Эль-Гамаля основана на том, что
проблема логарифмирования в конечном простом поле является сложной с
вычислительной точки зрения. Однако, конечные поля являются не единст-
венными алгебраическими структурами, в которых может быть поставлена
задача вычисления дискретного логарифма. В 1985 г. Коблиц и Миллер
независимо друг от друга предложили использовать для построения крип-
тосистем алгебраические структуры, определенные на множестве точек на
эллиптических кривых. Рассмотрим случаи определения эллиптических кри-
вых над простыми полями Галуа произвольной характеристики и над полями
Галуа характеристики 2.
Пусть р > 3 – простое число. Пусть a, b ∈ GF(p) такие, что
22
4270ab+≠
. Эллиптической кривой Е над полем GF(p) называется мно-
жество решений (х, у) уравнения

Страницы