ВеткаЗадача: 11

60 сообщений · 19:37–19:15

Crypto Math Group

Задача: 11 AddressX 1LM36maeRvr2wqNkrcMmVTfTv5Uqan6t3M с балансом около 25$. PubKeyX: 0378f8c3a5e41433a4d3f1af1752349ee6289dd78d504b993268a8b90014368816 Любой ненулевой приватный ключ кривой secp256k1 принадлежит мультипликативной подгруппе. Известно, что PrivateKeyX является 256-битным числом и принадлежит мультипликативной подгруппе небольшого порядка. Принадлежность указанной подгруппе позволяет восстановить его через операции с публичной точкой. Найдите приватный ключ по публичному ключу и заберите средства с адреса.

19:37

В
Владислав
Принадлежит ли PrivateKeyX одному из косетов подгруппы порядка 18 051 648?
22:19
1. C
  Crypto Math Group
  Да
  22:20
H
heliopt
Этож можно бинарный поиск устроить 😁 Давай тогда такой вопрос: решается ли оно на цпу за адекватное время (смогу ли я решить на телефоне)?
06:00
1. C
  Crypto Math Group
  Да, можно решить
  09:47
В
Владислав
Верно ли, что PrivateKeyX в степени 18 051 648 даёт остаток 1 по модулю n, где n — порядок группы secp256k1 n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 (именно порядок кривой, не простое поле p)?
06:26
1. H
  heliopt
  а разве тогда оно бы не решалось за 4к шагов?
  06:53
2. C
  Crypto Math Group
  Ну это уже будет сильно просто)
  09:48
A
Airtex
О задача, сейчас попробую решить
10:50
V
Volodya
Приватный ключ точно 256 бит? Диапазон 255 - 256.
15:49
1. C
  Crypto Math Group
  Да
  15:54
  1. ₮
    ₮Ø₲Ʉ₴₳
    Дайте диапозон, я его кенгурятиной пройду)))
    15:57
H
heliopt
Решено
16:13
1. В
  Владислав
  расскажешь как решил?)
  16:23
  1. H
    heliopt
    Задача остается актуальной, поэтому не расскажу)
    16:24
2. V
  Volodya
  не рассказывай, хочу своим алгоритмом проверить
  16:36
3. В
  Владислав
  на телефоне, я надеюсь😃
  16:50
  1. E
    Eugene
    в уме посчитал)
    16:57
  2. A
    Alex
    Использовал естественный интеллект, чтобы придумать концепт, и искуственный, чтобы с телефона написать код с помощью ИИ
    16:58
  3. H
    heliopt
    По итогу запустил на карте, потому что доехал до дома, но думается мне, что обычный цпу бы тоже справился
    17:01
    1. I
      IDO Money
      а решение будет?? ну так что б хотя бы понят ьвектор направления в решении этих задач
      17:12
      1. H
        heliopt
        Если его опубликуют админ или кто-то из решивших. Я завязал публиковать решения и подсказки)
        17:13
        I
        IDO Money
        может пора развязывать по согласию с админами )) интересно же
        17:14
        H
        heliopt
        Так приз лежит, ждет следующего
        17:14
4. М
  Максим
  Крутые задачи конечно, но 98% участников группы просто зрители))
  17:57
  1. H
    heliopt
    Любое глубокое изучение начинается с того, что тебе стало интересно. Сегодня ты зритель, а завтра - активный участник. Задачки в данном случае работают как маркетинг, привлекающих и старичков и новичков)
    18:32
    1. М
      Максим
      Тут согласен, очень интересно увидеть решение!
      18:34
В
Владислав
Верно ли, что представитель косета (множитель, который нужно найти, чтобы свести задачу к поиску внутри косета) вычисляется из y-координаты публичной точки (или её комбинации с x), а не из Hash160 или внешних данных?
09:07
1. H
  heliopt
  Нет
  12:35
A
Airtex
Чего то идеи кончались. Нужен перерыв
16:20
1. В
  Владислав
  согласен
  16:27
