Рейтинг:2

Почему r используется в подписи ECDSA, а R в подписи Шнорра?

флаг br

В подписи Шнорра (R, s) используется R. Но в подписи ECDSA (r, s) используется r, который является координатой x R. В чем разница?

kelalaka avatar
флаг in
Патент Шнорра!
флаг br
ECDSA не может использовать R из-за патента?
Рейтинг:4
флаг ng

В подписи Шнорра $(Р,с)$, $R$ используется. Но в подписи ECDSA $(р,с)$, $г$ используется, что является координатой x $R$.

Это утверждение технически неверно:

  • В подпись Шнорра (альт.), как первоначально было определено, первым компонентом подписи является хэш, а не элемент группы, не говоря уже о «точке» на группе эллиптических кривых, которая не использовалась в криптографии.
  • В определении Подпись ECDSA, первый компонент $г$ подписи является x-координата $x_R$ точки на эллиптической кривой, преобразованной в целое число, затем уменьшенной по модулю группового порядка $n$ (затем перешел к строке байтов, но мы оставим это в стороне); это не просто $x_R$.

Тем не менее, суть этого утверждения стоит с некоторыми изменениями:

  • В современном учебнике сигнатура Шнорра определяется для произвольной группы, где проблема дискретного логарифма сложна, с двумя основными вариантами в зависимости от того, является ли первый компонент сигнатуры
    • Хэш (как минимум) сообщения и группового элемента $R$, как в оригинальной подписи Шнорра.
    • Элемент группы (уникальное битовое представление a) $R$, например, ЭдДСА. Это вариант, к которому относится утверждение.
  • Указанная группа обычно является подгруппой эллиптической кривой простого порядка. $n$ эллиптической кривой на поле $\mathbb F_{p^m}$, и обычно $м=1$, таким образом, координата x $x_R$ из $R$ является целым числом в $[0,р)$.
  • Для обычных таких кривых $n\примерно p$, таким образом, с $r:=x_R\bmod n$ он держит $ г = х_R $ с большой вероятностью, даже если $n<p$ (например. secp256k1, секп256р1), или мы можем выбрать эллиптическую кривую с $n>p$.

Теперь, когда у нас есть истинное утверждение, мы можем спросить:

Почему разница?

Так как ЭЦДСА является адаптацией к группе эллиптических кривых ДСА, где первая компонента сигнатуры — элемент группы, приведенный по модулю простого порядка группы. В DSA это сокращение было сделано для того, чтобы сократить первый компонент подписи. Причины, по которым DSA использует этот метод, а не хэш, как в исходной подписи Шнорра, могут быть

  • Оригинальная подпись Шнорра была закрыта патент, в том числе в США, и, таким образом, возник интерес к другому методу¹.
  • ДСА оказался ближе к уже хорошо изученному подпись Эль-Гамаля.
  • оригинальный Подпись Шнорра из-за ее узкой $к$-битный хэш (и в отличие от современной подписи Шнорра с более широким хешем, в обоих вариантах выше):
    • Не может безопасно использоваться в качестве подтверждения подписанного сообщения: владелец закрытого ключа, подписывающий сообщение и способный выбрать его частично (например, изменить несколько байтов в конце), может преднамеренно сделать это таким образом, чтобы другое сообщение с другое значение по их выбору имеет ту же подпись. Атака представляет собой атаку столкновением выбранных префиксов на $к$-битный хеш, ожидаемая стоимость меньше чем $2^{к/2+1,4}$ хеши. Это увеличивает риск отказа от подписи и на законных основаниях может вызвать страх, неуверенность и сомнение.
    • Будет уязвим для гипотетической (первой или второй) атаки прообраза на ввод сообщения хэша, в том числе для хэшей среди тонкого подмножества $\{0,1\}^к$, ожидаемой стоимости $2^к$ хеши; когда DSA (благодаря гораздо более широкому хешу) имеет большой запас по этому поводу.

DSA использует Группа Шнорра, то есть циклическая подгруппа мультипликативная группа по модулю простой $р$. ECDSA существенно меняет это на Эллиптическая кривая группа через Поле Галуа, что позволяет использовать меньший открытый ключ и более быстрые вычисления. Принцип DSA уменьшения первого компонента подписи по модулю группового порядка сохраняется. Необходимое предварительное преобразование элемента поля в целое выполняется по координате x. $x_R$, игнорируя $y_R$. Между прочим, это приводит к потере свойства безопасности: ECDSA не sEUF-CMA, когда DSA есть, потому что $R$ и противоположность $R$ в группе эллиптических кривых имеют одинаковые $x_R$, позволяя превратить действительную подпись ECDSA в другую действительную подпись для того же сообщения, изменив $s$ к $-s$ по модулю группового порядка.


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

флаг br
Итак, технически ECDSA также может использовать (R, s) в качестве подписи?
fgrieu avatar
флаг ng
@sinoTrinity: да, мы могли бы немного изменить ECDSA, чтобы иметь двоичное представление $ R $ в качестве первого компонента подписи, и заставить верификатор преобразовать его в целое число, а затем использовать по модулю $ n $. Кажется, что можно восстановить sEUF-CMA [но сделать это, увеличив размер подписи как минимум на 1 бит, а не уменьшить его на 1 бит, как это происходит при замене $s$ на $\min(s,n-s)$]. И это по-прежнему не будет ни одной из двух форм подписи EC-Schnorr, поскольку только сообщение входит в хэш ECDSA, а не сообщение и точка в подписи EC-Schnorr (все варианты).

Ответить или комментировать

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