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

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

Во-первых, отметим, что любая супервозрастаюш,ая последовательность должна расти экспоненциально, поскольку минимальная супервозрастаюш,ая последовательность - это степени двойки. Во-вторых, отметим, что причина, по которой используются супервозрастаюш,ие последовательности заключается в том, что любая /г-элементная сумма из нее уникальна. Другими словами, если мы представим нашу последовательность в виде вектора f, функция скалярного произведения f на битовый вектор X будет однозначна и поэтому может быть обраш,ена Но оказывается возможным построить последовательность, расту-ш,ую только полиномиально, но сохраняюш,ую свойство единственности /г-элементных сумм. Конструкция такой последовательности была опубликована в 1962 г.

Пусть GF{p) - поле целых чисел по модулю простого числа р, и GFip) - расширение степени h основного поля. Также пусть 1 - вектор, все элементы которого равны 1.

С формальной точки зрения мы строим последовательность длины р, такую что для любого / от О до р - 1

1 < а, < / - 1

и для каждых различных х, у, таких что х*1 = у*1 = h, х*а и у*а также должны быть различны. Мы можем представлять векторы X и у как битовые (т.е. содержаш,ие только О и 1).

Далее построение проводится довольно просто. Во-первых, выберем t - алгебраический элемент степени h над GF{p), т.е. минимальный многочлен с коэффициентами из GF(p), корнем которого является t, имеет степень h. Далее выберем g - мультипликативный генератор (примитивный элемент) поля GF{p), т.е. для каждого элемента х из GF(p) (кроме нуля) суш,ествует некоторое /, такое, что g в степени / будет равно х.

Теперь рассмотрим аддитивный сдвиг GF(p), т.е. множество

t + GF(p) {t + i\0<i<p-\ jcGFip")

Пусть каждый элемент вектора а будет логарифмом по основанию g соответствуюш,его элемента из t+GFip):

Qi = loggit+i)

Мы должны проверить, что а, определенная подобным образом, удовлетворяет заданным свойствам. Определенно, каждый элемент в а будет лежать в заданном диапазоне, поскольку g порождает GF(p,h). Теперь пусть у нас есть различные х и у, такие что х*1 = у*1 = /г, но х*а = у*а. Тогда, возводя g в степень х*а и у*а, получим:

р-1 р-1

L Xtat L У tat gi=0 =gi=0

Поэтому мы также можем записать И далее

Теперь заметим, что произведение в обеих частях неравенства представляет собой приведенный многочлен от t степени h. Иными словами, если бы мы вычислили оба этих произведения и заменили значение t формальным параметром, например, z, тогда старшим членом на каждой стороне был бы х в степени h с коэффициентом 1. Мы знаем, что если мы подставим значение t вместо Z, то значения этих двух полиномов будут равны. Поэтому вычтем один из другого, старшие члены сократятся, и если мы подставим t, то получим 0. Мы получили полином степени /г-1, корнем которого является t. Но это противоречит тому, что мы выбрали t алгебраическим элементом степени h. Таким образом, доказательство закончено и построение корректно.

Хор разработал метод использования данного построения в качестве основы криптосистемы. Кратко он заключается в сле-дуюш,ем. Мы выбираемрик достаточно маленькими, чтобы мы могли вычислять дискретные логарифмы в GF(p). Хор рекомендует р около 200, а h около 25. Затем мы выбираем tng как

указано выше. Для каждого из них будет много вариантов, и мы можем просто произвести случайный выбор (В действительности, будет так много пар <t,g>, что очень большое количество пользователей могут использовать одинаковые р и h, и вероятность того, что два пользователя выберут одинаковые ключи, будет пренебрежимо мала.). Затем мы следуем конструкции Бо-уза-Чоула. Мы вычисляем логарифмы по основанию g от t+i для каждого /, это даст нам а. Наконец, мы выбираем случайную перестановку а, которая и будет нашим ключом. Мы публикуем результат перестановки а вместе с р и h. Величины t, g и использованная перестановка остаются в секрете.

Чтобы послать сообш,ение А, В просто берет свое сообш,ение и вычисляет S = х*а. В действительности, это не так уж и просто, поскольку сообш,ение должно быть длиной р бит и должно быть х*1 = /г, но Хор представил довольно прямолинейный метод преобразования неограниченной битовой строки в несколько блоков, каждый из которых имеет требуемую форму. А получает S. Он возводит g в степень S и выражает результат в виде полинома от t степени h с коэффициентами из GF(p). Далее он вычисляет h корней этого полинома, затем применяет обратную подстановку и получает индексы элементов в х, содержаш,их единицы.

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

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

3.3.5. Криптосистемы, осповаппые па эллиптических кривых

Рассмотренная выше криптосистема Эль-Гамаля основана на том, что проблема логарифмирования в конечном простом поле является сложной с вычислительной точки зрения. Однако, конечные поля являются не единственными алгебраическими структурами, в которых может быть поставлена задача вычисления дискретного логарифма. В 1985 году Коблиц и Миллер

