Недавно на всех порталах промелькнула новость про некого Andy Bauch’а, который закодировал в восемь своих картин биткоинов на сумму $10,000 (1.02963903 btc). Сделал он это в далеком 2016 году (при курсе ~$430), когда никто и подумать не мог, что в 2018 году биткоин будет искать свое дно где-то у $6,000, и тогда это были символические $20, $30, $40, $50, $60, $70, $80 и $90 соответственно в каждой из картин.
Для кого эта статья?
- Для тех, у кого не получилось. Статья построена по такому принципу, чтобы вы могли перейти сразу к нужному пазлу и прочитать полное решение. Вся необходимая информация будет содержаться в решении для каждого пазла.
- Для любознательных. Наверняка кому-то будет просто интересно посмотреть, как это вообще решается. Сразу скажу, что эти пазлы оказались простейшими, поэтому, с одной стороны, не так интересно, с другой — для новичка или человека без особых знаний будет в самый раз.
- Для пополнения знаний. Статья написана таким образом, чтобы для ее прочтения не требовалось дополнительных знаний. Вся необходимая информация, теоретические выкладки, ход рассуждений будут появляться в статье по мере необходимости. Вставленные гиперссылки пригодятся тем, кто хочет более углубленно изучить тот или иной аспект. Теоретически, человек с 6–7 классами общеобразовательной школы не должен встретить затруднений при прочтении. Я бы был очень рад обратной связи от прочитавших (или не дочитавших), получилось ли сделать статью настолько доступной или нет. Если нет, то что вызвало затруднения (кроме объема, тут я бессилен).
Внимание, дальше будут спойлеры, поэтому, если вы хотите попробовать себя, то стоит закончить на этом предложении.
Определимся с терминологией
Под узором понимается последовательность элементов, которая будет повторяться.
Под элементом понимается одноцветный кубик лего.
Как кодировались биткоинты в картинки?!
Все довольно просто: с помощью деталей лего в различных системах счисления записывались коды символов приватного-мини ключа из кодовой таблицы кодировки ASCII (7 bit).
Первый пазл 20$
Если вы присмотритесь внимательно, то сможете обнаружить повторяющийся узор:
Само поле имеет размеры 48х48 элементов. Узор повторяется через каждые 6 элементов по горизонтали (с некоторым смещением) и через каждые 35 элементов по вертикали (последовательно). В одну линию (см. рис. 3) из 6 элементов умещается полный узор (35 строк) + 13 первых строк, далее пропущено 9 строк и и начинается следующая линия, т.е. если на узоре отсчитать 22 строки вниз (13 + 9), то 23-я строка будет совпадать с первой строкой следующей линии:
На самом деле, последовательность узора не так принципиальна, а главное вот что: как мы можем заметить, на картине элементы представлены всего двумя цветами — серым и зеленым. Получается, что каждый элемент несет 1 бит информации. Сам узор имеет размеры 6х35 элементов или 210 элементов, т.е. 210 бит информации. Размер приватного ключа биткоина составляет 256 бит. Что-то не сходится.
Если мы предположим, что 1 символ кодируется 7 битами информации (ASCII), то выходит, что у нас закодировано 30 символов. Именно столько символов нужно для приватного мини-ключа биткоина. Теперь нам нужно принять один из цветов за 0, а второй за 1.
Принимаем зеленый цвет за 0, серый за 1, перебиваем 35 строк по 6 элементов и получаем строку:
010110110010011001001001100100111100001110001101001100111000110100110001110011111011001000100011110011100011010101101100010000100111010010001000001000101100111100001100000100101001010111110011101100010110001011
Дальше берем каждые 7 бит подряд, декодируем символы кодировки ASCII (см. графу “binary”) и … обламываемся. Пробуем инвертировать биты (взять серый за 0, а зеленый за 1) и … обламываемся снова. Пробуем циклически сдвигать каждые 6 бит (1 строку) влево, обламываемся, сдвигаем по 1 биту, обламываемся снова, психуем, крутим-вертим-реверсируем-перебираем строку целиком, по частям, в полнолуние, но снова никак.
И тут мы вспоминаем, что приватный мини-ключ берется не с потолка, а это 30 символов base58check (тут на русском), где первый обязательно должен быть “S”. Символ “S” кодируется числом 83 в десятичной системе счисления (в ASCII) или 1010011 в двоичной системе счисления. Пробуем взять первые 7 бит из верхнего левого угла (зеленый — 0, серый — 1) и получаем 0101100 — не подходит. Берем цвета наоборот (зеленый — 1, серый — 0) — 1010011 — бинго! Мы получили начало приватного мини-ключа.
Как вы уже догадались, последовательность элементов нужно брать не из узора, а из целой картины. А если быть еще более точным, то узор повторяется не окном поля размером 6х35 элементов, а просто через каждые 210 элементов подряд. За счет этого повторения и создаются пресловутые узоры, которые зрительно быстро улавливаются, но сбивают с толку.
Итого перебиваем 4 строки по 48 элементов и 18 элементов из 5 строки (слева направо от верхнего левого угла, зеленый — 1, серый — 0) и получаем:
101001101101000111001100101010000011110011110111001101110111001011010011010011110001111011011100100110110111001110101001101111110010010110001100110110010011001100110100011000110011101000011100011011000011000100
Делим по 7 бит, декодируем символы с помощью кодировки ASCII и получаем следующую строку:
S49JAsn794iqvr6sTodXfdf41NCFaD
Очень похоже на приватный мини-ключ. Чтобы удостовериться, прибавляем в конец строки знак “?”, и хешируем SHA-256:
SHA-256(S49JAsn794iqvr6sTodXfdf41NCFaD?) = 001060a8c01019278460da23ccfda7000281a4654131517d3c820c887529f5e6
Как вы можете заметить, хеш начинается с двух нулей, значит, наш мини-ключ верный.
Получаем хеш от самого ключа:
SHA-256(S49JAsn794iqvr6sTodXfdf41NCFaD) = 639104ad8faacf89c56ac220b3ef956049b35ce9e7636082ac1b3d413f196623
Этот хеш есть ни что иное, как 64 символа шестнадцатеричной системы счисления или 256 бит информации, или приватный ключ биткоина в hex формате (шестнадцатеричном формате). Напомню, что приватный ключ биткоина это всего лишь число в диапазоне:
0 — FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140
Но в таком формате не все кошельки позволяют импортировать ключи, поэтому переведем наше шестнадцатеричное число в Base58Check систему счисления и получим:
5Ja8scsM42BVcWABQ7QpSSN1DhC7tgcW6hqf7jBqKPQvZXHj6fJ
Что соответствует публичному адресу:
Как мы видим, биткоины были отправлены на адрес 19.04.16 и забраны почти через 2 года — 24.03.18.
На всякий случай напомню, что символы в ASCII чаще кодируются 8 битами. Такая кодовая таблица называется кодовой страницей, в которой первые 128 символов (0–127) это стандартная кодовая таблица ASCII, а вторые 128 символов (128–255) являются символами национальных алфавитов (например, символы кириллицы).
Второй пазл 30$
Если вы все еще хотите попробовать сами, то самое время это сделать!
Итак, второй пазл. Выглядит он интереснее. Первое, что бросается в глаза, это 3 цвета: желтый, оранжевый, красный (y, o, r, соответственно). Выходит, у нас есть 3 независимых значения, т.е. у каждого элемента может быть 3 состояния. В ASCII (7 bit) всего 128 значений (0–127). Главное правило информатики гласит, что для алфавита с мощностью M (количеством символов в алфавите), количество возможных сообщений N длиной L вычисляется по формуле:
N = M ^ L
В нашем алфавите всего 3 символа/значения (y, o, r), а количество возможных сообщений равно 128. Отсюда мы можем найти длину каждого сообщения L. Поскольку элементы узора на части мы делить не можем, то L должно быть целым. Получается следующее условие:
3 ^ L ≥ 128
Простым перебором получаем L = 5, N = 243 (при L = 4, N = 81, что меньше 128). Значит, для того, чтобы закодировать 7-битный символ ASCII нам нужно не менее 5 элементов.
Также можно найти графическую подсказку:
Как вы можете увидеть на рис. 6, идея идентична той, что была в предыдущем пазле: у нас есть некий повторяющийся узор. Этот узор состоит из 150 элементов. Для того, чтобы закодировать 30 символов, нам нужно 150 : 30 = 5 элементов на каждый символ, что и было до этого рассчитано теоретически. Дальше берем первые 5 элементов и получаем строку:
yooor
Как вы помните из прошлого пазла, приватный мини-ключ начинается с символа “S”, который имеет код 83 в десятичной системе счисления или 1010011 в двоичной. Поскольку у нас всего 3 значения (y, o, r), наша система счисления имеет основание 3. Всего возможно 3 значения, т.е. алфавит имеет мощность 3, и состоит из следующих знаков:
0, 1, 2
Теперь нам нужно догадаться, какой цвет какому значению соответствует. Можно написать простенький скрипт, который перебирает всевозможные варианты, а можно поступить еще проще: давайте попробуем перевести число 83 из десятичной системы счисления, в троичную? Напомню, что для этого мы должны целочислено делить число 83 на основание 3, выписывая остатки, пока не поучится 0.
83 : 3 = 27 (остаток 2)
27 : 3 = 9 (остаток 0)
9 : 3 = 3 (остаток 0)
3 : 3 = 1 (остаток 0)
1 : 3 = 0 (остаток 1)
Теперь выписываем остатки в обратном порядке:
10002
Получается:
1010011 (в двоичной системе) = 10002 (в троичной системе) = yooor
Теперь не так сложно догадаться, что:
o = 0
y = 1
r = 2
Переписываем 150 элементов (слева направо из верхнего левого угла):
yoooroyryyoryororroryoyrryyyyryyoryyorrrorrooorryryoryoyoryyyyyoryorooyyoororyyryyoyryorrooryyoyyoyoyoyrroryryyyyoryyyoyorrrryorryyooryorooryooyoyorry
Теперь делим строку по 5 символов и, с помощью полученных кодов и кодовой таблицы ASCII (7 bit), декодируем приватный мини-ключ:
S1AJbzskHMfgwcnDqiBobFwvPjX8Tj
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
684b3ca56aebdc67300cdac0a5009d6c10873f3e8754957a85fa59ab1d734173
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5JcDdSQNhtpE6yg9ocECDhhVT3U7Dyu4kT5jqvY2zT8zkcTFC4E
Который соответствует публичному адресу с 0.04678122 btc:
Третий пазл 40$
Тут вам уже должно стать скучно, но давайте продолжим. Итак, что у нас есть? Четыре цвета:
Фиолетовый — p(urple)
Белый — w(hite)
Красный — r(ed)
Розовый — (p)i(nk))
Значит, основание системы счисления у нас равно четырем. Чтобы закодировать 128 значений в системе счисления с основанием 4, длина строки L должна быть равна четырем (4³=64, что меньше 128, а 4⁴=256, что хоть и больше, но первое минимальное целое L). Итого, чтобы закодировать 30 символов нам понадобится 30 * 4 = 120 элементов.
Что у нас есть с точки зрения графики?
Как мы видим, снова повторяющийся узор длиной … 150 элементов. А вот тут возникает ступор, ведь нам нужно всего 120 элементов. Выходит, что либо мы что-то неправильно посчитали, либо способ кодирования приватного ключа изменился, либо у нас есть избыточные биты. Первый вариант отбрасывается после нескольких перепроверок, второй вариант отложим на потом, ведь пока наша тактика не давала осечек и вряд ли способ мог сильно измениться, если стиль картинки изменился не сильно, а вот с третьим вариантом можно поработать.
Для чего могут использоваться избыточные биты? Обычно они используется для проверки корректности передачи информации: раз и два. Очевидно, что это не тот случай.
Давайте для начала запишем символ “S” (код 83 в десятичной системе счисления в кодировке ASCII (7 bit)) в системе счисления с основанием 4:
83 : 4 = 20 (остаток 3)
20 : 4 = 5 (остаток 0)
5 : 4 = 1 (остаток 1)
1 : 4 = 0 (остаток 1)
1103
Как мы видим, у нас должно быть подряд два элемента одного цвета (которые мы примем за единицу). Если мы посмотрим на наш пазл, то первые два элемента имеют разные цвета: фиолетовый и белый. Зато третий элемент снова белый. Дополним нашу запись в четверичной системе счисления нулем в старшем бите и тогда у нас получится:
01103 = pwwpr
Как мы можем увидеть, p отлично совпадает с 0, w примем за 1, r за 3. У нас остается только розовый цвет, которому нужно присвоить какое-то значение. Алфавит четверичной системы счисления состоит из 4 знаков: 0, 1, 2, 3 — поскольку все, кроме одного, заняты, то методом исключения примем i за 2.
Перебиваем первые 150 элементов слева направо из верхнего левого угла (3 строки по 48 элементов + 6 элементов из 4-й строки):
pwwprpprwipwwwppwpwrpwwpwpwppwpwwwwpwirrpwiwrpwirrpwpirpwrwppwwwipwpirppriwpprpipwrprpwiripwipipwpwrpwprppwipipwipwpwirwpwpripwprppwwiwpwpirpwprwpwppw
Теперь делим строку по 5 символов и, с помощью полученных кодов и кодовой таблицы ASCII (7 bit), декодируем приватный мини-ключ:
S6TGQAUogoKtVK92snbGLbamNLYKMA
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
a654fa9db9bf61e54f62e0f2bad062269a8aaf6bc63b00a6e4537656bdabbbb0
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5K5YJp4BJZtAs5s6VFwNXwTjFXfLJ5b86BWGxK9BfWGr6JQ4bU7
Который соответствует публичному адресу с 0.09276721 btc:
Остается порадоваться или расстроиться, что нам не пришлось выдумывать новый способ решения головоломки.
Четвертый пазл 50$
Зная схему кодирования приватного мини-ключа, даже на глаз все выглядит очевидным. У нас есть пять цветов:
Черный — b(lack)
Красный — r(ed)
Зеленый — g(reen)
Желтый — y(ellow)
Розовый — p(ink)
Очевидно, что основание системы счисления равно пяти (алфавит: 0, 1, 2, 3, 4). И вот в чем проблема: чем выше основание системы счисления, тем больше нулей будет подряд или тем меньше элементов нужно будет, чтобы закодировать 1 символ. Здесь мы видим подряд много элементов с черным цветом и это подводит нас к мысли, что черный цвет это ноль. Из-за описанной выше проблемы и нашего предположения о нуле, легко зрительно определить где кончается один символ и начинается другой. Четыре или пять подряд элементов черного цвета + 3/2/1 цветных элемента и снова 4–5 элементов черного цвета. Но давайте по порядку.
Начнем с графической подсказки:
Ничего нового — 210 элементов. На каждый символ приватного мини-ключа приходится 210 : 30 = 7 элементов. Для того, чтобы закодировать 128 значений в системе счисления с основанием 5 нам нужно 4 элемента (5³ = 125, 5⁴ = 625). Избыточность в 3 элемента легко объясняет наличие такого объема черных элементов.
Запишем число 83 (код в десятичной системе счисления символа “S” в кодовой таблице кодировки ASCII (7 bit)):
83 : 5 = 16 (остаток 3)
16 : 5 = 3 (остаток 1)
3 : 5 = 0 (остаток 3)
313
Дополним четырьмя нулями и сравним с первыми семью элементами, расположенными в верхнем левом углу:
0000313 = bbbbrgr
Легко догадаться, что:
b = 0
r = 3
g = 1
У нас осталось два знака (y и p), которым мы еще не присвоили значений. Возьмем следующие 7 элементов:
bbbbyry = 0000y3y
Запишем это же число в развернутой форме:
y * 5⁰ + 3 * 5¹ + y * 5² + 0 * 5³ + 0 * 5⁴ + 0 * 5⁵ + 0 * 5⁶ =
= 26 * y + 15
Из оставшихся незанятых значений у нас есть 2 и 4, подставим их в наше выражение:
2: 26 * 2 + 15 = 67
4: 26 * 4 + 15 = 119
В кодовой таблице кодировки ASCII (7 bit) коду 119 соответствует символ “w”, а 67— “C”. Оба эти символа входят в base58check кодировку.
Возьмем следующие 7 элементов:
bbbbyrr = 0000y33
3 * 5⁰ + 3 * 5¹ + y * 5² + 0 * 5³ + 0 * 5⁴ + 0 * 5⁵ + 0 * 5⁶ =
= 25 * y + 18
2: 25 * 2 + 18 = 68 (“D”)
4: 25 * 4 + 18 = 118 (“v”)
Снова облом. Пробуем еще раз:
bbbbryp = 00003yp
p * 5⁰ + y * 5¹ + 3 * 5² + 0 * 5³ + 0 * 5⁴ + 0 * 5⁵ + 0 * 5⁶ =
= 1 * p + 5 * y + 75
y = 2, p = 4: 1 * 4 + 5 * 2 + 75 = 89 (“Y”)
y = 4, p = 2: 1 * 2 + 5 * 4 + 75 = 97 (“a”)
И опять облом. Забегая вперед, в реальных условиях проще вычислить сразу два ключа ({y = 2, p = 4} и {y = 4, p = 2})и и проверить их на наличие биткоинов (второй ключ выглядел бы как “SwvaWcog3%DEATBOWtHaQnKFwY_nLo”).
… итак, берем десятый символ:
bbbbgpp = 00001pp
p * 5⁰ + p * 5¹ + 1 * 5² + 0 * 5³ + 0 * 5⁴ + 0 * 5⁵ + 0 * 5⁶ =
= 1 * p + 5 * p + 25 =
= 6 * p + 25
2: 6 * 2 + 25 = 37 (“%”)
4: 6 * 4 + 25 = 49 (“1”)
Поскольку в base58check нет символа “%”, делаем вывод, что желтый цвет кодирует цифру 2 (y = 2), тогда для розового остается 4 (p = 4).
Перебиваем первые 210 элементов слева направо из верхнего левого угла:
bbbbrgrbbbbyrybbbbyrrbbbbrypbbbbrppbbbbryybbbbypgbbbbybrbbbbpbgbbbbgppbbbbprrbbbbprybbbbprbbbbbrgybbbbprgbbbbrbybbbbrppbbbbyrgbbbbpypbbbbrypbbbbrggbbbbypbbbbbrbbbbbbpybbbbbyrybbbbrpybbbbrybbbbbypbbbbbrbgbbbbypg
Теперь делим строку по 7 символов и, с помощью полученных кодов и кодовой таблицы ASCII (7 bit), декодируем приватный мини-ключ:
SCDYcWG5e1vusRtMcBrYQFKnCaUFLG
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
2a005846b5fcfaabf5cb24f7567ff748f834311f6e57d2923bd99ddce211b40d
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5J8nT2XXnwVh5WfSZgLTgCq5d3DvGqUzcYeyu4pb2qiaA8LmH4P
Который соответствует публичному адресу с 0.1170251 btc:
Пятый пазл 60$
Если вы меня спросите зачем я продолжаю, то я честно отвечу — не знаю. Возможно, это проф. деформация и HODL делает свое дело, возможно, на рынке сейчас паника и нужно чем-то себя занять, возможно, кто-нибудь попробовал решить конкретный пазл, у него не получилось и он бы был рад увидеть решение именно для своего пазла.
С чего начнем? Первое, за что быстро цепляется взгляд, это повторение узора через каждые 5 строк. Итого 5 * 48 = 240 элементов, по 240 : 30 = 8 элементов на каждый символ приватного мини-ключа.
Сразу же приходит в голову мысль, что пазл довольно пестрый (много цветов), т.е. основание системы счисления довольно большая цифра, на 1 символ приватного мини-ключа приходится аж 8 элементов, значит, должно быть много нулей, т.е. много повторяющихся элементов, как это было в предыдущем (четвертом) пазле. Но мы этого не замечаем. Напротив, если взять первую группу элементов, то мы увидим, что даже первые два элемента имеют уже разные цвета. Даже если взять первый элемент за ноль (если его принять за единицу и выше, то мы сразу выйдем за пределы допустимых значений), то второй будет минимум единицей. Также второй элемент является позицией шестого разряда (для числа из 8 цифр/элементов), что приводит нас к простой зависимости:
1 * M⁶ ≤ 127,
где M — мощность алфавита, или количество цифр в алфавите, или значение основания системы счисления (кому как удобнее).
При простой подстановке выходит:
2: 2⁶ = 64
3: 3⁶ = 729
Выходит, что единственной системой счисления может быть та, которая имеет основание 2 (а желтый цвет, цвет второго элемента, может обозначать только 1, т.к. если он будет обозначать 2, то 64 * 2 = 128, что уже больше 127, да и в алфавите двоичной системы счисления всего два знака: 0 и 1).
Как мы видим, цветов в пазле явно больше двух, а все знаки возможной системы счисления уже заняты. Что-то не сходится. Давайте попробуем посчитать количество цветов, чтобы хотя бы определиться с основанием системы счисления. В пазле можно найти: синий, желтый, серый, красный, светло-зеленый, темно-зеленый. Отлично, шесть цветов, значит, и основание 6. Но если присмотреться внимательнее, то в следующих 5 строках появляется ярко-красный цвет, а еще через 5 строк и ярко-желтый. Сама яркость повышается как бы градиентом от верха к низу.
Так 6 или 8? Вопрос интересный, можно попробовать перебрать разные варианты и пойти “в лобовую”. Но лень. Это надо перебивать кучу символов, писать код, не ошибиться в комбинаторике, потом все равно гадать, где ошибся — то ли в перебивке, то ли в алгоритме. Не хочется. Давайте смотреть дальше на картинку. Очевидно, что голубой цвет это 0. Просто потому, что его много, такой цвет у самого первого элемента и именно 0 скорее всего поможет нам остаться в диапазоне [0, 127], ведь в таком случае будет обнуляться старший разряд. Что еще интересно, что синий цвет довольно цикличен: если присмотреться, то он всегда будет первым в группе элементов по четыре:
Дальше давайте поделим на строки наш повторяющийся узор. Если каждый символ кодируется четырьмя элементами, то нам нужно 2 полных строки и первые 24 элемента из 3 строки (30 * 4 = 120 = 48 * 2 + 24):
И тут мы можем заметить, что ровно через 120 элементов (или 30 групп по 4 элемента), следующая, 31 группа, совпадает с первой группой:
Вторая и 32 группы тоже совпадают. Выходит, что в наших определенных изначально 5 строках, есть два повторения. Чтобы перестраховаться, пытаемся определить, есть ли какие-либо повторения в первых 30 группах элементов (120 элементов). Убеждаемся, что их нет. Получается, что изначально мы неправильно определили шаг повторения узора. Это объясняет, почему нет такого количества повторяющихся нулей. Если присмотреться, то такое повторение “в линию” 30 групп элементов создает новый, больший узор, который мы изначально и заметили. Но он оказался обманчивым, как и “вертикальные” узоры в первом пазле. Не знаю как для вас, но для меня звучит убедительно.
Теперь осталось определиться с количеством цветов. Не сложно заметить, что среди первых 120 элементов ни ярко-желтый, ни ярко-красный не появляются. Возможно, это своего рода подсказка, где искать границу повторения узора. Давайте попробуем взять систему счисления с основанием 6, а ярко-желтый и ярко-красный приравнять к обычным желтому и красному. Во всяком случае, такой шаг очевиднее и логичнее, как по мне.
Обозначим цвета:
Синий — b(lue)
Желтый — y(ellow)
Серный — g(rey)
Красный — r(red)
Светло-зеленый — l(ight-green)
Темно-зеленый — d(ark-green)
И перебьем первые 120 элементов:
bygrblbyblblbybrblgybyyyblbybyblbydyblgybgrgbgrrbgdrblbdblbybydlblbgbyybblyybgrlbyydbygrbydrblbdbgydbyrrbgrybgydbgrrblgg
Теперь нужно определиться, какой цвет что обозначает. Можно по-быстрому перебрать все варианты, но мы пойдем привычным путем. Для начала, запишем число 83 (код в десятичной системе счисления символа “S” в кодовой таблице кодировки ASCII (7 bit). Именно с этого символа должен начинаться приватный мини-ключ) в системе счисления с основанием 6:
83 : 6 = 13 (остаток 5)
13 : 6 = 2 (остаток 1)
2 : 6 = 0 (остаток 2)
215
Добавим незначащий ноль и сравним с первой группой из 4 элементов:
0215 = bygr
Принимаем:
b = 0
y = 2
g = 1
r = 5
Остается два цвета (светло-зеленый и темно-зеленый) и два значения 3 и 4. Возьмем следующую группу из 4 элементов:
blby = 0l02
Перепишем в развернутой форме:
0l02 =
= 2 * 6⁰ + 0 * 6¹ + l * 6² + 0 * 6³ =
= 36 * l + 2
Попробуем подставить последовательно 3 и 4:
3: 36 * 3 + 2 = 110 (“n”)
4: 36 * 4 + 2 = 146 (> 127)
Поскольку значение 146 выходит за возможные допустимые значения, значения цветов становятся однозначными, а нам, в отличие от предыдущего примера, повезло и не пришлось перебирать 10 групп элементов:
b = 0
y = 2
g = 1
r = 5
l = 3
d = 4
Теперь делим строку по 4 символа и, с помощью полученных кодов и кодовой таблицы ASCII (7 bit), декодируем приватный мини-ключ:
SnoMtVnKbtCGApncmTzEXSep4kD4Gs
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
f328af1da84271c144ed27196a3e8e659b6051f725403c7806c6d266dccb7407
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5KfNkSeQwNgjHr7cRErzDmq5XdUm8qc94YM3iEN5YaMYoA2UGky
Который соответствует публичному адресу с 0.14054367 btc:
Шестой пазл 70$
В шестом пазле мы сразу можем заметить множество белых элементов. Участвует 7 цветов:
Белый — w(hite)
Темно-синий — b(lue)
Светло-синий — c(yan)
Темно-зеленый — g(reen)
Светло-зеленый — l(light-green)
Темно - серый — g(rey)
Светло-серый — (light-gr)e(y)
Основание системы счисления — семь — что коррелируется с ценой пазла (20$ — двоичная, 30$ — троичная, 40$ — четверичная, 50$ — пятеричная, 60$ — шестеричная, 70$ — семеричная).
С графической точки зрения тоже все просто: повторяющийся узор через каждые 5 строк (5 * 48 = 240 элементов), видно четкое разделение на группы по 8 элементов (по 8 элементов для каждого из 30 символов приватного мини-ключа), где последние 3 элемента являются значащими:
Попробуем определить значения каждого цвета. Напомню, что приватный мини-ключ должен начинаться с символа “S”, который имеет код 83 (в десятичной системе счисления) в кодовой таблице кодировки ASCII (7 bit). Для начала перепишем цвета последних трех элементов первой группы и переведем число 83 из десятичной системы счисления в семеричную:
83 : 7 = 11 (остаток 6)
11 : 7 = 1 (остаток 4)
1 : 7 = 0 (остаток 1)
146 = bdl
Несложно догадаться, что:
Алфавит = [0, 1, 2, 3, 4, 5, 6]
w = 0
b = 1
d = 4
l = 6
c = ?
e = ?
g = ?
Что делать дальше? Можно перебрать возможные варианты. Но … лень. Давайте попробуем включить голову. Для трехзначного числа xyz в семеричной системе счисления развернутая форма записи будет выглядеть следующим образом:
xyz =
= z * 7⁰ + y * 7¹ + x * 7² =
= 49 * x + 7 * y + 1 * z
Давайте посмотрим в каких разрядах встречаются пока неизвестные нам цвета. Голубой (c) встречается в нулевом, первом и втором разрядах. Светло-серый (e) и темно-серый (g) в нулевом и первом разрядах. Если бы голубой цвет кодировал цифру 5, то во втором разряде он давал бы число 49 * 5= 245, что явно больше 127. Если бы было закодировано число 3, то во втором разряде мы бы получали 49 * 3 = 147, что тоже больше 127. Выходит, что c = 2. Для e и g у нас остаются цифры 3 и 5. Давайте возьмем значащие элементы из второй группы элементов:
cec = 2e2 =
= 2 * 7⁰ + e* 7¹ + 2 *7² =
= 2 + 7 * e + 98 =
= 7 * e + 100
Попробуем подставить последовательно значения 3 и 5:
3: 7 * 3 + 100 = 121 (“y”)
5: 7 * 5 + 100 = 135 ( >127)
Становится очевидным, что
w = 0
b = 1
d = 4
l = 6
c = 2
e = 3
g = 5
Перебиваем значащие 3 элемента каждой из 30 групп по 8 элементов (почему я не сделал тоже самое с черными элементами из четвертого пазла?!):
bdlcecbdbbbwbwebllbgwbdecclcbdccbceebggbbwbcebwecwbbglcewccebwdccebccbwdbwdcewcwlbcgcwlbge
Теперь делим строку по 4 символа и, с помощью полученных кодов и кодовой таблицы ASCII (7 bit), декодируем приватный мини-ключ:
SyN84aTPvmqzY8B4cZws5sA55whDhW
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
525b7532dff252b7283d3b26d8c7b7891c509ce264a3567a408594e7dc861386
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5JSZHc5RtPYkj5uxD6b66pn257r2vDWKGnMTjCvMQ6GCvA24NB5
Который соответствует публичному адресу с 0.164 btc:
Седьмой пазл 80$
Как мы видим, участвует 8 цветов:
Белый — w(hite)
Черный — b(lack)
Светло-синий — c(yan)
Синий — bl(ue)
Темно-синий — d(ark-blue)
Розовый — p(ink)
Красный — r(ed)
Бордовый — m(aroon)
С графической точки зрения мы можем увидеть зрительное разделение на группы по 6 элементов, которые начинаются с элемента синего цвета. На шестой группе элементов наша закономерность ломается, т.к. эта группа начинается уже со светло-синего цвета. От верха к низу снова идет градиент яркости. Пытаться зрительно определить где узор начинает повторяться, мне кажется затруднительным из-за большого количества цветов и градиента яркости. Давайте попробуем записать развернутую форму числа abcdef с основанием 7:
abcdef =
= f * 8⁰ + e * 8¹ + d * 8² + c * 8³ + b * 8⁴ + a * 8⁵ =
= 32768 * a + 4096 * b + 512 * c + 64 * d + 8 * e + 1 * f
Как вы можете заметить, после второго разряда должны быть нули, иначе мы выйдем за предел диапазона [0, 127], но графически мы этих нулей не видим. Все это нам намекает на то, что группу по 6 элементов стоит разделить на две группы по 3 элемента. Тогда через 15 групп по 6 элементов должно случиться повторение узора и он действительно начинает повторяться:
Попробуем определить значения каждого цвета. Напомню, что приватный мини-ключ должен начинаться с символа “S”, который имеет код 83 (в десятичной системе счисления) в кодовой таблице кодировки ASCII (7 bit). Для начала перепишем цвета первых трех элементов первой группы и переведем число 83 из десятичной системы счисления в восьмеричную:
83 : 8 = 10 (остаток 3)
10 : 8 = 1 (остаток 2)
1 : 8 = 0 (остаток 1)
upm = 123
Несложно догадаться, что:
Алфавит = [0, 1, 2, 3, 4, 5, 6, 7]
w = ?
b = ?
c = ?
u = 1
d = ?
p = 2
r = ?
m = 3
Если вспомнить запись для первых трех разрядов,
64 * d + 8 * e + 1 * f
то становится очевидным, что во втором разряде могут быть только цифры 0 или 1, ведь уже при d = 2 наше число будет больше 127 (64 * 2 = 128 > 127). Единственный цвет, который стоит во втором разряде кроме синего, это светло-синий (c), а поскольку цифра 1 уже занята, то:
Алфавит = [0, 1, 2, 3, 4, 5, 6, 7]
w = ?
b = ?
c = 0
u = 1
d = ?
p = 2
r = ?
m = 3
Дальше встает резонный вопрос, что делать. У нас есть 4 неопределенных цвета элемента. Можно попробовать действовать привычным образом: брать группы элементов с одним неизвестным цветом, писать развернутую форму и методом последовательных исключений определять цвета, но … лень. Нет, я серьезно (да-да, в прошлые разы мне было лень решать пазл по-другому, а теперь лень так). И на это есть несколько рациональных причин: во-первых, сам по себе метод хоть и работает, но дает осечки, и на примере четвертого пазла это было хорошо видно, когда нам пришлось перебрать 10 групп элементов подряд, прежде чем мы смогли однозначно понять значения цветов. Во-вторых, группы довольно маленькие (по 3 элемента, т.е. всего 3 разряда, где в старшем всегда 1 или 0 (синий или голубой цвета)), и значения могут оказаться близкими, например, для третьей группы:
ubm = 1b3 =
= 1 * 8² + b * 8¹ + 3 * 8⁰ =
= 67 + 8 * b
4: 67 + 8 * 4 = 99 (“c”)
5: 67 + 8 * 5 = 107 (“k”)
6: 67 + 8 * 6 = 115 (“s”)
7: 67 + 8 * 7 = 123 (“{“)
В таком случае придется перебирать несколько групп, составлять системы уравнений, а где-то и все равно перебирать “втупую”. В-третьих, групп с одним неизвестным цветом не так и много, значит, системы уравнений будут усложняться, как и зависимости, и шансы нарваться на неопределенность и впустую потратить время увеличиваются. Все это сказывается на скорости решения. С одной стороны, перебор позволяет почти моментально найти ответ, но можно ошибиться в коде и часами гулять вокруг трех сосен (и об этом мы поговорим позднее), с другой стороны, вручную и ошибиться можно, и количество затрачиваемого времени растет с увеличением количества вариантов, но некоторые закономерности зрительно быстрее прослеживаются или появляются новые идеи, да и ошибки, как правило, находятся быстрее. Но не стоит забывать, что мы все-таки не домашнее задание решаем, а соревнуемся со всем миром за драгоценные биточки.
Придется вспомнить комбинаторику. У нас есть 4 значения, которые не могут повторяться в одном варианте/строке: если один цвет кодирует цифру 4, то другой ее уже кодировать не может, иначе либо основание системы счисления должно быть меньше, чтобы повторяющиеся цвета могли существовать, либо диапазон значений будет урезан и все числа в таком случае представить не получится (хотя и при одинаковых значениях разных цветов все равно методом перебора в этих пазлах можно найти пустые приватные мини-ключи). В комбинаторике это называется перестановкой. Чтобы найти количество возможных перестановок нужно вычислить факториал количества элементов n:
P = n!
P = 4! = 1 * 2 * 3 * 4 = 24
Наши 24 варианта:
[4, 5, 6, 7],
[4, 5, 7, 6],
[4, 6, 5, 7],
[4, 6, 7, 5],
[4, 7, 5, 6],
[4, 7, 6, 5],
[5, 4, 6, 7],
[5, 4, 7, 6],
[5, 6, 4, 7],
[5, 6, 7, 4],
[5, 7, 4, 6],
[5, 7, 6, 4],
[6, 4, 5, 7],
[6, 4, 7, 5],
[6, 5, 4, 7],
[6, 5, 7, 4],
[6, 7, 4, 5],
[6, 7, 5, 4],
[7, 4, 5, 6],
[7, 4, 6, 5],
[7, 5, 4, 6],
[7, 5, 6, 4],
[7, 6, 4, 5],
[7, 6, 5, 4]
Теперь перебиваем цвета первых 90 элементов:
upmcwrubmcwdubwcwmuwwupmuwmudccwmubpurmupwuwwudcurpupdupruduupwuwrubpudpuwwupbupbucrurduuc
Подставлять значения будем следующим образом:
[b, w, d, r]
c = 0
u = 1
p = 2
m = 3
Фильтруем все варианты, где либо не попадаем в набор base58check, либо выходим за диапазон ASCII (7 bit) и получаем 2 адреса:
S5c7f3vSsx3bkVvxjWUyVubzvTTEoH при [4, 6, 7, 5]
S4k7n3vSsx3jcVvxbWTyVtjzvUUDgH при [5, 6, 7, 4]
На самом деле, сразу нужно фильтровать и на значение хеша алгоритма SHA-256 от строки “приватный_мини_ключ” + “?”. Напомню, что такой хеш должен начинаться с двух нулей, но тогда бы в результатах ничего не осталось, т.к.:
SHA-256(S5c7f3vSsx3bkVvxjWUyVubzvTTEoH?) = 73d2e504ab659d4ce336939570880a3c883469a18885c0e2daa1d18e3d2b4a03
SHA-256(S4k7n3vSsx3jcVvxbWTyVtjzvUUDgH?) =d7a7db79c2f6b40829ac288f22e68355ee9b182c5adf7b57393a4de855576ad0
Я же до последнего надеялся на “вдруг” и, конечно же, нарвался на пустые адреса:
Естественно, я несколько раз перепроверил корректность набранной строки, потом алгоритма, потом повторил все это еще несколько раз, потанцевал с бубном и снова потерпел неудачу.
Тут-то и стоит поговорить об ошибке в коде. Нет, у меня все было хорошо, кроме одного момента. На самом деле я поленился вспомнить комбинаторику и по-быстрому накидал варианты перестановок вручную. Придумал я всего 12 вариантов, вместо 24 и получил, соответственно, всего один адрес вместо двух. Я несколько раз перепроверил все, кроме количества вариантов перестановок. И этот просчет отправил меня в дивное путешествие по придумыванию всех степеней извращенности человеческой логики.
Первым делом я подумал, что где-то я мог в одной из групп элементов промахнуться, даже не смотря на расчерчивание всего рисунка на небольшие группы и их нумерацию, и написал перебор для ошибки в одном из символов. Снова провал. Потом я подумал, что темно-синий очень похож на черный и я мог где-то ошибиться. Перебрал разные варианты замены (+ перебор с ошибкой в 1 из символов). Облом. Потом я подумал, что светло-синий тоже можно спутать с синим. Как вы понимаете, все эти варианты и их комбинации я перебирал с усердием. Ничего не вышло.
Потом я подумал, что ошибиться в комбинациях, заменах и перестановках очень легко, а розовый можно спутать с красным или красный с бордовым и все усложнится еще сильнее. До меня дошло, что раз у нас есть градация яркости, то можно найти цвета, в которых я сомневаюсь, в следующих 90 символах, где яркость будет сильнее, сравнить, и тогда ошибиться будет сложнее. Для наглядности я решил нарезать узор на 90 символов и располагать каждую такую вырезку друг под другом. Как только я это сделал 2 раза, сомнение в правильности определения цветов вначале пропало, а потом его появилось еще больше. Дело в том, что в двух местах цвета двух элементов отличались.
Поскольку я не знал, то ли это фотография реального лего и так мог упасть свет при фотографировании, то ли это компьютерная графика и это очередная часть пазла, я решил продолжить нарезать узоры друг за другом. В какой-то момент я плюнул, поскольку таких косяков больше не встречалось и начал пробовать различные варианты с этими “косяками”. Вначале я попробовал 4 комбинации (2 неправильные группы одновременно в строке, 2 правильные группы, неправильная + правильная, правильная + неправильная), но снова остался с носом. Потом я пробовал менять все одинаковые правильные/неправильные группы элементов на неправильные/правильные группы элементов, различные сочетания и так далее. Не вышло.
Дальше у меня ничего не оставалось, кроме как продолжать нарезать строку за строкой. Биткоин все равно падал, да и сдаваться не хотелось. И на 13 строке я снова нашел отклонение. Заметил я его, правда, на 15 строке, но не суть. В итоге я решил нарезать весь рисунок до конца.
Как можно увидеть, у нас есть целых 4 отклонения от нормальной последовательности. За нормальную последовательность я взял для примера 7 строку. Дальше начался пытливый бездумный перебор всего и вся. Ничего не получалось. Очевидно, что такие 4 отклонения не просто так внесены в пазл и должна быть какая-то логика. Мне это не давало покоя. Какие варианты я только не придумывал и какую логику только не пытался найти. Что-то вроде “все бордовые элементы в третьей позиции должны быть заменены на красные” было самым безобидным. Но все упиралось в один странный момент. В первую группу. Если подумать логически и перестать пользоваться мощностью современного процессора, то при смене местами розового и бордового цветов, меняется и значение этих двух цветов (напомню, последовательность должна соответствовать кодовому слову 123). А это приводит к серьезным последствиям. И самое главное, что при ump = 123 не получается подобрать такую комбинацию из “4”, “5”, “6” и “7”, чтобы мы вписались в base58check.
Логика начала усложняться: а что если менять везде, кроме первого символа? Или вдруг это не первый, а второй символ, ведь первый всегда должен быть “S” и его, в принципе-то, можно было и не кодировать. Тогда нам нужно первые 29 символов прибавлять к “S”, а это значит, что все предыдущие сочетания и комбинации придется проверить еще раз. И мне стало снова лень. Но бросать не хотелось. Логично, что все это сложно, неоднозначно и утомительно. Должно быть как-то проще, более однозначно, но и учесть отклонения в решении тоже как-то нужно. Я решил перебить седьмую (любую строку без отклонений) еще раз:
upmcwrubmcwdubwcwmuwwupmuwmudccwmubpurmupwuwwudcurpupdupruduupwuwrubpuupuwwupbupbucrurduuc
И перебрать все комбинации из тех 12, что я составил. Ничего не вышло, а проблема первого символа мне не давала покоя. И тут меня осенило, а что если комбинаций больше? И действительно, их оказалось 24, а не 12. Первым делом я решил попробовать новые комбинации на последовательности без отклонений и о чудо, при
b = 5
w = 6
d = 7
r = 4
u = 1
c = 0
m = 3
p = 2
Мы получаем новый приватный мини-ключ:
S4k7n3vSsx3jcVvxbWTyVtjJvUUDgH
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
ce3ffcff9e9ee5f568e8025731fd6a29dc4a42833a1dc83acbde62edd58d52a4
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5KP7xcvojoJe1qRpC7BBdp4oFzAWuAwqe2ajZ5TNaSv3hxT87cS
Который соответствует публичному адресу с 0.1875 btc:
Больше всего в этот момент я обрадовался тому, что мне больше не нужно выдумывать зловещие комбинации и вникать в непостижимую логику, извращаясь все сильнее и сильнее. Также это хороший пример того, как с помощью небольших изменений “левой пяткой” даже простой и очевидный пазл можно сделать трудоемким для взлома. Нет, я не про ошибку в количестве комбинаций, а про модуляцию цветов. Для чего здесь были допущены ошибки, остается тайной, покрытой мраком. Первые две строки могли быть такими, чтобы пришлось перебрать чуть больше строк. А вот зачем есть изменения в 13 и 26 строках для меня остается секретом. По идее, туда никто даже и не дошел бы. Если у вас есть идеи, буду рад их почитать.
Восьмой пазл 90$
Первое, что бросается в глаза, это большое количество повторяющихся элементов синего цвета. Всего участвует 9 цветов:
Белый — w(hite)
Красный — r(ed)
Бордовый — m(aroon)
Синий — b(lue)
Голубой — c(yan)
Серый — g(rey)
Светло-серый — l(ight-grey)
Зеленый — (gr)e(en)
Хаки — (k)h(aki)
Можно заметить зрительное разделение на группы по 9 элементов: 6 синих элементов + 3 элемента разных цветов. Узор начинает повторяться через 270 элементов:
Несложно посчитать, что 270 : 9 = 30 групп элементов. Из 30 знаков состоит приватный мини-ключ биткоина. Поскольку первые 6 элементов в группе из 9 элементов всегда синего цвета, мы будем рассматривать как группу подмножество из последних 3 элементов.
Давайте проверим, совпадает ли последовательность цветов в повторяющихся узорах (все терзания и возможные страдания можно почитать в описании решения седьмого пазла. Там я собрал все возможные подводные). Для этого нарежем последовательно группы элементов следующим образом:
Как мы видим, в первом, втором и седьмом повторениях у нас есть отклонения в 28, 8 и 21 группах соответственно. За правильную строку мы возьмем любую, в которой таких отклонений нет. Например, третью.
Для того, чтобы закодировать 128 значений ASCII (7 bit) в девятеричной системе счисления, длина строки должна равняться трем (9^L ≥ 128, при L = 2 получится закодировать только 81 уникальное значение, при L = 3–729 значений).
Приватный мини-ключ должен начинаться с символа “S”, который имеет код 83 (в десятичной системе счисления) в кодовой таблице кодировки ASCII (7 bit). Переведем число 83 в систему счисления с основанием 9 и приравняем полученную запись к первой группе элементов:
83 : 9 = 9 (остаток 2)
9 : 9 = 1 (остаток 0)
1 : 9 = 0 (остаток 1)
102 = gbh
Несложно догадаться, что
Алфавит = [0, 1, 2, 3, 4, 5, 6, 7, 8]
b = 0
g = 1
h = 2
w = ?
r = ?
m = ?
c = ?
l = ?
e = ?
Теперь у нас остается 5 цветов, значения которых пока неизвестны. Для учебных целей и собственного удовольствия можно составить системы уравнений и с помощью таблицы кодов кодировки ASCII (7 bit) вычислять значение каждого цвета.
Но поскольку мы соревнуемся с целым миром за драгоценные биточки, мы воспользуемся перебором. У нас есть шесть уникальных значений (3, 4, 5, 6, 7, 8), каждое из которых должно присутствовать в строке и не повторяться. В комбинаторике это называется перестановкой. Количество перестановок вычисляется по формуле:
P = n!,
где n — количество элементов
Для нашего случая:
P = 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720
С вашего позволения я не буду печатать тут все возможные комбинации.
Теперь настраиваем фильтры: значение каждой группы элементов должно не просто укладываться в диапазон ASCII (7 bit) [0–127], но и в base58check. Также при хешировании функцией SHA-256 строки “приватный_мини_ключ” + “?”, хеш должен начинаться с двух нулей.
Перебиваем цвета 30 групп элементов:
gbhgmcghcgbbbrbgeeghgblwbrhbccgehbcmghrgbrgmhbwhbrwbcmgecgglgbbgerbcwgeegbgbrmblhblrblcbrb
И методом перебора всех возможных комбинаций узнаем, что единственной комбинацией, удовлетворяющей нашим фильтрам, является:
b = 0
g = 1
h = 2
w = 6
r = 8
m = 4
c = 5
l = 7
e = 3
Которой соответствует приватный-мини ключ:
SzhQHodEJ2n1kYw8N1qaQt3oRLAGDH
Хешируем приватный мини-ключ с помощью SHA-256 и получаем приватный ключ, записанный в шестнадцатеричной системе счисления (hex):
a763fede8c0f7f14ea772f98a6be5e6fa98450afcb73787d0b922015b8f003cc
Переводим полученное значение в base58check и получаем привычный нам приватный ключ:
5K61MFPg7srcEe3WGdpTc2ttbQbymRNJMy8ijHRPqnfTVhH6HAE
Который соответствует публичному адресу с 0.2108 btc:
Как видите, пазлы оказались однотипными. Суммы выигрышей не всегда соответствуют сложности. Но это отличный пример того, насколько мобильна криптовалюта. Только подумайте, вы можете закодировать любую сумму денег во что угодно, оставить это на самом видном месте и в любой момент времени из любой точки земного шара получить свои деньги обратно. Так называемое “value” никогда не было настолько мобильным и неуловимым. Это настоящее чудо 21 века и смена парадигмы. Мир сам по себе становится мобильнее, а с криптовалютами мобильным становится и ваше “value”.
