fork download
copy 
  1. <?php
  2.  
  3. function word_by_index($index, $dicts) {
  4.     $sizes = array_map(function($val){return count($val);}, $dicts); // получаем размеры каждого словаря
  5.     $result = '';
  6.     foreach($sizes as $key=>$size) {
  7.         $result .= $dicts[$key][$index % $size]; // сцепляем слово из частей
  8.         $index = floor($index / $size);
  9.     }
  10.     return $result;
  11. }
  12.  
  13. function R($hash, $dicts, $total) {
  14.     $index = gmp_intval(gmp_mod(gmp_init($hash, 16), $total));
  15.     return word_by_index($index, $dicts); 
  16. }
  17.  
  18. function make_chain($start, $length, $dicts, $total) {
  19.     $chain['start'] = $start;
  20.     for($i = 0; $i < $length; ++$i) {
  21.         $hash = md5($start);                    // <-- сюда вставьте нужную хэш-функцию
  22.         // echo ">>> $hash : $start\n";            // диагностическое сообщение
  23.         $start = R($hash, $dicts, $total);
  24.     }
  25.     $chain['end'] = $hash;
  26.     echo "Chain from ${chain['start']} to ${chain['end']} is ready.\n"; // диагностическое сообщение
  27.     return $chain;
  28. }
  29.  
  30. function make_chains($count, $length, $dicts) {
  31.     $sizes = array_map(function($val){return count($val);}, $dicts); // получаем размеры каждого словаря
  32.     $total = array_reduce($sizes, function($carry,$item){return $carry*$item;}, 1); // произведение размеров словарей
  33.     $chains = [];
  34.     mt_srand();
  35.     for($i = 0; $i < $count; ++$i) {
  36.         $word = word_by_index(mt_rand(0, $total - 1), $dicts);  // начинаем цепочку с псевдослучайного слова
  37.         $chain = make_chain($word, $length, $dicts, $total);
  38.         $hash = $chain['end'];                               // используем конец найденной цепочки как индекс для быстрого поиска
  39.         if(!isset($chains[$hash])) $chains[$hash] = [];      // если такого хэша не было в корзине, инициализируем её
  40.         if(!in_array($chain['start'], $chains[$hash])) {     // проверяем на дубли
  41.             $chains[$hash][] = $chain['start'];              // добавляем начало цепочки в корзину
  42.         }
  43.     }
  44.     return $chains;
  45. }
  46.  
  47. function find_hash_in_basket($needle, $haystack_start, $haystack_end, $dicts, $total) {
  48.     echo "Роемся в цепочке от $haystack_start до $haystack_end.\n";       // диагностическое сообщение
  49.     $current_word = $haystack_start;
  50.     do {
  51.         $current_hash = md5($current_word);         // <-- сюда вставьте нужную хэш-функцию
  52.         if($current_hash === $needle) {
  53.              return $current_word;                  // нашли слово, хэш от которого равен заданному
  54.         }
  55.         $current_word = R($current_hash, $dicts, $total);  // роем в глубину
  56.     } while($current_hash !== $haystack_end);
  57.     return false; // не нашли
  58. }
  59.  
  60. function search_hash($hash, $dicts, $chains, $length) {
  61.     $sizes = array_map(function($val){return count($val);}, $dicts); // получаем размеры каждого словаря
  62.     $total = array_reduce($sizes, function($carry,$item){return $carry*$item;}, 1); // произведение размеров словарей
  63.     $current_hash = $hash;
  64.     for($i = 0; $i < $length; ++$i) {
  65.           if(isset($chains[$current_hash])) {                // нашли хэш в одной из корзин
  66.               echo "Лезем в корзину $current_hash.\n";       // диагностическое сообщение
  67.               foreach($chains[$current_hash] as $start) {    // роемся в корзине
  68.                   $result = find_hash_in_basket($hash, $start, $current_hash, $dicts, $total); // пытаемся найти в каждой из цепочек корзины
  69.                   if($result) {
  70.                       return $result;                        // конец поиска
  71.                   }
  72.               }
  73.           }
  74.           $next_word = R($current_hash, $dicts, $total);             // копаем в глубину
  75.           $current_hash = md5($next_word);
  76.     }
  77.     return false; // не нашли
  78. }
  79.  
  80. ///////////////////// ПРИМЕР //////////////////////////////////
  81.  
  82. $dicts= array(
  83.       array('свино',  'овце', 'тигро', 'косатко', 'зубро', 'волко', 'кото'),
  84.       array('собака', 'бык',  'лев',   'дельфин', 'бизон')
  85. );
  86.  
  87. $chains = make_chains(15, 15, $dicts);
  88. echo "Радужные таблицы готовы.\n";
  89. var_dump($chains);
  90.  
  91. $hash = '360629d3cf05cee0240a23e1251c58a0';
  92. echo "Пытаемся обратить $hash.\n";
  93. $word = search_hash($hash, $dicts, $chains, 15);
  94. echo "$hash is reversed to $word.\n";
  95.  
