ECDSA

ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом для создания цифровой подписи, аналогичный по своему строению DSA, но определённый, в отличие от него, не над полем целых чисел, а в группе точек эллиптической кривой.

Особенности

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

Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению:

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

Алгоритм ECDSA в 1999 г. был принят как стандарт ANSI, в 2000 г. — как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO. Несмотря на то, что стандарты ЭЦП созданы совсем недавно и находятся на этапе совершенствования, одним наиболее перспективных из них на сегодняшний день является ANSI X9.62 ECDSA от 1999 — DSA для эллиптических кривых.

Выбор параметров

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

Параметры алгоритма

1. Выбор хэш-функции <math>H(x)</math>. Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в последовательность битов, которые можно потом преобразовать в число.
2. Выбор большого простого числа <math>q</math> — порядок одной из циклических подгрупп группы точек эллиптической кривой.

   Замечание: Если размерность этого числа в битах меньше размерности в битах значений хэш-функции <math>H(x)</math> то используются только левые биты значения хэш-функции.

3. Простым числом <math>p</math> обозначается характеристика поля координат <math>F_p</math>.

Генерирование ключей ECDSA

Для простоты будем рассматривать эллиптические кривые над полем <math>F_p</math>, где <math>F_p</math> — конечное простое поле. Причем, если необходимо, конструкцию можно легко адаптировать для эллиптических кривых над другим полем.

Пусть <math>E</math> — эллиптическая кривая, определенная над <math>F_p</math>, и <math>P</math> — точка простого порядка <math>q</math> кривой <math>E(F_p)</math>. Кривая <math>E</math> и точка <math>P</math> являются системными параметрами. Число <math>p</math> — простое. Каждый пользователь — условно назовём его Алиса — конструирует свой ключ посредством следующих действий:

1. Выбирает случайное или псевдослучайное целое число <math>x</math> из интервала <math>[1,q-1]</math>.
2. Вычисляет произведение (кратное) <math>Q</math> = <math>x</math>·<math>P</math>.

Открытым ключом пользователя Алисы <math>A</math> является точка <math>Q</math>, а закрытым — <math>x</math>.

Вместо использования <math>E</math> и <math>P</math> в качестве глобальных системных параметров, можно фиксировать только поле <math>F_p</math> для всех пользователей и позволить каждому пользователю выбирать свою собственную эллиптическую кривую <math> E</math> и точку <math>P</math><math>\in</math> <math>E(F_p)</math>. В этом случае определенное уравнение кривой <math>E</math>, координаты точки <math>P</math>, а также порядок <math>q</math> этой точки <math>P</math> должны быть включены в открытый ключ пользователя. Если поле <math>F_p</math> фиксировано, то аппаратная и программная составляющие могут быть построены так, чтобы оптимизировать вычисления в том поле. В то же время имеется огромное количество вариантов выбора эллиптической кривой над полем <math>F_p</math>.

Вычисление цифровой подписи

Для того, чтобы подписать какое-либо сообщение, для которого подсчитано значение <math>h</math> хэш-функции <math>H</math>, пользователь <math>A</math> должен сделать следующее:

1. Выбрать случайное целое число <math>k \in [1, q-1]</math>.
2. Вычислить <math>k\cdot P = (x_1, y_1)</math> и положить в <math>r = x_1\mod q</math>, где <math>r</math> получается из целого числа <math>x_1</math> между <math>0</math> и <math>(p - 1)</math> приведением по модулю <math>q</math>.

   Замечание: если <math>r = 0</math>, то уравнение подписи <math>s = k^{-1}(h + x\cdot r)\mod q</math> не зависит от секретного ключа <math>x</math>, и следовательно, <math>(r,s)</math> не подходит в качестве цифровой подписи. Значит, в случае <math>r = 0</math> необходимо вернуться к шагу 1.

3. Вычислить <math>k^{-1}\pmod q</math> и положить <math>s = k^{-1}(h + x\cdot r)\mod q</math>, где h — значение хеш-функции подписываемого сообщения.

   Замечание: если <math>s = 0</math>, то значение <math>s^{-1}\pmod q</math>, нужное для проверки, не существует. Значит, в случае <math>s = 0</math> необходимо вернуться к шагу 1.

Подписью для сообщения является пара целых чисел <math>(r, s)</math>.

Проверка цифровой подписи

Для того, чтобы проверить подпись пользователя Алисы <math>(r, s)</math> на сообщение, пользователь Боб <math>B</math> должен сделать следующее:

