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

Классы МПК:H04L9/32 со средствами для установления личности или полномочий пользователя системы
G06F17/10 комплексные математические операции
Автор(ы):
Патентообладатель(и):Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Санкт-Петербургский государственный политехнический университет" (ФГБОУ ВПО "СПбГПУ") (RU)
Приоритеты:
подача заявки:
2010-11-30
публикация патента:

Изобретение относится к вычислительной технике. Технический результат заключается в повышении скорости формирования и проверки ЭЦП и повышении защищенности системы ЭЦП от атак по внешнему каналу. Способ электронной цифровой подписи на основе эллиптической кривой в форме Вейерштрасса, в котором генерируют параметры системы электронной цифровой подписи, а также формируют и проверяют подпись, причем при формировании и проверке подписи находят результирующую точку путем удвоений и сложений точек эллиптической кривой, заданных проективными координатами (X,Y,Z), находят битовую строку, представляющую значение XZ-1 (modp) координат результирующей точки, причем выполняют линейное преобразование координат (X,Y,Z) точки эллиптической кривой в форме Вейерштрасса в координаты (U,V,W) точки эллиптической кривой в форме Гессе, операции сложения и удвоения точек выполняют на эллиптической кривой в форме Гессе, после чего выполняют линейное преобразование координат (U,V,W) результирующей точки эллиптической кривой в форме Гессе в координаты (X,Z) точки эллиптической кривой в форме Вейерштрасса. 5 з.п. ф-лы, 1 табл., приложение.

Формула изобретения

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

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

2. Способ по п.1, отличающийся тем, что линейное преобразование координат (X, Y, Z) точки эллиптической кривой в форме Вейерштрасса в координаты (U, V, W) точки эллиптической кривой в форме Гессе выполняют по формулам

Uспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 u2mX+u3Y+3-1(4-m3 )Z(modp),

Vспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 u2mX-u3Y+3-1(4-m3 )Z(modp),

Wспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 -2(u2X+m2Z)(modp).

3. Способ по п.1, отличающийся тем, что линейное преобразование координат (U, V, W) результирующей точки эллиптической кривой в форме Гессе в координаты (X, Z) точки эллиптической кривой в форме Вейерштрасса выполняют по формулам

Хспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 m2(U+V)+3-1(4-m3)W(modp),

Zспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 -u2(U+V+mW)(modp).

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

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

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

Описание изобретения к патенту

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

Известны системы электронной цифровой подписи (ЭЦП) на эллиптических кривых, в которых обрабатываемые данные представлены точками эллиптической кривой в форме Вейерштрасса (ЭКВ), заданной уравнением y 2способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 х3+ах+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, способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 }, образованного точкой Р, является простым числом q, длина которого в первом случае не менее 254 бит, а во втором случае не менее 160 бит. Поэтому достаточно рассмотреть только операции с точками эллиптической кривой, предусмотренные в ГОСТ Р 34.10-2001.

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

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

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

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

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

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

U3+V3+W3способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3mUVW(mod p), m3способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 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 такие, что выполняются условия

u4aспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 -3-1m(8+m3)(mod p), u6 bспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 27-12(-8-20m3+m6)(mod p).

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

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

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

1. Способ электронной цифровой подписи на ЭКВ, заданной уравнением Y2Z=X 3+aXZ2+bZ3(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) точки ЭКГ, заданной уравнением U3+V3+W3=3mUVW(mod p), операции удвоения и сложения точек выполняют на ЭКГ.

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

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

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

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

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

Uспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 u2mX+u3Y+3-1(4-m3 )Z(mod p),

Vспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 u2mX-u3Y+3-1(4-m3 )Z(mod p),

Wспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 -2(u2X+m2Z)(mod p).

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

Хспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 m2(U+V)+3-1(4-m3)W(mod p),

Zспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 -u2(U+V+mW)(mod p).

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

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

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

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

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

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

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

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

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

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

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

Это линейное преобразование можно также определить как умножение матрицы на вектор: способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625

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

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

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

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

Это линейное преобразование можно также определить как умножение матрицы на вектор: способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625

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

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

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

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

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

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

