Методы и средства криптографической защиты информации

Определение.

Пусть Е -- эллиптическая кривая над вещественными числами, и пусть Р и Q - две точки на Е. Определим точки -Р и P+Q по следующим правилам.

1.Точка О - тождественный элемент по сложению ("нулевой элемент") группы точек. В следующих пунктах предполагается, что ни Р, ни Q не являются точками в бесконечности.

2. Точки Р= (х, у) и -Р имеют одинаковые х - координаты, а их у - координаты различаются только знаком, т.е. -(х. у) = (х.- у). Из (1) сразу следует, что (х, -у) -- также точка на Е.

3. Если Р и Q имеют различные x - координаты, то прямая имеет с Е еще в точности одну точку пересечения R (за исключением двух случаев: когда она оказывается касательной в Р, и мы тогда полагаем R = Р, или касательной в Q. и мы тогда полагаем R = Q). Определяем теперь Р + Q как точку -R, т.е. как отражение от оси х третьей точки пересечения. Геометрическое построение, дающее Р + Q, приводится ниже в примере 1.

4. Если Q = -Р (т. е. х - координата Q та же, что и y P, а у - координата отличается лишь знаком), то полагаем P + Q = О (точке в бесконечности; это является следствием правила 1).

5. Остается возможность Р = Q. Тогда считаем, что l -- касательная к кривой в точке Р. Пусть R -- единственная другая точка пересечения l с Е. Полагаем P + Q = -R (в качестве R берем Р, если касательная прямая в Р имеет "двойное касание", т. е. если Р есть точка перегиба кривой).

Пример 1. На (рис.1) , изображены эллиптическая кривая в плоскости ху и типичный случай сложения точек Р и Q. Чтобы найти Р + О. проводим прямую и в качестве Р+Q берем точку, симметричную относительно оси x третьей точке, определяемой пересечением прямой PQ и кривой. Если бы Р совпадала с Q, т.е. если бы нам нужно было найти 2Р, мы использовали бы касательную к кривой в Р: тогда точка 2Р симметрична третьей точке, в которой эта касательная пересекает кривую.

рис.1

Теперь мы покажем, почему существует в точности еще одна точка, где прямаяд l, проходящая через Р и Q, пересекает кривую; заодно мы выведем формулу для координат этой третьей точки и тем самым -- для координат Р+Q.

Пусть (), () и () обозначают координаты соответственно P, Q и P+Q. Мы хотим выразить через ,.

Предположим, что мы находимся в ситуации п.3 определения P-Q, и пусть есть уравнение прямой, проходящей через Р и Q в этой ситуации она не вертикальна). Тогда и . Точка на l, т. е. точка (), лежит на эллиптической кривой тогда и только тогда, когда. Таким образом, каждому корню кубического многочлена ответствует точка пересечения. Мы уже знаем, что имеется два корня и . так как (),() -- точки Р, Q на кривой. Так как сумма корней нормированного многочлена равна взятому с обратным знаком коэффициенту при второй по старшинству степени многочлена, то в нашем случае третий корень -- это. Тем самым получаем выражение для , и, следовательно, Р+Q = или, в терминах ,,

(4)

Ситуация в п.5 аналогична, только теперь a -- производная dy/ dx в Р. Дифференцирование неявной функции, заданной уравнением (1), приводит к формуле , и мы получаем следующие формулы для координат удвоенной точки :

, (5)

.

Пример 2. На эллиптической кривой пусть Р = (-3,9) и Q = (-2,8). Найти Р + О и 2Р.

Решение. Подстановка ,в первое из уравнений (4) дает ; тогда второе из уравнений (4) дает. Далее, подставляя в первое из уравнений (5). получаем для х - координаты точки 2Р значение 25 / 4, а второе из уравнений (5) дает для у - координаты значение -35/ 8.

Существует несколько способов доказать, что принятое выше определение операции сложения Р + Q превращает множество точек на эллиптической кривой в абелеву группу. Можно использовать результаты из проективной геометрии, из комплексного анализа двоякопериодических функций или алгебраическое доказательство, использующее теорию дивизоров на кривых. Доказательства каждого из этих типов можно найти в источниках, указанных в списке литературы.

Если n -- целое число, то, как и в любой абелевой группе, nР обозначает сумму n точек Р при n > 0 и сумму |n| точек -Р, если.

Еще несколько слов о "точке в бесконечности" О. По определению, это -- тождественный элемент группового закона. На рисунке (см. выше) следует себе представлять ее расположенной на оси у в предельном направлении, определяемом все более "крутыми" касательными к кривой. Она является "третьей точкой пересечения" с кривой для любой вертикальной прямой: такая прямая пересекается с кривой в точках вида (), () и О. Мы изложим сейчас более естественный способ введения точки О.

Под проективной плоскостью мы понимаем множество классов эквивалентности троек (X,Y, Z) (не все компоненты равны нулю), при этом две тройки называются эквивалентными, если одна из них -- скалярное кратное другой, т.е. (X, Y, Z) ~ (X,Y,Z). Такой класс эквивалентности называется проективной точкой. Если проективная точка имеет ненулевую компоненту Z, то существует, причем только одна, тройка в ее классе эквивалентности, имеющая вид (х, у,1): просто полагаем х = X/Z, у = Y/Z. Тем самым проективную плоскость можно представить как объединение всех точек (х, у) обычной ("аффинной") плоскости с точками, для которых Z =0. Эти последние точки составляют то, что называется бесконечно удаленной прямой; наглядно ее можно, себе представить на плоскости как "горизонт". Любому алгебраическому уравнению F(x,y) = 0 кривой в аффинной плоскости отвечает уравнение (X,Y, Z) = 0, которому удовлетворяют соответствующие проективные точки: нужно заменить х на X/ Z, у -- на Y/ Z и умножить на подходящую степень Z, чтобы освободиться от знаменателей. Например, если применить эту процедуру к аффинному уравнению (1) эллиптической кривой, то получится "проективное уравнение" . Этому уравнению удовлетворяют все проективные точки (X, Y, Z) с Z0, для которых соответствующие аффинные точки (х, у), где х = X/ Z, y = Y/ Z, удовлетворяют (1). Помимо них, какие еще точки бесконечно удаленной прямой удовлетворяют последнему уравнению? Если положить в уравнении Z = 0, то уравнение примет вид = 0, т.е. X = 0. Но единственный класс эквивалентности троек с X =0, Z =0 -- это класс тройки (0, 1, 0). Это и есть точка, которую мы обозначили О; она лежит на пересечении оси у с бесконечно удаленной прямой.