1. Получить подтвержденную копию открытого ключа <math>Q</math> пользователя А;
2. Проверить, что числа <math>r</math> и <math>s</math> являются целыми числами из интервала <math>[1, q-1]</math>, и вычислить значение хеш-функции <math>h</math> от сообщения;
3. Вычислить <math>u_1 = s^{-1}h \mod q</math> и <math>u_2 = s^{-1}r \mod q</math>;
4. Вычислить <math>u_1\cdot P + u_2\cdot Q = (x_0, y_0)</math>, и относительно <math>x_0</math>, как целого числа между <math>0</math> и <math>(p - 1)</math>, положить <math>v = x_0 \mod q</math>;
5. Принять подпись, тогда и только тогда, когда <math>v = r</math>.

Заметим, что, если пользователь Алиса вычислила свою подпись правильно, то <math>u_1P + u_2Q = (u_1 + xu_2)P = (s^{-1}\cdot h\mod q + x\cdot s^{-1}\cdot r\mod q)\cdot P = k\cdot P </math>, так как <math>k = s^{-1}(h + xr)\pmod q </math>, и поэтому <math>v = r</math>.

Для подтверждения публичного ключа Q нужно проделать следующее (<math>O</math> здесь обозначает бесконечно удалённую точку):

1. Проверить, что <math>Q</math> не равно <math>O</math> и координаты верны;
2. Проверить, что <math>Q</math> лежит на кривой;
3. Проверить, что <math>qQ = O</math>;

ECDSA согласно стандарту ANSI X9.62

Для практического применения алгоритма ECDSA налагают ограничения на поля, в которых определены эллиптические кривые. Более того, для избежания некоторых известных атак, ограничения накладываются и на уравнения, задающие эллиптические кривые, и на порядок базовых точек. Для простоты в данном разделе будем рассматривать только конечные <math>F_p</math>.

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

Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой <math>E</math> делилось на достаточно большое простое число <math>n </math>. Стандарт ANSI X9.62 требует <math>n > 2^{160}</math>. Уравнение эллиптической кривой строится специфическим образом, используя случайные/псевдослучайные коэффициенты.

Главными параметрами при построении эллиптической кривой являются:

1. размерность поля <math>p</math>, где <math>p</math> является простым числом;
2. два элемента поля <math>F_p</math> — <math>a</math> и <math>b</math>, определенные уравнением эллиптической кривой <math>E</math>, где <math>E</math> имеет вид:

   <math>y^2 = x^3 + ax + b</math>,

   где <math>a</math>, <math>b</math> <math>\in</math> <math>F_p</math>, и <math>4a^3</math> + <math>27b^2</math> <math>\not\equiv</math> 0 <math>\pmod p</math>.

3. два элемента поля <math>F_p</math> — <math>x_G</math> и <math>y_G</math>, которые определяют конечную точку <math>G = (x_G, y_G)</math> — генератор группы <math>E(F_p)</math>
4. порядок <math>q</math> точки <math>G</math>, где <math>q > 2^{160}</math> и <math>q</math> > 4 <math>\sqrt{p}</math>
5. сомножитель <math>h</math> = #<math>E(F_p)</math>/<math>q</math>, где обозначение #<math>E(F_p)</math> означает порядок группы точек эллиптической кривой <math>E(F_p)</math>.

Генерация главных параметров

Один из способов генерирования криптографически надежных параметров заключается в следующем:

1. Выбираем коэффициенты <math>a</math> и <math>b</math> специфическим образом используя в вычислениях случайные/псевдослучайные числа. Пусть <math>E</math> — эллиптическая кривая — <math>y^2 = x^3 + ax + b</math>;
2. Вычисляем <math>N = \#E(F_p)</math>;
3. Проверяем, что <math>N</math> имеет делитель, который является большим простым числом <math>q (q > 2^{160}</math> и <math>q > 4 \sqrt{p})</math>. Если нет, то нужно вернуться на шаг 1.
4. Проверяем, что <math>q</math> не делит <math>{p^k - 1}</math> для каждого <math>k</math>, <math>1 \le k \le 100</math>. Если нет, то нужно вернуться на шаг 1;
5. Проверяем, что <math>q \ne p</math>. Если нет, то нужно вернуть на шаг 1;
6. Берем случайную точку <math>G' \in E(F_q)</math> и положить <math>G = (N/q)G'</math>. Повторяем до тех пор пока <math>G \ne O</math>.

