Современная прикладная криптография

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

Процедура начинается с присвоения начальных значений параметрам:

M - часть необработанной процедурой последовательности ,

H - текущее значение хэш-функции (в начальный момент это стартовый вектор),

Е - текущее значение контрольной суммы < 2²⁵⁶, l - текущее значение длины обработанной последовательности < 2²⁵⁶ .

Этап I. Присвоение начальных значений .

Этап 2.

2.1. Проверить условие для длины |M| > 256. Да --> этап 3.

2.2. l = l + |н|

2.3. M' = (символ обозначает присоединение)

2.4.

2.5. H = к (M',H) (функция к будет описана позже)

2.6. H = к (L,H)

2.7. H = к (,h)

2.8. Конец работы алгоритма. Значение H на шаге 2,7 является значением функции хэширования.

Этап 3.

3.1. Вычислить суффикс слова м длины 256 бит.

3.2.

3.3. L : = L + 256

3.4.

3.5.

3.6. Перейти к этапу 2.

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

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

Этап к.1. Генерация ключей - слов длины 256 - для ГОСТ 28147-89. Этап к.2. Зашифрование 64-битных блоков слова H на ключах

. полученных на этапе к.1, с помощью ГОСТ 28147-89 в режиме простой замены.

Этап к.3. Перемешивание выхода этапа к.2 с помощью регистров сдвига. пусть

-

представление двоичного вектора X длины 256 в виде конкатенации разного числа векторов одинаковой длины.

Обозначим через

, - сложение векторов по модулю 2.

,

где

Для генерации ключей этапа к.I необходимо использовать исходные данные H.M - 256-битные слова и слова , такие, что

I. i=1, U:=H, V:=M

2. W:=UV,

3. i=i+1

4. Проверить i=5. Да --> п.7, нет --> п.5.

5.

6. Перейти к п.3.

7. Конец.

На этапе к. 3 исходные данные с помощью набора ключей с этапа к.1 преобразуются с использованием ГОСТ 28147-89

где - обозначает преобразование зашифрования в режиме простой замены.

Пусть преобразование вида

Тогда значение пошаговой функции хэширования к после последнего этапа к.3 равно

где - i - тая степень преобразования .

Этим завершается описание всего алгоритма вычисления функции хэширования.

3.5 Использование эллиптических кривых в криптологии

Эллиптические кривые над различными полями оказались в последнее десятилетие в центре внимания по нескольким причинам, одной из которых является их применение в криптографии.

Криптосистемы на основе эллиптических кривых впервые были предложены в работах Миллера и Коблица [M86, K87]. Многие современные стандарты схем цифровой подписи также основаны на группах точек эллиптических кривых [например, ГОСТ 34.10-2001, FIPS 186-2]. Генераторы псевдослучайных последовательностей, широко используемые при получении криптографических ключей, также могут быть построены над группами точек эллиптических кривых [H94, BGS98, GL01]. В некоторых алгоритмах проверки простоты и факторизации целых чисел также используются эллиптические кривые [В03].

Рассмотрим в начале основные понятия и определения теории эллиптических кривых.

Аффинное и проективное пространства.

Пусть F - некоторое поле и - множество наборов = с из F. Его можно рассматривать как векторное пространство при обычном способе определения сложения и умножения на скаляры. А можно его рассматривать как множество и называть его n-мерным аффинным пространством над F. Элементы = с из F этого пространства будем называть аффинными точками или просто точками. Точка этого пространства (0,…,0) называется началом координат.

(F) , n-мерное проективное пространство над F, несколько более сложное понятие. Для этого рассмотрим (F), обозначая его точки через .

Определим отношение эквивалентности на этом (n+1)-мерном аффинном пространстве с выброшенным началом координат следующим образом. Точка эквивалентна точке , если существует такой элемент d из F*, что (F* - обратимые элементы поля F). Классы эквивалентности называются точками пространства (F) или проективными точками. Во многих работах, например в [K04], для обозначения классов эквивалентности

[а] =[] используется обозначение ().

Пространство(F) содержит больше точек, чем . Покажем это.

Утверждение.

Пусть H - множество классов [a] из(F) с нулевой координатой . Определим отображение ф точки [a] из ((F)\ H) в следующим образом

ф([a]) = ().

Тогда это отображение ф является взаимно однозначным.

Доказательство.

Для доказательства инъективности заметим, что, если для разных классов [a] и [b] из ((F)\ H) будет выполнено равенство ф([a])=ф([b]), то для i=0,1,…, n. Пусть с=.

Тогда для i=0,1, …,n, так что [a]=[b]. Получили противоречие.

Для доказательства сюрьективности заметим, что, если v=(v, …, v) из , то положим w=(1,v, …, v). Тогда ф([w]) = v и каждый элемент имеет прообраз.

Множество H называется бесконечно удаленной гиперплоскостью. Множество H обладает структурой пространства . Таким образом, (F) состоит из двух частей ((F)\ H) и Н, первая есть копия пространства , и его точки называются конечными точками, а другая - копия пространства , и его точки называются бесконечно удаленными точками.

Например, P(F) состоит из одной точки [a] (a - не нулевая) и начала координат [0].

Для определения множеств, называемых гиперповерхностями, привлечем многочлены.

Пусть F[] - кольцо многочленов от n переменных над полем F. Если

f(x) - элемент этого кольца, то он имеет вид

f(x) =

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

Многочлен вида a называется одночленом. По определению общая степень одночлена равна сумме (i+i+…+i), а степень по переменной x равна i. Степень многочлена f(x) есть максимум степеней одночленов, которые входят в f(x) с ненулевыми коэффициентами. Степень по x многочлена f(x) есть максимум степеней по x одночленов, которые входят в f(x) с ненулевыми коэффициентами. Если обозначить эти степени через deg f(x) и deg (f(x)), то

(а) deg( f(x) g(x)) = deg f(x) + deg g(x);

(b) deg (f(x)) g(x)) = deg (f(x)) + deg(g(x)).

Если все одночлены, входящие в f(x), имеют степень L, то f(x) называется однородным многочленом степени L. Однородный многочлен иногда называется формой. Форма степени 1 называется линейной формой, степени 2 называется квадратичной формой, а форма степени 3 - кубической формой и так далее.

Каждый однородный многочлен f(x, …, x) степени L удовлетворяет условию

f(d x,…, d x) = (d) f(x, …, x)

для всех x, …, x, d из поля F.

Оказывается, для бесконечного поля многочлен, удовлетворяющий этому условию, является однородным степени L (см. [K04, стр.37]).