. При рассмотрении эллиптических кривых с точки зрения теории алгебраических чисел обнаруживается глубокая аналогия между координатами "точек, делящих эллиптические кривые на n частей" (т.е. таких точек Р, что nР = О) и точками, делящими на n частей единичную окружность (которые соответствуют корням степени n из единицы в комплексной плоскости). Более подробные сведения об этом можно найти в[ ] .Точки конечного порядка.

Порядком n точки Р на эллиптической кривой называется такое наименьшее натуральное число, что nP = 0; разумеется, такого конечного n может и не существовать,в этом случае мы будем говорить о точке бесконечного порядка. Часто требуется найти точки конечного порядка на эллиптической кривой, в особенности, на эллиптических кривых, определенных над полем Q.

Пример 3. Найти порядок точки Р = (2, 3) на .

Решение. Применяя (5), находим, что 2Р = (0, 1), и вновь с помощью (5). что 4Р = 2(2Р) = (0,-1). Поэтому 4Р = -2P и, следовательно, 6P = О. Тем самым порядок Р может быть равен 2, 3 или 6. Но 2Р = (0,1) О, а если бы Р имела порядок 3, то было бы 4Р = Р, что неверно. Итак, Р имеет порядок 6.

Эллиптические кривые над рациональными числами.

Еели в уравнении (1) а и b -- рациональные числа, то естественно рассматривать рациональные решения (х, у), т.е. эллиптическую кривую над полем Q рациональных чисел. Теория эллиптических кривых над рациональными числами очень обширна. Было доказано, что соответствующие абелевы группы являются конечно 'порожденными (теорема Морделла). Это означает, что каждая из таких групп есть сумма конечной "подгруппы кручения" (точек конечного порядка) и подгруппы, порожденной конечным числом точек бесконечного порядка. Число (минимальное) образующих бесконечной части называется рангом r; оно равно нулю тогда и только тогда, когда вся группа конечна. Изучение ранга r и других свойств группы точек эллиптической кривой над Q связано со многими интересными вопросами теории чисел и алгебраической геометрии. Например, известный с древних времен вопрос "Существует ли прямоугольный треугольник с рациональными сторонами, площадь которого равна данному целому n?" эквивалентен следующему: "Верно ли, что ранг эллиптической кривой больше нуля?" Случай n = 6 и прямоугольного треугольника со сторонами 3, 4 и 5 соответствует точке Р = (-3,9) из примера 2, которая является точкой бесконечного порядка на эллиптической кривой . Более подробно см.[ ].

Эллиптические кривые над конечным полем.

Будем предполагать, что К -- конечное поле , с элементами. Пусть Е -- эллиптическая кривая, определенная над . Если р = 2 или 3, то Е задается уравнением вида (2) или (3) соответственно.

Легко усмотреть, что эллиптическая кривая может иметь не более 2q+1 различных -точек, т. е. точку в бесконечности и не более чем 2q пар (х, у), х.у , удовлетворяющих (1) (или (2) или (3), если р = 2 или 3). А именно, для каждого из q возможных значений х имеется не более двух значений у, удовлетворяющих (1).

Но так как лишь у половины элементов имеются квадратные корни, естественно ожидать (если бы были случайными элементами поля), что количество -точек примерно вдвое меньше этого числа. Точнее, пусть -- квадратичный характер. Это -- отображение, переводящее x в 1 или -1 в зависимости от того, является или нет элемент х квадратом элемента из (полагаем также (0) = 0). Например, если q -- это простое число р, то {х) = есть символ Лежандра . В любом случае число решений y, уравнения = и равно 1 + (и) и, значит, число решений (1) (с учетом точки в бесконечности) равно

(6)

Следует ожидать, что одинаково часто принимает значения + 1 и -- 1. Вычисление суммы очень похоже на "случайное блуждание", когда мы подбрасываем монету q раз. продвигаясь на шаг вперед, если выдал герб, и назад -- если решетка. Из теории вероятностей известно, что после q бросаний результат случайного блуждания оказывается на расстоянии порядка от исходного положения. Сумма ведет себя в чем-то аналогично случайному блужданию. Тсчнее, удалось доказать, что она ограничена величиной . Этот результат -- теорема Хассе

Теорема Хассе.

Пусть N -- число -точек на эллиптической кривой, определенной над . Тогда

В дополнение к числу N элементов на эллиптической кривой над Fg нам бывает нужно знать строение этой абелевой группы. Она -- не обязательно циклическая, но можно показать, что она-- всегда произведение двух циклических групп

2.8.2 Построение криптосистем на эллиптических кривых

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

Кратные точки. Для эллиптических кривых аналогом умножения двух элементов группы служит сложение двух точек эллиптической кривой Е, определенной над . Таким образом, аналог возведения в степень к элемента из -- это умножение точки Р Е на целое число k. Возведение в k-ю степень в методом повторного возведения в квадрат можно осуществить за O () двоичных операций (см. предложение II. 1.9). Аналогично, мы покажем, что кратное kР Е можно найти за O() двоичных операций методом повторного удвоения.

Пример 1. Чтобы найти 100Р, записываем 100Р = 2(2(Р + 2(2(2(Р + 2Р))))) и приходим к цели, производя 6 удвоений и 2 сложения точек на кривой.

Предложение 2.1. Пусть эллиптическая кривая Е определена уравнением Вейерштрасса (уравнением (1),(2) или (3) из предыдущего параграфа) над конечным полем. Если задана точка Р на Е, то координаты kР можно вычислить за О () двоичных операций.

