Bitcoin Forum

Тут в теме Амаклина зашел разговор об эллиптической криптографии биткоина: как она устроена внутри. Было предложено вынести обсуждение в отдельный топик. Предлагаю обсудить именно в кодерах, потому что тут уместны ссылки на исходники и могут быть предложены альтернативные алгоритмы.
Итак начать предлагаю с поста Амаклина где он ответил на мой вопрос


Итак, чтобы получить пару биткоин ключей (приватный + публичный), алгоритм будет следующий:
1. Придумываем любое 256-битное число. Это и будет приватный ключ.
2. Умножаем приватный ключ на магическую константу G которая на самом деле вектор с координатами
x= 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
y= 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


G*приватный_ключ = публичный ключ.

Теперь остается вопрос: как это умножение устроено?
Понятно, что
G*приватный_ключ = G+G+G+... (сложить столько раз, скольки равен приватный_ключ)

G*1 = G (по определению единицы)

Осталось понять: как вычислить хотя бы
G*2 = G+G

Ну, складывать по этой формуле мы затрахаемся будем пока солнце не погаснет.
Есть более эффективные процедуры умножения.
Запишем приватный ключ в двоичной системе счисления
Допустим, он равен ...000101011
То есть это G + 2G + 8G + 32G + ...
А это уже гораздо проще вычисляется

Вобщем-то я сам нагуглил ответ на вопрос.


То есть чтобы найти G*2 надо провести касательную к G
Поскольку график функции известен, то уравнение касательной найдется элементарно

y = f'(x₀)(x-x₀) + f(x₀)

Где
f(x) = sqrt(x³ + 7)
x₀ = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

Правильно?

А трудно проверить самому что ли?
Пишешь программу, вычисляешь pubkey для privkey=2 и проверяешь совпал ли
результат с тем, который выдает bitaddress.org

(PS. Я не знаю правильно или нет. Я сам задавался этим вопросом, но сейчас не могу
найти тот топик, где мне объясняли. А я не выучил тот урок)

Это понятно. Напишу на досуге.
Меня сейчас математика заинтересовала...

Если уравнение касательной правильное, то приравняв его к уравнению кривой мы должны получить квадратное уравнение, корнями которого являются публичный и приватный ключи?

 (sqrt(x³ + 7))'|_x0(x-x₀) + sqrt(x₀³ + 7) = sqrt(x³ + 7)

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

Блин, ну вы даете.
Вот это должно снять почти все вопросы:
https://habr.com/post/335906/ (https://habr.com/post/335906/)

Возможно 4 глава прояснит ситуацию
https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf

Да мы нубланы в этом вопросе. Кто ж сомневается? Нельзя объять необъятное и впихнуть невпихуемое.
Читать научно-популярные тексты - это, конечно, здорово.
Но еще перипатетики поняли, что обсуждение даёт очень эффективные результаты.

Ссылку на эту тему скиньте.

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

Итак, первое, что я понял из статьи - это как таки математически найти публичный ключ если кривая обычная без всяких модулей.
Вот формула для точки на кривой:

X_R = M² - 2 * X_P
Y_R = 3 * M * X_P - M³ - Y_P

где

M - это тангенс угла касательной к эллиптической кривой в точке с координатами (X_P, Y_P). То есть производная в этой точке от функции

f(x) = sqrt(x3 + 7)

В статье пишут (лень проверять), что она равна

M = 3 * X²_P / (2 * Y_P)

Продолжаю чтение... )

Формулы для эллиптических кривых разрабатывают математики-криптографы. Вроде бы, буква "k" в названии "secp256k1" означает, что используется эллиптическая кривая Коблица. Наверно, поэтому Сатоши Накамото при создании Bitcoin выбрал именно эту эллиптическую кривую, а не, например, кривую "NIST P-256", скорее всего, имеющую бэкдор.

Вот хороший англоязычный интернет-ресурс, посвящённый асимметричной криптографии ECDSA:
http://safecurves.cr.yp.to/

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

https://bitcointalk.org/index.php?topic=2431229.220

Так, продолжим чтение статьи хабра...

Я нашел в статье, формулы сложения двух векторов (двух точек, как угодно) в случае когда эллитическая кривая на самом деле никакая не кривая, а набор точек. Как и следовало ожидать, эти формулы абсолютно идентичны обычным (когда кривая это кривая). Просто добавляется деление по модулю числа "p".

X_R= (M² - X_R - X_Q) mod p
Y_R = (Y_P + M * ( X_R - X_P ) ) mod p

Понятие "наклон" тут весьма условно, но формула для него тоже такая же как для настоящего геометрического тангенса касательной, только по модулю.

Если точки P и Q разные, то  M = ( Y_P - Y_Q ) * ( X_P - X_Q )^-1 mod p

Если точки P и Q совпадают, то M = 3*X²_P * (2 * Y_P)^-1 mod p

Итак, чтобы перемножить два числа, нужно провести несколько таких вот операций сложения. Например
G*P = G+G+G+G...[и так P раз]

Ну или число G представить как сумму степеней двойки (перевести в двоичный вид), перегруппировать и получить что-то типа
G*P = 1*2⁵¹²*P + 0*2⁵¹¹*P+...+1*2⁰P

В любом случае, чтобы понять как работает умножение, достаточно понять - как работает сложение.

Со сложением/умножением в общем виде разобрались, идем дальше. Пробуем разобраться конкретно с биткоином и его криптографией.

Внезапно оказывается, что когда от непрерывных уравнений кривых мы переходим к точкам, то этих точек оказывается конечное количество

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

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

