Регистрация Войти
Рейтинг:1
RocketNuts avatar Crypto

Каков порядок образующей точки G=9 на кривой 25519?

флаг vn
RocketNuts

В Curve25519 у нас обычно есть эта генераторная точка или базовая точка:

Gx = 9
Гр = 14781619447589544791020593568409986887264606134616475288964881837755586237401
или же:
Гр' = р - Гр 
   = 43114425171068552920764898935933967039370386198203806730763910166200978582548

Где р = 2^255-19, размерность простого поля Fp, в котором мы оцениваем кривую.

Каков порядок этой образующей точки?

т. е. каково наименьшее n, чтобы nG = 0.

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

Поэтому мне интересно, каков порядок G, и, возможно, сложнее: как я могу найти это сам? (как только у меня будет значение, я могу легко его проверить, это намного проще)

258
0 + 0
knaccc avatar
флаг es
knaccc
$2^{255}-19$ — это не порядок кривой, это размерность простого поля. Порядок кривой — это количество возможных точек на кривой, равное $8p'$, где $p'=2^{252}+27742317777372353535851937790883648493$
2
Ответить
RocketNuts avatar
флаг vn
RocketNuts
Спасибо за исправление моего неосторожного неправильного названия, да, конечно, p в Fp (или Z/pZ) не имеет ничего общего с кривой.
0
Ответить
kelalaka avatar
флаг in
kelalaka
[Обобщите математическую проблему, лежащую в основе взлома открытого ключа Curve25519] (https://crypto.stackexchange.com/a/50414/18298)
0
Ответить
kelalaka avatar
флаг in
kelalaka
Обман для нахождения порядка [Как вычисляется порядок точки для эллиптических кривых над GF (p)] (https://crypto.stackexchange.com/q/40726/18298) и выше был обманом для названия.
0
Ответить
Рейтинг:5
Ievgeni avatar Crypto
флаг cn
Ievgeni

Согласно этому источник, точки этой кривой представляют собой группу мощностей $8\cdot p'$ с $p':=2^{252}+27742317777372353535851937790883648493$.

Это число можно вычислить с помощью Алгоритм Шуфа или более эффективный Алгоритм Шуфа-Элкиса-Аткина.

Затем, по Теорема Лагранжа, и потому что $р'$ является простым (можно проверить с помощью любого эффективного теста на простоту), он подразумевает все точки $P$ может быть только порядок $o_P= 2^{i_P}\cdot p^{\prime j_P}$, с $0\leq i_P\leq 3$ , и $0\leq j_P\leq1$.

Мы можем вычислить $p'\cdotG$ с быстрым возведением в степень (Алгоритм возведения в квадрат и умножения также называется Double-and-Add в контексте эллиптической кривой), и обратите внимание, что он равен $\mathcal{O}$ нейтральный элемент кривой.

Мы делаем вывод, что $o_G$ получатель чего-то $G$ делит $р'$. затем $i_G= 0$.

Так как $G\neq \mathcal{O}$, $o_G\neq 1$, тогда $j_G=1$.

Мы заключаем, что $G$ в порядке $o_G = p'$.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

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

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