Пусть К - некоторое поле, содержащее поле F. Если f(x) из F[] и a из A(K), то можно подставить a вместо x и вычислить f(a). Это показывает, что f(x) определяет функцию из A(K) в K, которая переводит a в f(a). Точка a из A(K), для которой f(a)=0, называется нулем функции f(x) [AP87].

Для произвольного ненулевого многочлена f(x) определим множество

H (K) = {a из A(K) : f(a)=0},

называемое гиперповерхностью в аффинном пространстве A(K), определяемой многочленом f. Если поле К конечно, то конечно и число точек в H(K).

Определим теперь проективную гиперповерхность. Пусть h(x) из F[] - ненулевой однородный многочлен степени L. Как и выше К есть поле, содержащее поле F. Для d из K* имеем h(dx) = (d) h(x). Отсюда следует, что если a из A(K) и h(a)=0, то h(da)=0. То есть, любой другой элемент из класса эквивалентности [a] также является нулем многочлена h(x). Таким образом, можно положить H` (K) = {[a] из P(K) : h(a)=0}. Это множество называется гиперповерхностью в проективном пространстве P(K) , определенной однородным многочленом h .

В более общем виде, если f, …, f - многочлены в F[], положим

V = {: a из F, i=1,…,n, f()=0, j=1,…,m}, которое называется алгебраическим множеством, определенным над полем F. В работе [Р91] это множество называется (алгебраическим) многообразием.

Аналогично, множество общих проективных нулей (т.е. корней из P(K)) конечного набора однородных многочленов из F[] называется проективным алгебраическим множеством.

Определим проективное замыкание аффинной гиперповерхности. Пусть f(x) из F[], и определим f `(y) = f `(y,y…,y) посредством формулы

f `(y) = y f(y/y,…,y/y)).

Утверждение.

f `(y) - однородный многочлен степени deg f. Кроме того, f `(1,y,…,y) = f(y,…,y).

Доказательство.

Положим L=deg f и рассмотрим одночлен степени d<L.

