Jump to content

Программы для вычисления приватного ключа


Recommended Posts

Posted (edited)

Есть три типа таких программ: вычисление по публичному ключу, по адресу и случайная генерация с подстановкой. От обычного адреса непросто вычислить, нужно хорошее везение чтобы случайно выпало, но для разгадывания головоломок хорошая тема, 256 видеокарт способны вычислить 119 битный ключ за 2 месяца с балансом 1.2 бтц

 

1) https://github.com/JeanLucPons/Kangaroo

Автор ограничил диапазон до 125 бит

 

2)  https://github.com/JeanLucPons/VanitySearch

 

3) https://github.com/traxm/Bitcoin-Micro-Collider

Edited by alevlaslo
Posted (edited)

@Bmstu Невозможно.. За разумное время это не реально.

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

Edited by Lenchik
Posted
2 минуты назад, Lenchik сказал:

@Bmstu Невозможно. Для того что бы высчитать приватный ключ от BTC нужно по сути пересчитать всю цепочку. За разумное время это не реально.

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

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

 

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

Posted

 программы работают без сети, интернет им не нужен, список адресов загружается файлом

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

Posted (edited)
30 минут назад, Bmstu сказал:

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

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

3 часа назад, Bmstu сказал:

256 видеокарт способны вычислить 119 битный ключ за 2 месяца с балансом 1.2 бтц

256 видеокарт за два месяца 1 биткоин могут и честно намайнить. А может даже и побольше выйдет.

Edited by Lenchik
Posted (edited)

Это тоже честно, пазл создан ради его вычисления

https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/puzzle32.txt

 

3 часа назад, Lenchik сказал:

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

По публичному ключу достаточно 128 бит, по адресу 160 бит. 

 

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

Edited by alevlaslo
Posted

10 мкей на процессоре - 130 тысяч лет это, на картах по 2000 мкей, делим на 200 и получаем 650 лет для одной карты, для 650 карт срок 1 год 

image_2020-10-27_233414.png

Карты стали намного мощнее и программы тоже в разы быстрее стали, адреса на единицу уязвимы уже

Posted (edited)
3 часа назад, Bmstu сказал:

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

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

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

Остаётся только Брутфорс (Brute force). То есть тупой перебор приватных ключей до получения нужного результата. Но и тут закавыка. Если ключ достаточно длинный, а известное сообщение короткое, то вы можете найти неверный ключ. То есть он будет подходить только конкретно к этому сообщению и не будет подходить ко всем сообщениям зашифрованным с помощью настоящего приватного ключа.

 

Майнинг то же по большому счёту брутфорс. То есть подгонка ключа перебором под нужный критерий.
 

12 минут назад, Bmstu сказал:

адреса на единицу уязвимы уже

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

Edited by Lenchik
Posted

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

Говорю же, возросли скорости программ значительно, появились крутые год назад, которые за этот год потом еще в 20 раз ускорились

00000000000000000000000000000001
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02545D2C25B98EC8827F2D9BEE22B7A9FB98091B2008BC45B3B806D44624DC038C

это настройки стартового текстового файла для этой программы

Posted
3 минуты назад, Bmstu сказал:

Перебор не тупой как раз, а умный,

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

Posted

Как это устроено

В программе используются 2 стада кенгуру, ручное стадо и дикое стадо. Когда 2 кенгуру (дикий и ручной) сталкиваются, ключ может быть разгадан. Из-за парадокса дня рождения, коллизия происходит (в среднем) после 2,08 * sqrt (k2-k1) [1] групповых операций, 2 стада имеют одинаковый размер. Для обнаружения коллизии используется метод выделенных точек с хеш-таблицей.

Вот краткое описание алгоритма:

Мы должны решить P = kG, P - открытый ключ, мы знаем, что k лежит в диапазоне [k1, k2], G - точка генератора SecpK1.
Групповые операции - это сложение эллиптической кривой, скалярные операции выполняются по модулю порядка кривой.

 

n = этаж (log2 (sqrt (k2-k1))) + 1

  • Создайте таблицу точек перехода jP = [G, 2G, 4G, 8G, ..., 2 n-1 .G]
  • Создайте таблицу расстояний перехода jD = [1,2,4,8, ...., 2 n-1 ]

