LINUX.ORG.RU

Дед Мороз решил создать свою криптовалюту

 


0

3

Дед Мороз решил создать свою криптовалюту MorozCoin (очень похожую на Bitcoin), дабы использовать в качестве подарков экономически продвинутым девочкам и мальчикам, и ему требуется помощь.

Чтобы помочь ему, требуется найти хеши MD5, которые в шестнадцатиричном виде начинаются как минимум с семи нулей. На вход функции хеширования подаётся строка «moroz» (без кавычек), конкатенированная с числом в десятичной записи. Чтобы намайнить Деду Морозу его валюту, вам нужно найти ему минимальное положительное число (без ведущих нулей: 1, 2, 3, ...), которое даёт удовлетворяющий вышеописанному условию хеш.

Реализуйте описанный майнер на вашем любимом языке программирования.



Последнее исправление: a1batross (всего исправлений: 1)

ты, что не в курсе, что дед Мороз - коммунист, и вертел он ваши коины? Дед Мороз дает подарки только за пятёрки.

record ★★★★★
()
Последнее исправление: record (всего исправлений: 1)
#!/usr/bin/env python3
from hashlib import md5

number = 1
while True:
    hash = md5()
    hash.update(b'moroz')
    hash.update(bytes(str(number), 'ascii'))
    digest = hash.hexdigest()
    if digest.startswith('0000000'):
        print('FOUND: moroz{}: {}'.format(number, digest))
    number += 1

Никто же не говорил, что майнер должен быть эффективный. Особенно если ты на самом деле чей-то пароль там подбираешь.

proud_anon ★★★★★
()
Последнее исправление: proud_anon (всего исправлений: 1)
Ответ на: комментарий от proud_anon

Тот, кто хеширует пароли с помощью MD5 в 2015-ом году - уже по определению ССЗБ.

ТСу стоит посмотреть в сторону радужных таблиц.

KivApple ★★★★★
()
Ответ на: комментарий от proud_anon

Особенно если ты на самом деле чей-то пароль там подбираешь.

Пароль я бы брутфорсил с помощью oclhashcat, учитывая то, что теперь он опенсорсный.

leakyleaf
() автор топика
Ответ на: комментарий от proud_anon

Никто же не говорил, что майнер должен быть эффективный

Довольно эффективный получился. Около минуты заняло под pypy.

$ perl -E 'print "moroz" . "1" x 69628591;' | md5sum 
0000000cc42372ba917e1e73ed1a790f  -
i-rinat ★★★★★
()

Дед Мороз решил создать свою криптовалюту

А царь разрешил?

somequest
()

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

I-Love-Microsoft ★★★★★
()

Siberian Mouse. For Neko.

anonymous
()
Ответ на: комментарий от proud_anon

Второй вариант. Он же быстрее — не надо создавать контекст каждый раз.

Твой код я тоже попробовал. Он за минут 10 отрабатывает, не так уж и долго.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Второй вариант. Он же быстрее — не надо создавать контекст каждый раз.

А ведь это мысль, да.

proud_anon ★★★★★
()
Ответ на: комментарий от loz

Чет я не понял, ты число из едениц получил, но оно же явно не минимальное?

Так ведь никто не просил минимальное. Тем более, если это криптовалюта, надо много разных чисел.

proud_anon ★★★★★
()

Хешик нашел «0000000247AFF955D8A274FE4BED2D3F», число забыл распечатать)

(ql:quickload "ironclad")
(ql:quickload "flexi-streams")