Тогда y( y/y) …( y/y) = (y) (y)…(y) , причем последний одночлен имеет степень L. Таким образом, в f ` все одночлены имеют степень L, что доказывает первую часть утверждения. Вторая часть следует из определения многочлена.

Рассмотрим гиперповерхность H (K) в A(K). Многочлен f `(y) однороден по переменным y,…,y, а потому f ` определяет гиперповерхность H`(K) ={[a] из P(K) : f`(a)=0} в P(K). Эта гиперповерхность называется проективным замыканием аффинной гиперповерхности H(K) в P(K).

Пусть отображение : A(K) в P(K) определено равенством

(a,…,a) = [(1, a,…,a)].

Отображение взаимно однозначно с Im,где Im-область значений отображения (т.е. образ), и, кроме того, образ H (K)при содержится в H`(K), так как, очевидно,

f`([(1, a,…,a)]) = f(a,…,a) = 0 для всех a из H (K).

Вообще говоря, гиперповерхность H`(K) имеет больше точек, чем H (K), поскольку в ней еще имеется пересечение с бесконечно удаленной гиперплоскостью.

Основываясь на предыдущих определениях перейдем к эллиптическим кривым.

Далее мы будем фактически рассматривать случай n=2. А именно, аффинное пространство A(F) и проективное пространство P(F). Согласно определениям работ [Р91, K04] пространство P(F) называется проективной плоскостью (projective plane). Поменяем для простоты обозначения, точки P(F) будем обозначать через (x :y :z).

Иногда, где не может возникнуть путаница, будем обозначать точку проективной плоскости P(F) с однородными координатами (x : y : z) и через (x , y , z).

Более наглядно проективную плоскость можно представить над полем действительных чисел R. В этом случае точками проективной плоскости P(R) являются прямые в A(R) (или R) , проходящие через начало координат, или классы эквивалентности (x : y : z) на R\{0}, где (x,y,z) эквивалентно (dx,dy,dz), если d из R\{0}. Приведенные выше рассуждения показывают, что P(R) содержит экземпляр A(R) , такое стандартное вложение задается отображением точки (x,y) из A(R) вида :(x,y) (x : y : 1). Дополнение к образу в P(R) состоит в точности из тех точек, у которых z=0 (Ранее обозначалось через Н). Эти точки называются бесконечно удаленными [K04].

В свою очередь (P(R)\ H) отображается взаимно однозначно на A (R), (где H - множество точек (x : y : z) из P(R) с нулевым значением z) с помощью отображения вида

ф((x : y : z)) = (x/z, y/z).

Пусть K -некоторое поле и f(x,y,z) из K[x,y,z] - однородный многочлен степени d. Полезно ввести геометрическую терминологию. Говорят, что уравнение

f(x,y,z) = 0

определяет кривую степени d над полем К. Поле К называется ее полем определения.

В работе [K04] проективной плоской кривой над полем К называется именно однородный многочлен степени d. Многочлен f нельзя рассматривать как функцию, определенную на проективной плоскости P(K). Тем не менее, можно говорить о множестве корней многочлена f как о подмножестве P(K). В самом деле, если f(x,y,z) = 0 для некоторых однородных координат точки (x:y:z) проективной плоскости, то это же равенство выполняется для любых других однородных координат этой точки в силу однородности многочлена f. Множество

f(K) = {(x:y:z) : x,y,z К, f(x,y,z) = 0}

называется множеством K-точек кривой f . В этих обозначениях соответствующей аффинной кривой называется кривая, задаваемая многочленом вида F(x,y) = f(x,y,1).

В тех случаях, когда d = 1,2 или 3, проективная кривая называется соответственно прямой, кривой второго порядка и кубической кривой [K04, стр.40].

В работе [Р91, стр. 18, 20] плоская кривая, задаваемая однородным квадратным уравнением

Ах +Bxy +Cy +Dxz +Eyz +Fz = 0

называется коникой.

Если L - поле, содержащее К, то можно рассматривать корни многочлена f в проективном пространстве P(L). В введенной выше терминологии это есть H`(L). Гиперповерхность в проективном 2-пространстве и называется кривой.

Точка a из H`(L) называется неособой, если она не является решением системы уравнений

df/dx = 0,

df/dy = 0,

df/dz = 0.

Прямой в P(K) над полем К будем далее, следуя [K04] , называть гиперповерхность, определяемую в P(K) ненулевым многочленом Ах+Вy+Сz с коэффициентами из К (правда в русском переводе в [K04] прямой называется и ненулевой многочлен ax+by+cz , и уравнение ax+by+cz=0. ).

Точки из P(R) , для которых z=0, соответствуют классам (x : y : 0). Эти точки образуют «бесконечно удаленную прямую». По определению прямая L на проективной плоскости P задается уравнением aX+bY+cZ=0 и проходит через точку (X:Y:0) тогда и только тогда, когда aX+bY =0. В аффинных координатах та же прямая задается уравнением ax+by+c=0, так что все прямые с одним и тем же отношением a:b проходят через одну точку на бесконечности. [P91, c.21]

В таком случае прямая, задаваемая уравнением

(df/dx(a)) x + (df/dy(a)) y + (df/dz(a)) z = 0

называется касательной к кривой f в точке a.

Кривая, определяемая уравнением f(x,y,z) = 0, называется неособой кривой, если все точки в H(L) неособые для всех расширений L поля K.

Утверждение.

(а) Две различные прямые в P(K) пересекаются ровно в одной точке.

(b) Для любых двух различных точек (x:y:z) и (x`:y`:z`) проективной плоскости P(K) существует ровно одна прямая ax+by+cz=0, содержащая эти точки.

Доказательство.

(а) Пусть ax+by+cz=0 и a`x+b`y+c`z=0 - задают 2 различные прямые в P(K). Рассмотрим пространство решений системы уравнений над К вида

ax+by+cz=0

a`x+b`y+c`z=0

Прямые считаются совпадающими, если (a,b,c) кратно (a`,b`,c`). А так как прямые различные, то коэффициенты не кратны и ранг матрицы составленной из коэффициентов системы равен 2. Следовательно, пространство решений этой системы имеет размерность 1 и ему соответствует в точности одна точка пересечения прямых на проективной плоскости P(K).

(b) Для того, чтобы убедиться в этом достаточно рассмотреть систему уравнений

xa+yb+zc=0

x`a+y`b+z`c=0,

матрица коэффициентов которой имеет ранг 2, а система одно решение (a,b,c).

Утверждение согласуется с нашими представлениями из аналитической геометрии в 3-х мерном пространстве над полем действительных чисел R. Прямой в P(R) соответствует плоскость в R, проходящая через начало координат, а точке в P(R) соответствует прямая, проходящая через начало координат. Две различные такие плоскости в R пересекаются по прямой, проходящей через начало координат. Она соответствует точке в пространстве P(R). Также в R через две прямые, проходящие через начало координат можно провести одну плоскость, что соответствует утверждению (b).

Заметим, что в A(K) прямые не обязательно пересекаются в одной точке.

Утверждение.

Если поле L алгебраически замкнуто, то прямая в пространстве P(L) пересекает кривую степени d, определяемую однородным многочленом f(x,y,z), в d точках.

Доказательство. Чтобы показать это, запишем x=x/z, y=y/z, и обозначим

f*(x,y) = f(x,y,1). Мы рассмотрим в данный момент аффинное пространство A(L) и аффинную часть кривой. Для нахождения точек пересечения кривой, задаваемой уравнением f*(x, y) = 0, с прямой y = mx+b (получается из ax+by+cz=0 ) подставляем значение y в f* и находим корни уравнения. Если f имеет степень d, то последнее уравнение будет иметь в общем случае степень d, а так как L алгебраически замкнуто, будет в наличии d корней с учетом кратности. Исключениями являются лишь пересечения на бесконечности, когда f*(x, mx+b) , будет иметь степень меньшую d.

Если a из H`(L), то касательная прямая к f в точке a пересекается с кривой f=0 с кратностью 2 или больше. Если кратность больше, чем 2, то a называется точкой перегиба.

Если многочлен f(x,y,z) определен над К, то его корень в P(K) называется рациональной точкой над К.

Будем говорить, что неособый однородный кубический многочлен f(x,y,z) из K[x,y,z] определяет эллиптическую кривую над К, если имеется по крайней мере одна рациональная точка [AP87].

Группы преобразований занимают в геометрии центральное место.

Аффинная замена координат в K имеет вид Ф v +B , где v=(x,y) из К, Ф - обратимая 2X2 - матрица из группы обратимых матриц GL(2,K), а В - вектор сдвига. Известно, что любая невырожденная коника Ах+Bxy +Cy+Dxz +Eyz +Fz= 0 приводится аффинным преобразованием к одной из 12 форм. [P91, c.18]

Рассмотрим группу GL(3,K) всех обратимых матриц третьего порядка над полем К. Так как для любой матрицы Ф из GL(3,K) будет Ф(d v) = dФv для любого v из A(K), то Ф задает взаимно однозначное отображение P(K) на P(K), называемое проективным преобразованием проективной плоскости P(K), соответствующим матрице Ф [K04, P91].

Матрицы Ф1 и Ф2 задают одно и то же преобразование пространства P(K) тогда и только тогда, когда одна из них пропорциональна другой, то есть Ф1 = d Ф2, где d из К*.

Кубическая кривая общего вида задается однородным многочленом

F(x,y,z)= C y+C x y +C x y+C y z+ Cx y z +C y z+ C x + +C x z +Cx z + C z.

Утверждение.

Пусть f -такая кубическая кривая над полем К, что точка (x,y,z) является ее точкой перегиба. Тогда существует такое проективное преобразование Ф, что

f = yz+a xyz + a yz - x -a xz - a x z-az.

Доказательство. См. [K04, c. 59].

Кубическую кривую такого вида называют кривой, заданной в длинной форме Вейерштрасса. Соответствующее уравнение в аффинных координатах (при z=1) записывается в виде

y+a xy+ a = x+ a x +a x + a.

(Обозначения в этих записях стандартные [K04].)

Эллиптической кривой над полем К называется неособая (гладкая) кривая, заданная в длинной форме Вейерштрасса

y+a xy+ a = x+ a x +a x + a,

при условии, что все коэффициенты лежат в поле К [БССШ03].

Через E(K) обозначается множество, состоящее из точек (x, y) из А(К), удовлетворяющих этому уравнению, и «бесконечно удаленной» точки О.

Следует еще раз отметить на встречающиеся различные определения эллиптической кривой. Например, во многих работах [K87, B03, ГОСТ 34.10-2001, FIPS 186-2] эллиптической кривой называется именно множество точек Е(К), удовлетворяющих соотношению y+a xy+ a = x+ a x +a x + a или y = x+ a x +b, со специально выбранными коэффициентами для гладкости, причем «бесконечно удаленную» точку О не всегда включают в множество Е(К) [ГОСТ 34.10 - 2001].

Условие гладкости кривой означает, что в множестве E(K) , где К -алгебраическое замыкание поля К, не существует точек, в которых одновременно обращались бы в нуль частные производные d f(x,y)/dx и d f(x,y)/d y,

где f(x,y)= y+axy+ ay - x- a x -a x - a.

Иными словами, система уравнений

d f(x,y)/dx = ay-3x - 2a x - a = 0

d f(x,y)/d y = 2y+a x+a = 0

не имеет решений в E(K). Условие гладкости необходимо для задания на точках кривой структуры абелевой группы. Проверка гладкости кривой достаточно проста.

Если характеристика поля char K не равна 2, то линейной заменой переменных

y y -(ax+ a)/2 кривая приводится к виду

y= x+a x +a x + a.

Конечно, в последнем выражении значения коэффициентов a, a, a другие, чем в исходном.

Если характеристика поля char K не равна 2 и 3, то линейной заменой переменных x x - 1/3 a2, эллиптическая кривая примет вид

y = x + a x +b,

где a,b из поля К. Этот вид задания эллиптической кривой называется короткой формой Вейерштрасса.

Условие гладкости кривой в этом случае означает, что кубический многочлен

x+a x+b не имеет кратных корней. Это выполняется тогда и только тогда, когда дискриминант этого многочлена, равный - (4 a + 27 b), отличен от нуля.

Как правило, в многочисленных криптографических приложениях эллиптические кривые задаются именно в этой короткой форме Вейерштрасса [K87, B03, ГОСТ 34.10-2001, FIPS 186-2], а в качестве поля выбираются конечные поля вида F и F.

Сложение точек эллиптической кривой.

Сначала заметим, что на некоторых плоских кривых существуют естественные законы сложения, такие, что относительно этой операции точки кривых образуют алгебраическую группу. Простейшими примерами таких кривых являются прямая и окружность [ПС97]. Например, суммой двух точек (r cos a, r sin a) и (r cos b, r sin b) , окружности x+y = r будем считать точку (r cos (a+b), r sin (a+b)).

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

Определим операцию сложения точек P и Q на кривой E отправляясь от графического изображения кривой [K87, БССШ03]. Проведем через точки P и Q прямую. В общем случае эта прямая пересечет кривую еще в третьей точке. Отразим эту точку относительно оси Ох и назовем полученную точку суммой P + Q точек P и Q. Не всегда прямая, проходящая через две точки, пересекает кривую Е в третьей точке, например, этого не происходит с вертикальной прямой. Этот случай рассмотрим далее подробно.

Заметим, что определить сумму P + Q точек P и Q можно не только таким образом, но именно такое определение наделяет множество точек эллиптической кривой структурой абелевой группы. Проиллюстрируем описание операции на рисунке.

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

Очевидно, что так определенная операция коммутативна, так как для вычисления Q+P используется та же самая прямая, что и для P+Q.

Займемся существованием нейтрального по сложению элемента - нуля. Это такая точка O на кривой, что Р+О = Р для любой точки Р кривой. Мы хотим найти нечто такое, что, если провести прямую через Р и это нечто, пересечь получившуюся прямую с кривой и потом отразить точку пересечения от оси Ох, то вновь получится точка Р. Обозначим через Р` точку, симметричную Р относительно оси Ох. Из сказанного вытекает, что прямая должна проходить через точки Р и Р`, то есть должна быть вертикальной. Следовательно, если имеется точка О, для которой Р+О = Р для всех Р, то эта точка должна лежать и на кривой и на любой вертикальной прямой. Разумеется в плоскости (xOy) такой точки нет. Поэтому добавим ее к плоскости и кривой и назовем ее бесконечно удаленной точкой или точкой в бесконечности. Каким требованиям она должна удовлетворять? Любая вертикальная прямая стремится к бесконечности сверху и снизу. Потребуем, чтобы все эти точки в бесконечности были одной и той же точкой О, то есть будем считать, что точка О есть точка пересечения всех вертикальных прямых. Для того, чтобы точно понять, что это значит, рассмотрим проективное дополнение аффинной плоскости и кривой на ней. Рассмотрим проективную плоскость Р(K) с однородными координатами (X:Y:Z), причем будем считать, что координаты на исходной аффинной плоскости имеют вид

x = X/Z, y = Y/Z.

Тогда уравнение, соответствующее эллиптической кривой

y = x + a x +b,

примет вид

Y Z = X + a X Z + b Z.

При ненулевой Z, мы видим, что y = x + a x +b выполняется тогда и только тогда, когда

(Y/Z) = (X/Z) + a (X/Z) + b.

Бесконечные точки нашей кривой - это классы точек (X : Y : 0), для которых выполнено соотношение

Y 0 = X + a X (0) + b 0 ,

то есть X=0. Существует только один такой класс эквивалентности (0 : 1 : 0). Это и есть искомая бесконечно удаленная точка О.

Требования, которые мы предъявили к точке О, корректно определяют ее как нулевую точку относительно операции сложения точек на эллиптической кривой. Действительно, в силу нашего соглашения, вертикальная прямая , проходящая через точку Р, проходит через Р и О. Поэтому точка Р` пересечения этой прямой с эллиптической кривой удовлетворяет соотношению Р + Р` = О, то есть является обратной по сложению к точке Р. В то же время, Р` - это точка, симметричная к Р относительно оси Ох. Значит, любая точка Р имеет обратную точку - Р = Р`.

Для вычисления точки 2Р = Р+Р нужно провести не секущую, а касательную в этой точке. Точки вида n P теперь находятся по индукции: 3Р= 2Р+Р, … .

Для того, чтобы окончательно убедиться, что точки эллиптической кривой относительно описанной операции сложения образуют абелеву группу, осталось проверить ассоциативность для этой операции, то есть выполнение равенства (P+Q)+S=P+(Q+S) для всех точек кривой Е(К), включая бесконечно удаленную точку О.

Геометрически доказать это трудно [ПС97], но можно показать с помощью приводимых ниже формул вычисления координат точки, являющейся суммой двух произвольных точек. При этом надо будет рассмотреть несколько случаев, в зависимости от того, P=Q или нет, и от того, S=(P+Q) или нет, что делает доказательство достаточно трудоемким (http://math.rice.edu/~friedl/papers/AAELLIPTIC.PDF ).

Формулы для вычисления координат суммы точек эллиптической кривой.

Пусть Р = (х, у), Q= (х, у), P+Q = (x, y). Уравнение прямой на аффинной плоскости, соединяющей точки Р и Q, имеет вид у=к х+d, где

k=(у - у)/(х - х), d = y - k x = (x y - x y)/(x - x).

Подставив у=к х+d в уравнение эллиптической кривой y = x + a x +b, получим уравнение третьей степени (к х+d ) = x+ a x +b, то есть

x- k x + (a - 2 kd) x + b - d= 0.

Мы знаем два его корня х1 и х2, так как точки (х, k x+ d) и (x, k x+d) лежат на кривой.

Отсюда по теореме Виета

x= k - x - x,

y= -k x - d (знак минус взят в силу определения операции сложения точек).

Подставляя в эти формулы значения k и d , получим

x = ((y-y) / (x-x)) - x - x,

y = -y1 + ((y - y)/(x - x)) (x - x).

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

Случай, когда Р = Q разбирается аналогично. В этом случае уравнение секущей

у = к х+d нужно заменить уравнением касательной и действовать по прежней схеме, здесь k есть значение производной в точке Р и равно k = ((3 x + a)/2 y) , и поэтому мы получаем координаты удвоенной точки Р вида

x = ((3x + a)/2 y) - 2x,

y = - y + ((3x + a)/2y)(x - x).

Ясно, что эти формулы верны для любого поля, характеристика которого отлична от 2 и 3. Для указанных случаев будут справедливы приводимые ниже формулы (см., например [БССШ03]).

Если а=а=0 в длинной форме Вейерштрасса, а а не обязательно нуль (случай, включающий char K = 3), то

x = ((y-y)/(x-x)) - a - x - x,

y = -y + ((y-y)/(x-x)) (x-x),

когда складываются различные точки и

x = (3x + 2 a x + a/2y) - a - 2x,

y = - y + (3x + 2 a x + a/2y) (x - x),

когда точка удваивается.

Если char K = 2 и в длинной форме Вейерштрасса a= a=0, a=1,то

x = ((y+y)/(x + x)) + (y+y)/(x+x) + x+x+a,

y = ((y+y)/(x + x)) (x+x) + x +y,

когда складываются различные точки и

x = x + a/x,

y = x + (x+ y/x) x + x

когда точка удваивается.

Если char K =2 и в длинной форме Вейерштрасса a=a=0, но a не равно 0, то

x = ((y+y)/(x + x)) = x + x,

y = (y+y)/(x + x) (x+x) + y + a,

когда складываются различные точки и

x = (x +a)/a,

y = (x+a/a)(x+x) + y + a,

когда точка удваивается.

Отметим еще раз важность рассмотрения именно гладких (или неособых) кривых. Уравнение неособой кубической кривой можно записать в виде

y= (x - e)(x - e)(x - e),

где числа e,e,e попарно различны. В качестве примера можно рассмотреть кривую, задаваемую уравнением

y = x - x = (x + 1)x(x - 1).



Пусть e<e<e. При слиянии корней e и e, получается кривая вида

y = x (x-1). При слиянии корней e и e получается кривая вида y = x (x+1).

При слиянии всех трех корней получается кривая вида y = x.

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

Форма Лежандра

Существуют и отличные от формы Вейерштрасса представления эллиптических кривых (наиболее часто используются также формы Лежандра, Монтгомери). Форма Лежандра для эллиптической кривой над алгебраически замкнутым полем позволяет выразить кривую с помощью всего одного параметра.

Если характеристика поля не равна 2, то уравнение задающее кривую можно представить в виде

y= x+a x +a x + a= (x - e)(x - e)(x - e),

где e, e, e принадлежат полю в силу его замкнутости. Сделаем замены

x = x (e - e) + e и y = y (e - e).

Получим

y (e - e) = x ( e - e) (x (e - e) - (e - e))(x (e - e) +e - e),

или при разных e и e получим

y = x (x - 1)(x -L), где L=(e - e)/(e - e).

Значение параметра L в представлении не однозначно и в зависимости от перестановки e, e, e в приведенных заменах может принимать одно из 6 значений

L, 1/L, 1 -L, 1/(1 - L), L/(1-L), (L-1)/L.

Уравнение неособой кубической кривой, как уже отмечалось, можно записать в виде

y= (x - e)(x - e)(x - e),

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

Рассмотрим следующее понятие

j-инвариант эллиптической кривой

Пусть уравнение y = x + a x + b определяет некоторую эллиптическую кривую над полем К, характеристики отличной от 2 или 3. Если положить

x = x/d и y = y/d,

при некотором обратимом d (из алгебраического замыкания поля К), то получим аналогичное соотношение в форме Вейерштрасса

y = x + a x+ b , где a = a (d), b = b (d).

Заметим, что если бы мы сделали такую замену в длинной форме Вейерштрасса, то новые коэффициенты имели бы вид a(d) , что объясняет нумерацию коэффициентов в этой форме.

Определим j-инвариант кривой как

j = 1728 (4a/( 4a + 27b)).

Знаменатель в этом выражении совпадает с дискриминантом многочлена [В76]

x + a x + b, взятым со знаком минус, поэтому не может быть нулевым в силу выбора коэффициентов a и b для гладкости кривой.

Оказывается, что проведенная замена не меняет j-инвариант.

Теорема.

Пусть y= x + a x + b и y= x+ a x + b , будут определять эллиптические кривые с j-инвариантами j и j соответственно. Если j = j, то существует d не равное 0 в алгебраическом замыкании поля К, такое что a = a (d) и b = b (d). Преобразование x = x (d), y = y (d) преобразует одно соотношение в другое.

Доказательство.

Сначала предположим, что a не равно 0. Это равносильно тому, что j=j не равен 0, поэтому и a не равно 0. Выберем d так, a = a (d), что возможно в силу замкнутости.

Тогда в силу равенства j=j получаем

4 a/(4a + 27 b) = 4 a/(4a+27b) = 4 d a/(4 d a+ 27 b) = 4 a/(4a+27d b),

что означает, что b = (b d).

Поэтому b = (b d). Если b = + b d, то все доказано. Если b = - bd, то заменим d на i d ( где i = - 1). Это дает a= a (d) и b = b d.

Если а равно 0, то и а = 0. Так как дискриминант не равен 0, то b и b не равны 0. Выбираем d таким, что b= b (d). Ч.т.д.

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

Наконец, заметим, что число j является j- инвариантом для кривой вида

Y = x + (3j/(1728 -j)) x + (2j/1728 - j),

если j не равен 0 или 1728. (Существуют 2 специальных значения j=0 и j=1728. В стандарте цифровой подписи ГОСТ 34.10-2001 кривые с такими инвариантами исключены) То есть, как коэффициенты эллиптической кривой определяют j-инвариант, так и j-инвариант определяет коэффициенты эллиптической кривой.

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

При построении криптосистем широко используются эллиптические кривые над конечными полями. В основном рассматривается простое поле F и поле F, но исследования ведутся и для произвольного конечного поля F, где q=p (p-простое число) [ГОСТ 34.10 - 2001(F), FIPS 186-?(Fи F)].

В силу конечности поля F число пар (x,y), удовлетворяющих уравнению

y = x + a x +b над этим полем тоже конечно, и группа точек эллиптической кривой является конечной абелевой группой.

Легко видеть, что порядок этой абелевой группы не может превышать число 2q+1. Если задать кривую в форме Вейерштрасса y = x + a x +b , то для каждого x из F число решений сравнения y = a (mod q) не может превышать двух, и 1 добавляет точка в бесконечности.

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

Напомним основную теорему о строении конечных абелевых групп [ГЕН03].

Теорема.

Любая конечная абелева группа либо является примарной циклической группой, либо раскладывается в прямую сумму примарных циклических подгрупп:

G = (g) + (g) + … +(g),

где порядки элементов ord g= p, где p, …, p - не обязательно различные простые числа.

При этом, приведенное разложение, в котором слагаемые упорядочены так, что

(p>=p) & ((p = p (k>=k), i = 1, …, (t -1),

называется каноническим разложением конечной абелевой группы, а вектор (p, …, p) - типом этого разложения.

Существование приведенного разложения равносильно тому, что существует изоморфизм:

G = Z p + … + Z p,

который также называется каноническим разложением группы G.

В [K87, 197с.] показано, что тип абелевой группы точек эллиптической кривой в форме y= x - x над полем F_71 равен (4,2,9).

Иногда теорему о разложении конечных абелевых групп формулируют в другом виде, когда разложение приводится в так называемой форме Смита [].

Теорема.

Любая конечная абелева группа изоморфна прямой сумме групп

Z + … + Z,

где n делит n для i=1, …, (s-1). Числа n однозначно определяются группой.

Эта форма записи и называется формой Смита. Форму Смита можно преобразовать в форму представления по степеням простых чисел и обратно. Для перехода к форме Смита надо выбрать наибольшие из степеней каждого простого числа и перемножить их, а затем повторить это пока ничего не останется. Для перехода от формы Смита надо просто разложить порядки циклических групп. Например, Z+Z+Z+Z изоморфна Z+Z. Это разные формы представления одной и той же группы.

Теорема.

Пусть E(F) -группа точек эллиптической кривой над конечным полем F.

Тогда она изоморфна или Z или прямой сумме Z+ Z, для некоторых целых n>=1, или n, n >=1 и n делит n.

Рассмотрим несколько примеров.

Пример.

Пусть Е(F_5) - группа точек эллиптической кривой, задаваемой уравнением

y = x + x + 1

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

x	X+x+1	y	Точки
0	1	+1, -1	(0,1), (0,4)
1	3	-	-
2	1	+1, -1	(2,1), (2,4)
3	1	+1, -1	(3,1), (3,4)
4	4	+2, -2	(4,2), (4,3)

Поэтому порядок группы равен 9 , группа является циклической с порождающим элементом (0, 1).

Доказательство

Из таблицы видно, что уравнению удовлетворяют 8 точек и, добавляя точку в бесконечности O, получаем ,что порядок группы равен 9.

Для доказательства цикличности воспользуемся критерием [ГЕН03]:

G-циклическая gG: ord g=

Рассмотрим элемент (0,1) и по формулам сложения точек эллиптической кривой докажем критерий:

1.(0,1)+O=(0,1) 6.(3,1)+(0,1)=(2,4)

2.(0,1)+(0,1)=(4,2) 7.(2,4)+(0,1)=(4,3)

3.(4,2)+(0,1)=(2,1) 8.(4,3)+(0,1)=(0,4)

4.(2,1)+(0,1)=(3,4) 9.(0,4)+(0,1)=O

5.(3,4)+(0,1)=(3,1).

Порядок элемента (0,1) равен 9 по определению (ord gG=nN :gn=e).

Пример.

Пусть Е(F) - группа точек эллиптической кривой, задаваемой уравнением

y = x + 2 над простым конечным полем F.

Для этого примера группа Е(F) содержит следующие элементы

Е(F) = {O, (0,3), (0,4), (3,1), (3,6), (5,1), (5,6), (6,1), (6,6)}

Все эти точки Р удовлетворяют соотношению 3Р = О, а группа Е(F) изоморфна прямой сумме Z + Z.

Доказательство

Первое утверждение проверяется непосредственной проверкой по формулам сложения точек эллиптической кривой.

Составим таблицу Кели для группы Е(F):

+	О	(0,3)	(0,4)	(3,1)	(3,6)	(5,1)	(5,6)	(6,1)	(6,6)
О	О	(0,3)	(0,4)	(3,1)	(3,6)	(5,1)	(5,6)	(6,1)	(6,6)
(0,3)	(0,3)	(0,4)	О	(6,1)	(5,6)	(3,1)	(6,6)	(5,1)	(3,6)
(0,4)	(0,4)	О	(0,3)	(5,1)	(6,6)	(6,1)	(3,6)	(3,1)	(5,6)
(3,1)	(3,1)	(6,1)	(5,1)	(3,6)	О	(6,6)	(0,3)	(5,6)	(0,4)
(3,6)	(3,6)	(5,6)	(6,6)	О	(3,1)	(0,4)	(6,1)	(0,3)	(5,1)
(5,1)	(5,1)	(3,1)	(6,1)	(6,6)	(0,4)	(5,6)	О	(3,6)	(0,3)
(5,6)	(5,6)	(6,6)	(3,6)	(0,3)	(6,1)	О	(5,1)	(0,4)	(3,1)
(6,1)	(6,1)	(5,1)	(3,1)	(5,6)	(0,3)	(3,6)	(0,4)	(6,6)	О
(6,6)	(6,6)	(3,6)	(5,6)	(0,4)	(5,1)	(0,3)	(3,1)	О	(6,1)

Представим группу Е(F) в виде прямой суммы двух подгрупп, воспользовавшись основной теоремой о строении конечной абелевой группы и теоремой о выделении прямого слагаемого в примарной абелевой группе получаем Е(F)=<g>+<f>(группа не циклическая т.к. ее порядок равен 9,а порядки всех элементов равны 3) , в частности из таблицы следует Е(F)=<(0,3)>+<(5,1)> ,т.к. порядки образующих элементов равны 3,то и порядки подгрупп <g> и <f> будут равны 3.

А по критерию об изоморфизме циклических групп(Две циклические группы изоморфныих порядки равны([ГЕН03] Т.1,с249)) каждая из подгрупп изоморфна Z,из чего следует:

Е(F)= Z + Z. ч.т.д.

Пример.

Пусть Е(F) - группа точек эллиптической кривой, задаваемой уравнением

y = x + x над простым конечным полем F.

Имеется 23 точки, удовлетворяющие этому уравнению над данным полем:

Е(F_23) = {O, (0,0),(1,5),(1,18),(9,5),(9,18),(11,10),(11,13),(13,5),(13,18),(15,3),(15,20),

(16,8),(16,15),(17,10) (17,13),(18,10),(18,13),(19,1),(19,22),(20,4),(20,19),(21,6),(21,17)}

Графически точки кривой можно изобразить следующим образом:



На рисунке видна симметрия точек.

Во многих приложениях, на основе аппарата эллиптических кривых, используются кривые над F₂^m поскольку в этом случае точки на кривой и её коэффициенты представимы в виде двоичных векторов. Однако, в отечественном стандарте на цифровую подпись на основе эллиптических кривых [ГОСТ 34.10-2001], кривые над такими полями вообще не используются, а используются только кривые над конечным простым полем Fпри p > 2.

При перечислении точек кривой в форме Вейерштрасса y = x+a x +b над конечным полем F мы перебирали все возможные значения x, а затем находили y как квадратные корни из (x+ax +b), если они существуют. Рассмотрим вопрос существования и нахождения решений сравнения y = a (mod p) подробнее.

Далее потребуется

Определение [Г05].

Целое число a, взаимно простое с простым числом p, называется квадратичным вычетом по модулю p, если сравнение y = a (mod p) имеет решение, и квадратичным невычетом по модулю p в противном случае.

Известно, что среди чисел 1, … ,(p - 1) содержится (p-1)/2 квадратичных вычетов и (p-1)/2 квадратичных невычетов по модулю p. Кроме того, справедлива

Теорема (критерий Эйлера).

Целое число a, взаимно простое с p, является квадратичным вычетом или невычетом по простому модулю p>2 в том и только том случае, когда соответственно выполняется условие

a) a = 1 (mod p) или b) a = - 1 (mod p).

При этом в случае а) сравнение y = a (mod p) имеет точно 2 решения.

Нахождение самих решений сравнения y = a (mod p) , в случае его разрешимости, достаточно просто при р=3 (mod 4) и р=5 (mod 8). Есть и вероятностные методы нахождения решений [К87, Г05, 257с.].

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

Символ Лежандра (обозначается как (a/p), а - числитель, p - знаменатель символа) для нечетных простых чисел p определяется как 1, если a - квадратичный вычет по модулю p, и как - 1, если a квадратичный невычет. С использованием этого понятия критерий Эйлера можно переформулировать так. Целое число a является квадратичным вычетом по нечетному простому модулю p тогда и только тогда, когда (a/p)=a(mod p).

В работе [R87] вводится понятие квадратичного характера , обобщающего символ Лежандра. Это отображение, переводящее элемент конечного поля F в 1 или - 1, в зависимости от того, является или нет этот элемент квадратом некоторого элемента из этого поля. В случае когда q=p, где p простое число, (а) = (a/p) - символу Лежандра. В любом случае число решений уравнения y = a над F равно 1+(а). Тогда число точек N эллиптической кривой E(F) равно величине

N = 1+ (1+ (x+ax+b)) = q + 1 +( (x+ax+b)),

где суммирование берется по всем x из F.

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

Теорема (Hasse).

Число точек N эллиптической кривой над полем F (q=p), удовлетворяет неравенству

N- (q+1) < 2 .

Если обозначить через N(a,b,p) - число точек эллиптической кривой в форме Вейерштрасса над полем F , равное (p+1-t) при некотором t, то для числа N(a,b, p) - числа точек кривой с теми же коэффициентами a,b , но над полем F, то его можно найти [В03, 109 с.] из соотношения

N(a,b, p) = p+ 1 - t, где t удовлетворяет рекуррентному соотношению 2-го порядка

t_(j+1) = (t)(t) - p (t), j>=1, t = t, t = 2.

Поэтому важно уметь находить число точек кривой над конечным простым полем. Это имеет важное значение как в криптографии [ГОСТ 34.10-2001], так и в алгоритмах проверки простоты чисел [B03, 123 c.].

На практике часто необходимо знать не оценку, а точное число точек эллиптической кривой. Для подсчета этого числа к настоящему времени разработано несколько алгоритмов, а их реализацию можно найти в Интерненте (например, на странице http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html ).

Сначала Шуф (Schoof) в 1985 году предложил полиномиальный алгоритм для подсчета числа точек эллиптической кривой для нечетных q. Вскоре Коблиц (Koblitz) распространил его на случай поля F [В03]. Алгоритм Шуфа эффективен для небольших значений q<100. Далее методы подсчета числа точек кривых были усовершенствованы Аткиным, Элкисом, Мюллером и другими для больших значений q.

В отечественном стандарте [ГОСТ 34.10 - 2001] требуется, чтобы порядок группы точек эллиптической кривой делился на большое простое число q из интервала 2< q <2. В стандарте [FIPS 186-2] используются кривые, порядок которых имеет вид q f, где f равен 1,2 или 4, а q также большое простое число.

Порядки точек эллиптических кривых

Пусть Р - точка из группы E(F) точек эллиптической кривой. Порядком точки Р называется наименьшее положительное целое число k, такое что kP = (P+ … +P) = O (суммирем k точек Р).

По теореме Лагранжа порядок точки всегда делит порядок группы E(F) = N.

Даже если порядок группы неизвестен, то в силу теоремы Хассе для него верно соотношение q+1 - 2q < N < q+1 + 2q и можно попробовать искать в этом интервале. Размер его 4 q. Есть алгоритмы позволяющие сократить число проб до

4 q (см. например, [W03, 103 c., Baby Step-Giant Step]).

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

Дискретное логарифмирование в группе точек эллиптической кривой

Задача логарифмирования может быть поставлена для любой группы (G,*) с операцией *, в том числе и для группы точек эллиптической кривой. В общем случае в задаче требуется найти целое число х по элементам а и b = а, где а обозначает (a*a*…*a), то есть результат многократного применение операции * к элементу а из группы G. Ясно, задача имеет решение, если в принадлежит подгруппе G, порожденной элементом а.

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

ax = b(mod m), и не представляет трудности. Гораздо сложнее решение этой задачи в мультипликативной группе кольца Z, где р - большое простое число[В03]. В настоящее время размер этого простого числа должен составлять порядка 1000 бит, чтобы эта задача была трудно решаема и ее можно было использовать при построении стойких криптосистем. Но ввиду больших размеров используемых чисел, реализация таких систем требует больших объемов машинной памяти.

В случае группы точек эллиптической кривой (Е(F), +) с введенной операцией сложения точек, задача принимает вид нахождения целого числа х из соотношения х P = Q для точек P и Q эллиптической кривой. Временная сложность наилучшего из всех известных алгоритмов решения этой задачи имеет порядок О( p). С такой сложностью решать задачу дискретного логарифма можно в любой группе [В03], и до сих пор не удалось существенно использовать специфику самой группы точек кривой.

Поэтому использование группы точек эллиптической кривой при построении криптосистем позволило уменьшить параметры криптосистем при сохранении их стойкости.

Цифровые подписи

ECDSA: Elliptic Curve Digital Signature Algorithm

Алгоритм Цифровой Подписи на основе Эллиптической Кривой (ECDSA) является аналогом Алгоритма Цифровой Подписи (DSA), но для другой группы. Вместо мультипликативной группы Z_p используется группа точек эллиптической кривой над конечным полем. Схема описана в ряде стандартов - ANSI X9.62, FIPS 186-2, IEEE 1363-2000 и ИСО/IEC 15946-2 .

В последующем, обозначим хеш-функцию - R, и она имеет не более n значений.

Генерация подписи ECDSA.

ВХОД: Параметры подписи D = (q, FR, S, a, b, P, n, h), секретный ключ d, сообщение m.

ВЫХОД: Подпись (r, s).

1. Выбор* e_R[l,n-1].

2. Вычислить kP = (x1, y1) и преобразовать x1 в целое x_i.

3. Вычислить r =x_i mod n. Если r = 0, тогда шаг 1.

4. Вычислить e = H(m).

5. Вычислить s = k^~l (e + dr) mod n. Если s = 0, тогда шаг 1.

6. Возврат(r, s).

Проверка подписи ECDSA.

ВХОД: Параметры подписи D = (<7,FR, S,a,b, P,n,h), открытый ключ Q, сообщение m, подпись (r, s).

ВЫХОД: Принятие или отказ подписи.

1. Проверить, что r и s - целые в интервале [1, n - 1]. Если они не удовлетворяют этому условию, тогда возврат ("признание не корректности подписи").

2. Вычислить e = H(m).

3. Вычислить w = s"1 mod n.

4. Вычислить u1 = ew mod n и u2 = rw mod n.

5. Вычислить X = u1P + M2<2

6. Если X = oo, тогда возврат ("признание не корректности подписи ");

7. Преобразовать x-координату x1 из X в целое x1; вычислить v = x1 mod n.

8. Если v = r, тогда возврат (“Принятие подписи");

Иначе возврат ("признание не корректности подписи ").

Доказательство того, что проверка подписи верна.

Если подпись (r, s) в сообщении в на самом деле была сгенерирована законным владельцем, тогда s = k^(- l) (e + dr) (mod n). Перестроенное дает

k = s^(- l) (e + dr) = s^(- l) e + s^(- l) rd = we + wrd = u1 +u2d (mod n).

Таким образом, X = u1P + u2Q = (M1 + u2d)P = kP, и так v = r как и требовалось.

ECNR: Elliptic Curve Nyberg Rueppel

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

Пространством сообщений здесь является M = Z*_p где р - простое, в качестве пространства Ms подготовленных к подписанию сообщений используется декартово произведение Ms = Zp x Zq, где q - простое число, являющееся делителем (р - 1). Пусть R - функция избыточности из пространства сообщений M в пространство подписанных сообщений Ms. Например, значение R(m) может иметь вид (m, m(mod q). Через R^-l обозначается функция из образа функции R в её область определения: R^-1 : Im(R) ->M, например, R^-1(m,m(mod q) = m.

Алгоритм генерации ключа тот же, что и в алгоритме DSA, с тем отличием, что на различие размеров р и q не накладывается ограничений (то есть q может быть того же порядка, что и р).

Алгоритм генерации подписи на сообщении т следующий:

а) Вычислить m* = R(m),

б) Выбрать случайное секретное целое число к,1 < к < q- 1, и

вычислить r = а^~к (modp).

в) Вычислить е = m*r (mod p).

г) Вычислить s = (ае + к) (mod q).