Но дальнейшее чтение статьи меня разочаровало... Оказывается, что если умножать на одно и то же число, то результатов умножения будет сильно меньше чем полное количество точек.
На самом деле это очевидно с точки зрения элементарной математики, но блин когда думаешь о каких-то там группах с полями на десерт, то мозги начинают закипать ((
Я лучше на примере опишу, как я понял:
1. В ряду натуральных чисел от 1 до 100, этих чисел 100 штук.
2. Совершенно очевидно, что чисел кратных двойке в этом ряду 50, а чисел кратных 30 всего три и т.д.

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

Как мы знаем, чтобы получить приватный ключ биткоина, надо произвольное число умножить на константу G. Интересный вопрос: чему равен порядок подгруппы порожденной точкой G? Особенно интересен этот вопрос в свете того, что пока непонятно - кто и почему выбрал G таким, какое оно есть...

Продолжаю чтение...

Не, ну тут вы что-то намудрили.
Количество приватных ключей равно количеству публичных ключей
(про разные формы записи пока разговор не ведем)

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

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

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

0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141

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

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

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

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

Надо сложение умудриться таким образом определить, чтобы при умножении всегда выполнялось условие:

если A*B = C то A = C * B^-1 и B = C * A^-1

В вашем примере надо определить сумму так, чтобы при умножении

Если 2*4 = X то 2 = X*4^-1 и 4 = X*2^-1

Соответственно нужно доопределить в целых числах от 0 до 6, чему равны эти числа в минус первой степени.

Тут проще будет на словах: договоримся, что если при умножении A на B получается число больше 6, то ответом будет наименьшее из чисел A или B.
Тогда

1 * 4 = 4
2 * 4 = 2+2+2+2 = 2
3 * 4 = 3+3+3+3 = 3
4 * 4 = 4
5 * 4 = 4
6 * 4 = 4

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

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

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

Сложение векторов в пространстве - уже сильно отличается от сложения целых чисел, хотя так же коммутативно и ассоциативно (т.е. фундаментально без разницы что с чем складывать и в каком порядке), однако правила сложения уже несколько отличаются, т.к. вектор описывается не одним числом а набором чисел (в зависимости от размерности пространства). На плоскости вектор можно описать двумя числами - координатами конца стрелочки протянутой из нуля. Например у вектора тянущегося под 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 самим собой по правилу сложения которое я описал выше.  

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

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

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

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

https://bitcointalk.org/index.php?topic=553091.msg6020830#msg6020830

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

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


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 - это и есть простое число, которое определяет кол-во точек и порядок группы. Если группу урезать, то кол-во точек уменьшится.

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

Ну вообще-то это кривая. Ее визуализация на плоскости - выглядит как горох, но тем не менее это кривая. Просто мы начинаем пытаться понять с рассмотрения непрерывной кривой, а потом ее дескретизируем оператором 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. 

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

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

Я бы хотел сказать что "да это все легко", но это не так, точно не мне. Тут намешано очень много, хоть и не сложной, но разной и в значительной степени абстрактной математики (тут и линал, и теория групп и множеств и геометрия). Мне вот интересно какая голова это все собрала в ECC и, главное, донесла до остальных. Цепочка логических выводов очень тонкая и тянется через одну теорию в другую. Я очень много опустил - куча теорем с доказательствами, которые тянут за собой огромный пласт базовых знаний, которые, я порядком подзабыл.

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

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

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

Скорее всего вы правы. Везде еще пишут, что
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!

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

Вот доказательства:
https://ru.wikipedia.org/wiki/Критерий_Поклингтона
https://safecurves.cr.yp.to/proof/115792089237316195423570985008687907853269984665640564039457584007908834671663.html

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

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

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

от 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

Я думал что должно быть ограничение на чет/не чет или что не должно быть остатка от деления например на 16 и.т.д.
А как тогда получается что все адреса в биткоине начинаются на 1 или 3?
Как потом из числа формируется биткоин адрес в котором присутстуют символы которые не входят в список шестнадцатиричных значений - от A до F?

Держи нас в курсе, хотя нет, не держи, всем похуй. Как получается? Магия блять. Сатоши потомок Гарри Гуддини. Тебе религия запрещает поискать ответы на свои вопросы на форуме или в гугле? Этот топик не для тех кто не в состоянии вбить поисковый запрос, здесь обсуждаются более сложные алгоритмы.

Я тут почитал про цифровую подпись еще. Подписывание сообщение у большинства нормальных людей проходит следующим образом:
1. Берем случайное целое k число от 1 до n-1 где n - порядок группы (в биткоине 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141)
2. Вычисляем
3. Из результата вычислений пункта 2 (из числа P) берем первые 32 байта - это типа координата X точки P или назовем это X_p
4. Вычисляем первые 32 байта подписи
5. Вычисляем вторые 32 байта подписи. Только тут понадобится сообщение и приватный ключ подписывающего.
5.1. Хэшируем сообщение
z = sha256(message)
5.2. Вычисляем "мультипликативную инверсию" числа k. Для этого надо решить уравнение
( k^-1 * k ) mod n = 1
или
Я хз, как это уравнение решать, но как-то оно довольно быстро решается и из него находят k^-1
5.3 Вычисляем вторую часть подписи с помощью закрытого ключа D_a

Такой вот неочевидный алгоритм, кто-то его придумал и он работает. Как видно в алгоритме участвуют два секретных ключа: случайное число k и приватный ключ D_a.

Алярм 1: если кто-то узнает или подберет k, то он вычислит приватный ключ D_a !!!111

Алярм2: если подписать два разных сообщения с одним и тем же (не случайным) k, то опять можно вычислить приватный ключ D_a !!!111
Сначала вычисляем k
Ну а когда вычислим k, то см. Алярм1.

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

Я когда это понял, даже офигел: как так, биткоин не следует стандарту? Но порывшись в исходниках разных либ и самого битка обнаружил, что все таки есть еще один стандарт который называется "Deterministic ECDSA" https://tools.ietf.org/html/rfc6979#section-3

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

Кстати, насколько я понял, сообщения и транзакции клиент биткоина тоже подписывает по разному...
Перед тем как хэшировать сообщение, к сообщению добавляется "магическая фраза" типа "Bitcoin signed message\n". А перед тем как хэшировать транзакцию никаких магических фраз не добавляется. Думаю это такая защита для дурака: чтобы никто не мог с помощью кошелька вместо сообщения подписать транзакцию ))

Ну ты, блин, семимильными шагами идешь в правильном направлении.
Придраться не к чему, только чуть дополню.


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

Там просто берется дайджест сообщения = 256 бит которые сами являются хэшом каких-то данных
Конкатенируется (то есть дописывается в хвост) приватный ключ. И эти 512 бик хэшируются HMAC-ом и sha256
Или наоборот сперва ключ потом дайджест? Ну почитайте сами. Можно вообще через символ брать то и другое
как зубья у расчески.

Вы спросите почему не хэшировать только sha256? Зачем еще hmac какой-то приплели? Тут я сам не очень
понимаю в чем подвох, но смысл такой, что sha256 - блочный алгоритм хэширования и из-за этого обладающий
проблемами при хэшировании вот таких вот кусков, где одна часть известна. Эту проблему с некоторых пор
даже в биткойне заметили. Асик-буст как раз на этом построен. То есть без hmac у нас падает расчетная сложность
брутфорса. А хорошие криптографы такого не любят.

Короче, число `k` для подписывания можно вычислять любым изъебистым способом. Я, например, не парюсь
и в своих программах беру 128 бит от приватного ключа и 128 бит от дайждеста. Если мой приватный ключ подберут
и сопрут 46 центов с кошелька - я не очень расстроюсь. Но если вы хотите обеспечить в своей программе все по
криптографическому стандарту - юзайте RFC 6979.

