Рейтинг:2

Модуль p в криптографии на основе эллиптических кривых

флаг vn

Для выполнения криптографии на основе эллиптических кривых между сторонами все уравнения эллиптических кривых рассматриваются в форме $\bмод р$?

Например, $secp256k1$ Биткойн-кривая уравнения $у^2=х^3+7$ использует $\bмод р$, куда $p=2^{256}-2^{32}-977$.

Рейтинг:5
флаг ng

Для выполнения криптографии на основе эллиптических кривых между сторонами все уравнения эллиптических кривых рассматриваются в форме $\bмод р$?

Да для secp256k1, когда речь идет о координатах точек, но не для каждой кривой.

Эллиптические кривые, используемые для криптографии, работают с координатами в Галуа Филд $\mathbb F_q$. Он должен держать $q=p^m$ для некоторого простого $р$, и $m\ge1$. $\bмод р$ случай соответствует $м=1$, и является наиболее распространенным и признанным (Эд25519, secp256k1, секп256р1 являются примерами). Другим относительно распространенным выбором является $д=2^м$, см., например. сек2в2 раздел 3. Также используются другие значения, например. $q=9767^{19}$ там.

$2^м$ имеет преимущества в скорости в аппаратном обеспечении или когда умножение целых чисел является дорогостоящим из-за распространения переноса по битам. В более общем смысле, $п^м$ с остатком в размере $р$ и $м$ может упростить параллельную реализацию.


Дополнительно: даже для кривых с координаты в $\mathbb F_p$ с $р$ простое число как secp256k1, некоторые вычисления с использованием скаляров, которые умножают точки кривой (включая вычисления с использованием закрытого ключа), выполняются по модулю порядка кривой, что часто отмечается $n$ и простые, и отличные от $р$.

poncho avatar
флаг my
Да, вы можете использовать эллиптические кривые, определенные над полями расширения (которые для аудитории являются полями $\mathbb{F}_{p^k}$ для $k > 1$); с другой стороны, кривая secp256k1, о которой он спрашивал, и, если на то пошло, кривые, которые мы в настоящее время используем в 99% случаев, являются простыми кривыми, то есть кривыми, которые мы можем выполнять в наших вычислениях по модулю $p$
Рейтинг:3
флаг in

Штрих в определении кривой Secp256k1

Премьер $р$ является частью проектирования, анализа и определения кривой, которая определяет $\mathbb{F_P}$. Если кто-то использует другой $р$ затем у них есть разные кривые, которые необходимо проанализировать, затем опубликовать и распространить для связи с этой кривой.

Для того, чтобы общаться $р$, уравнение кривой (здесь $(а,б)$), базовая точка $G$, бесконечно удаленная точка, порядок кривой $n$, и кофактор $ч$ предусмотрены в стандарте.

это шестерка $T = (p,a,b,G,n,h)$ и для Secp256k1 является;

  • ''p'' = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • = $2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

Кривая $E: y^2 = x^3+ax+b$ над $\mathbb{F}_p$ определяется:

  • ''а'' = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • ''b'' = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

Базовая точка G в сжатом виде:

  • ''G'' = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 а в несжатом виде:
  • ''G'' = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6858B419 8F44419 Наконец, порядок «n» в «G» и кофакторе:
  • ''n'' = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • ''ч'' = 01

$а,б,р,г$ достаточно для связи, однако нет необходимости пересчитывать остальные.


Небольшой пример, чтобы продемонстрировать, что они совершенно разные.

К = ГФ (19)
E = Эллиптическая кривая (K, [0,7])
печать (Е)
печать (E.order())
печать (E.abelian_group())

тогда $n = 12$ и группа кривых изоморфна $\mathbb{Z}_6 \oplus \mathbb{Z}_2$

К = GF(31)
E = Эллиптическая кривая (K, [0,7])
печать (Е)
печать (E.order())
печать (E.abelian_group())

тогда $n = 21$ и группа кривых изоморфна $\mathbb{Z}_{21}$

Конечно, можно найти два кортежа, $(p_1,a_1,b_1)$ и $(p_2,a_2,b_2)$ так, чтобы они имели одинаковые группы точек.Это не проблема, просто нужна стандартизированная шестерка.

Мы ограничены $\mathbb{F}_p$?

Если вы спрашиваете, мы всегда должны использовать основное поле $\mathbb{F}_p$ тогда ответ нет. Любое конечное поле $\mathbb{F}_{p^m}$ хорошо, если безопасно и быстро. Видеть Фгриё ответ для деталей.

Порядок группы кривых

Некоторые кривые, такие как secp256k1, имеют простой порядок (т. е. количество точек простое). Другие, такие как Curve25519 и Curve448, не имеют простых порядков. Это помогает им иметь представление Монтгомери, которое имеет быстрое скалярное умножение на лестницу Монтгомери. У других может быть менее эффективная лестница Джойса.

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

Модуль в скалярном умножении

скалярное умножение $[к]П$ на самом деле это означает добавление $P$ сам $к$-раз. Более формально;

позволять $k \in\mathbb{N}\обратная косая черта\{ 0\}$

\начать{выравнивать} [k]:&E \к E\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ раз}}.\end{align}

и будучи личностью $[0]P = \mathcal{O}$.

При вычислении этого мы используем порядок точек $P$, если кривая имеет простой порядок, такой как secp256k1, то все элементы, кроме единицы, имеют один и тот же простой порядок. У нас есть это равенство

$$[k]P = [k \bmod \text{ord}(P)]P$$

и мы используем $P$с первоочередным приказом смягчить атаки.

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

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