Сторнирование функции ha sh - PullRequest
Новая
       18

Сторнирование функции ha sh

3 голосов
/ 24 марта 2020

У меня есть следующая функция, которая хеширует a string: 

public static uint hashString(string myString)
{
     uint hash = 0;

     foreach (char c in myString)
     {
         hash *= 0x1F;
         hash += c;
     }

     return hash;
}

Так что, если я захочу ха sh hello, она выдаст 99162322.

Можно ли написать реверс , который принимает number и выплевывает string (учитывая, что string результат равен неизвестно )

Ответы [ 2 ]

3 голосов
/ 24 марта 2020

Поскольку вы не используете cryptographi c га sh, ваша реализация легко реверсирует (т.е. возвращает некоторые string, которые имеет значение га sh)

код: 

public static uint hashString(string myString) {
  //DONE: validate public methods' parameters
  if (null == myString)
    return 0;

  uint hash = 0;

  //DONE: hash function must never throw exceptions
  unchecked {
    foreach (char c in myString) {
      hash *= 0x1F;
      hash += c;
    }
  }

  return hash;
}

private static string HashReverse(uint value) {
  StringBuilder sb = new StringBuilder();

  for (; value > 0; value /= 31) 
    sb.Append((char)(value % 31));

  return string.Concat(sb.ToString().Reverse());
}

Демо: (учитывая hash мы производим string и вычислите hash, чтобы проверить) 

uint[] tests = new uint[] {
  99162322,
  123,
  456
};

// Since the string can contain control characters, let's provide its Dump
string Dump(string value) => string.Join(" ", value.Select(c =>((int) c).ToString("x4")));

string report = string.Join(Environment.NewLine, tests
  .Select(test => new { 
    test,
    reversed = HashReverse(test)
  })
  .Select(item => $"{item.test,9} :: {Dump(item.reversed),-30} :: {hashString(item.reversed),9}"));

Console.WriteLine(report);

Результат: 

 99162322 :: 0003 000e 000b 0012 0012 0012  ::  99162322
      123 :: 0003 001e                      ::       123
      456 :: 000e 0016                      ::       456

Пожалуйста, обратите внимание, что много string выдает то же га sh значение (скажем, "hello" и мое "\u0003\u000e\u000b\u0012\u0012\u0012")

1 голос
/ 24 марта 2020

Нет.

Одним из фундаментальных моментов хеширования является то, что оно необратимо.

Есть много строк, которые будут иметь значение 99162322, поэтому, хотя можно было бы найти их все (с учетом максимальной длины строки), но не было бы способа определить, какая из них была «правильной» .

...