Это не уравнение. к - это точка на эл.кривой. Обратная ей точка это координата y с противоположным знаком. Нужно только знать к. В той "научно-популярной", как выразился @amaclin, есть геометрический пример как найти эту точку. Я тут много скриптов понаписывал и поотлаживал скрипты многих алгоритмов, используемых в крипте.

Кстати, можно много напридумывать всякого с этим вот k^-1. Я вот увлекся сейчас битовой сложностью sha(256)->hash(160). Там есть где поискать красоты обычной математики.

Не совсем так. sha256 "хеширует" (да простит меня Лобачевский), вычисляет новое большое по определенному алгоритму. Входящее сообщение бьется на блоки по 64 байта (8х8 бит), котрые сами по себе представляют int. Затем происходит сложение/умножение по модулю int каждого такого числа, но 64 раза. В итоге получем на выходе ряд чисел (8х8) которые и дают нам хэш.

АсикБус немного по-другому работает и устроен то по другому. Он что-то сродни вот этой вот штуки: https://en.bitcoin.it/wiki/Mini_private_key_format (https://en.bitcoin.it/wiki/Mini_private_key_format)

Да ну прям.
Это ж скаляр, а не вектор. Так что ну никак это не точка на кривой.
По смыслу - это то же самое, что приватный ключ.

Не. Ну откуда же это обратная по игрек? Это в минус первой степени. То есть k * k^-1 = 1
Вот вам код на скорую руку:

вот такой результат дает исполнение этого кода:

А как работает функция MyKey32::inv ( k ) ?

k это не точка, но ее можно рассматривать как одну из координат точки (x или y). По сути да, k это второй приватный ключ. Когда k умножаем на G то получаем точку, которая по сути то же самое что второй публичный ключ.

Я вот тут еще поизучал либы и понял, что многие статьи безбожно пиздят про то, как публичный ключ связан с адресом.
Тут https://bits.media/bitcoin-address-theory/ и еще в паре мест видел, что
адрес = "1" + ripemd160(sha256("04" + x + y)) + чексумма

На самом деле правильная формула
адрес = "1" + ripemd160(sha256(("02" || "03") + x)) + чексумма

То есть хэшируется не полный публичный ключ, а только его первые 32 байта плюс 2 или 3, то есть публичный ключ в compressed-формате.

Проверка. Берем первую попавшуюся транзакцию из блокчейна
http://chainquery.com/bitcoin-api/getrawtransaction/25e442d4413ed5d013af38b5c9538fda3a9a38ab9c85dfb7d1778d282da26a34/1

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

Есть приватный ключ.
Можно сделать публичный ключ (вектор).
Этот публичный ключ можно записать в стандартизированном представлении [как минимум] двумя способами.
Можно записать обычным способом 04 + x + y
Moжно записать компрессированным способом 02/03 + x

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

Поэтому сейчас [почти] все юзают именно компрессированные публичные ключи.
В вики написано все верно.

В вашем коде надо дальше копать функцию BN_mod_inverse ( _r, _s, bn_order, _c )
Я вобщем сам нарыл уже, что мультипликативная инверсия по модулю может быть найдена двумя способами:
1. Полный перебор
2. Расширенный алгоритм Евклида.

Про перебор понятно, что не наш случай. На досуге почитаю про Евклида. )

ЗЫ про compressed ключи понял. Спасибо.

Ну это из модуля BigNumber библиотеки OpenSSL
https://man.openbsd.org/BN_mod_inverse.3

В такие базовые функции я уже не вдавался - сделал себе класс-обёртку MyKey32
напихал туда всё что использую и забыл. Как она считает там внутре k^-1
- это я не знаю. Видимо, не самая сложная операция. Про алгоритм Евклида я краем
уха слышал, но экзамен по этому вопросу завалю. :)

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

Да мне чисто академический интерес.
Для дела я на node.js насобачился кодить. Там 100500 либ готовых есть и компилировать не надо париться )

Доброго . можно немного оффтопа в академические тёрки.
https://bitcointalk.org/index.php?topic=963373.0
этот эксперимент кто смог повторить?
буду рад любым мыслям

Что-то сомнительный эксперимент имхо. Ибо

Интересно искать вещи в интернете.
Главное - правильно вопрос сформулировать ( это 75% успеха )
Я вот задал в поиске "compressed public keys site:bitcointalk.org" - так вообще кладезь знаний.

Например, компрессированные ключи появились в версии 0.6.0
https://bitcointalk.org/index.php?topic=74737.0

Про префиксы публичных ключей тут:
https://bitcointalk.org/index.php?topic=42384.0
Там главная фраза "Correct. The public key format is managed by OpenSSL, bitcoin treats it as a black box."
Потом уже решили что зависеть от OpenSSL нельзя.

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

Да, да и еще раз да.

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

Насколько подписывание быстрее или медленнее алгоритма проверки подписи? Нигде не могу найти бенчмарков. На js подписывание с использованием ECC в ~2.3 раза быстрее верификации.
https://github.com/indutny/elliptic
Хотелось бы узнать производительность на кодовой базе биткоина.


Про клиент биткоина в топике речи не идёт. Скорее всего в онлайн кошельках дыра не заштопана или была не заштопана и доверчивый хомяк подписывал транзакцию по переводу некой суммы на адрес злоумышленника.

Зависит от имплементации.
Тут некий trade-off между потреблением памяти, временем старта и скоростью присутствует.
Если говорить про либу secp256k1 - ну попробуй собрать https://github.com/bitcoin-core/secp256k1
Там есть вроде бенчмарки. И даже с OpenSSL можно сравнить

Это насколько криворукий кодер онлайн кошелька должен быть? В этом случае подпись онлайн-кошелька будет инвалидной для десктопного кошелька. Думаешь есть вероятность, что какой-то кодер не проверил свою онлайн поделку в первую очередь на коре?

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


Вероятность есть, там ещё те рукожопы. Возможно атакующему нужен был публичный ключ жертвы для вычисления из него и неслучайного значения R приватного ключа. Онлайн кошельки регулярно факапятся с RNG. Имхо, помогло бы даже подмешивание к кривому RNG каких-то пользовательских хешей от хешей, но это не точно. Удивляет что рукожопы не додумались даже до этого, полностью положившись на RNG.
https://www.coindesk.com/hacker-returns-225-btc-taken-blockchain-wallets
https://99bitcoins.com/blockchain-info-wallet-users-get-stolen-service-patched-the-bug-and-assures-it-will-refund-everyone/

Да, сорри. Пьяный был)

Ребят, человеку с уровнем знаний математики на уровне 8 класса сколько лет осталось изучать сей предмет, чтобы понимать все, что вы тут пишите? При условии, что в день есть только 1 час на это дело :)

Я тут на досуге поэкспериментировал с нахождением sha256 от чисел. Получил интересные результаты
Если посчитать все хэши чисел от 1 до 1 000 000, то среди них будут:

