Quote from: Destrodream on December 04, 2018, 01:39:54 PM

Короткий ответ:

Quote

Почему порядок подгруппы в secp256k1 выбран числом 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 ? Кто его придумал?

1. Множитель конечной группы P выбран последним простым числом меньше чем 2^256 :

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F (115792089237316195423570985008687907853269984665640564039457584007908834671663)

Скорее всего вы правы. Везде еще пишут, что
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2²⁵¹ - 1 = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1
Но я что-то нигде не нашел доказательства того, что это число простое. Но тут думаю можно поверить. В википедии кстати пишут что это Число Мерсенна и типа равно 2²⁵¹ - 1 Однако там же в вике в статье про этого Мерсенна, про число 2²⁵¹ - 1 ничего не известно.
Короче тут поверю на слово: это наиболее близкое простое к 2²⁵⁶

Quote from: Destrodream on December 04, 2018, 01:39:54 PM

Это и есть порядок группы, если брать все элементы из группы.

Тут фэйл!
Число "p" это размер конечного поля. Этот размер не равен порядку группы (хотя по Теорема Хассе эти числа близки). Порядок группы вычисляется алгоритмом Шуфа, в который входными данными идут: параметры эллиптической кривой и этот самый размер поля.

Quote from: Destrodream on December 04, 2018, 01:39:54 PM

Однако, все решили не брать, а брать только элементы начиная с определенной точки G (я писал - я хз как именно эту точку выбрали). То количество точек станет меньше, и их останется

ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 (115792089237316195423570985008687907852837564279074904382605163141518161494337)

тоже простое число, но чутка поменьше, потому что у кривой "откусили" начало.

Пальцем в небо и опять фэйл в каждой строчке.
1. Точку G взяли не совсем с потолка, а по определенному правилу, следуя определенной логике. Смотрите конец моего поста.
2. Я лично не уверен, что число ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 простое. Есть доказательство?
С простыми числами всегда так: в общем случае чтобы проверить является ли число простым, придется перебрать все простые числа которые могут быть делителями. А когда перебирать придется 2 в степени дохуя, то как вы надеюсь понимаете, перебор займет времени тоже чуть более чем овердохуя.
Хотя злые языки говорят, что есть алгоритмы которые умеют довольно шустро проверять число на простоту. Так что тут поверю на слово опять.

Quote from: Destrodream on December 04, 2018, 01:39:54 PM

Этот порядок - определяет кол-во точек на исходной элептической кривой.

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

Фэйл.
Как я уже выше написал и повторю еще раз: порядок группы не выбирается, он вычисляется. А число ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 это не порядок группы, а порядок подгруппы. В общем случае (в 99.99% случаев) эти порядки не совпадают. Порядок подгруппы связан с порядком эллиптической кривой теоремой Лагранжа, согласно которой порядок подгруппы это делитель порядка исходной группы.

Quote from: Destrodream on December 04, 2018, 01:39:54 PM

Quote

Как посчитать порядок группы эллиптической кривой над конечным полем?

2. Наверное логичнее задавать порядок группы изначально чем его считать. Если посмотреть на уравнение которым описывается кривая - оно содержит в себе mod P, вот P - это и есть простое число, которое определяет кол-во точек и порядок группы. Если группу урезать, то кол-во точек уменьшится.

Фэйл почти в каждом слове (

Внимание, правильный ответ

В биткоине для криптографии выбрана кривая secp256k1 группы SECG. Почему именно эта кривая? Просто Сатоши Накомото так захотел и все! Гевин вроде говорит, что они че-то там обсуждали, но я что-то сомневаюсь. Либо Гевин и есть Сатоши. Тогда все сходится. Но сейчас не об этом...

Итак в выбранной кривой параметры можно скопипастить из библиотеки OpenSSL. Эта библиотека, как это ни странно, существовала задолго до биткоина и эта либа долго входила в зависимости первых версий битка. Вот эти параметры

p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
a = 0
b = 7
X_G = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
Y_G = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
h = 1

Теперь, глядя на эти параметры и вдумчиво читая статью на хабре, можно сделать некоторые выводы... Но сначала еще одна выдержка из статьи.
В статье есть глава "Поиск базовой точки". В этой главе дан пошаговый алгоритм: как искать базовую точку G ! Вот этот алгоритм:
1. Вычисляем порядок N эллиптической кривой
2. Выбираем порядок n подгруппы. Чтобы алгоритм сработал, число "n" должно быть простым и быть делителем числа "N"
3. Вычисляем кофактор h = N / n
4. Выбираем на кривой случайную точку P
5. Вычисляем G = h * P
6. Если G = 0 равно 0, то возвращаемся к шагу 4. В противном случае мы нашли генератор подгруппы с порядком "n" и кофактором h

Вот теперь можно еще раз проследить за логикой чуваков, которые вставили магические параметры в OpenSSL откуда эти параметры скопипастил Сатоши. Думаю логика была такая:
1. У нас универсальная либа, давайте добавим кривую где y² = x³ + 7
2. Возьмем какой-нибудь польшой размер поля. 256 бит вроде достаточно много.
Деление по модулю p (которое необходимо для операций сложения и умножения) может выполняться быстрее, если в качестве p выбрать простое число, близкое к степени числа 2. Значит возьмем максимальное 256-битное простое число
p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
3. Вычислим порядок получившейся группы.
Получается
N = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
4. Хотелось бы чтобы число точек в подгруппе было максимальным. Нам повезло, потому что N - получилось простым числом и мы можем выбрать кофактор = 1 и тогда порядок подгруппы будет равен порядку группы! Получаем
n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
h = 1
5. Внимание, магия!
Выбираем на кривой случайную точку P. Поскольку кофактор = 1, то G = P

То есть у кривой secp256k1 группы SECG есть замечательное свойство: абсолютно любая точка на кривой secp256k1 группы SECG, генерирует подгруппу с кофактором 1!