Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§ 2. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ 205
Аналог ключевого обмена Диффи-Хеллмана. Предположим, что Аида и Бернардо хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего они открыто выбирают какое-либо конечное поле F9 и какую-либо эллиптическую кривую E над ним. Их ключ строится по случайной точке P на этой эллиптической кривой. Если у них есть случайная точка Р, то, например, ее х-координата дает случайный элемент F9, который можно затем преобразовать в г-разрядное целое число в р-ичной системе счисления (где q = р ), и это число может служить ключом в их классической криптосистеме. (Здесь мы пользуемся словом «случайный» в неточном смысле; мы лишь хотим сказать, что выбор из некоторого большого множества допустимых ключей произволен и непредсказуем). Они должны выбрать точку P так, чтобы все их сообщения друг другу были открытыми и все же никто, кроме них двоих, ничего бы не знал о Р.
Аида и Бернардо первым делом открыто выбирают точку В Є E в качестве «основания»; В играет ту же роль, что образующий д в системе Диффи-Хеллмана для конечных полей. Мы, однако, не требуем, чтобы В была образующим элементом в группе точек кривой Е. Эта группа может и не быть циклической. Даже если она циклическая, мы не хотим тратить время на проверку того, что В — образующий элемент (или даже на нахождение общего числа N точек, которое нам не понадобится в последующем). Нам хотелось бы, чтобы порожденная В подгруппа была большой, предпочтительно того же порядка величины, что и сама Е. Позже мы обсудим этот вопрос. Пока что предположим, что В — взятая открыто точка на E весьма большого порядка (равного либо N, либо большому делителю N).
Чтобы образовать ключ, Аида вначале случайным образом выбирает целое число а, сравнимое по порядку величины с q (которое близко к N); это число она держит в секрете. Она вычисляет аВ Є E и передает эту точку открыто. Бернардо делает то же самое: он выбирает случайно b и открыто передает ЬВ Є Е. Тогда используемый ими секретный ключ — это P =¦ аЬВ Є Е. Оба пользователя могут вычислить этот ключ. Например, Аида знает ЬВ (точка была передана открыто) и свое собственное секретное а. Однако любая третья сторона знает лишь аВ и ЬВ. Кроме решения задачи дискретного логарифмирования — нахождения а по В и аВ (или нахождения Ь по В и ЬВ), — по-видимому, нет способа найти аЬВ, зная лишь аВ и ЬВ.
Аналог системы Мэсси—Омуры. Как и в случае конечного поля, это — криптосистема с открытым ключом для передачи элементов сообщения т, которые мы теперь предположим представлен-
206
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
ными точками P7n фиксированной (и не скрываемой) эллиптической кривой E над F9 (q берется большим). Предполагается также, что общее число N точек на E вычислено и не составляет секрета. Каждый пользователь системы секретно выбирает такое целое случайное число е между IhN, что НОД (е, N) = 1. Используя алгоритм Евклида, он находит затем обратное c1k числу е по модулю N, т.е. такое целое число d, что de = 1 (mod N). Если Алиса хочет послать Бобу сообщение P7n, то она сначала посылает ему точку еАРт (индекс А указывает на пользователя Алису). Это ничего не говорит Бобу, который, не зная ни еА, ни dA, не может восстановить Рт. Однако, не придавая этому значения, он умножает ее на свое ев и посылает обратно Алисе евеАРт. На третьем шаге Алиса должна частично раскрыть свое сообщение, умножив евеАРт на dA. Так как NP7n = О и d-AeA = 1 (mod N), при этом получается точка евРт, которую Алиса возвращает Бобу. Тот может теперь прочитать сообщение, умножив точку евРт на dB.
Заметим, что злоумышленник может знать еАРт, евеАРт и евРт. Если бы он умел решать задачу дискретного логарифмирования на Е, то он мог бы определить ев по первым двум точкам, вычислить dB = е~в (mod А) и Рт = dBeBPm.
Аналог системы Эль-Гамаля. Это — другая криптосистема с открытым ключом для передачи сообщений Рт. Как и в описанной выше системе ключевого обмена, мы исходим из данных несекретных: а) конечного поля F9, б) определенной над шгм-зллиптической кривой E и в) точки-«основания» В на ней. (Знать общее число N точек на E нам не нужно.) Каждый из пользователей выбирает случайное целое число а, которое держит в секрете, затем находит и делает общедоступной точку аВ.
Чтобы послать Бьорну сообщение Рт, Анюта выбирает случайно целое число к и посылает пару точек (кВ,Рт + к(авВ)) (где авВ — открытый ключ Бьорна). Чтобы прочитать сообщение, Бьорн умножает первую точку из полученной пары на свое секретное число ав и вычитает результат умножения из второй точки:
Pm + k(aBB)-aB(kB) = P7n.
Таким образом, Анюта посылает замаскированное P7n вместе с «подсказкой» kB, при помощи которой можно снять «маску» кавВ, если знать секретное число ав. Злоумышленник, который умеет решать задачу дискретного логарифмирования на Е, может, конечно, найти ав, зная авВ и В.
§ 2. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ
207
Выбор кривой и точки. Существуют различные способы выбора эллиптической кривой и (в системах Диффи-Хеллмана и Эль-Гамаля) точки В на ней.