для всех г в herdSize
  приручить я = RAND (0 .. (к2-k1)) # скалярных операции
  tamePos я = (k1 + ручной я ) .G # Группа операция
  дикий я = Rand (0 .. (к2-k1)) - (k2-k1) / 2 # Скалярная операция
  wildPos i = P + wild i .G # Групповая операция

найдено = ложь

пока не найдено
  для всех i в стаде
     tamePos i = tamePos i + jP [tamePos i .x% n] # Групповая операция
     tame i + = jD [tamePos i .x% n] # Скалярная операция
     wildPos i = wildPos i + jP [ wildPos i .x% n] # Групповая операция
     wild i + = jD [wildPos i .x% n] # Скалярная операция,
     если tamePos i выделяется

 

 add (TAME, tamePos i , tame i ) в хэш-таблицу
     если wildPos i выделен,
       добавьте (WILD, wildPos i , wild i ) в hashTable
  found = есть ли конфликт в hashTable между ручным и диким кенгуру?
 

(Tame, Wild) = Collision
k = k1 + Tame.dist - Wild.dist

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

 

Пути

 

По первой ссылочке в описании к программе всё это написано

Posted

Предположим, что есть pubkeyX, неизвестный privkeyX, но privkeyX находится в диапазоне w = [L..U]. У ключей есть свойство - если мы увеличим pubkey на S, то его приватный ключ также увеличится на S. Начнем шаг за шагом, чтобы увеличить pubkeyX на S (i), сохраняя sumX (S (i)). Это дикий кенгуру. Мы выбираем случайный privkeyT из диапазона [L..U], вычисляем pubkeyT. Мы начинаем шаг за шагом увеличивать pubkeyT на S (i), сохраняя sumT (S (i)). Это ручной кенгуру. Размер прыжка S (i) определяется координатой x текущей точки, поэтому, если дикий или ручной кенгуру приземлится в одной точке, их пути сольются. (нас интересуют псевдослучайные блуждания, следующий шаг которых определяется текущей позицией) Благодаря парадоксу дня рождения (карточный фокус Крускала) их пути однажды встретятся. Зная каждый пройденный путь (sumX и sumT), вычисляется privkeyX.1/2 групповых операций, что намного меньше, чем полный поиск w.

Posted
52 минуты назад, Bmstu сказал:

10 мкей на процессоре - 130 тысяч лет это, на картах по 2000 мкей, делим на 200 и получаем 650 лет для одной карты, для 650 карт срок 1 год 

image_2020-10-27_233414.png

Карты стали намного мощнее и программы тоже в разы быстрее стали, адреса на единицу уязвимы уже

 

Во-первых, вы задали диапазон приватных ключей - 128 бит, хотя реальный диапазон поиска произвольного приватного ключа - 256 бит.

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

 

Поэтому, ваша оценка времени поиска произвольного приватного ключа может быть несостоятельна. 2000 mkey/s для урезанного диапазона поиска могут превратиться в значительно более низкую величину для полного диапазона.

Posted

Не позорь славное имя BMSTU))). Дружище, я в свое время перед 70 людьми выходил и брал "неберущийся интеграл". С вполне предсказуемым финалом. К чему говорю - велосипед изобретен, Америка открыта и все идеи уже опробованы. Ну не получается, не по лу ча ет ся такая атака. Гипотетически возможно все, но экономически нет смысла! С таким же успехом езжайте в Южную Америку на ауяску, в Мексику на пейотль, в Купчино на соли, скорее там получте приватник из космоса.

Posted
4 часа назад, Bmstu сказал:

У ключей есть свойство - если мы увеличим pubkey на S, то его приватный ключ также увеличится на S

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

Posted

@Old Miner 

256 диапазон нет смысла перебирать потому что для каждого адреса приватных ключей очень много: 2^96, пожтому достаточно диапазона 2^160, но здесь еще известен публичный ключ, поэтому достаточно диапазона 2^128. Да, разработчик ограничил 125, но почему не выдаёт ошибку и вычисляет 128, да и можно переписать программу самому

 

4 часа назад, Lenchik сказал:

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

 

https://github.com/Telariust/vs-kangaroo

А вот этот релиз работает с 132 битами, но скорость низкая потому что релизу год

Posted
5 минут назад, Bmstu сказал:

256 диапазон нет смысла перебирать потому что для каждого адреса приватных ключей очень много: 2^96, пожтому достаточно диапазона 2^160, но здесь еще известен публичный ключ, поэтому достаточно диапазона 2^128.

Это что за чушь? Если длина ключа 256 бит, то какой смысл перебирать половину? Вероятность нахождения ключа будет равна 0.

Posted

@Lenchik 

Ключ в каждом последующем диапазоне потому что имеется начиная со 128 бит

Длина 256 привычного, но есть еще куча ключей начинающихся на 0, 00, 000 и т.д

Старый релиз не для пазла написан, но вы не запустите его шире чем 132

Вот еще один, более 130 не работает https://github.com/Telariust/pollard-kangaroo-c99

Posted

Приватников существует 2^256, адресов 2^160 потому что они короче, а пабликов 2^128 несмотря на то что они длиннее 

Posted

@Bmstu Почитайте основы криптографии https://drive.google.com/file/d/1OXg0geYLc7SNFIp2NM4Bw0VF1TmSPaZC/view?usp=sharing

 

Бывает конечно что не весь ключ нужно перебирать. Например часть ключа это контрольная сумма ключа или есть неизменная часть. Но вы этого не показали. Следовательно если ключ 256 бит, то их все и нужно перебирать. Естественно если это не 32 байта, а скажем ограниченный набор символов, буквы цифры, знаки препинания, то вариантов перебора меньше. Но совсем немного меньше и на время нахождения влияет мало. Скажем вместо 600 лет получится 400. 

Posted

 Сатоши сделал так чтобы сдача приходила на новый адрес, чтобы не светился паблик, зная который легче вычислить приватник

Иначе не было бы смысла бояться этого если бы их было не меньше чем адресов 

Posted (edited)

400 лет было раньше, с тех пор карты и программы ускорились на порядки

 

Edited by alevlaslo
Posted (edited)
4 часа назад, Bmstu сказал:

 поэтому достаточно диапазона 2^128

 

3 часа назад, Bmstu сказал:

а пабликов 2^128

 

Публичный ключ - это точка на эллиптической кривой, определённой над полем Fp. Общее число этих точек, а следовательно, и публичных ключей определяется параметром порядок группы (n), который для secp256k1 равен:

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

 

Это немного меньше, чем 2256, но гораздо больше чем 2128. То есть, вы сильно ошибаетесь в количестве всех возможных публичных ключей.

 

Жан-Люк приводит пример нахождения приватного ключа №85 из пазла. Диапазон этого приватного ключа - 84 бит. Обратите внимание, во входных данных к его программе задаётся полный диапазон - 84 бита, а не половинный. Но, почему? Ведь половинный  диапазон перебирается быстрее.

 

Цитата

Puzzle #85: 84bits private key [284,285-1], 1Kh22PvXERd2xpTQk3ur6pPEqFeckCJfAr


1000000000000000000000
1FFFFFFFFFFFFFFFFFFFFF
0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a

 

Мне кажется, вы путаете криптостойкость secp256k1 (128 бит) с диапазоном приватных ключей (256 бит).  Криптостойкость определяет максимальное количество итераций (попыток), необходимых для нахождения приватного ключа. То есть, для нахождения любого 256-битного приватного ключа необходимо сделать в худшем случае 2128 попыток. Но это не значит, что мы должны как-то ограничивать диапазон приватных ключей, иначе мы рискуем пропустить нужный ключ.

Edited by Old Miner
Posted (edited)

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

Edited by alevlaslo
Posted
10 минут назад, Bmstu сказал:

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

Есть варианты. К примеру поиск по радужной таблице. Но в данном случае он неприменим. К примру ключ кодировки CSA, это то чем я как то занимался, не путайте с RSA, восемь байт. Но он как бы из двух половинок по три байта и у каждой один байт контрольная сумма остальных трёх. Искать нужно всего лишь 6 байт, 48 бит то есть. Так вот, для этого ключа радужная таблица около трёх терабайт. И это только для одного образца. Дело в том что создатели CSA зашифровали не только видеопоток, но и заголовки MPEG пакетов. А заголовки MPEG пакетов имеют варианты и для каждого нужна своя радужная таблица. 

 

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...