62326 хэшей у которых один или больше нулей в начале, среднее число переборов = 16, при этом в 64.3% случаев, требуемое число переборов меньше среднего

3855 хэшей у которых два или больше нулей в начале, среднее число переборов = 259, при этом в 62.4 % случаев, требуемое число переборов меньше среднего

248 хэшей у которых три или больше нулей в начале, среднее число переборов = 3993, при этом в 59.3 % случаев, требуемое число переборов меньше среднего

23 хэша у которых четыре нуля в начале, среднее число переборов = 42065, при этом в 69.6 % случаев, требуемое число переборов меньше среднего


Таким образом оказалось, что решения с заданной сложностью распределены неравномерно. Значит sha256 не дает нормального распределения? Можно ли эту особенность использовать как преимущество в майнинге?
Сейчас на слуху какой-то супер секретный алгоритм асик буст. Кто что про него знает? Я ничего толкового нагуглить не могу.

это на одинарной или двойной SHA?

В майнинге двойная(то есть SHA(SHA(x)) ) - если не трудно, то проверьте то-же самое на двойной?..

Равномерно они будут распределены на значительно больших выборках, чем 1м
То, что у тебя получилось не 256, а 259 - это в порядке вещей, потому что выборка была маленькая
Флуктации рандома, так сказать

А для sha256d результат аналогичен? В каком формате были числа? Не стоит воспринимать равномерность так буквально. "Надёжный" RNG может выдать число 42 хоть 10 раз подряд, а ненадёжный покажет равномерное распределение уже на малой выборке, что говорит о его предсказуемости.

Никакой он не секретный
Несколько оптимизаций, которые позволяют перебрать большее количество вариантов
sha256d от 80 байт заголовка используя меньшее количество вычислений sha256

Эти оптимизации основаны на том что хеширование двойное и HMAC не используется?

Ну ты уж совсем не делай вид, что я на экзамене и тебе зачет сдаю :)
В общем да. Ещё связано с тем, что sha256 - блочный алгоритм. То есть на первом проходе
отдельно и по сути параллельно хэшируются первые 64 байта заголовка блока и отдельно
оставшиеся 16 (я по памяти, лень искать).

Помог бы в этом случае HMAC куда-нибудь засунутый - не знаю. Скорее всего помогло бы иное
построение заголовка блока - чтобы, например, merkle-hash и hash предыдущего блока шли
бы не друг за другом, а "расческой" - то есть байт от одного, байт от другого...

sha256d это то же самое, что sha256 от sha256.
Вот результаты двойного хэширования чисел от 1 до 1000 000

62404 хэшей у которых один или больше нулей в начале, среднее число переборов = 16, при этом в 64.3% случаев, требуемое число переборов меньше среднего

3895 хэшей у которых два или больше нулей в начале, среднее число переборов = 257, при этом в 63.0 % случаев, требуемое число переборов меньше среднего

259 хэшей у которых три или больше нулей в начале, среднее число переборов = 3845, при этом в 61.0 % случаев, требуемое число переборов меньше среднего

16 хэшей у которых четыре нуля в начале, среднее число переборов = 60312, при этом в 68.8 % случаев, требуемое число переборов меньше среднего

То есть результаты практически идентичны одиночному хэшированию.

Рассмотрим несколько способов поиска хэша с заданной сложностью
1. Последовательный перебор nonce от нуля
2. Последовательный перебор не от нуля, а от рэндомной точки
3. Рэндомный перебор nonce.

Теперь каждый из способов отдельно. Для наглядности пусть nonce может изменяться от 0 до 1 000 000 и пусть мы ищем хэш с тремя нулями

Последовательный перебор nonce от нуля.
В этом случае майнер найдет хэш в среднем за 3845 итераций, но с вероятностью 61% итераций будет меньше. То есть Из 100 найденных хэшей, 61 хэш будет найден быстрее чем за 3845 итераций.

Последовательный перебор не от нуля, а от рэндомной точки
В этом случае майнер найдет хэш в среднем за 3845 / 2  = 1923 итераций, при этом с вероятностью 39.4 % итераций будет меньше (это я дополнительно посчитал). То есть из 100 хэшей, 40 будут найдены быстрей чем за 1923 итераций.
 
В два раза быстрее чем в первом случае! Это потому что рэндомное начало, при нормальном распределении, будет падать в среднем на центр отрезка для перебора.
Так же в этом способе с вероятностью 259/1000000 хэш будет найден сразу.

Рэндомный перебор nonce.
В этом случае можно вообще никогда не найти нужный хэш, но с вероятностью 259/1000000 хэш будет найден с первой попытки. Если рэндом распределен нормально, то вероятности должны складываться и значит после 1923 итераций вероятность найти хэш будет уже 50%. То есть из 100 хэшей, 50 будут найдены быстрей чем за 1923 итераций.

В итоге получается, что первый алгоритм самый медленный. Третий алгоритм самый быстрый. Если я ничего не напутал конечно...

Напутал, разумеется.
Возьми другие диапазоны, например от 1000001 до 2000000,
от 2000001 до 3000000 и так далее и попробуй повторить те же результаты.

Хотя если имеется в виду "при этом в хх.х % случаев, требуемое число переборов меньше среднего"
то опять же не значит, что хх.х - это какая-то магия. Это - матожидание. Иногда - находится за
Х переборов, иногда за Y. Чтобы найти среднее значение - надо не просто брать среднее
между Х и Y, а с учетом их встречаемости. Там гауссиана должна получиться в результате.

В других диапазонах все то же самое.
Я для этих целей сделал простенькую страничку
https://trade.multicoins.org/test.html

И в мыслях не было, просто поделился своим предположением :)
Бес меня попутал с этими бустами, мог бы сам догадаться, знаю же про блочность sha256 и про то что при хешировании уникальную соль следует перед паролями ставить именно из-за этого, но подумалось что могли что-то похитрее откопать. Да, в 256-битной версии блок как раз 64 байта.

Наверно HMAC бы не помог, не туда меня понесло. Данные в 64-байтном блоке редко меняются, поэтому буст останется и после "расчёсывания". Возможно эффективнее было бы изменить порядок заголовков при расчёте хеша, чтобы в 64 байта попадал перебираемый nonce.

Тогда в 16-байтовом остатке (80-64) вообще будет константное значение, которое можно будет 1 раз вычислить на пуле

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

Будет, но 16 уже не так эффективно как текущие 64 и в общем-то это гипотетически решаемо. Очень абстрактно - считаем в одном 64-байтном блоке hash предыдущего блока|nonce|..., в следующем 64-байтном блоке считаем merkle-hash|nonce|... и тд.


