Topic: Математика и алгоритмы биткоина. - page 6. (Read 17569 times)

от 1 до 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140 включительно
(в десятичную систему переводите сами, мне удобнее видеть это число в шестнадцатеричной системе)

Числа вне этого диапазона можно тоже считать приватными ключам, потому что все математические операции
делаются после взятия остатка от деления на 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

А это точно что абсолютно любое число может быть приватным ключем, может есть еще какие то ограничения?

Конечно, переведи в dec и вставь вместо *

Спасибо.
А число 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 так же проверить можно?

Кое что слышал про точку G. В остальном - дуб, но страшно интересно

Не буду вдаваться в ваш ученый спор. Я и половины не понял, что вы сказали друг
другу, так что не могу понять - кто из вас прав. Лучше пойду свежим воздухом подышу.

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


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


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

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


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

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

В биткоине для криптографии выбрана кривая 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!

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

Ну как не применял? Мы же все время на компьютере это применяем - например, при сложении
16-битных чисел мы не просто над числами операцию сложения производим, а операцию сложения
в группе вычетов по модулю 2¹⁶. Ну а на 64-битных процессорах - в группе по модулю 2⁶⁴

Эллиптическая криптография - вообще достаточно недавно появилась - всего-то 20-30 лет назад.
Ну и там основная фишка в проблеме факторизации - умножать числа просто, а разложить число
на множители - хервам.

Да мне-то понятно. Когда читаю. Но вот стоит отвлечься - и опять все из головы вылетает,
то есть уже самостоятельно я это не сформулирую правильно.

Для лирического отступления я бы предложил людям нарисовать эллиптическую кривую на обычном
тетрадном листе в клеточку. Почему бы и нет? Взять P=13, N = 11 и G какое-нибудь выбрать.
А потом посчитать - если мы secp256k1 захотим так на листочке нарисовать - то влезет ли этот
листочек в размеры нашей Вселенной (видимой её части)?

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

Дело в том, что если взять неразрывную кривую и модель приватный ключ - это A, публичный ключ это C = A * B, то резултат произведения A*B может быть очень больших размеров, и их трудно будет описывать в машинном коде.

Проблема в том, что если взять любую точку и начать складывать ее саму с собой, то рано или поздно результат сложения (публичный ключ) нельзя будет описать числом меньше определенного числа бит. Соответственно кривую надо каким-то образом ограничивать.

Разумным ограничением будет переопределение кривой не в евклидовом пространстве, а в простренстве конечного числа целых чисел, подчиняющихся какому-либо правилу, которое не позволяет координатам ни при каких условиях превысить заданной границы (чтобы длина нашего публичного ключа не росла бесконечно). Это легко сделать, если во первых ограничить себя только целыми числами и вспомнить про операцию mod (остаток от деления) на какое-нибудь простое число. Почему простое? Потому что использование простого числа дает возможность определить операцию деления через умножение, поскольку результатов деления может быть ровно два - 1 и само число). Итак уравнение элептической кривой (которое записано как Y^2=X3+AX+B) мы перепишем в форме:
Y^2 mod P = (X^3 + AX + B) mod P

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

Решения такого уравнения, например, для P = 3, А = 0 B =0  будут выглядеть примерно так: (1,1), (2,2), (3,0) и потом, если подставлять X>3, точки на плоскости начинают повторяться, всегда внутри квадрата 0-3 - советую посчитать решения руками для разных наборов P,A и B и нарисовать в тетрадке, чтобы понять, что из-за целочисленного деления - не важно какое х и y я буду брать - точек строго ограниченное количество и они симметричны относительно оси Х, а самое главное - точек всегда ровно P (в моем примере - 3). Если мы вместо P = 3 возьмем P = 5 - точек будет 5. 

Ну, это вы как-то вольно оперируете словами
Что есть "начало", и что тогда "конец", если группа у нас циклическая? Или не циклическая?
А "кривая" на самом деле не кривая (тропинка в лесу, берёза на склоне, итд), а как-то
рассыпанный по плоскости горох?
Я выступаю против интуитивно непонятных формулировок Читатели-дошколята нас не поймут.

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


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

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

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

ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141  (115792089237316195423570985008687907852837564279074904382605163141518161494337)

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



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


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