В 1985 г. Скооф (Schoof) представил алгоритм, работающий за полимиальное время, для подсчета <math>\#E(F_p)</math>, число точек эллиптической кривой определенная над полем <math>F_p</math> (p — нечетное простое число). Алгоритм Скоофа является достаточно не эффективным на практике для значений <math>p</math>, которые действительно представляют интерес, то есть <math>p > 2^{160}</math>. В последние несколько лет было проделано много работы по улучшению и ускорению алгоритма Скоофа, сейчас он называется SEA (Schoof-Elkies-Atkin) алгоритм. С такими улучшениями криптографически пригодные эллиптические кривые, определенные над полями, чьи порядки более, чем <math>2^{200}</math>, могут быть сгенерированы за несколько часов на рабочих станциях.

Преимущества ECDSA перед DSA

ECDSA является очень привлекательным алгоритмом для реализации ЭЦП. Самым важным преимуществом ECDSA является возможность его работы на значительно меньших полях <math>F_p</math>. Как, в общем, с криптографией эллиптической кривой, предполагается, что битовый размер открытого ключа, который будет необходим для ECDSA, равен двойному размеру секретного ключа в битах. Для сравнения, при уровне безопасности в 80 бит (то есть атакующему необходимо примерно <math>2^{80}</math> версий подписи для нахождения секретного ключа), размер открытого ключа DSA равен, по крайней мере, 1024 бит, тогда как открытого ключа ECDSA — 160 бит. С другой стороны размер подписи одинаков и для DSA, и для ECDSA: <math>4t</math> бит, где <math>t</math> — уровень безопасности, измеренный в битах, то есть — примерно 320 бит для уровня безопасности в 80 бит.

Практическая реализация

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

Ссылки

• [eprint.iacr.org/2006/230.pdf Neal Koblitz and Alfred Menezes] (1995). — Another Look at Generic Groups. Проверено 27 ноября 2008. [www.webcitation.org/65kpKi0LJ Архивировано из первоисточника 27 февраля 2012].

Отрывок, характеризующий ECDSA