Видимо версию придётся запихивать во все 64-байтные блоки во избежание такого онанизма.

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

Меркла разве не пул считает? Асик тупо nonce перебирает и хэширует.
Оптимизировать внутри асика можно только алгоритм перебора соли. Или нет?

Поле nonce - всего 32 бита.
Асик на 14 TH/s перебирает этот интервал за доли секунды.
Это, как вы понимаете, бессмысленно - несколько раз в секунду лезть на пул за новыми данными.
Так что давно в протоколе стратум передается дерево меркла (может быть как-то частично подсчитанное)
Асик перебирает не только нонс в заголовке блока - он также перебирает экстранонс
в scriptSig coinbase-транзакции. Считает получившийся merkle-hash, формирует 80-байтовый
заголовок и там уже перебирает нонс.

А асик буст это я так понимаю новый протокол общения асика и пула? Более быстрый протокол. Раз он запатентован, то должно же быть описание патента в открытом доступе?

В гугле забанили? Не, я понимаю, зима, тоска... У меня у самого в жизни какая-то черная полоса пошла.
https://www.asicboost.com/
https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf

Ты понимаешь что эти кудесники патентовать собрались? Я лично нет.
Всё та же полоса что с начала года? Печально.

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


Про патенты я не особо в курсе как и что там патентуют. Подозреваю, что там все основано
на том, насколько обтекаемыми формами будет все описано. Кто-то же патентовал двойной
(или тройной?) клик мышкой? Так почему бы не запатентовать "более технологичный способ
добычи биткойнов"? Мы же можем запатентовать "более технологичный способ добычи железа
из руды в расчете на джоуль потраченной энергии"?

Версию чего? Блока? Ну так от того, что мы дополним данные еще одним фиксированным числом -
хэш этих данных все равно останется фиксированным при пересчете других данных. Опять же - один
раз посчитали, 4 миллиарда раз используем.

Тут можно было бы так сделать: мы хэшируем не 80 байт заголовка блока байт-за-байтом, а сперва проводим
некоторое "усечение длины" - допустим, ксорим (делаем битовую операцию XOR) меркль-хэша и
хэша предыдущего блока. Тем самым у нас не два 64-байтных блока, а один получается (и даже еще
куча места для увеличения размера nonce остается). И вот над этим 64-байтным значением уже
изгаляемся. Это хард-форк, разумеется. Но, я вообще-то, не настоящий сварщик: меня усовершенствования
биткойна и других крипт, анти-асик механизны интересуют чисто гипотетически.

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


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


Не, ты не понял. Сейчас все заголовки блока подаются на вход единоразово по порядку. А можно повторно в каждый 64-байтный чанк на вход подавать версию, nonce и прочее, чтобы нельзя было перебирать версию или nonce в отдельном чанке без пересчёта остальных. Да мне в общем-то тоже монопенисуально на проблемы битка и прочих лохчейнов, не более чем разминка для мозга.

Там два вектора атаки было overt и covert - кажется так назывались.
Я щас уже не вспомню что к чему.
Из того что помню - можно при неизменных полях, в том числе и nonce менять неиспользуемые
биты в версии блока (второй чанк остается без изменений и его пересчитывать не нужно)
Можно в некоторых пределах использовать поле таймстампа блока (но это уже совсем мелочевка)

Можно подобрать два меркль-хэша, которые заканчиваются на одинаковые 4 байта (то, что
зовется "Tail" на рисунке 2 https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf ) и опять же
крутить не nonce, а version. Короче, меня не слушайте, разбирайтесь сами. Я в этом только
"по верхам" понимаю.

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

В целом идея буста мне вполне ясна, а больше чем "по верхам" она интересна лишь Джиханам.


Наоборот намекаю на какую-то позитивную активность в реальном мире, но если хочется как Перельман, то конечно дело хозяйское.

https://youtu.be/GyRAK5Pqv2k

А я хочу разобраться с бустом. Но для начала с классическим майнингом.

Как происходит поиск хэша.

Плюсы тут означают не арифметическое сложение, а добавление информационного блока в конец. То есть 10+20=1020

1. extraNonce = 0
2. коинбейс_транзакция = константа1 + extraNonce + константа2
3. дерево_меркла = хитрый_хэш(коинбейс_транзакция+остальные_транзакции)
4. заголовок_блока = версия + хэш_предыдущего_блока + дерево_меркла + юникс_время + сложность
5. nonce = 0
6. заголовок_блока = заголовок_блока + nonce.

После этих манипуляций получается буфер с размером 80 байт. Чтобы сделать sha256, нужно иметь 128 байт. Поэтому недостающее место заполняем нулями на следующем шаге.

7. заголовок_блока = заголовок_блока + 48_нулей.

8. хэш = sha256(sha256(заголовок_блока))

Если хэш не удовлетворяет сложности, то нужно продолжать перебор. Перебираем сначала nonce (добавляем единицу и идем в п.6), а когда nonce кончатся, то добавляем 1 к extraNonce и идем в п.2

Так работает классический асик-перебор. Все правильно?

Еще раз повторяю. SHA256 - блочный алгоритм. Грубо говоря,
а) считаем сперва первые 64 байта от 80
б) потом вторые 64 байта. (16 плюс паддинг)
в) потом считаем sha256 от того что получилось (потому как у нас sha256d)
г) сравниваем, если не подошло, увеличиваем nonce на 1
д) идем не в (а), а сразу в (б)

Это то что очевидно. Есть менее очевидные оптимизации

Вот как я понял оптимизацию асик буст.

sha256 можно описать примерно так:
1. Разбить буфер на 64 байтныйе куски
2. С каждым куском сделать какую-то хрень
3. Хрени от кусков объединить и сделать с результатом другую хрень.

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

Для буфера в 128 байт, хэширование можно записать так:

Асик буст так и делает.

Алгоритм следующий
1. Пул раздает асикам разные nonce
2. Для асика nonce = константа, юникс_время = константа, сложность = константа. Тогда если асик сам с собой договорится, что последние 4 байта дерева меркла это тоже константа (например нули), то тогда для асика последние 64 байта заголовка блока это тоже будет константа. Вуаля, для этой константы можно сэкономить время на вычисления хэшей!

Итак имеем для асика sha256_step(последние64байта) = константа

3. extraNonce = 0
4. коинбейс_транзакция = константа1 + extraNonce + константа2
5. дерево_меркла = хитрый_хэш(коинбейс_транзакция+остальные_транзакции)
6. Если последние 4 байта у дерева меркла не нули, то увеличиваем extraNonce и идем в п.3
7. заголовок_блока = версия + хэш_предыдущего_блока + первые28байт_дерева_меркла + последние64байта.
8. хэш = sha256( sha256_final( sha256_step(первые64байта) + константа ) )

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

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