Группа это пространство чего-либо (например пространство векторов, или точек или слонов), для которых вы определяете операцию сложения. В применении к элептической кривой группа - это множество наборов из трех точек, лежащих на прямой в точке пересечения этой прямой с кривой. "Сумма" этих точек равна нулю (это определение их сложения, которое обладает всеми свойствами сложения). Если взять все-все точки кривой - группа получится бесконечной (т.к. на ней бесконечное кол-во троек точек дающих по определению сложения в группе - ноль. У бесконечных групп - порядок группы не определен. Но мы можем взять не все точки кривой, а только некоторое конечное количество точек. Тогда порядок группы станет конечным и будет определяться правилом выбора тех точек которые мы выберем для построения группы. То есть мы берем из всех "троеточий" только некоторые, которые удовлетворяют конкретному правилу (например берем только троекточие от пересечения с осью Х). Тогда наша группа будет состоять из одного троеточия и ее порядок будет равен 1.

О том как получить порядок группы над конечном полем я напишу чуть позже (сначала разберемся с тем что такое поле). Но сразу спойлер - почему Base Point в ненаглядном взяли такой какой взяли - я не скажу. Примерно вот так это мотивирует светоч:

https://bitcointalksearch.org/topic/m.6020830

А сейчас - спать пора.

Честно сказать, я не понял к кому вы обращаетесь своим длинным постом на какую-то отвлеченную тему.
Если можно, давайте конкретно, у меня остались следующие вопросы:
1. Как посчитать порядок группы эллиптической кривой над конечным полем?
2. Почему порядок подгруппы в secp256k1 выбран числом 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 ? Кто его придумал?

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

Например сложение целых чисел - мы все знаем. Оно обладает свойством коммутативности, ассоциативности и подчиняется правилу сложения.

Сложение векторов в пространстве - уже сильно отличается от сложения целых чисел, хотя так же коммутативно и ассоциативно (т.е. фундаментально без разницы что с чем складывать и в каком порядке), однако правила сложения уже несколько отличаются, т.к. вектор описывается не одним числом а набором чисел (в зависимости от размерности пространства). На плоскости вектор можно описать двумя числами - координатами конца стрелочки протянутой из нуля. Например у вектора тянущегося под 45% направо вверх будет запись (1,1) или (2,2) и т.п. Умножение вектора на число - это помножение всех "координат", его описывающих на число (если это нарисовать, то это будет выглядеть как удлиннение стрелочки без изменения направления). Умножив вектор (1,1) на 2 получим вектор (2,2).


Сложение в применении к элептической криваой определяется совсем иначе - а именно как поиск решения системы уравнений и инвертирования его знака по оси Y.  Одно уравнение описывает кривую, другое - прямую, проведенные через две точки - но это вы уже видимо поняли.
Складывать, разумеется можно только те точки, которые УЖЕ находятся на кривой (т.е. являются решением уравнения кривой при фиксации X или Y в уравнении кривой. Сложить точки с координатами (1,1) и (0,1) на криваой не получится, т.к. они не лежат на кривой ).

Возникает резонный вопрос - что делать в тех случаях, когда точку надо сложить с самой собой, чтобы через такое сложение можно определить умножение? Сложение точки с самой собой предполагает такую прямую, которая проходит через эту едиственную точку на бесконечно малом участке кривой, то есть - касательную. А уравнение касательной, как известно легко вычисляется, расчетом производной. То есть если мы имеем произвольную точку на кривой, мы считаем ПРОИЗВОДНУЮ элиптического уравнения в этой точке (производная - это уравнение прямой). Потом мы решаем систему уравнений этой прямой и уравнения кривой, инвертируем по знаку и получаем ту точку, которая будет "суммой" A+A или иными словами A*2. Вот так определяется умножение. Чтобы посчитать 3*А - можно прибавить к 2A еще один A.

Как видите, если вчитаться в этот абзац "умножение" на кривой это адский гемморой, но он несколько облегчается, ели организованно использовать память и свести умножение к сложению. Например чтобы посчитать 9A можно посчитать 2A+2A = 4A, потом посчитать 4A+4A = 8A а потом прибавить 1А.

Если А это произвольное число длинной в 256 бит (~10^77), то, чтобы посчитать его произведение на любое другое число (НА КРИВОЙ) потребуется операций сложения не более чем 510. (Если очень надо - можно это доказать).

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

Теперь о криптографии. Допустим есть A - это старотовая точка. И есть B - множитель. Есть так же произведение A * B = C.
Если я вам дам С, то сможете ли вы узнать сколько раз B сложили с самим собой (A), чтобы получить С? Оказывается, что нет, потому что не определено (во всяком случае на данный момент) операции деления и единственная опция поиска A это тупо складывать B с самим собой в надежде получить С.

Ну вот тут мы и подходим к шифрованию.
в моем примере A - это ваш приватный ключ, С - это ваш публичный ключ а B - это стартовая точка на кривой, по которой вы начинаете свое путешествие из точки A в точку C, складывая B c самим собой по правилу сложения которое я описал выше.  

Надо глубже, или так понятно?

Хорошо. Я ту статью не читал. Давайте на примере разберемся
Есть, допустим, группа - множество чисел от 0 до 6 или попросту радуга
{
  красный=0,
  оранжевый=1,
  желтый=2,
  зеленый=3,
  голубой=4,
  синий=5,
  филипетовый=6
}

Определим операцию умножения элемента на число. Для этого ⊕ определим как сложение по модулю
красный ⊕ красный = красный
оранжевый ⊕ желтый = зеленый
зеленый ⊕ синий = оранжевый
и так далее. Ну, а умножение элемента на число - через сложения.
Что такое синий * 3?
Это ( синий ⊕ синий ) ⊕ синий = зеленый ⊕ синий = оранжевый.

Но операцию ⊕ можно определить и иным способом. Как-нибудь изъебнуться с простыми
числами и всякими степенями. Особенно хорошо получается, когда в группе простое
количество элементов. Семь - как раз простое.

Ну я только конспектирую тут эту статью https://habr.com/post/335906/

Сейчас дошел до главы "Скалярное умножение и циклические подгруппы". За что купил, как говорится...

А вот и порядок подгруппы (число возможных публичных ключей) там нашел. Глава "Эксперименты с ECDH"

0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141

Оказывается Сатоши числа эти не придумывал с потолка, а тупо скопипастил из либы OpenSSL.