6

我正在尝试开发一个在彩虹表生成器中使用的缩减函数。

归约函数背后的基本原理是它接受一个散列，执行一些计算，并返回一个特定长度的字符串。

目前我正在使用 SHA1 哈希，我需要返回一个长度为 3 的字符串。我需要由以下任意三个随机字符组成的字符串：

abcdefghijklmnopqrstuvwxyz0123456789

我面临的主要问题是我编写的任何归约函数总是返回已经生成的字符串。一个好的归约函数很少会返回重复的字符串。

任何人都可以就实现这一目标的方式提出任何想法吗？或者任何关于哈希到字符串操作的建议都会很棒。

提前致谢

乔什

4

2 回答 2

6

所以听起来你有 20 位基数 255（SHA1 哈希的长度）需要映射到基数 36 的三位数字。我只需从哈希字节、模数 36^3 和返回以 36 为基数的字符串。

public static final BigInteger N36POW3 = new BigInteger(""+36*36*36));
public static String threeDigitBase36(byte[] bs) {
  return new BigInteger(bs).mod(N36POW3).toString(36);
}
// ...
threeDigitBase36(sha1("foo")); // => "96b"
threeDigitBase36(sha1("bar")); // => "y4t"
threeDigitBase36(sha1("bas")); // => "p55"
threeDigitBase36(sha1("zip")); // => "ej8"

当然会有碰撞，就像当你将任何空间映射到一个更小的空间时，但熵应该比比上述解决方案更愚蠢的东西要好。

于 2012-02-19T21:50:58.207 回答
4

应用KISS原则：

  • SHA 只是一个字符串
  • 的 JDK 哈希码String“足够随机”
  • Integer可以在任何基础上渲染

这行代码就可以做到：

public static String shortHash(String sha) {
    return Integer.toString(sha.hashCode() & 0x7FFFFFFF, 36).substring(0, 3);
}

注意：& 0x7FFFFFFF符号位为零（哈希码可以是负数，否则会以负号开头）。

编辑 - 保证哈希长度

我最初的解决方案是幼稚的——它没有处理int哈希小于100（base 36）的情况——这意味着它会打印少于 3 个字符。此代码修复了该问题，同时仍保持值“随机”。它还避免了substring()调用，因此性能应该更好。

static int min = Integer.parseInt("100", 36);
static int range = Integer.parseInt("zzz", 36) - min;

public static String shortHash(String sha) {
    return Integer.toString(min + (sha.hashCode() & 0x7FFFFFFF) % range, 36);
}

100此代码通过强制它介于和之间来保证最终哈希具有 3 个字符zzz- 以 36 为基数的最低和最高 3 字符哈希，同时仍使其“随机”。

于 2012-02-19T22:48:54.523 回答