Либо я чего-то не понимаю, либо ты не понял принцип. ExtraNonce и дерево Меркла перебирать дорого, а в каждой итерации с бустом вертят только то что можно без предварительного хеширования легко менять пока диапазон не кончится. И лишь когда он кончится вертят extraNonce и дерево Меркла, а затем снова перебирают "мелочь" в диапазоне.

Дорого. Но оно того стоит, похоже.
Давай с простого начнем.
Находим (используем парадокс дней рождения) два меркл-дерева, хэши которых совпадают в 4 последних байтах.
Что это нам дает? То что мы можем сэкономить 4 миллиарда вычислений второго блока, если параллельно
будем перебирать nonce - последние 16 байт блока будут одинаковыми в двух параллельных процессах.

Плюс к этому - для каждой вычисленной второй части можно прокручивать в цикле версию блока. То есть опять же экономия.

А что мешает сделать тупо повтор блока?

После того, как хоть 1 хэш с заданной сложностью найден(сложность вроде раз в 2 нед пересчитывается?) - уже известно какой блок(то есть данные на входе, которые по сути сворачиваются SHA до объема внутренней памяти!) дает хешь с нужной сложностью - остается только его повторить...

Одинарная или двойная SHA значения не имеет - это просто f(x)

То есть если y = f(x1) = f(x2) в случае если x1 = x2.   (точнее они не равны, но эквивалентны для SHA)


Остается только потусовать транзакции чтобы найти такой-же экв. для SHA блок...

Иди, мальчик, учи уроки. Не мешай дяденькам.

Точно, зря я в однопотоке рассматривал, в многопотоке намного эффективнее. Но насколько я понял, в каждой итерации мы перебираем именно последние 16 байт, а отдельные 64 байта для каждого потока вычисляем единожды за ~4 миллиарда итераций.

Что значит прокручивать версию блока в цикле? Придётся же заново пересчитывать первую часть для каждого потока.

Имеется в виду, что дешевле перебирать версию блока вместо ExtraNonce, потому как в случае перебора ExtraNonce нужно каждый раз вычислять ещё и корень дерева Меркла, а в случае перебора версии, корень дерева Меркла вычислять не требуется.

Перебор версии называют оvert AsicBoost, перетасовку транзакций с целью сохранения последних 4-х байт корня дерева Меркла называют соvert AsicBoost. (https://blog.bitmex.com/an-overview-of-the-covert-asicboost-allegation-2/)

https://blog.bitmex.com/wp-content/uploads/2017/09/Diagram-1-1024x888.png

Про версию я сразу не догнал. Какой примерно диапазон получим, если покрутить в ней неиспользуемые биты?

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

Вот эти приватные ключи дают один и тот же публичный:

ffffffffffffffffffffffffffffffff5d576e7357a4503bbfd25e8cd0364141
и
00000000000000000000000000000000a2a8918ca85bb0000000000000000000

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Но могу привести кое-какие количественные оценки данного действа:
В подгруппе эллиптической кривой порядка биткоина может быть сгенерировано 2^131 степени таких ключей.
Сразу оговорюсь, что клиент их не генерирует, а вот сторонний софт вполне себе.

Ну и собственно их генерирует сеть (половина нулей слева дает хороший шанс попробовать найти привкей)

Да и еще немного накину матана вам в мозг.

Вот здесь https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=2ahUKEwiyjIvc-tngAhVpxIsKHf2EC9EQFjABegQICBAB&url=https%3A%2F%2Fistina.msu.ru%2Fdownload%2F18836198%2F1gCJiV%3A9tP1ODSVO_-fEn5MoWaXrXJJl8E%2F&usg=AOvVaw17vEKPcPZScYZ4jWRHDgJM (https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=2ahUKEwiyjIvc-tngAhVpxIsKHf2EC9EQFjABegQICBAB&url=https%3A%2F%2Fistina.msu.ru%2Fdownload%2F18836198%2F1gCJiV%3A9tP1ODSVO_-fEn5MoWaXrXJJl8E%2F&usg=AOvVaw17vEKPcPZScYZ4jWRHDgJM) диссертация к.м.н по криптографии, в которой есть сравнение сложности алгоритмов "зашифровать" для эллиптических кривых.

Так вот, по первым оценкам алгоритм "захешировать" гораздо сложнее.

Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая)
Что будет если взять остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 ?
(можно просто вычесть столбиком - даже без калькулятора)
Лень считать, уверен на 100% что получится 0x00000000000000000000000000000000a2a8918ca85bb0000000000000000000

Оба ключа записаны в hex. Ключи разные. Числа в инт'е
115792089237316195423570985008687907853053774472357734211582463631972694901057
и
216210193282829828977300490454533406720

(подсказка: циклическая группа)

берется только при подписи, но не при генерации привкея

при генерации мы в группе p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

Генерация привкея по определению число из диапазона от 1 до
0хFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Твоё 256-битное число не удовлетворяет этому условию. То, что некоторые программы
могут гипотетически генерировать такие приватные ключи ничего ровным счетом не
добавляет и ничего не меняет, так как при вычислении и публичного ключа, и подписи
сначала все берется по модулю


Да генерировать мы можем хоть 100500-битное число и считать его приватным ключом!
Все равно никто не узнает что у нас на бумажке в сейфе записано!
Публичный ключ и подпись строятся при взятии приватного ключа по модулю
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

https://en.bitcoin.it/wiki/Private_key

То есть настрогать таких пар (и троек, и пятерняшек) я могу не глядя миллион.
Берем приватный ключ и добавляем к нему число
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141
Вуаля!

При генерации все числа берутся по модулю 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f.
То есть тебе никто не запрещает взять в качестве ключа 512-байтовое число. Однако модуль в расчетах будет взят по числу выше.

А вот генерация подписи ограничена именно тем числом, которое ты указал. Там модуль 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

Где ты это взял? Ну бред же!

Нифига, нифига.. Не бред.
Во первых в определении эллиптической кривой. Там есть параметры:



Так вот мы работаем в поле чисел р. То есть публичный ключ считается по модулю р. Однако подписать мы можем только ключом из n (Subgroup order). То есть 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Ну а я что сказал?
Первым делом вычисляем остаток от деления числа на n (Subgroup order)
Потом делаем все остальное.
Те два числа которые ты дал на этом первом шаге станут одним числом

Можешь сам проверить чему будут равны публичные ключи от пар:

0x1 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142
0x2 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364143
0x3 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364144

Тут больше интересно следующее. Я в свое время сканировал этот форум и гитхаб на ключи (оставленные в любой записи) на предмет забывчивости разрабов/дилетантов.
Понаходил всякого и, в том числе, hex'ы ключей в диапазоне 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f


