Способ электронной цифровой подписи на основе эллиптической кривой

Способ электронной цифровой подписи на основе эллиптической кривой

Реферат

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

Известны системы электронной цифровой подписи (ЭЦП) на эллиптических кривых, в которых обрабатываемые данные представлены точками эллиптической кривой в форме Вейерштрасса (ЭКВ), заданной уравнением y²≡х³+ах+b (mod p) для большого простого числа р [ГОСТ Р 34.10-2001. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. Госстандарт России, М., 2001]; [ANSI X9.62. Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), 2005, доступно с http://www.comms.scitech.susx.ac.uk/fft/crypto/ecdsa.pdf], также см. Приложение 1.

В известных системах ЭЦП обрабатываемые данные представлены битовой строкой или набором битовых строк. Под битовой строкой (БС) понимается электромагнитный сигнал в цифровой двоичной форме, параметром которого является число битов и порядок следования нулевых и единичных значений. Битовые строки допускают операцию конкатенации, логические и арифметические операции. Формирование и проверка ЭЦП заключается в выполнении действий с БС (преобразованиях БС и выполнении операций с БС) и выполняется с помощью вычислительных устройств, например персональных компьютеров или смарт-карт [доступно с http://www.aloaha.com/press_en/elliptic-curves-and-sha-256-support.php].

В соответствии с Федеральным законом об электронной цифровой подписи юридическая значимость ЭЦП на территории РФ обеспечивается только при реализации ее в соответствии с ГОСТ Р 34.10-2001. Поэтому практически наиболее интересны способы ЭЦП, реализованные в соответствии с действующими стандартами.

Процессы формирования и проверки подписи предусматривают выполнение операций сложения точек, представленных БС, и нахождение БС, представляющей значение х-координаты результирующей точки, и реализуются в вычислительном устройстве, например в процессоре персонального компьютера. В качестве не зависящей от типа вычислительного устройства меры длительности криптографической обработки данных удобно использовать число операций модульного умножения. Для ускорения операций удвоения и сложения точек координаты точек представляются в проективной форме. В этом случае удвоение точки ЭКВ требует выполнения 13 операций модульного умножения, а сложение двух различных точек ЭКВ требует выполнения 15 операций модульного умножения. Если одна из складываемых точек имеет единичную третью координату, то для сложения точек требуется 12 операций модульного умножения [Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - «Профессионал», СПб., 2005, с.171, 172].

Стандарты подписи [ГОСТ Р 34.10-2001. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. Госстандарт России, М., 2001]; [ANSI X9.62. Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), 2005, доступно с http://www.comms.scitech.susx.ac.uk/fft/crypto/ecdsa.pdf] аналогичны и по сути различаются размером задачи: длина цикла {Р,2P,3P, …}, образованного точкой Р, является простым числом q, длина которого в первом случае не менее 254 бит, а во втором случае не менее 160 бит. Поэтому достаточно рассмотреть только операции с точками эллиптической кривой, предусмотренные в ГОСТ Р 34.10-2001.

Известные системы ЭЦП предусматривают этап генерации параметров системы ЭЦП и открытого ключа (далее для краткости этап генерации параметров системы ЭЦП). Параметрами системы ЭЦП являются: простое число р длиной не менее 256 бит, коэффициенты a, b ЭКВ, число точек ЭКВ, простое число q>2²⁵⁴, являющееся делителем числа точек, и точка Р порядка q. При этом число q является делителем числа точек ЭКВ. Конфиденциальным ключом создания подписи является натуральное число d, 1≤d≤q-1. Открытым ключом проверки ЭЦП является точка Q=dP. Параметры системы ЭЦП, открытый и конфиденциальный ключ представлены БС.

Для формирования подписи вырабатывается случайное число k, 0<k<q, и вычисляется точка kP путем сложений и удвоений точки Р. Значение r как х-координата точки kP по модулю q является частью ЭЦП.

Для проверки подписи вычисляется точка z₁P+z₂Q по известным z₁, z₂, и ее х-координата по модулю q сравнивается с r. При совпадении х-координаты точки z₁P+z₂Q (mod q) и r делают вывод о подлинности ЭЦП.

Однократное вскрытие числа k ведет к вычислению конфиденциального ключа [Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - «Профессионал», СПб., 2005]. На практике умножение точки Р на число k выполняют методом удвоений и сложений. Поскольку операции сложения и удвоения выполняются по разным формулам, они могут быть распознаны в реальном масштабе времени путем анализа мгновенной потребляемой мощности. Такая скрытая атака возможна, если подпись формируется в смарт-карте, которая получает электропитание от внешнего терминала.

Аналогом заявленного способа является патент РФ 2232476, МПК H04L 9/30, опубл. 7.10.04, позволяющий сократить суммарную длину коэффициентов ЭКВ за счет преобразования уравнения ЭКВ и координат точки. Недостатком этого способа является то, что он практически не увеличивает скорость обработки данных.

Известны способ и устройство, реализующее ЭЦП на основе эллиптической кривой в форме Гессе (ЭКГ), заданной уравнением

U³+V³+W³≡3mUVW(mod p), m³≠1(mod p)

[патент FR 2624653, МПК G06F 17/10, опубл. 15.11.02], см. также статью [Joye M., Quisquater J.-J. Hessian elliptic curves and side channel attacks // Cryptographic hardware and embedded systems (CHES 2001), Lecture Notes in Computer Science, v.2162, 2001, pp.402-410, доступно с http://www.gemplus.com/smart/rd/publications/pdf/JQ01hess.pdf]. Данное устройство реализует более быстрый способ, чем в указанном аналоге (удвоение точки ЭКГ требует 9 операций модульного умножения, а сложение точек ЭКГ требует 12 операций модульного умножения и 10 операций модульного умножения, если одна из складываемых точек имеет единичную координату, см. также Приложение 1). Недостатком этого технического решения является невозможность применения его при реализации стандартов электронной цифровой подписи ГОСТ Р 34.10-2001 и FIPS 186-3 (ECDSA), предусматривающих использование ЭКВ.

Известен способ, позволяющий преобразовывать данные, представленные точкой ЭКВ, в данные, представленные точкой ЭКГ, и обратно [Joye M., Quisquater J.-J. Hessian elliptic curves and side channel attacks // Cryptographic hardware and embedded systems (CHES 2001), Lecture Notes in Computer Science, v.2162, 2001, pp.402-410, доступно с http://www.gemplus.com/smart/rd/publications/pdf/JQ01hess.pdf], см. также Приложение 1. Недостатком данного способа является то, что преобразование точки ЭКВ в точку ЭКГ занимает сравнительно много времени, поскольку задается нелинейными выражениями. Кроме того, это преобразование определено не для всех точек, так как знаменатель этого преобразования иногда может обращаться в 0 (см. Приложение 1).

За прототип выбран способ криптографической обработки данных, представленных в виде битовой строки БС, заключающийся в удвоении и сложении точки ЭКВ, в котором точка задана тремя проективными координатами (X,Y,Z), хотя бы одна из координат ненулевая, причем (X,Y,Z)=(сХ,cY,cZ) для любого ненулевого параметра с, а обработка данных ведется с использованием проективных координат (US 20080205638, H04L 9/30, опубл. 28.08.08). Недостатком прототипа является низкая скорость обработки данных, обусловленная тем, что сложение и удвоение точек выполняют на ЭКВ. Кроме того, если процесс формирования ЭЦП в соответствии с прототипом выполняется смарт-картой, которая получает электропитание от внешнего терминала, то конфиденциальный ключ может быть вскрыт атакой по внешнему каналу (см. Приложение 1).

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

Решение задачи обеспечивается тем, что выполняют линейное преобразование координат (X,Y,Z) точки ЭКВ в координаты (U,V,W) точки ЭКГ с параметром m (см. формулы (II)), предусмотренные ГОСТ Р 34.10-2001, и ECDSA, операции сложения и удвоения точек выполняют на ЭКГ, после чего выполняют обратное линейное преобразование трех проективных координат точки (U,V,W) ЭКГ в две проективных координаты (X,Z) точки ЭКВ (см. формулы (II).

Для вычисления указанного линейного преобразования проективных координат точки ЭКВ в проективные координаты точку ЭКГ и обратного линейного преобразования находят БС, представляющие параметры u, m такие, что выполняются условия

u⁴ a≡-3^-1m(8+m³)(mod p), u⁶b≡27^-12(-8-20m³+m⁶)(mod p).

При генерации параметров системы ЭЦП выбирают p≡5 (mod 6), а число точек эллиптической кривой выбирают кратным 3, либо выбирают р≡1 (mod 6), а число точек эллиптической кривой выбирают кратным 9.

Увеличение скорости криптографической обработки данных связано с тем, что сложение и умножение точек ЭКГ выполняется быстрее, чем на ЭКВ, а предложенное линейное преобразование точки ЭКВ в точку ЭКГ и обратно практически не снижает скорость обработки данных.

Существенные признаки заявленного способа:

1. Способ электронной цифровой подписи на ЭКВ, заданной уравнением Y²Z=X³+aXZ²+bZ³(mod p), в котором генерируют параметры (р,а,b,Р,Q) системы ЭЦП, где Р - точка большого простого порядка q и Q=dP для конфиденциального ключа d, a также формируют и проверяют ЭЦП, причем при формировании и проверке ЭЦП находят результирующую точку путем удвоений и сложений точек эллиптической кривой, заданных проективными координатами (X,Y,Z). По проективным координатам (X,Y,Z) результирующей точки находят БС, представляющую значение XZ^-1(mod p) координат результирующей точки.

2. Выполняют линейное преобразование координат (X,Y,Z) точки ЭКВ в координаты (U,V,W) точки ЭКГ, заданной уравнением U³+V³+W³=3mUVW(mod p), операции удвоения и сложения точек выполняют на ЭКГ.

3. Выполняют операции сложения и удвоения точек на ЭКГ.

4. Выполняют линейное преобразование координат (U,V,W) результирующей точки ЭКГ в координаты (X,Z) точки ЭКВ.

5. Находят два параметра (u,m) линейного преобразования, для которых выполняются условия

6. Линейное преобразование координат (X,Y,Z) в координаты (U,V,W) выполняют по формулам

U≡u²mX+u³Y+3^-1(4-m³)Z(mod p),

V≡u²mX-u³Y+3^-1(4-m³)Z(mod p),

W≡-2(u²X+m²Z)(mod p).

7. Линейное преобразование координат (U,V,W) в координаты (X,Z) выполняют по формулам

Х≡m²(U+V)+3^-1(4-m³)W(mod p),

Z≡-u²(U+V+mW)(mod p).

8. При генерации параметров системы ЭЦП выбирают р≡5 (mod 6), а число точек ЭКВ выбирают кратным 3.

9. При генерации параметров системы ЭЦП выбирают р≡1 (mod 6), а число точек ЭКВ выбирают кратным 9.

10. При генерации параметров системы подписи для каждой из точек Р, Q находят координаты (U,V,W), затем заменяют ее координаты на (1, VU^-1(mod p), WU^-1(mod p)) при U≠0, или на (UV^-1(mod p), 1, WV^-1 (mod p)) при V≠0, или на (UW^-1(mod p), VW^-1(mod p), 1) при W≠0.

Признаки по п.1 - общие с прототипом. Признаки 2, 3, 4, 5 являются отличительными признаками, общими для всех вариантов исполнения заявленного способа. Признаки 6, 7, 8, 9, 10 могут варьироваться для вариантов исполнения. Так, линейное преобразование ЭКВ в ЭКГ и обратно по пп.6, 7 дает одинаковый результат при умножении всех элементов матрицы, задающей преобразование, на произвольный ненулевой элемент поля. При генерации параметров системы ЭЦП может использоваться любой из признаков 8 или 9. Признак по п.10 не является обязательным.

Указанная совокупность отличительных признаков позволяет решить задачу - повышение скорости формирования и проверки ЭЦП и повышение защищенности системы ЭЦП от атак по внешнему каналу.

Основой заявленного способа является обратимое линейное преобразование точки ЭКВ в точку ЭКГ. На этапе генерации по известным параметрам а, b ЭКВ и простому числу р, которые являются параметрами криптосистемы по ГОСТ Р 34.10-2001, ECDSA, с учетом эквивалентности ЭКВ находят параметры линейного преобразования (u, m) решением двух уравнений

Параметры u, m могут быть найдены на персональном компьютере с использованием пакета MATHEMATICA на этапе генерации параметров системы ЭЦП. Линейное преобразование координат точки ЭКВ в координаты точки ЭКГ задается выражениями

Это линейное преобразование можно также определить как умножение матрицы на вектор:

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

Обратное линейное преобразование координат (для формирования и проверки ЭЦП достаточно вычислить только координаты X, Z) задается выражениями

Это линейное преобразование можно также определить как умножение матрицы на вектор:

Указанные линейные преобразования ЭКВ в ЭКГ и обратно переводят сумму точек ЭКВ в сумму соответствующих точек ЭКГ и наоборот, а также переводят нулевой элемент для сложения точек в нулевой элемент.

При формировании подписи по ГОСТ Р 34.10-2001 ECDSA нужно найти БС, представляющую значение r как х-координату точки kP на ЭКВ, вычисленную по модулю q. Для формирования подписи по заявленному способу выполняют следующие преобразования БС.

1. Точку Р=(X,Y,Z) на ЭКВ преобразуют в точку Р'=(U,V,W) на ЭКГ. Это может быть сделано при генерации параметров системы ЭЦП. Благодаря равенству (U,V,W)=(cU,cV,cW) для любого с≠0, хотя бы одна из координат точки Р' может равняться 1.

2. Находят три координаты точки kP' на ЭКГ методом сложений и удвоений.

3. Выполняют обратное линейное преобразование и по трем координатам полученной точки kP' на ЭКГ находят две координаты (X,Z) соответствующей точки на ЭКВ, вычисляют х=XZ^-1(mod p), r≡х(mod q).

4. Вычисляют оставшиеся параметры цифровой подписи известным способом.

Умножение точки Р' на число k выполняется известным способом. Например, число k записывают в двоичном виде k=k₀+2k₁+…+2ⁿk_n, k_n=1. Полагают T_n=Р'. Для i от n-1 до 0 полагают T_i=2T_i+1+k_iP'. Результат: Т₀.

Проверка подписи (r, s) для значения хэш-функции е по ГОСТ Р 34.10-2001 требует проверки условий 0<r, s<q, нахождения значений z₁≡se^-1(mod q), z₂≡-re^-1(mod q), нахождения точки z₁P+z₂Q, вычисления ее х-координаты и сравнения х (mod q) с r. При совпадении подпись верна.

Проверка подписи (r, s) для значения хэш-функции е по ECDSA требует проверки условий 0<r, s<q, нахождения значений z₁≡es^-1(mod q), z₂≡rs^-1(mod q), нахождения точки z₁P+z₂Q, вычисления ее х-координаты и сравнения х (mod q) с r. При совпадении подпись верна.

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

1. Точки P, Q на ЭКВ преобразуют в точки Р', Q' на ЭКГ. Это может быть сделано на этапе генерации параметров системы ЭЦП. Благодаря равенству (U,V,W)=(cU,cV,cW) для любого с≠0, хотя бы одна из координат каждой из точек Р', Q' может равняться 1. Это преобразование координат может быть выполнено при генерации параметров системы ЭЦП.

2. Находят значения z₁, z₂ по соответствующему стандарту подписи.

3. Находят точку z₁P'+z₂Q' на ЭКГ методом сложений и удвоений.

4. Выполняют обратное линейное преобразование и по трем координатам полученной точки на ЭКГ находят две координаты (X,Z) соответствующей точки на ЭКВ, вычисляют значение x=XZ^-1(mod p), проверяют условие r≡х(mod q). При совпадении подпись верна.

Наиболее трудоемкой операцией при формировании и проверке подписи является операция умножения точки на число, которая выполняется путем сложений и удвоений точек. Удвоение точки на ЭКГ выполняется в раза быстрее чем на ЭКВ, а сложение двух точек, если у одной из них третья координата (Z или W) единичная, выполняется в 1,2 раза быстрее, при этом число удвоений примерно в два раза больше, чем число сложений. Поэтому в среднем умножение точки на число заявленным способом выполняется в 1,35 раза быстрее, чем в прототипе. Поскольку сложение точек ЭКГ описывается симметрическими функциями, можно сделать единичной любую из ненулевых координат одного из слагаемых.

Заявленный способ корректен, если система (I) имеет решение по модулю р. Предлагается два варианта выбора параметров криптосистемы. Первый вариант: выбрать р≡5 (mod 6), а число точек ЭКВ, задаваемое параметрами а, b, выбирать кратным 3 так, чтобы при этом выполнялись требования, предписанные стандартами подписи ГОСТ Р 34.10-2001 и ECDSA. Второй вариант: выбрать р≡1(mod 6), а число точек ЭКВ, задаваемое параметрами а, b, выбирать кратным 9 так, чтобы при этом выполнялись требования, предписанные стандартами подписи ГОСТ Р 34.10-2001 и ECDSA. Оба варианта выбора эллиптических кривых допускаются указанными стандартами.

Предложенный способ позволяет повысить защищенность системы ЭЦП от атак по внешнему каналу (см. Приложение 1). Известно, что однократное вскрытие случайного числа k при формировании подписи ведет к вскрытию конфиденциального ключа формирования подписи [Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография, СПб, НПО «Профессионал», 2005, доступно с http://progbook.net/seti/kriptograf/1568-teoreticheskaya_kriptografiya.html]. На практике вычисление точки kP при формировании подписи выполняется методом удвоений и сложений в соответствии с двоичным кодом k. Анализ мгновенной потребляемой мощности (например, если ЭЦП формируется смарт-картой, которая получает электропитание от терминала, контролируемого нарушителем) позволяет скрытно получить двоичные цифры числа k и, следовательно, получить конфиденциальный ключ [Zhou Y., Feng D. Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing // Cryptology e-print archive, technical report 205-388, http://eprint.iacr.org/2005/388.pdf]. Известно, что использование ЭКГ позволяет заменить удвоение точки сложением двух точек [Joye М., Quisquater J.-J. Hessian elliptic curves and side channel attacks // Cryptographic hardware and embedded systems (CHES 2001), Lecture Notes in Computer Science, v.2162, 2001, pp.402-410], см. также Приложение 1. Это позволяет сделать операции сложения и удвоения точек практически неразличимыми при анализе потребляемой мощности и за счет этого повысить защищенность системы ЭЦП к атакам по внешнему каналу.

Рассмотрим примеры реализации заявленного способа для поля небольшого размера.

Пример 1. Выбор эллиптической кривой и расчет параметров линейного преобразования. Для p=83 (случай р≡5(mod 6)) возможны лишь ЭКВ, для которых число точек N, кратное 3, равно 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102. Для каждой из эллиптических кривых с указанным числом точек существует эквивалентная ЭКГ, связанная с исходной ЭКВ с помощью параметров (m,u), как показано в таблице 1. Каждая пара (m,u) задает линейную эквивалентность между ЭКВ и ЭКГ с указанным числом точек N.

Таблица 1Параметры линейно эквивалентных эллиптических кривых в форме Вейерштрасса и Гессе
N	66	69	72	75	78	81	84	87	90	93	96	99	102
а	5	1	1	1	1	3	1	1	1	1	1	4	6
b	16	21	6	20	3	3	27	32	1	17	13	2	6
m	30	73	19	7	61	54	40	59	26	23	49	46	24
u	±33	±28	±1	±19	±37	±10	±16	±36	±37	±26	±6	±2	±19

Для р=71 (случай p≡1 (mod 6)) возможны лишь ЭКВ, для которых число точек N, кратное 3, равно 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90. Эквивалентная ЭКГ над полем из р элементов, связанная с исходной ЭКВ уравнениями (I), существует лишь для N=63, 72, 75, 81, 90 (это числа, кратные 9).

Пример 2. Формирование подписи по ГОСТ Р 34.10-2001. Параметры криптосистемы: р=83, число точек N=93, q=N/3=31. Уравнение ЭКВ (см. пример 1):

Y²Z=X³+XZ²+17Z³(mod p).

Точка порядка q на ЭКВ: Р=(0,10,1). Пусть k=9.

Известный способ умножения точки на число дает на ЭКВ точку 9Р=(29,45,1). Получаем r=29.

Предложенный способ. Линейное преобразование точки Р на ЭКГ по формулам (II) дает точку Р'=(34,19,21)=(53,76,1)=(28,1,71)=(1,3,47), единичные значения координат получены с учетом проективной эквивалентности. Для k=9 находим 9Р'=(37,38,10). Обратное линейное преобразование трех координат (U,V,W) точки 9Р' в две координаты точки 9Р ЭКВ по формулам (III) дает X=36, Z=27, XZ^-1=29 (mod 83), то есть r=29, как и в известном способе. На вычисление параметра s подписи заявленный способ не влияет.

Пусть значение хэш-функции для подписываемого сообщения е=10, конфиденциальный ключ проверки подписи d=19. Второй параметр подписи определяется так: s≡(rd+ke)(mod q), s=21. Подпись равна (r,s)=(29,21).

Пример 3. Проверка подписи по ГОСТ Р 34.10-2001. Параметры криптосистемы те же, что в примере 2. Открытый ключ проверки подписи (точка на ЭКВ) равен Q=dP=(73,70,1). Подпись равна (r,s)=(29,21), е=10. Условия 0<r, s>q выполнены.

Находим z₁≡se^-1(mod q)=30, z₂≡-re^-1(mod q)=25.

Проверка подписи известным способом на ЭКВ дает: z₁P=(0,73,1), z₂Q=(22,35,1). Точка z₁P+z₂Q имеет х-координату 29, что совпадает с r (mod q). Подпись верна.

Предложенный способ. Линейное преобразование точек Р, Q на ЭКГ по формулам (II) имеет вид Р'=(34,19,21)=(53,76,1)=(28,1,71)=(1,3,47), Q=(58,36,12)=(74,3,1)=(80,1,28)=(1,55,46). Находим на ЭКГ z₁P'=(19,34,21), z₂Q'=(45,34,74), R'=z₁P'+z₂Q'=(73,66,13). Обратное линейное преобразование трех координат точки R' ЭКГ в две координаты точки R ЭКВ по формулам (III) дает значения: Х=80, Z=60, XZ^-1=29(mod 83), что совпадает с r (mod q). Подпись верна.

Таким образом, предлагаемый способ обеспечивает возможность ускорения формирования и проверки электронной цифровой подписи во вновь разрабатываемых и существующих системах ЭЦП, в том числе построенных на основе ESDSA, ГОСТ Р 34.10-2001, а также повысить защищенность от атак по внешнему каналу.

Приложение 1

Объяснение терминов, используемых в описании и формуле изобретения.

Запись а≡b(mod p) означает, что а-b делится на р.

Конечное поле F_p из простого числа p элементов - множество {0, 1, …, р-1}. Сложение и умножение в конечном поле выполняются по модулю р и обозначается а+b (mod p), ab (mod p) (см. [Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра. - М.: Гелиос-АРВ, 2003]), например 3+4≡0(mod 7), 3·4≡5 (mod 7). Для любого ненулевого элемента а существует обратный элемент a ^-1 такой, что aa ^-1=1. Элемент а ^-1 может быть найден расширенным алгоритмом Евклида. Если p>3, то выполняется одно из двух условий p≡1 (mod 6) или p≡5 (mod 6).

Проективная плоскость - множество точек, представленных ненулевыми тройками (X,Y,Z), X,Y,Z∈F_p, с учетом эквивалентности (X,Y,Z)=(cX,cY,cZ) для любого с≠0. Множество точек проективной плоскости вида (X,Y,0) определяет бесконечно удаленную прямую. Остальные точки проективной плоскости с учетом эквивалентности однозначно представимы в виде пар (х,y)=(х,y,1), где х=XZ^-1, y=YZ^-1.

Поскольку хотя бы одна из координат любой точки проективной плоскости отлична от 0, эта точка эквивалентна точке, у которой соответствующая ненулевая координата равна 1.

Эллиптическая кривая в форме Вейерштрасса (ЭКВ) над полем F_p - подмножество точек проективной плоскости для p≥5, удовлетворяющих уравнению Y²Z≡X³+aXZ²+bZ³(mod p), 4a ³+27b²≠0 (mod p). Эта кривая содержит единственную бесконечно удаленную точку (0, 1, 0). Число точек N эллиптической кривой лежит в пределах . Точки ЭКВ допускают операцию сложения, при этом для любых точек Р₁, Р₂, Р₃ выполняются условия Р₁+Р₂=Р₂+P₁, (P₁+Р₂)+Р₃=Р₁+(P₂+Р₃). Нулем по сложению является точка (0,1,0), при этом -(X,Y,Z)=(X,-Y,Z). Сложение точек (Х₁,Y₁,Z₁)+(Х₂,Y₂,Z₂)=(Х₃,Y₃,Z₃) задается формулами [Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография, СПб., НПО «Профессионал», 2005, доступно с http://progbook.net/seti/kriptograf/1568-teoreticheskaya_kriptografiya.html].

если (X₁,Y₁,Z₁)=(X₂,Y₂,Z₂) (случай удвоения точек) или

X₃≡(X₂Z₁-X₁Z₂)(Z₁Z₂(Y₂Z₁-Y₁Z₂)²-(X₂Z₁+X₁Z₂)(X₂Z₁-X₁Z₂)²)(modp),

Y₃≡(X₂Z₁-X₁Z₂)²(Y₂Z₁(X₂Z₁+2X₁Z₂)-Y₁Z₂(X₁Z₂+2X₂Z₁))-Z₁Z₂(Y₂Z₁-Y₁Z₂)³

(mod p), Z₃≡Z₁Z₂(X₂Z₁-X₁Z₂)³(mod p),

если (X₁,Y₁,Z₁)≠(Х₂,Y₂,Z₂). Наименьшее натуральное число q такое, что q*(X₁,Y₁,Z₁)=(0,1,0) называется порядком точки (Х₁,Y₁,Z₁). ЭКВ допускает эквивалентное преобразование координат и коэффициентов (X,Y,Z,а,b) в (X',Y',Z',а',b'), где X'=u²X(mod p), Y'=u³Y(mod p), Z'=Z(mod p), а'=u⁴ a(mod p), b'=u⁶b(mod p) для любого и u≠0.

Эллиптическая кривая в форме Гессе (ЭКГ) над полем F_p - подмножество точек проективной плоскости для р≥5, удовлетворяющих уравнению U³+V³+W³≡3mUVW(mod p), где m³≠1 (mod p). Если р≡5 (mod 6), то ЭКГ содержит единственную бесконечно удаленную точку (1,-1,0). Точки ЭКГ допускают операцию сложения. Нулевым элементом по сложению является бесконечно удаленная точка (1,-1,0), при этом -(U,V,W)=(V,U,W).

Сложение точек (U₁,V₁,W₁)+(U₂,V₂,W₂)=(U₃,V₃,W₃) задается соотношениями U₃=V₁(W₁ ³-U₁ ³)(mod p), V₃=U₁(V₁ ³-W₁ ³)(mod p),

W₃=W₁(U₁ ³-V₁ ³)(mod p), если (U₁,V₁,W₁)=(U₂,V₂,W₂) (удвоение точки), и

U₃=U₁W₁V₂ ²-U₂W₂V₁ ²(mod p), V₃=V₁W₁V₂ ²-V₂W₂U₁ ²(mod p),

W₃=U₁V₁W₂ ²-U₂V₂W₁ ² (mod p), если (U₁,V₁,W₁)≠(U₂,V₂,W₂).

ЭКГ всегда содержит точку (0,-1,1) порядка 3. Поэтому число точек ЭКГ всегда делится на 3. Если р≡1 (mod 6), то ЭКГ содержит 9 точек порядка 3, в этом случае число точек ЭКГ делится на 9. Любая точка ЭКГ имеет хотя бы две ненулевых координаты и эквивалентна точке, у которой одна из ненулевых координат равна 1. Например, точка (U,V,W) при U≠0 эквивалентна точке (1,VU^-1,WU^-1), при V≠0 она эквивалентна точке (UV^-1,1,WV^-1), при W≠0 она эквивалентна точке (UW^-1,VW^-1,1).

Известно [Joye M., Quisquater J.-J. Hessian elliptic curves and side channel attacks // Cryptographic hardware and embedded systems (CHES 2001), Lecture Notes in Computer Science, v.2162, 2001, pp.402-410;

http://www.gemplus.com/smart/rd/publications/pdf/JQ01hess.pdf], что точку (X,Y,Z) ЭКВ можно преобразовать в точку (U,V,W) ЭКГ и обратно с помощью нелинейных выражений

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

Атака со стороны нарушителя по внешнему каналу (side channel attack) основана на измерении времени, затрачиваемого на формирование подписи, мгновенной потребляемой мощности и других физических величин и позволяет получить информацию о числе k, так как сложение и удвоение точек эллиптической кривой требуют различного времени и различного мгновенного энергопотребления. Однократное нахождение числа k ведет к вскрытию секретного ключа формирования подписи. ЭКГ затрудняет указанную атаку за счет замены операции удвоения точки операцией сложения двух различных точек [Joye M., Quisquater J.-J. Hessian elliptic curves and side channel attacks // Cryptographic hardware and embedded systems (CHES 2001), Lecture Notes in Computer Science, v.2162, 2001, pp.402-410; http://www.gemplus.com/smart/rd/publications/pdf/JQ01hess.pdf]:

2(U₁,V₁,W₁)=(W₁,U₁,V₁)+(V₁,W₁,U₁).

1. Способ электронной цифровой подписи на основе эллиптической кривой в форме Вейерштрасса, заданной уравнением Y²Z≡X³+aXZ²+bZ³(modp), где простое число р, коэффициенты a, b и координаты точек (X, Y, Z) заданы битовыми строками, в котором генерируют параметры системы электронной цифровой подписи: а, b, р, число точек эллиптической кривой, имеющее большой простой делитель q, точку Р порядка q и точку Q=dP для конфиденциального ключа d, а также формируют и проверяют подпись, причем при формировании и проверке подписи находят результирующую точку путем удвоений и сложений точек эллиптической кривой, заданных проективными координатами (X, Y, Z), находят битовую строку, представляющую значение XZ^-1(modp) координат результирующей точки, отличающийся тем, что выполняют линейное преобразование координат (X, Y, Z) точки эллиптической кривой в форме Вейерштрасса в координаты (U, V, W) точки эллиптической кривой в форме Гессе, заданной уравнением U³+V³+W³≡3mUVW(modp), операции сложения и удвоения точек выполняют на эллиптической кривой в форме Гессе, после чего выполняют линейное преобразование координат (U, V, W) результирующей точки эллиптической кривой в форме Гессе в координаты (X, Z) точки эллиптической кривой в форме Вейерштрасса, при этом в ходе генерации параметров системы электронной цифровой подписи находят два параметра (u, m) указанного линейного преобразования, для которых выполняются условия

2. Способ по п.1, отличающийся тем, что линейное преобразование координат (X, Y, Z) точки эллиптической кривой в форме Вейерштрасса в координаты (U, V, W) точки эллиптической кривой в форме Гессе выполняют по формуламU≡u²mX+u³Y+3^-1(4-m³)Z(modp),V≡u²mX-u³Y+3^-1(4-m³)Z(modp),W≡-2(u²X+m²Z)(modp).

3. Способ по п.1, отличающийся тем, что линейное преобразование координат (U, V, W) результирующей точки эллиптической кривой в форме Гессе в координаты (X, Z) точки эллиптической кривой в форме Вейерштрасса выполняют по формуламХ≡m²(U+V)+3^-1(4-m³)W(modp),Z≡-u²(U+V+mW)(modp).

4. Способ по п.1, отличающийся тем, что при генерации параметров системы электронной цифровой подписи выбирают р≡5 (mod 6), а число точек эллиптической кривой в форме Вейерштрасса выбирают кратным 3.

5. Способ по п.1, отличающийся тем, что при генерации параметров системы электронной цифровой подписи выбирают р≡1 (mod 6), а число точек эллиптической кривой в форме Вейерштрасса выбирают кратным 9.

6. Способ по п.1, отличающийся тем, что при генерации параметров системы электронной цифровой подписи для каждой из точек Р, Q находят координаты (U, V, W), затем заменяют ее координаты на (1, VU^-1(modp), WU^-1(modр)) при U≠0, или на (UV^-1(modp), 1, WV^-1(modp)) при V≠0, или на (UW^-1(modp), VW^-1(modp), 1) при W≠0.