使用C#中的默认哈希函数生成三个具有相等哈希值的不同字符串。

huangapple go评论64阅读模式
英文:

Generating three distinct strings with equal hashes using the default hash function in C#

问题

我正在尝试生成三个不同的字符串,分别为 A、B 和 C,使它们的哈希值都相等,使用编程语言提供的默认哈希函数。具体来说,我需要确保 A 不等于 B,B 不等于 C,以及 A 不等于 C。

我尝试了几种方法,但尚未成功找到解决方案。我正在寻求帮助来实现一个可以满足这些要求的方法或算法。非常关键的一点是,这三个字符串的哈希值都必须相同。

以下是我的实现,但它仍然不完整,因为前两个字符串发生了冲突,但第三个字符串没有冲突。

var dictionary = new Dictionary<int, string>();

int collusionCounter = 0, stringCounter = 0;
string myString;
int hash = 0;

List<string> myList = new List<string>();

while (true)
{
    stringCounter++;
    myString = stringCounter.ToString();

    try
    {
        hash = myString.GetHashCode();
        dictionary.Add(hash, myString);
    }
    catch (Exception)
    {
        if (dictionary.ContainsKey(hash))
        {
            myList.Add(myString);
            collusionCounter++;
            if (collusionCounter == 2)
            {
                break;
            }
        }
        continue;
    }
}

var A = myList[0];
var B = myList[1];
var C = dictionary[hash];

Console.WriteLine($"{A.GetHashCode()} {B.GetHashCode()} {C.GetHashCode()}");

以下是实现的结果:

374545419 1954295680 1954295680

我将不断尝试寻找满足您要求的解决方案。谢谢!

【注意】:您的实现仍然存在问题,因为A和B的哈希值不相等,只有B和C的哈希值相等。要解决这个问题,您可能需要重新考虑算法的设计。

英文:

I am trying to generate three distinct strings, A, B, and C, such that their hash values are all equal using the default hash function provided by the programming language. Specifically, I need to ensure that A is not equal to B, B is not equal to C, and A is not equal to C.

I have tried several approaches but haven't been successful in finding a solution yet. I am seeking assistance to implement a method or algorithm that can fulfill these requirements. It's crucial that the hash values of all three strings are the same.

Here is my implementation, however, it is still incomplete because I have a collision with the first two strings but not with the third one.

var dictionary = new Dictionary&lt;int, string&gt;();

  int collusionCounter = 0, stringCounter = 0;
  string myString;
  int hash = 0;

  List&lt;string&gt; myList = new List&lt;string&gt;();


  while (true)
  {
    stringCounter++;
    myString = stringCounter.ToString();

    try
    {
      hash = myString.GetHashCode();
      dictionary.Add(hash, myString);
    }
    catch (Exception)
    {
      if (dictionary.ContainsKey(hash))
      {
        myList.Add(myString);
        collusionCounter++;
        if (collusionCounter == 2)
        {
          break;
        }
      }
      continue;
    }
  }

  var A = myList[0];
  var B = myList[1];
  var C = dictionary[hash];

  Console.WriteLine($&quot;{A.GetHashCode()} {B.GetHashCode()} {C.GetHashCode()}&quot;);

And hier is a result of implementation :

374545419 1954295680 1954295680

I would appreciate any guidance or insights on how to achieve this task effectively. Thank you!

答案1

得分: 5

.NET中的字符串哈希码不稳定,这意味着每次运行程序时,特定字符串的哈希码都不同。哈希码仅在程序的单次执行期间保持稳定。.NET的这个特性可能会破坏您尝试的目标,但让我们假设.NET中的字符串哈希码是稳定的,并尝试在此假设下找到您问题的答案。

你可能能够在数学上找到3个不同的字符串具有相同的哈希码,方法是了解生成哈希码的算法并进行逆向工程。这可能并非不切实际,因为哈希码不是用于加密安全的,因此可能可以逆向工程。但我无法在这个方向上提供帮助,因为我不是数学家。

我建议采用一种蛮力概率方法来解决这个问题。.NET的哈希码是32位数字,因此如果你有2 ^ 32 + 1(4,294,967,297)个元素的集合,可以保证你会得到至少一个碰撞。你需要一个能够产生比这个数字更多独特字符串的字符串生成器。一个好的选择似乎是生成8个小写拉丁字符的所有排列,其种群空间为26 ^ 8 = 208,827,064,576个字符串。平均来说,大约有 ~48 个字符串将共享相同的哈希码,因此如果你随机选择一个与其他2个不发生碰撞的字符串,你将非常不幸。找到3个字符串的算法如下:

  1. 将第一个生成的字符串添加到列表a中,并将其哈希码存储在变量b中。
  2. 开始一个循环,在每次迭代中生成下一个字符串,并将其哈希码与b进行比较。如果值相等,将生成的字符串添加到列表a中。
  3. 当列表a中有3个字符串时退出循环。这些字符串是不同的,并且它们共享相同的哈希码。

我预计在大约80亿次循环后会得到您的结果。

英文:

String hashcodes in .NET are not stable, meaning that a specific string has different hashcode each time you run a program. Hashcodes are stable only during a single execution of a program. This .NET feature probably undermines what you are trying to do, but let's assume that string hashcodes in .NET were stable, and try to find an answer to your question under this assumption.

You might be able to find 3 different strings having the same hashcode mathematically, by knowing the algorithm that produces the hashcode and reverse-engineering it. This might not be unrealistic because hashcodes are not meant to be cryptographicaly secure, so reverse-engineering them might be feasible. But I can't help you in this direction because I am not a mathematician.

I'll suggest a brute-force probabilistic approach for solving this problem. .NET hashcodes are 32 bit numbers, so it's guaranteed that you'll get at least one collision if you have a set of 2 ^ 32 + 1 (4,294,967,297) elements. You will need a generator of strings that can produce more unique strings than this number. A good candidate seems to be a generator of all permutations of 8 lower-case Latin characters, with a population space of 26 ^ 8 = 208,827,064,576‬ strings. On average ~48 strings will share the same hashcode, so you will be very unlucky if you pick randomly a string that doesn't collide with 2 others. The algorithm to find the 3 strings goes like this:

  1. Add the first generated string in a list a, and store its hashcode in a variable b.
  2. Start a loop where in each iteration you generate the next string, and compare its hashcode with the b. If the values are equal add the generated string in the list a.
  3. Exit the loop when you have 3 strings in the list a. These strings are different, and they share the same hashcode.

I would expect to have your result after about 8 billion iterations of the loop.

huangapple
  • 本文由 发表于 2023年5月28日 06:24:20
  • 转载请务必保留本文链接:https://go.coder-hub.com/76349282.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定