Замечание 1. Оценки времени работы в предложении 2.1 не являются наилучшими, особенно для конечных полей характеристики р = 2. Нам, однако, достаточно этих оценок, которые следуют из наиболее очевидных алгоритмов арифметики в конечных полях.

Замечание 2. Если известно число N точек на нашей эллиптической кривой Е и если k > N, то в силу равенства NP = О мы можем заменить к его наименьшим неотрицательным вычетом по модулю N; в этом случае временная оценка заменяется на O() (напомним, что ). Рене Шуф (R. Schoof) предложил алгоритм, вычисляющий N за O() двоичных операций.

Представление открытого текста. Мы намереваемся кодировать наши открытые тексты точками некоторой заданной эллиптической кривой Е, определенной над конечным полем Мы хотим ото осуществить простым и систематическим способом так чтобы открытый текст m (который можно рассматривать как целое число из некоторого интервала) можно было легко прочитать, зная координаты соответствующей точки . Заметим, что это "кодирование" - не то же самое, что засекречивание. Позднее мы будем рассматривать способы шифрования точек открытого текста. Однако законный пользователь системы должен быть в состоянии восстановить т после дешифрования точки шифртекста.

Следует сделать два замечания. Во-первых, не известно детерминистического полиномиального (по log q) алгоритма для выписывания большого числа точек произвольной эллиптической кривой E над . Однако, как мы увидим далее, существуют вероятностные алгоритмы с малой вероятностью неудачи. Во-вторых, порождать случайные точки на Е недостаточно: чтобы закодировать большое число возможных сообщений т, необходим какой-то систематический способ порождения точек, которые были бы связаны с т определенным образом например, чтобы x-координата имела с т простую связь.

Приведем один возможный вероятностный метод представления открытых текстов как точек на эллиптической кривой Е, определенной над, где предполагается большим (и нечетным (см ниже упражнение 8 при)). Пусть - достаточно большое целое число, настолько, что можно считать допустимым, если попытка представить в нужном нам виде элемент ("слово") открытого текста m оказывается неудачной в одном случае из ; практически достаточно = 30 или, на худой конец, = 50. Пусть элементы нашего сообщения m - целые числа, . Предположим также, что выбранное нами конечное толе имеет q элементов, q > М. Записываем петые числа от 1 до М в виде , где устанавливаем взаимно однозначное соответствие между такими числами и некоторым множеством элементов из . Например, можно записать такое число как r -значное числе в р-ичной системе счисления и, отождествляя цифры в этой записи с элементами , рассматривать их как коэффициенты многочлена степени не выше r - 1 над . соответствующего элементу поля . Таким образом, числу () ставится в соответствие многочлен который, будучи рассмотрен по модулю некоторого фиксированного неприводимого многочлена степени r над , дает элемент.

Итак, при данном m при каждом j = 1,2,... , мы получаем элемент х из, соответствующий. Для такого х вычисляем правую часть уравнения

и пытаемся найти квадратный корень из f(x), используя метод, изложенный в конце § II. 2. Хотя этот алгоритм был приведен для простого поля , он дословно переносится на любое конечное поле. Чтобы воспользоваться им, нужно иметь элемент g в этом поле, не являющийся квадратом; его можно легко найти с помощью вероятностного алгоритма.) Если мы находим такой у, что . то берем . Если f(x) не оказывается квадратом, то увеличиваем j на 1 и повторяем попытку с соответствующим значением х. Если мы находим х, для которого j(x) -- квадрат, прежде, чем j превысит , то мы можем восстановить т по известной тетке (х, у) с помощью формулы , где -- целое число, соответствующее х при установленном взаимно однозначном соответствии между целыми числами и элементами. Так как f(x) -- квадрат приблизительно в 50% случаев, то вероятность того, что метод не приведет результату и мы не найдем точки с x-координатой, соответствующей целому числу между и , равна примерно . (Точнее, вероятность того, что f(x) есть квадрат, фактически равна N/(2q), однако N/(2q) очень близко к 1/2.)

Дискретный логарифм на Е.

Определение. Пусть Е -- эллиптическая кривая над , и В -- точка на Е. Задачей дискретного логарифмирования на Е (с основанием В) называется задача нахождения для данной точки Р Е такого целого числа х Z (если оно существует), что хВ = Р.

Вполне возможно, что задача дискретного логарифмирования на эллиптической кривой окажется более трудной для решения, чем задача дискретного логарифмирования в конечных полях. Наиболее сильные методы, разработанные для конечных полей, по-видимому, не работают в случае эллиптических кривых. Это обстоятельство поособенному отчетливо проявляется в случае полей характеристики 2. Как объясняется в обзорной статье Одлыжко, упомянутой в списке литературы, специальные методы решения задачи дискретного логарифмирования в позволяют сравнительно легко вычислять дискретные логарифмы и, следовательно, вскрывать соответствующие криптосистемы, если r не выбрано очень большим. Аналогичные системы, использующие эллиптические кривые над (см. ниже), судя но всему, являются надежными при значительно меньших значениях r. Так как имеются практические причины (связанные с устройством ЭВМ и программированием) предпочтительности арифметических операций над полям, криптосистемы с открытым ключом, рассматриваемые ниже, могут оказаться более удобными для практического применения, чем системы, основанные на задаче дискретного логарифмирования в

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

Теперь мы опишем аналоги систем с открытым ключом из § IV. 3, основанные на задаче дискретного логарифмирования на эллиптической кривой, определенной над конечным полем .

Аналог ключевого обмена Диффи-Хеллмана. Предположим, что абоненты А и Б хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего они открыто выбирают какое-либо конечное поле и какую-либо эллиптическую кривую Е над ним. Их ключ строится по случайной точке Р на этой эллиптической кривой. Если у них есть случайная точка Р, то, например, ее x-координата дает случайный элемент который можно затем преобразовать в x-разрядное целое число в р-ичной системе счисления (где ), и это число может служить ключом в их классической криптосистеме. (Здесь мы пользуемся словом "случайный" в неточном смысле; мы лишь хотим сказать, что выбор из некоторого большого множества допустимых ключей произволен и непредсказуем). Они должны выбрать точку Р так, чтобы все их сообщения друг другу были открытыми и все же никто, кроме них двоих, ничего бы не знал о Р.

