Математика и алгоритмы биткоина. - page 5.

kzv

legendary

Activity: 1722

Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange

Quote from: fxpc on December 19, 2018, 06:25:53 AM

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: fxpc on December 19, 2018, 06:25:53 AM

Насколько подписывание быстрее или медленнее алгоритма проверки подписи? Нигде не могу найти бенчмарков.

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

fxpc

sr. member

Activity: 1316

Merit: 420

KTO EC/\U HUKTO?

amaclin1

sr. member

Activity: 770

Merit: 305

Quote

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

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

Code:

const std::string strMessageMagic = "Bitcoin Signed Message:\n";

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

amaclin1

sr. member

Activity: 770

Merit: 305

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

Например, компрессированные ключи появились в версии 0.6.0
https://bitcointalksearch.org/topic/version-060-released-74737

Про префиксы публичных ключей тут:
https://bitcointalksearch.org/topic/the-prefix-byte-0x04-in-public-keys-42384
Там главная фраза "Correct. The public key format is managed by OpenSSL, bitcoin treats it as a black box."
Потом уже решили что зависеть от OpenSSL нельзя.

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

kzv

legendary

Activity: 1722

Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange

Quote from: lolobit2 on December 19, 2018, 06:01:15 AM

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

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

Quote

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

lolobit2

newbie

Activity: 14

Merit: 0

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

kzv

legendary

Activity: 1722

Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: kzv on December 19, 2018, 05:17:20 AM

В вашем коде надо дальше копать функцию BN_mod_inverse ( _r, _s, bn_order, _c )

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

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

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

kzv

legendary

Activity: 1722

Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange

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

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: kzv on December 19, 2018, 04:47:16 AM

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

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

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: kzv on December 19, 2018, 04:47:16 AM

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

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

Code:

//  static const MyKey32 inv ( const MyKey32& s );

const MyKey32 MyKey32::inv ( const MyKey32& s )
{
  BIGNUM* _r = BN_new ( );
  BIGNUM* _s = BN_bin2bn ( s.constPtr ( ), 32, BN_new ( ) );
  BN_CTX* _c = BN_CTX_new ( );
  BN_mod_inverse ( _r, _s, bn_order, _c );      // обратная величина
  MyKey32 r;
  BN_bn2bin ( _r, r.ptr ( ) + ( 32 - BN_num_bytes ( _r ) ) );
  BN_CTX_free ( _c );
  BN_free ( _s );
  BN_free ( _r );
  return r;
}

kzv

legendary

Activity: 1722

Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange

А как работает функция 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

Quote

            "scriptSig": {
               "asm": "3045022100ceb27a63c2d831c4db72be3b6447cb844aa2d891c05fb1fbe871d82335b0c2cc02204 020c58ea9c84149d59aa3451c6436d226f806a1f92496859f123593a64ebe04[ALL] 039ba9494f5ec12628aec689ea46ce4cb14e2d828e1c317640612aec0f748c4d1e",
               "hex": "483045022100ceb27a63c2d831c4db72be3b6447cb844aa2d891c05fb1fbe871d82335b0c2cc022 04020c58ea9c84149d59aa3451c6436d226f806a1f92496859f123593a64ebe040121039ba9494f 5ec12628aec689ea46ce4cb14e2d828e1c317640612aec0f748c4d1e"
            },

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on December 18, 2018, 04:23:04 PM

Это не уравнение. к - это точка на эл.кривой.

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

Quote

Обратная ей точка это координата y с противоположным знаком.

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

Code:

static void test ( )
{
  const MyKey32 k ( MyKey32::brain ( "correct horse battery staple" ) );
  qDebug ( ) << "k=" << k.toStringRev ( );
  const MyKey32 k1 ( MyKey32::inv ( k ) );
  qDebug ( ) << "k1=" << k1.toStringRev ( );
  const MyKey32 m ( MyKey32::mul ( k, k1 ) );
  qDebug ( ) << "m=" << m.toStringRev ( );
}

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

Code:

k= "c4bbcb1fbec99d65bf59d85c8cb62ee2db963f0fe106f483d9afa73bd4e39a8a"
k1= "29e775d4509f0844eb5ee81fd21bc408c2e1f791edb1436fe0e2ad4b3285ee2c"
m= "0000000000000000000000000000000000000000000000000000000000000001"

n00by

member

Activity: 172

Merit: 11

n00by

member

Activity: 172

Merit: 11

Quote from: kzv on December 18, 2018, 02:17:59 PM

Я хз, как это уравнение решать, но как-то оно довольно быстро решается и из него находят k^-1

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

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

Quote from: kzv on December 18, 2018, 02:17:59 PM

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

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

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

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

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

kzv

legendary

Activity: 1722

Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange

Я тут почитал про цифровую подпись еще. Подписывание сообщение у большинства нормальных людей проходит следующим образом:
1. Берем случайное целое k число от 1 до n-1 где n - порядок группы (в биткоине 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141)
2. Вычисляем

Quote

P = k*G = random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) * 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

3. Из результата вычислений пункта 2 (из числа P) берем первые 32 байта - это типа координата X точки P или назовем это X_p
4. Вычисляем первые 32 байта подписи

Quote

r = X_p mod n = первые32байта(k*G) mod n = первые32байта(random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) * 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

5. Вычисляем вторые 32 байта подписи. Только тут понадобится сообщение и приватный ключ подписывающего.
5.1. Хэшируем сообщение
z = sha256(message)
5.2. Вычисляем "мультипликативную инверсию" числа k. Для этого надо решить уравнение
( k^-1 * k ) mod n = 1
или

Quote

( k^-1 * random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) ) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 = 1

Я хз, как это уравнение решать, но как-то оно довольно быстро решается и из него находят k^-1
5.3 Вычисляем вторую часть подписи с помощью закрытого ключа D_a

Quote

s = k^-1 * (z + D_a * r) mod n = k^-1 * (sha256(message) + D_a * первые32байта(random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) * 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

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

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

Quote

D_a = r^-1 * (s * k - z) mod n = первые32байта_подписи^-1 * (вторые32байта_подписи * k - sha256(message)) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140

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

Quote

k = (z1 - z2) * (s1 - s2)^-1 mod n = (sha256(message1) - sha256(message2)) * (вторые32байта_подписи1 - вторые32байта_подписи2)^-1 mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140

Ну а когда вычислим k, то см. Алярм1.

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

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

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

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

fxpc

sr. member

Activity: 1316

Merit: 420

KTO EC/\U HUKTO?

Quote from: zan0za on December 14, 2018, 08:35:41 AM

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

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

zan0za

jr. member

Activity: 46

Merit: 3

Quote from: amaclin1 on December 12, 2018, 11:32:47 AM

Quote from: zan0za on December 12, 2018, 10:46:55 AM

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

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

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