независимо друг от друга предложили использовать для построения криптосистем алгебраические структуры, определенные на множестве точек на эллиптических кривых. Мы рассмотрим случаи определения эллиптических кривых над простыми полями Галуа произвольной характеристики и над полями Галуа характеристики 2.

Определение 3.2. Пусть р> Ъ - простое число. Пусть а, b & GF{p) такие, что 4а + 21Ь Ф 0. Эллиптической кривой Е над полем GF(p) называется множество решений (х, у) уравнения

ух + ах + Ь (3.1)

над полем GF(p) вместе с дополнительной точкой оо, называемой точкой в бесконечности или нулевой точкой О (поскольку эта точка выполняет роль нейтрального элемента в группе точек).

Представление эллиптической кривой в виде уравнения (3.1) носит название эллиптической кривой в форме Вейерштрасса.

Обозначим количество точек на эллиптической кривой Е через #Е. Теорема Хассе гласит, что #Е = р + \ - t, где

#Е называется порядком кривой E,at- следом кривой Е.

Зададим бинарную операцию на Е (в аддитивной записи) следуюш,ими правилами:

(i) оо + оо = оо;

(И) V{x,y)G Е,{х,у) + -{х,у);

(Ш) V (Х, у) g Е, (Х, у) + {Х, -у) = оо;

(iv) V (xi, yi) g E, (X2, ут) e Е,Х1Ф Xj, (xi, ух) + (хг, уг) = (хз,уз), где

Хз = Х-Х1-Х2, Уз = X{Xi - Хз) - уи

Х2 - Xl

(v) V (xi. Ух) е Е,ухФ О, (xi, ух) + (xi, ух) = (хз, уз), где

Хз = Х - 2хх, уз = Х{хх-Хз)-ухИ

3xi +а

Множество точек эллиптической кривой Е с заданной таким образом операцией образует абелеву группу.

Если #Е=р + 1, то криваяЕназывается суперсингулярной.

Эллиптическая не являющаяся суперсингулярной кривая Е над полем GF{2") характеристики 2 задается следующим образом.

Определение 3.3. Пусть т> Ъ - целое число. Пусть а, b s GF{2"), bO. Эллиптической кривой Е над полем GF{2") называется множество решений (х, у) уравнения

у+хух + ах + Ь (3.2)

над полем GF{2") вместе с дополнительной точкой оо, называемой точкой в бесконечности.

Количество точек на кривой Е также определяется теоремой Хассе:

q + l-2 <#E<q + l + 2,

где q = 2". Более того, #Е четно.

Операция сложения на .£ в этом случае задается следующими правилами:

(i) оо + оо = оо;

(и) y{x,y)GE,{x,y) + -{x,yy,

(iii) V (х, у) g Е, (х, у) + (х, X + у) °°;

(iv) V (Xi, yi) g E, {X2, yi) G Е,Х1Ф X2, (Xi, yi) + (X2, yi) =

(хз,уз),где

Хз = + X + Xl + X2 + a,

Уз = Х{Х1+Хз)+Хз+УиИ

XI+X2

(v) V (xi, yi) G E,xi 0, (xi, yi) + (xi, yi) = (хз. Уз), где

Уз =jci +(; + 1)д:з И

Х = :

в этом случае множество точек эллиптической кривой Е с заданной таким образом операцией также образует абелеву группу.

Группа точек на кривой имеет простую структуру, а именно она является абелевой группой ранга 1 или 2, т.е. изоморфна прямому произведению двух циклических групп х , где

«1 и «2 - целые числа, «2 делит щ и пг делит - 1, где - порядок поля коэффициентов, при этом щ может быть равно 1. Индекс подгруппы в группе точек называют кофактором эллиптической кривой.

Пользуясь операцией сложения точек на кривой, можно естественным образом определить операцию умножения точки Р g .£ на произвольное целое число п:

пР = Р + Р+ ...+Р,

где операция сложения выполняется п раз.

Теперь построим одностороннюю функцию, на основе которой можно будет создать криптографическую систему.

Пусть Е - эллиптическая кривая, Р s Е - точка на этой кривой. Выберем целое число п < #Е. Тогда в качестве прямой функции выберем произведение пР. Для его вычисления по оптимальному алгоритму потребуется не более 2-log2« операций сложения. Обратную задачу сформулируем следующим образом: по заданным эллиптической кривой Е, точке Р g Е и произведению пР найти п. В настоящее время все известные алгоритмы решения этой задачи требуют экспоненциального времени.

Теперь мы можем описать криптографический протокол, аналогичный известному протоколу Диффи-Хеллмана. Для установления защищенной связи два пользователя А и В совместно выбирают эллиптическую кривую Е и точку Р на ней. Затем каждый из пользователей выбирает свое секретное целое число, соответственно а и Ь. Пользователь А вычисляет произведение аР, а пользователь В - ЬР. Далее они обмениваются вычислен-