Офицеры хотели откланяться, но князь Андрей, как будто не желая оставаться с глазу на глаз с своим другом, предложил им посидеть и напиться чаю. Подали скамейки и чай. Офицеры не без удивления смотрели на толстую, громадную фигуру Пьера и слушали его рассказы о Москве и о расположении наших войск, которые ему удалось объездить. Князь Андрей молчал, и лицо его так было неприятно, что Пьер обращался более к добродушному батальонному командиру Тимохину, чем к Болконскому.
– Так ты понял все расположение войск? – перебил его князь Андрей.
– Да, то есть как? – сказал Пьер. – Как невоенный человек, я не могу сказать, чтобы вполне, но все таки понял общее расположение.
– Eh bien, vous etes plus avance que qui cela soit, [Ну, так ты больше знаешь, чем кто бы то ни было.] – сказал князь Андрей.
– A! – сказал Пьер с недоуменьем, через очки глядя на князя Андрея. – Ну, как вы скажете насчет назначения Кутузова? – сказал он.
– Я очень рад был этому назначению, вот все, что я знаю, – сказал князь Андрей.
– Ну, а скажите, какое ваше мнение насчет Барклая де Толли? В Москве бог знает что говорили про него. Как вы судите о нем?
– Спроси вот у них, – сказал князь Андрей, указывая на офицеров.
Пьер с снисходительно вопросительной улыбкой, с которой невольно все обращались к Тимохину, посмотрел на него.
– Свет увидали, ваше сиятельство, как светлейший поступил, – робко и беспрестанно оглядываясь на своего полкового командира, сказал Тимохин.
– Отчего же так? – спросил Пьер.
– Да вот хоть бы насчет дров или кормов, доложу вам. Ведь мы от Свенцян отступали, не смей хворостины тронуть, или сенца там, или что. Ведь мы уходим, ему достается, не так ли, ваше сиятельство? – обратился он к своему князю, – а ты не смей. В нашем полку под суд двух офицеров отдали за этакие дела. Ну, как светлейший поступил, так насчет этого просто стало. Свет увидали…
– Так отчего же он запрещал?
Тимохин сконфуженно оглядывался, не понимая, как и что отвечать на такой вопрос. Пьер с тем же вопросом обратился к князю Андрею.
– А чтобы не разорять край, который мы оставляли неприятелю, – злобно насмешливо сказал князь Андрей. – Это очень основательно; нельзя позволять грабить край и приучаться войскам к мародерству. Ну и в Смоленске он тоже правильно рассудил, что французы могут обойти нас и что у них больше сил. Но он не мог понять того, – вдруг как бы вырвавшимся тонким голосом закричал князь Андрей, – но он не мог понять, что мы в первый раз дрались там за русскую землю, что в войсках был такой дух, какого никогда я не видал, что мы два дня сряду отбивали французов и что этот успех удесятерял наши силы. Он велел отступать, и все усилия и потери пропали даром. Он не думал об измене, он старался все сделать как можно лучше, он все обдумал; но от этого то он и не годится. Он не годится теперь именно потому, что он все обдумывает очень основательно и аккуратно, как и следует всякому немцу. Как бы тебе сказать… Ну, у отца твоего немец лакей, и он прекрасный лакей и удовлетворит всем его нуждам лучше тебя, и пускай он служит; но ежели отец при смерти болен, ты прогонишь лакея и своими непривычными, неловкими руками станешь ходить за отцом и лучше успокоишь его, чем искусный, но чужой человек. Так и сделали с Барклаем. Пока Россия была здорова, ей мог служить чужой, и был прекрасный министр, но как только она в опасности; нужен свой, родной человек. А у вас в клубе выдумали, что он изменник! Тем, что его оклеветали изменником, сделают только то, что потом, устыдившись своего ложного нарекания, из изменников сделают вдруг героем или гением, что еще будет несправедливее. Он честный и очень аккуратный немец…
– Однако, говорят, он искусный полководец, – сказал Пьер.
– Я не понимаю, что такое значит искусный полководец, – с насмешкой сказал князь Андрей.
– Искусный полководец, – сказал Пьер, – ну, тот, который предвидел все случайности… ну, угадал мысли противника.
– Да это невозможно, – сказал князь Андрей, как будто про давно решенное дело.
Пьер с удивлением посмотрел на него.
– Однако, – сказал он, – ведь говорят же, что война подобна шахматной игре.
– Да, – сказал князь Андрей, – только с тою маленькою разницей, что в шахматах над каждым шагом ты можешь думать сколько угодно, что ты там вне условий времени, и еще с той разницей, что конь всегда сильнее пешки и две пешки всегда сильнее одной, a на войне один батальон иногда сильнее дивизии, а иногда слабее роты. Относительная сила войск никому не может быть известна. Поверь мне, – сказал он, – что ежели бы что зависело от распоряжений штабов, то я бы был там и делал бы распоряжения, а вместо того я имею честь служить здесь, в полку вот с этими господами, и считаю, что от нас действительно будет зависеть завтрашний день, а не от них… Успех никогда не зависел и не будет зависеть ни от позиции, ни от вооружения, ни даже от числа; а уж меньше всего от позиции.
– А от чего же?
– От того чувства, которое есть во мне, в нем, – он указал на Тимохина, – в каждом солдате.
Князь Андрей взглянул на Тимохина, который испуганно и недоумевая смотрел на своего командира. В противность своей прежней сдержанной молчаливости князь Андрей казался теперь взволнованным. Он, видимо, не мог удержаться от высказывания тех мыслей, которые неожиданно приходили ему.
– Сражение выиграет тот, кто твердо решил его выиграть. Отчего мы под Аустерлицем проиграли сражение? У нас потеря была почти равная с французами, но мы сказали себе очень рано, что мы проиграли сражение, – и проиграли. А сказали мы это потому, что нам там незачем было драться: поскорее хотелось уйти с поля сражения. «Проиграли – ну так бежать!» – мы и побежали. Ежели бы до вечера мы не говорили этого, бог знает что бы было. А завтра мы этого не скажем. Ты говоришь: наша позиция, левый фланг слаб, правый фланг растянут, – продолжал он, – все это вздор, ничего этого нет. А что нам предстоит завтра? Сто миллионов самых разнообразных случайностей, которые будут решаться мгновенно тем, что побежали или побегут они или наши, что убьют того, убьют другого; а то, что делается теперь, – все это забава. Дело в том, что те, с кем ты ездил по позиции, не только не содействуют общему ходу дел, но мешают ему. Они заняты только своими маленькими интересами.
– В такую минуту? – укоризненно сказал Пьер.
– В такую минуту, – повторил князь Андрей, – для них это только такая минута, в которую можно подкопаться под врага и получить лишний крестик или ленточку. Для меня на завтра вот что: стотысячное русское и стотысячное французское войска сошлись драться, и факт в том, что эти двести тысяч дерутся, и кто будет злей драться и себя меньше жалеть, тот победит. И хочешь, я тебе скажу, что, что бы там ни было, что бы ни путали там вверху, мы выиграем сражение завтра. Завтра, что бы там ни было, мы выиграем сражение!
– Вот, ваше сиятельство, правда, правда истинная, – проговорил Тимохин. – Что себя жалеть теперь! Солдаты в моем батальоне, поверите ли, не стали водку, пить: не такой день, говорят. – Все помолчали.
Офицеры поднялись. Князь Андрей вышел с ними за сарай, отдавая последние приказания адъютанту. Когда офицеры ушли, Пьер подошел к князю Андрею и только что хотел начать разговор, как по дороге недалеко от сарая застучали копыта трех лошадей, и, взглянув по этому направлению, князь Андрей узнал Вольцогена с Клаузевицем, сопутствуемых казаком. Они близко проехали, продолжая разговаривать, и Пьер с Андреем невольно услыхали следующие фразы:
– Der Krieg muss im Raum verlegt werden. Der Ansicht kann ich nicht genug Preis geben, [Война должна быть перенесена в пространство. Это воззрение я не могу достаточно восхвалить (нем.) ] – говорил один.
– O ja, – сказал другой голос, – da der Zweck ist nur den Feind zu schwachen, so kann man gewiss nicht den Verlust der Privatpersonen in Achtung nehmen. [О да, так как цель состоит в том, чтобы ослабить неприятеля, то нельзя принимать во внимание потери частных лиц (нем.) ]
– O ja, [О да (нем.) ] – подтвердил первый голос.
– Да, im Raum verlegen, [перенести в пространство (нем.) ] – повторил, злобно фыркая носом, князь Андрей, когда они проехали. – Im Raum то [В пространстве (нем.) ] у меня остался отец, и сын, и сестра в Лысых Горах. Ему это все равно. Вот оно то, что я тебе говорил, – эти господа немцы завтра не выиграют сражение, а только нагадят, сколько их сил будет, потому что в его немецкой голове только рассуждения, не стоящие выеденного яйца, а в сердце нет того, что одно только и нужно на завтра, – то, что есть в Тимохине. Они всю Европу отдали ему и приехали нас учить – славные учители! – опять взвизгнул его голос.
– Так вы думаете, что завтрашнее сражение будет выиграно? – сказал Пьер.
– Да, да, – рассеянно сказал князь Андрей. – Одно, что бы я сделал, ежели бы имел власть, – начал он опять, – я не брал бы пленных. Что такое пленные? Это рыцарство. Французы разорили мой дом и идут разорить Москву, и оскорбили и оскорбляют меня всякую секунду. Они враги мои, они преступники все, по моим понятиям. И так же думает Тимохин и вся армия. Надо их казнить. Ежели они враги мои, то не могут быть друзьями, как бы они там ни разговаривали в Тильзите.
– Да, да, – проговорил Пьер, блестящими глазами глядя на князя Андрея, – я совершенно, совершенно согласен с вами!
Тот вопрос, который с Можайской горы и во весь этот день тревожил Пьера, теперь представился ему совершенно ясным и вполне разрешенным. Он понял теперь весь смысл и все значение этой войны и предстоящего сражения. Все, что он видел в этот день, все значительные, строгие выражения лиц, которые он мельком видел, осветились для него новым светом. Он понял ту скрытую (latente), как говорится в физике, теплоту патриотизма, которая была во всех тех людях, которых он видел, и которая объясняла ему то, зачем все эти люди спокойно и как будто легкомысленно готовились к смерти.
– Не брать пленных, – продолжал князь Андрей. – Это одно изменило бы всю войну и сделало бы ее менее жестокой. А то мы играли в войну – вот что скверно, мы великодушничаем и тому подобное. Это великодушничанье и чувствительность – вроде великодушия и чувствительности барыни, с которой делается дурнота, когда она видит убиваемого теленка; она так добра, что не может видеть кровь, но она с аппетитом кушает этого теленка под соусом. Нам толкуют о правах войны, о рыцарстве, о парламентерстве, щадить несчастных и так далее. Все вздор. Я видел в 1805 году рыцарство, парламентерство: нас надули, мы надули. Грабят чужие дома, пускают фальшивые ассигнации, да хуже всего – убивают моих детей, моего отца и говорят о правилах войны и великодушии к врагам. Не брать пленных, а убивать и идти на смерть! Кто дошел до этого так, как я, теми же страданиями…