Success #stdin #stdout 0.02s 24532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Chain from овцесобака to 3283cdd8c6255dcded193a5b4a20a2bd is ready.
Chain from зубролев to ba7e22917c117379d199586a2cdeefe8 is ready.
Chain from зубрособака to 04695ee83f725f18a0fb876b56f4950f is ready.
Chain from косатколев to 34015e916ea500c831c8e75aa515db92 is ready.
Chain from зубродельфин to 01c681f4ecba27149eb566d595c71fcd is ready.
Chain from косаткодельфин to c368c543126e4acd98419c9e64a7fc5a is ready.
Chain from свинолев to c368c543126e4acd98419c9e64a7fc5a is ready.
Chain from волкодельфин to 6f2e4e3025c9dd840f1fa4a78792ef31 is ready.
Chain from свинодельфин to 04695ee83f725f18a0fb876b56f4950f is ready.
Chain from волкобизон to c368c543126e4acd98419c9e64a7fc5a is ready.
Chain from тигробык to 04695ee83f725f18a0fb876b56f4950f is ready.
Chain from овцебизон to 46bd910a586555f5f99ca385396ebb7e is ready.
Chain from тигрособака to 360629d3cf05cee0240a23e1251c58a0 is ready.
Chain from косаткодельфин to c368c543126e4acd98419c9e64a7fc5a is ready.
Chain from котобык to 360629d3cf05cee0240a23e1251c58a0 is ready.
Радужные таблицы готовы.
array(9) {
  ["3283cdd8c6255dcded193a5b4a20a2bd"]=>
  array(1) {
    [0]=>
    string(20) "овцесобака"
  }
  ["ba7e22917c117379d199586a2cdeefe8"]=>
  array(1) {
    [0]=>
    string(16) "зубролев"
  }
  ["04695ee83f725f18a0fb876b56f4950f"]=>
  array(3) {
    [0]=>
    string(22) "зубрособака"
    [1]=>
    string(24) "свинодельфин"
    [2]=>
    string(16) "тигробык"
  }
  ["34015e916ea500c831c8e75aa515db92"]=>
  array(1) {
    [0]=>
    string(20) "косатколев"
  }
  ["01c681f4ecba27149eb566d595c71fcd"]=>
  array(1) {
    [0]=>
    string(24) "зубродельфин"
  }
  ["c368c543126e4acd98419c9e64a7fc5a"]=>
  array(3) {
    [0]=>
    string(28) "косаткодельфин"
    [1]=>
    string(16) "свинолев"
    [2]=>
    string(20) "волкобизон"
  }
  ["6f2e4e3025c9dd840f1fa4a78792ef31"]=>
  array(1) {
    [0]=>
    string(24) "волкодельфин"
  }
  ["46bd910a586555f5f99ca385396ebb7e"]=>
  array(1) {
    [0]=>
    string(18) "овцебизон"
  }
  ["360629d3cf05cee0240a23e1251c58a0"]=>
  array(2) {
    [0]=>
    string(22) "тигрособака"
    [1]=>
    string(14) "котобык"
  }
}
Пытаемся обратить 360629d3cf05cee0240a23e1251c58a0.
Лезем в корзину 360629d3cf05cee0240a23e1251c58a0.
Роемся в цепочке от тигрособака до 360629d3cf05cee0240a23e1251c58a0.
360629d3cf05cee0240a23e1251c58a0 is reversed to свинособака.
https://ideone.com/otdCDg
language:
PHP (php 7.3.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!