-1

是否可以解密 Peter Weinberger 的哈希算法？

我正在尝试编写自己的加密解密函数。我理解哈希值意味着您不能或不应该解密哈希值的概念，但我认为因为算法相对简单，在这种情况下可能可以解密这种哈希值。我已经完成了使用简单旋转的简单加密解密，现在我想尝试一些更困难的事情。

那么是否可以解密彼得温伯格哈希算法产生的哈希值呢？

以下加密函数是 Peter Weinberger 的精确哈希算法，解密是我自己的尝试，但不起作用：

int encrypt(char *s)
{
    /* Peter Weinberger's */

    char *p;
    unsigned int h, g;
    h = 0;
    for(p=s; *p!='\0'; p++){
        h = (h<<4) + *p; printf("Step : ");
        if (g = h&0xF0000000) {
            h ^= g>>24;
            h ^= g;
        }
    }
    return h % 211;
}

std::string decrypt(int v)
{
    /* Peter Weinberger's */

    unsigned int h, g;
    h = 0;
    v /= 211;
    int s = sqrt(v);

    /* Not sure what to do here
    for(p=s; *p!='\0'; p++){

    }
    */

    return string(h);
}
4

2 回答 2

3

考虑到极小的输出大小，蛮力攻击是微不足道的。

  1. 生成一个字符串（例如随机）
  2. 哈希它
  3. 如果它与已知值匹配，则您找到了第一个原像，否则转到步骤 1

这将平均需要 211 次尝试才能获得与给定哈希匹配的字符串。它可能不是原始字符串，但考虑到散列的有损性质，这是可以预料的。

对于两个字符输入，此哈希变为(16*s[0]+s[1])%211您可以重写为(16*(s[0]-'A')+(s[1]-'A') + 50)%211

求解你得到的字符串：

s[0]=(hash+161)/16+'A';
s[1]=(hash+161)%16+'A';

例如为s == "AB"你得到hash==51. 然后使用上面的公式来反转它：

s[0] = 13 +'A' = 'N'
s[1] =  4 +'A' = 'E'

=>s="NE"匹配哈希 51，但不是原始字符串。

于 2013-01-12T10:01:04.517 回答
0

如果我正确理解算法，对于每个字符它都会：

  1. 将哈希乘以 16（向左移动 4 位）
  2. 添加字符串的一个字符
  3. 如果结果超过 28 位，则删除高 4 位并在散列中的某处对它们进行异或。

通过将字符串的大小限制为 6（如果第一个字节小于 16，则为 7），步骤 3 将永远不会发生。所以剩下的就是一个简单的移位和加法。

当字符串有 6 个字符时，最终结果是这个和（h = 一个字符的高 4 位，l = 低 4 位）：

pos: bits
0: .hl00000
1: ..hl0000
2: ...hl000
3: ....hl00
4: .....hl0
5: ......hl
----------- +
   0*******  Result is 32 bits with upper 4 bits zero

我们看到 24-27 位是由位置 0 处字符的高 4 位确定的，加上低位加法可能产生的进位。位 20-23 是 char 0 的低位和 char 1 的高位（加上可能的进位）的总和。

如果输入字符可以具有所有 255 个可能的值（零除外），那么创建一个生成散列的字符串并不难。

  1. 查看哈希中的最高 4 位。这将是 pos 0 处角色的高位部分。
  2. 查看散列中的下 4 位。这是 char 1 的高位部分和 char 0 的低位部分的相加。
  3. 为最高部分选择一个值。例如“最高部分始终为零”或“最高部分始终为 0100（大写字母）”。
  4. 如果 has 中的位小于您在步骤 3 中选择的值，请从前面的位中借一些（如果这些位为零，则将其复制到下一个位组）。
  5. 现在你有了 char 0 的下半部分和 char 1 的上半部分。
  6. 回到第 2 步获取接下来的 4 位，直到到达哈希的末尾
  7. 检查字符串中是否没有值为 0 的字符。

代码会有点复杂，因为存在各种边缘情况（例如哈希 01000000），并留给读者作为练习；）。

编辑：我完全错过了h % 211手术。正如 CodesInChaos 演示的那样，这使它变得更加容易。

于 2013-01-12T10:23:49.917 回答