Ну и, сначал интуитивно, а потом с помощью диссертации на прошлой странице нашел, что искать траты на скрипт hash160(sha256d(priv)) гораздо затратнее, чем искать траты на pubkey.

Непонятно что тут интересного.
Я повторю мысль.
Приватный ключ - он только у тебя. Как ты его запишешь - в хексе, октале или на языке сомалийских пиратов -
это твоя личная половая драма.
Кода ты вычисляешь публичный ключ и сигнатуру - ты должен брать число из интервала [1..n-1]
Многие программы (в том числе OpenSSL) не парятся, а берут по модулю от того, что ты им дал в параметре
Некоторые (например https://www.bitaddress.org ) проверяют входящее значение на попадание в интервал.

От того, что ты нашел 256-битные числа за пределами диапазона ровным счетом никаких бенефитов нет.

Интересно вот что. Откинув всю математику (которая только в 2-3 формулах существует) для эллиптической кривой, возможно ли зная точку на этой кривой и максимальную битовую длину числа "родителя" найти это число "родитель"?
Мне кажется это возможным. Математических доказательств обратного до сих пор ни у кого не появилось.
Сейчас вот и исследую это поле, ну и циклические группы вдобавок.

Я тут уже немного не понимаю. Точка на эллиптической кривой - это [x,y] - то есть публичный ключ.
Мы уже выяснили, что он делается умножением приватного ключа p на число G
По публичному ключу определить приватный - в настоящий момент мы не знаем как решать эту задачу, кроме
как перебором, который вряд ли закончится до угасания солнца.

Твой вопрос звучит так: если мы определенно знаем, что приватный ключ из диапазона [a..b] -
может ли это упростить нашу задачу? Для определенности, a=1
По-моему, нет.
Разумеется, с учетом того, что диапазон меньше - то и перебор у нас меньше и быстрее получится.
То есть при b=1000 нам надо перебрать только 1000 значений, а не 2²⁵⁶

Я просто выдвигаю гипотезы, которые сам же потом и стараюсь опровергнуть или принять на вооружение.

Гипотеза 1: В настоящее время существует ненулевое количество непотраченных выходов с приватных ключей в диапазоне чисел от 2^0 до 2^131+-1 (которые являются разницей характеристикой поля Р и порядком циклической группы n).

Примерами таких выходов могут служить вот эти: https://www.blockchain.com/btc/tx/5d45587cfd1d5b0fb826805541da7d94c61fe432259e68ee26f4a04544384164 (https://www.blockchain.com/btc/tx/5d45587cfd1d5b0fb826805541da7d94c61fe432259e68ee26f4a04544384164), а также многие другие из моего списка, но которые уже были использованы.

Гипотеза 2: Алгоритмы формирования публичного ключа "не теряют информацию", а следовательно, должны существовать алгоритмы восстановления приватного ключа. Прямой перебор наиболее уебищный из алгоритмов. Я бы вот этих вообще загнобил, увидев их на улице https://bitcointalk.org/index.php?topic=1306983.msg49486901#msg49486901 (https://bitcointalk.org/index.php?topic=1306983.msg49486901#msg49486901)

Ну и Гипотеза 3: Алгоритм взятия дискретного логарифма функции эллиптической кривой "легче" алгоритма нахождения коллизии sha256, либо старших алгоритмов хэширования.

Вот на этих гипотезах пытаюсь на пальцах (Ведь еще перипатетики поняли, что обсуждение даёт очень эффективные результаты(с)amaclin1) развить до чего то применимого.

В случае с ECDSA действительно известны более эффективные алгоритмы (https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/) нахождения приватного ключа, чем простой перебор. В теме, на которую вы сослались, arulbero демонстрирует виртуозное владение алгоритмом "baby-step, giant-step" для нахождения частично известного приватного ключа из публичного ключа.

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

Перечитайте еще раз гипотезу №1. Упоминание транзакции-пазла очень хорошо ложится на нее. Выходы с ключами от 2^61 до 2^131 можно считать попутной нагрузкой (в случае если они будут найдены).
Полный перебор - это адово вычислительно сложная задача.
Таким образом мы переходим к гипотезе 2.

Где асики для ECC? Нет их. А почему их нет? Потому что профит не предсказуем?

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


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

Давайте посчитаем вероятность нахождения адреса с непустым балансом.
Адресов всего у нас 2¹⁶⁰
непустых из них, допустим, 16 миллионов, то есть 2¹⁰ * 2¹⁰ * 2⁴ = 2²⁴
То есть вероятность найти непустой адрес перебирая хеши 2^-136

Сравните с вероятностью найти подходящий хэш для блока - это что-то порядка 2^-80
Вы понимаете разницу в этих цифрах?
Без учета того, что для вычисления публичного ключа, адреса и сравнения с базой непустых адресов
потребуется колоссальное количество дополнительных операций. И асик, который перебирает sha256d
хэши со скоростью 14 Th/s просто в тысячи раз замедлится, если его еще нагрузить этой работой


Давайте без "кажется", а?
Вот здесь есть графики: http://bitcoin.sipa.be/
Перебрали что-то в районе 10²⁷ хэшей
Сравните какое это количество от 2¹⁶⁰

[Здесь надо картинку с солнцем запостить для тех, кто еще не видел её]

непустых сейчас 50 с хвостиком миллионов. Никто не говорит, что нужно перебирать все. Ну и да, половину диапазона можно убрать по причине распределения 0 и 1 в битовой записи.
В общем не убедил.


в консоли питона выполнил

получил 2⁹²

При использовании ECDSA secp256k1 длина приватного ключа равна 256 битам, но стойкость этой эллиптической кривой равна 128 битам. Атакующему для решения проблемы дискретного логарифмирования требуется выполнить работу по перебору 2¹²⁸ вариантов (методом Полларда, и т.п.) при условии, что с целевого BTC-адреса была совершена хотя бы одна исходящая транзакция, то есть известен публичный ключ, являющийся координатами [X, Y] точки на эллиптической кривой secp256k1.

По-моему, в Bitcoin нет никакого смысла нахождения коллизии SHA256. Возможно, Вы имели в виду коллизии RIPEMD160, которым хешируются BTC-адреса на конечной стадии генерации.

В любом случае, да, решение проблемы логарифмирования на эллиптической кривой является менее ресурсоёмкой задачей по сравнению с перебором хешей.

Более ресурсоемкой. (Да, вот такой я зануда)

Ну да. Можно перебирать биткойн-скрипты вида PUSH_20_байт_мусора OP_DROP OP_TRUE
И ждать пока hash160 ( ) от скрипта станет 385cR5DM96n1HvBDMzLHPYcw89fZAXULJP (https://www.blockchain.com/btc/address/385cR5DM96n1HvBDMzLHPYcw89fZAXULJP)
Ну или другому P2SH-адресу - список непустых адресов можно составить

Да, про половинный интервал я умолчал специально. Вы все правильно поняли.

Как-то прям голословно выглядит.

А, я не понял. Вы нашли что-то эффективнее брутфорса? Тогда вы правы, а я нет.

Эти функции являются односторонней функцией, которая означает, что если a = function (b), то нет практического способа найти b, если вы знаете a.
и нет практического способа получить private_key из public_key.

Способы есть, их много, все они на переборе. Самые современные алгориты выполняются за (0.97+О(1))sqrt(N), где N - порядок подгруппы.
Это теоретические оценки, которые на кривых малых порядков бьются с практическими показателями.
Но дождаться результата для secp256k1 вы, к сожалению, пока не сможете.

В смысле: "сумели разложить"?
Что конкретно китайцы сделали с этим числом?

Факторизацию числа делает любой ленивый с помощью компьютера. Функция divmod в любом языке программирования дает идентичный результат. Другое дело EC шифрование и связанное с ним.
Согласен, что знание публичного ключа существенно увеличивает шансы стырить приватный, но они все еще призрачные (в сравнении с количеством значений). Однако, факторизация заранее неизвестного целого числа это задача, у которой нет решения в принципе.

Простите за тупой вопрос: китайцы годятся тем, что сумели разложить на простые множители число 1 005 973 ???
Это которые китайцы? Те, что строили Великую Стену или их прадедушки?

А, ну так бы сразу и говорили: "китайские ученые на якобы квантовом компьютере научились делать то, что любой школьник умеет делать калькулятором".
Вообще конечно вещь захватывающая: несколько лабораторий в мире заявляют, что у них есть настоящие квантовые компьютеры и даже предоставляют онлайн доступ для всех желающих попробовать свои алгоритмы. Беда в том, что эти типа компьютеры состоят из менее чем сотни кубитов и поэтому придумать хоть какой-то рабочий алгоритм для такого  - это само по себе научное открытие!

В 2010 году обычные компьютеры смогли разложить на множители 768-битное число. Чтобы сделать то же самое квантовыми компьютерами, нужно 147,454 кубитов (так в вашей ссылке написано).

Смотрим прогресс кубитов по википедии
В 2001 году IBM сообщила, что у нее есть 7-кубитный квантовый компьютер
В 2017 году заявлено об изобретении 53-кубитного квантового компьютера
В 2018 году типа изобрели 72-кубитный квантовый компьютер
В 2019 китайцы обрадовали 89-кубитным компьютером.

За последние три года, прогресс действительно на лицо: в среднем добавляют 15 кубитов в год!
Похоже и правда, сроки когда квантовый компьютер сможет делать то же, что компьютеры прошлого - слегка сдвигаются... На 10 000 лет в будущее примерно ))

