Является ли кривая СТАРКа SafeCurve?

Кривая STARK кажется разумным выбором для ECDSA.

Кривая СТАРК определяется над $\mathbb{F}_p$ с $p = 2^{251} + 17*2^{192} +1$ с коротким уравнением Вейерштрасса

$$у^2 = х^3 + А х + В$$

с

• $А = 1$, и
• $B = 3141592653589793238462643383279502884197169399375105820974944592307816406665$

• Порядок группы кривых (количество точек) равен $n = \#E(\mathbf{F}_p)$ является $n= 3618502788666131213697322783095070105526743751716087489154079457884512865583$

  И это указание простого числа, что

  • Каждый элемент, кроме идентификатора ( $\mathcal{O})$ может быть генератор.Число ничего в моем рукаве этой кривой (спасибо Арии за указание), происходит от $\пи$.

    Так Старкс имеет некоторую жесткость по крайней мере на данный момент.

    В конце концов, число «ничего в рукаве» довольно физиологично.

  • Кофактор $ч=1$ это означает, что нет представления Монтгомери кривой, как следствие, нет быстрой лестницы Монтгомери (требуется элемент порядка 2, т.е. 2|кофактор), Лестница Джойса все еще возможно с более низкой производительностью. В ECDSA это полезно при расчете $[k]G$ так как только $х$ используется координата.

  • Нет необходимости рассматривать атаки малых групп, хотя это не проблема для законных пользователей ECDSA. Если пользователи не являются законными, они могут использовать это для двойного расходования монет, как это было в Крив25519 однако это не относится к кривой ШТАРК.

  • Группа кривых изоморфна $\mathbb{Z_n}$

• $n$ имеет 252-битное двоичное представление, а это означает, что оно имеет около $126$-битовая защита от лучших классических задач дискретного логарифмирования.

• Размер кривой не дает столкновения $к$ если используется хороший генератор случайных чисел. Если кто-то все еще опасается этого, можно использовать детерминированную ECDSA, приведенную в rfc-6979.

• Безопасность накрутки (не связанная с ECDSA); квадратичный поворот этой кривой равен $$y^2 = x^3 + 5^2*x +B*5^3$$ ^*

  • Мощность поворота = "618502788666131213697322783095070105623107215331596699973092056135872020481"
  • Факторы твист-группы = "499669 * 26023817775804638430931 * 278275836047110893120702478691334736277272165979", и это дает безопасность около 158 бит. Умеренный уровень.

• И у нас есть $2*p+2 = Ord(E) + Ord(\text{E_quaratic_twist})$

• $n \neq p$ поэтому это не аномальная кривая где дискретный журнал может быть решен быстро.

а = 1
б = 3141592653589793238462643383279502884197169399375105820974944592307816406665
р = 2^251 + 17*2^192 +1

E = Эллиптическая кривая (GF (p), [0,0,0,a,b])

печать (Е)
Et = E.quadratic_twist()
печать(и)

print("E abelian =", E.abelian_group())
print("E покрутить = ", Et.abelian_group())

карта = E.cardinality()
cardEt = Et.cardinality()

print("мощность E =",карта)
print("мощность E Twist =",карта)


print("факторы E",фактор(карта))
print("факторы Et",фактор(cardEt))

#Генераторная часть не для квадратичного поворота.
#G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
#n = G.порядок()
#print("Порядок генератора =", n)

печать (журнал (карта, 2). n () + 1)

утверждать(2*p+2 == карта + картаEt)

_{^*Квадратичная закрутка, сформированная с помощью QNR 5, к сожалению, не сработала так, как предполагалось. Спасибо Пончо, чтобы указать на это. Я сохраняю уравнение, чтобы можно было увидеть проблему. Вместо этого я использовал квадратичный_твист функция SageMath довольно медленная.}