Абоненты (пользователи)А и Б первым делом открыто выбирают точку В Е в качестве "основания"; В играет ту же роль, что образующий q в системе Диффи-Хеллмана для конечных полей. Мы, однако, не требуем, чтобы В была образующим элементом в группе точек кривой Е. Эта группа может и не быть циклической. Даже если она циклическая, мы не хотим тратить время на проверку того, что В -- образующий элемент (или даже на нахождение общего числа N точек, которое нам не понадобится в последующем). Нам хотелось бы, чтобы порожденная В подгруппа была большой, предпочтительно того же порядка величины, что и сама Е. Позже мы обсудим этот вопрос. Пока что предположим, что В -- взятая открыто точка на Е весьма большого порядка (равного либо N, либо большому делителю N).

Чтобы образовать ключ, А вначале случайным образом выбирает целое число а, сравнимое по порядку величины с q (которое близко к N); это число он держит в секрете. Он вычисляет аВ Е и передает эту точку открыто.Абонент Б делает то же самое: он выбирает случайно b и открыто передает bВ Е. Тогда используемый ими секретный ключ - это Р = abВ Е. Оба пользователя могут вычислить этот ключ. Например, А знает bB (точка была передана открыто) и свое собственное секретное а. Однако любая третья сторона знает лишь аВ и bВ. Кроме решения задачи дискретного логарифмирования - нахождения а по В и аВ (или нахождения b по B и bB по-видимому, нет способа найти аbВ. зная лишь аВ и bВ.

Аналог системы Мэсси-Омуры. Как и в случае конечного толя, это -- криптосистема с открытым ключом для передачи элементов сообщения т, которые мы теперь предположим представленными точками фиксированной (и не скрываемой) эллиптической кривой Е над (q берется большим). Предполагается также, что обшее число N точек на Е вычислено и не составляет секрета. Каждый пользователь системы секретно выбирает такое целое случайное число е между 1 и N, что НОД (e, N) = 1. Используя алгоритм Евклида. он находит затем обратное к числу е по модулю N, т.е. такое целое число d. что de 1 (mod N). Если А хочет послать Б сообщение, то он сначала посылает ему точку индекс А указывает на пользователя А). Это ничего не говорит Б. который, не зная ни , ни, , не может восстановить , Однако, не придавая этому значения, он умножает ее на свое и посылает обратно А. На третьем шаге А должен частично раскрыть свое сообщение, умножив на. Так как N = О и = 1 (mod N), при этом получается точка , которую А возвращает Б. Тот может теперь прочитать сообщение, умножив точку на .

Заметим, что злоумышленник может знать , и Если бы он умел решать задачу дискретного логарифмирования на Е, то он мог бы определить по первым двум точкам, вычислить = (mod N) и =.

Аналог системы Эль-Гамаля. Это -- другая криптосистема с открытым ключом для передачи сообщений. Как и в описанной выше системе ключевого обмена, мы исходим из данных несекретных: а) конечного поля , б) определенной над ним эллиптической кривой Е к в) точки-"основания" В на ней. (Знать общее число N точек на Е нам не нужно.) Каждый из пользователей выбирает случайное целое число а, которое держит в секрете, затем находит и делает общедоступной точку аВ.

Чтобы послать Б сообщение, А выбирает случайно целое число k и посылает пару точек {kВ, + k{В)) (где В -- открытый ключ Б). Чтобы прочитать сообщение, Б умножает первую точку из полученной пары на свое секретное число и вычитает результат умножения из второй точки:

+ k{В)- (k В) = .

Таким образом. А посылает замаскированное вместе с "подсказкой" k В, при помощи которой можно снять "маску" kВ, если знать секретное число . Злоумышленник, который умеет решать загачу дискретного логарифмирования на Е, может, конечно, найти зная В и В.

Выбор кривой и точки. Существуют различные способы выбора эллиптической кривой и (в системах Диффи-Хеллмана и Эль-Гамаля) точки В на ней.

Случайный выбор (Е,В). Взяв какое-либо большое конечное поле , можно следующим образом осуществить одновременный выбор Е и В = (x, у) Е. (Будем предполагать, что характеристика р поля больше 3, так что эллиптическая кривая задана уравнением (1) из § 1; при q = или нетрудно сделать очевидные изменения в дальнейшем изложении.) Выбираем сначала случайным образом три элемента из в качестве х, у, а. Далее полагаем . Убеждаемся в том, что кубический многочлен не имеет ' кратных корней, что равносильно проверке условия . (Если это условие не выполняется, берем другую случайную тройку х, у, а.) Полагаем В = (х, у). Тогда В -- точка на эллиптической кривой .

Число N точек кривой можно найти несколькими способами. Первый полиномиальный алгоритм для вычисления #Е, построенный Рене Шуфом (Rene Schoof), является даже детерминистическим. Он основывается на нахождении значения #Е по модулю l для всех простых чисел l, меньших некоторой границы. Для этого анализируется действие автоморфизма Фробениуса (отображения в р-ю степень) на точках порядка l.

В статье Шуфа оценка времени работы была фактически O(), т. е. хотя и полиномиальной, однако быстро растущей. Вначале казалось, что алгоритм не имеет практического значения. Однако с тех пор многие пытались повысить скорость алгоритма Шуфа (Миллер (V. Miller), Элкис (N. Elkis). Бухман (J. Buchman), Мюллер (V. Miiller), Менезес (A. Menezes), Чарлап (L. Charlap), Коули (R. Coley) и Роббинс (D.Robbins)). Кроме того. Эткин (А. О. L. Atkin) разработал другой метод, который, хотя и не гарантирует полиномиального времени работы, на практике дает весьма удовлетворительные результаты. В результате всех этих усилий стало возможным вычислять порядок произвольной эллиптической кривой над , если q -- степень простого числа, записываемая 50 или даже 100 знаками.