Да-да. Это в статье из вашей ссылки написано. А в википедии написано, что IBM сделала 7-кубитный компьютер еще в 2001 году...


Ага, их тысячи миллионов и на их разработку уже потрачено и еще потратят не один миллиард, но за последние 20 лет все они вместе взятые смогли решить задачу которую грамотный пятикласник способен решить за 10 минут с помощью блокнота, ручки и китайского калькулятора )))


Я вижу вы большой специалист в этой области? Помогите мне тоже ее изучить.

я такие числа потрошил на простые множители еще на IBM PC XT лет 20 назад...

получи фашист гранату...


Меняюсь - ссылку на перевод статьи с научного на человеческий ;)

https://arxiv.org/pdf/1108.3445.pdf

Пока что квантовые компьютеры похожи на такую секту и пирамиду, по сравнению с которой биткоин - детские шалости )

e-mail взломать не пробовали?   С паролем всего-то 5-10 лоховских символов...


PS  после N попытки подбирать дальше просто не сможете.  N = например 5

PPS  в SCO-юниксе тоже такой прикол был - после каждой попытки задержка увеличивалась...

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

Дали в школе домашку - помогите решить:

Необходимо написать алго вычисления (1 / a) mod p, используя "Euclidean Inversion"  :'(

Условия:
* а и р тут 256 битные,  
* р - константа ( p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F )
* нету ограничений на число циклов и разрядность машины, на которой это решается (пусть разрядность будет даже 256)
* ALU машины не умеет делать операции в floating point
* ALU машины не умеет делать деление (+ , - и умножение по-прежнему доступны)


mod p традиционным способом можно было бы сделать через итеративное вычитание и проверку условия (1/a) <= p, но как реализовать используя "Euclidean Inversion" непонятно, именно этот кейс не рассматривается в интернетах при описании (есть целая книжка по ней  https://math.ru/lib/files/pdf/mp-seria/035_zhizhilkin.pdf )

нутром чую, тут надо какие-то итеративные численные методы задействовать, но не получается наткнуться - вводных мало(

Где вы тут гуру увидели?
Весь этот топик, по сути, попытка домохозяек разобраться в том, что написано в хабро-статье из седьмого поста https://bitcointalk.org/index.php?topic=5075972.msg48243414#msg48243414

Я вот из всего обсуждения вынес для себя единственную основную мысль:

публичный_ключ = рэндом * константу

все остальное (хитрость алгоритма умножения) это уже заумные частности.

По конкретно вашему вопросу у меня сразу возникают вопросы встречные: как вы определяете операцию деления по модулю? Вся криптография вроде как на том и строится, что в пространстве модулей умножать можно легко, а вот делить - хер вам, никак кроме перебора умножений.

Обычно для имплементации очень больших чисел используются специальные классы, позволяющие работать с массивами 32-х или 64-битных чисел как с одним числом. Если рассматривать, например, распространённый язык программирования JavaScript, который по умолчанию функционирует в интернет-браузерах, то можно применять следующие JS-библиотеки BigInteger и BigNumber, например:
https://github.com/silentmatt/javascript-biginteger/
https://github.com/MikeMcl/bignumber.js/



По всей видимости, Вам нужно расчитать число по формуле: a^-1 mod p

В общем-то, это стандартная функция, которая применяется в криптографии RSA и называется ModInverse. В протоколе Bitcoin эта криптография не задействована, хотя при обилии недостатков и высокой ресурсоёмкости у RSA есть положительные характеристики.

Можете посмотреть реализацию Вашей задачи, например, здесь:
https://stackoverflow.com/questions/26985808/calculating-the-modular-inverse-in-javascript

Вот более подробная статья на английской Википедии, но перевода на русский язык пока нет:
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Какие на данный момент существуют алгоритмы
для решения задачи дискретного логарифмирования на несуперсингулярной эллиптической кривой в конечном поле?
Имеются ли полиномиальные или хотя-бы субэкспоненциальные алгоритмы? А как насчёт квантовых алго?