Умножение точки Р' на число k выполняется известным способом. Например, число k записывают в двоичном виде k=k0+2k1 +способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 +2nkn, kn=1. Полагают Tn=Р'. Для i от n-1 до 0 полагают Ti =2Ti+1+kiP'. Результат: Т0 .

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

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

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

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

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

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

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

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

Заявленный способ корректен, если система (I) имеет решение по модулю р. Предлагается два варианта выбора параметров криптосистемы. Первый вариант: выбрать рспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 5 (mod 6), а число точек ЭКВ, задаваемое параметрами а, b, выбирать кратным 3 так, чтобы при этом выполнялись требования, предписанные стандартами подписи ГОСТ Р 34.10-2001 и ECDSA. Второй вариант: выбрать рспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 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 (случай рспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 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

Параметры линейно эквивалентных эллиптических кривых в форме Вейерштрасса и Гессе
N66 6972 7578 8184 8790 9396 99102
а 51 11 13 11 11 14 6
b 1621 620 33 2732 117 132 6
m 3073 197 6154 4059 2623 4946 24
u ±33 ±28±1 ±19 ±37±10 ±16 ±36±37 ±26 ±6±2 ±19

Для р=71 (случай pспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 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):

Y2Z=X3+XZ2+17Z 3(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способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 (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 1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 se-1(mod q)=30, z2способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 -re-1(mod q)=25.

Проверка подписи известным способом на ЭКВ дает: z1P=(0,73,1), z 2Q=(22,35,1). Точка z1P+z2Q имеет х-координату 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 1P'=(19,34,21), z2Q'=(45,34,74), R'=z 1P'+z2Q'=(73,66,13). Обратное линейное преобразование трех координат точки R' ЭКГ в две координаты точки R ЭКВ по формулам (III) дает значения: Х=80, Z=60, XZ -1=29(mod 83), что совпадает с r (mod q). Подпись верна.

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

Приложение 1

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

Запись аспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 b(mod p) означает, что а-b делится на р.

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

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

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

Эллиптическая кривая в форме Вейерштрасса (ЭКВ) над полем Fp - подмножество точек проективной плоскости для pспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 5, удовлетворяющих уравнению Y2Zспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 X3+aXZ2+bZ3(mod p), 4a3+27b2способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 0 (mod p). Эта кривая содержит единственную бесконечно удаленную точку (0, 1, 0). Число точек N эллиптической кривой лежит в пределах способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 . Точки ЭКВ допускают операцию сложения, при этом для любых точек Р1, Р2, Р3 выполняются условия Р122+P1 , (P12)+Р31+(P 23). Нулем по сложению является точка (0,1,0), при этом -(X,Y,Z)=(X,-Y,Z). Сложение точек (Х1,Y 1,Z1)+(Х2,Y2,Z2 )=(Х3,Y3,Z3) задается формулами [Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография, СПб., НПО «Профессионал», 2005, доступно с http://progbook.net/seti/kriptograf/1568-teoreticheskaya_kriptografiya.html].

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

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

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

если (X1,Y1,Z 1)=(X2,Y2,Z2) (случай удвоения точек) или

X3способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 (X2Z1-X1Z2)(Z 1Z2(Y2Z1-Y1 Z2)2-(X2Z1+X 1Z2)(X2Z1-X1 Z2)2)(modp),

Y3 способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 (X2Z1-X1Z2) 2(Y2Z1(X2Z1 +2X1Z2)-Y1Z2(X 1Z2+2X2Z1))-Z1 Z2(Y2Z1-Y1Z2 )3

(mod p), Z3способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 Z1Z2(X2Z1-X 1Z2)3(mod p),

если (X1,Y1,Z1)способ электронной цифровой подписи на основе эллиптической кривой, патент № 24576252,Y2,Z2). Наименьшее натуральное число q такое, что q*(X1,Y1 ,Z1)=(0,1,0) называется порядком точки (Х1 ,Y1,Z1). ЭКВ допускает эквивалентное преобразование координат и коэффициентов (X,Y,Z,а,b) в (X',Y',Z', а',b'), где X'=u2X(mod p), Y'=u 3Y(mod p), Z'=Z(mod p), а'=u4 a(mod p), b'=u6b(mod p) для любого и uспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 0.

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

Сложение точек (U 1,V1,W1)+(U2,V2 ,W2)=(U3,V3,W3) задается соотношениями U3=V1(W1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3-U1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3)(mod p), V3=U1(V 1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3-W1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3)(mod p),

W3=W 1(U1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3-V1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 3)(mod p), если (U1,V1 ,W1)=(U2,V2,W2) (удвоение точки), и

U3=U1W1 V2способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 2-U2W2V1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 2(mod p), V3=V1W1 V2способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 2-V2W2U1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 2(mod p),

W3=U 1V1W2способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 2-U2V2W1способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 2 (mod p), если (U1,V1 ,W1)способ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 (U2,V2,W2).

ЭКГ всегда содержит точку (0,-1,1) порядка 3. Поэтому число точек ЭКГ всегда делится на 3. Если рспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 1 (mod 6), то ЭКГ содержит 9 точек порядка 3, в этом случае число точек ЭКГ делится на 9. Любая точка ЭКГ имеет хотя бы две ненулевых координаты и эквивалентна точке, у которой одна из ненулевых координат равна 1. Например, точка (U,V,W) при Uспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 0 эквивалентна точке (1,VU-1,WU-1 ), при Vспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 0 она эквивалентна точке (UV-1,1,WV-1 ), при Wспособ электронной цифровой подписи на основе эллиптической кривой, патент № 2457625 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) ЭКГ и обратно с помощью нелинейных выражений

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

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

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

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

Атака со стороны нарушителя по внешнему каналу (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(U1,V1,W1)=(W 1,U1,V1)+(V1,W1 ,U1).

Класс H04L9/32 со средствами для установления личности или полномочий пользователя системы

методики обеспечения и управления цифровым телефонным аппаратом для аутентификации с сетью -  патент 2518441 (10.06.2014)
способ и устройство для генерации и аутентификации псевдонима -  патент 2512139 (10.04.2014)
способ и устройство управления потоками данных распределенной информационной системы -  патент 2509425 (10.03.2014)
аутентификация потоков данных -  патент 2509424 (10.03.2014)
интеграция корпоративной авторизации идентичности в конференциях -  патент 2507692 (20.02.2014)
сетевая архитектура для безопасной передачи данных -  патент 2504912 (20.01.2014)
электронная сертификация, индентификация и передача информации с использованием кодированных графических изображений -  патент 2494455 (27.09.2013)
способ аутентификации пользовательского терминала в сервере интерфейса, а также сервер интерфейса и пользовательский терминал для его осуществления -  патент 2491771 (27.08.2013)
способ аутентификации пользовательского терминала и сервер аутентификации и пользовательский терминал для него -  патент 2491733 (27.08.2013)
способы для автоматической идентификации участников для события мультимедийной конференц-связи -  патент 2488227 (20.07.2013)

Класс G06F17/10 комплексные математические операции

криптография на эллиптической кривой -  патент 2520379 (27.06.2014)
способ вычисления физического значения, способ численного анализа, программа вычисления физического значения, программа численного анализа, устройство вычисления физического значения и устройство численного анализа -  патент 2519331 (10.06.2014)
цифровой функциональный преобразователь -  патент 2513683 (20.04.2014)
способ моделирования разнородных сетей связи -  патент 2481629 (10.05.2013)
способ определения траектории движения автономного транспортного средства в динамической среде -  патент 2479015 (10.04.2013)
способ формирования регулярных последовательностей с элементами, составленными из двоичных сигналов -  патент 2469382 (10.12.2012)
быстрое вычисление произведений посредством двоичных дробей со знакосимметричными ошибками округления -  патент 2468422 (27.11.2012)
способ и устройство прогнозирования нестационарного временного ряда -  патент 2467383 (20.11.2012)
способ формирования нерегулярных последовательностей с элементами, составленными из двоичных сигналов -  патент 2467378 (20.11.2012)
устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации -  патент 2447485 (10.04.2012)
Наверх