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

[alevlaslo]

Есть три типа таких программ: вычисление по публичному ключу, по адресу и случайная генерация с подстановкой. От обычного адреса непросто вычислить, нужно хорошее везение чтобы случайно выпало, но для разгадывания головоломок хорошая тема, 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 27 Oct 2020, 14:30 by alevlaslo

[Lenchik]

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

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

Edited 27 Dec 2023, 00:57 by Lenchik

[Desconect]

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

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

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

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

 

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

[alevlaslo]

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

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

[Lenchik]

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

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

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

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

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

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

Edited 27 Oct 2020, 17:25 by Lenchik

[alevlaslo]

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

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

 

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

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

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

 

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

Edited 27 Oct 2020, 20:40 by alevlaslo

[alevlaslo]

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

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

[Lenchik]

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

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

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

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

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

 

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

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

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

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

Edited 27 Oct 2020, 20:47 by Lenchik

[alevlaslo]

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

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

00000000000000000000000000000001
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02545D2C25B98EC8827F2D9BEE22B7A9FB98091B2008BC45B3B806D44624DC038C

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

[Lenchik]

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

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

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

[alevlaslo]

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

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

 

 

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

[alevlaslo]

Предположим, что есть 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.

[Old Miner]

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

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

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

 

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

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

 

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

[moneymaker]

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

[Lenchik]

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

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

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

[alevlaslo]

@Old Miner 

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

 

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

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

 

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

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

[Lenchik]

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

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

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

[alevlaslo]

@Lenchik 

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

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

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

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

[alevlaslo]

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

[Lenchik]

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

 

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

[alevlaslo]

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

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

[alevlaslo]

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

 

Edited 28 Oct 2020, 07:08 by alevlaslo

[Old Miner]

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

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

 

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

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

 

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

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

 

Это немного меньше, чем 2²⁵⁶, но гораздо больше чем 2¹²⁸. То есть, вы сильно ошибаетесь в количестве всех возможных публичных ключей.

 

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

 

Цитата

Puzzle #85: 84bits private key [2⁸⁴,2⁸⁵-1], 1Kh22PvXERd2xpTQk3ur6pPEqFeckCJfAr

1000000000000000000000
1FFFFFFFFFFFFFFFFFFFFF
0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a

 

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

Edited 28 Oct 2020, 10:04 by Old Miner

[alevlaslo]

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

Edited 28 Oct 2020, 10:05 by alevlaslo

[Lenchik]

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

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

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

 

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