д) Объявить пару (е, s) как подпись на сообщении m.

Алгоритм верификации подписи следующий:

а) Получить авторизированную копию открытого ключа подписавшего.

б) Проверить, что 0<e<p и 0<s<p, если нет, то отклонить подпись.

г) Вычислить v = a^sy^~e (mod р) и m* = ve (mod p).

д) Проверить, что m* Mr, если нет, то отклонить подпись.

е) Извлечь (восстановить) сообщение m = R^~l(m).

Доказательство корректности алгоритма весьма коротко:

По алгоритму генерации подписи

v = а^sу^~е = a^s~ae = a^k(mod p).

Таким образом,

ve = a^km*a^-k = m*(mod p),

что и требуется.

Схема Нуберга-Рюппеля ( Nyberg-Rueppel ) цифровой подписи с использованием группы точек эллиптической кривой.

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

Q = sP.

Предполагается, что порядок точки Р равен n.

Алгоритм генерации подписи следующий:

1) Образовать случайную битовую строку к и вычислить R = kP.

2) Используя первую х - компоненту точки R как целое число, вычислить

с = х + е (mod n), (*)

d = к - sc(mod n). (**)

Пара (c,d) является подписью для документа m, такого, что h(m) = e.

Для проверки, что h(m) является корректным хеш-значением, выполняется следующий алгоритм:

1) Вычислить

R' = dP + cQ. (***)

2) используя первую х-компоненту R', вычислить

е' =с-х'{ mod n). (****)

3) если полученное значение совпадает с хеш-значением h(m),

то последнее удостоверяется.

Рассмотрим эту схему более подробно.

Точка Р умножается на случайное число к, и получается точка R, x-компонента этой точки R также является случайным числом. Прибавление этой точки к хеш-значению е = h(m) по модулю n (порядка точки Р) эффективно маскирует это хеш-значение.

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

При вычислении R соединяются случайные данные с секретным ключом, так же с использованием модульной арифметики. Поскольку модуль равен порядку точки эллиптической кривой, то же самое можно делать с точками эллиптической кривой.

Действительно, вместо вычисления с по * вычислим

...