Почему протоколы криптографии на основе эллиптических кривых зависят от фиксированных кривых?

я узнаю о Эд25519. Это зависит от множества магических значений: Конечное поле порядка $2^{255}-19$, конкретная эллиптическая кривая над этим полем, конкретная точка на этой кривой. Это в отличие от Диффи-Хеллмана или RSA.

Почему это? И наоборот, почему DH не исправит простое число и генератор, или RSA не исправит, скажем, $n = pq$ стоимость?

Я подозреваю, что в случае DH и RSA очень легко генерировать новые экземпляры протокола. Мы много знаем о простых числах, поэтому легко генерировать новые, а также, наоборот, если бы мы зафиксировали простое число для всех экземпляров протокола, мы могли бы проанализировать его и сломать.

Значит ли это, что в случае эллиптических кривых не так просто найти кривую и генератор?

Причина, по которой нельзя исправлять конкретную кривую/группу/что-либо, над чем нужно работать, заключается в том, что это вредит безопасности, а именно, если:

1. Существуют атаки с предварительным вычислением — атака, которая стоит $Т$ который может быть амортизирован в течение $n$ пользователей теперь эффективно стоит $т/n$. За $n\приблизительно$ 1 миллиард потенциально может изменить расчет затрат/выгод.

2. Злонамеренный орган по стандартизации может стандартизировать «слабую» кривую/группу/что угодно, например, кривую с бэкдором или ту, которая каким-то образом просто слабее «случайной».

Это проблемы для некоторых сложных задач — например, проблема LWE и DH с конечным полем допускают атаки с предварительным вычислением. Для LWE это используется как оправдание для отказа от стандартизации «Матрицы LWE». $\mathbf{А}$".

При этом может быть полезно исправить конкретную кривую/группу/что угодно. А именно:

1. Вам больше не нужно генерировать его во время протоколов, сохраняя некоторую эффективность.
2. Вам больше не нужно его передавать (или можно передавать краткое описание постоянного количества стандартизированных объектов), что позволяет сэкономить некоторую полосу пропускания.
3. Вы можете оптимизировать операции для этой кривой/группы/что угодно, сохраняя эффективность
4. Труднее случайно выбрать "слабые" кривые/группы/что-то еще.

Что касается того, почему кривая 25519 принимает именно такую ​​форму, см., например, Безопасные кривые страница для некоторых описаний/сравнений различных свойств кривых.

По этим вопросам:

Почему DH не исправляет простое число и генератор

Они делают в определенных приложениях. Вот список групп DH с конечным полем, используемых в TLS. (включая 1.3). Обратите внимание, что с этим нужно быть осторожным — раньше существовали стандартизированные «слабые» группы ($\около 512$ биты), которые на самом деле никто бы не использовал. Их присутствие в этом списке стандартизированных групп привело к Атака в тупике, где против них проводится предварительная атака + сочетается с определенной «атакой на понижение».

Или исправление RSA, скажем, $n=pq$ стоимость?

Непонятно, как вы можете использовать это на практике, так как на самом деле с ним связан только один закрытый ключ, поэтому два разных пользователя не могут использовать один и тот же ключ. $n$ для шифрования. На самом деле, даже если они используют $п, п'$ которые имеют общий фактор, это приводит к атакам (и еще одна статья Нади Хенингер, Добыча ваших P и Q). При этом есть специальные приложения, где это может быть полезно, см., например, эта статья о распределенной генерации модуля RSA для некоторого обсуждения приложений.

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

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

Кроме того, использование предварительно заданных эллиптических кривых означает, что гораздо проще писать реализации с постоянным временем. Это очень важно для онлайн-протоколов, таких как TLS, где можно продемонстрировать возможность использования реализаций с непостоянным временем. это возможное написать общие реализации эллиптических кривых с постоянным временем, но это сложно, и люди практически этого не делают.

Конечно, можно использовать фиксированные группы в не-EC Диффи-Хеллмана; Это делает TLS и SSH. Пока выбрана достаточно большая группа правильной формы, это надежно. Использование фиксированной группы также более эффективно с точки зрения пропускной способности протокола, поскольку параметры не нужно отправлять.

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

Что касается RSA, повторное использование параметров обычно небезопасно. Кроме того, из соображений эффективности закрытый ключ часто включает $р$ и $q$, что немедленно скомпрометирует закрытый ключ любого, кто поделится $N$. Даже если поделиться $N$ не было проблем с безопасностью, потому что $р$ и $q$ не могут быть раскрыты, это было бы гораздо менее эффективно, чем создание новых параметров для каждого пользователя.