(defmacro element-zerop (array index)
  `(zerop (aref ,array ,index)))

(defun is-good-hash (hash)
  (declare (optimize (speed 3) (debug 0) (safety 0))
           (array hash))
  (and (element-zerop hash 0)
       (element-zerop hash 1)
       (element-zerop hash 2)
       (< (aref hash 3) #x10)))

(defun search-loop (&optional (start 0))
  (declare (optimize (speed 3) (debug 0) (safety 0)))
  (loop for i = start then (incf i)
     with hash
     do (progn
          (setf hash (ironclad:digest-sequence :md5
                      (flexi-streams:string-to-octets
                       (concatenate 'string "moroz" (write-to-string i)))))
          (when (is-good-hash hash)
            (return (list i hash))))))

loz ★★★★★
()
Ответ на: комментарий от loz

Ах да, не заметил. Но мой код у меня нашёл за полтора часа на pypy3 четыре числа:

FOUND: moroz321966836: 0000000247aff955d8a274fe4bed2d3f
FOUND: moroz540995235: 0000000b251e58ff1a9f5461436fed48
FOUND: moroz950376463: 00000009a3e84a2b8686fa180b553b0a
FOUND: moroz962557611: 00000005b2f6b22a53da2738e9870f81
Значит, минимальное — 321966836.

proud_anon ★★★★★
()
Ответ на: комментарий от loz

вам нужно найти ему минимальное положительное число

А нужно ли им это на самом деле?

anonymous
()
Ответ на: комментарий от proud_anon

А если усложнить.
FOUND: moroz321966836: 0000000247aff955d8a274fe40000000
вот это получить типа и с начала и с конца (просто спрот. интерес)

pvvking ★★
()
Последнее исправление: pvvking (всего исправлений: 1)
Ответ на: комментарий от kiotoze

Нееееет нееееет неееет мааааам ну нееееет.

Dron ★★★★★
()
Ответ на: комментарий от pvvking

А если усложнить.

Ещё семь нулей это 28 бит. Если предположить, что хеш даёт равномерное распределение бит, а скорость обработки одного хеша не вырастет (а она вырастет, то есть это оценка снизу), то задача усложняется в 2^28 раз. За полтора часа найдено 4 решения, то есть среднее время поиска составило 0,375 часа. Если всё перемножить и поделить, выходит одиннадцать с половиной тысяч лет.

Не надо усложнять.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

А, если просто пропробывать то что наступит типа 20160101 в начале и конце, то тогда только те, кто на сатурн будут ездить просто так на такси только могут посчитать. И то при огромном оптимизме валюты Деда морозаp

pvvking ★★
()

Надо параллельное решение еще

-module(moroz).

-compile([export_all]).

go(Workers, Start) when is_integer(Workers), is_integer(Start) ->
  {NewInit, Size} = make_workers(Workers, Start),
  main_loop(NewInit, Size).

main_loop(CurrentInit, Size) ->
  receive
    {stop, Pid} ->
      To = CurrentInit+Size,
      Pid ! {CurrentInit, To},
      main_loop(To, Size);
    {found, Hash, N} ->
      io:format("hash found!!: ~p / ~p~n", [N, Hash]),
      main_loop(CurrentInit, Size)
  end.

make_workers(N, Start) -> make_workers(N, Start, 500000).
make_workers(N, Start, Size) ->
  Init = lists:foldl(fun(_, Acc) ->
                         To = Acc+Size,
                         make_worker(Acc, To),
                         To
                     end, Start, lists:seq(0, N-1)),
  {Init, Size}.

make_worker(Init, Stop) -> spawn(moroz, worker_init, [self(), Init, Stop]).

worker_init(Parent, Init, Stop) ->
  %% io:format("worker started: ~p -> ~p~n", [Init, Stop]),
  worker_loop(Parent, Init, Stop).

worker_loop(Parent, Stop, Stop) ->
  Parent ! {stop, self()},
  receive
    {NewCurrent, NewStop} ->
      %% io:format("new task: ~p -> ~p", [NewCurrent, NewStop]),
      worker_loop(Parent, NewCurrent, NewStop)
  end;

worker_loop(Parent, Current, Stop) ->
  Hash = crypto:hash(md5, "moroz" ++ integer_to_list(Current)),
  case binary:part(Hash, {0, 4}) of
    <<0,0,0,X:8,_/binary>> when X < 16#10 ->
      Parent ! {found, Hash, Current};
    _ -> ok
  end,
  worker_loop(Parent, Current+1, Stop).
loz ★★★★★
()
Последнее исправление: loz (всего исправлений: 1)
Ответ на: комментарий от i-rinat

Вон эрланговый вариант довольно шустро ищет, на моих 4х ядрах, например)

loz ★★★★★
()

Ждем варианта на GPU.

loz ★★★★★
()
Ответ на: комментарий от loz

Где тут меняют хешики на бабло?

hash found!!: 1218544621 / <<0,0,0,12,224,85,239,87,202,189,59,196,38,94,26,223>>
hash found!!: 1630552252 / <<0,0,0,10,190,168,165,85,253,244,130,183,9,118,18,169>>
hash found!!: 2780934506 / <<0,0,0,14,163,94,244,103,4,89,191,26,209,64,254,162>>
hash found!!: 3579877286 / <<0,0,0,7,133,152,91,149,20,217,105,203,216,152,230,36>>
hash found!!: 4628136237 / <<0,0,0,7,124,108,161,6,226,25,10,179,29,117,88,148>>
loz ★★★★★
()
Последнее исправление: loz (всего исправлений: 1)
Ответ на: комментарий от i-rinat

За полтора часа найдено 4 решения

Параллельный вариант нашел за пол часа все что в моем сообщении.

loz ★★★★★
()
Ответ на: комментарий от anonymous

Это был код для adventofcode, там две части — 5 и 6 ведущих нулей (и персональный префикс).

Для местного варианта:

  \t 0N!{15<16/:4#-15!"moroz",$x}(1+)/0
321966836
681581

Минимальный суффикс — 321966836, нашли за ~11.5 минут (681581 миллисекунду).

anonymous
()
Ответ на: комментарий от loz

Конечно, задача идеально параллелится. Но сколько ты готов вложить денег в поиск решения?

i-rinat ★★★★★
()
Ответ на: комментарий от loz

Полный код решения. На встроенном в kdb+ языке k.

(kdb+ запускается в режиме интерпретации q. Переключение в k и обратно — бекслеш (\) с переводом строки)

anonymous
()
package main

import (
	"crypto/md5"
	"encoding/hex"
	"fmt"
)

func numDigits(n int) int {
	num := 1
	for n > 9 {
		n /= 10
		num++
	}
	return num
}

func toBytes(n int, p []byte) {
	l := len(p) - 1
	for {
		r := n % 10
		p[l] = "0123456789"[r]
		n /= 10
		if n == 0 {
			break
		}
		l--
	}
}

func main() {
	var buf [16]byte
	n := copy(buf[:], "moroz")
	h := md5.New()
	for i := 1; i < 9999999999; i++ {
		m := numDigits(i)
		toBytes(i, buf[n:n+m])
		h.Reset()
		h.Write(buf[:n+m])
		sum := h.Sum(nil)
		if sum[0] == 0 && sum[1] == 0 && sum[2] == 0 && sum[3]&0xf0 == 0 {
			fmt.Printf("%s %s\n", buf[:n+m], hex.EncodeToString(sum))
			break
		}
	}
}


$ time ./moroz  
moroz321966836 0000000247aff955d8a274fe4bed2d3f

real    2m6.908s
user    2m12.632s
sys     0m1.016s

anonymous
()
var crypto = require('crypto');
var moroz  = 'moroz';
var detect = '0000000';

console.log('Start minner => '+Date());

for (var count = 0; count < 9999999999999; count++)
{
    var hash = crypto.createHash('md5').update((moroz+count)).digest('hex');

    if(hash.substr(0,7) === '0000000')
    {
        console.log(Date());
        console.log("FOUND: hash =>"+hash+" [moroz"+count+"]");
    };
}
dron@gnu:~$ node moroz.js 
Start minner => Sat Dec 12 2015 22:51:34 GMT+0300 (MSK)
Sat Dec 12 2015 23:08:11 GMT+0300 (MSK)
FOUND: hash =>0000000247aff955d8a274fe4bed2d3f [moroz321966836]
Dron ★★★★★
()
Ответ на: комментарий от Dron

Больше какакода ::)


#include <stdio.h>
#include <stdlib.h>
#include <openssl/md5.h>
#include <string.h>

int main()
{
    long int i;
    MD5_CTX md5handler;
    unsigned char md5digest[MD5_DIGEST_LENGTH];
    char toostrbuff[100];
    long int len;
    MD5_Init(&md5handler);

    system("echo Start minner ;date");
    for (long long int count = 0; count < 99999999999; count++)
    {
        sprintf(toostrbuff,"%i",count);
        len = strlen(toostrbuff);
        MD5_Update(&md5handler, "moroz", 5);
        MD5_Update(&md5handler, toostrbuff, len);
        MD5_Final(md5digest,&md5handler);



        sprintf(toostrbuff,"%02x",md5digest[0]);
        if(strcmp(toostrbuff,"00")!=0) goto go_new;
        sprintf(toostrbuff,"%02x",md5digest[1]);
        if(strcmp(toostrbuff,"00")!=0) goto go_new;
        sprintf(toostrbuff,"%02x",md5digest[2]);
        if(strcmp(toostrbuff,"00")!=0) goto go_new;
        sprintf(toostrbuff,"%02x",md5digest[3]);
        if(toostrbuff[0]!='0') goto go_new;




        printf("FOUNT HASH => ");
        for (i=0; i<MD5_DIGEST_LENGTH; i++)
        {
            printf("%02x",md5digest[i]);
        };
        printf("\n");
        go_new:;
    }

    return 0;
};



dron@gnu:~$ gcc moroz.c -lcrypto
dron@gnu:~$ ./a.out 
Start minner
Вс дек 13 02:00:22 MSK 2015
FOUNT HASH => 0000000b72869f54b00b15a8f24f222b
^C
Dron ★★★★★
()
Последнее исправление: Dron (всего исправлений: 1)
Ответ на: комментарий от Dron

А почему просто не сравнить md5digest[n] с нулем? Зачем эти sprintf?

anonymous
()
Ответ на: комментарий от Dron

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

Ох лол :D

Deleted
()
Ответ на: комментарий от Deleted

Хеш тоже неправильный, поскольку контекст MD5 не ресетится.

anonymous
()
{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE OverloadedStrings #-}

import           Crypto.Hash.MD5
import           Data.ByteString.Builder
import qualified Data.ByteString.Lazy    as B
import           Data.String

main :: IO ()
main = print $ findIt (1::Word)
  where hexHash = toLazyByteString . byteStringHex . hash
        findIt !x | b x = x
                  | otherwise = findIt (x+1)
        b !x = B.isPrefixOf "0000000" $ hexHash $ a x
        a !x = fromString $ "moroz" ++ show x

Вот.
И да, я тоже считаю что ТС следовало-бы указать на источник задачи (http://adventofcode.com/day/4)

Deleted
()
Ответ на: комментарий от anonymous

На самом деле мне следовало-бы его пересмотреть перед тем как сюда постить.

Deleted
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.