M
Mr Crazy
m простое число? И меньше ли 1000?
08:38
1. C
  Crypto Math Group
  Задача уже решена участниками группы но приз еще на месте, так что уже без подсказок
  08:39
  1. M
    Mr Crazy
    Разложения n−1 = 2^6·3·149·631·p5·p6·p7, p−1 = 2·3·7·13441·(простое 2^240). Подгруппа H порядка 18 051 648 в Z_n* (это m = 1), перебрал полностью, ключа нет. Подгруппы порядка p5 и 2·p5, BSGS, ключа нет. Z_p*, все подгруппы порядка, делящего 564 522, ключа нет. Косеты m·H для m от 1 до 10^8, ключа нет. Kangaroo по диапазону 2^255–2^256 нереален, его не гонял.
    11:02
    1. C
      Crypto Math Group
      Ход ваших мыслей правильный)
      11:16
      1. M
        Mr Crazy
        у меня осталось только два варианта либо m больше 10⁸, либо косет задан не через маленькое целое, а как 7^i·H и сдаюсь 😁
        11:20
        C
        Crypto Math Group
        Не сдавайтесь, вы ее можете решить
        11:21
        M
        Mr Crazy
        я и так ночь не спал😁подсказку бы в качестве исключения новичку 🤓😁
        11:21
        C
        Crypto Math Group
        Может быть вам просто не хватает одной переменной) (подсказка абстрактная)
        11:24
  2. E
    Eugene
    Как будто кому то от этого легче.
    11:05
    1. C
      Crypto Math Group
      Ну если смогли решить одни участники то теоретически смогут и другие. И я не говорил что должно быть легко😀
      11:15
      1. E
        Eugene
        Прям таки участники) Мне бы больше энтузиазма давало если бы задачу решили бы несколько людей, а так это что угодно, но не математическая задача, когда нужно домысливать что под каждым словом имеется ввиду в условиях задачи и угадывать переменные..
        15:59
        C
        Crypto Math Group
        Че ты на меня напал как на родного, ну не решай если не выходит. Или придумай лучше😀
        16:03
        E
        Eugene
        Да никто не нападает, просто загадки и задачки разные вещи. Задачи решать горазд, а загадки не очень.
        16:05
        C
        Crypto Math Group
        Условия задачи даны в полном объеме для ее решения
        16:08
        E
        Eugene
        Только вот на допвопросы с ответами Да/Нет рассчитывать уже не приходится только потому что какой то один челик решил. Задача в которой условия меняются на лету не очень то и интересна и по сути превращается в угадайку.
        16:12
Z
Zevs Z
можно ещё намек а то буксую
19:54
1. C
  Crypto Math Group
  Можно, но так как задача решается уже очень долго, сразу напишу порядок решения а не подсказку)
  11:13
H
heliopt
Файл
mkang.zip · 766 КБ · нажмите — покажем
обычно в опубликованных статьях встречается предложение решать задачи такого рода с помощью bsgs. Я же предлагаю не совсем стандартный подход брута с помощью мультипликативного кенгуру. Основная подсказка, которая натолкнула на решение была тут: https://t.me/CryptoMathGroup/1/19491
11:02
1. C
  Crypto Math Group
  Пока еще не смотрел твой код, а по какому критерию кенгуру переходит на следующий порядок группы для поиска?
  12:46
  1. H
    heliopt
    Если ты имеешь в виду переход на следующий порядок подгруппы, то в этом коде его вообще нет. Код принимает -m и ищет в нем. Мне повезло, я угадал нужный достаточно быстро)
    12:52
    1. C
      Crypto Math Group
      Ааа ясно, ну так да кенгуру мне тоже ближе)
      12:54
      1. H
        heliopt
        Мне просто захотелось чего-то необычного, а тут можно со скалярами работать)
        12:55
        C
        Crypto Math Group
        Есть какие-нибудь идеи?)
        12:56
        H
        heliopt
        Неа)
        12:57
2. D
  Denis T
  Код не смотрел, под CUDA?
  13:07
  1. H
    heliopt
    Ага
    13:07
3. V
  Volodya
  Супер решения, подскажите, оптимизированной функции bitcoin_hash160 у вас случаем не будет? Спасибо🙂
  14:54
  1. М
    Максим
    А можешь не оптимизированую показать?
    16:34
  2. H
    heliopt
    А есть примеры того, что мы тестируем и что считать эталоном, чтобы понять, что надо оптимизировать?)
    19:15