Почему эллиптические кривые над бинарными полями используются меньше, чем над простыми?

В практических приложениях эллиптические кривые более $F_p$ кажутся более популярными, чем те, что $F_{2^n}$. Не потому ли, что операции над простыми полями выполняются быстрее, чем над $F_{2^n}$ для того же уровня безопасности?

Может быть, это мое воображение. Я просто вижу гораздо больше открытых проектов, использующих эллиптические кривые. $F_p$ но не так много $F_{2^n}$.

Безопасность: у двоичных полей больше векторов атаки, чем у простых полей.

Дискретный журнал на ECC с бинарным полем не прерывается. Это не причина. Бернштейн сказал;

история безопасности для непростых полей (например, бинарных полей расширения) более сложный и менее устойчивый чем история безопасности для простых полей, как показано Фреем в 1998 г., Годри в 2002 г. — Хесс — Смарт, Годри в 2009 г. и Пети — Квискватер в 2012 г.

В результате выбор простых полей уменьшает количество векторов атак, поэтому возникает меньше проблем с безопасностью.

• 2002 Конструктивные и деструктивные аспекты спуска Вейля на эллиптических кривых

  В этой статье мы подробно рассмотрим кривые, которые возникают в методе Гэлбрейта и Смарта для получения кривых в ограничении Вейля эллиптической кривой над конечное поле характеристики два составной степени. Мы объясняем, как этот метод можно использовать для построения гиперэллиптических криптосистем, которые могут быть такими же безопасными, как криптосистемы, основанные на исходной эллиптической кривой. С другой стороны, мы показываем, что это может обеспечить способ атаки на исходную криптосистему эллиптических кривых с использованием последних достижений в изучении проблемы дискретного логарифмирования на гиперэллиптических кривых.

• 2004 Исчисление индексов абелевых многообразий и проблема дискретного логарифмирования эллиптических кривых Пьеррик Годри

  Мы показали, что асимптотически эллиптические кривые, определенные над полями расширения малых степеней, являются слабее чем те, которые определены над простыми полями или большими полями расширения простой степени.

• 2012 О полиномиальных системах, возникающих из спуска Вейля Кристоф Пети и Жан-Жак Кискватер

  Они рассмотрели ECDLP в поле двоичного расширения и показали, что их алгоритм превосходит общие алгоритмы дискретного логарифмирования для $N >2000$. Рекомендуемые размеры пока не затронуты!

Патенты Certicom (и др.)

Еще одним важным вопросом является патенты что в основном у Certicom есть/было.

Первый Цитата Брюса Шнайера

«Certicom, безусловно, может претендовать на владение ECC, — сказал нам Шнайер. «Алгоритм был разработан и запатентован основателями компании, и патенты хорошо написаны и сильны. Мне это не нравится, но они могут претендовать на право собственности».

• Один из патентов Certicom касался эффективного $\operatorname{GF}(2^n)$ умножение в нормальном базисном представлении; Патент США 5 787 028.. Этот патент был выдан в 1998 году и окончательно истек в 2016 году.
• У АНБ было несколько патентов на $\operatorname{GF}(2^n)$, тоже; [1] [2] [3] [4], однако срок их действия истекает намного раньше, так как АНБ не платило сборы (я думаю, что это было преднамеренно)

Текущий этап атак для сравнения

Если мы посмотрим на Проблемы ECC Certicom

• Кривая Коблица над $2^{108}$ сломан в 2000 году.
• А $109$ кривая простого бита сломана в 2002 году.
• Кривая над $2^{109}$ сломан в 2004 году.
• 131-битные вызовы Binary или Prime еще не сломаны.

Помимо этих проблем;

• Проблема дискретного логарифмирования 117,35-битной эллиптической кривой на двоичной кривой была нарушена в 2016 году Bernstein et. все

Приземленный факт, смещающий баланс в сторону $\mathbb F_p$ заключается в том, что стандартные процессоры 1990-х и начала 2000-х годов часто имели инструкции по умножению, но не имели аппаратной поддержки для продукт без переноски, обращая преимущество $\mathbb F_{2^k}$ имеет в оборудовании. И арифметика в $\mathbb F_p$ были тщательно изучены для RSA и DSA. Поэтому понятно, что люди начали использовать $\mathbb F_p$, и тогда не было веских причин для изменения. Возможно (в этот комментарий) Патенты Certicom на ECC в $\mathbb F_{2^k}$ отогнал прожекты. Кроме того, все больше людей понимают арифметику в $\mathbb F_p$, и никого никогда не увольняли за его выбор.

С точки зрения безопасности, я думаю, есть разумное ощущение, что с $\log_2p\приблизительно м$, ECC в основном поле $\mathbb F_p$ безопаснее, чем в бинарном поле $\mathbb F_{2^m}$. Причины, которые я понимаю, следующие:

• Для данного $м$, есть около $\приблизительно0.69\cdot2^м/м$ выбор для $р$. Все конечные поля данного порядка изоморфны. Так $\mathbb F_{2^m}$ — это особый случай, а в криптографии особые случаи редко бывают более безопасными.
• По крайней мере, в аппаратном обеспечении добавление точки ECC значительно дороже в полевых условиях. $\mathbb F_p$ чем в поле $\mathbb F_{2^m}$. Возможно, «жестче» означает «безопаснее», а «жестче» означает «менее безопасно» было бы довольно удивительно.
• Решение ДЛП в мультипликативной подгруппе поля $\mathbb F_p$ намного сложнее, чем для $\mathbb F_{2^m}$, как видно из записей ($795\текст{-бит}р$ в $\mathbb F_p$, $м=30750$ в $\mathbb F_{2^m}$ ). Опять же, возможно, более сложный DLP в мультипликативной подгруппе подразумевает более сложный DLP в группе ECC, и было бы удивительно, если бы он подразумевал более легкий DLP в группе ECC.

Есть и другие причины безопасности. Я имею в виду первые три пули другой ответ. Я их едва понимаю, чтобы сказать, что они не ведут к общей атаке на ECC в $\mathbb F_{2^m}$, например на кривых в раздел 3 sec2v2. Но все же разумно, что они внушают беспокойство.

В конце концов, как и большинство, я принимаю Мудрость Safecurve :

2006 Бернштейн заявил, что простые поля «имеют то преимущество, что сводят к минимуму количество проблем с безопасностью для криптографии с эллиптическими кривыми». Точно так же стандарт Brainpool и стандарты NSA Suite B требуют простых полей. Существует общее мнение, что простые поля являются безопасным и консервативным выбором для ECC.