Следует также отметить, что хотя для реализации систем Диффи-Хеллмана или Эль-Гамаля знать N не нужно, на практике желательно быть уверенным в их надежности, которая зависит от того, имеет ли N большой простои делитель. Если N есть произведение малых простых чисел, то для решения задачи дискретного логарифмирования можно использвать метод Полига-Силвера-Хеллмана (см. § IV. 3). Заметим, что метод Полига-Силвера-Хеллмана решает задачу дискретного логарифмирования в любой конечной абедевой группе (в отличие от также рассмотренного в § IV.3 алгоритма зычисления индекса, который зависят от особенностей ). Таким обрезом, нужно знать, что N не есть произведение малых простых чисел и не похоже, что это можно узнать, если не найти фактически значение N.

Редукция глобальной пары {Е,В) по модулю р. Упомянем теперь второй способ нахождения пары, состоящей из эллиптической кривой и точки на ней. Выберем сначала раз и навсегда "глобальную" эллиптическую кривую и точку бесконечного порядка на ней. Итак, пусть Е -- эллиптическая кривая, определенная над полем рациональных чисел (или, для большей общности, можно было бы использовать эллиптическую кривую, определенную над некоторым числовым полем), и В -- точка беексконечного порядка на Е.

Пример 2. Точка В = (0, 0) является точкой бесконечного порядка на эллиптической кривой Е: и фактически порождает всю группу рациональных точек на Е.

Пример 3. Точка В = (0, 0) является точкой бескспечного порядка на, Е: и порождает всю группу рациональных точек.

Далее, мы выбираем большое простое число р (или, если наша эллиптическая кривая определена над расширением К поля Q, выбираем некоторый простой идеал в К) и рассматриваем редукцию Е и В по модулю р. Точнее, для всех р, за исключением нескольких малых простых чисел, коэффициенты в уравнении для Е имеют взаимно простые с р знаменатели и, следовательно, могут рассматриваться пак коэффициенты в уравнении по модулю р. Если сделать замену переменных, приведя полученное уравнение над к виду то кубический многочлен в главой части не будет иметь кратных корней (за исключением нескольких малых простых р) и дает поэтому эллиптическую кривую над (которую мы будем обозначать Е(mod p)). Координаты точки В, будучи также приведенными по модулю р, дают точку на эллиптической кривой Е (mod p), которую мы будем обозначать В (mod p).

При использовании этого второго способа мы раз и навсегда фиксируем Е и В и за счет этого получаем много различных возможностей посредством изменения простого р.

Порядок точки В. С какой вероятностью "случайная" точка В на "случайной" эллиптической кривой оказывается порождающим элементом? Или, в случае нашего второго метода выбора (Е, В), какова вероятность того, что (для случайного р) точка В при редукции по модулю дает образующий элемент кривой Е (mod p)? Этот вопрос близок к следующему вопросу о мультипликативных группах конечны: полей: пусть целое b фиксированно, а простое р случайно; какова вероятность того, что b -- образующий в ? Вопрос изучался как для конечных полей, так и для эллиптических кривых. Более подробное изложение можно найти в работе Гулты (Gupta) и Мурти (Murty), приведенной в списке литературы.

Описанные криптосистемы могут быть надежными, даже если точка В не является порождающим элементом Фактически нужно, чтобы в циклической группе, порождаемой В: задача дискретного логарифмирования не была эффективно разрешима. Это будет так (т.е. все известные методы решения задачи дискретного логарифмирования в произвольной абелевой группе оказываются слишком медленными), если порядок В делится на очень большое простое число, скажем, имеющее порядок величины, близкий к N.

Один из способов гарантировать что наш выбор В является надлежащим (а фактически, что В порождает эллиптическую кривую) -- это взять такую эллиптическую кривую и такое конечное поле, чтобы число точек N было простым чистом. Тогда всякая точка В О будет порождающим элементом. Если использовать первый из описанных выше методов, то при фиксированном можно продолжать выбор пар (Е, В), пока не найдется такая, для которой число точек на Е есть простое число (что можно определить одним из тестов на простоту, обсуждавшихся в § V.1). Если применять второй метод, то для фиксированной глобальной эллиптической кривой Е над Q можно продолжать выбирать простые р, иона не найдем кривую Е(mod p), число точек на которой -- простое. Как долго нам придется ждать? Этот вопрос аналогичен следующему вопросу о группах : является ли (р-1)/2 простым числом, т.е. верно ли, что любой элемент, отличный от ±1, -- либо порождающий, либо квадрат порождающего элемента (см. упражнение 13 к §II.1)? Ни для эллиптических кривых, ни для конечных полей вопрос дока не получил явного ответа, однако в обоих случаях предполагается, что вероятность выбора р с требующимся свойством есть O(1/). 3аиечание. Для того чтобы Е(mod p) имела простой порядок N при большом р, надо выбирать Е так, чтобы она имела тривиальное кручение, т.е. чтобы на ней не было точек конечного порядка. кроме О. В противном случае N будет делиться на порядок периодической подгруппы.

2.8.3 Примеры эллиптических кривых и их применение

Пример. пусть р = 23. Рассмотрим эллиптическую кривую. В этом случае a=b=1 и мы имеем , что удовлетворяет условиям эллиптической группы по модулю 23.

Для эллиптической группы рассматриваются только целые значения от (0, 0) до (р, р) в квадранте неотрицательных чисел, удовлетворяющих уравнению по модулю р. В таблице 1. представлены точки (отличные от О), являющиеся элементами . В общем случае такой список создается по следующим правилам.

1. Для каждого такого значения х, что 0 х < р, вычисляется .

2. Для каждого' из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р. Если нет, то в нет точек с этим значением х. Если же корень существует, имеется два значения y, соответствующих операции извлечения, квадратного корня (исключением является случай, когда единственным таким значением оказывается у = 0). Эти значения (х, у) и будут точками

