Topic: 2 ^ 256 закрытых ключей (Read 823 times)

Ты ошибся.
2^256 = 16^64 = шестьдесят четыре английские буквы фэ.

ну так это число 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 и есть 2 в 256
переводим в dec получаем 115792089237316195423570985008687907852837564279074904382605163141518161494337
делаем логарифм - получаем 2 в 256.

не понимаю, то ли ты ошибся, то ли я.

Спасибо, я, благодаря A-Bolt, уже все осознал ).P2SH вообще к ключам не привязан, в redeem скрипте может быть и 15 публичных ключей, и ни одного.Не только в "Sweep", но и при простом импорте (кстати, Electrum почему-то явно не предлагает выбрать, как трактовать введенный приватник, что новичков, не заметивших кнопку "info", постоянно ставит в тупик).

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

Это очень важно для осознания. В любой криптографии с открытым ключом у нас есть пара privkey - pubkey . И адреса это просто разные методы хэширования и превращения оригинального публичного ключа (о чем писали выше неоднократно).
Поэтому, в какой то мере, одному публичному ключу соответствуют сразу несколько адресов в разных системах. Отличие составляет лишь P2SH, так как адреса "3" получаются не прямо из публичного ключа, а из redeem script-a, и при одинаковом публичном ключе они могут отличаться.

Это кстати очень хорошо видно по Electrum: при использовании функции "Swap", Electrum просит указать в каком формате необходимо превратить импортируемый приватник: p2pkh, p2wpkh, p2wpkh-p2sh .

Ну вот теперь все значительно понятнее стало)))

---

Вот теперь стало немного понятнее, спасибо. Нужно почитать еще будет об этом.

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

Тут дело не в том, что хеш-функция может быть неидеальна и давать коллизии, а в том, что размерность хеша меньше размерности ключа (20 байт против 32). То есть это как пытаться 20 яблок положить в 10 корзин - по одному в корзину поместить никак не получится. Поэтому на каждый немультиподписной адрес приходится в среднем 2⁹⁶ приватных ключей. Если представить емкость размером с Землю, заполненную горохом, то количество горошин примерно и будет равно количеству приватников, "отпирающих" каждый адрес ). И тем не менее, я не слышал, чтобы были найдены хотя бы два ключа, дающих одинаковый хеш.

Можно както объяснить на пальцах, чтобы простому обывателю тоже было понятно.

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

Темный лес. Я всегда думал что если хэш одинаковый то и ключ полностью одинаковый, иначе были бы отличия в хэше. Не понимаю.

По двум причинам:

1. Даже если брутфорсер уже нашел 2⁹⁰ коллизий, нет никакой гарантии что очередной проверяемый ключ даст уникальное значение, а не будет новой коллизией. Все равно придется перебирать все ключи, без оглядки на ранее найденные коллизии.

2. От ключа могут зависеть не только P2SH/P2PKH выходы, но и другие скрипты. Даже если у двух конкретных ключей один хэш, им может соответствовать разный набор P2PK и raw multisig выходов, поскольку при их создании не используется функция hash160. Проверка по хэшу на оба таких ключа даст положительный результат, т.е. что баланс есть, но для полной траты балансов придется использовать разные ключи. Это актуально, потому что во времена продажи пиццы по 10 тысяч биткойнов P2PK транзакции использовались довольно часто, и на таких выводах висит очень много монет.

Мне, видимо, следовало выразиться яснее. Я имел в виду, какой смысл в знании, что пар ключ-хеш не 2¹⁶⁰, а больше?

Вы написали:Поясните, почему это множество нас интересует, и почему полезно?

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

Я оценил исходя из стартового поста, в котором написано что "коллайдер" ставит своей целью перебор множества из 2¹⁶⁰ ключей. Можно почитать, что там у них написано в планах, но вряд ли стоит заморачиваться.

А никакого практического смысла нет.

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

С быстрым квантовым компьютером, оснащенным достаточным количеством памяти, было бы веселее и можно было бы щелкать такие ключи пачками, за время заваривания чашки чая. Но таких нет и пока даже близко непонятно, как их придумать.

А какой в этом практический смысл?

У нас есть 2²⁵⁶ закрытых ключей, из каждого получаем 2 открытых ключа - сжатый (33 байта) и несжатый (65 байт).
Все эти ключи (2²⁵⁷) хешируем HASH160, получается 2¹⁶⁰ уникальных адресов и 2⁹⁷ коллизий.

Где здесь ошибка? Кстати, количество пар у меня получилось 2²⁵⁷, а не 2¹⁶¹.

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

Не всё равно. Даже если у хэша длина 1 бит, соответствий (ключ, хэш) всё равно будет 2¹⁶¹. Просто в этих парах будут коллизии, то есть одинаковые значения хэша для разных ключей.

Как такое возможно? Это все равно что 4 значения вместить в одном бите, 8 в двух и так далее.

И да и нет. На самом деле пространство больше, потому что для легаси адресов разрешено использование несжатых публичных ключей. Поэтому за их счёт на 2¹⁶⁰ закрытых ключей приходится 2¹⁶¹ значений hash160. Из которых половина валидна для всех типов выходов (p2pkh, P2SH, p2wpkh), а другая валидна только для p2pkh и не может применяться для двух других типов выходов. Вернее, может, но такие выходы нельзя будет потратить.

Все три типа адресов (P2PKH, P2SH и P2WPKH) используют в качестве хеш-функции на последнем этапе одну и ту же функцию - RIPEMD160. Её выходной диапазон значений - от 0 до 2¹⁶⁰. Адрес любого типа - это всего лишь вот этот 160-битный хеш, ничего кроме 160 бит в адресе нет. Поэтому все эти адреса помещаются в одном общем пространстве - 2¹⁶⁰.

Исключение - P2WSH-адрес, где в качестве хеш-функции используется только SHA-256 и пространство адресов получается  2²⁵⁶.

Оценка "более" или "менее" в отношении надежности в данном случае представляется как штука сильно теоретическая. Криптостойкость 128 бит, что на современном железе в принципе невзламываемо ни перебором, ни криптоанализом, если подписывание делается с использованием нормального ГСЧ. До появления квантовых компьютеров все эти коллайдеры - не более, чем смехотворная имитация бурной деятельности, результат известен заранее. Если ребята делают это всерьёз, то по ним плачут ударные дозы аминазина. Если же под попил донатов, то схема понятна, и остаётся поднять пальцы вверх и оценить грамотный развод спонсоров.

Хорошо, я понял, спасибо за ликбез.

Так сколько адресов в итоге нужно считать в первом посте?

Получается, 2¹⁶¹ P2(W)PKH + 2¹⁶⁰ P2WPKH-P2SH = 1.5 * 2¹⁶¹. Так?

P2(W)SH получается самый надежный тип адреса - его никто не будет даже пытаться ломать всякими "коллайдерами" )).

Когда я захотел просканировать пространство приватных ключей в диапазоне:
от 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
до 00000000 00000000 00000000 00000000 00000000 00000000 00000000 FFFFFFFF
на наличие транзакций, содержащих адреса, соответствующие этим приватным ключам, я сделал это так:

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

Далее просканировал все выходы транзакций блокчейна и выцарапал из них хеши публичных ключей в виде, опять же, 20-байтных последовательностей, записав их в два файла: один - для P2PKH-выходов, второй - для P2WPKH-выходов.

Ну, и наконец, проверил наличие хешей из двух последних файлов в первом файле. Заметьте, мне ни разу не понадобились преобразования в base58check и bech32. Для каких задач, по-вашему, нужны эти преобразования?

Ок, я понимаю, что 20-байтный хеш в P2PKH и P2WPKH одинаковый, можно ли после преобразования в удобный формат считать их одним адресом хотя бы в контексте расчетов в первом посте? Я думаю, что нет. Ведь при кодировании в base58check еще два SHA256 считать приходится, так что конвертация из bech32 в base58check проходит лишь в два раза быстрее, чем полная генерация P2PKH-адреса из ключа (про скорость кодирования в bech32 не знаю, чек-сумма как-то хитро там считается и, кажется, без хешей).

Они и могут. Лайткойн плохой пример, это копипастный шиткойн, который не принёс и никогда не принесёт ничего нового.

Да, но функционально не эквивалентен и потому этот вариант не имеет смысла учитывать наравне с остальными

По крайней мере, адрес P2PKH (1...) и P2PWKH (bc1...) - это один и тот же хеш публичного ключа RIPEMD160(SHA256(pubKey)), только первый преобразуется в base58check, а второй - в bech32, исключительно для человекочитаемого отображения. Внутри выхода транзакции этот хеш в виде 20-байтной последовательности будет выглядеть одинаково и для P2PKH-выхода, и для P2WPKH-выхода.

Совместимые SegWit-адреса (P2PWKH-P2SH) создаются следующим образом:
1. Берётся хеш приватного ключа RIPEMD160(SHA256(pubKey))
2. К нему спереди добавляются два байта 0014(HEX)
3. Над полученной последовательностью из 22 байт снова выполняется операция хеширования RIPEMD160(SHA256(0014))
4. Результат хеширования представляется в кодировке base58check c версией 05.

Таким образом, получается, что из legacy-адреса можно получить bech32-адрес, и наоборот.
Из legacy-адреса или bech32-адреса можно получить P2PWKH-P2SH-адрес, а наоборот не получится.

Но это же разные адреса? А то получается, что как-будто 3 адреса из одного публичного ключа  - это один и тот же адрес, но тогда они могли бы конвертироваться друг в друга (как, скажем, в лайткоине адреса на 3 и M).Точно! Про несжатые P2PKH вылетело из головы.Почему на 2^160? На 2^256, в среднем 2^96 закрытых ключа будут давать одинаковый адрес.Да, но я говорил про количество всех возможных биткоин-адресов (не обязательно полученных из ключа). P2WSH-адрес тоже является биткоин-адресом, не так ли?

Закрытых ключей меньше 2^256 штук. Если точнее, то твердолобая реализация конечно же может использовать можно любое число на отрезке [0, 2^256 - 1], но безопасными в качестве ключей являются только числа меньше 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. Потому что бОльшие значения могут иметь соответствие более чем одному публичному ключу. Поэтому, практически все библиотеки при загрузке ключа первым делом проверяют, чтобы загруженное значение было меньше 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Значение HASH160 для всех типов адресов (legacy, P2WPKH-in-p2sh, bc1-P2WPKH) вычисляется одинаково, поэтому формат адреса не имеет никакого значения. Это просто разные способы записи одного и того же хэша в "человекопонятном" виде, и не более того.

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

Итого, на 2^160 закрытых ключей получается:

2¹⁶¹ адресов на "1" (P2PKH)
2¹⁶⁰ адресов на "3" (P2WPKH-in-P2SH)
2¹⁶⁰ адресов на "bc1" (42 символа) (P2WPKH)

Где 2¹⁶⁰ легаси адресов будет использовать тот же самый хэш, что и сгенерированные из того же приватного ключа P2WPKH-in-P2SH и P2WPKH адреса, а для оставшихся 2¹⁶⁰ легаси адресов не будет соответствия среди новых.

P2WSH адреса совсем другая степь, для них никакого соответствия не будет. Равно как и для обычных P2SH адресов, не сегвитных.

Побольше, по-моему:
2¹⁶⁰ адресов на "1" (P2PKH)
2¹⁶⁰ адресов на "3" (P2SH)
2¹⁶⁰ адресов на "bc1" (42 символа) (P2WPKH)
2²⁵⁶ адресов на "bc1" (62 символа) (P2WSH)

любителям прочитать про приватные ключи возможно заинтересует также этот пост

Визуальный генератор приватных ключей
https://bitcointalksearch.org/topic/--5188860

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

Это перевод, оригинал статьи принадлежит fillippone. Спасибо за полезную информацию!

2²⁵⁶ закрытых ключей: насколько велико это число?

Вчера, просматривая bitcoinrabbithole.org, я наткнулся на печально известный веб-сайт https://keys.lol

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

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

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

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

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

В ожидании решения от @babo, я подумал про себя: «Fillippone - единственная пешка в игре жизни"...почему никто никогда не думал об этом?

Вернувшись на bitcoinrabbithole.org, я быстро обнаружил Большой биткойн коллайдер.

https://lbc.cryptoguru.org/abow

Круто, это серьезный проект.
В основном тысячи распределенных серверов ежедневно генерируют и проверяют 26 триллионов (!!!) закрытых ключей.
За первые три года им удалось найти 7 закрытых ключей. Это много! Я предположил, что шансы были намного ниже, но, вероятно, в каком-то кошельке есть какая-то ошибка, использующая неоптимальный генератор случайных чисел для создания ключей. (Здесь необходимы дальнейшие исследования!)


Давайте быстро рассмотрим несколько цифр:
Количество закрытых ключей, теоретически возможно: 2²⁵⁶ или примерно 10⁷⁷
Количество адресов биткойнов: 2¹⁶⁰
Количество закрытых ключей, которые ищет биткойн-коллайдер: 2¹⁶⁰
Количество атомов во вселенной: от 10⁷⁸ до 10⁸²
Количество использованных адресов Биткойн : 18 000 000

Количество закрытых ключей, которое В действительности возможно, немного меньше, чем 2²⁵⁶, как указано здесь

Давайте рассмотрим несколько примеров.
Предположим, у нас есть миллиард активных адресов, каждый с положительным балансом: мы знаем, что это примерно на 10³ больше, чем фактическое число.
Вероятно, число атомов во вселенной в 10³ раза больше, чем количество адресов, поэтому справедливо сказать, что найти закрытый ключ с положительным количеством примерно так же вероятно, как найти один из этих атомов, разбросанных по всей  видимой вселенной.
Насколько велики миллиарды атомов? Согласно этому ответу Quora, он меньше, чем бактерия E. Coli. Так что догадайтесь взять эту бактерию, измельчить на атомном уровне, распределить ее по вселенной и попытаться найти один из этих атомов. Довольно сложно, не так ли?

Второй пример из этой статьи.  Предположим, мы хотим сканировать все закрытые ключи в поисках положительного баланса и предположим, что каждый житель Земли имеет скорость сканирования в миллиард раз выше, чем двойная текущая вычислительная мощность сети Биткойн, таким образом:
* 10 миллиардов человек;
* умноженный на один миллиард;
* умноженнаяна 2  вычислительная мощность биткойна, около 100 тысяч терахеш в секунду;
получаем: 1 000 000 000 000 * 1 000 000 000 * 100 000 * 100 0000 000 000 = 10¹⁰ * 10⁹ * 10⁵ * 10¹² = 10³⁶
Для простоты мы округлили '115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336' до 10⁷⁷,и мы получили, что, если мы проверим каждый отдельный закрытый ключ в поисках положительного баланса, это займет  10⁷⁷/10³⁶ = сколько лет это будет?
Поскольку в году около 31557600 секунд, это соответствует примерно 10⁴¹/31557600 = 31³³ годам, что более или менее в 10²³ раза превышает предполагаемый возраст Вселенной (в настоящее время оценивается в 13,82 миллиарда лет), короче говоря
100,000,000,000,000,000,000, то есть примерно в 100 миллиардов миллиардов раз больше возраста Вселенной.

Это видео о том, насколько безопасен алгоритм SHA 256.
 https://youtu.be/S9JGmA5_unY

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




Reddit

Другие примеры того, сколько потребуется, чтобы случайным образом угадать закрытый ключ:
Reddit: время и энергия, необходимые для грубого шифрования AES-256


Дальнейшие ссылки:

Тема Bitcointalk о возможном количестве адресов биткойнов
Освоение Биткоина: Ключи, Адреса

Другие очень большие цифры:

52!: Начинается с простой колоды игральных карт

Вот лишь несколько примеров, если у вас есть дополнительные ресурсы или комментарии, не стесняйтесь размещать свои ниже, и я добавлю в список!


_______________________________________________________________________________ ___________________
От меня.  Легендарная статья
Кто найдет кошелек с баллансом на сайте https://keys.lol/  обязательно напишите

Даже есть люди, которые годами вычисляют https://lbc.cryptoguru.org/stats