Таблица 1 Точка на эллиптической кривой

(О,1)	(6,4)	(12,19)
(0,22)	(6, 19)	(13,7)
(1,7)	(7,11)	(13,16)
(1,16)	(7,12)	(17,3)
(3,10)	(9.7)	(17,20)
(3,13)	(9,16)	(18,3)
(4,0)	(11,3)	' (18,20)
(5,4)	(11,20)	(19,5)
(5,19)	(12,4)	(19,18)

Пусть Р = (3, 10) и Q = (9, 7).

Тогда

Поэтому Р + Q = (17, 20). Чтобы найти 2Р, найдем

и поэтому 2Р = (7, 12).

Пример обмена ключами по схеме Диффи-Хеллмана

В качестве примера возьмем р = 211, (что соответствует кривой и G = (2, 2). Можно подсчитать, что 241G = О. Личным ключом пользователя А является = 121, поэтому открытым ключом А будет = 121(2, 2) = (115, 48). Личным ключом пользователя В является = 203 , поэтому открытым ключом участника В будет 203(2, 2) = (130, 203). Общим секретным ключом является 121(130, 203) = 203(115, 48) = (161,169).

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

Шифрование/расшифрование с использованием эллиптических кривых

В специальной литературе можно найти анализ нескольких подходов к шифрованию/дешифрованию, предполагающих использование эллиптических кривых. В этом разделе мы рассмотрим, пожалуй, наиболее простой из этих подходов. Первой задачей в рассматриваемой системе является шифрование открытого текста сообщения m, которое должно будет пересылается в виде значения х - у для точки . Здесь точка будет представлять шифрованный текст и впоследствии будет дешифроваться. Обратите внимание, что мы не можем закодировать сообщение просто координатой х или у точки, так как не все такие координаты имеются в (см., например, табл. 6.4). Опять же, существует несколько подходов к такому кодированию, но мы их рассматривать не будем -- для наших целей достаточно просто отметить, что имеются относительно прямые методы, которые могут быть здесь применены.

Как и в случае системы обмена ключами, в системе шифрования, дешифрования в качестве параметров тоже рассматривается точка G и эллиптическая группа . Пользователь А выбирает личный ключ и генерирует открытый ключ . Чтобы зашифровать и послать сообщение пользователю В, пользователь А выбирает случайное положительное целое число к и вычисляет шифрованный текст , состоящий из пары точек

= {kG, + k).

Заметим, что сторона А использует открытый ключ стороны В: . Чтобы дешифровать этот шифрованный текст, В умножает первую точку в паре на секретный ключ В и вычитает результат из второй точки:

+ k - (kG)= + k (G)- (kG)=

Пользователь А замаскировал сообщение с помощью добавления к нему k. Никто, кроме этого пользователя, не знает значения k, поэтому, хотя и является открытым ключом, никто не сможет убрать маску k. Однако пользователь А включает в сообщение и "подсказку", которой будет достаточно, чтобы утрать маску тому, кто имеет личный ключ . Противнику для восстановления сообщения придется вычислить k по данным G и kG, что представляется трудной задачей.

В качестве примера подобного шифрования рассмотрим случай р = 751, (-1,188) (что соответствует кривой и G = (0, 376). Предположим, что пользователь А собирается отправить пользователю В сообщение, которое кодируется эллиптической точкой =(562, 201), и что пользователь А выбирает случайное число k = 386. Открытым ключом В является =(201,5). Мы имеем 386(0,376)= (676,558) и (562,201) + 386(201, 5) = (385, 328). Таким образом, пользователь А должен послать шифрованный текст {(676, 558), (385, 328)}.

2.8.4 Безопасность криптографии с использованием эллиптических кривых

Безопасность, обезпечизаемая криптографическим подходом на основе эллиптических кривых, зависит от того, насколько трудной для решения оказывается задач; определения k по данным kP и Р. Эту задачу обычно называют проблемой логарифмирования на эллиптической кривой. Наиболее быстрым из известных на сегодня методов логарифмирования на эллиптический кривой является так. называемый -метод Полларда (Pollard). В таблице 2. сравнивается эффективность этого метода и метода разложения на простые множители с помощью решета в поле чисел общего вида. Как видите, по сравнению с RSA в случае применения методов криптографии на основе эллиптических кривых примерно тот же уровень защиты достигается со значительно меньшими значениями длины ключей.

К тому же при равных длинах ключей вычислительные усилия, требуемые при использовании RSA и криптографии на основе эллиптических, кривых, не сильно различаются [JLJRI97]. Таким образом, в сравнении с RSA при равных уровнях защиты явное вычислительное преимущество принадлежит криптографии на основе эллиптических кривых с более короткой длиной ключа.

Таблица 2 Вычислительные усилия, необходимые для криптоанализа при использовании эллиптических кривых и RSA

Размер ключа	MIPS-годы
150
205
234

а) Логарифмирование на эллиптической кривой с помощью р-метода Полларда

Размер ключа	MIPS-годы
512
768
1024
1280
1536
2048

б) Разложение на множители в целых числах с помощью метод! решета в поле чисел общего вида

2.9 Шифры совершенные и близкие к совершенным

Вопрос о теоретической стойкости шифров систематически исследовал К. Шеннон в фундаментальной работе [23]. Заметим, что независимо изучение теоретической стойкости шифров проводил коллектив под руководством В.А. Котельникова [24].

2.9.1 Шифры совершенные по К. Шеннону

Шеннон ввел понятие совершенного шифра, точнее, совершенного по открытому тексту. Обозначим: X, Y, K, F - множества соответственно открытых текстов, шифртекстов, ключей, отображений. Отображение - это ограничение отображения на множество . Здесь {k} - множество из одного элемента. Для дальнейшего изложения удобным будет следующее определение.

Определение 1. Тройка множеств X, Y, K с функцией называется шифром, если выполнены условия [25, с.89]:

1. Функция f сюръективна.

2. Для любого функция инъективна.

Определение 2. Шифр (X, K, Y, f) с вероятностными распределениями называется совершенным (при нападении на xЄX и перехвате yЄY), если для любых xЄX и yЄY [15, с.153]: p(x/y)=p(x).

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

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

Рассмотрим пример под названием "Одноразовый блокнот" ("One Time Pad").

Пусть имеется русский алфавит в виде таблицы:

А	Б	В	Г	Д	Е	Ё
Ж	З	И	Й	К	Л	М
Н	О	П	Р	С	Т	У
Ф	Х	Ц	Ч	Ш	Щ	Ъ
Ы	Ь	Э	Ю	Я

Для зашифрования и расшифрования в "одноразовом блокноте" используется следующая таблица шифрования, полученная путем случайного перемешивания:

Ж	Ш	Г	А	Ь	Ы	Д
П	О	Р	Н	Е	Ъ	С
З	В	И	Э	Я	Б	Й
М	Л	К	Ф	Ч	Ё	У
Х	Ц	Т	Ю	Щ

Шифрование: первой букве А исходного текста соответствует буква Ж шифрованного текста, букве Я - буква Щ и так далее. Шифрование происходит следующим образом: перейдя к очередной букве исходного текста, шифровальщик заменяет ее в тексте на соответствующую букву из таблицы шифрования. Расшифрование происходит в обратном порядке.

Таблица шифрования вырабатывается в двух экземплярах и более (в зависимости от числа участников информационного обмена), которые распределяются между участниками. Таблицу шифрования следует хранить в секрете.

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

В битовом варианте данный шифр работает следующим образом.

Исходный текст преобразуется в битовую последовательность.

Генерируется случайная битовая последовательность (например, с помощью генератора случайных чисел), длина которой равна длине сообщения. Этак последовательность является ключом.

Этот ключ по защищенному каналу передается всем участникам защищенного информационного обмена.

Ключ надлежит хранить в секрете.

Зашифрование происходит путем побитового сложения текста с ключом по модулю 2 (операция XOR).

Расшифрование происходит аналогичным образом.

В работе "Заметки о совершенных шифрах" А.С. Щепинов [22] доказывает, что группа подстановок элементов конечного множества содержит подмножества, некоторые из которых являются совершенными шифрами, по определению Шеннона.

Приведем ряд утверждений о совершенных шифрах без доказательства (доказательства подробно изложены в работе Зубова А.Ю.[15]).

1. Шифр с ограниченным ключом не является совершенным

2. У совершенного шифра может быть ограниченный ключ, но только если длина ключа равна длине сообщения

3. Для совершенного шифра справедливы неравенства .

Определение 3. Шифр с условием p(k/y)=p(k) для любых kЄK и yЄY называется совершенным по ключу.

Криптостойкость совершенных шифров не вызывает сомнения. Однако использование их при защищенной передаче данных сопряжено с рядом трудностей. Например, длина ключа должна быть не меньше длины сообщения. То есть защищенный канал, по которому будет передан ключ, должен пропускать объем информации не меньше объема открытого текста.

В силу этой и других причин широкое распространение получили несовершенные шифры (например, в шифровании деловой переписки малого и среднего бизнеса).

Поэтому вместе с определением совершенного шифра возникла необходимость определить шифр, близкий к совершенному.

2.9.2 Шифры, близкие к совершенным

В книге "Криптография" А. Бабаш и Г. Шанкин говорят о шифрах, близких к совершенным [25 с.304-305].

Пусть - произведение шифров такое, что А₁=(X₁, K₁, Y₁, f₁), A₂=( X₂, K₂, Y₂, f₂), Y₁=X₂, то есть множество шифробозначений первого шифра является множеством шифрвеличин второго шифра.

Произведение шифров, не являющихся совершенными, может дать шифр "близкий" к совершенному шифру.

Пусть (X, K, Y, f) - шифр модульного гаммирования (X = Y) и распределение вероятностей P(K)=(p(k), kЄK), такое, что p(k) > 0, для любого kЄK. Тогда квадратная матрица условных вероятностей M = РРp(y/x)РР является дважды стохастической и, следовательно, как известно из курса алгебры, существует предел

В частности, к-ая степень (X, K, Y, f)^k шифра предсавляет собой шифр, переходные вероятности которого стремятся к величине 1/|?| ??? ?>?, то есть шифр (X, K, Y, f)^k близок к совершенному шифру при достаточно большом k.

Аналогично определениям 2 и 3, введем понятия шифров, близких к совершенным.

Определение 4. Шифр с условием для любых xЄX, yЄY назовем е - совершенным по тексту, обозначение: .

Заметим, что конструкция Бабаша-Шанкина является примером такого шифра: к-я степень (X, K, Y, f)^k является е(k) - совершенным шифром (т.е. е зависит от k).

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

Интересной является задача построения "шкалы" шифров, т.е. е-отклонений от совершенного по тексту.

Точно так можно ввести понятие БСШ по ключу, обозначим . Теперь шифр , являющийся е-совершенным по тексту и д-совершенным по ключу, является обобщением шифра, совершенного по тексту и по ключу.

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

И "меру отклонения" шифра от совершенного можно изучать по тому, насколько распределения P(x), P(k) отличаются от равномерных (ср. с теоремой 3 [15 c/156]).

Как известно, совершенные шифры используются крайне редко. Причина тому - требуемая большая длина ключа. Шифры , представляются разумным компромиссом в соотношении "цена - качество". Именно, можно задавать необходимые е max и д max, одновременно вычислив возможные для шифров данного вида е min и д min. Тогда множество допустимых в данной ситуации шифров изображается точками прямоугольника , и можно строить целевую функцию: стоимость реализации . После этого задача выбора оптимального при заданных условиях шифра может быть сформулирована так: найти экстремум функции двух переменных в области.

2.10 Экстремальные шифры

К. Шеннон в ряде своих основополагающих работ по теории шифрования [23] сформулировал условия, которым должен удовлетворять стойкий блочный шифр. Этими условиями он назвал рассеивание и перемешивание:

Рассеивание - это свойство шифра, при котором один символ (бит) исходного текста влияет на несколько символов (битов) шифртекста, оптимально - на все символы в пределах одного блока. Если данное условие выполняется, то при шифровании двух блоков данных с минимальными отличиями между ними должны получаться совершенно непохожие друг на друга блоки шифртекста. Точно такая же картина должна иметь место и для зависимости шифртекста от ключа - один символ (бит) ключа должен влиять на несколько символов (битов) шифртекста.

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

А.Винокуров в серии выпусков по криптографии для электронного журнала "iNFUSED BYTES Online" раскрывает смысл этих свойств следующим образом: "Если шифр обладает обоими указанными свойствами в достаточной степени, то любые изменения в блоке открытых данных приводят к тому, что с точки зрения наблюдателя все символы (биты) в зашифрованном блоке получат новые значения, равновероятные в области их определения и независимые друг от друга. Так, если шифр оперирует информацией, представленной в двоичной форме, то инвертирование даже одного бита в блоке исходных данных приведет к тому, что все биты в соответствующем блоке шифрованных данных с вероятностью 1/2 независимо друг от друга так же поменяют свое значение. Такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа. Данное условие является обязательным для шифра рассматриваемого типа, претендующего на то, чтобы считаться хорошим". [26]

В своей работе Столлингс говорит о следующем свойстве шифра, которое называет лавинным эффектом.

Лавинный эффект - это способность шифра максимально изменять выходные данные при минимальных изменениях во входных данных [16]. Например, изменение значения всего одного бита открытого текста или ключа должно отражаться в изменении значений многих битов шифрованного текста.

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

Далее предлагается свойство, которое объединяет в себе все вышеперечисленные свойства.

Понятие экстремальности

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

Далее нам потребуется одна из теорем Эрнесто Чезаро.

Теорема 2.1 (Э. Чезаро).

Вероятность того, что наибольшим общим делителем двух случайно выбранных целых чисел является 1, равна .

Приведенная теорема используется для исследования последовательности целых чисел (например, номеров бит) на случайность. Если при обработке последовательности получена оценка для значения , близкая к 3,14, то можно считать данную последовательность случайной.

Далее нам потребуется понятие кодового расстояния. Введем это понятие.

Кодовым расстоянием двух битовых последовательностей назовем количество бит, на которые отличаются последовательности.

Пусть имеется шифр А с длиной блока N бит, открытые тексты и длины N и ключ . Открытый текст отличается на один бит от текста , позиция этого бита случайна, обозначим ее . При зашифровании текстов и получены зашифрованные тексты и соответственно. Сравнив тексты и , получим - кодовое расстояние этих текстов при -м отличном бите исходных текстов и - последовательность номеров бит, на которые и отличаются. Мы излагаем здесь свой подход к характеристикам шифра.

Проверим на случайность с помощью метода, основанного на теореме 2.1. Удалив из последовательности элементы, которые делают ее неслучайной, получим последовательность независимых номеров бит. Количество элементов последовательности обозначим и назовем его случайным кодовым расстоянием выходных текстов при -м отличном бите исходных текстов.

Определение 2.1.

Пусть имеется шифр А с длиной блока N, и случайным кодовым расстоянием , тогда экстремальностью шифра А по тексту при -м отличном бите исходных текстов назовем величину , которая вычисляется по формуле:

, (2.1)

Очевидно, что нельзя судить об экстремальности шифра, проанализировав отклик в выходном тексте, при изменении всего одного бита исходного текста. Нужно получить значения для каждого бита исходного текста в пределах блока, каким-то образом обработать полученные данные (например, взять среднеарифметическое значение) и вывести финальное значение экстремальности шифра .

Из формулы (2.1) видно, что экстремальность может принимать значения от 0 до 1 включительно.

Чем ближе значение к нулю, тем более "хорошим" является алгоритм.

Действительно, если мало, то это значит, что при изменении всего одного бита в исходных данных в выходных данных меняется количество бит, близкое к половине. При этом номера этих бит образуют случайную последовательность. А это значит, что инвертирование даже одного бита в блоке исходных данных приведет к тому, что все биты в соответствующем блоке шифрованных данных с вероятностью близкой к 1/2 независимо друг от друга так же поменяют свое значение.

И наоборот, чем ближе значение к 1, тем более "плохим" является алгоритм.

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

Введем понятие экстремальности по ключу.

Пусть имеется шифр А с длиной блока N бит, открытый текст длины N и ключи и . Ключ отличается на один бит от ключа , позиция этого бита случайна, обозначим ее . При зашифровании текста на ключах и получены зашифрованные тексты и соответственно. Сравнив тексты и , получим - кодовое расстояние этих текстов при -м отличном бите исходных текстов и - последовательность номеров бит, на которые и отличаются.

Проверим на случайность с помощью метода, основанного на теореме 2.1. Удалив из последовательности элементы, которые делают ее неслучайной, получим последовательность независимых номеров бит. Количество элементов последовательности обозначим и назовем его случайным кодовым расстоянием выходных текстов при -м отличном бите ключей.

Определение 2.2.

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

, (2.2)

Нахождение и интерпретация значения экстремальности по ключу аналогично нахождению и интерпретации значения экстремальности по тексту.

Определение 2.3.

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

(2.3)

Вектор экстремальности является наиболее тонкой характеристикой алгоритмов шифрования. Он объединяет в себе все вышеперечисленные характеристики и свойства.

Экстремальный шифр

Введем понятие экстремального шифра.

Определение 2.4.

Шифр А назовем экстремальным, если его вектор экстремальности является нулевым:

(2.4)

Иными словами экстремальным назовем шифр, который при изменении одного любого бита исходных данных (в исходном тексте или ключе) инвертирует в выходном тексте N/2 случайных бит. Это означает, что все биты в выходном тексте поменяли свое значение с вероятность 1/2. Согласно А. Винокурову такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа.